二次规划与非线性规划.ppt

1、1,二次规划与非线性规划,2,一、二次规划(Quadratic Program) 概念,3,2二次规划研究的意义 (1) 二次规划问题简单，便于求解.某些较复杂的非线性规划问题可以转化为求解一系列二次规问题. (2) 实际应用广泛： 工作计划，时间调度，规模经济学，工程设计以及控制领域，设施分配问题，选址问题，二次分配问题，微观经济学的很多问题.化学工程建模.,4,二、Matlab中求解二次规划,5,6,转化为matlab求解格式：,7,8,定义 如果目标函数或约束条件中至少有一个是非线性函数,则最优化问题就叫做非线性规划问题,四、非线性规划的基本概念,一般形式: （1） 其中 ， 是定义在

2、Rn 上的实值函数,9,定义 把满足问题（1）中条件的解 称为可行解（或可行点），所有可行点的集合称为可行集（或可行域）记为D即 问题(1)可简记为 ,10,五、非线性规划的基本解法,SUTM外点法,SUTM内点法（障碍罚函数法）,1 罚函数法,2 近似线性规划法,11,1、罚函数法,罚函数法基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解这类方法称为序列无约束最小化方法简称为SUMT法 其一为SUMT外点法，其二为SUMT内点法,12,近似规划法的基本思想：将问题中的目标函数 和约束条件 近似为线性函数，并对变量的取值范围加以限制，从而得到一个近似

3、线性规划问题，再用单纯形法求解之，把其符合原始条件的最优解作为解的近似,2、近似规划法,每得到一个近似解，都从这点出发，重复以上步骤,这样，通过求解一系列线性规划问题，产生一个由线性规划最优解组成的序列，经验表明，这样的序列往往收敛于非线性规划问题的解,13,14,六、Matlab求解非线性规划问题,其中X为n维变元向量，G(X)与Ceq(X)均为非线性函数组成的向量。,15,1 首先建立M文件fun.m,用来定义目标函数F（X）: function f=fun(X); f=F(X);,MATLAB求解上述问题，基本步骤分三步,16,3 建立主程序.求解非线性规划的函数是fmincon,命令的

4、基本格式如下： (1) x=fmincon(fun,X0,A,b) (2) x=fmincon(fun,X0,A,b,Aeq,beq) (3) x=fmincon(fun,X0,A,b, Aeq,beq,VLB,VUB) (4) x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon) (5)x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon,options) (6) x,fval= fmincon() (7) x,fval,exitflag= fmincon() (8)x,fval,exitflag,output= fm

5、incon(),输出极值点,M文件,迭代的初值,参数说明,变量上下限,fmincon函数可能会给出局部最优解，这与初值X0的选取有关,17,1写成标准形式： s.t.,2x1+3x2 6 s.t. x1+4x2 5 x1,x2 0,例,18,2先建立M-文件 fun3m: function f=fun3(x); f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)2,MATLAB(youh2),3再建立主程序youh2m： x0=1;1; A=2 3 ;1 4; b=6;5; Aeq=;beq=; VLB=0;0; VUB=; x,fval=fmincon(fun3,x0

6、,A,b,Aeq,beq,VLB,VUB),4运算结果为： x = 07647 10588 fval = -20294,19,1先建立M文件fun4m定义目标函数: function f=fun4(x); f=exp(x(1) *(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);,x1+x2 0 s.t. 1.5+x1x2 - x1 - x2 0 -x1x2 10 0,例,2再建立M文件myconm定义非线性约束： function g,ceq=mycon(x) g=x(1)+x(2); 1.5+x(1)*x(2)-x(1)-x(2); -x(1)*x(2)-10;

7、 ceq=;,20,3主程序youh3m为: x0=-1;1; A=;b=; Aeq=1 1;beq=0; vlb=;vub=; x,fval=fmincon(fun4,x0,A,b,Aeq,beq,vlb, vub,mycon),MATLAB(youh3),4 运算结果为： x = -12250 12250 fval = 18951,21,例,1先建立M文件funm定义目标函数: function f=fun(x); f=-2*x(1)-x(2);,2再建立M文件mycon2m定义非线性约束： function g,ceq=mycon2(x) g=x(1)2+x(2)2-25;x(1)2-x(2)2-7; ceq= ;,22,