最优化方法第三章(1)

1、 从本章起，以后两章将讨论非线性规划问题。本章首先讨论无约束最优化问题，其一般形式为)(minxf（3.1） 其中 1:RRfn 求解无约束问题的最优化方法可以分为两大类：一类是根据目标函数的梯度（即一阶导数），有时还要根据Hesse矩阵（即二阶导数）提供的信息构造出来的方法导数方法导数方法。本章介绍其中的最速下降法、Newton法、共轭梯度法和拟Newton法。另一类是不使用导数，仅仅利用目标函数值的信息构造出来的方法直接方法直接方法。本章将介绍其中的步长加速法、方法加速法和单纯形替换法。两类方法各有利弊。前者收敛速度快，但需要计算梯度，甚至需要计算Hesse矩阵；后者不涉及导数，适应性强，

2、但收敛速度慢。一般的经验是，在可以求得目标函数导数的情况下，尽可能使用导数方法。3.1 直线搜索直线搜索 直线搜索（一维搜索）是指求解如下一元函数极小化问题min( ) t（3.3） 的迭代方法，其中11:RR 。在微积分中，解决问题（3.3）的范围一般限于方程0)( t（3.4）可以直接解出的情况。而这里介绍的直线搜索对 严格的要求。当然，对于可以求出导数的情况，相应的求解方法一般也会简单些。不作直线搜索，理论上，分为精确的和不精确的。 精确的直线搜索方法主要分为两类：一类为区间收缩法，另一类为函数逼近法。本节将相应地介绍两种常用的精确的直线搜索方法：适用于一般函数的黄金分割法和适用于一般连

3、续函数的抛物线插值法。最后还将介绍实用的不精确一维搜索技术。 精确的直线搜索算法的实现通常是在所谓的搜索区间上进行的 1. 搜索区间的确定搜索区间的确定在以下讨论中，总假定一元函数)(t是单谷函数。11:RRL*t)(t定义定义3.1 设，是 在L上的全局极小点。如果对于L上任意的两点 1212,t ttt，当*2tt 时， )()(21tt；当*1tt 时， )()(21tt，那么称 )(t是区间L上的单谷函数单谷函数。下图给出了单谷函数的基本图形。定义定义3.2 设 11:RRL,*t是)(t在L上的全局极小点。如果能够找到 Ltt21,*12 , ,tt t，使得 ,21tt)(t那么闭

4、区间就称为极小点的一个搜索区间搜索区间，记为 ,21tt132 , , t t t132ttt。搜索区间有时也记作，其中显然，单谷函数的定义域区间是搜索区间。单谷函数的性质。,ba)(t定理定理3.1 设是单谷函数极小点的一个搜索区间。),(ba1212,t ttt在内任取两点 ，若)()(21tt，则 ,2ta)(t是极小点的一个搜索区间；若 )()(21tt,1bt)(t，则是极小点的一个搜索区间。 直线搜索算法的第一步一般得先确定)(t的一个 （初始）搜索区间。根据定理3.1，可以给出确定搜索区间的如下算法。算法算法3.1（确定搜索区间）已知：目标函数)(t。0th选定初始点和步长。)(

5、00thtt02)(22t计算，。0201tt 若，则置，01tt 0120tt 20hh2，。01,hh ，转； 否则转。置htt02)(22t02计算，。若，则转；否则转。,min21tta ,max21ttb ,ba置，（即为搜索区间），计算结束。上述过程开始时，必须选定初试点 0th和步长 。对于 任意给定的 )(t，一般来说， 无固定选取模式。)()(kkp txft0t但对于在下降算法模式中所引入的而言，可选取等于0（理论上）或接近0（实际计算中）。而对于 ，如果选得过小，那么需要迭代许多次才能找到一个搜索区间；如果选得太大，虽然很少几步就可能把极小点包括进来，但是这又会给下一步搜

6、索极小点的过程增加负担。下面是确定 的一种比较合理而有效的方法。hh0k0 x1x第一次迭代（，即从到的迭代）时， )(t的初始步长可取为1，或根据问题中出现的数据的数量级估计选定。而以后各次迭代的初始步长可按公式（3.5）计算， kkkpxxh1（3.5）其中 。这是因为从 到 的距离 一般比从 到 的距离 小或接近，所以把按（3.5）算出的作为下一次迭代的初始步长是合适的。在实际计算中，当 较小时，相应的 可取得小些，而随着的 增大，相应的 可取得接近1。kx1kxkkxx1101kxkx1kkxxkk2. 直线搜索的方法直线搜索的方法（1）黄金分割法 黄金分割法属于区间收缩法。它适用于任

7、何单谷函数求极小值问题。对函数除“单谷”外，不作其它要求，甚至可以不连续。因此这种方法的适用面相当广。 黄金分割法的思想是：在每次迭代中，合理地设置两个插入点的位置，以使得在计算函数值次数同样多的条件下，将区间缩小得最快。 a设区间 的长为1。在距点 分别为 和 的地方插入 和 。为了确定 和 ，提出以下条件： 1t2t,baa 第一，希望 和 在 中的位置是对称的。按这一条件，有1t2t,babtat21即 1. （3.6）这样无论删去哪一段，总保留长为的区间。,2bt第二，删掉一段，例如删掉3t，在保留下来的区间，使得里再插入一个点13,tt,2ta12,t t,ba在中的位置与在中的位置

8、具有相同的比例，从而保证每次迭代都能缩小区间。按这一条件，有以同一比率abatatat221即 1或 2. （3.7）把（3.7）代入（3.6）中，得到关于的一元二次方程其合理的根是618. 0215（3.8）代回（3.6），得382. 0253 在古代，人们认为按比率0.618分割线段是最协调的，胜似黄金，故称黄金分割。因此，上述按比率0.618缩小搜索区间的迭代方法称为黄金分割法黄金分割法或0.618法法。算法算法3.2 （黄金分割法）（黄金分割法）P145（2）抛物线插值法 抛物线插值法属于函数逼近法。它适用于连续的单谷函数求极小值问题。 抛物线插值法的思想是：设 11:RR 在搜索区间

9、,321ttt上连续。记 1122( ),( )tt)(33t和。 如果321ttt（3.9） 与123（3.10）（两等号不同时成立）同时成立，那么可以过 1122( ,),( ,)tt),(33t和 三点作抛物线插值，设抛物线方程为rqtpttQ2)(（3.11）( )yQ t13 , t t( )yt其实是在区间上对所作的一个曲线拟合。( )yQ t4t4t记的极小点为，则根据 提供的信息，我们可以将搜索区间 13 , t t缩小，然后在缩小了的区间上再作抛物线插值。如此下去，最终可以求到 )(t,31tt在 中的极小点*t。 令( )20Q tptq(3.12）解出 pqt24（3.1

10、3）1122( ),( )Q tQ t33)(tQ根据插值条件和，列出关于 qp,r和的线性方程组211122222333ptqtrptqtrptqtr由此解出)()()()()(133221321213132ttttttttttttp，)()()()()(133221322212212312322ttttttttttttq，并代入（3.13）中，得)()()(2)()()(3212131323222122123123224ttttttttttttt（3.14）1122( ,),( ,)tt),(33t这个公式的使用条件仅仅是和 三点不共线。可以证明（习题3.5），在（3.9）和（3.10）（

11、两等号不同时成立）同时成立的条件下，由（3.14）所确定的 4t)(tQ341ttt是的极小点，并且。以下讨论算法的终止准则和缩小搜索区间的方法。按（3.14）计算出4t。由极限理论知道，如果 *2tt *4tt 42tt24与都很小，那么也必然很小，当然也应该很小。 计算经验指出，可以采用1224（3.15） 作为终止准则。4t2t4t,321ttt当终止准则满足时，取和中函数值较小的点提供的缩小。这个过程如下：作为极小点；当终止准则未满足时，则需要利用信息将原来的搜索区间4t2t24tt 比较和的大小，有两种情况：若，则转；否则，转。243434,tt若，则置，转； 2421tt 2412

12、24,tt 若，则，转。 置241414,tt若，则置，转； 2423tt 243224,tt 若，则，转。置,321ttt转向计算新的搜索区间上的插值抛物线的极小点算法流程图见书上图3-5。 包括黄金分割法和抛物线插值法在内的许多一维问题的迭代方法全部依赖于函数单谷性的假设。但在许多问题中，这一假设不成立或难以验证。解决这一困难的办法，尤其当初始搜索区间很大的时候，是将搜索区间分成若干个较小区间，然后在每个子区间上寻求极小，最后又在所有子区间的极小中选取最小的一个作为问题的最优解。（3）不精确一维搜索技术 精确的一维搜索过程往往需要花费很大的计算量才有可能求到符合精度要求的最优步长因子。当多

13、维问题的迭代点距极小点较远时，显然精确地求解一维子问题对求解多维问题本身没有太大的意义。另外很多最优化方法，如Newton法和拟Newton法，其收敛速度也并不依赖于精确的一维搜索过程。因此，在实际计算中，只要选取的步长因子能够保证目标函数在每一步的迭代中都有“满意的”下降就可以了。这样，既会大大地节省计算量，同时还会从整体上加快计算进程。考虑由多维问题引出的一维问题),()(minkkp txft（3.16）其中1:RRfn具有一阶连续偏导数。 Goldstein(1965年)和Powell（1975年）给出了用来设计（3.16）不精确一维搜索过程的两个条件： ）1()()()Tkkkkkf

14、 xf xtf xp ； （3.17）1()()TTkkkkf xpf xp (3.18).ktkkkkptxx1) 10(,其中使得，而是给定的常数，通常取 210。条件）表示应使新迭代点1kx的函数值相对上一迭代点 kx的函数值的下降幅度须不低于某个量，而条件）则表示目标函数 f在新迭代点1kx处沿 kp方向的方向导数应不小于 ff在上一迭代点 kx处沿kp方向的方向导数的 倍。换句话说，若 1kx满足 条件），则认为在点 1kx处已获得“满意的”函数值的下降。 而若1kx满足条件），这时有两种可能性， 要么kp已是点 方向1kx处的上升方向， kp1kx要么方向虽然还是点下降方向， 处的

15、f1kx但函数在点 处沿kp方向的下降率已低于 处沿kp方向的下降率f在点kx 倍，这时若继续沿 kp方向作一维搜索，只会徒增计算量，而不会再获得函数值的较大下降量，因此，一旦 1kx满足条件）就需要确定1kp。新的搜索方向 以上分析表明，在实际计算中，选取满足（3.17）和（3.18）的 kt作为确定1kx的步长因子是合适的， 即kkkkptxx1。一般地， 越小，一维搜索越精确，但计算量也越大。 不精确的一维搜索不要求过小的而越小，条件）越容易满足。 0.14 . 0在实际计算中，通常取或更小的值值的选取不太敏感），。（由此得出的解通常对算法算法3.3（不精确一维搜索）( )()kktf

16、xtp()0Tkkf xp已知：，且。给定1),1 ,(),21, 0( 2t（通常取），初始（可取1或参照（3.5）给出）。步长(),()kkkkff xgf x 0,0abj 计算。置。计算11111,(),()kkkkkkkxxt pff xgf x ；若（3.18）成立，则转；否则，置,min,1abat tajj，然后转； ttk,1abbt tjj若（3.17）成立，则打印，计算结束；否则，然后转。置 算法说明：）第步中若（3.18）不成立，则表明沿kp方向有继续前进的必要； ）第步中若（3.17）不成立，这表明当前步长过大，需缩小搜索范围。不精确一维搜索的算法流程图3.2 最速下

17、降法最速下降法 最速下降法是最早的求解多元函数极值的数值方法。它直观、简单。它的缺点是，收敛速度较慢、实用性差。1. 基本思想基本思想1,kxxkx求解问题（3.1）。假设迭代已得到。在点处，取搜索方向为()kkpf x （3.19）沿kp进行直线搜索，由此确定1()kkkkxxtf x （3.20） 其中步长因子kt满足()min()kkkkktf xtf xf xt f x （3.21） （3.20）、（3.21）简单地合记为1(,()kkkxls xf x（3.22） 3.20）或（3.22）称为最速下降迭代公式最速下降迭代公式，由该公式产生的算法称为最速下降法最速下降法。 今后记()(

18、)kkkgg xf x 2. 算法算法算法算法3.4（最速下降法） P151将最速下降法应用于正定二次函数1( )2TTf xx Qxb xc（3.23） 可以推出显式迭代公式。kkx1kx设第迭代点为，求的表达式。由( )g xQxb（3.24）kkgQxb （3.25）1kkkkxxt g， （3.26），10Tkkgg，（直线搜索性质）得 ()0TkkkkQ xt gbg即0Tkkkkgt Qgg由此解出TkkkTkkg gtg Qg （3.27） 例例3.1 P1523. 锯齿现象锯齿现象 最速下降法的迭代点在向极小点靠近的过程中，走的是曲折的路线：后一次搜索方向 1kp与前一次搜索方

19、向 kp总是相互垂直的，称它为锯齿现象锯齿现象。这一点在前面的例题中已得到验证。除极特殊的目标函数（如等值面为球面的函数）和极特殊的初始点外，这种现象一般都要发生。 从直观上可以看到，在远离极小点的地方，每次迭代都有可能使目标函数值有较多的下降，但在接近极小点的地方，由于锯齿现象，每次迭代行进的距离开始逐渐变小。因而收敛速度不快。 已有结论表明，最速下降法对于正定二次函数关于任意初始点都是收敛的，而且恰好是线性收敛的。3.3 Newton法法( )f xnR如果目标函数在上具有连续的二阶偏导数，其Hesse矩阵 2( )f x正定且可以表达成显式（今后记 2( )( )G xf x ），那么使

20、用Newton法求解（3.1）会很快地得到极小点。 1. 基本思想基本思想kx1kxkx( )f x考虑从到的迭代过程。在点处，对按Taylor级数展开到第三项，即1( )( )()() ()()()()2TTkkkkkkf xQ xf xg xxxxxG xxx （3.29） ()kG x( )Q x因为正定，所以是正定二次函数。令( )()()()0kkkQ xG xxxg x 得()()()kkkG xxxg x （3.30） ( )Q x1kx由此解出的极小点，记为，即11()()kkkkxxG xg x（3.31） 1kx( )f x*x是极小点的新的近似点。 （3.31）称为New

21、ton迭代公式迭代公式，由该公式产生的算法称为Newton法法。( )f x( )( )f xQ x注意到，当目标函数是正定二次函数（3.36）时，。这说明：对于正定二次函数，Newton法一次迭代就会得到最优解。( )f xkx（3.31）有直观的几何解释。函数过点的等值面方程为( )()kf xf x（3.32）在点kx处，用一个与曲面（3.32）最密切的二次曲面来代替它，这个二次曲面的方程即是( )()kQ xf x()kG x( )Q x当正定时，它是一个超椭球面，的极小点 1kx正是这个超椭球面的中心。我们就用 1kx( )f x*x作为极小点 的新的近似点。下图画出了二维情况时的几何解释。例例3.2 P1542. 算法算法算法算法3.5（Newton法） P1553. 修正修正Newton法法 Newton法的优点是收敛速度快、程序简单。特别是前一个优点，在最优化方法中