最优化共轭梯度法

共轭梯度法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1()||||(iiiTigDixondg共轭梯度法）。