工程优化第4章-1

最优性条件最速下降法牛顿法及其阻尼牛顿法共轭方向法共轭梯度法变尺度法（DFP算法和BFGS算法）第4章无约束最优化方法

求解（1），就是找中的一点，使对均有，称为(1)的全局极小点。

无约束最优化问题：求解(1)的计算方法称为无约束最优化方法。

无约束最优化方法应用广泛，理论也比较成熟；可将约束优化问题转化为无约束优化问题来处理；最优化方法中的基本方法---无约束优化方法：利用函数的一阶或二阶导数的方法收敛速度快，需要计算梯度或者Hesse矩阵：仅利用函数值的信息，寻找最优解不涉及导数，适用性强，但收敛速度慢可求得目标函数的梯度时使用解析法在不可能求得目标函数的梯度或偏导数时使用直接法本章介绍解析法最优性条件(OptimalityConditions)

所谓最优性条件，是指最优化问题的最优解所要满足的必要条件或充分条件。

这些条件对于最优化算法的建立和最优化理论的推导都是至关重要的。

解析法要用到目标函数的梯度或者Hesse矩阵，容易想到利用一阶必要条件将无约束优化问题转化成一个梯度为0确定的方程组。这里用到的一阶必要条件就是最优性条件。定理(一阶必要条件)

设，若为的局部极小点，且在内连续可微，则无约束优化的最优性条件----一阶必要条件

若为的局部极小点，且在内二次连续可微，则半正定。无约束优化的最优性条件----二阶必要条件定理（二阶必要条件）定理(二阶充分条件)

设若在内二次连续可微，且正定，则为的严格局部极小点。

如果负定，则为的严格局部极大点。无约束优化的最优性条件----二阶充分条件定理(一阶充要条件)

设是凸函数且在处连续可微，则为

的全局极小点的充要条件是无约束优化的最优性条件----凸优化的一阶条件定理(一阶必要条件)

设是严格凸函数且在处连续可微，若则为的唯一全局极小点。例：利用最优性条件求解下列问题：解：令即：得到驻点：无约束优化的最优性条件利用二阶条件判断驻点是否是极小点利用一阶条件求驻点函数的Hesse阵：在点处的Hesse阵依次为：无约束优化的最优性条件利用二阶条件判断驻点是否是极小点的行列式小于0；无约束优化的最优性条件是正定矩阵；是负定矩阵；是鞍点；是极小点；是极大点。对某些较简单的函数，这样做有时是可行的；但对一般n元函数f(x)来说，由条件

得到的是一个非线性方程组，解它相当困难。为此，常直接使用迭代法。(1)选定某一初始点，并令(2)确定搜索方向(3)从出发，沿方向求步长，以产生下一个迭代点(4)检查得到的新点是否为极小点或近似极小点。，转(2)继续进行迭代。

在以上步骤中，步长的选取可采用精确一维搜索或非精确一维搜索，下降方向的选取正是下面要介绍的，不同的下降方向，得到不同的算法。若是，则停止迭代。线搜索迭代法的步骤否则，令从而得到第k+1次迭代点，即步长由精确一维搜索得到。最速下降法负梯度方向这是函数值减少最快的方向假设f连续可微，最速下降法负梯度方向是函数值减少最快的方向？令是单位长度的向量，

P是什么方向时，函数值下降最快？也就是p是什么方向时，取得最小值？

当时，最小，最小值为，此时由可得

最速下降法是求多元函数极值的最古老的数值算法，早在1847年法国数学家Cauchy提出该算法，后来Curry作了进一步的研究。

该方法直观，简单，计算方便，而且后来的一些新的有效的方法大多数是对它的改进，或受它的启发而得到的。最速下降法(1)选定某一初始点，并令(2)若，否则转（3）；

由精确一维搜索确定最佳步长，最速下降法的迭代格式(3)令转（2）。算法框图x1,ε>0,k=1||▽f(xk)

||<ε?Yesstop.xk–解Nodk=－▽f(xk

)解minf(xk+λdk)s.t.λ>0得xk+1=xk+λkdkk=k+1最速下降法框图

例利用最速下降法求解令解：函数的梯度为第1次迭代：取得令得第2次迭代：令得第3次迭代：继续迭代可得到函数的近似最优解。最速下降法的收敛性分析

设f(x)连续可微，且水平集有界，则最速下降法或者在有限迭代步后终止；或者得到点列，它的任何聚点都是f(x)的驻点。

在收敛定理的假设下，若f(x)为凸函数，则最速下降法或在有限迭代步后达到最小点；或得到点列，它的任何聚点都是f(x)的全局最小点。收敛性定理：推论：

最速下降法在两个相邻点之间的搜索方向是正交的。最速下降法向极小点逼近是曲折前进的，这种现象称为锯齿现象。除特殊的目标函数和极特殊的初始点外，这种现象都会发生。令利用精确一维搜索，可得由此得出1.相邻两次迭代的方向互相垂直最速下降法的两个特征注：在最速下降法中，利用精确一维搜索求最佳步长，导致相邻两次迭代的搜索方向总是垂直的，使得逼近极小点过程是“之”字形，

这样从任何一个初始点开始，都可以很快到达极小点附近，但是越靠近极小点步长越小，移动越慢，导致最速下降法的收敛速度很慢。实际运用中，在可行的计算时间内得不到需要的结果。最速下降法收敛速度慢最速下降法的两个特征对正定二次函数，用最速下降法产生的点列：偶数项点列均在一条直线上，奇数项点列也均在一条直线上，且都过最优点.最速下降法的两个特征

对正定二次函数，用最速下降法产生的点列：偶数项点列均在一条直线上，奇数项点列也均在一条直线上，且都过最优点.

则分析：因为相邻方向正交，t与k有关

优点：理论明确，程序简单，每次的计算量小，所需的存

储量小，对初始点要求不严格。缺点：收敛速度并不快，因为最速下降方向仅仅是指某点

的一个局部性质。最速下降法相邻两次搜索方向的正交性，决定了迭代全

过程的搜索路线呈锯齿状，远快近慢。最速下降法的优缺点

最速下降法不是好的实用算法，但是一些有效算法

是通过对它的改进或利用它与其他收敛快的算法结合而得到的，因此它是无约束优化的基本方法之一。

为了清除最速下降法中两个搜索方向正交的不良后果，提出了许多改进的方法，如：(1)选择不同初始点

例令最速下降法的改进取初始点第1次迭代得然后再从开始新的迭代，经过10次迭代，得最优解

计算中可以发现，开始几次迭代，步长比较大，函数值下降将较快，但当接近最优点时，步长很小，目标函数值下降很慢。如果不取初点为而取一步就得到了极小点。

可见：造成锯齿现象与初始点的选择有关，但怎样选一个初始点也是一件困难的事。第1次迭代

虽然后一初始点较前一初始点离最优点远，但迭代中不出现锯齿现象。

采用非精确一维搜索求步长,

可使相邻两个迭代点处的梯度不正交，从而改变收敛性。

对于最速下降法，有时为了减少计算工作量，采用固定步长，称为固定步长最速下降法。

但

到底取多大，没有统一的标准，

取小了，收敛太慢，而取大了，又会漏掉极小点。（2）采用不精确的一维搜索：最速下降法的改进（3）采用加速梯度法：

由于最速下降法在极小点附近成“锯齿”状，因此下降过程中的搜索方向可取

下两步继续用最速下降方向即负梯度方向。

Shah等人于1964年提出了一种“平行切线法”（简记为PARTAN法），又称加速梯度法。最速下降法的改进负梯度方向和结合这两种方向交替使用，效用要比最速下降法好的多。

用于二次函数时的收敛速度分析定理：设二次函数 A对称正定，分别为其最小和最大特征值，从任意初点出发，用最速下降

法求f的极小点，产生的序列为，对于有由于

而函数的极小点恰好是。故最速下降法对于二次函数关于任意初始点均收敛，且是线性收敛。

下面说明最速下降法收敛性的几何意义。

考虑A为正三角矩阵时的二次函数函数的等值线为其中

用于二次函数时的收敛速度分析改写为：

这是以和为半轴的椭圆从下面的分析可见两个特征值的相对大小决定最速下降法的收敛性。

（1）当时，等值线变为圆此时因而由上述定理知：

即只需迭代一步就到了极小点，这表明最速下降法用于等值线为圆的目标函数时，只需迭代一步就到了极小点。

（3）当，