二次规划与非线性规划

1二次规划与非线性规划2一、二次规划(QuadraticProgram)概念二次规划:带有二次目标函数和线性约束的最优化问题.它是最简单的约束非线性规划问题.1.标准形式1min(),2..,,,.TTTiiTiiqxxGxgxstaxbiEaxbiI(1)其中G是nn的对称矩阵.,EI分别对应等式约束和不等式约束指标集合.,,,igxandaiEI都是n维向量32．二次规划研究的意义(1)二次规划问题简单，便于求解.某些较复杂的非线性规划问题可以转化为求解一系列二次规问题.(2)实际应用广泛：工作计划，时间调度，规模经济学，工程设计以及控制领域，设施分配问题，选址问题，二次分配问题，微观经济学的很多问题.化学工程建模.4二、Matlab中求解二次规划类型模型基本函数名一元函数极小minF（x）s.t.x1xx2x=fminbnd(‘F’,x1,x2)无约束极小minF(X)X=fminunc(‘F’,X0)X=fminsearch(‘F’,X0)线性规划minXcTs.t.AX≤bX=linprog(c,A,b)二次规划min21xTHx+gTxs.t.Ax≤bX=quadprog(H,g,A,b)约束极小（非线性规划）minF(X)s.t.G(X)≤0X=fmincon(‘FG’,X0)达到目标问题minrs.t.F(x)-wr≤goalX=fgoalattain(‘F’,x,goal,w)极小极大问题minmax{Fi(x)}x{Fi(x)}s.t.G(x)≤0X=fminimax(‘FG’,x0)5[X,FVAL]=QUADPROG(H,g,A,b,Aeq,beq,LB,UB,X0,OPTIONS)X的返回值是向量x，FVAL的返回值是目标函数在X处的值。（具体细节可以参看在Matlab指令中运行helpquadprog后的帮助）。例求解二次规划0,94336442)(min21212121222121xxxxxxx-x-xxx-xxf6转化为matlab求解格式：1221122121221122441min()244634821130..,4190xfxx-xxx-x-xxxxxxstxx7解编写如下程序：h=[4,-4;-4,8];g=[-6;-3];A=[1,1;4,1];b=[3;9];[x,value]=quadprog(h,g,A,b,[],[],zeros(2,1))求得1.02501)(Min,0500.19500.1xfx8定义如果目标函数或约束条件中至少有一个是非线性函数,则最优化问题就叫做非线性规划问题．四、非线性规划的基本概念一般形式:（1）其中，是定义在Rn上的实值函数Xfminjihgf,,nTnRxxxX,,,21L.,...,2,10m;1,2,...,0..ljXhiXgtsji9定义把满足问题（1）中条件的解称为可行解（或可行点），所有可行点的集合称为可行集（或可行域）．记为D．即问题(1)可简记为．XfDXmin)(nRXnjiRXXhXgXD,0,0|10五、非线性规划的基本解法SUTM外点法SUTM内点法（障碍罚函数法）1．罚函数法2．近似线性规划法111、罚函数法罚函数法基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解．这类方法称为序列无约束最小化方法．简称为SUMT法．其一为SUMT外点法，其二为SUMT内点法．12近似规划法的基本思想：将问题中的目标函数和约束条件近似为线性函数，并对变量的取值范围加以限制，从而得到一个近似线性规划问题，再用单纯形法求解之，把其符合原始条件的最优解作为解的近似．Xf0(1,...,);0(1,,)ijgXimhXjl2、近似规划法每得到一个近似解，都从这点出发，重复以上步骤．这样，通过求解一系列线性规划问题，产生一个由线性规划最优解组成的序列，经验表明，这样的序列往往收敛于非线性规划问题的解．13实现方法是:在点kX处，将Xf，XhXgji,按泰勒级数展开并取一阶近似，得到近似线性规划问题：TminkkkfXfXfXXX01,,TkkkiiigXgXgXXXimT0j1,,kkkjjjhXhXhXXXl；14六、Matlab求解非线性规划问题标准型为：minF(X)s.t．AXbbeqXAeqG(X)0Ceq(X)=0VLBXVUB其中X为n维变元向量，G(X)与Ceq(X)均为非线性函数组成的向量。151．首先建立M文件fun.m,用来定义目标函数F（X）:functionf=fun(X);f=F(X);2.若约束条件中有非线性约束:G(X)0或Ceq(X)=0,则建立M文件nonlcon.m定义函数G(X)与Ceq(X):function[G,Ceq]=nonlcon(X)G=…Ceq=…MATLAB求解上述问题，基本步骤分三步163．建立主程序.求解非线性规划的函数是fmincon,命令的基本格式如下：(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]=fmincon(…)输出极值点M文件迭代的初值参数说明变量上下限fmincon函数可能会给出局部最优解，这与初值X0的选取有关．171．写成标准形式：s.t.00546322121xxxx2100xx22212121212minxxxxf22212121212minxxxxf2x1+3x26s.t.x1+4x25x1,x20例182．先建立M-文件fun3．m:functionf=fun3(x);f=-x(1)-2*x(2)+(1/2)*x(1)^2+(1/2)*x(2)^2MATLAB(youh2)3．再建立主程序youh2．m：x0=[1;1];A=[23;14];b=[6;5];Aeq=[];beq=[];VLB=[0;0];VUB=[];[x,fval]=fmincon('fun3',x0,A,b,Aeq,beq,VLB,VUB)4．运算结果为：x=0．76471．0588fval=-2．0294191．先建立M文件fun4．m定义目标函数:functionf=fun4(x);f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);12212122()e(42421)xfxxxxxxx1+x20s.t.1.5+x1x2-x1-x20-x1x2–100例2．再建立M文件mycon．m定义非线性约束：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];ceq=[];203．主程序youh3．m为:x0=[-1;1];A=[];b=[];Aeq=[11];beq=[0];vlb=[];vub=[];[x,fval]=fmincon('fun4',x0,A,b,Aeq,beq,vlb,vub,'mycon')MATLAB(youh3)4．运算结果为：x=-1．22501．2250fval=1．895121例12221122221212min2s.t.2507005,010fXxxgXxxgXxxxx1．先建立M文件fun．m定义目标函数:functionf=fun(x);f=-2*x(1)-x(2);2．再建立M文件mycon2．m定义非线性约束：function[g,ceq]=mycon2(x)g=[x(1)^2+x(2)^2-25;x(1)^2-x(2)^2-7];ceq=[];223．主程序fxx．m为:x0=[3;2．5];VLB=[00];VUB=[510];[x,fval,exitflag,output]=fmincon('fun',x0,[],[],[],[],VLB,VUB,'mycon2')MATLAB(fxx(fun))