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

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

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

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

（5）一般模型的外點法

算法步驟相同第51頁,共81頁，2024年2月25日，星期天52(6)算法收斂性詳見P202，引理8.1，定理8.2.詳見P203，定理8.4.第52頁,共81頁，2024年2月25日，星期天535、內點法（障礙函數法）（1）集合結構第53頁,共81頁，2024年2月25日，星期天54（2）算法思想

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

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

?

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

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

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

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

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

第69頁,共81頁，2024年2月25日，星期天70函數

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年2月25日，星期天71解:(1)寫成標準形式：例1第71頁,共81頁，2024年2月25日，星期天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,得運算結果為：

x=0.76471.0588fval=-2.0294第72頁,共81頁，2024年2月25日，星期天73解：約束條件的標準形式為（1）在MATLAB編輯器中建立非線性約束函數文件：function[c,ceq]=nlcon(x)c=(x(1)-1)^2-x(2);ceq=[];%無等式約束第73頁,共81頁，2024年2月25日，星期天74（1）在MATLAB編輯器中建立非線性約束函數文件：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)';%目標函數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年2月25日，星期天75則結果為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=%目標函數在最小值點的梯度

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

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

第76頁,共81頁，2024年2月25日，星期天77函數

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