非線性規(guī)劃課件

數(shù)學(xué)建模與數(shù)學(xué)實驗參考書目：趙靜但琦－數(shù)學(xué)建模于數(shù)學(xué)實驗，高等教育出版社，2005非線性規(guī)劃

西安電子科技大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院李偉1例1：約束回歸某大學(xué)希望為它的畢業(yè)生安排工作位置。為簡單起見，假設(shè)每個畢業(yè)生接受政府部門、工業(yè)界或科學(xué)院中的一個位置。令：2最小，模型可表示為：3解設(shè)投資決策變量4

定義

目標(biāo)函數(shù)或約束條件中至少有一個是非線性函數(shù)時的最優(yōu)化問題就叫做非線性規(guī)劃問題．非線性規(guī)劃的基本概念

一般形式:

（1）其中，是定義在En上的實值函數(shù)，簡記:

其它情況:

求目標(biāo)函數(shù)的最大值或約束條件為小于等于零的情況，都可通過取其相反數(shù)化為上述一般形式．5

定義1

把滿足問題（1）中條件的解稱為可行解（或可行點），所有可行點的集合稱為可行集（或可行域）．記為D．即問題(1)可簡記為．定義2

對于問題(1)，設(shè)，若存在,使得對一切，且，都有，則稱X*是f(X)在D上的局部極小值點（局部最優(yōu)解）．特別地當(dāng)時，若則稱X*是f(X)在D上的嚴(yán)格局部極小值點（嚴(yán)格局部最優(yōu)解）．定義3對于問題(1),設(shè),對任意的,都有則稱X*是f(X)在D上的全局極小值點（全局最優(yōu)解）．特別地當(dāng)時，若，則稱X*是f(X)在D上的嚴(yán)格全局極小值點（嚴(yán)格全局最優(yōu)解）．6非線性規(guī)劃的基本解法SUTM外點法SUTM內(nèi)點法（障礙罰函數(shù)法）1、罰函數(shù)法2、近似規(guī)劃法7

罰函數(shù)法

罰函數(shù)法基本思想是通過構(gòu)造罰函數(shù)把約束問題轉(zhuǎn)化為一系列無約束最優(yōu)化問題，進(jìn)而用無約束最優(yōu)化方法去求解．這類方法稱為序列無約束最小化方法．簡稱為SUMT法．其一為SUMT外點法，其二為SUMT內(nèi)點法．8

其中T(X,M)稱為罰函數(shù)，M稱為罰因子，帶M的項稱為罰項，這里的罰函數(shù)只對不滿足約束條件的點實行懲罰：當(dāng)時，滿足各，故罰項=0，不受懲罰．當(dāng)時，必有的約束條件，故罰項>0，要受懲罰．SUTM外點法9

罰函數(shù)法的缺點是：每個近似最優(yōu)解Xk往往不是容許解，而只能近似滿足約束，在實際問題中這種結(jié)果可能不能使用；在解一系列無約束問題中，計算量太大，特別是隨著Mk的增大，可能導(dǎo)致錯誤．1、任意給定初始點X0，取M1>1，給定允許誤差，令k=0；2、求無約束極值問題的最優(yōu)解，設(shè)為Xk=X(Mk)，即；3、若存在使則取Mk+1>Mk()令k=k+1返回（2），否則，停止迭代．得最優(yōu)解.SUTM外點法(罰函數(shù)法)的迭代步驟10SUTM內(nèi)點法（障礙函數(shù)法）11

內(nèi)點法的迭代步驟12

近似規(guī)劃法的基本思想：將問題(1)中的目標(biāo)函數(shù)和約束條件近似為線性函數(shù)，并對變量的取值范圍加以限制，從而得到一個近似線性規(guī)劃問題，再用單純形法求解之，把其符合原始條件的最優(yōu)解作為(1)的解的近似．近似規(guī)劃法每得到一個近似解后，都從這點出發(fā)，重復(fù)以上步驟．

這樣，通過求解一系列線性規(guī)劃問題，產(chǎn)生一個由線性規(guī)劃最優(yōu)解組成的序列，經(jīng)驗表明，這樣的序列往往收斂于非線性規(guī)劃問題的解。13

近似規(guī)劃法的算法步驟如下1415Matlab求解有約束非線性規(guī)劃1.用fmincon函數(shù)求解形如下面的有約束非線性規(guī)劃模型一般形式：用Matlab求解有約束非線性最小化問題求解非線性規(guī)劃問題的Matlab函數(shù)為：fmincon

1.約束中可以有等式約束 2.可以含線性、非線性約束均可輸入?yún)?shù)語法：x=fmincon(fun,x0,A,b)x=fmincon(fun,x0,A,b,Aeq,beq)x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub)x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2,...)輸入?yún)?shù)的幾點說明模型中如果沒有A,b,Aeq,beq,lb,ub的限制，則以空矩陣[]作為參數(shù)傳入；nonlcon：如果包含非線性等式或不等式約束，則將這些函數(shù)

編寫為一個Matlab函數(shù)，nonlcon就是定義這些函數(shù)的程序文件名；不等式約束c(x)<=0等式約束ceq(x)=0.如果nonlcon=‘mycon’;則myfun.m定義如下function[c,ceq]=mycon(x)c=...

%計算非線性不等式約束在點x處的函數(shù)值ceq=...

%計算機(jī)非線性等式約束在點x處的函數(shù)值

對參數(shù)nonlcon的進(jìn)一步示例2個不等式約束，2個等式約束3個決策變量x1，x2，x3如果nonlcon以‘mycon1’作為參數(shù)值，則程序mycon1.m如下對照約束條件編寫myfun1.mfunction[c,ceq]=mycon1(x)c(1)=x(1)*x(1)+x(2)*x(2)+x(3)*x(3)-100c(2)=60-x(1)*x(1)+10*x(3)*x(3)ceq(1)=x(1)+x(2)*x(2)+x(3)-80ceq(2)=x(1)^3+x(2)*x(2)+x(3)-80nonlcon的高級用法允許提供非線性約束條件中函數(shù)的梯度設(shè)置方法：options=optimset('GradConstr','on')

如果提供非線性約束條件中函數(shù)梯度，nonlcon的函數(shù)必須如下格式：參數(shù)nonlcon的函數(shù)一般格式如下function[c,ceq,GC,GCeq]=mycon(x)c=...

%計算非線性不等式約束在點x處的函數(shù)值

ceq=...

%計算機(jī)非線性等式約束在點x處的函數(shù)值

ifnargout>2

%nonlcon如果四個輸出參數(shù)

GC=...

%不等式約束的梯度

GCeq=...

%等式約束的梯度end輸出參數(shù)語法：[x,fval]=fmincon(...)[x,fval,exitflag]=fmincon(...)[x,fval,exitflag,output]=fmincon(...)[x,fval,exitflag,output,lambda]=fmincon(...)[x,fval,exitflag,output,lambda,grad]=fmincon(...)[x,fval,exitflag,output,lambda,grad,hessian]=fmincon(...)運用步驟：將自己的模型轉(zhuǎn)化為上面的形式寫出對應(yīng)的參數(shù)調(diào)用函數(shù)fmincon應(yīng)用求解示例：請問：1、結(jié)合fmincon函數(shù)，需要提供哪些參數(shù)第一步：編寫一個M文件返回目標(biāo)函數(shù)f在點x處的值函數(shù)程序functionf=myfun(x)f=-x(1)*x(2)*x(3);函數(shù)myfun.m第二步：為了調(diào)用MATLAB函數(shù)，必須將模型中的約束轉(zhuǎn)化為如下形式(<=)。

這里：A=[-1-2-2;122];b=[072]’;這是2個線性約束，形如第三步：提供一個搜索起點，然后調(diào)用相應(yīng)函數(shù)，程序如下：%給一個初始搜索點 x0=[10;10;10];[x,fval]=fmincon('m