共轭梯度法

共轭梯度法对于任意形式的目标函数()fX，在极值点*X附近展开成泰勒级数，且取前三项，有****2**1()...2TTfXfXfXXXXXfXXX因在极值点*X处*0fX，而2**()fXHX为()fX在*X的二阶偏导数矩阵，即Hessian矩阵，故****1().().2TfXfXXXHXXX对于二次函数来说，若令2*2*2*221122,,fXfXfXabcxxxx则**1(),abHXfXdbc而—常数则，得到11221212121122*1**112*2**12**112**1222****11122-1()+--2---1=+--2--1-2---2xxabfXdxxxxbcxxaxxbxxdxxxxbxxcxxdaxxbxxxxcxx由上式可知，当12*1**2xxXXxx时，得到目标函数的极小值*1()fXfXd，当22(),,...fXdd时，则有等值线族。令2()fXd，代入上式，则有112222****2111221()-2---2fXddaxxbxxxxcxx所以目标函数()fX在*X点附近的等值线方程为112222****1122-2---0axxbxxxxcxxd式中，122()ddd常数。由极小值点存在的充分必要条件为二阶导数行列式小于零，即20bac在解析几何中已经证明，当20bac时为椭圆，所以二元函数的等值线在极值点附近是近似的同心椭圆族。1.算法原理共轭梯度法是利用目标函数梯度逐步产生共轭方向作为线搜索方向的方法，每次搜索方向都是在目标函数梯度的共轭方向，搜索步长通过一维极值算法确定。设二次函数为1()2TTfXCbXXAX，其中C为常数，,bX为n维列向量，A为对称正定矩阵，用共轭梯度法求()fX的极小点：共轭梯度法探索的第一步是沿负梯度方向。即()kX点按()()kkSfX方向找到(1)kX，然后沿着与上一次探索方向()kS相共轭的方向(1)kS进行探索直达到最小点*X。令(1)(1)()kkkkSfXS。上式的意义就是以原来的负梯度()()kkfXS的一部分即()kkS，加上新的负梯度(1)kfX，构造(1)kS。在上式中k的选择，应使n维欧氏空间nE中的两个非零向量()kS与(1)kS关于矩阵A共轭。即(1)()0(0,1,2,...1)TkkSASkn因1()2TTfXCbXXAX，故有()fXbAX若令()()()kkkgfXbAX(1)(1)(1)kkkgfXbAX二式相减，得(1)()(1)()()kkkkggAXX设在第1k次迭代中(1)()()()kkkkXXS代入上式，得(1)()()(),(0,1,2,...1)kkkkggASkn式中()k为第1k次迭代的最优步长。由式(1)()0(0,1,2,...1)TkkSASkn和式(1)()()(),(0,1,2,...1)kkkkggASkn，得(1)(1)()()0TkkkSgg将式(1)(1)()kkkkSfXS和式(1)(1)(1)kkkgfXbAX代入上式，得(1)()(1)()[]()0kkkTkkgSgg因为(1)()(0),,...,kkggg是一正交系，故有(1)()[]0kTkgg或(1)()[]0kTkgS故上式可简化为(1)(1)()()()[][]0kTkkkTkgggg得22(1)(1)(1)(1)()22()()()()[][]kkkTkkkTkkkfXggggggfX()k用一维探索最优化方法确定，即求()()()()()min()()kkkkkafXSfXS或用解析法，使()()()()0kkkdfXSd求得()k。或由式(1)()()(),(0,1,2,...1)kkkkggASkn，得(1)()()()kkkkggAS即(1)()()()kkkkfXfXAS又由于进行一维最优化搜索，故有(1)()0TkkfXS由上两式可求得()()()()()TkkkTkkfXSSAS如此，即可得到共轭梯度法的一组计算公式为(1)()()()kkkkXXS()()()()()()()()()()TTkkkkkTTkkkkkfXSfXSSASSHXS(1)(1)()kkkkSfXS22(1)(1)(1)(1)()22()()()()[][]kkkTkkkTkkkfXggggggfX2.算法步骤用共轭梯度法求无约束多维极值问题min(),nfxxR的算法步骤如下：（1）给定初始点(0)x，及精度0；（2）若(0)()fx，停止，极小值点为(0)x，否则转步骤（3）；（3）取(0)(0)()pfx，且置0k；（4）用一维搜索法求kt，使得()()()()0()minkkkkktfxtpfxtp，令，(1)()()kkkkxxtp，转步骤5；（5）若(1)()kfx，停止，极小值点为(1)kx，否则转步骤（6）；（6）若1kn，令(0)()nxx，转步骤（3），否则转步骤（7）；（7）令(1)(1)()()kkkkpfxp，2(1)2()()()kkkfxfx，置1kk，转步骤（4）。3.算法的MATLAB实现在MATLAB中编程实现的共轭梯度法函数为：minGETD功能：用共轭梯度法求解多维函数的极值。调用格式：[,min]min(,0,var,)xfGETDfxeps其中，f：目标函数；0x：初始点；var：自变量向量；x：目标函数取最小值时的自变量值；minf：目标函数的最小值。共轭梯度法的MATLAB程序代码如下：function[x,minf]=minGETD(f,x0,var,eps)%目标函数:f;%初始点:x0;%自变量向量:var;%目标函数取最小值时的自变量值:x;%目标函数的最小值:minf;formatlong;ifnargin==3eps=1.0e-6;endx0=transpose(x0);n=length(var);symsl;gradf=jacobian(f,var);%梯度方向v0=Funval(gradf,var,x0);p=-transpose(v0);k=0;while1v=Funval(gradf,var,x0);tol=norm(v);iftol=epsx=x0;break;endy=x0+l*p;yf=Funval(f,var,y);[a,b]=minJT(yf,0,0.1);xm=minHJ(yf,a,b);x1=x0+xm*p;vk=Funval(gradf,var,x1);tol=norm(vk);iftol=epsx=x1;break;endifk+1==nx0=x1;continue;elselamda=dot(vk,vk)/dot(v,v);p=-transpose(vk)+lamda*p;%共轭方向k=k+1;x0=x1;endendminf=Funval(f,var,x);formatshort;例：用共轭梯度法求函数22(,)(3)ftsts的极小值，其中初始值取0(2,6)x。解：在MATLAB命令窗口中输入：symsts;f=(t-3)^2+s^2;[x,mf]=minGETD(f,[-26],[ts])所得结果为：x=3.00000.0000mf=2.0116e-037例：试用共轭梯度法求解目标函数22121212()10460fXxxxxxx的极小值。设初始点(0)(0)(0)12[]00TTXxx。解：原函数的梯度为122112()()()[]21024TTfXfXfXxxxxxx(0)()104TfX第一次探索的方向：(0)(0)104TSg1222212222221()()21()()12()()fXfXxxxfXHXfXfXxxx由式()()()()()()()()()()TTkkkkkTTkkkkkfXSfXSSASSHXS，得(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)1010441160.7631578942110152104124TTTTfXSfXSSASSHXS由此得(1)(0)(0)(0)0100.7631578947.631578943.05263157604TXXS求(1)X点处的梯度为(1)2.210526305.52631579Tg由式22(1)(1)(1)(1)()22()()()()[][]kkkTkkkTkkkfXggggggfX求(0)：2(1)(0)2(0)35.426592780.305401661116gg第二次探索的方向：(1)(1)(0)(0)0.84349036.74792243TSgS由式()()()()()()()()()()TTkkkkkTTkkkkkfXSfXSSASSHXS求探索步长为：(1)0.84349032.210526305.526315796.74792243210.84349030.84349036.74792243126.7479224335.426592830.43678160981.10825193a由此得(2)1(2)(2)(1)(1)(2)27.99999995.9999999TxXXaSx(2)0.00000020.0000002Tg2(2)g210则，极小值点为(2)1(2)27.99999995.9999999Txx