第7章 約束問題的優(yōu)化方法

第7章約束問題的優(yōu)化方法§7.1可行方向法7.1.1可行方向法的基本思想可行方向法是一類算法，可看作無約束下降算法的自然推廣。典型策略是從可行點出發(fā)，沿著下降可行方向進(jìn)行搜索，求出使目標(biāo)函數(shù)值下降的新的可行點.考慮只含線性約束的非線性規(guī)劃問題：minf(x)(1)s.t.Ax>b(1)Ex=ef(x)為非線性函數(shù)，AgRmxn，EgRixn，bgRm，eGRl.注1:線性約束規(guī)格保證了優(yōu)化問題(1)的可行方向集、線性化可行方向集以及序列化可行方向集是等同的。當(dāng)某個可行方向同時也是目標(biāo)函數(shù)的下降方向時，沿此方向移動一定會在滿足可行性的情況下改進(jìn)迭代點的目標(biāo)函數(shù)值。目前已經(jīng)提出許多可行方向法，用來處理具有線性約束的非線性規(guī)劃問題。搜索方向選擇方式不同形成不同的可行方向法：Zoutendijk可行方向法Rosen梯度投影法Wolfe既約梯度法可行方向的判定：AA2」則非零向量d為X處的可行方向的充要條件是Ad>0，Ed=0AA2」則非零向量d為X處的可行方向的充要條件是Ad>0，Ed=0ib廠b2證明：必要性：設(shè)非零向量d是X處的可行方向.根據(jù)可行方向的定義，35>0,使得對每個Xg(0,5).有X+人d為可行點，即A(X+人d)>b,E(X+人d)=e.b+XAdiiAX+^Ad2b廠bb+XAdiiAX+^Ad2b廠b-2」A2由于X>0，由上式得到Ad>0.1又由E(X+Xd)=e得到1」Ed=0.

充分性：設(shè)Ad>0,Ed=0.i由于A￡>b，則士〉0,使得對于所有的入￡(0,8)，成立A(￡+人d)>b.2 2 2 2根據(jù)假設(shè)及A￡=b，得到A(￡+人d)>b.ii i i上述兩式組合起來就是A(X+Xd)>b.又由Ed=0及EX=e可知E(x+人d)=e表明X+人d是可行點，因此d是X處的可行方向.Zoutendijk可行方向法Zoutendijk子問題：根據(jù)定理1,如果非零向量d同時滿足Nf(X)Td<0,Ad>0,Ed=0,則d是X處的下降可行方向.Zoutendijk可行方向法把確定搜索方向歸結(jié)為求解線性規(guī)劃問題minNf(X)rd(2)如果則x(2)如果則xiEd=0\d\<1,j=1,2,,n在(2)式中，顯然d=0是可行解，可推知目標(biāo)函數(shù)最優(yōu)值必定小于或等于零.目標(biāo)函數(shù)最優(yōu)值小于零，則得到下降可行方向d；否則，如果目標(biāo)函數(shù)最優(yōu)值為零，是K-T點.定理2：考慮問題(1)，設(shè)X是可行解，在點X處有Ax=b，Ax>b，其中112 2,b，b=我1

b1-2」則X為K-T點的充要條件是問題(2)的目標(biāo)函數(shù)最優(yōu)值為零.一維搜索步長的確定：設(shè)d(k)為X(k)處一個下降可行方向.后繼點迭代公式：X(k+1)=X(k)+人d(k)

k人k的取值原則：保持迭代點X(k+1)=X(k)+人d(k)的可行性；k使目標(biāo)函數(shù)值盡可能減小.根據(jù)上述原則，可以通過求解一維搜索問題來確定步長：minf(x(k)+人d(k))(3)s.t.A(x(k)+人d(k))>b(3)E(x(k)+人d(k))=eX>0

由于d（k是可行方向，因此，（3）式中第2個約束是多余的.在點x（k）處，把不等式約束區(qū)分為起作用約束和不起作用約束：A*）=b1,A2x（k）>b2（3）式中第1個約束可以寫成由于d（k）為可行方向，由于d（k）為可行方向，Ad（k）>01然成立.約束條件（4）簡化為Ax（k）+XAd（k）i iAx（k）+1Ad（k）1-2 2b人1b2（4）人>0，以及Aix（k）=b，因此Ax（k）+人Ad（k）>b自問題（3）簡化為minf（x（k）+人d（k））（5）s.t.Ax（k）+XAd（k）>b（5）2 2 2X>0根據(jù)（5）式的約束條件，容易求出入的上限，令.， ，.廣C由Ax（k）>b知b<0.人d人d>b

X>0（5）式的約束條件寫成：由此得到人的上限：入maxmin」￡Id<0>,d不大于0

=[1d?，j.入max8, d>0問題（3）最終簡化成：minf（x（k）+人d（k））（6）s.t.0<X<Xmax給定問題（1）和一個可行點以后，可以通過求解問題（2）得到下降可行方向，通過求解問題（6）確定沿此方向進(jìn)行一維搜索的步長.初始可行點的確定：為求（1）式的一個可行點，引入人工變量（向量）&和門，解輔助線性規(guī)劃min（尤&.+心）i=1 i=1s.t.Ax+&=b （7）Ex+門=e&m>0如果（7）式的最優(yōu)解（x,MR）=（x,0,0），那么x就是（1）式的一個可行解.可行方向法的計算步驟：(l)給定初始可行點X⑴，置k=1.(2)在點X((2)在點X(k)處把A和b分解成-a_b1和Jab1-2」2使得(3)求解線性規(guī)劃問題minNf（x（k））rds.t.Ad>0iEd=0Id\<1,j=1,2,,n得到最優(yōu)解d(k).(4)如果Nf(X(k))Td(k)=0,則停止計算，X(k)為K-T點，否則，進(jìn)行步驟(5).(5)計算力的上限人max，在［0,人max］上作一維搜索：minf(x(k)+人d(k))s.t.0<X<Xmax得到最優(yōu)解人，令kX(k+1)=X(k)+人d(k)k(6)置k:=k+1，返回步驟(2).例：用Zoutendijk可行方向法解下列問題：minx2+x2一2x-4x+6s.t.—2x+X+1>0—X—X+2>0X,X>0取初始可行點X⑴=(0,0)T.第1次迭代：Nf(X(1))=(—2,—4)T，在X⑴處，起作用約束和不起作用約束的系數(shù)矩陣及右端分別為10—210—1a=，a=；b=，b=101，2—1—1；10，2—2min—2dmin—2d—4d1 2s.t.d,d>0-1<d<1-1<d2<1minNf（x⑴）Tds.t.Ad>0即1\d\<1,j=1,2由單純形方法求得最優(yōu)解:

沿d⑵搜索，求步長長2:d=Ad(2)=2100一1「-「1=「-「1人「0「10]「「「-「b=b-Ax⑵=-=220011-1人max=1解一維搜索問題「-21一「「「-「d=Ad⑴==2-1-11-2「-21一「「「-「d=Ad⑴==2-1-11-2再求步長\:-1-210-1b=b-Ax⑴=22-2--1-10=-2=min力maxi解一維搜索問題minf(x(i)+kd⑴)=2處-6人+6s.t.0<k<1得到：ki=1,「1令x⑵=x(i)+kd⑴=i1第2次迭代:及右端分別為A="-21-，A=10「；b=「-「，b=「0一1-1-1，201；1-2，20Vf(X(2))=(0,-2)r，在x⑵處，起作用約束和不起作用約束的系數(shù)矩陣求在x⑵處的下降可行方向:min-2ds.t.2-2d+d>0-d-d>0-1<d<1-1<d2<1由單純形方法求得最優(yōu)解：d⑵-1]minf(x⑵+kd⑵)=2處-2k+2s.t.0<k<1得到：k2=—.2 2

令X(3)=X(2)+人d(2)=令X(3)=X(2)+人d(2)=1/2一3/2第3次迭代：W3(3))=(-1,-1)^；b1=(-2)求在X⑶處的下降可行方向:mins.t.-d-d1 2-d-d>0-1<d<1-1<d2<1由單純形方法求得最優(yōu)解：d⑶=0】13、根據(jù)定理1，X⑶=(2,2)t是K-T點。該例是凸規(guī)劃，X(3)是最優(yōu)解，目標(biāo)函數(shù)最優(yōu)值f=3/2.min將可行方向法推廣到非線性約束情形：考慮不等式約束問題(8)minf(x)(8)s.t.g.(x)>0,i=1,...,m定理3：設(shè)x是問題(8)的可行解，I={i|g.(x)=0}是在x處起作用約束下標(biāo)集，又設(shè)函數(shù)f(x),gi(x)(ieI)在x處可微，函數(shù)gi(x)(iWl)在x處連續(xù)，如果Vf(x)Tdv0，Ng(x)Td>0,ieI則d是下降可行方向.根據(jù)定理3,求下降可行方向歸結(jié)為求解LP問題minz(9)s.t.Vf(x)Td-z<0(9)Vg(x)Td+z>0,ieI設(shè)(9)式的最優(yōu)解為(z,d).如果zv0應(yīng)的X必為設(shè)(9)式的最優(yōu)解為(z,d).如果zv0應(yīng)的X必為FritzJohn點.定理4：設(shè)x是問題(9)的可行解，則d是在x處的下降可行方向；如果z=0，相1={i1§,(x)=0}，則X是FritzJohn點的充要條件是問題(9)的目標(biāo)函數(shù)最優(yōu)值等于零.步長\的確定，仍然需要求解一維搜索問題minf(x(k)+人d(k))s.t.0<X<Xmax其中人 =sup{人Ig(x(k+Xd(k))>0,i=1,...,m} (10)計算步驟：給定初始可行點x⑴，置k=1.令I(lǐng)={iIg(x(k"0}，解線性規(guī)劃問題minzs.t.Nf(x(k))Td-z<0Ng(x(k))Td+z>0,ieIIdl<1,j=1,...,n得最優(yōu)解(zk,d(k))，若乙廣0，則停止計算，x(k)為FritzJohn點；否則，進(jìn)行步驟(3).(3)求解一維搜索問題minf(x(k)+人d(k))s.t.0<X<Xmax其中Xmax由(10)式確定，得到最優(yōu)解Xk.(4)令x(k+1)=x(k)+Xd(k)，置k:=k+1，返回步驟(2).kZoutendijk算法的收斂問題：不能保證Zoutendijk方法迭代產(chǎn)生的序列收斂于K-T點.Topkis-Veinott彳修正Topkis和Veinott把求方向的線性規(guī)劃改成minzs.t.Nf(x)Td-z<0Ng(x)Td+z>-g(x),i=1,…,m|d|<1,j=1,…,n緊約束和非緊約束在確定下降可行方向中均起作用，并且在接近非緊約束邊界時，不至發(fā)生方向突然改變.修正方法計算步驟：給定初始可行點x⑴，置k=1.解線性規(guī)劃問題minzs.t.Nf(x(k))Td-z<0Ng(x(k))Td+z>-g(x(k)),i=1,…，m|dl<1,j=1,.,n得最優(yōu)解(z,d(k)).k若z=0，則停止計算，x(k)為FritzJohn點；否則，進(jìn)行步驟(4).k求解一維搜索問題minf(x(k)+人d(k))s.t.0<X<Xmax其中Xmax由(10)式確定，得到最優(yōu)解Xk.(5)令x(k+i)=x(k)+Xd(k)，置k:=k+1，返回步驟(2).kTopkis-Veinott修正方法的收斂性：定理5:考慮問題(8)，設(shè)函數(shù)f(x),gj(x)(i=1,?..,m)連續(xù)可微，又設(shè)｛x(k))是Topkis-Veinott算法產(chǎn)生的序列，則｛x(k)｝的任一聚點是FritzJohn點.§7.2懲罰函數(shù)法7.2.1懲罰函數(shù)法的基本思想懲罰函數(shù)法的基本思想:借助罰函數(shù)把約束問題轉(zhuǎn)化為無約束問題，進(jìn)而用無約束最優(yōu)化方法來求解.考慮約束問題minf(x)s.t.g(x)>0,i=1,…,m (1)hj(x)=0,j=1,...,l求解的一種途徑是由目標(biāo)函數(shù)和約束函數(shù)組成輔助函數(shù)，把原來的約束問題轉(zhuǎn)化為極小化輔助函數(shù)的無約束問題.對于等式約束問題：(2)minf(x)(2)s.t.h(x)=0,j=1,.,l可定義輔助函數(shù)F(x,b)=f(x)+b^h2(x)j=1參數(shù)b是很大的正數(shù).(2)式轉(zhuǎn)化為無約束問題(3)minF(x,b)(3)求解問題(3)能夠得到問題(2)的近似解.對于不等式約束問題：(4)minf(x)(4)s.t.g(x)>0,i=1,…,m定義輔助函數(shù)F(x,c)=f(x)+b*[max｛0,—g^(x)｝]2i=1

(4)式轉(zhuǎn)化為無約束問題minF2(x,c) (5)通過(5)式求得(4)式的近似解.一般情形((1)式)：可定義輔助函數(shù)F(x,c)=f(x)+cP(x)其中i=1‘4(J)=0,4(j)>0,連續(xù)函數(shù)i=1‘4(J)=0,4(j)>0,連續(xù)函數(shù)4和中滿足條件：｛,、八平(J)=0,j=1J>0J<0J=0〔甲(J)>0,J。0函數(shù)4和中的典型取法：4=[max{0,—g.(x)}]aI中=1h(x)IPj以,P>1為給定常數(shù).通常取作以=P=2.約束問題(1)轉(zhuǎn)化為無約束問題minF(x,c)=f(x)+cP(x) (6)cP(x)稱為罰項，C稱為罰因王，而F(x,c)稱為罰函數(shù)。當(dāng)x為可行點時，P(x)=0，有F(xq)=f(x)；當(dāng)x不是可行點時，cP(x)是很大的正數(shù)，它的存在是對點脫離可行域的一種懲罰，作用是在極小化過程中迫使迭代點靠近可行域.求解問題(6)能夠得到約束問題(1)的近似解。C越大，近似效果越好。7.2.2乘子法1乘子法的基本思想考慮只有等式約束問題(2).運用乘子法事先需要定義增廣Lagrange函數(shù)(乘子罰函數(shù))：4(x,V,c)=f(x)一?h(x)+空h2(x)jj2jj=1 j=1C,,=f⑴一泓⑴+1h(x時⑴b?3,vq)與Lagrange函數(shù)的區(qū)別在于增加罰項5h(x)Th(x)；與罰函數(shù)的區(qū)別在于增加了乘子項—vTh(x).注1：增廣Lagrange函數(shù)與Lagrange函數(shù)及罰函數(shù)具有不同的性態(tài)，即對于?(x,v,b)，只要取足夠大的罰因子b，不必趨向無窮大，就可通過極小化?(x,v,b)，求得問題(2)的局部最優(yōu)解.為證明上述結(jié)論，先給出如下假設(shè)：設(shè)X是等式約束問題(2)的一個局部最優(yōu)解，且滿足二階充分條件，即存在乘子v=(七,…,為)，使得vf(X)—aV=0h(X)=0,j=i,…,i且對每一個滿足dr?七(對=0(j=L…,1)的非零向量d，有dTV2L(X,v)d>0X其中a=(Vh(X),…,Vh(X))，L(X,v)=f(X)—vrh(x)1 l定理1：設(shè)X和v滿足問題(2)的局部最優(yōu)解的二階充分條件，則存在。'>0，使得對所有的b>b'，X是?(x,v,b)的嚴(yán)格局部極小點.反之，若存在點x(0)，使得h(x(0))=0,j=1,…,l且對于某個V(0)，X(0)是?(x,v(0),b)的無約束極小點，又滿足極小點的二階充分條件，則X(0)是問題(2)的嚴(yán)格局部最優(yōu)解.證明：需要用到矩陣?yán)碚摰南嚓P(guān)知識和二階充分條件的定義。注2：根據(jù)定理1，如果知道最優(yōu)乘子v，那么只要取充分大的罰因『，不需趨向無窮大，就能通過極小化?(x,v,b)求出問題(2)的解.注3：確定最優(yōu)乘子v一般方法：先給定充分大的b和Lagrange乘子的初始估計v，然后在迭代過程中修正v，力圖使v趨向v.修正v的公式：設(shè)在第k次迭代中，Lagrange乘子向量的估計為v(k)，罰因子取b，得到?(x,v(k),b)的極小點x(k).這時有V?(x(k),v(k),b)=Vf(x(k))—￡(v(k)—bh(x(k)))Vh(x(k))=0j=1對問題(2)最優(yōu)解X，當(dāng)Vh](X),…,Vhi(X)線性無關(guān)，應(yīng)有Vf(X)—l^v.Vh(X)=0j=1假如x(k)=x，則必有v,=v(k)一。h(x(k))一般來說，X(k)并非是x，因此該等式并不成立.但由此可以給出修正乘包的公式，令V(k+1)=V(k)-Ch,(X(k)),j=1,…，l (7)然后再進(jìn)行第k+1次迭代，求Nx,V(k+1),C)的極小點.這樣做下去，可望v(k)—V,從而X(k)—X.如果｛V(k))不收斂，或者收斂太慢，則增大參數(shù)C，再進(jìn)行迭代.收斂快慢一般用||h(x(k))|/||h(x(k-1))|來衡量.2等式約束問題乘子法計算步驟給定初始點x(0)，乘子向量初始估計v(1)，參數(shù)。，允許誤差^>。，常數(shù)a〉1,P￡(0,1)，置k=1.以x(k-1)為初點，解無約束問題min巾(x,v(k),c)得解x(k).若||h(x(k))||<￡，則停止計算，得到點x(k)；否則，進(jìn)行步驟(4).若||h(x(k))||/||h(x(k-1))||>p，則置C：=ac，轉(zhuǎn)步驟(5)；否則，進(jìn)行步驟(5).用(7)式計算Vj*+1)(j=1,…,l)，置k:=k+1，轉(zhuǎn)步驟(2).例1：用乘子法求解下列問題：min2x2+x2-2xxs.t.h(x)=x+x-1=0增廣Lagrange函數(shù), C9(x,V,C)=2x2+x2—2xx一v(x+x一1)+—(x+x一1)21 2 12 1 2 2 1 2取罰因子c=2，令Lagrange乘子的初始估計v⑴=1，由此出發(fā)求最優(yōu)乘子及問題的最優(yōu)解.以下用解析方法求函數(shù)9(x,v,C)的極小點.第1次迭代：容易求得9(x,V(1),C)的極小點為「1/21x(D=3/4第k次迭代：取乘子v(k)，增廣Lagrange函數(shù)9(x,V(k),C)的極小點為

(v(k)+2)/6x(k)=(v(k)+2)/4現(xiàn)在通過修正v(k)求v(k+1)，由(7)式，有v(k)+2 v(k)+2 v(k)+2v(k+1)=v(k)-bh(X(k))=v(k)一2( + 一1)= 646易證當(dāng)kT8時，序列v(k)」收斂，且「 〃、2limv(k)=—ks 52同時X2同時X(k)———1 5問題的最優(yōu)解得到最優(yōu)乘子v=5.2/5一3/5_注4：在實際計算中，應(yīng)注意b的取值.如果b太大，則會給計算帶來困難；如果b太小，則收斂減慢，甚至出現(xiàn)不收斂情形.3不等式約束問題的乘子法考慮只有不等式約束的問題(4).為利用關(guān)于等式約束問題得到的結(jié)果，引入變量七,把問題(4)化為等式約束問題minf(x)TOC\o"1-5"\h\z\o"CurrentDocument"s.t.g(x)—*=0,j=1, ,mjj這樣可定義增廣Lagrange函數(shù)6(x,y,wq)=f(x)一2.(gj(x)—*)+?2(gj(x)—*)2=1 j=1問題(4)轉(zhuǎn)化為求解~min?(x,y,w,b) (8)~將?(x,y,w,b)關(guān)于y求極小，由此解出y，并代入(8)式，將其化為只關(guān)于x求極小的問題.為此求解~min?(x,y,w,b)y~用配方法將?(x,y,w,b)化為?(x,y,w,b)=f(x)+2[—wj(gj(x)—y2)+：(gj(x)—y2)2]TOC\o"1-5"\h\zj=1 (9)Vb1 w2=f(x)+2![y2—(bg(x)—w)]2-j}2jbj j 2bj=1~為使?(x,y,w,b)關(guān)于yj取極小，yj取值如下：

當(dāng)—g.(當(dāng)—g.(x)—w.>0時當(dāng)—g.(x)—w.<0時綜合以上兩種情形，將上式代入(9)式七=O1即y2= max{0,—g(x)—w.}由此定義增廣Lagrange函數(shù)巾(x,w,—)=f(x)+1Y{[max(0,w——g(x))]2-w2}2— jj jj=1將問題(4)轉(zhuǎn)化為求解無約束問題：min?(x,w,—)4一般約束問題的乘子法對于既含有不等式約束又含有等式約束的問題(1)，定義增廣Lagrange函數(shù)巾(x,w,v,—)=f(x)+—!—Y{[max(0,w——g(x))]2—w2}2— jj jj=1—￡vh(x)+—A(x)jj2jj=1 j=1在迭代中，與只有等式約束問題類似，取定充分大的參數(shù)—，通過修正第k次迭代中的乘子w(k)和v(k)，得到第k+1次迭代中的乘子W(5和v(k+D.乘子w(k)和v(k)修正公式:(10)w(k+1)=max(0,w(k)一—g'(x(k))), j=1,…，m(10)v(k+1)=v(k)——h(x(k)), j=1,.?.,lj計算步驟與等式約束情形相同.例2：用乘子法求解下列問題：min

s.t.x1增廣Lagrange函數(shù)為?(x,w,—)=x2+2x2+2—fmax(0,w——(x+x—1))]2—w2}x2+2x2+-1 2 2—w2x2+2x2—2——fw——(xx2+2x2+-1 2 2—w2x2+2x2—2—TOC\o"1-5"\h\z2— 1 2 1 2 —wx+x—1>——袖2x—[w——(x+x—1)],x+x—1<一。? 1 1 2 1 2 ——-=3 …辦 入 *+*_1>w1 2x, x+x—1>—1 1 2 —w5?dx212 —wx+x—1>12 —4x—[w——(x+5?dx212 —wx+x—1>12 —2 1 2 一

令V?3,w,a)=0尤得到?3,w,a)的無約束極小點2(w+a)V—1 4+3aX2_w+a4+3a取。=2，wen=1，得到?(x,w(1),a)的極小點:X⑴=一%⑴-X(1)L2J=-3/5-3/10修正w(1),令3 3八、6w(2)=max(0,1-2(—+—-1))=5 10 5求得?3,w(2),a)的極小點X(2)=XX(2)=X(2)1X(2)216/258/25以此類推，設(shè)在第k次迭代取乘子w(k)，求得?(X,w(k),a)的極小點「X(k)「「(2+w(k))/5-X(k)=1=X(k)2(2+w(k))/10修正w(k)，得到1w(k+1)=max(0,w(k)-2(X(k)+X(k)-1))=—(2w(k)+4)顯然，按上式迭代得到的序列｛w(k))是收斂的.4X(k)「2/3一貝Ijw(k)——及X(k)=1X(k)2—1/3因此不出注5：在乘子法中，由于參數(shù)a不必趨向無窮大就能求得約束問題的最優(yōu)解，現(xiàn)罰函數(shù)法中的病態(tài).因此不出計算經(jīng)驗表明，乘子法優(yōu)于罰函數(shù)法，受到廣大使用者的歡迎.§7.3序列二次規(guī)劃法7.3.1序列二次規(guī)劃法的基本思想序列二次規(guī)劃法(SQP)的基本思想：在迭代點處構(gòu)造一個二次規(guī)劃(QP)子問題，近似原來的約束優(yōu)化問題：通過求解該QP子問題，獲得約束優(yōu)化問題的一個改進(jìn)迭代點；不斷重復(fù)這個過程，直到求出滿足一定要求的迭代點?？紤]一般的約束優(yōu)化問題

minf(x)s.t.g(x)>0,i=1,…,mhj(x)=0,j=1,?..,l直覺：利用泰勒展開在迭代點X(k)構(gòu)造QP子問題:minf(x)=f(x(k))+.f(x(k))t(x-x(k))+2(x-x(k))TV2f(x(k))(x-x(k))s.t.g(x(k))+Vgi(x(k))t(x-x(k))>0,i=1,…，mh.(x(k))+Vh(x(k))t(x-x(k))=0,j=1,...,l令d=x—x(k)，則(2)等價于二次規(guī)劃：.?、1…、，一 、，minf(x)=—dTV2f(x(k))d+Vf(x(k))td2s.t.g(x(k))+Vg(x(k))td>0,i=1,…,mh.(x(k))+Vh(x(k))td=0,j=1,.,l求出最優(yōu)解為d(k)，則新的迭代點為:x(k+1)=x(k)+d(k)Lagrange-Newton法等式約束的Lagrange-Newton法求解非線性方程組F(x)=0的Newton迭代公式為VF(x)Td(k)+F(x(k))=0x(k+1)=x(k)+d(k)可以證明：解方程組的Newton法具有局部二次收斂性?？紤]等式約束最優(yōu)化問題：minf(x)s.t.h(x)=0,j=1,.,l問題(3)的Lagrange函數(shù)為L(x,v)=f(x)-vTh(x)令A(yù)(x)表示h(x)在x處的Jacobi矩陣，即dh(x) dh(x)TOC\o"1-5"\h\zdx dx:1 :”dh(x) dh(x)\o"CurrentDocument"dx dx1 n」(1)(2)(3)dhA(x)=——dxF(x,v)=VL(x,v)

h(x)Vf(x)-A(1)(2)(3)dhA(x)=——dxF(x,v)=VL(x,v)

h(x)Vf(x)-A(x)tv

h(x)(4)令W(x,v)=V2L(x,v)，則函數(shù)F(x,v)的Jacobi矩陣為xW(x,v)-A(x)TA(x) 0求解非線性方程組(4)的Newton迭代公式為:x(x(k+1)=-x(k)-+d(k)v(k+1)v(k)d(k)v(5)d(k)7是如下線性方程組的解:d(k)v」W(x(k),v(k))—A(x(k))t-d-=—Vf(x(k))—A(x(k))tv(k)A(x(k))0dvh(x(k))(6)稱由(5)-(6)式建立的求解約束最優(yōu)化問題(3)的算法為Lagrange-Newton法.Lagrange-Newton法不易于直接用于不等式約束最優(yōu)化問題，需要導(dǎo)出Lagrange-Newton法的另一種形式.(與QP掛鉤)由約束最優(yōu)化問題的K-T條件不難看出:Lagrange-Newton法迭代公式(5)-(6)計算的d(k)是如下QP問題的解：minq(d)=2d^W(x(k),v(k))d+VL(x(k),v(k))rd )s.t.A(x(k))d+h(x(k))=0且d(k)是相應(yīng)于等式約束的Lagrange乘子.v求解等式約束問題(3)的Newton法可等價地敘述為：先求二次規(guī)劃(7)的K-T點(d(k),d(k))，然后由(5)式確定(x(k+i),v(k+D).v對問題(7)的任何可行點d，有VL(x(k),v(k))Td=Vf(x(k))Td—v(k)tA(x(k))d=Vf(x(k))Td+v(k)Th(x(k))問題(7)等價于二次規(guī)劃minq(d)=2dTW(x(k),v(k))d+Vf(x(k))tds.t.A(x(k))d+h(x(k))=0二次規(guī)劃問題(8)的K-T條件為:Vf(x(k))(9)W(x(k),v(k))—A(x(k))TVf(x(k))(9)h(x(k))A(x(k)h(x(k))比較(5)、(7)、(9)式，可看出：求解非線性方程組(4)的Lagrange-Newton法可等價地敘述為：求QP問題(8)的K-T點(d(k),v(k+1))，令x(k+1)=x(k)+d(k)，由此產(chǎn)生迭代序列｛(x(k),v(k))｝，稱此Lagrange-Newton法為求解等式約束問題(3)的SQP算法.一般約束優(yōu)化問題的Lagrange-Newton法對一般約束優(yōu)化問題，在當(dāng)前點(x(k),似k),v(k))構(gòu)造如下QP子問題:.，八1、[… 、，minq(d)=—dTW(x(k),w(k),v(k))d+Vf(x(k))rdk2(10)s.t.g(x(k))+Vg(x(k))rd>0,i=1,…，m(10)h.(x(k))+Vh.(x(k))Td=0,j=1,...,l解上述QP子問題，得到解d(k)及對應(yīng)的乘子“(k+i)和v(k+i)，產(chǎn)生新的迭代點(x(k+1),“(k+1),v(k+1))，其中x(k+1)=x(k)+d(k).該算法稱為求解約束問題(1)的局部Newton-SQP算法.注1：子問題(10)的目標(biāo)函數(shù)是問題(1)的Lagrange函數(shù)的二次近似，而不是我們通常認(rèn)為的僅是問題(1)的目標(biāo)函數(shù)的二次近似.基于Lagrange-Newton法的局部SQP算法步驟：(1)取初始點(x(D,“⑴,v⑴)，置k=1.(2)若(x俄),似k),v俄))滿足約束問題(1)的K-T條件(從計算角度應(yīng)考察IIVxL(x(k),“(k),v(k))||<e)，則停止計算，得到x(k)；否則，轉(zhuǎn)步驟(3).(3)解QP子問題(10)，得到解(d(k),w(k+i),v(k+i)).(4)令x(k+1)=x(k)+d(k)，k:=k+1，轉(zhuǎn)步驟(2).注2：遺留問題：如何求解QP子問題(后面再討論)？如果初始點取得不恰當(dāng)，即使原問題可行，也可導(dǎo)致QP子問題不相容。QP子問題不相容(可行域為空)如何處理？例1：對于約束V1(x)=，+1>0，在點x=3處，線性化近似約束為匚2產(chǎn)?，[g2(x)=x2>0 [9+6d>0不相容!Wilson-Han-Powell法在構(gòu)造QP子問題(10)時，需要計算Lagrange函數(shù)在迭代點的 Hesse矩陣W=W(x(k),“(k),v(k))，這種計算工作量比較大。k借鑒無約束優(yōu)化的擬牛頓法在迭代過程中利用對稱正定矩陣替代Hesse矩陣的思想，韓世平(S.P.Han)1976年基于Lagrange-Newton法提出了一種利用對稱正定矩陣B^替代矩陣W的序列二次規(guī)劃法(也稱為約束擬牛頓法，約束變尺度法).kWilson在1963年較早地考慮了Lagrange-Newton法.后來Powell在1977年修正了Han的方法，故將這種序列二次規(guī)劃法稱為Wilson-Han-Powell(WHP)方法.對于一般的約束問題(1)，WHP方法需要構(gòu)造如下的QP子問題：./八1，minq(d)=萬drBd+Nf(x(k))td(11)s.t.g(x(k))+Vg(x(k))td>0,i=1,…，mh(x(k))+Vh(x(k))Td=0,j=1,???，l(11)利用子問題(11)的解d(k)作為搜索方向。WHP方法除了用矩陣Bk替代矩陣吒外，新的迭代點不直接按X(k+1)=x(k)+d(k)計算，而是由一維搜索確定步長人k，新的迭代點為X(k+1)=X(k)+ld(k).由于這些改進(jìn)，WHP方法在一定條件下具有全局收斂性.相對于Lagrange-Newton法(局部SQP算法)，WHP方法稱為全局SQP算法.(11)式確定的d(k)具有一個比較好的性質(zhì)：它是許多罰函數(shù)(價值函數(shù)，MeritFunction)的下降方向.WHP方法中一種罰函數(shù)形式如下(范數(shù)-1罰函數(shù)):P(x)=f(x)+億max{0,—g(x)}+工Ih(x)I]/c (12)i=1 j=1c>0為罰因子.利用該罰函數(shù)作一維搜索確定步長.WHP方法的計算步驟：(1)初始化：給定初始點X(。)，對稱正定矩陣B0，容許誤差8>0和滿足芝￡kV+8k=1的非負(fù)序列{￡k}；取參數(shù)c>0，8>0，置k=0.收斂性檢驗：求解二次規(guī)劃子問題(11)，得到最優(yōu)解d(k).若d(k)<8，則得到原來約束優(yōu)化問題的一個近似K-T點X(k)，算法停止；否則，轉(zhuǎn)步驟(3).(3)改進(jìn)迭代點：利用(12)式的罰函數(shù)P(X),按照某種線性搜索規(guī)則確定步長孔6[0,8]，使得P(x(k)+人d(k))<minP(x(k)+人d(k))+8

c k 腥[0,8]c k置X(k+1)=X(k)+人d(k).k(4)修正矩陣Bk:利用矩陣Bk，在x(k)和x(k+1)點的其它信息，計算對稱正定矩陣Bk+1令k:=k+1，轉(zhuǎn)步驟(2).注3：遺留問題：如何求解QP子問題(11)？(后面討論)如何修正Bk獲得Bk+1？如何處理QP子問題不相容？(1)Bk的修正方法：Bk的修正有多種方法：(i)基于擬牛頓校正公式的方法(ii)基于增廣Lagrange函數(shù)的方法

（iii）基于既約Hesse矩陣的方法只介紹基于擬牛頓校正公式的方法.對于Bk的修正，一方面，Bk應(yīng)為Lagrange函數(shù)的Hesse矩陣的近似；另一方面，要保持Bk的對稱正定性，使得相應(yīng)的QP子問題是一個嚴(yán)格的凸二次規(guī)劃問題.類似于無約束問題的擬牛頓法，令p(k)=X(k+1)一%(k)q(k)=VL(%(k+1),W(k+1),V(k+1))-VL(%(k),W(k),v(k))nW(%(k+1),w(k+1),v(k+1))p(k)然后可利用BFGS等公式計算Bkq(BFGS公式)B=b+q(k)q(k)t Bp(k)p(k)tB(BFGS公式)k+1 kq(k)Tp(k) p(k)tBp(k)k注4：與無約束問題不同的是：這種修正不能保證條件q(k)Tp(k)>0(曲率條件)成立，因此，即使Bk對稱正定，也不能保證Bk+1正定.為了克服此困難，1978年P(guān)owell利用q(k)和p(k)的一個凸組合代替q(k)，記為q(k), 如果0(k)Tp(k)>0.2p(k)tBp(k)§q(k)+(1-0k)Bp(k), 其它 " (13)0.8p(k)tBp(k)0= k kp(k)tBp(k)—q(k)Tp(k)

k修正后的BFGS公式(稱為截斷BFGS修正)(14)（15）q(k)q(k)T Bp(k)p(k)tB(14)（15）B=B+— ——k kk+1 k ](k)Tp(k) p(k)TBp(k)k(2)QP子問題不相容的處理：Powell提出了一種處理方法：引進(jìn)輔助變量&，解LP：max&TOC\o"1-5"\h\z\o"CurrentDocument"s.t.Vg(%(k))Td+&g(%(k))>0,ieV={ie11g(%(k))<0}

i i k i\o"CurrentDocument"Vg(x(k))Td+g(x(k))>0,ieS={ie11g(%(k))>0}i i k iVh(%(k))Td+&h(%(k))=0,je{1,,/}\o"CurrentDocument"0<^<1 '&=0,d=0為該問題的可行解，故（15）式的最優(yōu)解總是存在的，記為&，顯然有0<&<1.顯然原子問題（11）（或（10））相容當(dāng)且僅當(dāng)E=1.（i） 若S=0或很小，則改變初始點重新開始，此情況的發(fā)生常常因原問題是不相容的；（ii） 若8>0，則將子問題（11）中的約束條件用（15）中的約束條件代替，即子問題取為

min4(d)=2dTBd+.f(x(k))rds.t.Vg(x(k))Td+Wg(x(k))>0,ieV={ie11g(x(k))<0}(相)TOC\o"1-5"\h\zi i k i 6，\o"CurrentDocument"Vg(x(k))Td+g(x(k))>0,ieS={ie11g(x(k))>0}i i k i\o"CurrentDocument"Vh(x(k))td+Wh(x(k))=0,je{1, ，/}其中&取為(0,W］中的一個定值.例2：對于約束V1(x)=x+1>0，在點x=3處，求如下線性規(guī)劃〔g2(x)=x2>0max&s.t.-d-2^>06d+9>00<^<1最優(yōu)解為W=3/4.若取&=1/2，則對應(yīng)的QP子問題（16）是相容的.7.3.4二次規(guī)劃的求解方法二次規(guī)劃（QP）是非線性規(guī)劃中一種特殊情形，目標(biāo)函數(shù)是二次函數(shù)，約束是線性函數(shù)。許多現(xiàn)實問題本身可建模為二次規(guī)劃。QP是前面討論的SQP的基礎(chǔ)，在每一迭代步，均要求解一個QP子問題。Lagrange方法起作用集方法LemkeLagrange方法起作用集方法Lemke方法路徑跟蹤法（1）（2）（3）（4）Lagrange方法（求解等式約束QP問題）考慮QP問題L1（17）min—xtHx+ctx2（17）s.t.Ax=bh為n階對稱矩陣，A為mxn矩陣，秩為m.該問題的Lagrange函數(shù)為、1L(x,v)=2xtHx+ctx一vt(Ax一b)令VL(x,v)=0，VL(x,v)=0，得到方程組Hx+c一ATv=0-Ax+b=0將此方程組寫成

1H—At「x「「-c]-A0v=-bH -At系數(shù)矩陣 稱為Lagrange矩陣._-A0_設(shè)Lagrange矩陣可逆，可表示為「H一At-1=「Q-Rt-一A0一rS一Rtm+n，推得由式一AtHQ+AtR由式一Atn一HRt一AtS=0nxm一AQ=0mxnARt=Im假設(shè)逆矩陣H-1存在，由上述關(guān)系可得Q,R,S的表達(dá)式Q=H-1-H-1At(AH-1At)-1AH-1R=(AH-1At)-1AH-1S=-（AH-1At）-1（18）式兩端乘以Lagrange矩陣的逆，得到問題的解x=-Qc+RTbv=Rc一Sbx,v的另一種表達(dá)式：設(shè)x（k）是問題（17）的任一可行解，即滿足Ax（k）=b，在此點目標(biāo)函數(shù)的梯度g=.f（X（k））=Hx（k）+C利用X（k）和gk，可將（22）、（23）改寫為X=X（k）一Qgkv=Rgk例3：用Lagrange法求解minX2+2X2+x2-2xx+xs.t.x+x+x=4（19）（20）（21）（22）（（19）（20）（21）（22）（23）（24）（25）-2-20一「0-「1 1「「4一H=-240，c=，0，A=，，b=，2-1120 021」—1」—*TOC\o"1-5"\h\z1 1/20可計算出H-1=1/21/2 00 01/2由(19)-(21)式算得一11/4-3/4-44「3/47/41/4一Q=—1/41/8—3/8，R=—11113/4—11/4—3/4—3/89/8—1—4一3—5/2「S=——11_—5/23再根據(jù)(22)式，計算問題的最優(yōu)解x=(21/11,43/22,3/22)tv=(29/11,-15/11)t起作用集方法(具有不等式約束的QP問題)考慮具有不等式約束的QP問題：.…1 _(26)minf(x)=2xtHx+ctx(26)s.t.Ax>bH為n階對稱正定矩陣，A為mXn矩陣，秩為m.該問題不能直接用Lagrange方法求解，求解的策略之一，是用起作用集方法將它轉(zhuǎn)化為求解等式約束問題.起作用集方法的基本思想：在每次迭代中，以已知的可行點為起點，把在該點起作用約束作為等式約束，在此約束下極小化目標(biāo)函數(shù)，而其余的約束暫且不管，求得新的比較好的可行點后，再重復(fù)以上做法。設(shè)在第k次迭代中，已知可行點x(k)，在該點起作用約束指標(biāo)集用I(k)表示.這時需求解等式約束問題(27)(28)minf((27)(28)s.t.aix=b,ieI(k)a表示矩陣A的第i行，也是在x(k)處起作用約束函數(shù)的梯度.將坐標(biāo)原點移至x(k)，令5=x—x(k)，貝ijf(x)=[(5+x(k))tH(5+x(k))+CT(5+x(k))2=J-5tH5+5tHx(k)+—x(k)tHx(k)+CT5+CTx(k)22=15tH5+.f(x(k))T5+f(x(k))2問題(27)等價干求校等量5(k)的問題:

(29)min^8tH8+Vf(尤(k))t6(29)2s.t.ai8=0,ieI(k)解此二次規(guī)劃問題，求出最優(yōu)解8(k)，然后區(qū)別不同的情形，決定下面應(yīng)采取的步驟.(1)如果x(k)+8(k)是可行點，且8(k)主0，則在第k+1次迭代中，已知點取作X(k+1)=x(k)+8(k)(2)如果x(k)+8(k)不是可行點，則令方向d(k)=8(k)，沿d(k)搜索.令X(k+1)=x(k)+人d(k)沿方向d(k)搜索步長孔確定方法：基本要求：保持點的可行性.氣的取值應(yīng)使得對于每個i冬I(k)，有ai(x(k)+人d(k))>b (30)已知X(k)是可行點，故aiX(k)>b.當(dāng)ad(k)>0時，對于任意非負(fù)數(shù)R,(30)式總成立；當(dāng)aid(k)<0時，只要取正數(shù)b—aix(k)人<min] 1i冬I(k),aid(k)<0>k aid(k)對于每個i任I(k)，(30)式成立..b.b—aix(k)=min] aid(k)IiwI(k),aid(k)<0>8(k)是問題(29)的最優(yōu)解，為在第k次迭代中得到較好的可行點，應(yīng)取TOC\o"1-5"\h\z人=min{1,人} (31)k k并令 x(k+1)=x(k)+人d(k)k如果\o"CurrentDocument"人b-apx(k) 1k apd(k)則在點x(k+1)，有apx(k+1)=ap(x(k)+人d(k))=b故在x(k+1)處，apx>bp為起作用約束.把指標(biāo)p加入I(k)，得到在x(k+1)處的起作用約束指標(biāo)集I(k+1).如果8(k)=0，則x(k是問題(27)的最優(yōu)解，這時應(yīng)判斷x(k是否為問題(26)的最優(yōu)解.為此，需要用(25)式計算起作用的約束乘子v(k)(ieI(k)).i(i)如果這些v(k)>0，則點x(k)是問題(26)的K-T點.(26)是凸規(guī)劃，因i此x(k是最優(yōu)解.(ii)如果存在qeI(k，使得v(k)<0,則x(k)不可能是最優(yōu)解.把下標(biāo)q剔出qI(k).如果有幾個乘子同時為負(fù)數(shù)，令vk)=min{v件IieI(k)}，將對應(yīng)v(k)的約束從起作用約束集中去掉，再解問題(29).注5：可以驗證：當(dāng)%<0時，在x(k)處存在可行下降方向.如設(shè)4(k)是起作用約束系數(shù)矩陣，