第三章 梯度法和共轭梯度法

第三章无约束多变量问题优化1.无约束最优化问题2.最速下降法（梯度法）3.共轭梯度法一.无约束最优化问题无约束最优化问题nRxtsxf..)(min有一阶连续偏导数。其中)(xf解析方法：利用函数的解析性质构造迭代公式，使之收敛到最优解。下降迭代算法的概念回顾1.一般迭代算法集合S上的迭代算法A：（1）初始点0x；（2）按照某种规则A产生下一个迭代点)(1kkxAx。（i）如果点列}{kx收敛于最优解*x，则称算法A收敛。（ii）如果)()()(10kxfxfxf，则称算法A为下降迭代算法。.0x.1x.2x2.下降迭代算法步骤（1）给出初始点0x，令0k；（2）按照某种规则确定下降搜索方向kd；（3）按照某种规则确定搜索步长k，使得)()(kkkkxfdxf；（4）令kkkkdxx1，1:kk；（5）判断kx是否满足停止条件。是则停止，否则转第2步。搜索步长确定方法：)(min)(kkkkkdxfdxf称0)(kTkkkddxf。k为最优步长，且有二.最速下降法（梯度法）迭代公式：kkkkdxx1如何选择下降最快的方向？)(kxf)(kxf函数值下降最快的方向函数值增加最快的方向函数值下降的方向kx最速下降法（梯度法）：也称为最速下降方向；搜索方向：,)(.1kkxfd。即满足取最优步长搜索步长)(min)(,:.2kkkkkkdxfdxf最速下降法算法步骤：。令允许误差给定初始点1,0,.11kRxn;)(.2kkxfd计算搜索方向kkkxd否则，求最优步长为所求极值点；则停止计算，若,||||.3。使得)(min)(kkkkkdxfdxf。转令令2,1:,.41kkdxxkkkk,)1,2(,3)(min:.12221Txxxxf设初始点为用最速下降法求解例。求迭代一次后的迭代点2x解：,)6,2()(21Txxxf.)6,4()(11Txfd.)61,42(11Tdx，令2211)61(3)42()()(dxf)(min求解0)61(36)42(8)(令62131Tdxx)318,3136(1112收敛性)(min)(kkkkkdxfdxf。则有0)(kTkkkddxf性质.证明：所以，令)()(kkdxf.)()(kTkkddxf)(min)(kkkkkdxfdxf.0)()(kTkkkkddxf满足步长有一阶连续偏导数，若设kxf)(注：。kkkTkdddd110)(所以，因为梯度法的搜索方向)(1kkkkdxfd锯齿现象，其等值面近似数可以用二次函数近似在极小点附近，目标函椭球面。1x*x2x3x它只是。标函数的一种局部性质最速下降方向反映了目快的方向。局部目标函数值下降最注的算法。最速下降法是线性收敛三.共轭梯度法1.共轭方向和共轭方向法定义共轭。关于和，则称若有AddAddT21210ARdddnk它们两两关于中一组非零向量，如果是设,,,21。共轭，即kjijiAddjTi,,2,1,,,0共轭方向。组共轭的，也称它们是一则称这组方向是关于AA注：002121dddIdTT21dd共轭是正交的推广。，和中的两个非零向量的对称正定矩阵，对于是设21ddRnnAn是单位矩阵，则如果A共轭的非零个是阶对称正定矩阵，是设AkdddnAk,,,21性无关。向量，则这个向量组线.1定理证明，使得设存在实数k,,,21,01kiiid，则有上式两边同时左乘AdTj,01kiiTjiAdd可化简为共轭的向量，所以上式个是因为Akdddk,,,21.0jTjjAdd，是正定矩阵，所以而因为0,0jTjjAddAd所以。kjj,,2,1,0线性无关。因此kddd,,,21几何意义设有二次函数)()(21)(xxAxxxfT对称正定矩阵，是其中nnA是一个定点。x的等值面则函数)(xfcxxAxxT)()(21为中心的椭球面。是以x由于,0)()(xxAxf,0)(2AxfA所以正定，因为的极小点。是因此)(xfxx,)(2Axf而点，是在某个等值面上的一设)0(x处的法向量为该等值面在点)1(x.)()()1()1(xxAxfo1x2xx)1(d)0(x中的一个方向，是nRd)1(。以最优步长搜索得到点沿着)1()1()0(xdx所在等值面的切向量。是点则)1()1(xd正交，与则)()1()1(xfd,0)()1()1(xfdT即,)1()2(xxd令)1(x所以,0)2()1(AddT共轭。小点的向量关于向量与由这一点指向极即等值面上一点处的切A)2(d.2定理，设有函数cxbAxxxfTT21)(共轭向量。一组是阶对称正定矩阵。是其中AdddnAk)()2()1(,,,进行搜索，为初始点，依次沿以任意的)()2()1()1(,,,kndddRx上的在是函数则得到点kkkBxxfxxxx)1()1()1()3()2()(,,,,极小点，其中},|{1)(RdxxBikiiik是时，当，生成的子空间。特别地是由)1()()2()1(,,,nkxnkddd上的唯一极小点。在nRxf)(推论有在上述定理条件下，必。kidxfiTk,,2,1,0)()()1(共轭方向法对于极小化问题:法为共轭方向法是正定矩阵，称下述算其中A,21)(mincxbAxxxfTT；共轭方向取定一组)()2()1(,,,)1(ndddA,,)2()1()()1(kkxxx确定点依次按照下式由任取初始点)(min)()()()()()()()1(kkkkkkkkkdxfdxfdxx。满足直到某个0)()()(kkxfx注至多经过求解上述极小化问题，可知，利用共轭方向法由定理2。次迭代必可得到最优解n2.共轭梯度法如何选取一组共轭方向？:共轭梯度法eevesRFletcher代点向相结合，利用已知迭将共轭性和最速下降方基本思想：进行搜索，求出共轭方向，并沿此方向处的梯度方向构造一组函数的极小点。以下分析算法的具体步骤。cxbAxxxfTT21)(min是常数。，是对称正定矩阵，其中cRbARxnn,；，第一个搜索方向取为任取初始点)()1()1()1()1(xfdx，令，若，设已求得点)(0)()2()1(1)1()1(kkkkxfgxfx:)1(按如下方式确定则下一个搜索方向kd)1()(1)1(kkkkdgd令共轭。关于和要求Addkk)()1(？如何确定k，得）式两边同时左乘则在（AdTk)(1)()(1)()1()(0kTkkkTkkTkdAdAgdAdd)2()()(1)(kTkkTkkdAdgAd解得:)3(搜索步长的确定，步长利用一维搜索确定最优和搜索方向已知迭代点kkkdx,)()(。即求解)(min)()(kkdxf,)()()()(kkdxf记，令0)()()()()(kTkkddxf，即有0])([)()()(kTkkdbdxA，则有令bAxxfgkkk)()()(，0][)()(kTkkdAdg)3()()()(kTkkTkkAdddg解得3定理次算法在，对于正定二次函数nmFRcxbAxxxfTT21)(），下列关系成立（且对所有的一维搜索后即终止，并mii1;1,,2,1,0)1()()(ijAddjTi;1,,2,1,0)2(ijggjTi。iTiiTiggdg)()3(注共轭的。是可知搜索方向）由定理（Adddm)()2()1(,,,31则构造的搜索必须取负梯度方向，否算法中第一个搜索方向)2(方向不能保证共轭性。）可知，的（由定理33)3(,0||||2)(iiTiiTigggdg处的下降方向。是迭代点所以)()(iixd的计算公式可以简化。算法中，由定理iFR3)4()()(1)(iTiiTiiAddgAd)()()(1iTiiTiAdddAg]/)([]/)([)()1()()()1(1iiiTiiiiTixxAdxxAg.)()()(bxAxfgiii)()(1)(11iiTiiiTiiggdgggiTiigdg)(21||||)4(||||||||221iigg算法步骤：FR。，令精度要求，任取初始点1.1)1(kx为所求极小点；停止，若令)1(1)1(1,||||,)(.2xgxfg。令，）计算利用公式（否则，令)1(1)1()2(11)1(3,dxxgd为所求极小点；停止，若令)1(1)1(1,||||,)(.3kkkkxgxfg）计算。用公式（其中否则，令4,)(1)1(kkkkkdgd。转，令）计算利用公式（3,3.4)()()1(kkkkkdxx。令1:kk算法求解下述问题：用例FR22212)(minxxxf。初始点取为Tx)2,2()1(解：.)2,4()(21Txxxf次迭代：第1,)4,8(1)1(Tgd令)1()1()1(11AdddgTT,2004),(21)(2121xxxxxf.2004A而482004)4,8(48)4,8(185)1(1)1()2(dxx所以TT)4,8(185)2,2(T)98,92(次迭代：第2.)916,98(2Tg21221||||||||gg.81448)916()98(2222)1(12)2(dgdTT)4,8(814)916,98(T)4,1(8140)2()2()2(22AdddgTT412004)4,1()8140(41)916,98(81402209)2(2)2()3(dxxTT)4,1(8140209)98,92(T)0,0(Tg)0,0(3即为所求极小点。)3(x3.用于一般函数的共轭梯度法nRxtsxf..)(min共轭梯度法进行修改：对用于正定二次函数的确定。）计算，需由一维搜索不能利用公式（搜索步长3)2(i。速下降方向，即第一个搜索方向仍取最)()1()1()1(xfd算：其它搜索方向按下式计,)()()1()1(iiiidxfd。其中2)(2)1(||)(||||)(||iiixfxf此时可采取一定能满足停止条件，算法在有限步迭代后不)3(如下措施：没有求成一轮搜索后，如果还次迭代为一轮，每次完以n新的初始点，的最后一个迭代点作为得极小点，则以上一轮一轮搜索。一个搜索方向，开始下取最速下降方向作为第注，如算采用其它形式的公式计在共轭梯度法中，也可i。）共轭梯度法PRPgggggiTiiiTii()(11