优化算法及应用报告 （一）用Newton 法求函数最优解1.1课本P117页例4.3.2t0min （t ） = arctan xdx ϕ⎰1.2方法步骤Step1：给定初始点 1t ，k ε>0,=1Step2：对函数求一次导数得到df1，若|1|df <ε ，则迭代停止，输出k t 否则，二次求导dff2=0时，停止，解题失败。

当dff2不等于0时，转下一步。

Step3:计算1(1/2)k k t t df dff +=- ，如果1||k k t t +-<ε ，停止迭代，输出1k t +，否则，k=k+1，转step21.3计算结果：Df1= atan(x)（matlab 中arctan （x ）用atan （x ）表示） Dff2= 1/(x^2 + 1) （1）t1=1时接近最优解*t =0. （2）t1=2时1.4程序，见附件test1，newtonTest1 函数带入clcclear allsyms x tf1=int(atan(x),x,0,t);beex=newton(f1,t,1,0.5);newton 牛顿方法的函数function[besx]=newton(f1,t,t1,c) %step1syms tdf1=diff(f1,t);%函数一次求导dff2=diff(f1,t,2);%函数二次求导while(true)if(abs(subs(df1,t1))<c)%step2，满足条件，迭代停止.disp(t1);break%dff2等于0失败，否则转step3elsetk=t1-(subs(df1,t1))/(subs(dff2,t1))%step3if(abs(tk-t1)<c)besx=tk;%满足绝对值内tk-t1小于c，停止迭代，输出tk disp(besx);breakelset1=tk%条件不成立，k=k+1，转step2，t1=tk，构造循环endendendend1.5程序结果截图（二）用最速下降法求解（UMP ）2.1课本P124页例4.4.2221212min (,)25f x x x x =+ 取初始点0(2,2)T x = ，终止误差610-ε= 2.2方法步骤Step1：给定初始点0x ，终止误差ε >0,令k=0；Step2：用ccc1作为函数对x1的偏导，ccc2作为函数对x2的偏导，ccc3作为()kf x ∇ ，计算可得ccc3，若||3||ccc <ε，则停止迭代，输出k x 否则，转step3Step3:取pk=-ccc3Step4：利用第一问的牛顿法求最优解tk。

同时，令x0：x0=x0+tk*pk;k=k+1，转step22.3计算结果：用牛顿法解得t0约为0.0200（结果见2.5附图）而10001.919878 0.003070x x t p ⎛⎫=+= ⎪-⎝⎭2.4程序，见附件test2，newton2，，funump Test2 题目函数带入clcclear allsyms x1x2tdfdx1=diff((x1)^2+25*(x2)^2,x1);dfdx2=diff((x1)^2+25*(x2)^2,x2);funump([2;2],10^(-6),0,dfdx1,dfdx2,10)newton 牛顿方法的函数（作为引用）%同第一问，不再注释function[beex]=newton2(f1,t,t1,c)syms tdf1=diff(f1,t);ddf1=diff(f1,t,2);t1=0;while(true)if(abs(subs(df1,t1))<c)beex=t1;disp(beex);breakelsetk=t1-(subs(df1,t1))/(subs(ddf1,t1));if(abs(tk-t1)<c)beex=tkdisp(beex);breakelset1=tk;endendendendfunump 最速下降法的函数（ump）function[bex]=funump(x0,c,k,dfdx1,dfdx2,m)syms x1x2tdf=[dfdx1;dfdx2];while(k>=0)x10=x0(1,1);%step1：给定初始点x20=x0(2,1);ccc1=subs(dfdx1,'x1',x10);%step2：用ccc1作为函数对x1的偏导ccc1=subs(ccc1,'x2',x20);ccc2=subs(dfdx2,'x2',x20);%ccc2作为函数对x2的偏导ccc2=subs(ccc2,'x1',x10);ccc3=[ccc1;ccc2];%计算可求得ccc3if(norm(ccc3)<c)%若ccc3的绝对值小于cbex=x0;breakelsepk=-ccc3;%Step3:取pk=-ccc3x1=x10+t*pk(1,1);x2=x20+t*pk(2,1);f1=(x10+t*pk(1,1))^2+25*(x20+t*pk(2,1))^2;beex=newton2(f1,t,0,c); %step4：引用第一问的牛顿算法方程 x0=x0+beex*pk;%x0=x0+tk*pk;k=k+1;%k=k+1，进行循环转入step2if(k>m)bex=x0;breakendendend2.5程序结果截图牛顿法解出t0X1（三）惩罚函数法——罚函数法3.1课本P146页例4.5.32min x 且s.t 10x -<= ，取,1,2k c k k == ……3.2 定义&定理罚函数法定义：它将有约束最优化问题转化为求解无约束最优化问题，其中M 为足够大的正数，起"惩罚"作用， 称之为罚因子，F(x, M )称为罚函数。

定理：对于某个确定的正数M, 若罚函数F(x, M )的最优解x* 满足有约束最优化问题的约束条件，则x* 是该问题的最优解。

序列无约束最小化方法罚函数法在理论上是可行的，在实际计算中的缺点是罚因子M 的取值难于把握，太小起不到惩罚作用；太大则由于误差的影响会导致错误。

3.3方法步骤Step1：给定初始点0x ，罚参函数的数列{k c }（k=1,2……）给出检验终止条件的误差ε >0,令k=1；Step2：按（4.5.30）算出罚函数pck ，按（4.5.29）构造MP 的增光目标函数，即满足()()()ck ck F x f x p x =+Step3:选用某种无约束最优化方法（这里用第二问的最速下降法），以1k x- 为初始点，求解min ()ck F x设得到了最优解kx ，若得到了kx 已满足某种终止条件，则停止迭代，输出kx ， 否则k=k+1，转入step23.4计算结果：目标函数最终为22(1),1时xk x x +-< 或 2,1时x x >，求得/(1)k x k k =+ ，k=1,2，…… K 无限增大时，其结果趋向13.5程序，见附件test3，funump3，chengfa Test3题目函数带入clc clear all syms x f=x^2; g1=1-x;bba = chengfa(0,1,f,g1)funump3 最速下降法的函数（作为引用）%同第二问，不再注释，与第二问区别，此处为一元function[bex]=funump3(x0,c,k,dfdx1,m)syms x1tdf=dfdx1;while(k>=0)x10=x0;ccc1=subs(dfdx1,x10);ccc3=ccc1;if(abs(ccc3)<c)bex=x0;breakelsepk=-ccc3;x1=x10+t*pk;f1=subs(dfdx1,x10+t*pk);beex=newton2(f1,t,0,c);%引用第一问的牛顿算法方程 x0=x0+beex*pk;k=k+1;if(k>m)bex=x0;breakendendendendchengfa惩罚函数法——罚函数法function[bba]=chengfa(x0,k,f,g1)syms x%step1，设置初始点，在函数中输入ck=k;%罚函数的数列while(true)ck=k;if(subs(g1,x0(1,1))>0)%step2，构造罚函数和目标函数 pck=ck*(1-x);%x<1时Fck=f+pck;elsepck=0;%x>1时Fck=f+pck;endx0=funump3(x0,10^(-2),k,Fck,20);%调运最速下降法的函数（见问题二） k=k+1;%k=k+1，进入循环，转入step2if(k>50)x0;break%设置终止条件，假设满足此条件终止endend2.5程序结果截图随终止条件改变而改变，部分截图：。