第九章经典最优化方法

1、第九章 经典最优化方法9.1 最优化的基本概念最优化方法是一门古老而又年青的学科。这门学科的源头可以追溯到17世纪法国数学家拉格朗日关于一个函数在一组等式约束条件下的极值问题（求解多元函数极值的Lagrange乘数法）。19世纪柯西引入了最速下降法求解非线性规划问题。直到20世纪三、四十年代最优化理论的研究才出现了重大进展，1939年前苏联的康托洛维奇提出了解决产品下料和运输问题的线性规划方法；1947年美国的丹奇格提出了求解线性规划的单纯形法，极大地推动了线性规划理论的发展。非线性规划理论的开创性工作是在1951年由库恩和塔克完成的，他们给出了非线性规划的最优性条件。随着计算机技术的发展，各

2、种最优化算法应运而生。比较著名的有DFP和BFGS无约束变尺度法、HP广义乘子法和WHP约束变尺度法。最优化问题本质是一个求极值问题，几乎所有类型的优化问题都可概括为如下模型：给定一个集合（可行集）和该集合上的一个函数（目标函数），要计算此函数在集合上的极值。通常，人们按照可行集的性质对优化问题分类：如果可行集中的元素是有限的，则归结为“组合优化”或“网络规划”，如图论中最短路、最小费用最大流等；如果可行集是有限维空间中的一个连续子集，则归结为“线性或非线性规划”；如果可行集中的元素是依赖时间的决策序列，则归结为“动态规划”；如果可行集是无穷维空间中的连续子集，则归结为“最优控制”。线性规划与

3、非线性规划是最优化方法中最基本、最重要的两类问题。一般来说，各优化分支有其相应的应用领域。线性规划、网络规划、动态规划通常用于管理与决策科学；最优控制常用于控制工程；非线性规划更多地用于工程优化设计。前面提到的算法是最优化的基本方法，它们简单易行，对于性态优良的一般函数，优化效果较好。但这些经典的方法是以传统微积分为基础的，不可避免地带有某种局限性，主要表现为：大多数传统优化方法仅能计算目标函数的局部最优点，不能保证找到全局最优解。对于多峰值函数，这些方法往往由于过分追求“下降”而陷于局部最优解；许多传统优化方法对目标函数的光滑性、凹凸性等有较高的要求，对于离散型函数、随机型函数基本上无能为力

4、。二十世纪六、七十年代以来，人们将人工智能技术和生物进化机理引入最优化方法，逐渐形成了一批完全不同于传统优化方法、令人耳目一新的现代优化方法。如模拟退火、神经网络、进化计算、模糊逻辑等，其中进化计算中的遗传算法以其良好的全局搜索性成为现代优化算法中最受关注的算法之一，已被广泛应用于函数优化、组合优化、自动控制、生产调度、图像与信号处理、机器人和人工生命等领域。9.1.1 预备知识1、梯度定义9.1 对元可微函数，向量称为在处的梯度，记为或，称为梯度算子或Hamilton算子。从几何上讲，的方向是在处上升最快的方向，的模是在处上升最快的速率。若，则函数曲面在处的切平面是水平的。 2、二阶导数矩阵

5、定义9.2 设元函数具有二阶连续偏导数，则的所有二阶偏导数构成的矩阵称为在处的二阶导数矩阵或海色（Hessain）矩阵，记为。显然，是一个对称矩阵。在几何上，反映了函数曲面的弯曲方向。若（正定），则函数曲面向上弯曲（凹）；若（负定），则函数曲面向下弯曲（凸）。例9.1 设为阶对称矩阵，、为元列向量，为标量，对二次函数求梯度、Hessain矩阵。解：可将算子、理解为对向量函数的一阶、二阶导数，易得3、元函数的二阶Taylor展式一元函数的Taylor展式：其中二元函数的Taylor展式：其中二元函数的二阶Taylor展式： 若引入矩阵记号 则元函数的二阶Taylor展式与二元函数的二阶Taylo

6、r展式形式类似。4、凸集与凸函数定义9.3 设，若中任两点的连线都属于，即对任意、，均有，则称为一个凸集。定义9.4 设为定义在凸集上的函数，若对任意、，均有，则称为上的凸函数。若上式改为严格不等式，则称为上的严格凸函数。定理9.1 （一阶判别条件）一阶可微函数在凸集上为凸函数的充要条件是：对任意、，均有。定理9.2 （二阶判别条件）二阶连续可微函数在凸集上为凸函数的充要条件是：对任意，半正定。为严格凸函数的充要条件是正定。9.1.2最优化的基本概念最优化问题的数学模型为称为目标函数，称为约束函数。当和均为线性时，称之为线性规划（LP）；当和至少有一个为非线性时，称之为非线性规划（NLP）。对

7、非线性规划，如果变量的取值范围没有限制，称之为无条件极值或无约束最优化，否则称之为条件极值或约束最优化。求解最优化问题最常用的方法是迭代法。迭代法的基本思想是：从最优点的一个初始值出发，按一定迭代法则产生点序列，使目标函数值逐步减小。当序列是有限点列时，其最后一点即为最优解；当是无穷点列时，其极限点即为最优解。对于迭代法有下列四个问题：如何由产生，即迭代格式或算法结构；迭代何时中止，即停止准则或最优性条件；迭代产生的序列是否收敛于最优解，即收敛性问题；收敛算法的收敛速度问题。1、最优性条件由微积分知识不难得出下列最优性条件。定理9.3 （一阶必要条件）设可微，若为的一个极小点，则。本定理的几何

8、意义是，函数在处取极小值的必要条件是该函数曲面在处的切平面是水平的；梯度为零的点可能是极小或极大点，也可能是鞍点即既非极小也非极大的点。定理9.4 （二阶充要条件）设二阶连续可微，若，且处的二阶导数矩阵正定，则为极小点。本定理的几何意义是，为极小点的充要条件是函数曲面在处有水平切平面且向上弯曲。定理9.5 （凸函数的最优性条件）设为二阶连续可微的凸函数，且，则为全局极小点。2、算法结构根据最优条件，从理论上讲，可以先解非线性方程组，然后再判定其解的二阶导数矩阵是否正定，即可求出函数的最优解。但由于解非线性方程组和判定矩阵是否正定是极为复杂和困难的，其难度甚至已超过优化问题本身。因此，上述想法在

9、实际上是不可行的。最优化中大多采用逐步下降算法，其基本思想是：根据当前解选择一个适当的下降方向，沿此方向下降到一个合适位置从而得到新解，然后判断新解是否为最优解；若是，则停止，否则重复上述过程。经过有限次迭代后，在一定条件下即可得出近似最优解。下降算法的迭代格式为：，其中是第次迭代点，是第次迭代方向，是第次迭代步长。显然，用迭代法求解无约束最优化问题的关键是：构造迭代方向和确定迭代步长。确定迭代步长可通过一维搜索方法进行，而选择不同的方法构造迭代方向，将会得到不同的算法。根据一阶Taylor展式可见，如果，那么存在，使得当时上式右端小于零，从而，即为下降方向的条件是其与梯度方向成钝角。3、收敛

10、性与收敛速度个算法是否收敛，往往同初始点的选取有关。如果只有当充分接近最优解时，由算法产生的点列才收敛于，则该算法称为具有局部收敛性的算法。如果对于任意的初始点，由算法产生的点列都收敛于最优解，则这个算法称为具有全局收敛性的算法。由于一般情况下最优解是未知的，所以严格来说只有具有全局收敛性的算法才是有实用意义的。令人遗憾的是大多数经典优化算法都是局部优化算法，全局优化的理论和算法远不及局部优化那么成熟，至今为止还没有得到类似于局部极小点那样的解析条件，即没有肯定的方法能判断一个局部极小点是否为全局极小点，现有的一些全局优化算法也只能在一定程度上避免迭代终止于一个非全局的局部极小点。定义9.5

11、设点列收敛于，且对实数，有，则称点列为阶收敛的。9.2 一维搜索方法在基本迭代格式中，若已知当前点和迭代方向，则迭代步长可由的极小值确定，即。这种确定的方法称为一维搜索，其实质就是求一元函数的极小值。一维搜索方法分为两类：一类是不需要求导运算、只利用的函数值、适用于单峰函数的直接法，主要有黄金分割法（0.618法）和斐波那契（Fibonacci）法；另一类是需要求导运算的解析法，例如插值方法等。直接法能适应不可微的情况，而解析法的效率相对较高。9.2.1 直接法1、确定搜索区间的进退算法 在区间中任取一点，若，(两头大中间小)，则为搜索区间。取定初始点及初始步长；令，计算和；若，转，否则缩短步

12、长t，比如（后退运算），转；加大步长t，比如（前进运算），令；若，则得到，否则，转。2、直接法的基本原理 假设为单峰函数，即有唯一的极小点，且搜索区间已知。因为在内单减，在内单增，故若在内任取二点，则仅有如下两种情形： ，由于为单峰，所以极小点必在内；，则极小点必在内。可见，只要在当前搜索区间内取二点，比较其函数值，即可将搜索区间缩短。自然地，我们会提出下列两个问题：问题1：计算个函数值可获得的区间最大缩短率（缩短后的区间长度与原区间长度之比）为多少？问题2：要将区间缩短到规定的程度，怎样选取试验点才能使计算次数最少？问题1等价于“计算个函数值能把多长的区间缩短为长度为1的区间？”用表示所能取

13、得的最大区间长度，这个区间经计算个函数值能够缩成单位区间。显然，。因为不计算函数值或只计算1个函数值无法缩短区间，只有原区间长度本来就是1才行。现考虑两个点情形：在区间内取两个相异点，缩短后的区间为或。这两个区间的长度和必大于的长度，故其中至少有一个子区间的长度大于的一半，即计算两个函数值一般无法把长度大于2的区间缩成单位区间。但是，对于长度为2的区间，可以如图所示选取试验点，缩短后的区间长度为1+，其中为任意小的正数。因为可任意选取，所以缩短后的区间长度接近1，因此。同理可知，一般地，序列有递推公式这就是著名的Fibonacci序列。综上所述，计算个函数值可获得的区间最大缩短率为。对于问题2

14、，既然个试点的最大缩短率为，要想把的长度缩短为原来的倍，称为缩短的相对精度，只要试点数满足即可，试点的具体位置可以根据每次的缩短率确定。3、Fibonacci法和0.618法若按上述方法选取试点，则对当前搜索区间，若在搜索区间内取个点，则各次缩短率分别为 ，其中为Fibonacci序列。这种方法称为Fibonacci法。从理论上讲，Fibonacci法是缩短搜索区间的最优方法，但实际计算时要用到Fibonacci数列，而且每次缩短率不同，这就增加了计算上的困难。为了计算上的方便，通常采用等速缩短的方法。缩短率取为的极限，此方法称为0.618法。若当前搜索区间为，则，。显然，取个点后，缩短率为，

15、若要求相对精度为，则。0.618法的计算步骤如下：求在区间上的最小值，相对精度为。给定，记，；，若，转，否则转；，转；，转；若，置，转，否则转；取最优点，最优值为。注：Fibonacci法和0.618法仅适用于单峰函数；若初始搜索区间未知，要用进退算法先确定。例9.2 用0.618法求单峰函数在区间内的极小值。9.2.2 插值法多项式是逼近函数的一种常用工具。在搜索区间上，我们可以利用在若干点处的函数值来构成低次插值多项式，用它作为函数的近似表达式，并用这个多项式的极小点作为原函数极小点的近似，而低次多项式的极小点是比较容易计算的。常用的插值多项式为二次或三次，一般说来三次插值公式的收敛性较好

16、，但在导数不便计算时，二次插值多项式也是常用的一种方法。1、二次插值方法设函数在点处的值分别为，利用这三点作二次插值公式，很容易得到它的极小点为若三点等距，相邻两点距离为，则 2、三次插值方法在二次插值方法中，极小点不一定在区间中，即插值可能为外插，这就使得二次插值方法的误差可能较大，不易控制。因为一般情况下在搜索区间上满足，所以若利用在两点的函数值以及一阶导数值作三次插值多项式，则插值法为内插，精度较高。经过计算，可得三次插值多项式的极小点为9.3共轭梯度法9.3.1最速下降法Cauchy于1947年提出的最速下降法是求无约束极值最早的数值方法，其基本思想是：从迭代点出发，沿目标函数值的负梯

17、度方向进行一维搜索，求出新的迭代点，直到找到局部极小点或满足精度要求。1、最速下降法的计算步骤给定初始点、控制误差，置；计算梯度，若，则，停机，否则令，由一维搜索求步长，使；令，转。定理9.6 从出发沿任意下降方向执行一维搜索，得新迭代点，则与垂直，即。证：由一元函数取极值的必要条件知， 又，故。2、最速下降法的特点由于负梯度的方向仅仅在附近才具有“最速下降”性质，因此最速下降法不一定具有较高的收敛速度；由定理2.1，即相邻两次搜索方向是相互正交的。可见，最速下降法逼近最小点的路线是锯齿形的，并且越靠近极小点步长越小，即越走越慢。最速下降法是基本方法，但不是有效的实用方法，一般适宜于其它方法结

18、合用于早期搜索。例9.3 用最速下降法求Rosenbrock函数的极小值。解： 在函数优化问题中，目标函数等高面内经常出现“超山谷”。对于二维函数，在由目标函数等值线绘出的曲线图中则表现为“山谷”。对一个成功的最优化方法的要求之一就是能够沿着狭长的山谷迅速逼近极值。本例中的就是由Rosenbrock设计用以考察最优化方法这一方面性能的典型函数，也称香蕉函数。下面给出时的三条等高线。从图中可以看出，Rosenbrock函数的等值线是一条条弯曲而又狭长的山谷，山谷中点的最速下降方向几乎与通向极小值的最好方向垂直，因此最速下降法收敛得极慢（主要是方向收敛太慢），甚至在合理的时间内完全不收敛。9.3.

19、2共轭梯度法1、共轭方向从前面已经看出，负梯度方向并不是理想的搜索方向，要提高算法的收敛速度，需要寻找其它搜索方向。为了对寻找搜索方向提供依据，我们先考虑判断算法优劣的方法。二次函数是一种比较简单的函数，而一般的目标函数在极小点附近的性态又近似于二次函数，所以可以设想，一个算法如果对于二次函数比较有效，就可望对于一般函数（至少在极小点附近）也有较好的效果。下面我们就从二次函数出发，寻找比较有效的搜索方向。考虑正定二次函数由于为正定矩阵，从而函数的等值线为平面上的一簇椭圆。显然，如果椭圆非常狭长，则最速下降法锯齿形迭代的步长越来越小。能否找到理想的搜索方向，使算法用最短的迭代找到极小点呢？下面的

20、分析告诉我们，对于只包含两个变量的正定二次函数，最多只要两次迭代即可找到极小点。在初始点处，取负梯度方向为搜索方向，即，沿下降至处。假设在处，选择适当的搜索方向，沿即可直接找到极小点，即有，使。由最优性条件，即，代入得，亦即。用乘上式后得到 ，由最速下降法知，从而。因为与正交，当然线性无关，从而它们构成二维平面的基底，故可表示为和的线性组合，即，用左乘上式得，考虑到，得，从而。定义9.6 设为中的个非零向量，为阶正定矩阵。若对任意均有，则称关于两两共轭。当为单位矩阵时，意味着两两正交，所以共轭是正交的推广。定理9.7 设为阶正定矩阵，若非零向量关于两两共轭，则是线性无关的。证：设有使得，因为关

21、于两两共轭，即，所以用左乘上式得，又，正定，得，从而，即线性无关。2、n元正定二次函数的共轭梯度法对元的正定二次函数有下面两个重要定理。定理9.8 对元正定二次函数，设关于两两共轭。从任意初始点出发，依次沿方向执行一维搜索到则垂直于前面所有的搜索方向，即。证：由 得 用左乘上式，根据定理2.1，再由本定理条件,故。定理9.9 对元正定二次函数，设关于两两共轭。从任意初始点出发，依次沿执行一维搜索到，则即为极小点。证：由定理9.7，线性无关，即可作为的一组基，由定理9.8，从而。又正定，为凸函数，由定理9.5，为惟一全局极小点。仿照与的关系，我们构造下列搜索方向据此可证明下列定理。定理9.10

22、对元正定二次函数，从任意初始点出发，依次按上述搜索方向经次迭代下降至，即则即为极小点。证：只须用归纳法证明上述关于两两共轭，再利用定理2.4即可证明本定理。如果一个算法能用有限步求出二次函数的极小点（从理论上说），则称这个算法具有二阶收敛性或有限步收敛性。3、一般函数的共轭梯度法对于一般函数，已无正定矩阵和共轭的概念，因此我们必须寻求一种与上述共轭方向表达式等价的形式，其中不含有矩阵。由，得，从而又故最终综上所述，对于一般目标函数，可按下述规则确定搜索方向：此方法称为F-R（Fletcher-Reeves）共轭梯度法。9.4 拟牛顿法9.4.1 牛顿法最速下降法的本质是用线性函数逼近目标函数。

23、因此，要想得到快速算法，需要考虑用高次函数逼近。若采用二次多项式逼近，则称为牛顿法。对给定点，在这个点附近将展为二阶Taylor展式，即记，则，如果正定，则为凸函数，有惟一极小点，满足，即，。若记，则，称之为牛顿迭代，称为牛顿方向。牛顿迭代可以理解为从出发，沿牛顿方向取步长。显然，对正定二次函数，从任意初始点出发，牛顿迭代一步即可达到最小点。 理论分析表明，当初始点离较近时，牛顿迭代法能以二阶速度收敛到。但当离较远时，牛顿迭代可能不收敛，甚至迭代过程无法进行，原因如下：当为奇异阵时，无意义，迭代无法进行；即使非奇异，但不一定正定，从而不能保证，即牛顿方向不一定是下降方向；即使正定，此时是下降方

24、向，但牛顿迭代取步长，也不能保证。其实，即便牛顿迭代可以正常进行且收敛，因为它在每次迭代时要计算Hesse矩阵及其逆，从而得出迭代方向，这使得每次迭代的计算量太大，大大降低了牛顿迭代的实用性。9.4.2 变尺度法（拟牛顿法）牛顿法主要缺点是要计算Hesse矩阵及其逆。一个很自然的想法是不直接计算Hesse矩阵，也不计算其逆矩阵，而设法构造另一个矩阵来直接逼近，这一类算法称为变尺度法或拟牛顿法，其中以DFP算法和BFGS算法最为著名。在所有无约束最优化方法中，若综合考察收敛速度、计算量、适用范围等算法性能，变尺度法是最出色的。变尺度法的基本思想是在处，按某种规则产生一个对称正定矩阵，用作为处的搜

25、索方向。显然，取时，分别为最速下降方向和牛顿方向。1、拟Newton条件由Taylor展式，得，。记，则。对于二次函数，上式精确成立，我们称为拟Newton条件。作为的近似自然应该满足。2、DFP变尺度法我们的目标是在处构造满足拟Newton条件的对称正定阵，为此假设已知（可取为任一对称正定阵，比如），且。因对称，故可令，其中待定。将其代入拟牛顿条件得，即。为使上式成立，只要选择使得从知，与共线，故可令，代入得，从而。 类似地可得。最终得到，称之为DFP公式。DFP算法计算步骤：给定初始点，精度，取，；计算梯度，若，则，停机，否则用DFP公式求出，令，由一维搜索求步长；令，转。DFP方法是一种

26、非常有效的无约束最优化方法，但在有些实际计算中发现其在数值稳定性方面存在一定的问题。如果对数值稳定性要求较高，可采用BFGS变尺度方法。定理9.11：如果对称正定，则。证：因为，是下降方向，故从到的迭代步长，并且。定理9.12：如果对称正定，则由DFP公式产生的均对称正定。3、BFGS变尺度法DFP变尺度法是一种非常有效的无约束最优化方法，自从1959年发表以来，大量的计算实践确实反映了这一点。但到了六十年代后期，一方面从计算实践中发现了DFP算法在数值稳定性方面存在一定的问题，同时在变尺度法理论的研究上也获得了显著的进展，陆续提出了许多变尺度算法。在七十年代初期，从数量繁多的算法中，人们发现

27、一个比DFP算法具有更好数值稳定性的算法，即BFGS算法。与DFP公式的推导过程类似，可以得到满足拟牛顿条件的一组 参数取不同的值就得到不同的公式。例如，就得到了DFP公式，而若取，则相应的公式就称为BFGS公式。BFGS公式也可记为BFGS公式可以看做DFP公式的改进，一般来说，BFGS公式比DFP公式有更好的数值稳定性。在用Matlab优化工具箱时，要根据具体问题的特点选择不同的优化算法、优化参数和一维搜索方法。Matlab提供最速下降法、DFP算法、BFGS算法等，但缺省设置为BFGS算法。Matlab中的一维搜索采用二次或三次插值。9.5 Powell方向加速法前面介绍的共轭梯度法、牛顿法、变尺度法都需要计算目标函数的梯度，这类方法统称为解析法。在实际中有许多问题的目标函数