最优化理论与算法牛顿法

Ⅰ 什么是最优化

最优化是应用数学的一个分支，主要指在一定条件限制下，选取某种研究方案使目标达到最优的一种方法。最优化问题在当今的军事、工程、管理等领域有着极其广泛的应用。

常见方法：

1. 梯度下降法（Gradient Descent）

梯度下降法是最早最简单，也是最为常用的最优化方法。

梯度下降法实现简单，当目标函数是凸函数时，梯度下降法的解是全局解。一般情况下，其解不保证是全局最优解，梯度下降法的速度也未必是最快的。

梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向，因为该方向为当前位置的最快下降方向，所以也被称为是”最速下降法“。最速下降法越接近目标值，步长越小，前进越慢。

2. 牛顿法（Newton's Method）和拟牛顿法（Quasi-Newton Methods）

（1）牛顿法：

牛顿法是一种在实数域和复数域上近似求解方程的方法。方法使用函数f(x)的泰勒级数的前面几项来寻找方程f(x) = 0的根。牛顿法最大的特点就在于它的收敛速度很快。

（2）拟牛顿法：

拟牛顿法是求解非线性优化问题最有效的方法之一，其本质思想是改善牛顿法每次需要求解复杂的Hessian矩阵的逆矩阵的缺陷，它使用正定矩阵来近似Hessian矩阵的逆，从而简化了运算的复杂度。拟牛顿法和最速下降法一样只要求每一步迭代时知道目标函数的梯度。

通过测量梯度的变化，构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法更为有效。如今，优化软件中包含了大量的拟牛顿算法用来解决无约束，约束，和大规模的优化问题。

3. 共轭梯度法（Conjugate Gradient）

共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。

在各种优化算法中，共轭梯度法是非常重要的一种。其优点是所需存储量小，具有步收敛性，稳定性高，而且不需要任何外来参数。

4. 启发式优化方法

启发式方法指人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时,利用过去的经验，选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案。

启发式优化方法种类繁多，包括经典的模拟退火方法、遗传算法、蚁群算法以及粒子群算法等等。

5. 拉格朗日乘数法

作为一种优化算法，拉格朗日乘子法主要用于解决约束优化问题，它的基本思想就是通过引入拉格朗日乘子来将含有n个变量和k个约束条件的约束优化问题转化为含有（n+k）个变量的无约束优化问题。拉格朗日乘子背后的数学意义是其为约束方程梯度线性组合中每个向量的系数。

将一个含有n个变量和k个约束条件的约束优化问题转化为含有（n+k）个变量的无约束优化问题，拉格朗日乘数法从数学意义入手，通过引入拉格朗日乘子建立极值条件，对n个变量分别求偏导对应了n个方程，然后加上k个约束条件（对应k个拉格朗日乘子）一起构成包含了（n+k）变量的（n+k）个方程的方程组问题，这样就能根据求方程组的方法对其进行求解。

Ⅱ 2、牛顿法和最速下降法只能求解无约束优化，有约束的非线性规划有哪些求解方法

Data Mining

无约束最优化方法

梯度的方向与等值面垂直，并且指向函数值提升的方向。

二次收敛是指一个算法用于具有正定二次型函数时，在有限步可达到它的极小点。二次收敛与二阶收敛没有尽然联系，更不是一回事，二次收敛往往具有超线性以上的收敛性。一阶收敛不一定是线性收敛。

解释一下什么叫正定二次型函数：

n阶实对称矩阵Q，对于任意的非0向量X，如果有XTQX>0，则称Q是正定矩阵。

对称矩阵Q为正定的充要条件是：Q的特征值全为正。

二次函数，若Q是正定的，则称f(X)为正定二次函数。

黄金分割法

黄金分割法适用于任何单峰函数求极小值问题。

求函数在[a,b]上的极小点，我们在[a,b]内取两点c,d，使得a<c<d<b。并且有

1）如果f(c)<f(d)，则最小点出现在[a,d]上，因此[a,d]成为下一次的搜索区间。

2）如果f(c)>f(d)，则[c,b]成为下一次的搜索区间。

假如确定了[a,d]是新的搜索区间，我们并不希望在[a,d]上重新找两个新的点使之满足(1)式，而是利用已经抗找到有c点，再找一个e点，使满足：

可以解得r=0.382，而黄金分割点是0.618。

练习：求函数f(x)=x*x-10*x+36在[1,10]上的极小值。

+ View Code
最速下降法

泰勒级数告诉我们：

其中Δx可正可负，但必须充分接近于0。

X沿D方向移动步长a后，变为X+aD。由泰勒展开式：

目标函数：

a确定的情况下即最小化：

向量的内积何时最小？当然是两向量方向相反时。所以X移动的方向应该和梯度的方向相反。

接下来的问题是步长a应该怎么定才能使迭代的次数最少？

若f(X)具有二阶连续偏导，由泰勒展开式可得：

H是f(X)的Hesse矩阵。

可得最优步长：

g是f(X)的梯度矩阵。

此时：

可见最速下降法中最优步长不仅与梯度有关，而且与Hesse矩阵有关。

练习：求函数f(x1,x2)=x1*x1+4*x2*x2在极小点，以初始点X0=(1,1)T。

+ View Code
梯度下降法开始的几步搜索，目标函数下降较快，但接近极值点时，收敛速度就比较慢了，特别是当椭圆比较扁平时，收敛速度就更慢了。

另外最速下降法是以函数的一次近似提出的，如果要考虑二次近似，就有牛顿迭代法。

牛顿迭代法

在点Xk处对目标函数按Taylar展开：

令

得

即

可见X的搜索方向是，函数值要在此方向上下降，就需要它与梯度的方向相反，即。所以要求在每一个迭代点上Hesse矩阵必须是正定的。

练习：求的极小点，初始点取X=(0,3)。

+ View Code
牛顿法是二次收敛的，并且收敛阶数是2。一般目标函数在最优点附近呈现为二次函数，于是可以想象最优点附近用牛顿迭代法收敛是比较快的。而在开始搜索的几步，我们用梯度下降法收敛是比较快的。将两个方法融合起来可以达到满意的效果。

收敛快是牛顿迭代法最大的优点，但也有致命的缺点：Hesse矩阵及其逆的求解计算量大，更何况在某个迭代点Xk处Hesse矩阵的逆可能根本就不存在（即Hesse矩阵奇异），这样无法求得Xk+1。

拟牛顿法

Hesse矩阵在拟牛顿法中是不计算的，拟牛顿法是构造与Hesse矩阵相似的正定矩阵，这个构造方法，使用了目标函数的梯度（一阶导数）信息和两个点的“位移”（Xk-Xk-1）来实现。有人会说，是不是用Hesse矩阵的近似矩阵来代替Hesse矩阵，会导致求解效果变差呢？事实上，效果反而通常会变好。

拟牛顿法与牛顿法的迭代过程一样，仅仅是各个Hesse矩阵的求解方法不一样。

在远离极小值点处，Hesse矩阵一般不能保证正定，使得目标函数值不降反升。而拟牛顿法可以使目标函数值沿下降方向走下去，并且到了最后，在极小值点附近，可使构造出来的矩阵与Hesse矩阵“很像”了，这样，拟牛顿法也会具有牛顿法的二阶收敛性。

对目标函数f(X)做二阶泰勒展开：

两边对X求导

当X=Xi时，有

这里我们用Hi来代表在点Xi处的Hesse矩阵的逆，则

(5)式就是拟牛顿方程。

下面给出拟牛顿法中的一种--DFP法。

令

我们希望Hi+1在Hi的基础上加一个修正来得到：

给定Ei的一种形式：

m和n均为实数，v和w均为N维向量。

(6)(7)联合起来代入(5)可得：

下面再给一种拟牛顿法--BFGS算法。

(8)式中黑色的部分就是DFP算法，红色部分是BFGS比DFP多出来的部分。

BFGS算法不仅具有二次收敛性，而且只有初始矩阵对称正定，则BFGS修正公式所产生的矩阵Hk也是对称正定的，且Hk不易变为奇异，因此BFGS比DFP具有更好的数值稳定性。

Ⅲ 最优化理论与算法的图书目录

第1章引言
1.1学科简述
1.2线性与非线性规划问题
*1.3几个数学概
1.4凸集和凸函数
习题
第2章线性规划的基本性质
2.1标准形式及图解法
2.2基本性质
习题
第3章单纯形方法
3.1单纯形方法原理
3.2两阶段法与大M法
3.3退化情形
3.4修正单纯形法
*3.5变量有界的情形
*3.6分解算法
习题
第4章对偶原理及灵敏度分析
4.1线性规划中的对偶理论
4.2对偶单纯形法
4.3原始对偶算法
4.4灵敏度分析
*4.5含参数线性规划
习题
第5章运输问题
5.1运输问题的数学模型与基本性
5.2表上作业法
5.3产销不平衡运输问题
习题
第6章线性规划的内点算法
*6.1Karmarkar算法
*6.2内点法
6.3路径跟踪法
第7章最优性条件
7.1无约束问题的极值条件
7.2约束极值问题的最优性条件
*7.3对偶及鞍点问题
习题
*第8章算法
8.1算法概念
8.2算法收敛问题
习题
第9章一维搜索
9.1一维搜索概念
9.2试探法
9.3函数逼近法
习题
第10章使用导数的最优化方法
10.1最速下降法
10.2牛顿法
10.3共轭梯度法
10.4拟牛顿法
10.5信赖域方法
10.6最小二乘
习题
第11章无约束最优化的直接方法
11.1模式搜索法
11.2Rosenbrock方法
11.3单纯形搜索法
11.4Powell方法
习题
第12章可行方向法
12.1Zoutendijk可行方向法
12.2Rosen梯度投影法
*12.3既约梯度法
12.4Frank?Wolfe方法
习题
第13章惩罚函数法
13.1外点罚函数法
13.2内点罚函数法
*13.3乘子法
习题
第14章二次规划
14.1Lagrange方法
14.2起作用集方法
14.3Lemke方法
14.4路径跟踪法
习题
*第15章整数规划简介
15.1分支定界法
15.2割平面法
15.301规划的隐数法
15.4指派问
习题
第16章动态规划简介
16.1动态规划的一些基本概念
16.2动态规划的基本定理和基本方程
16.3逆推解法和顺推解法
16.4动态规划与静态规划的关系
16.5函数迭代法
习题
参考文献

Ⅳ 什么是高斯-牛顿算法

用于解无约束最优化问题的

在解非线性方程组时,处理困难.因此用一个线性逼近(我理解是相似).
具体可以看运筹学或者是最优化书籍相关章节.

如果你已经看过了，那我也无能为力

Ⅳ 非线性最优的方法

最优化方法是一种数学方法，它是研究在给定约束之下如何寻求某些因素(的量)，以使某一(或某些)指标达到最优的一些学科的总称。常见的最优化方法有梯度下降法、牛顿法和拟牛顿法、共轭梯度法等等。

Ⅵ 牛顿法求解无约束最优化问题的方法

1. B6公式是从B2对x求导得到的

2. pk是定义的方向，沿着负梯度方向，后面是证明这样确实是f(x)减小的方向。

   这些在《数值计算》这些书里都有。

Ⅶ 什么是高斯-牛顿算法 好像又有牛顿法，高斯法，牛顿-高斯法，找书也不好找啊

用于解无约束最优化问题的
在解非线性方程组时,处理困难.因此用一个线性逼近(我理解是相似).
具体可以看运筹学或者是最优化书籍相关章节.
如果你已经看过了,那我也无能为力

Ⅷ 最优化问题中，牛顿法为什么比梯度下降法求解需要的迭代次数更少

不过牛顿法对初值的要求更为严格，很容易得到局部极小值

Ⅸ 用MATLAB体现牛顿高斯最优化方法

《应用最优化方法及MATLAB实现》系统讲述如何将最优化方法实现为应用软件。系统阐述了各种无约束和带约束优化问题的计算方法和程序实现，内容包括：精确/非精确一维搜索、最速下降法、牛顿/拟牛顿法、共轭梯度法、单纯形法、内点法、积极集法、序列二次规划方法等。书中包含了必要的最优化理论知识，为得到最优化方法并用程序实现做准备。书中给出的许多应用优化技术是我们的最新研究成果，给出的优化程序是以专业编程技巧实现的最优化算法。书中还给出了大量的例子和习题。《应用最优化方法及MATLAB实现》可作为高等院校自动化、控制、系统工程、工业工程、计算机、应用数学、经济、管理、化工、材料、机械、能源等相关专业学生的教材，也可作为有关研究人员和工程技术人员的参考书。