3无约束优化

第四章无约束问题的最优化方法(一)最速下降法(梯度法)基本思想以迭代点的负梯度方向为搜索方向迭代公式X(k+1)＝X(k)+αk▽F(X(k))(k=0,1,2,…)算法特点迭代过程中，相邻的搜索方向相互垂直，即向极小点的逼近路径是一条曲折的锯齿形路线。对初始点要求不高，最初几步下降快，越来越慢。最速下降法的搜索路径开始是k←0给定X(0)、εk←k+1)()1(kkXX否)1(kXX结束最速下降法程序框图)()()(kkXFSkkkkkkkSXFSXX求)(min)()()()()1(例用最速下降法求22214)(xxXF的极小值，设初始点TT)0(2)0(1)0(]22[][xxX解：目标函数的梯度T21T21]82[)()()(xxxXFxXFXF收敛要求ε1=10-2。在X(0)点的梯度为T)0(]164[)(XF梯度的模为492.16164)()()(2222)0(21)0()0(xXFxXFXF负梯度方向为TT)0()0()0(]970.0243.0[]164[492.161)()(XFXFS22)0()0()970.02(4)243.02()(SXFT)1(]738.0952.2[)(XF0923.0476.1157.20d)(d)1()0()0(XSXF，)1(2)1(1)0()0()1(970.02243.02970.0243.022xxSXX043.3)738.0()952.2()(22)1(XF新的搜索方向TT)1(]243.0970.0[]738.0952.2[043.31S，继续搜索；21)1(10043.3)(XF)2(2)2(1)1()1()2(243.009232.0970.0476.1243.0970.00923.0476.1xxSXX22)1()1()243.00923.0(4)970.0476.1()(SXFT)2(]776.1444.0[)(XF222.0222.0293.10d)(d)2()1()1(XSXF，，继续搜索；122)2(831.1)776.1()444.0()(XF新的搜索方向TT)2(]970.0242.0[]776.1444.0[831.11S)3(2)3(1)2()2()3(970.0222.0242.0222.0xxSXX22)2()2()970.0222.0(4)242.0222.0()(SXF0098.0164.0293.00d)(d)3()2()2(XSXF，…新的搜索方向00256.0]975.0223.0[T)6(S继续搜索；，122)3(337.0)0784.0()328.0()(XFT)3(]0784.0328.0[)(XF000096.00016.0)7(2)7(1xx6)7(T)7(10596.2)(,]000768.000032.0[)(XFXF0)(]00[TXFX当k=7时，停止搜索。1)7(0032.0)(XF(二)牛顿法基本思想在X(k)点用一个二次函数Φ(X)去逼近F(X)，求出Φ(X)的极小点作为原目标函数F(X)的极小点的一次近似值进行迭代计算。迭代公式X(k+1)＝X(k)－[H(X(k)]-1▽F(X(k))(k=0,1,2,…)X(k+1)＝X(k)－αk[H(X(k)]-1▽F(X(k))(k=0,1,2,…))()(21)()()()()(kTkkTkkXXHXXXXXFXFXXF0)(1kX0)()(1kkkXXHXF故迭代公式X(k+1)＝X(k)－[H(X(k)]-1▽F(X(k))(k=0,1,2,…))()(1kkkkxFxFxx阻尼牛顿法其迭代公式为X(k+1)＝X(k)－αk[H(X(k))]-1▽F(X(k))(k=0,1,2,…)阻尼牛顿法避免了牛顿法可能收敛于极大点或鞍点的不足，具有二次收敛特性，并且即使初始点选择不当，用这种探索方法也会成功。几点说明：⑴当海赛矩阵非正定或奇异时，牛顿法搜索失败或不能进行迭代。⑵计算工作量大，当F(X)不可微时，此算法不能用。开始是k←0给定X(0)、εk←k+1)()1(kkXXkkkkkkkSXFSXX求)(min)()()()()1(否)1(kXX结束阻尼牛顿法程序框图)()]([)(1)()(kkkXFXHS例用牛顿法求60410)(21212221xxxxxxXF的极小值。设初始点TT)0(2)0(1)0(]00[][xxX解：41042102)()()(122121)0()0(xxxxxXFxXFXFXXXX2112)()()()()()()0(222122212212)0(2)0(XXxXFxxXFxxXFxXFXFXH2112312112)]([1)]([)0(1)0(XHXH其逆矩阵为681824310041021123100)()]([)0(1)0()0()1(XFXHXXT21T)1(][]68[xxXX只迭代一次就达到了最优点。0042102)(1221)0(xxxxXFXX(三)共轭方向1.共轭方向的概念设A为正定对称矩阵，若有一组非零向量S1，S2，…，Sn满足)(0TjiASSji则称这组向量关于矩阵A共轭。若A为单位矩阵，则有)(0TjiSSji负梯度方向与共轭方向α0S(0)X(1)X(0)Xα1S(1)S(2))()1(XF此时称向量Si(i=1，2，…，n)相互正交。共轭是正交的推广，正交是共轭的特例。共轭方向对于构造一种有效的算法非常重要。2.共轭方向的性质对于一般函数，共轭方向具有以下性质：⑴若S(i)(i=1,2,…,n)是以A共轭的n个向量，则对于正定二次函数从任意初始点X(0)出发，依次沿这n个方向进行一维搜索，最多n次即可达到极小点。⑵从任意两个点X1(0)和X2(0)出发，分别沿同一方向S(0)进行一维搜索，得到两个一维极小点X1(1)和X2(1)，则连接此两点构成的向量S(1)＝X2(1)－X1(1)与原方向S(0)关于该函数的二阶导数矩阵相共轭。)0(S)1(S)0(S)()1(1XF)1(1X)1(2X)()1(2XF通过一维搜索确定共轭方向提供共轭向量系的方法有多种，如共轭梯度法、鲍威尔(Powell)法等等。(四)共轭梯度法基本思想利用相邻两点的负梯度构造共轭方向，使其尽快达到最优点。迭代公式2)(2)1()()()()1()1()()()1()()()(kkkkkkkkkkkXFXFSXFSSXXX)(jS)(kS)(kX)1(kX)()1(kXF)()(kXF)()()()1(kkXFXF共轭梯度的几何说明2)(2)1()()()()1()1()()()1()()()(kkkkkkkkkkkXFXFSXFSSXX算法特点所需的存贮量少，不用计算二阶偏导数矩阵及其逆阵，计算简单，收敛速度快。开始是给定X(0)、εk←k+1kkkkkkkSXFSXX求)(min)()()()()1(否)1(kXX结束)()1(kXF)(0)0()0(XFSk2)(2)1()()()1()1()()()(kkkkkkkXFXFSXFS是k=n否)1()0(kXX共轭梯度法程序框图例用共轭梯度法求60410)(21212221xxxxxxXF的极小值。设初始点TT)0(2)0(1)0(]00[][xxX解：41042102)()()(122121)0()0(xxxxxXFxXFXFXXXX410)()0()0(XFS第一次迭代的搜索方向526315788.5210526304.2)()1(XF052631576.363157894.7763157894.00d)(d)1()0()0(XSXF，410)0()0()1(SXX305401661.011642659273.35)]([)]([2)0(2)1()0(XFXF747922432.684390306.0)()0()0()1()1(SXFS436781609.00d)(d)1()1(SXF)1()1()2(SXX第二次迭代的搜索方向XX999999993.5999999993.7)2((五)变尺度法基本思想利用牛顿法的迭代形式，构造一个对称正定矩阵A(k)来代替目标函数F(X)的[H(X)]-1，并在迭代过程中使其逐步逼近[H(X)]-1。迭代公式)(][)()()()()()()1(kTkkkkkkXFASSXX算法特点简化了牛顿法的计算，且保持了牛顿法收敛快的优点。说明：⑴当A(k)＝I(单位矩阵)时，上式为梯度法的迭代公式；⑵当A(k)＝[H(X)]-1时，上式为牛顿法的迭代公式。在实际应用中，当k=0时，一般令A(0)＝I。因此，变尺度法在最初的几步迭代，与梯度法类似，函数值下降较快；在最后几步迭代，与牛顿法相近，可较快地收敛到极小点。1.构造变尺度矩阵应遵循的原则⑴A(k)必须是对称正定矩阵，以保证算法具有下降性质。⑵A(k)具有简单的递推形式，以保证算法的方便性。A(k+1)=A(k)+E(k)式中E(k)为第k次的校正矩阵。⑶要求迭代产生的搜索方向S(k)=-[A(k)]T▽F(X(k))关于矩阵H(X(k))共轭，以保证算法的二次收敛性。2.变尺度法的一般步骤⑴选定初始点X(0)和收敛精度ε；⑵计算g(0)=▽F(X(0))，选取初始对称正定矩阵A(0)＝I，k←0；⑶计算搜索方向S(k)=－A(k)g(k)；⑷沿S(k)方向进行一维搜索X(k+1)=X(k)+α(k)S(k)，计算g(k+1)=▽F(X(k+1))，ΔX(k)=X(k+1)－X(k)，Δg(k)=g(k+1)－g(k)和E(k)；⑸判断是否满足迭代终止准则，若满足，则X*=X(k+1)，停止计算。否则转⑹；⑹当迭代n次后还没找到极小点，重置A(k)＝I，并以当前设计点为初始点X(0)←X(k)，返回⑵进行下一轮迭代，否则转⑺；⑺计算A(k+1)=A(k)+E(k)，置k←k+1，返回到⑶。说明校正矩阵E(k)的不同计算公式，确定了不同的变尺度法，如DFP(Davidon-Fletcher-Powell)法，BFGS(Broyden-Fletcher-Goldfarb-Shanno)法等。例用DFP法求2221)6()5(4)(xxXF的极小值。设初始点TT)0(2)0(1)0(]98[