第三章--无约束最优化的梯度方法

第三章无约束最优化的梯度方法1.最速下降法假定我们已经迭代了k次，获得了第k个迭代点kx。从kx出发，显然应沿下降方向进行，由于负梯度方向是最速下降方向，因此沿负梯度方向应该是有利的。因此，取搜索方向)(kkxfp。)(1kkkkxftxx此时有：0)()(1kTkxfxf如将该方法应用于二次函数cxbQxxxfTT21)(，则可求出kt的显式表达式。)()()())(()(1kkkkkkkkkkxfQtxfxfQtbQxbxftxQbQxxf0)()()()(kTkkkTkxfQxftxfxfkTkkTkkTkkTkkQggggxfQxfxfxft)()()()(2.Newton法适用条件：如果目标函数)(xf在nR上具有连续的二阶偏导数，其Hesse矩阵)(xG正定。基本想法：考虑从kx到1kx的迭代过程。在kx点处用二次函数来逼近)(xf，即：))(()(21)()()()()(kkTkkTkkxxxGxxxxxgxfxQxf0)())(()(kkkxgxxxGxQ)()(11kkkkxgxGxxx3.共轭方向法与共轭梯度法1)共轭方向法定义1:设Q是nn对称正定矩阵。若n维空间中非零向量系110,...,,mppp满足0jTiQpp，)(1,...,2,1,jimji,则称110,...,,mppp是Q共轭的，或称110,...,,mppp的方向是Q共轭方向。定理1:若非零向量系110,...,,mppp是共轭的，则这m个向量线性无关。推论：在n维空间中，互相共轭的非零向量的向量个数不超过n。定义2:设110,...,,mppp是线性无关的向量系，110,...,,m是任意实数。对于任意指定的nRx0，称形式为100miiipxz的向量集合称为由点0x和向量系110,...,,mppp所生成的线性流形，记为1100,...,:mpppxL。定理2:假设：①Q为nn对称正定矩阵②非零向量110,...,,mppp是Q共轭向量系；③对二次目标函数cxbQxxxfTT21)(顺次进行如下m次直线搜索：),(1iiipxlsx，1,...,1,0mi，其中nRx0是任意选定的初始点。则①0)(mTjxfp,mj0②mx是二次函数在线性流形1100,...,:mpppxL上的极小点。证明①：前面已经证明0)(1mTmxfp由条件③可知iiiiptxx1上式左乘Q后再在两边加上b，得：iiiiQptbQxbQx1即：iiiiQptxfxf)()(1由上式有)(mxf111)(mmmQptxf22112)(mmmmmQptQptxf.............................111)(mjiiijQptxf，)20(mj将所得等式两边左乘Tjp，有0)()(111mjiiTjijTjmTjQpptxfpxfp证明②:按条件③，],...,,:[1100mmpppxLx，则存在一组数110,...,,m使得100miiimpxx同样，对于任意100miiipxx上面两式相减得10)(miiiimpxx由结论①0)(mTjxfp可知0)()()()(10mmiTiiimTmxfpxfxx)()(21)()()(21)()()()(mTmmmTmmTmmxxQxxxfxxQxxxfxxxfxf由于Q是正定的，因此mx是在线性流行1100,...,:mpppxL上的极小点。当nm时，线性流行1100,...,:mpppxL就是整个n维空间nR了，因此此时mx就是nR中的极小点。共轭方向法：已知：具有正定矩阵Q的二次目标函数cxbQxxxfTT21)(和终止限。①选定初始点0x和具有下降方向的向量0p；置0k。②作直线搜索),(1kkkpxlsx。③判别)(1kxf是否满足：若满足，停机。④提供共轭方向1kp，使得01kTjQpp，kj,...,1,0⑤k=k+1二次函数的直线搜索：0))(()(kkTkkkTktQpxfptpxfpkTkkTkQppxfpt)(kkTkkTkkkpQppxfpxx)(1共轭向量系110,...,,mppp的构造方法：先选定n个线性无关的向量系110,...,,nvvv，令00vp设已求得共轭向量kppp,...,10，现在来求1kp令krrrkkkpvp0,111为使1kp与),...1,0(kjpj共轭，应有：0)(0,111krrrkkTjkTjpvQpQpp，kj,...1,0由此解得：jTjkTjjkQppQvp1,1于是jkjjTjkTjkkpppQvpvp0111共轭方向法的适用范围：可用于非二次函数，首先通过Taylor公式用二次函数来逼近非二次函数。其次，可用)(02xfQ来构造共轭向量系，这要求0x充分地靠近*x。2)共轭梯度法初始共轭向量0p恰好取为初始点0x处的负梯度0g，以下各共轭方向kp由第k迭代点kx处的负梯度kg与已得到的共轭向量的线性组合来确定。因为该方法每一个共轭向量都是依赖于迭代点处的负梯度构造出来的，所以称为共轭梯度法。设已求得共轭向量110,...,kppp，现在来求kp由01kTkgp，知1kp和kg是线性无关的，取11kkkkpgp考虑kp与1kpQ共轭，需满足：011111kTkkkTkkTkQppQpgQpp于是有：1111kTkkTkkQppQpg1111kkTkkTkkkpQppQpggp现在证明kp除与1kp共轭外，还与210,...,kppp共轭。对2,...,1,0kj依次计算jTkkjTkjTkkTkjTkQppQpgQppgQpp1111)(由于110,...,kppp是共轭向量，因此01jTkQpp，2,...,1,0kjjTkjTkkjTkjTkkTkjTkQpgQppQpgQppgQpp1111)(因为iiiiQptxfxf)()(1jjjTkjTktgggQpg/)(1又因为0)(mTjxfp,mj0从共轭向量系构建方法可以看出，迭代点处的梯度是共轭向量系的线性组合。00pg，0111ppg，1222ppg因此有：)(11jjjppg，)(11111jjjjjpppg01jTkjTkgggg,2,...,1,0kj从而证明了kp与110,...,kppp共轭。共轭梯度法在非二次函数中的应用：为了把共轭梯度法应用在非二次函数中，有必要消去表达式kkTkkTkkkkkkpQppQpggpgp1111中的Q。由于kkkktggQp/)(1)()(111kkTkkkTkkggpggg因为01kTkgp，kTkkTkkkTkgggpggp)(1kTkkkTkkTkkTkkkkkTkkkTkkggggggpggggggpggg)()()(111121111根据k表达式的不同，可得到四种共轭梯度算法。最常采用的是第二种表达方式。4.变尺度法1)基本想法考虑Newton迭代公式kkkkgGxx11，,...1,0k变尺度法就是要消除这个迭代公式中的Hesse逆矩阵1kG，为此拟采用某种近似矩阵)(kkxHH来替换它，即构造一个矩阵序列kH去逼近kG。因此，迭代公式为kkkkkgHtxx1其中kt可通过从kx出发沿kkkgHp作直线搜索来确定。为使kH确实与1kG近似并具有容易计算的特点，对kH附加下列条件。①要求kH对称正定，保证迭代公式具有下降性质。如kH对称正定，则0kkTkkTkgHgpg，保证迭代公式具有下降性质。②要求kH之间的迭代具有简单的形式。kkkEHH1，其中kE称为校正矩阵，上式称为校正公式。③kH必须满足拟Newton条件kkkkkxxggH111)(对于二次函数cxbQxxxfTT21)(而言,有:bQxgkkbxQxgkk11上面两式相减有:)(11kkkkxxQgg如Q的逆存在,则有kkkkxxggQ111)(kkkkkxxggH111)(成立,表明1kH能很好近似11kQ。如记kkkggy1，kkkxxs1，于是拟Newton条件可写为：kkksyH1拟牛顿法算法：已知：目标函数)(xf及其梯度)(xg，终止准则。①选定初始点0x；计算)(),(0000xggxff，选定初始矩阵0H。②计算搜索方向kkkgHp。③作直线搜索),(1kkkpxlsx。④如满足终止准则，停机。⑤计算kkkEHH1。⑥1kk，转②。2)校正公式(1)对称秩1算法(SR1法)校正公式取为TkkkkkuuHH1其中ku是n维待定非零向量，k是待定常数，由于校正公式必须满足拟牛顿条件，于是有：kkkkTkkyHsuu。取kkkkyHsu，于是)(11kkkTkkTkkyHsyuy校正公式为：)())((1kkkTkTkkkkkkkkyHsyyHsyHsHH对称秩1算法的性质：性质1:设将SR1法施用于具有对称正定矩阵Q的二次函数，如果①初始矩阵0H是对称的。②迭代点是互异的。③当0k时，0)(kkkTkyHsy那么有：(Ⅰ)此算法所生成的搜索方向110,...,,kppp是互相Q共轭的。(Ⅱ)对kj,...1,0，jjkpQpH1性质2:若性质1的条件都满足，并且经过n次迭代才求到极小点，则1QHn。(2)DFP算法考虑如下形式的校正公式TkkkTkkkkkvvuuHH1由于校正公式必须满足拟牛顿条件，于是有：kkkkTkkkTkkkyHsyvvuu)(取kkTkkksyuu，kkkTkkkyHyvv再令kksu，kkkyHv于是有：kTkkys1，kkTkkyHy1校正公式为：kkTkkTkkkkTkTkkkkyHyHyyHysssHH1DFP算法性质：性质1:设将DFP法施用于具有对称正定矩阵Q的二次函数，如果①初始矩阵0H是对称的。②迭代点是互异的。那么有：(Ⅰ)此算法所生成的搜索方向110,...,,kppp是互相Q共轭的。(Ⅱ)对kj,...1,0，jjkpQpH1性质2:若性质1的条件都满足，并且经过n次迭代才求到极小点，则1QHn。性质3:在DFP算法中，若初始矩阵是对称正定的，则kH中每一个都是正定的。