一、优化算法及其应用 1.简介共轭梯度法（Conjugate Gradient ）是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse 矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。

在各种优化算法中，共轭梯度法是非常重要的一种。

其优点是所需存储量小，具有步收敛性，稳定性高，而且不需要任何外来参数。

2.算法原理共轭梯度法是利用目标函数梯度逐步产生共轭方向作为线搜索方向的方法，每次搜索方向都是在目标函数梯度的共轭方向，搜索步长通过一维极值算法确定。

设二次函数为1()2T T f X C b X X AX =++，其中C 为常数，,b X 为n 维列向量，A 为对称正定矩阵，用共轭梯度法求()f X 的极小点：共轭梯度法探索的第一步是沿负梯度方向。

即()k X 点按()()()k k S f X =-∇方向找到(1)k X +，然后沿着与上一次探索方向()k S 相共轭的方向(1)k S +进行探索直达到最小点*X 。

令()(1)(1)()k k k k S f X S β++=-∇+。

上式的意义就是以原来的负梯度()()()k k f X S -∇=的一部分即()k k S β，加上新的负梯度()(1)k f X +-∇，构造(1)k S +。

在上式中k β的选择，应使n 维欧氏空间n E 中的两个非零向量()k S 与(1)k S +关于矩阵A 共轭。

即(1)()(0,1,2,...1)Tk k SAS k n +⎡⎤==-⎣⎦因1()2T Tf X C b X X AX =++，故有()f X b AX ∇=+ 若令()()()()k k k g f X b AX =∇=+ ()(1)(1)(1)k k k g f X b AX +++=∇=+二式相减，得(1)()(1)()()k k k k g g A X X ++-=-设在第1k +次迭代中(1)()()()k k k k X X S α+=+代入上式，得(1)()()(),(0,1,2,...1)k k k k g g A S k n α+-==-式中()k α为第1k +次迭代的最优步长。

由式(1)()0(0,1,2,...1)Tk k S AS k n +⎡⎤==-⎣⎦和式(1)()()(),(0,1,2,...1)k k k k g g A S k n α+-==-，得(1)(1)()()0Tk k k S gg ++⎡⎤-=⎣⎦ 将式()(1)(1)()k k k k S f X S β++=-∇+和式()(1)(1)(1)k k k g f X b AX +++=∇=+代入上式，得(1)()(1)()[]()0k k k T k k g S g g β++--=因为(1)()(0),,...,k k g g g +是一正交系，故有(1)()[]0k T k g g +=或(1)()[]0k T k g S +=故上式可简化为(1)(1)()()()[][]0k T k k k T k g g g g β++-=得()()22(1)(1)(1)(1)()22()()()()[][]k k k Tk k k T k k k f X g g gg g g f Xβ++++∇===∇()k α用一维探索最优化方法确定，即求()()()()()min ()()k k k k k af X S f X S αα+=+或用解析法，使()()()()0k k k df X S d αα+=求得()k α。

或由式(1)()()(),(0,1,2,...1)k k k k g g A S k n α+-==-，得(1)()()()k k k k g g A S α+=+即()()(1)()()()k k k k f X f X AS α+∇=∇+又由于进行一维最优化搜索，故有()(1)()0Tk k f X S +⎡⎤∇=⎣⎦由上两式可求得()()()()()()Tk k k T k k f X S S ASα⎡⎤∇⎣⎦=-⎡⎤⎣⎦ 如此，即可得到共轭梯度法的一组计算公式为(1)()()()k k k k X X S α+=+()()()()()()()()()()()()()TTk k k k k T T k k k k k f X S f X S S AS S H X Sα⎡⎤⎡⎤∇∇⎣⎦⎣⎦=-=-⎡⎤⎡⎤⎡⎤⎣⎦⎣⎦⎣⎦()(1)(1)()k k k k S f X S β++=-∇+()()22(1)(1)(1)(1)()22()()()()[][]k k k Tk k k T k k k f X g g gg g g f Xβ++++∇===∇3.算法步骤用共轭梯度法求无约束多维极值问题min (),n f x x R ∈的算法步骤如下： （1） 给定初始点(0)x ，及精度0ε>；（2） 若(0)()f x ε∇≤，停止，极小值点为(0)x ，否则转步骤（3）； （3） 取(0)(0)()p f x =-∇，且置0k =；（4） 用一维搜索法求k t ，使得()()()()()0()min k k k k k t f x t p fx tp ≥+=+，令，(1)()()k k k k x x t p +=+，转步骤5；（5） 若(1)()k f x ε+∇≤，停止，极小值点为(1)k x +，否则转步骤（6）； （6） 若1k n +=，令(0)()n x x =，转步骤（3），否则转步骤（7）；（7） 令(1)(1)()()k k k k p f x p λ++=-∇+，2(1)2()()()k k k f xf x λ+∇=∇，置1k k =+，转步骤（4）。

4.算法的MATLAB 实现在MATLAB 中编程实现的共轭梯度法函数为：min GETD功能：用共轭梯度法求解多维函数的极值。

调用格式：[,min ]min (,0,var,)x f GETD f x eps = 其中，f ：目标函数；0x ：初始点； v a r ：自变量向量；x ：目标函数取最小值时的自变量值； m i n f ：目标函数的最小值。

共轭梯度法的MATLAB 程序代码如下： function [x,minf]=minGETD(f,x0,var,eps) %目标函数:f; %初始点:x0;%自变量向量:var;%目标函数取最小值时的自变量值:x; %目标函数的最小值:minf; format long; if nargin==3 eps=1.0e-6; endx0=transpose(x0); n=length(var); syms l;gradf=jacobian(f,var); %梯度方向 v0=Funval(gradf,var,x0); p=-transpose(v0); k=0; while 1v=Funval(gradf,var,x0); tol=norm(v); if tol<=eps x=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);if tol<=epsx=x1;break;endif k+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);format short;4.例题例1.f=(x-2)^2+(y-4)^2M文件：function f=conjugate_grad_2d(x0,t)x=x0;syms xi yi af=(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))>ts=-fi;if count<=0s=-fi;elses=s1; endx=x+a*s;f=subs(f,{xi,yi},x); f1=diff(f); f1=solve(f1); if f1~=0ai=double(f1); elsebreakx,f=subs(f,{xi,yi},x),count endx=subs(x,a,ai);f=xi-xi^2+2*xi*yi+yi^2; fxi=diff(f,xi); fyi=diff(f,yi);fxi=subs(fxi,{xi,yi},x); fyi=subs(fyi,{xi,yi},x); fii=[fxi,fyi];d=(fxi^2+fyi^2)/(fx^2+fy^2); s1=-fii+d*s; count=count+1; fx=fxi; fy=fyi; endx,f=subs(f,{xi,yi},x),count 输入：conjugate_grad_2d([0,0],0.0001) 结果：x = 0.24998825499785 -0.24999998741273 f = 0.12499999986176 count = 10ans = 0.12499999986176例2．试用共轭梯度法求解目标函数22121212()10460f X x x x x x x =+---+的极小值。

设初始点[](0)(0)(0)12[]00TTX x x ==。

解：原函数的梯度为[]122112()()()[]21024TT f X f X f X x x x x x x ∂∂∇==----∂∂ [](0)()104Tf X ∇=--第一次探索的方向：[](0)(0)104TS g =-=--1222212222221()()21()()12()()f X f X x x x f X H X f X f X x x x ⎡⎤∂∂⎢⎥∂∂∂-⎡⎤⎢⎥∇===⎢⎥⎢⎥-∂∂⎣⎦⎢⎥∂∂∂⎢⎥⎣⎦由式()()()()()()()()()()()()()TTk k k k k T T k k k k k f X Sf X S S AS S H X Sα⎡⎤⎡⎤∇∇⎣⎦⎣⎦=-=-⎡⎤⎡⎤⎡⎤⎣⎦⎣⎦⎣⎦，得()()()[][](0)(0)(0)(0)(0)(0)(0)(0)(0)(0)1010441160.7631578942110152104124TTT T f X S f X S S AS S H X Sα⎡⎤⎡⎤∇∇⎣⎦⎣⎦=-=-⎡⎤⎡⎤⎡⎤⎣⎦⎣⎦⎣⎦⎡⎤--⎢⎥⎣⎦=-==-⎡⎤⎡⎤⎢⎥⎢⎥-⎣⎦⎣⎦由此得[](1)(0)(0)(0)0100.7631578947.63157894 3.05263157604TX X S α⎡⎤⎡⎤=+=+=⎢⎥⎢⎥⎣⎦⎣⎦求(1)X 点处的梯度为[](1) 2.21052630 5.52631579Tg =-由式()()22(1)(1)(1)(1)()22()()()()[][]k k k Tk k k T k k k f Xg g gg g g f X β++++∇===∇求(0)β：2(1)(0)2(0)35.426592780.305401661116g g β===第二次探索的方向：[](1)(1)(0)(0)0.8434903 6.74792243TS g S β=-+=由式()()()()()()()()()()()()()T Tk k k k k T T k k k k k f X S f X S S AS S H X Sα⎡⎤⎡⎤∇∇⎣⎦⎣⎦=-=-⎡⎤⎡⎤⎡⎤⎣⎦⎣⎦⎣⎦求探索步长为： [][](1)0.84349032.21052630 5.52631579 6.74792243210.84349030.8434903 6.7479224312 6.7479224335.426592830.43678160981.10825193a ⎡⎤--⎢⎥⎣⎦=-⎡⎤⎡⎤⎢⎥⎢⎥-⎣⎦⎣⎦== 由此得[](2)1(2)(2)(1)(1)(2)27.9999999 5.9999999Tx X X a S x ⎡⎤=+==⎢⎥⎢⎥⎣⎦[](2)0.00000020.0000002Tg =--2(2)g < 210ε-=则，极小值点为[](2)1(2)27.9999999 5.9999999Tx x ⎡⎤=⎢⎥⎢⎥⎣⎦ 二、遗传算法及其应用 1.简介遗传算法（Genetic Algorithm ）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan 大学J.Holland 教授于1975年首先提出来的，并出版了颇有影响的专著《Adaptation in Natural and Artificial Systems 》，GA 这个名称才逐渐为人所知，J.Holland 教授所提出的GA 通常为简单遗传算法（SGA ）。