一、优化算法及其应用 1.简介
共轭梯度法（Conjugate Gradient）是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。 在各种优化算法中，共轭梯度法是非常重要的一种。其优点是所需存储量小，具有步收敛性，稳定性高，而且不需要任何外来参数。
2.算法原理
共轭梯度法是利用目标函数梯度逐步产生共轭方向作为线搜索方向的方法，每次搜索方向都是在目标函数梯度的共轭方向，搜索步长通过一维极值算法确定。
1设二次函数为f(X)?C?bTX?XTAX，其中C为常数，b,X为n维列向
2量，A为对称正定矩阵，用共轭梯度法求f(X)的极小点：
共轭梯度法探索的第一步是沿负梯度方向。即X(k)点按S(k)???f?X(k)?方向找到X(k?1)，然后沿着与上一次探索方向S(k)相共轭的方向S(k?1)进行探索直达到最小点X*。
令S(k?1)???f?X(k?1)???kS(k)。
上式的意义就是以原来的负梯度??f?X(k)??S(k)的一部分即?kS(k)，加上新的负梯度??f?X(k?1)?，构造S(k?1)。
在上式中?k的选择，应使n维欧氏空间En中的两个非零向量S(k)与S(k?1)关于矩阵A共轭。即
??S(k?1)T(k)??AS?0(k?0,1,2,...n?1)
因
f(X)?C?bTX?1TXAX，故有?f(X)?b?AX 2若令
g(k)??f?X(k)??b?AX(k) g(k?1)??f?X(k?1)??b?AX(k?1)
1
二式相减，得
g(k?1)?g(k)?A(X(k?1)?X(k))
设在第k?1次迭代中
X(k?1)?X(k)??(k)S(k)
代入上式，得
g(k?1)?g(k)?A?(k)S(k),(k?0,1,2,...n?1)
式中?(k)为第k?1次迭代的最优步长。
(k?1)(k)?SAS?0由式???T(k?0,1,2,...n?1)和式
g(k?1)?g(k)?A?(k)S(k),(k?0,1,2,...n?1)，得
(k?1)(k?1)???g(k))?0 ?S?(gT将式S(k?1)???f?X(k?1)???kS(k)和式g(k?1)??f?X(k?1)??b?AX(k?1)代入上式，得
[g(k?1)??kS(k)]T(g(k?1)?g(k))?0
因为g(k?1),g(k),...,g(0)是一正交系，故有[g(k?1)]Tg(k)?0或[g(k?1)]TS(k)?0
故上式可简化为
[g(k?1)]Tg(k?1)??(k)[g(k)]Tg(k)?0
得
?(k)?g[g]g?[g(k)]Tg(k)g(k)(k?1)T(k?1)(k?1)22??f?X(k?1)??f?X(k)22?
?(k)用一维探索最优化方法确定，即求
minf(X(k)??S(k))?f(X(k)??(k)S(k))
a或用解析法，使
df(X(k)??(k)S(k))?0
d?求得?(k)。
或由式g(k?1)?g(k)?A?(k)S(k),(k?0,1,2,...n?1)，得
g(k?1)?g(k)?A?(k)S(k)
2
即
?f?X(k?1)???f?X(k)???(k)AS(k)
又由于进行一维最优化搜索，故有
??f?X(k?1)??S(k)?0 ??由上两式可求得
??f?X(k)??S(k)? ???(k)T(k)??S??ASTT?(k)如此，即可得到共轭梯度法的一组计算公式为
X(k?1)?X(k)??(k)S(k)
?(k)??f?X??S????(k)T(k)??SAS??(k)T(k)??f?X??S(k)????T
(k)(k)(k)????S???H?X??S(k)TS(k?1)???f?X(k?1)???kS(k)
?(k)?g[g]g?[g(k)]Tg(k)g(k)(k?1)T(k?1)(k?1)22??f?X(k?1)??f?X(k)22?
3.算法步骤
用共轭梯度法求无约束多维极值问题minf(x),x?Rn的算法步骤如下： （1） 给定初始点x(0)，及精度??0；
（2） 若?f(x(0))??，停止，极小值点为x(0)，否则转步骤（3）； （3） 取p(0)???f(x(0))，且置k?0；
(k)（4） 用一维搜索法求tk，使得f(x(k)?t?x(k)?tpk(?)，令，kp)?minft?0k)k()x(k?1)?x(?tkp，转步骤5；
（5） 若?f(x(k?1))??，停止，极小值点为x(k?1)，否则转步骤（6）； （6） 若k?1?n，令x(0)?x(n)，转步骤（3），否则转步骤（7）；
3
（7） 令p(k?1)???f(x(k?1))??kp(k)，?k?（4）。
?f(x(k?1)(k))22，置k?k?1，转步骤
?f(x)4.算法的MATLAB实现
在MATLAB中编程实现的共轭梯度法函数为：minGETD
功能：用共轭梯度法求解多维函数的极值。 调用格式：[x,minf]?minGETD(f,x0,var,eps) 其中，f：目标函数；
x0：初始点； var：自变量向量；
x：目标函数取最小值时的自变量值； minf：目标函数的最小值。 共轭梯度法的MATLAB程序代码如下： function [x,minf]=minGETD(f,x0,var,eps) %目标函数:f; %初始点:x0;
%自变量向量:var;
%目标函数取最小值时的自变量值:x; %目标函数的最小值:minf; format long; if nargin==3 eps=1.0e-6; end
x0=transpose(x0); n=length(var); syms l;
gradf=jacobian(f,var); %梯度方向 v0=Funval(gradf,var,x0); p=-transpose(v0); k=0; while 1
v=Funval(gradf,var,x0); tol=norm(v); if tol<=eps x=x0; break; end
y=x0+l*p;
4
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); if tol<=eps x=x1; break; end
if k+1==n x0=x1; continue; else
lamda=dot(vk,vk)/dot(v,v);
p=-transpose(vk)+lamda*p; %共轭方向 k=k+1; x0=x1; end end
minf=Funval(f,var,x); format short;
4.例题
例1.f=(x-2)^2+(y-4)^2
M文件：
function f=conjugate_grad_2d(x0,t) x=x0;
syms xi yi a
f=(xi-2)^2+(yi-4)^2; fx=diff(f,xi); fy=diff(f,yi);
fx=subs(fx,{xi,yi},x0); fy=subs(fy,{xi,yi},x0); fi=[fx,fy]; count=0;
while double(sqrt(fx^2+fy^2))>t s=-fi;
if count<=0 s=-fi; else
5