第三章无约束最优化方法技巧

第三章 无约束最优化方法本章开始讨论无约束优化问题

（3.1）

的计算方法。所介绍的几个算法基本上都属于下降算法。前面已经讲过了步长的求法，记忆未搜索。所以现在构造算法的关键在于如何选取搜索方向。根据选取搜说方向是否使用目标函数的导数，可将无约束优化算法分为两类：一类称为解析法，本章将介绍最速下降法，Newton法，共轭梯度法和拟Newton法，它们都使用目标函数的导数；另一类称为直接法，不使用导数。本章将介绍Powell的方向加速法。在介绍具体的算法之前，我们先来讨论问题（3.1）的极小点所应具有的特征，即所谓的最优性条件。§3.1

无约束最优化问题的最优性条件本节将给出问题（3.1）的局部极小点的一阶、二阶必要条件和二阶充分条件，这是一个古典极值问题，在微积分学中已经有所研究，那里给出了定义在几何空间上的实函数极值存在的条件，这一节只是把已有理论在n维欧氏空间中加以推广。定理

3.1.1（一阶必要条件）若

为

的局部极小点，且在

的某领域内

具有一阶连续偏导数，则

=

=0。证明：若使

＜0.

由微分学中值定理，存在≠0，则存在方向

∈

（例如

=－

）使得成立。由于

在

的某领域内连续，故存在

＞0使有，有

＜0。所以，对＜

。这与从定理的证明中可以看出，是

的局部极小点矛盾。=0并不能区分出极小点、极大点或鞍点。要区分必须进一步考察

的二阶导数，即考察

的Hesse矩阵§3.1

无约束最优化问题的最优性条件定理

3.1.2（二阶充分条件）若在

的某领域内

有二阶连续偏导数，且

=0，=

正定，则

为问题（3.1）的严格局部极小点。定理

3.1.3（二阶必要条件）若

为

的局部极小点，且在

的某领域内

有二阶连续偏导数，则

=0，

半正定。定理

3.1.4设

在

上是凸函数，且有一阶连续偏导数，则

为的整体极小点的充分必要条件是

=0。证明略。§3.1

无约束最优化问题的最优性条件§3.2

最速下降法对于无约束最优化问题，前面提到过，我们主要考虑下降算法。为了求其最优解，人们总希望从某点出发，选择一个目标函数值下降最快的方向，以利于尽快达到极小点。正是基于这样一种愿望，早在1847年法国数学家Cauchy提出了最速下降法。这是求无约束极值的最早的数值方法。现在一个很自然的问题是，沿怎样的方向

，

下降最快？由Taylor公式，由于

，其中

为

与当

，

固定时，

=1使

取最小值，从而的夹角，下降最多，即当

=0时，

下降最快，此时

=

。因此，下降最快，我们称之为最速下降方负梯度方向使目标函数向。§3.2.1

最速下降法最速下降法迭代公式是计算步骤如下：给定初点

，允许误差

＞0，令k=0。计算搜索方向，（3）若

，则由一维搜索步长（4）令，停止；否则令，使得，k=k+1，转步骤（2）。，设初始点为。例

3.2.1

用最速下降法求解解：，显然，目标函数是正定二次函数，有唯一的极小点

。可以证明，如果

是正定二次函数，则由精确一维搜索确定步长满足

，故，对正定二次目标函数，算法3.2.1的迭代公式如下由于

，所以由上式可得类似地计算下去，并可用归纳法证明，算法3.2.1产生如下点列显然，

，可见对所给目标函数，算法是整体收敛的，收敛速度是线性的。§3.2.1

最速下降法o由所给点列描绘在下图中，从图上可以看出，两个相邻的搜索方向是正交的。§3.2.1

最速下降法§3.2.2

收敛性最速下降法的优点是算法简单，每次迭代计算量小，占用内存量小，即使从一个不好的初始点出发，往往也能收敛到局部极小点，但他有一个严重缺点就是收敛速度慢。沿负梯度方向函数值下降很快的说法，容易使人们产生一种错觉，认为这一定是最理想的搜索方向，沿该方向搜索时收敛速度应该很快，然而事实证明，梯度法的收敛速度并不快。特别是对于等值线（面）具有狭长深谷形状的函数，收敛速度更慢。其原因是由于每次迭代后下一次搜索方向

总是与前一次方向

相互垂直，如此继续下去就产生所谓的锯齿现象（如右图所示）。即从直观上看，在远离极小点的地方每次迭代可能使目标函数有较大的下降，但是在接近极小点的地方，由于锯齿现象，从而导致每次迭代进行距离缩短，因而收敛速度不快。§3.3

Newton法上节讲过，最速下降法因迭代路线呈锯齿形，故收敛速度慢，仅是线性的。其实，最速下降法的本质是用线性函数去近似目标函数。因此，要想得到快速算法，需要考虑目标函数的高阶逼近。如果目标函数在上具有连续的二阶偏导数，其Hesse矩阵

了简便起见，记正定并且可以表达成为显式（今后为），那么可以使用下述的Newton法。这种方法一旦好用，收敛速度是很快的。它是一维搜索Newton切线法的推广。§3.3.1Newton法设

为

的极小点的一个近似，将

在

附近作Taylor展开，有其中一极小点，将它取为正定，则

有唯。由一阶必要条，若的下一次近似=0，即件知，

应满足令

（3.11），其中应满足方程组（3.12）称为Newton方程，从中解出（3.12），并带入（3.11）得

（3.13）我们称（3.11）、（3.12）为Newton迭代公式，有时也称(3.13)为Newton迭代公式。根据上面的推导，我们得到如下算法:已知目标函数

及其梯度

，Hesse矩阵

，终止限

。；置k=0。选定初始点

；计算计算

。由方程

解出

。计算。（5）判别终止准则是否满足：如满足，则打印最优解（

）结束；否则，置k=k+1，转（2）。§3.3.1

Newton法例

3.3.1

用Newton法求解，初始点取为解：梯度为，Hesse矩阵为，。由迭代公式得例

3.3.2

问题具有极小点。，用Newton法求解此问题，则得到迭代点如下所示：若取初始点为k0123456§3.3.1

Newton法从上述例子，我们看到用Newton法求解，只经一轮迭代就得到最优解。这一结果并不是偶然的，因为从Newton方向的构造我们知道，对于正定二次函数，Newton方向就是指向其极小点的方向。因此，用Newton法解目标函数为正定二次函数的无约束最优化问题，只需一次迭代就可得到最优解。对于目标函数是非二次函数的非约束最优化问题，一般地说，用Newton法通过有限轮迭代并不能保证可求得最优解。但由于目

标函数在最优解附近能近似于二次函数，因此当先取接近于最优解的初始点使用Newton法求解时，其收敛速度一般是较快的。事实

上，可以证明在初始点里最优解不远的条件下，Newton法是二次

收敛的。但是当初始点选的离最优解太远时，Newton法并不一定

是收敛的方法，甚至连其下降性也很难保证。§3.3.1

Newton法§3.3.2

Newton法的优缺点Newton法有很快的收敛速度，但它只是局部收敛的。对Newton法的优缺点的讨论是发展有效算法的关键，为此，我们把它们列于下。优点：（1）如果

正定且初始点合适，算法是二阶收敛的。（2）对正定二次函数，迭代一次就可得到极小点。缺点：（1）对多数问题算法不是整体收敛的。，该方非正定），在每次迭代中需要计算

。每次迭代需要求解线性方程组，程组有可能是奇异或病态的（有时可能不是下降方向。（4）收敛于鞍点或极大点的可能性并不小。§3.3.3

Newton法的改进为了克服Newton法的缺点，人们保留选取Newton方向作为搜索方向，采用一维搜索确定最优步长，由此产生的算法称为修正Newton法（或阻力Newton法）。其迭代步骤如下：（1）选取初始点（2）计算

，若（3）构造Newton方向。计算，取，令k=0。停止迭代，输出

，否则转（3）。。。（4）进行一维搜索。求令，使得，k=k+1，转（2）。修正Newton法克服了Newton法的缺点。特别是，当迭代点接近于最优解时，此法具有收敛速度快的优点，对初始点的选择要求不严。但是，修正Newton法仍需要计算目标函数的Hesse矩阵和逆矩阵，所以计算量和存贮量均很大。另外，当目标函数的Hesse矩阵在某点出现奇异时，迭代将无法进行，因此修正Newton法仍有局限性。§3.4

共轭方向法和共轭梯度法对于n元正定二次目标函数，从任意初始点出发，如果经过有限次迭代就可得到极小点，那么这种算法称为具有二次终止性。下面将要介绍的共轭方向法，就是建立在二次模型基础上，并且具有二次终止性。这类算法的效果介于最速下降法和Newton法之间，既能克服最速下降法的慢收敛性，又避免了Newton法的计算量大和具有局部收敛性的缺点，因而是比较有效的算法。值得指出的是，共轭方向法中的共轭梯度法，由于其存贮量小，可用来求解大规模（n较大）无约束优化问题。§3.4.1共轭方向法定义3.4.1

共轭向量设G为n阶正定矩阵，=0，i，j=1，2，……k，i≠j为n维向量组，如果则称向量组关于G共轭。=0，即是正交的，所以共如果G=I，则化为轭概念是正交概念的推广。定理3.4.1设G为n阶正定矩阵，非零向量组量组线性无关。推论1设G为n阶正定矩阵，非零向量组关于G共轭，则此向关于G共轭，则此向量组构成n维向量空间

的一组基。推论2设G为n阶正定矩阵，非零向量组关于G共轭，则v=0。关于G共轭。若向量v与定义3.4.2设n维向量组，称向量集合线性无关，为由点

与生成的k维超平面。引理3.4.2设为连续可微的严格凸函数，又为一组线性无，则

是

在

与上的唯一极小点的充分必要条件是

=0，关的n维向量，所生成的k维超平面i=1，2，……，k定理3.4.3设G为n阶正定矩阵，向量组由任意初始点关于G共轭，对正定二开始，依次进行k次精确，i=1，2，……，k=0，i=1，2，……，k次函数一维搜索则（i）（ii）

是二次函数在k维超平面

上的极小点。§3.4.1共轭方向法一般地，在n维空间中可以找出n个互相共轭的方向，对于n元正定二次函数，从任意初始点出发，顺次沿这n个共轭方向最多作n次直线搜索就可以求得目标函数的极小点。这就是共轭方向法的算法形成的基本思想。二次函数的共轭方向法的迭代步骤：已知具有正定矩阵G的二次目标函数

和终止限

。给定初始点

及下降方向

，置k=0。作精确一维搜索

，求步长

。令

。（4）若

，则（5）取共轭方向

使得，停；否则，转步骤（5）。=0，i=0，1，……，k（6）令k=k+1，转步骤（2）。§3.4.1

共轭方向法§3.4.2

共轭梯度法如果在共轭方向法中初始的共轭向量恰好取为初始点

处的负梯度

，而以下各共轭方向

由第k迭代点

处的负梯度与已经得到的共轭向量

的线性组合来确定，那么就构成了一种具体的共轭方向法。因为每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以称为共轭梯度法。设从任意点当搜索得到点处的负梯度方向，k=0，1，……n+2来产生搜索方向。为了选择

（k=0，1，……，n-2）是所产生的和（

k=0，1，……，n-2）是G共轭，以于是有右乘上式的两端，因为要使

和

是G共轭，应有故由上式得=0，综上所述，可以生成n个方向§3.4.2共轭梯度法出发，第一个搜索方向取为后，设以下按§3.4.2

共轭梯度法上式含有目标函数系数矩阵，这对于目标函数是非二次函数的问题是不方便的。通过简化，一般可以利用目标函数的梯度信息，来产生n个共轭方向由此得共轭梯度法。§3.4.2

FR共轭梯度法是Fletcher和Reeves在1964年得到的，故称Fletcher－Reeves公式，简称FR公式。对于一般函数，将FR公式与

，

结合产生搜索方向，即得如下的FR共轭梯度法：给定初始点

，k=1，给定控制误差

。计算若

，则

停；否则令。由精确一维搜索确定步长令，满足转步骤（2）。用FR共轭梯度法求解。例3.4.1取初始点解：，故取，从

出发，沿

作一维搜因索，即求的极小点，得步长。于是得到。由FR公式得故。从出发，沿作一维搜索，求的极小点，解之得，于是。此时，故。§3.4.2

FR共轭梯度法Polak-Ribiere-Polyak公式：注意到

=0，故

。此式是Polak和Ribiere以及Polyak分别于1969年提出的，故称Polak-Ribiere-Polyak公式，简称PRP公式。，在FR共轭梯度法步骤（3）中用PRP公式代替FR公式，就得PRP共轭梯度法。对于正定二次函数，FR共轭梯度法与PRP共轭梯度法等价。但是对于一般函数，二者是不同的，并且由于目标函数的Hesse阵不是常数矩阵，因而迭代过程中所产生的方向不再是共轭方向了。不过两个算法所产生的搜索方向都满足故二者都是下降算法。从一些实际计算的结果发现，PRP算法一般优于FR算法。§3.4.2

PRP共轭梯度法现在考虑对共轭梯度法进行改进。我们知道，在最优解附近，目标函数与一个正定二次函数很接近。因此，当迭代点进入目标函数逼近正定二次函数的区域后，如

果我们能及时产生接近于共轭方向的搜索方向，则就能较迅速地收敛到最优解。然而，对于PRP和FR算法来说，如果初始方向不取负梯度方向，则即使应用于二次函数，也往往不能产生n个共轭方向（参看习题3.11）。因此，我们设想，当在现行迭代点目标函数与正定二次函数很接近时，重新取负梯度方向为搜索方向，那么后面几次迭代，将产生近似的共轭方向，从而提高了算法的效率。基于上述想法，对共轭梯度法进行如下修改：每迭代n或n+1次，就重新取负梯度方向为搜索方向，这样得到的算法，称为n步重新开始的共轭梯度法。§3.4.3

n步重新开始的共轭梯度法n步重新开始的PRP共轭梯度法：，k=1，给定控制误差

。，若

，则

，停；否则，给定初始点计算转步骤（3）。若k是n+1的倍数，则

。否则，令由精确一维搜索确定步长

，令

转步骤（2）。如果在步骤（3）中，用FR公式代替PRP公式，则得到n步重新开始的FR共轭梯度法。§3.4.3

n步重新开始的共轭梯度法前面介绍了Newton法，它的突出优点是收敛很快。但是，运用Newton法需要计算二阶偏导

数，而且目标函数的Hesse矩阵可能非正定，为了克服Newton法的缺点，人们提出了拟Newton法。它的基本思想是用不包含二阶导数的矩阵近似

Newton法中的Hesse矩阵的逆矩阵。由于构造近

似矩阵的方法不同，因而出现不同的拟Newton法。经理论证明和实践检验，拟Newton法已经成为一类公认的比较有效的算法。§3.5

拟Newton法§3.5.1

拟Newton法的基本思想最速下降法和阻尼Newton法的迭代公式可以统一表示为，其中

为步长，

，

为n阶对称矩阵。在上式中，若令

，则是最速下降法；若令

，就是阻尼Newton法。前者具有较好的整体收敛性，但收敛速度太慢；后者虽收敛性差，且需要计算二阶导数，计算量大。因此，如果能做到的选取既能逐步逼近

，又不需要计算二阶导数，那么由此算法就有可能比最速下降法快，又比Newton法计算简单，且整体收敛性好。为了使

确实能有上述特点，必须对

附加一些条件：C1：

是对称正定矩阵。这是为使算法具有下降性质。显然，当

正定时，从而

为下降方向。C2：

由

经简单形式修正而得，

称为修正公式，其中称为修正矩阵。C3：

满足所谓的拟Newton方程（后面将推导此方程）。§3.5.1

拟Newton法的基本思想我们希望经过对任意初始矩阵

的逐步修正能得到

的一个好的逼近。能做到这点的一个方法如下：令

，由Taylor公式，有当

非奇异时，有

对于二次函数，此式为等式。

因为目标函数在极小点附近的性态与二次函数近似，所以一个合理的想法就是：如果使得

满足

此式称为拟Newton方程。

那么

就可以较好地近似

。显然，由于

有

个未知数，n个方程，所以一般有无穷多个解，故由拟Newton方程确定的是一族算法，称之为拟Newton法。事实上有些拟Newton法不具备C1，通常称具备条件C1的拟Newton法为变尺度法。§3.5.2

DFP算法DFP算法是Davidon（1959）提出的，后来Fletcher和Powell（1963）作了改进，形成了Davidon-Fletcher-Powell算法，简称DFP算法。它是第一个被提出的拟Newton法，也是无约束最优化问题的最有效的算法之

一，已被广泛地采用。如前所诉，拟Newton法首先要解决的问题是如何构造据阵列

，使其满足条件C1-C3。考虑修正矩阵由拟Newton方程有，其中u，v为n维待定向量。，满足这个方程的待定向量u和v有无穷多种取法、一个明显的取法是令

和

，而

和

的值由及

确定，利用

的对称性可导出公式称此公式为DFP修正公式。§3.5.2

DFP算法DFP算法迭代步骤如下：（1）给定初始点

，初始矩阵（通常取单位阵）计算

，令k=0，给定控制误差

。令

。由精确一维搜索确定步长

，。，则

停；（4）令（5）若否则令，（6）由DFP修正公式得。。令k=k+1，转步骤（2）§3.5.2

DFP算法例

3.5.1

用DFP算法求解，取解：（i）求迭代点

，令得

的极小点为，所以，于是，由DFP修正公式有下一个搜索方向为（ii）求迭代点

，令其极小点为

，于是所以，为正定阵，为严格凸函数，所以，因Hesse阵为整体极小点。还可以验证，再用一次DFP修正公式，则得§3.5.2

DFP算法由上述计算过程知，对所给的二维正定二次函数，DFP算法只须迭代两次，就可得到极小点，因此，是非常有效的。事实上，对一般的n维正定二次函数，DFP算法具有二次终止性。对于一般函数，DFP算法的效果也很好，它比最速下降法以及共轭梯度法要有效得多。DFP算法具有下列一些重要的性质。（1）对于正定二次函数：；；至多经过n次迭代即终止，且保持满足前面的拟Newton方程产生的搜索方向是共轭方向；（2）对于一般函数：保持矩阵

的正定性，从而确保了算法的下降性；算法为超线性收敛速度；对于凸函数是整体收敛的；每次迭代需要

次乘法运算（注意Newton法需要 次）。§3.5.3DFP算法的正定性及二次终止性引理3.5.1设，H为正定矩阵，且y≠0，s≠0，则

为正定矩阵的充分必要条件是。定理3.5.2（DFP修正公式的正定继承性）正定，则整个矩阵列在DFP算法中，如果初始矩阵定的。定理3.5.3将DFP算法用于目标函数都是正。设初始矩阵

是正定的，产生的迭代点是互异的，并设产生的搜索方向为

，则（i）

（ii）推论（DFP算法的二次终止性）在定理3.5.3的条件下，我们有（i）DFP算法至多迭代n次就可得到极小点，即存在，使。（ii）若，则。证明略。§3.5.4

BFGS算法我们再介绍另一个有效和著名的拟Newton法。由于它是Broyden，Fletcher（1970），Goldfarb（1969）和Shanno（1970）共同研究的结果，因而叫做BFGS法。考虑校正公式：其中

为参数，可取任何实数，而这族公式被成为Broyden族修正公式。容易证明，对任意

，由上式得到的

满足拟Newton方程。把DFP算法中涉及DFP修正公式的部分换成上式，就得到了一族拟Newton算法，我们称之为Broyden族拟Newton算法。显然，当取取=0时，Broyden族给出的修正公式就是DFP修正公式。，得到如下修正公式：这个公式被称为对称秩1公式。它不适合用于DFP算法的框架中。然而，它有一个突出的优点，就是往往比别的修正公式逼近

的程度高。当取

=1时，得到一个新的修正公式：把他替换DFP算法中的DFP修正公式，就得到了著名的BFGS算法。在实际计算中，由于舍入误差的存在以及一维搜索的不精确，DFP算法的效率和受到很大影响，但BFGS算法所受影响要小得多。特别是采用非精确一维搜索时，DFP算法效率很低，然而BFGS算法却仍然十分有效。目前BFGS算法被公认为最好的拟Newton算法。§3.5.4

BFGS算法§3.6

Powell方向加速法前面几节所介绍的算法都要用到目标函数

的一阶或二阶导数，但实际问题中所遇到的目标函数有时很复杂，其一、二阶导数或是很复杂或是难以求得，甚至有时连目标函数的解析表达式也不知道，只能通过直接测量得到某些点上的函数值。这时，前面所介绍的解析法就不是用了，而应采用不使用导数的直接法。直接法一般对目标函数的解析性质不做苛刻要求，因而就目标函数的类型而言，适用面较广。但是，正因为直接法一般不利用函数的解析性质，所以收敛速度较慢，同时计算量也往往随问题维数的增加而迅速增大。本节将介绍直接发中最有效者之一：Powell方向加速法。§3.6.1

Powell方向加速法定理3.6.1对于n维正定二次函数设

关于G共轭，

与

为不同的任意两点，分别从

与

出发，依次沿

作一维搜索，并设最后一次搜和

。如果

，则

与。索得到的极小点为关于G共轭，即

证明略。这个定理告诉我们，通过在不同起点沿同一方向求极小的方法可以产生共轭方向。Powell正是基于这一思想，于1964年提出了所谓的方向加速法。其核心思想是：在迭代过程的每个阶段都作n+1次一维搜索。首先依次沿给定的n个线性无关的方向

作一维搜索；再沿由这一阶段的起点到第n次搜索所得到的点的连线方向p做一次一维搜索，并把这次所得点作为下一阶段的起点，下一阶段的n个搜索方向为

。§3.6.1

Powell方向加速法Powell原始算法迭代步骤如下：给定控制误差

>0，初始点

，设分别为作一维搜索，得步长n个坐标轴上的单位向量。令依次沿，令，再令令作一维搜索若，则令，停；否则转（6）（6）令，转步骤（2）。§3.6.2

Powell改进算法根据定理3.6.1，对于正定二次函数上述算法各阶段的出发点和终止点所确定的向量毕是关于G共轭的，故至多经过n个阶段的迭代就可以求得极小点。因为此算法是在迭代中逐次生成共轭方向，而共轭方向又是较好的搜索方向，所以称之为方向加速法。但是后来发现，有时用此算法产生的n个向量可能线性相关或近似线性相关，这时张不成n维空间，所以可能得不到真正的极小点。因此，Powell原始算法并不是很实用。为了克服上述缺点，Powell对其原始算法进行了改进。改进后的算法虽不再具有二次终止性，但确实克服了搜索方向的线性相关的不利情形。Powell改进算法是较有效的直接法之一。§3.6.2

Powell改进算法Powell改进算法迭代步骤如下：给定控制误差

>0，初始点

，设分别为n个坐标轴上的单位向量。令k=1。计算

，令作一维搜索

，令若k=n，转（4）；若k<n，令k=k+1，转（2）。，则

，停；否则转（5）。，或（4）若（5）令（6）若则搜索方向不变，令，，，。，令转（2）；否则转（7）。令而令作一维搜索转（2）。例如，已知两维变量函数f(X)的等高线，内圈比外圈函数低。图7-3极小化f(X)时得到的正单纯形序列137586421091112x1x2单纯形法其思路为，首先取3个点（n+1=2+1）X(1)，X(2)，X(3)，并

计算函数值f(X(1))，f(X(2))，f(X(3))。然后比较大小（这三个点称为初始单纯形）。发现f(X(3))最大，舍去f(X(3))，找出余下两点X(1)和X(2)的形心点，连结X(3)与形心点并延

长找出X(3)关于形心点的对称点X(4)，再用X(1)，X(2)和X(4)构成新的正多面体，继续前述步骤，直到找出极小点为止。上图描绘了寻找f(X)极小点的正多面体序列。单纯形法在迭代过程中，不保持每步都为正多面体，而是根据情况改变形状。其算法步骤如下：设

X

(k)

=[x

(k)，…，x

(k)，…，x

(k)]T，

i=1，…，n+1i

i1

ij

in是搜索第k阶段（k=0，1，…）上n维欧氏空间的第i个