最优化方法实验报告Numerical Linear Algebra And ItsApplications学生所在学院：理学院学生所在班级：计算数学10-1学生姓名：甘纯指导教师：单锐教务处2013年5月实验三实验名称：无约束最优化方法的MATLAB实现实验时间: 2013年05月10日星期三实验成绩：一、实验目的：通过本次实验的学习，进一步熟悉掌握使用MATLAB软件，并能利用该软件进行无约束最优化方法的计算。
二、实验背景：（一）最速下降法1、算法原理最速下降法的搜索方向是目标函数的负梯度方向，最速下降法从目标函数的负梯度方向一直前进，直到到达目标函数的最低点。
2、算法步骤用最速下降法求无约束问题n R()min的算法步骤如下：xxf，a ）给定初始点)0(x ，精度0>ε，并令k=0；b ）计算搜索方向)()()(k k x f v -∇=，其中)()(k x f ∇表示函数)(x f 在点)(k x 处的梯度；c ）若ε≤)(k v ，则停止计算；否则，从)(k x 出发，沿)(k v 进行一维搜索，即求k λ，使得)(min )()()(0)()(k k k k v x f v x f λλλ+=+≥； d ）令1,)()()1(+=+=+k k v x x k k k k λ，转b ）。
（二）牛顿法1、算法原理牛顿法是基于多元函数的泰勒展开而来的，它将)()]([-)(1)(2k k x f x f ∇∇-作为搜索方向，因此它的迭代公式可直接写出来：)()]([)(1)(2)()(k k k k x f x f x x ∇∇-=-2、算法步骤用牛顿法求无约束问题n R x x f ∈),(min 的算法步骤如下：a ）给定初始点)0(x ,精度0>ε，并令k=0；b ）若ε≤∇)()(k x f ，停止，极小点为)(k x ，否则转c ）；c ）计算)()]([,)]([)(1)(2)(1)(2k k k k x f x f p x f ∇∇-=∇--令；d ）令1,)()()1(+=+=+k k p x x k k k ，转b ）。
（三）共轭梯度法1、算法原理共轭梯度法是利用目标函数梯度逐步产生共轭方向作为线搜索方向的方法，每次搜索方向都是在目标函数梯度的共轭方向，搜索步长通过一维极值算法确定。
2、算法步骤a ）给定初始点)0(x ,精度0>ε；b ）若ε≤∇)()0(x f ，停止，极小点为)0(x ，否则转c ）；c ）0()0()0(=-∇=k x f p ），且置取；d ）用一维搜索方法求k t ，使得)(min )()()(0)()(k k t k k k tp x f p t x f +=+≥ 令)()()1(k k k k p t x x +=+，转e ）；e ）若ε≤∇+)()1(k xf ，停止，极小值为)1(+k x ，否则转f ）；f ）若,,1)()0(n x x n k ==+令转c ），否则转g ）； g ）令2)(2)1()1()1(()()(k k k k k x f x f x f p ∇∇=+-∇=+++λ，三、实验内容：1．最速下降法的MATLAB 实现2．牛顿法的MATLAB 实现3．共轭梯度法的MATLAB实现四、实验过程：1．最速下降法的函数：function [x,minf] = minFD(f,x0,var,eps)%最速下降法主函数if nargin == 3eps = 1.0e-6;endsyms l;tol = 1;gradf = - jacobian(f,var);while tol>epsv = Funval(gradf,var,x0);tol = norm(v);y = x0 + l*v;yf = Funval(f,var,y);[a,b] = minJT(yf,0,0.1);%进退法求区间xm = minHJ(yf,a,b);%黄金分割法x1 = x0 + xm*v;x0 = x1;endx = x1;minf = Funval(f,var,x);%进退法函数function [minx,maxx] = minJT(f,x0,h0,eps) if nargin == 3eps = 1.0e-6;endx1 = x0;k = 0;h = h0;while 1x4 = x1 + h;f4 = subs(f, findsym(f),x4); f1 = subs(f, findsym(f),x1); if f4 < f1x2 = x1;x1 = x4;f2 = f1;f1 = f4;h = 2*h;elseif k==1h = -h;x2 = x4;f2 = f4;elsex3 = x2;x2 = x1;x1 = x4;break;endendminx = min(x1,x3);maxx = x1+x3 - minx;%黄金分割法函数function [x,minf] = minHJ(f,a,b,eps) if nargin == 3eps = 1.0e-6;endl = a + 0.382*(b-a);u = a + 0.618*(b-a);k=1;tol = b-a;while tol>eps && k<100000fl = subs(f , findsym(f), l);fu = subs(f , findsym(f), u);if fl > fua = l;l = u;u = a + 0.618*(b - a);elseb = u;u = l;l = a + 0.382*(b-a);endk = k+1;tol = abs(b - a);endif k == 100000disp('找不到最小值！');x = NaN;minf = NaN;return;endx = (a+b)/2;minf = subs(f, findsym(f),x);2．牛顿法的函数：function [x,minf] = minNT(f,x0,var,eps) if nargin == 3eps = 1.0e-6;endtol = 1;x0 = transpose(x0);gradf = jacobian(f,var);jacf = jacobian(gradf,var);while tol>epsv = Funval(gradf,var,x0);tol = norm(v);pv = Funval(jacf,var,x0);p = -inv(pv)*transpose(v);p = double(p);x1 = x0 + p;x0 = x1;endx = x1;minf = Funval(f,var,x);3.共轭梯度法的函数：function [x,minf] = minGETD(f,x0,var,eps) if nargin == 3eps = 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<=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);if tol<=epsbreak;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);%进退法函数function [minx,maxx] = minJT(f,x0,h0,eps) if nargin == 3endx1 = x0;k = 0;h = h0;while 1x4 = x1 + h;k = k+1;f4 = subs(f, findsym(f),x4);f1 = subs(f, findsym(f),x1);if f4 < f1x2 = x1;x1 = x4;f2 = f1;f1 = f4;h = 2*h;elseif k==1x2 = x4;f2 = f4;elsex3 = x2;x2 = x1;x1 = x4;break;endendendminx = min(x1,x3);maxx = x1+x3 - minx;%黄金分割法函数function [x,minf] = minHJ(f,a,b,eps) if nargin == 3endl = a + 0.382*(b-a);u = a + 0.618*(b-a);k=1;tol = b-a;while tol>eps && k<100000fl = subs(f , findsym(f), l);fu = subs(f , findsym(f), u);if fl > fua = l;l = u;u = a + 0.618*(b - a);elseb = u;u = l;l = a + 0.382*(b-a);endk = k+1;tol = abs(b - a);endif k == 100000disp('找不到最小值！');x = NaN;minf = NaN;return;endx = (a+b)/2;minf = subs(f, findsym(f),x);五、实验结果(总结/方案)1、最速下降法：用最速下降法求函数1)2()4(),(22+++-=s t s t f 的极小值，初始点取)3,1(0-=x 。
在command window 中输入：>>syms t s;f=(t-4)^2+(s+2)^2+1;[t,mf]=minFD(f,[1 -3],[t s])输出结果：x= 4.0000 -2.0000mf= 12、牛顿法：用牛顿法求函数1)2()4(),(22+++-=s t s t f 的极小值，其中初始点取为)0,0(0=x 。