二次規(guī)劃與非線性規(guī)劃

1、1,二次規(guī)劃與非線性規(guī)劃,2,一、二次規(guī)劃(Quadratic Program) 概念,3,2．二次規(guī)劃研究的意義(1) 二次規(guī)劃問題簡單，便于求解.某些較復(fù)雜的非線性規(guī)劃問題可以轉(zhuǎn)化為求解一系列二次規(guī)問題.(2) 實際應(yīng)用廣泛：工作計劃，時間調(diào)度，規(guī)模經(jīng)濟學(xué)，工程設(shè)計以及控制領(lǐng)域，設(shè)施分配問題，選址問題，二次分配問題，微觀經(jīng)濟學(xué)的很多問題.化學(xué)工程建模.,4,二、Matlab中求解二次規(guī)劃,5,6,轉(zhuǎn)化為matlab求解格式

2、：,,7,8,定義 如果目標(biāo)函數(shù)或約束條件中至少有一個是非線性函數(shù),則最優(yōu)化問題就叫做非線性規(guī)劃問題．,四、非線性規(guī)劃的基本概念,一般形式: （1） 其中 ， 是定義在

3、Rn 上的實值函數(shù),9,定義 把滿足問題（1）中條件的解 稱為可行解（或可行點），所有可行點的集合稱為可行集（或可行域）．記為D．即 問題(1)可簡記為 ．,10,五、非線性規(guī)劃的基本解法,SUTM外點法,SUTM內(nèi)點法（障礙罰函數(shù)法）,1． 罰函數(shù)法,2． 近似線性規(guī)劃法,11,1、罰函數(shù)法,罰函數(shù)法基本思想是通過構(gòu)造罰函數(shù)把約束問題轉(zhuǎn)化為一

4、系列無約束最優(yōu)化問題，進而用無約束最優(yōu)化方法去求解．這類方法稱為序列無約束最小化方法．簡稱為SUMT法． 其一為SUMT外點法，其二為SUMT內(nèi)點法．,12,近似規(guī)劃法的基本思想：將問題中的目標(biāo)函數(shù) 和約束條件 近似為線性函數(shù)，并對變量的取值范圍加以限制，從而得到一個近似線性規(guī)劃問題，再用單純形法求解之，把其符合原始條件的最優(yōu)解作為解的

5、近似．,2、近似規(guī)劃法,每得到一個近似解，都從這點出發(fā)，重復(fù)以上步驟．,這樣，通過求解一系列線性規(guī)劃問題，產(chǎn)生一個由線性規(guī)劃最優(yōu)解組成的序列，經(jīng)驗表明，這樣的序列往往收斂于非線性規(guī)劃問題的解．,13,14,六、Matlab求解非線性規(guī)劃問題,其中X為n維變元向量，G(X)與Ceq(X)均為非線性函數(shù)組成的向量。,15,1． 首先建立M文件fun.m,用來定義目標(biāo)函數(shù)F（X）:function f=fun(X);f=F(X);,MAT

6、LAB求解上述問題，基本步驟分三步,16,3． 建立主程序.求解非線性規(guī)劃的函數(shù)是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

7、,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(…),輸出極

8、值點,,M文件,,迭代的初值,,參數(shù)說明,,變量上下限,,,fmincon函數(shù)可能會給出局部最優(yōu)解，這與初值X0的選取有關(guān)．,17,,,1．寫成標(biāo)準(zhǔn)形式： s.t.,2x1+3x2 6 s.t. x1+4x2 5 x1,x2 0,例,18,,2．先建立M-文件 fun3．m: function f=fun

9、3(x); f=-x(1)-2*x(2)+(1/2)*x(1)^2+(1/2)*x(2)^2,MATLAB(youh2),3．再建立主程序youh2．m： x0=[1;1]; A=[2 3 ;1 4]; b=[6;5]; Aeq=[];beq=[]; VLB=[0;0]; VUB=[]; [x,fval]=fmincon('fun3',x0,A,b,Aeq,beq,VLB,VUB),4．運算結(jié)果為：

10、 x = 0．7647 1．0588 fval = -2．0294,19,,1．先建立M文件fun4．m定義目標(biāo)函數(shù): 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

11、 - x2 0 　　-x1x2 –10 0,例,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=[];,20,,3．主程序youh3．m為:x0=

12、[-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． 運算結(jié)果為： x = -1．2250 1．2250 fval = 1．8951,21,例

13、,1．先建立M文件fun．m定義目標(biāo)函數(shù): function f=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=[ ];,22,3． 主程序fxx．m為: x0=[3;2．5]; VLB=[0 0]