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

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

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

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

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

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

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

內(nèi)點(diǎn)法要求可行點(diǎn)集的內(nèi)點(diǎn)集合非空，否則算法無(wú)法運(yùn)行。這樣一來(lái)內(nèi)點(diǎn)法只對(duì)不等式約束的優(yōu)化問(wèn)題才可能有效。第54頁(yè),共81頁(yè)，2024年2月25日，星期天55（3）算法分析第55頁(yè),共81頁(yè)，2024年2月25日，星期天56第56頁(yè),共81頁(yè)，2024年2月25日，星期天57（4）算法步驟（內(nèi)點(diǎn)法）：第57頁(yè),共81頁(yè)，2024年2月25日，星期天58內(nèi)點(diǎn)法框圖yesNo第58頁(yè),共81頁(yè)，2024年2月25日，星期天59例解第59頁(yè),共81頁(yè)，2024年2月25日，星期天60用對(duì)數(shù)罰函數(shù)會(huì)更簡(jiǎn)單其他例子見P217-218.第60頁(yè),共81頁(yè)，2024年2月25日，星期天61（5）算法收斂性：（6）罰函數(shù)法的缺點(diǎn)第61頁(yè),共81頁(yè)，2024年2月25日，星期天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)相同(可選用的無(wú)約束最優(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).第62頁(yè),共81頁(yè)，2024年2月25日，星期天636.乘子法乘子罰函數(shù):乘子罰函數(shù)與Langrange函數(shù)及懲罰函數(shù)的區(qū)別：多一項(xiàng)。

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

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

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

從表中可見，xk*比xk近于x*的速度慢得多，用乘子法迭代6次就達(dá)到懲罰函數(shù)法迭代15次的效．這里，懲罰因子在懲罰函數(shù)法中要增大到u15＝3276.8，而在乘子法中只要增大到u6=6.4．相比之下，乘子法不需過(guò)分地增大懲罰因子，確實(shí)比懲罰函數(shù)法有效很多.第68頁(yè),共81頁(yè)，2024年2月25日，星期天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ù)。

第69頁(yè),共81頁(yè)，2024年2月25日，星期天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頁(yè),共81頁(yè)，2024年2月25日，星期天71解:(1)寫成標(biāo)準(zhǔn)形式：例1第71頁(yè),共81頁(yè)，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,得運(yùn)算結(jié)果為：

x=0.76471.0588fval=-2.0294第72頁(yè),共81頁(yè)，2024年2月25日，星期天73解：約束條件的標(biāo)準(zhǔn)形式為（1）在MATLAB編輯器中建立非線性約束函數(shù)文件：function[c,ceq]=nlcon(x)c=(x(1)-1)^2-x(2);ceq=[];%無(wú)等式約束第73頁(yè),共81頁(yè)，2024年2月25日，星期天74（1）在MATLAB編輯器中建立非線性約束函數(shù)文件：function[c,ceq]=nlcon(x)c=(x(1)-1)^2-x(2);ceq=[];%無(wú)等式約束（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=[];%無(wú)線性等式約束beq=[];lb=[];%x沒(méi)有下、上界ub=[];[x,fval,exitflag,output,lambda,grad,hessian]=fmincon(fun2,x0,A,b,Aeq,beq,lb,ub,@nlcon)

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

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

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

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第75頁(yè),共81頁(yè)，2024年2月25日，星期天76二次規(guī)劃問(wèn)題（quadraticprogramming）的Matlab解

第76頁(yè),共81頁(yè)，2024年2月25日，星期天77函數(shù)

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