优化算法——牛顿法(Newton Method)

一、牛顿法概述

    除了前面说的梯度下降法,牛顿法也是机器学习中用的比较多的一种优化算法。牛顿法的基本思想是利用迭代点

处的一阶导数(梯度)和二阶导数(Hessen矩阵)对目标函数进行二次函数近似,然后把二次模型的极小点作为新的迭代点,并不断重复这一过程,直至求得满足精度的近似极小值。牛顿法的速度相当快,而且能高度逼近最优值。牛顿法分为基本的牛顿法和全局牛顿法。

二、基本牛顿法

1、基本牛顿法的原理

2、基本牛顿法的流程

三、全局牛顿法

    牛顿法最突出的优点是收敛速度快,具有局部二阶收敛性,但是,基本牛顿法初始点需要足够“靠近”极小点,否则,有可能导致算法不收敛。这样就引入了全局牛顿法。

1、全局牛顿法的流程

2、Armijo搜索   

四、算法实现

    实验部分使用Java实现,需要优化的函数

最小值为

1、基本牛顿法Java实现

package org.algorithm.newtonmethod;

/**
 * Newton法
 * 
 * @author dell
 * 
 */
public class NewtonMethod {
	private double originalX;// 初始点
	private double e;// 误差阈值
	private double maxCycle;// 最大循环次数

	/**
	 * 构造方法
	 * 
	 * @param originalX初始值
	 * @param e误差阈值
	 * @param maxCycle最大循环次数
	 */
	public NewtonMethod(double originalX, double e, double maxCycle) {
		this.setOriginalX(originalX);
		this.setE(e);
		this.setMaxCycle(maxCycle);
	}

	// 一系列get和set方法
	public double getOriginalX() {
		return originalX;
	}

	public void setOriginalX(double originalX) {
		this.originalX = originalX;
	}

	public double getE() {
		return e;
	}

	public void setE(double e) {
		this.e = e;
	}

	public double getMaxCycle() {
		return maxCycle;
	}

	public void setMaxCycle(double maxCycle) {
		this.maxCycle = maxCycle;
	}

	/**
	 * 原始函数
	 * 
	 * @param x变量
	 * @return 原始函数的值
	 */
	public double getOriginal(double x) {
		return x * x - 3 * x + 2;
	}

	/**
	 * 一次导函数
	 * 
	 * @param x变量
	 * @return 一次导函数的值
	 */
	public double getOneDerivative(double x) {
		return 2 * x - 3;
	}

	/**
	 * 二次导函数
	 * 
	 * @param x变量
	 * @return 二次导函数的值
	 */
	public double getTwoDerivative(double x) {
		return 2;
	}

	/**
	 * 利用牛顿法求解
	 * 
	 * @return
	 */
	public double getNewtonMin() {
		double x = this.getOriginalX();
		double y = 0;
		double k = 1;
		// 更新公式
		while (k <= this.getMaxCycle()) {
			y = this.getOriginal(x);
			double one = this.getOneDerivative(x);
			if (Math.abs(one) <= e) {
				break;
			}
			double two = this.getTwoDerivative(x);
			x = x - one / two;
			k++;
		}
		return y;
	}

}

2、全局牛顿法Java实现

package org.algorithm.newtonmethod;

/**
 * 全局牛顿法
 * 
 * @author dell
 * 
 */
public class GlobalNewtonMethod {
	private double originalX;
	private double delta;
	private double sigma;
	private double e;
	private double maxCycle;

	public GlobalNewtonMethod(double originalX, double delta, double sigma,
			double e, double maxCycle) {
		this.setOriginalX(originalX);
		this.setDelta(delta);
		this.setSigma(sigma);
		this.setE(e);
		this.setMaxCycle(maxCycle);
	}

	public double getOriginalX() {
		return originalX;
	}

	public void setOriginalX(double originalX) {
		this.originalX = originalX;
	}

	public double getDelta() {
		return delta;
	}

	public void setDelta(double delta) {
		this.delta = delta;
	}

	public double getSigma() {
		return sigma;
	}

	public void setSigma(double sigma) {
		this.sigma = sigma;
	}

	public double getE() {
		return e;
	}

	public void setE(double e) {
		this.e = e;
	}

	public double getMaxCycle() {
		return maxCycle;
	}

	public void setMaxCycle(double maxCycle) {
		this.maxCycle = maxCycle;
	}

	/**
	 * 原始函数
	 * 
	 * @param x变量
	 * @return 原始函数的值
	 */
	public double getOriginal(double x) {
		return x * x - 3 * x + 2;
	}

	/**
	 * 一次导函数
	 * 
	 * @param x变量
	 * @return 一次导函数的值
	 */
	public double getOneDerivative(double x) {
		return 2 * x - 3;
	}

	/**
	 * 二次导函数
	 * 
	 * @param x变量
	 * @return 二次导函数的值
	 */
	public double getTwoDerivative(double x) {
		return 2;
	}

	/**
	 * 利用牛顿法求解
	 * 
	 * @return
	 */
	public double getGlobalNewtonMin() {
		double x = this.getOriginalX();
		double y = 0;
		double k = 1;
		// 更新公式
		while (k <= this.getMaxCycle()) {
			y = this.getOriginal(x);
			double one = this.getOneDerivative(x);
			if (Math.abs(one) <= e) {
				break;
			}
			double two = this.getTwoDerivative(x);
			double dk = -one / two;// 搜索的方向
			double m = 0;
			double mk = 0;
			while (m < 20) {
				double left = this.getOriginal(x + Math.pow(this.getDelta(), m)
						* dk);
				double right = this.getOriginal(x) + this.getSigma()
						* Math.pow(this.getDelta(), m)
						* this.getOneDerivative(x) * dk;
				if (left <= right) {
					mk = m;
					break;
				}
				m++;
			}
			x = x + Math.pow(this.getDelta(), mk)*dk;
			k++;
		}
		return y;
	}
}

3、主函数

package org.algorithm.newtonmethod;

/**
 * 测试函数
 * @author dell
 *
 */
public class TestNewton {
	public static void main(String args[]) {
		NewtonMethod newton = new NewtonMethod(0, 0.00001, 100);
		System.out.println("基本牛顿法求解:" + newton.getNewtonMin());

		GlobalNewtonMethod gNewton = new GlobalNewtonMethod(0, 0.55, 0.4,
				0.00001, 100);
		System.out.println("全局牛顿法求解:" + gNewton.getGlobalNewtonMin());
	}
}   

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏新智元

【榜单】计算机科学中最重要的32个算法

【新智元导读】 奥地利符号计算研究所(Research Institute for Symbolic Computation,简称RISC)的Christoph...

38770
来自专栏AI研习社

从聚合-转移框架浅谈卷积神经网络的架构设计

本次Paper Reading我们并没有关注某些特定的paper,而是用一个视角对现有的代表性的卷积神经网络设计进行总结。

14320
来自专栏AI2ML人工智能to机器学习

变分の美

变分法(Variational method)已经成为微积分后主流的分析工具, 在物理和应用数学有着极大的功能。 变分法的诞生起源于最强大的数学家家族两个兄弟之...

12510
来自专栏AI2ML人工智能to机器学习

一步一步走向锥规划 - LP

一般来说凸优化(Convex Optimization, CO)中最一般的是锥规划 (Cone Programming, CP) 问题, 前面我们介绍了最简单...

11220
来自专栏深度学习之tensorflow实战篇

R语言与机器学习学习笔记(分类算法

logistic回归及其MLE 当我们考虑解释变量为分类变量如考虑一个企业是否会被并购,一个企业是否会上市,你的能否考上研究生 这些问题时,考虑线性概率模型P...

52480
来自专栏自然语言处理

程序员眼中的统计学2

均值有两种计算方法:第一种计算方式是:将所有的数字加起来,然后除以数字的个数 。可用记为:µ=∑x/n。另一种计算方法是把每个数的频数考虑进去了的,它表示如下:...

9630
来自专栏素质云笔记

NLP+2vec︱认识多种多样的2vec向量化模型

1、word2vec 耳熟能详的NLP向量化模型。 Paper: https://papers.nips.cc/paper/5021-distributed...

66170
来自专栏华章科技

大数据等最核心的关键技术:32个算法

奥地利符号计算研究所(Research Institute for Symbolic Computation,简称RISC)的Christoph Koutsch...

11320
来自专栏大数据挖掘DT机器学习

R语言与机器学习(分类算法)logistic回归

由于我们在前面已经讨论过了神经网络的分类问题,如今再从最优化的角度来讨论logistic回归就显得有些不合适了。Logistic回归问题的最优化问题可以表述为:...

78740
来自专栏AI启蒙研究院

【读书笔记】之概率统计知识梳理

9230

扫码关注云+社区

领取腾讯云代金券