關(guān)于非線性規(guī)劃理論與算法第一頁(yè)，共八十一頁(yè)，編輯于2023年，星期四非線性規(guī)劃及其最優(yōu)性條件第二頁(yè)，共八十一頁(yè)，編輯于2023年，星期四3約束集或可行域:非線性規(guī)劃x*是整體(全局)極小點(diǎn)x*是嚴(yán)格整體(全局)極小點(diǎn)x*是局部極小點(diǎn)x*是嚴(yán)格局部極小點(diǎn)非線性規(guī)劃向量化表示p=q=0即無約束規(guī)劃第三頁(yè)，共八十一頁(yè)，編輯于2023年，星期四4非線性規(guī)劃的幾個(gè)概念線性化可行方向:可行方向錐第四頁(yè)，共八十一頁(yè)，編輯于2023年，星期四5定義3:積極約束:或起作用約束（緊約束\積極約束\有效約束）。第五頁(yè)，共八十一頁(yè)，編輯于2023年，星期四6證明:定理1:定義4:可行下降方向第六頁(yè)，共八十一頁(yè)，編輯于2023年，星期四7定理2:定理3:證略③極值點(diǎn)的必要條件:第七頁(yè)，共八十一頁(yè)，編輯于2023年，星期四8嚴(yán)格凸組合嚴(yán)格凸線性組合為凸規(guī)劃。若f(x)是凸函數(shù)，S是凸集，一般要求當(dāng)i=1,2,…,p時(shí)為凸函數(shù)，當(dāng)i=p+1,…,p+q時(shí)為線性函數(shù)。凸規(guī)劃的局部解是整體解！第八頁(yè)，共八十一頁(yè)，編輯于2023年，星期四9第九頁(yè)，共八十一頁(yè)，編輯于2023年，星期四10定理：可微函數(shù)解的必要條件：x*是局部解,則：最優(yōu)性條件無約束規(guī)劃x*是駐點(diǎn)(穩(wěn)定點(diǎn))可微凸函數(shù)解的充要條件：x*是整體極小解當(dāng)且僅當(dāng)?shù)谑?yè)，共八十一頁(yè)，編輯于2023年，星期四11約束規(guī)劃最優(yōu)性條件的幾何表述梯度共線第十一頁(yè)，共八十一頁(yè)，編輯于2023年，星期四12共面梯度被線性標(biāo)示約束規(guī)劃最優(yōu)性條件的幾何表述第十二頁(yè)，共八十一頁(yè)，編輯于2023年，星期四13結(jié)論：在解處僅等式(緊)約束有效！約束規(guī)劃最優(yōu)性條件的幾何表述第十三頁(yè)，共八十一頁(yè)，編輯于2023年，星期四14對(duì)約束定義7.有效約束(緊約束、積極約束)——activeconstraint在x*處有則稱在x*處ci(x)是緊約束。x*處有效約束指標(biāo)集梯度的負(fù)線性表示!第十四頁(yè)，共八十一頁(yè)，編輯于2023年，星期四15向量化表示約束規(guī)劃最優(yōu)性必要條件Karush-Kuhn-Tucker條件——KKT條件互補(bǔ)松弛條件第十五頁(yè)，共八十一頁(yè)，編輯于2023年，星期四16Lagrange函數(shù)Karush-Kuhn-Tucker條件——KKT條件Lagrange乘子：互補(bǔ)松弛條件：約束規(guī)格——約束限制(規(guī)范)條件第十六頁(yè)，共八十一頁(yè)，編輯于2023年，星期四17約束規(guī)劃最優(yōu)性充分條件鞍點(diǎn)條件同時(shí)的最優(yōu)解！證明：由的任意性知:且進(jìn)一步由不等式的后兩部分知:第十七頁(yè)，共八十一頁(yè)，編輯于2023年，星期四18凸規(guī)劃最優(yōu)性充要條件Karush-Kuhn-Tucker條件——KKT條件第十八頁(yè)，共八十一頁(yè)，編輯于2023年，星期四19定理(FritzJohn條件):其他最優(yōu)性條件第十九頁(yè)，共八十一頁(yè)，編輯于2023年，星期四20FritzJohn條件與KKT條件的區(qū)別:FritzJohn條件可能出現(xiàn)w0=0的情形。這時(shí)FritzJohn條件中實(shí)際上不包含目標(biāo)函數(shù)的任何數(shù)據(jù)，只是把起作用約束的梯度組合成零向量。這樣的條件，對(duì)于問題的解的描述，沒有多大價(jià)值。我們感興趣的是w0≠0的情形，所以為了保證w0≠0，還需要對(duì)約束施加某種限制。這種限制條件通常稱為約束規(guī)格。在上一個(gè)定理中，如果增加緊約束的梯度線性無關(guān)的約束規(guī)格，則給出問題的KKT條件。第二十頁(yè)，共八十一頁(yè)，編輯于2023年，星期四211)所有規(guī)劃解的最優(yōu)性必要條件=KKT條件+約束規(guī)格2)凸規(guī)劃解的最優(yōu)性充分條件=KKT條件最優(yōu)性條件總結(jié)最優(yōu)性必要條件證明：需要用到凸集分離定理、擇一性定理(Farkas引理凸規(guī)劃最優(yōu)性充分條件證明較簡(jiǎn)單，但對(duì)非凸規(guī)劃結(jié)果沒有實(shí)際指導(dǎo)意義，蘊(yùn)含著對(duì)偶原理——Langrange對(duì)偶第二十一頁(yè)，共八十一頁(yè)，編輯于2023年，星期四22例:

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

（5）一般模型的外點(diǎn)法

算法步驟相同第五十一頁(yè)，共八十一頁(yè)，編輯于2023年，星期四52(6)算法收斂性詳見P202，引理8.1，定理8.2.詳見P203，定理8.4.第五十二頁(yè)，共八十一頁(yè)，編輯于2023年，星期四535、內(nèi)點(diǎn)法（障礙函數(shù)法）（1）集合結(jié)構(gòu)第五十三頁(yè)，共八十一頁(yè)，編輯于2023年，星期四54（2）算法思想

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

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

?

R5.非凸規(guī)劃適用內(nèi)點(diǎn)法外點(diǎn)法作業(yè)：P246.1,2,4,7,8,9,10.補(bǔ)充——求2、9、10、11中規(guī)劃的KKT點(diǎn).第六十二頁(yè)，共八十一頁(yè)，編輯于2023年，星期四636.乘子法乘子罰函數(shù):乘子罰函數(shù)與Langrange函數(shù)及懲罰函數(shù)的區(qū)別：多一項(xiàng)。

(1)等式約束第六十三頁(yè)，共八十一頁(yè)，編輯于2023年，星期四64乘子罰函數(shù):第六十四頁(yè)，共八十一頁(yè)，編輯于2023年，星期四65(2)等式、不等式約束第六十五頁(yè)，共八十一頁(yè)，編輯于2023年，星期四66算法步驟（乘子罰函數(shù)法）：第六十六頁(yè)，共八十一頁(yè)，編輯于2023年，星期四67解：1.懲罰函數(shù)法。對(duì)于懲罰函數(shù)例：?jiǎn)栴}的最優(yōu)解為x*=(0.25,0.75),分別用懲罰函數(shù)法和乘子法求它的迭代點(diǎn)列。

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

2.乘子法。對(duì)于乘子罰函數(shù)可求得最優(yōu)解為：第六十七頁(yè)，共八十一頁(yè)，編輯于2023年，星期四68

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

第六十九頁(yè)，共八十一頁(yè)，編輯于2023年，星期四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(…)第七十頁(yè)，共八十一頁(yè)，編輯于2023年，星期四71解:(1)寫成標(biāo)準(zhǔn)形式：例1第七十一頁(yè)，共八十一頁(yè)，編輯于2023年，星期四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,得運(yùn)算結(jié)果為：

x=0.76471.0588fval=-2.0294第七十二頁(yè)，共八十一頁(yè)，編輯于2023年，星期四73解：約束條件的標(biāo)準(zhǔn)形式為（1）在MATLAB編輯器中建立非線性約束函數(shù)文件：function[c,ceq]=nlcon(x)c=(x(1)-1)^2-x(2);ceq=[];%無等式約束第七十三頁(yè)，共八十一頁(yè)，編輯于2023年，星期四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)';%目標(biāo)函數(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)

第七十四頁(yè)，共八十一頁(yè)，編輯于2023年，星期四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=%目標(biāo)函數(shù)在最小值點(diǎn)的梯度

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

1.0000-0.0000-0.00001.0000第七十五頁(yè)，共八十一頁(yè)，編輯于2023年，星期四76二次規(guī)劃問題（quadraticprogramming）的Matlab解

第七十六頁(yè)，共八十一頁(yè)，編輯于2023年，星期四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,x0)%x0為設(shè)置的初值x=qua