非線性規(guī)劃理論與算法

關(guān)于非線性規(guī)劃理論與算法非線性規(guī)劃及其最優(yōu)性條件第2頁,共81頁，星期六，2024年，5月3約束集或可行域:非線性規(guī)劃x*是整體(全局)極小點x*是嚴格整體(全局)極小點x*是局部極小點x*是嚴格局部極小點非線性規(guī)劃向量化表示p=q=0即無約束規(guī)劃第3頁,共81頁，星期六，2024年，5月4非線性規(guī)劃的幾個概念線性化可行方向:可行方向錐第4頁,共81頁，星期六，2024年，5月5定義3:積極約束:或起作用約束（緊約束\積極約束\有效約束）。第5頁,共81頁，星期六，2024年，5月6證明:定理1:定義4:可行下降方向第6頁,共81頁，星期六，2024年，5月7定理2:定理3:證略③極值點的必要條件:第7頁,共81頁，星期六，2024年，5月8嚴格凸組合嚴格凸線性組合為凸規(guī)劃。若f(x)是凸函數(shù)，S是凸集，一般要求當i=1,2,…,p時為凸函數(shù)，當i=p+1,…,p+q時為線性函數(shù)。凸規(guī)劃的局部解是整體解！第8頁,共81頁，星期六，2024年，5月9第9頁,共81頁，星期六，2024年，5月10定理：可微函數(shù)解的必要條件：x*是局部解,則：最優(yōu)性條件無約束規(guī)劃x*是駐點(穩(wěn)定點)可微凸函數(shù)解的充要條件：x*是整體極小解當且僅當?shù)?0頁,共81頁，星期六，2024年，5月11約束規(guī)劃最優(yōu)性條件的幾何表述梯度共線第11頁,共81頁，星期六，2024年，5月12共面

梯度被線性標示約束規(guī)劃最優(yōu)性條件的幾何表述第12頁,共81頁，星期六，2024年，5月13結(jié)論：在解處僅等式(緊)約束有效！約束規(guī)劃最優(yōu)性條件的幾何表述第13頁,共81頁，星期六，2024年，5月14對約束定義7.有效約束(緊約束、積極約束)——activeconstraint在x*處有則稱在x*處ci(x)是緊約束。x*處有效約束指標集梯度的負線性表示!第14頁,共81頁，星期六，2024年，5月15向量化表示約束規(guī)劃最優(yōu)性必要條件Karush-Kuhn-Tucker條件——KKT條件互補松弛條件第15頁,共81頁，星期六，2024年，5月16Lagrange函數(shù)Karush-Kuhn-Tucker條件——KKT條件Lagrange乘子：互補松弛條件：約束規(guī)格——約束限制(規(guī)范)條件第16頁,共81頁，星期六，2024年，5月17約束規(guī)劃最優(yōu)性充分條件鞍點條件同時的最優(yōu)解！證明：由的任意性知:且進一步由不等式的后兩部分知:第17頁,共81頁，星期六，2024年，5月18凸規(guī)劃最優(yōu)性充要條件Karush-Kuhn-Tucker條件——KKT條件第18頁,共81頁，星期六，2024年，5月19定理(FritzJohn條件):其他最優(yōu)性條件第19頁,共81頁，星期六，2024年，5月20FritzJohn條件與KKT條件的區(qū)別:FritzJohn條件可能出現(xiàn)w0=0的情形。這時FritzJohn條件中實際上不包含目標函數(shù)的任何數(shù)據(jù)，只是把起作用約束的梯度組合成零向量。這樣的條件，對于問題的解的描述，沒有多大價值。我們感興趣的是w0≠0的情形，所以為了保證w0≠0，還需要對約束施加某種限制。這種限制條件通常稱為約束規(guī)格。在上一個定理中，如果增加緊約束的梯度線性無關(guān)的約束規(guī)格，則給出問題的KKT條件。第20頁,共81頁，星期六，2024年，5月211)所有規(guī)劃解的最優(yōu)性必要條件=KKT條件+約束規(guī)格2)凸規(guī)劃解的最優(yōu)性充分條件=KKT條件最優(yōu)性條件總結(jié)最優(yōu)性必要條件證明：需要用到凸集分離定理、擇一性定理(Farkas引理凸規(guī)劃最優(yōu)性充分條件證明較簡單，但對非凸規(guī)劃結(jié)果沒有實際指導(dǎo)意義，蘊含著對偶原理——Langrange對偶第21頁,共81頁，星期六，2024年，5月22例:

求約束極值問題第22頁,共81頁，星期六，2024年，5月23第23頁,共81頁，星期六，2024年，5月24第24頁,共81頁，星期六，2024年，5月25第25頁,共81頁，星期六，2024年，5月26最優(yōu)性條件舉例線性規(guī)劃最優(yōu)性條件是充分的？是必要的？標準形式：練習：推廣形式的最優(yōu)性條件第26頁,共81頁，星期六，2024年，5月27最優(yōu)性條件舉例二次規(guī)劃最優(yōu)性條件什么條件下是充分的？什么條件下是必要的？推廣一：推廣二：簡化：第27頁,共81頁，星期六，2024年，5月對偶理論第28頁,共81頁，星期六，2024年，5月29最大最小對偶目標函數(shù):x方的目標是無論y怎樣，都應(yīng)使F越小越好；y方的目標是無論x怎樣，都應(yīng)使F越大越好；立于不敗之地的決策方法——保守主義決策相關(guān)結(jié)論：——一對對偶問題——弱對偶定理——對偶間隙第29頁,共81頁，星期六，2024年，5月30最大最小對偶舉例——博弈第30頁,共81頁，星期六，2024年，5月31最大最小對偶鞍點條件:對相關(guān)結(jié)論：——弱對偶定理——對偶間隙若有點則稱(x*,y*)滿足鞍點條件。——強對偶定理滿足鞍點條件。第31頁,共81頁，星期六，2024年，5月32原規(guī)劃:Lagrange對偶Lagrange函數(shù)Lagrange對偶弱對偶性:——弱對偶定理——對偶間隙原規(guī)劃凹函數(shù)第32頁,共81頁，星期六，2024年，5月33Lagrange對偶舉例第33頁,共81頁，星期六，2024年，5月34像集第34頁,共81頁，星期六，2024年，5月35第35頁,共81頁，星期六，2024年，5月36第36頁,共81頁，星期六，2024年，5月37連續(xù)可微凸規(guī)劃:強對偶定理：連續(xù)可微凸規(guī)劃，滿足一約束規(guī)格，則Lagrange對偶的強對偶定理f、g可微凸，h線性1)：若原問題有解，則對偶問題也有解；2)：若原問題與對偶問題分別有可行解，則他們是最優(yōu)解的充分必要條件是他們對應(yīng)相同的目標值(對偶間隙為0).證1)：即證可微凸規(guī)劃的最優(yōu)解與其KKT條件的乘子滿足鞍點條件！證2)：利用鞍點條件可得。3)：對偶問題無上界，則原問題不可行；原問題無下界，則對偶問題不可行。第37頁,共81頁，星期六，2024年，5月38連續(xù)可微凸規(guī)劃:Wolfe對偶：Wolfe對偶f、g可微凸，h線性1)：若原問題有解，則對偶問題也有解；2)：若原問題與對偶問題分別有可行解，則他們是最優(yōu)解得充分必要條件是他們對應(yīng)相同的目標值(對偶間隙為0).Lagrange函數(shù)Wolfe對偶定理：連續(xù)可微凸規(guī)劃，滿足一約束規(guī)格，則第38頁,共81頁，星期六，2024年，5月39凸規(guī)劃對偶舉例(Q正定)二次規(guī)劃(Q正定)推廣一：推廣二：Lagrange對偶共軛對偶、廣義Lagrange對偶——參閱《非線性規(guī)劃及其理論》(應(yīng)玖茜、魏權(quán)齡)第6章第39頁,共81頁，星期六，2024年，5月罰函數(shù)法第40頁,共81頁，星期六，2024年，5月41懲罰函數(shù)法將有約束優(yōu)化問題轉(zhuǎn)化為一系列無約束優(yōu)化問題進行求解。（SequentialUnconstrainedMinimizationTechnique-SUMT）1、算法思想：2、算法類型：外點法（外懲法）內(nèi)點法（內(nèi)懲法）3、問題：第41頁,共81頁，星期六，2024年，5月424、外點法（外部懲罰函數(shù)法）第42頁,共81頁，星期六，2024年，5月43第43頁,共81頁，星期六，2024年，5月44第44頁,共81頁，星期六，2024年，5月45（1）幾何解釋第45頁,共81頁，星期六，2024年，5月46（2）算法步驟（外點法）：第46頁,共81頁，星期六，2024年，5月47yesNo（3）外點法框圖第47頁,共81頁，星期六，2024年，5月48（4）應(yīng)注意的問題第48頁,共81頁，星期六，2024年，5月49例:第49頁,共81頁，星期六，2024年，5月50參閱P207——例2關(guān)于2個約束的例子!第50頁,共81頁，星期六，2024年，5月51

（5）一般模型的外點法

算法步驟相同第51頁,共81頁，星期六，2024年，5月52(6)算法收斂性詳見P202，引理8.1，定理8.2.詳見P203，定理8.4.第52頁,共81頁，星期六，2024年，5月535、內(nèi)點法（障礙函數(shù)法）（1）集合結(jié)構(gòu)第53頁,共81頁，星期六，2024年，5月54（2）算法思想

內(nèi)點法（障礙函數(shù)法）的迭代點是在可行域點集內(nèi)部移動的，對接近可行域邊界上的點施加越來越大的懲罰，對可行域邊界上的點施加無限大的懲罰，這好比邊界是一道障礙物，阻礙迭代點穿越邊界。

內(nèi)點法要求可行點集的內(nèi)點集合非空，否則算法無法運行。這樣一來內(nèi)點法只對不等式約束的優(yōu)化問題才可能有效。第54頁,共81頁，星期六，2024年，5月55（3）算法分析第55頁,共81頁，星期六，2024年，5月56第56頁,共81頁，星期六，2024年，5月57（4）算法步驟（內(nèi)點法）：第57頁,共81頁，星期六，2024年，5月58內(nèi)點法框圖yesNo第58頁,共81頁，星期六，2024年，5月59例解第59頁,共81頁，星期六，2024年，5月60用對數(shù)罰函數(shù)會更簡單其他例子見P217-218.第60頁,共81頁，星期六，2024年，5月61（5）算法收斂性：（6）罰函數(shù)法的缺點第61頁,共81頁，星期六，2024年，5月62(7)內(nèi)、外點法的優(yōu)缺點的比較1.x(0)∈S0(參閱P220討論內(nèi)點的選取)2.等式約束不適用3.障礙函數(shù)B(x)在S0的可微階數(shù)與gi(x)相同(可選用的無約束最優(yōu)化方法廣)4.迭代中x（k）∈R(隨時可取x（k）≈x*)5.非凸規(guī)劃適用1.任意x(0)∈Rn2.等式約束適用3.懲罰項的二階偏導(dǎo)在S的邊界上不存在4.迭代中x(k)

?

R5.非凸規(guī)劃適用內(nèi)點法外點法作業(yè)：P246.1,2,4,7,8,9,10.補充——求2、9、10、11中規(guī)劃的KKT點.第62頁,共81頁，星期六，2024年，5月636.乘子法乘子罰函數(shù):乘子罰函數(shù)與Langrange函數(shù)及懲罰函數(shù)的區(qū)別：多一項。

(1)等式約束第63頁,共81頁，星期六，2024年，5月64乘子罰函數(shù):第64頁,共81頁，星期六，2024年，5月65(2)等式、不等式約束第65頁,共81頁，星期六，2024年，5月66算法步驟（乘子罰函數(shù)法）：第66頁,共81頁，星期六，2024年，5月67解：1.懲罰函數(shù)法。對于懲罰函數(shù)例：問題的最優(yōu)解為x*=(0.25,0.75),分別用懲罰函數(shù)法和乘子法求它的迭代點列。

可求得最優(yōu)解為：

2.乘子法。對于乘子罰函數(shù)可求得最優(yōu)解為：第67頁,共81頁，星期六，2024年，5月68

從表中可見，xk*比xk近于x*的速度慢得多，用乘子法迭代6次就達到懲罰函數(shù)法迭代15次的效．這里，懲罰因子在懲罰函數(shù)法中要增大到u15＝3276.8，而在乘子法中只要增大到u6=6.4．相比之下，乘子法不需過分地增大懲罰因子，確實比懲罰函數(shù)法有效很多.第68頁,共81頁，星期六，2024年，5月69Matlab求解約束非線性規(guī)劃其中：x、b、beq、lb、ub是向量，A、Aeq為矩陣，C(x)、Ceq(x)是約束向量的函數(shù)，f(x)為目標函數(shù)，f(x)、C(x)、Ceq(x)可以是非線性函數(shù)。

第69頁,共81頁，星期六，2024年，5月70函數(shù)

fmincon格式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,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(…)第70頁,共81頁，星期六，2024年，5月71解:(1)寫成標準形式：例1第71頁,共81頁，星期六，2024年，5月72(2)先建立M-文件fun1.m:

functionf=fun1(x);f=-x(1)-2*x(2)+(1/2)*x(1)^2+(1/2)*x(2)^2(3)再建立主程序youh1.m：

x0=[1;1];A=[23;14];b=[6;5];Aeq=[];beq=[];LB=[0;0];UB=[];[x,fval]=fmincon('fun1',x0,A,b,Aeq,beq,LB,UB)(4)在命令窗口中輸入youh1,得運算結(jié)果為：

x=0.76471.0588fval=-2.0294第72頁,共81頁，星期六，2024年，5月73解：約束條件的標準形式為（1）在MATLAB編輯器中建立非線性約束函數(shù)文件：function[c,ceq]=nlcon(x)c=(x(1)-1)^2-x(2);ceq=[];%無等式約束第73頁,共81頁，星期六，2024年，5月74（1）在MATLAB編輯器中建立非線性約束函數(shù)文件：function[c,ceq]=nlcon(x)c=(x(1)-1)^2-x(2);ceq=[];%無等式約束（2）在命令窗口鍵入如下命令或建立M文件：fun2='x(1)^2+x(2)^2-x(1)*x(2)-2*x(1)-5*x(2)';%目標函數(shù)x0=[01];A=[-23];%線性不等式約束b=6;Aeq=[];%無線性等式約束beq=[];lb=[];%x沒有下、上界ub=[];[x,fval,exitflag,output,lambda,grad,hessian]=fmincon(fun2,x0,A,b,Aeq,beq,lb,ub,@nlcon)

第74頁,共81頁，星期六，2024年，5月75則結(jié)果為x=34fval=-13exitflag=%解收斂

1output=iterations:2funcCount:9stepsize:1algorithm:'medium-scale:SQP,Quasi-Newton,line-search'firstorderopt:[]cgiterations:[]lambda=lower:[2x1double]%x下界有效情況，通過lambda.lower可查看。

upper:[2x1double]%x上界有效情況，為0表示約束無效。

eqlin:[0x1double]%線性等式約束有效情況，不為0表示約束有效。

eqnonlin:[0x1double]%非線性等式約束有效情況。

ineqlin:2.5081e-008%線性不等式約束有效情況。

ineqnonlin:6.1938e-008%非線性不等式約束有效情況。grad=%目標函數(shù)在最小值點的梯度

1.0e-006*-0.17760hessian=%目標函數(shù)在最小值點的Hessian值

1.0000-0.0000-0.00001.0000第75頁,共81頁，星期六，2024年，5月76二次規(guī)劃問題（quadraticprogramming）的Matlab解

第76頁,共81頁，星期六，2024年，5月77函數(shù)

quadprogx=quadprog(H,f,A,b,Aeq,beq,lb,ub)%lb,ub分別為為x的下上界。x=quadprog(H,f,A,b,Aeq,beq,lb,ub,x