6.3有约束最优化问题计算机求解

◆惩罚函数法
惩罚函数法可以求解等式或不等式约束的最优 化问题，比拉格朗日法适用性更广。拉格朗日法的 限制性条件为等式，对于限制条件为不等式的最优 化问题，其虽可以近似求解，但不常用。
◆ 1、算法原理：
惩罚函数法所求解的最优化问题的限制条件可 以是没有严格零约束的模糊的或宽松的限制。
考虑如下的最优化问题：
ff=optimset; ff.LargeScale='off'; ff.TolFun=1e-30;ff.TolX=1e-15;ff.Tolcon=1E-20; x0=[1;1;1]; xm=[0;0;0];xM=[]; A=[];B=[];Aeq=[];Beq=[]; [x,f_opt,c,d]=fmincon(y,x0,A,B,Aeq,Beq,xm,xM, @opt_con1,ff)
在matlab中编写函数ex1.m来进行求解，具体 代码如下：
>> x=zeros(1,2); syms x y lama； %用syms表示出转化后的无约束函数 f=x+y+lama*(x^2+y^2-2); %分别求函数关于x、y、lama的偏导 dx=diff(f,x);dy=diff(f,y);dlama=diff(f,lama); %令偏导为0，求解x、y xx=solve(dx,x); %将x表示为lama的函数 yy=solve(dy,y); %将y表示为lama的函数 ff=subs(dlama,{x,y},{xx,yy}); %代入dlama的关于lama的一元函数 lama0=solve(ff); %求解得lama0 x0=subs(xx,lama,lama0)%求得取极值处的x0 y0=subs(yy,lama,lama0)%取极值处的y0 f0=subs(f,{x,y,lama},{x0,y0,lama0})%极值点函数值
例6-24：考虑例6-23中给出的最优化问题，试利用 梯度求解最优化问题，并比较和原例子中所用方 法的优劣。
1、由给出的目标函数可以立即求出下面的梯度函 数（或jocobi矩阵）： syms x1 x2 x3; f=1000-x1*x1-2*x2*x2-x3*x3-x1*x2-x1*x3; J=jocobi(f,[x1 x2 x3])
此例中调用了optinset函数，此函数是用来设 置最优化选项的。该函数的调用格式为： Options=optinset(‘display’， ‘param’1,value1,’param2’,value2,…) 其中，param1、param2…为优化参数名，value1、 value2…为优化参数对应的值。 display有四种选择： off(不显示)，iter（显示迭代） final(显示最后结 果)，nitify(不显示参数)。
>> f=[-2 -4 -6 -8];H=diag([2 2 2 2]); OPT=optimset;OPT.LargeScale='off'; A=[1 1 1 1;3 3 2 1];B=[5;10]; Aeq=[];Beq=[];LB=zeros(4,1); [x,f_opt]=quadprog(H,f,A,B,Aeq,Beq,LB,[],[],OPT)
◆二次型规划的求解
Matlab最优化工具箱提供了求解二次型规划 问题的quadprog()函数，该函数的调用格式为： [x,f_opt,flag,c]=quadprog(H,f,A,B,Ae,Be,xm,xM,x0 OPT,p1,p2)
例6-22：试求解下面的4元二次型规划问题。
min [( x1 1) 2 ( x2 2) 2 ( x3 3) 2 ( x4 4) 2 ] x1 x2 x3 x4 5 x s.t. 3x1 3x2 2 x3 x4 10 x , x , x , x 0 1 2 3 4
代数方程与最优化问题 ---有约束最优化问题计算机求解
石建力 2011.9.25
内容大纲
◆ 约束条件与可行解区域 ◆Βιβλιοθήκη Baidu线性规划问题的计算机求解
◆ 二次规划的求解
◆ 一般非线性规划问题的求解
◆约束条件与可行解区域
◆ 1、有条件最优化问题的一般描述：
◆ 2、约束条件与可行解区域：
下面通过一个例子演示二元问题的可行解 范围与图解结果。
>> [x1,x2]=meshgrid(-3:.1:3);%生成网格线 z=-x1.^2-x2;%计算出矩阵各点的高度 i=find(x1.^2+x2.^2>9);z(i)=NaN; i=find(x1+x2>1);z(i)=NaN; surf(x1,x2,z);shading interp;
>> view(0,90) >> view(-37.5,30)
例6-23：试求解下面的有约束最优化问题。
2 2 min [1000 x12 2 x2 3 x3 x1 x2 x1x3 ] 2 2 x12 x2 x3 25 0 x s.t. 8 x1 14 x2 7 x3 56 0 x , x , x 0 1 2 3
%惩罚函数法求约束最优化问题 clear f='f2222';x0=[3 0]; TolX=1e-4;TolFun=1e-9;MaxIter=100;alpha0=1; %选用不是基于梯度的无约束最优化方法求解，得 正确结果 [xo_Nelder,fo_Nelder]=opt_Nelder(f,x0,TolX,TolFun ,MaxIter); %Nelder方法 [fc_Nelder,fo_Nelder,co_Nelder]=f2222(xo_Nelder); %Nelder方法的结果 [xo_s,fo_s]=fminsearch(f,x0); %matlab内置函数fminsearch() [xo_s,fo_s,co_s]=f2222(xo_s);%相应的结果
3、调用最优化求解函数： x0=[1;1;1];xm=[0;0;0];xM=[]; A=[];B=[];Aeq=[];Beq=[]; ff=optimset;ff.GradObj='on';ff.LargeScale='off'; [x,f_opt,c,d]=fmincon(@opt_fun2,x0,A,B,Aeq,Beq,x m,xM,@opt_con1,ff)
一：将所有约束当做非线性约束 1、写出目标函数： y=@(x)1000-x(1)*x(1)-2*x(2)*x(2)-x(3)*x(3)x(1)*x(2)-x(1)*x(3);%写出目标函数
2、写出非线性约束函数： function [c,ceq]=opt_con1(x) ceq=[x(1)*x(1)+x(2)*x(2)+x(3)*x(3)25;8*x(1)+14*x(2)+7*x(3)-56]; c=[]; %写出非线性约束函数，其中返回值ceq为等 式约束的数学描述，而c为不等式约束 3、调用fmincon()函数
◆一般非线性规划问题求解
通过将约束条件 细化为线性等式、线 性不等式、变量的上 下界约束、非线性等 式、非线性不等式， 原规划问题可写成：
Matlab最优化工具箱中提供了一个fmincon()函 数，专门用于求解各种约束下的最优化问题。该函 数的调用格式为：
[x,f_opt,flag,c]=fmincon(F,x0,f,A,B,Ae,Be,xm,xM, CF,OPT,p1,p2) 其中，F为给目标函数写的M函数或inline()函数， x0为初始搜索点。CF为给非线性约束函数写的M函 数。
◆拉格朗日乘子法
◆ 1、算法原理：
约束条件：
将上述有约束最优化问题转化为下面的无约 束最优化问题：
Remark：拉格朗日乘子法也可以求解约束条件包 含不等式的最优化问题。求解时可以通过引入一个 松弛变量使不等式约束变为等式约束。
◆ 2、算法举例：
例子1：拉格郎日乘子法求解约束最优化问题实 例。采用拉格朗日乘子法求如下最优化问题：
二、考虑线性和非线性 此时，非线性约束函数可简化为： function [c,ceq]=opt_con2(x) ceq=x(1)*x(1)+x(2)*x(2)+x(3)*x(3)-25;c=[]; x0=[1;1;1];Aeq=[8 14 7];Beq=56; [x,f_opt,c,d]=fmincon(@opt_fun1,x0,A,B,Aeq ,Beq,xm,xM,@opt_con2,ff)
常用优化参数说明; TolX为变量误差容限，取值为正，如1e-5，默认值 为1e-10； TolFun为函数值误差容限，取值为正，如1e-9，默 认值为1e-6； MaxIter为最大迭代次数，取值为正整数，如100； TolCon为约束条件误差容限，取值为正，默认值 为1e-6； TolMaxEvals为允许进行函数最大求值次数，取值 为正整数。
◆线性规划问题的计算机求解
下面介绍matlab的最优化工具箱中实现的单纯 形法，通过调用函数linprog()来求解，其调用格式 为：
[x,f_opt,flag,c]=linprog(f,A,B,Ae,Be,xm,xM,x0,… OPT,p1,p2)
其中，f,A,B,Ae,Be,xm,xM与前面的约束条件和目 标函数中的记号是一致的，x0为初始搜索点。各个 矩阵约束如果不存在，则用空矩阵来占位。OPT为 控制选项，该函数还允许使用附加参数p1,p2。x为 返回的结果，f_opt返回的是最优化的目标函数。
f [2, 1, 4, 3, 1]
T
xm [0,0,3.32,0.678, 2.57]T
>> f=-[2 1 4 3 1]'; A=[0 2 1 4 2;3 4 5 -1 -1]; B=[54;62];Ae=[];Be=[]; xm=[0 0 3.32 0.678 2.57]; ff=optimset;ff.LargeScale='off';%不使用大规模 问题求解 ff.TolX=1e-15; ff.TolFun=1e-20; ff.TolCon=1e-20; [x,f_opt,key,c]=linprog(f,A,B,Ae,Be,xm,[],[],ff)
3 1 f [ ,150, ,6] T 4 50
xm [5 5 -5 -5]
xM [inf inf 1inf]
T
T
>> f=[-3/4,150,-1/50,6]'; Aeq=[];Beq=[]; A=[1/4,-60,-1/50,9;1/2,-90,… -1/50,3];B=[0;0]; xm=[-5;-5;-5;-5]; xM=[inf;inf;1;inf]; ff=optimset; ff.TolX=1e-15; ff.TolFun=1e-20; ff.TolCon=1e-20; [x,f_opt,key,c]=linprog(f,A,B ,Aeq,Beq,xm,xM,[0;0;0;0],ff)
2、有了梯度，可把目标函数改写为： function [y,Gy]=opt_fun2(x) y=1000-x(1)*x(1)-2*x(2)*x(2)-x(3)*x(3)-x(1)*x(2) -x(1)*x(3); Gy=[-2*x(1)-x(2)-x(3);-4*x(2)-x(1);-2x(3)-x(1)]; %改写目标函数
例子2：采用惩罚函数求解下面的最优化问题：
约束条件：
将该约束最优化问题转化为无约束问题，构 造新的目标函数：
function [fc,f,c]=f2222(x) f=((x(1)+1)^2+4*(x(2)-1.5)^2)*((x(1)1.2)^2+0.4*(x(2)-0.5)^2); %约束向量 c=[-x(1);-x(2);2*x(1)-x(1)*x(2)+5*x(2)-6; x(1)-x(2)+0.5;x(1)^2-4*x(2)^2+x(2)]; v=[1 1 1 1 1];e=[1 1 1 1 1]'; fc=f+v*((c>0).*exp(e.*c));%新的目标函数
约束条件：
惩罚函数法包含以下两个步骤：
步骤1：构造新的目标函数，将原问题转化为无 约束最优化问题：
步骤2：利用上一节介绍的求解无约束最优化问 题的方法，求新的目标函数的最小值点。
此处使用的无约束最优化方法不能采用基 于梯度的最优化方法，如不可采用牛顿法、最 速下降法等，Nelder-Mead方法可用于此步。