最优化方法实验报告

最优化方法实验报告optimizationmethodExperimentReport学生所在学院：理学院学生所在班级：信息1学生姓名：教务处20014年5月最优化方法实验报告书说明:1.下面程序在MATLABR2012a中均能正常运行。程序之间有关联。实验一熟悉MATLAB根本功能〔２学时〕实验的目的和要求：在本次实验中，通过亲临使用MATLAB，对该软件做一全面了解并掌握重点内容。实验内容：全面了解MATLAB系统实验常用工具的具体操作和功能学习建议：本次实验在全面了解软件系统根底之上，学习和熟悉一些MATLAB的根底用途，重点掌握优化工具箱函数选用的内容。重点和难点：优化工具箱函数选用。利用Matlab的优化工具箱，可以求解线性规划、非线性规划和多目标规划问题。具体而言，包括线性、非线性最小化，最大最小化，二次规划，半无限问题，线性、非线性方程〔组〕的求解，线性、非线性的最小二乘问题。另外，该工具箱还提供了线性、非线性最小化，方程求解，曲线拟合，二次规划等问题中大型课题的求解方法，为优化方法在工程中的实际应用提供了更方便快捷的途径。优化工具箱中的函数优化工具箱中的函数包括下面几类：1．最小化函数表1最小化函数表函

数描

述fgoalattain多目标到达问题fminbnd有边界的标量非线性最小化fmincon有约束的非线性最小化fminimax最大最小化fminsearch,fminunc无约束非线性最小化fseminf半无限问题linprog线性课题quadprog二次课题2．方程求解函数表2方程求解函数表函

数描

述/线性方程求解fsolve非线性方程求解fzero标量非线性方程求解3．最小二乘〔曲线拟合〕函数表3最小二乘函数表函

数描

述/线性最小二乘lsqlin有约束线性最小二乘lsqcurvefit非线性曲线拟合lsqnonlin非线性最小二乘lsqnonneg非负线性最小二乘4．实用函数表4实用函数表函

数描

述optimset设置参数optimget

5．大型方法的演示函数表5大型方法的演示函数表函

数描

述circustent马戏团帐篷问题—二次课题molecule用无约束非线性最小化进行分子组成求解optdeblur用有边界线性最小二乘法进行图形处理6．中型方法的演示函数表6中型方法的演示函数表函

数描

述bandemo香蕉函数的最小化dfildemo过滤器设计的有限精度goaldemo目标到达举例optdemo演示过程菜单tutdemo教程演示下面以我们最常用的线性规划模型求解函数linprog作为典型对优化工具箱进行简单的介绍。linprog函数功能：求解线性规划问题。在命令窗口，键入doclinprog,得到下列图〔该图为帮助窗口〕数学模型：其中f,x,b,beq,lb和ub为向量，A和Aeq为矩阵。语法：x=linprog(f,A,b,Aeq,beq)x=linprog(f,A,b,Aeq,beq,lb,ub)x=linprog(f,A,b,Aeq,beq,lb,ub,x0)x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)[x,fval]=linprog(...)[x,fval,exitflag]=linprog(...)[x,fval,exitflag,output]=linprog(...)[x,fval,exitflag,output,lambda]=linprog(...)描述：x=linprog(f,A,b)求解问题minf'*x，约束条件为A*x<=b。x=linprog(f,A,b,Aeq,beq)求解上面的问题，但增加等式约束，即Aeq*x=beq。假设没有不等式存在，那么令A=[]、b=[]。x=linprog(f,A,b,Aeq,beq,lb,ub)定义设计变量x的下界lb和上界ub，使得x始终在该范围内。假设没有等式约束，令Aeq=[]、beq=[]。x=linprog(f,A,b,Aeq,beq,lb,ub,x0)设置初值为x0。该选项只适用于中型问题，缺省时大型算法将忽略初值。x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)用options指定的优化参数进行最小化。[x,fval]=linprog(...)返回解x处的目标函数值fval。[x,lambda,exitflag]=linprog(...)返回exitflag值，描述函数计算的退出条件。[x,lambda,exitflag,output]=linprog(...)返回包含优化信息的输出变量output。[x,fval,exitflag,output,lambda]=linprog(...)将解x处的拉格朗日乘子返回到lambda参数中。变量：lambda参数lambda参数是解x处的拉格朗日乘子。它有以下一些属性：

lambda.lower–lambda的下界。

lambda.upper–lambda的上界。

lambda.ineqlin–lambda的线性不等式。

lambda.eqlin–lambda的线性等式。其它参数意义同前。算法：大型优化算法

大型优化算法采用的是LIPSOL法，该法在进行迭代计算之前首先要进行一系列的预处理。中型优化算法

linprog函数使用的是投影法，就象quadprog函数的算法一样。linprog函数使用的是一种活动集方法，是线性规划中单纯形法的变种。它通过求解另一个线性规划问题来找到初始可行解。诊断：大型优化问题

算法的第一步涉及到一些约束条件的预处理问题。有些问题可能导致linprog函数退出，并显示不可行的信息。在本例中，exitflag参数将被设为负值以表示优化失败。假设Aeq参数中某行的所有元素都为零，但Beq参数中对应的元素不为零，那么显示以下退出信息：Exitingduetoinfeasibility:anallzerorowintheconstraintmatrixdoesnothaveazeroincorrespondingrighthandsizeentry.假设x的某一个元素没在界内，那么给出以下退出信息：

Exitingduetoinfeasibility:objectivef'*xisunboundedbelow.假设Aeq参数的某一行中只有一个非零值，那么x中的相关值称为奇异变量。这里，x中该成分的值可以用Aeq和Beq算得。假设算得的值与另一个约束条件相矛盾，那么给出以下退出信息：Exitingduetoinfeasibility:Singletonvariablesinequalityconstraintsarenotfeasible.假设奇异变量可以求解但其解超出上界或下界，那么给出以下退出信息：Exitingduetoinfeasibility:singletonvariablesintheequalityconstraintsarenotwithinbounds.应用实例这是matlab帮助窗口里给出的一个例子：Findxthatminimizesf(x)=–5x1–4x2–6x3,subjecttox1–x2+x3≤203x1+2x2+4x3≤423x1+2x2≤300≤x1,0≤x2,0≤x3.First,enterthecoefficientsf=[-5;-4;-6];A=[1-11324320];b=[20;42;30];lb=zeros(3,1);Next,callalinearprogrammingroutine.[x,fval,exitflag,output,lambda]=linprog(f,A,b,[],[],lb);ExaminethesolutionandLagrangemultipliers:x,lambda.ineqlin,lambda.lowerx=0.000015.00003.0000ans=0.00001.50000.5000ans=1.00000.00000.0000下面在来用linprog解我们最优化考试的题：Minf(x)=-3x1+x2+x3;S.T.x1–2*x2+x3<=11-4*x1+x2+2*x3–x4=3-2*x1+x3=1X1,x2,x3,x4>=0;在matlabcommandwindow中键入以下指令：f=[-3;1;1];>>A=[1-21;4-1-2];>>b=[11;-3];>>Aeq=[-201];>>beq=1;>>lb=zeros(3,1);>>[x,fval,exitflag]=linprog(f,A,b,Aeq,beq,lb)Optimizationterminated.x=4.00001.00009.0000fval=-2.0000exitflag=1实验二一维搜索方法的MATLAB实现〔２学时〕实验的目的和要求：通过本次实验应使学生掌握如何使用MATLAB软件进行一维搜索，并学会对具体问题进行分析。实验内容：0.618法的MATLAB实现Fibonacci法的MATLAB实现学习建议：本次实验是学生初次使用MATLAB进行优化问题的实验，本次实验就是要通过对一些具体问题的分析学会软件的操作并加深对理论知识的理解。重点和难点：具体问题的步长因子确实定，理解、掌握精度与效率的关系。实验内容：0.618法和Fibonacci法都是分割方法，其根本思想是通过取试探点和进行函数值的比拟，使包含极小点的搜索区间不断缩短，当区间长度缩短到一定程度时，区间上每个点的函数值均接近极小值，从而各点可以看作为极小点的近似。这类方法仅需计算函数值，不涉及导数，又称直接法。他们用途很广，尤其适用于非光滑及导数表达式复杂或写不出的情形。注意，这些方法要求所考虑区间上的目标函数是单峰函数，如果这个条件不满足，我们可以把所考虑的区间分成假设干个小区间，在每个区间上的函数式单峰的。这样，我们在每个小区间上求极小点，然后选取其中的最小点。一0.618法1.0.618法方法原理:0.618法的根本思想是通过取试探点使包含极小点的区间(不确定区间)不断缩短,当区间长度小到一定程度时,区间上各点的函数值均接近极小值,因此任意一点都可作为极小点的近似.0.618法计算试探点的公式:2.0.618法的算法步骤:=1\*GB3①置初始区间及精度要求,计算试探点和,计算函数值和.计算公式是令.=2\*GB3②假设,那么停止计算.否那么,当时,转步骤=3\*GB3③;当时,转步骤=4\*GB3④.=3\*GB3③置,,,,计算函数值,转步骤=5\*GB3⑤.=4\*GB3④置,,,,计算函数值,转步骤=5\*GB3⑤.=5\*GB3⑤置,返回步骤=2\*GB3②.MATLAB实现:3.代码及数值算例:程序源代码:function[X,FMIN,K]=find0618(f,a1,b1,e)%[X,FMIN,K]=find0618(f,a1,b1,e)0.618法一维搜索%f目标函数%a1,b1初始区间%e精度要求%X极小点%FMIN极小值%K迭代次数%2014张超a=a1;b=b1;k=1;r=a+0.328*(b-a);u=a+0.618*(b-a);while1iff(r)>f(u)if(b-r)<=eu;break;elsea=r;b=b;r=u;u=a+0.618*(b-a);endelseif(u-a)<=er;break;elsea=a;b=u;u=r;r=a+0.382*(b-a);endk=k+1;endX=(r+u)/2;FMIN=double(f(X));K=k;end数值算例:Minf(x)=2*x*x–x–1;初始区间,精度e<=0.16.键入命令并输出结果：symsxf(x)=2*x^2-x-1;a1=-1;b1=1;e=0.16;[X,FMIN,K]=find0618(f,a1,b1,e)X=0.2258FMIN=-1.1238K=6二Fibonacci法1.Fibonacci法根本原理和步骤思想：搜索区间长度缩短率采用Fibonacci数123581321345589……MATLAB实现:2.代码及数值算例:程序源代码:function[X,Fmin,K]=fibonacci(f,a0,b0,e)%fibonacci()Fibonacci法求极小值%X极值点%Fmin极小值%K需要用到第K个Fibonacci数%a0,b0初始搜索区间%e精度%张超编写于2014/04/01a=a0;b=b0;F=[11];i=1;whileF(i)<=(b-a)/eF(i+2)=F(i)+F(i+1);i=i+1;endm=i;r=a+F(m-2)/F(m)*(b-a);u=a+F(m-1)/F(m)*(b-a);fork=1:m-3iff(r)<f(u)a=a;b=u;u=r;r=a+F(m-k-2)/F(m-k)*(b-a);elsea=r;b=b;r=u;u=a+F(m-k-1)/F(m-k)*(b-a);endendX=(r+u)/2;Fmin=double(f(X));K=m;end数值算例:Minf(x)=x*x–x+2;初始区间,精度e<=0.08.容易验证，在此区间上的函数为严格凸函数。为了进行比拟我们给出其精确解：t*=0.5,f(t*)=1.75。键入命令并输出结果：symsxf(x)=x^2-x+2;a1=-1;b1=3;e=0.08;[X,FMIN,K]=fibonacci(f,a1,b1,e)X=0.5273FMIN=1.7507K=10实验三无约束最优化方法的MATLAB实现〔２学时〕实验的目的和要求：通过本次实验使学生进一步熟悉掌握使用MATLAB软件，并能利用该软件进行无约束最优化方法的计算。实验内容：１、最速下降法的MATLAB实现２、牛顿法的MATLAB实现３、共轭梯度法的MATLAB实现学习建议：本次实验就是要通过对一些具体问题的分析进一步熟悉软件的操作并加深对理论知识的理解。重点和难点：通过同一个具体问题用不同的方法解决的比拟，加深理解恰中选用优化问题解决方法的重要性。一最速下降法1.最速下降法根本原理和步骤思想：寻求最速下降方向即负梯度方向MATLAB实现:2.代码及数值算例:程序源代码:function[X,FMIN,K]=zuisuxiajiang(f,x,x0,e)%[X,FMIN,N]=zuisuxiajiang()法求解无约束问题%X极小点%FMIN极小值%K迭代次数%f问题函数%x变量%x0初始点%e终止误差%张超编写于2014/04/15count=0;td=jacobian(f,x)';whilenorm(subs(td,x,x0))>eP=-subs(td,x,x0);symsry=x0+r*P;ft(r)=subs(f,x,y);[r0]=fibonacci(ft,0,100,0.01);x0=x0+r0*P;count=count+1;endX=x0;FMIN=subs(f,x,x0);K=count;end二牛顿法1.牛顿法根本原理和步骤思想：在第k次迭代的迭代点x(k)邻域内，用一个二次函数〔如二阶泰勒多项式〕去近似代替原目标函数f(x)，然后求出该二次函数的极小点作为对原目标函数求优的下一个迭代点，依次类推，通过屡次重复迭代，使迭代点逐步逼近原目标函数的极小点。设f(x)二次连续可微，在点x(k〕处的Hesse矩阵正定。MATLAB实现:2.代码及数值算例:程序源代码:function[X,FMIN,K]=ysNewton(f,x,x0,e)%[X,FMIN,N]=ysNewton()原始牛顿法求解无约束问题%X极小点%FMIN极小值%K迭代次数%f问题函数%x变量%x0初始点%e终止误差%张超编写于2014/04/15count=0;td=jacobian(f,x)';H=jacobian(td',x);whilenorm(subs(td,x,x0))>eP=-subs(H,x,x0)^(-1)*subs(td,x,x0);x0=x0+P;count=count+1;endX=x0;FMIN=subs(f,x,x0);K=count;end牛顿法对于二次正定函数只需做一次迭代就得到最优解。特别在极小点附近，收敛性很好速度也很快。但牛顿法也有缺点，它要求初始点离最优解不远，假设初始点选的离最优解太远时，牛顿法并不能保证其收敛，甚至也不是下降方向。为了克服牛顿法的缺点，人们保存了从牛顿法中选取牛顿方向作为搜索方向，摒弃其步长恒取1的作法，而用一维搜索确定最优步长来构造算法。程序源代码:function[X,FMIN,K]=xzNewton(f,x,x0,e)%[X,FMIN,N]=xzNewton()带步长牛顿法求解无约束问题%X极小点%FMIN极小值%K迭代次数%f问题函数%x变量%x0初始点%e终止误差%张超编写于2014/04/15count=0;td=jacobian(f,x)';H=jacobian(td',x);whilenorm(subs(td,x,x0))>eP=-subs(H,x,x0)^(-1)*subs(td,x,x0);symsry=x0+r*P;ft(r)=subs(f,x,y);[r0]=fibonacci(ft,0,100,0.01);x0=x0+r0*P;count=count+1;endX=x0;FMIN=subs(f,x,x0);K=count;end三共轭梯度法1.共轭梯度法根本原理和步骤思想：将共轭性和最速下降方向相结合，利用迭代点处的梯度方向构造一组共轭方向，并沿此方向进行搜索，求出函数的极小点。MATLAB实现:2.代码及数值算例:程序源代码:function[X,FMIN,K]=gongetidu(f,x,x0,e)%[X,FMIN,N]=gongetidu()共轭梯度法求解无约束问题%X极小点%FMIN极小值%K迭代次数%f问题函数%x变量%x0初始点%e终止误差%张超编写于2014/04/15count=1;td=jacobian(f,x)';H=jacobian(td',x);ifnorm(subs(td,x,x0))>eP=-subs(td,x,x0);r0=-subs(td,x,x0)'*P/(P'*H*P);x0=x0+r0*P;elsex0;endwhilenorm(double(subs(td,x,x0)))>eb0=subs(td,x,x0)'*subs(td,x,x0)/(P'*P);P=-subs(td,x,x0)+b0*P;r0=-subs(td,x,x0)'*P/(P'*H*P);x0=x0+r0*P;count=count+1;endX=x0;FMIN=subs(f,x,x0);K=count;end四一个算例分别用上述三中方法计算下题,并比拟各算法.Minf(x)=(x1-2)^2+(x1–2*x2)^2初始点x0=(0,3)T允许误差e=0.1键入命令并输出结果：symsx1x2>>f=(x1-2)^2+(x1-2*x2)^2;>>x=[x1;x2];>>x0=[0;3];>>e=0.1;[X,FMIN,N]=zuisuxiajiang(f,x,x0,e)X=1.97630.9818FMIN=7.2076e-04N=10>>[X,FMIN,N]=ysNewton(f,x,x0,e)X=21FMIN=0N=1[X,FMIN,N]=gongetidu(f,x,x0,e)X=21FMIN=0N=2由上述结果我们发现：对于二次正定函数newton法只需一次迭代就得到正确结果，共轭梯度法只需进行两次〔因为目标函数是二元函数〕迭代就得出正确结果。但最速下降法却迭代了10次，虽然一维搜索存在误差，但实际上最速下降法也需迭代屡次。实验四约束最优化方法的MATLAB实现〔２学时〕实验的目的和要求：通过本次实验使学生较为熟练使用MATLAB软件，并能利用该软件进行约束最优化方法的计算。实验内容：１、罚函数法的MATLAB实现２、可行方向法的MATLAB实现学习建议：本次实验就是要通过对一些具体问题的分析进一步熟悉软件的操作并加深对理论知识的理解。重点和难点：可行点和辅助函数选取。一罚函数法用罚函数法解minf(x)=(x1-1)^2+x2^2S.T.g(x)=x2-1>=0编写下面m文件fahanshu.msymsx1x2f=(x1-1)^2+x2^2;g=x2-1;x=[x1;x2];x0=[0;0];e=0.0001;M=1;whileabs(subs(g,x,x0))>eifsubs(g,x,x0)<0Q=f+M*g^2;elseQ=f;endx0=xzNewton(Q,x,x0,0.0001);M=10*M;endx0运行得：fahanshux0=1.00000.9999与理论值x=[1;1]很接近。二投影梯度法1.梯度投影法根本原理和步骤思想：当迭代点是可行域的内点时，将目标函数负梯度作为搜索方向，当迭代点在可行域边界上时，将目标函数负梯度在可行域边界上的投影作为搜索方向。无论何种情况，所构造的方向都是可行下降方向。然后在可行域内沿该方向进行最优一维搜索得到新的迭代点。MATLAB实现:2.代码及数值算例:程序源代码:function[X,FMIN,K]=tidutouying(f,A,b,x1,x,e)%[X,FMIN,K]=tidutouying(f,A,b,x1,e)梯度投影法%f目标函数%A约束矩阵b右端项%x1初始点x自由变量%e精度要求%X极小点%FMIN极小值%K迭代次数%张超编写与2014/5/3count=1;n=length(x1);tf=jacobian(f,x)';while1[A1,A2,b1,b2,k]=fenjie(A,b,x1);while1M=A1;ifisempty(M)P=eye(n);elseP=eye(n)-M'*(M*M')^(-1)*M;endPk=-P*subs(tf,x,x1);ifnorm(Pk)<=eifisempty(M)x1;break;elseW=(M*M')^(-1)*M*subs(tf,x,x1);u=W;ifmin(u)<0fori=1:length(u)ifu(i)==min(u)j=i;endendA1(j,:)=[];elsex1;break;endendelseb_=b2-A2*x1;P_=A2*Pk;fori=1:length(P_)ifP_(i)<0r(i)=b_(i)/P_(i);elser(i)=