第4章 最優(yōu)性條件

第4章最優(yōu)性條件§4.1最優(yōu)性條件的預(yù)備知識極小點(diǎn)的定義無約束問題：1 (1)定義1(全局極小點(diǎn))若存在XGRn使得f(X)Zf(x), VxgRn則稱X為問題(1)的全局極小點(diǎn)。如果有f(x)>f(X), VxgRn,X豐X則稱X為問題(1)的嚴(yán)格全局極小點(diǎn)。定義2(局部極小點(diǎn))設(shè)XGRn，如果存在5>0使得f(x)>f(X), VxgN5(X)則稱X為問題(1)的局部極小點(diǎn)。如果有f(X)>f(X), VxgN5(X)/{X}則稱X為問題(1)的嚴(yán)格局部極小點(diǎn)。約束問題：minf(x) (2)s.t.g(x)>0,i=1,…,mh(x)=0,j=1,…,l其中f(x),g,(x),h/(x)都是定義在Rn上的實值連續(xù)函數(shù)，且至少有一個是非線性的。稱f(x)為目標(biāo)函數(shù)，g,(x)為不等式約束函數(shù)，七(x)為等式約束函數(shù)。(i)如果m=0,稱(2)為等式約束優(yōu)化問題；如果l=0,稱(2)為不等式約束優(yōu)化問題；如果g,(x)(i=1,…,m),h\x)(j=1,...,l)都為線性函數(shù)，f(x)是二次函數(shù)，則稱(2)為二次規(guī)劃問題。若xgRn滿足(2)的所有約束條件，稱X為(2)的可行點(diǎn)(或可行解)。可行集(可行域)：S=g.(x)>0,i=1,...,m,可行集(可行域)：S=Xhj(x)>0,j=1,???,l.定義3(全局極小點(diǎn))設(shè)XgS使得f(x)>f(X), VxgS成立，則稱x為問題(2)的全局極小點(diǎn)。如果有f(x)>f(x), VxgS,x。x

成立，則稱無為問題(2)的嚴(yán)格全局極小點(diǎn)。定義4(局部極小點(diǎn))設(shè)%eS，如果存在5>0使得f⑴>f(%), VxeN5(%)AS成立，則稱％為問題(2)的局部極小點(diǎn)。如果有f(%)>f(%), V%eN5(%)AS,%。%成立，則稱%為問題(2)1的嚴(yán)格局部極小點(diǎn)。內(nèi)容安排■求全局極小點(diǎn)一般來說相當(dāng)困難。實際上可行的只是求一個局部(或嚴(yán)格局部)極小點(diǎn)。故本課程后面所指極小點(diǎn)，通常指求局部極小點(diǎn)?！鰞H當(dāng)問題為凸規(guī)劃(即目標(biāo)函數(shù)f(%)為凸函數(shù)，不等式約束函數(shù)一g(%),i='???,m為凸函數(shù)，等式約束函數(shù)hj(%),j=1,…,l為線性函數(shù))時，局部極小點(diǎn)才是全局極小點(diǎn)。■按定義驗證最優(yōu)解是不可能的。因此有必要給出只依賴于在％處目標(biāo)函數(shù)和約束函數(shù)信息的、且與定義等價的條件。這樣的條件稱其為最優(yōu)性條件，它們是各種基于梯度算法的理論基礎(chǔ)。§4.2無約束問題的最優(yōu)性條件Max單變量優(yōu)化問題必要f(%)=0Max單變量優(yōu)化問題必要f(%)=0充分*3f(%)=0f(%)凹必要f(%)=0f(%)<0充分*4f(%)=0以%)<0多變量優(yōu)化問題Vf(%)=0f(%)凹V2f(%)半負(fù)定V2f(%)負(fù)定考慮無約束問題(1)，回憶當(dāng)%eR時，即單變量函數(shù)極值問題的最優(yōu)性條件：必要條件：若%eR且f(%)在％處取到極值，如果f(%)在％可微，則％為f(%)的駐點(diǎn)，即滿足f'(%)=0。充分條件：若%eR且f(%)在%處可微，如果f,(%)=0且f"(%)>0，則f(%)在%處取到極小值；如果f,(%)=0且f,(%)<0，則f(%)在元處取到極大值。Min一階條件必要二階條件充分*2必要充分知單變量優(yōu)化問題f(%)=0f(%)=0f(%)凸f(%)=0f(%)>0f(元)=0f(%)>0多變量優(yōu)化問題Vf(%)=0*1：%為全局極小點(diǎn)；Vf(%)=0 Vf(%)=0f⑴凸 V2f(%)半正定*2：%為嚴(yán)格局部極小點(diǎn)。Vf(%)=0V2f(%)正定一階條件二階條件

*3：元為全局極大點(diǎn)； *4：x為嚴(yán)格局部極大點(diǎn)。定理1(一階必要條件):設(shè)無eRn為函數(shù)f(x)在Rn的局部極小點(diǎn)，且f(x)在x可微，則W(X)=0。證明利用§4.0中的定理1可證。幾何解釋:若X為局部極小點(diǎn)，則f(x)在X處不能有下降方向。從而，當(dāng)Nf(x)。0時，-Vf(x)為f(x)在x處的一個下降方向，故若xeRn為函數(shù)f(x)在Rn的極值點(diǎn)，必有Nf(x)=0。定理2(二階必要條件)：設(shè)xeRn為函數(shù)f(x)在Rn的局部極小點(diǎn)，且f(x)在x二階可微，則有Vf(x)=0，且V2f(x)半正定證明：利用f(x)在x的二階Taylor展開及局部極小點(diǎn)的定義可得。幾何解釋：由x為局部極小點(diǎn)及Vf(x)=0所確定。定理3(二階充分條件)：設(shè)f(x)是定義在Rn上的二次可微函數(shù)，如果Vf(x)=0，且V2f(x)正定，則x為函數(shù)f(x)在Rn的嚴(yán)格局部極小點(diǎn)。證明利用f(x)在x的二階Taylor展開及正定矩陣的定義可得。注：滿足Vf(x)=0的點(diǎn)稱為f(x)的平穩(wěn)點(diǎn)或駐點(diǎn)。駐點(diǎn)可能是極大值點(diǎn)，也可能是極小值點(diǎn)，也可能不是極值點(diǎn)。但若目標(biāo)函數(shù)為凸函數(shù)，則駐點(diǎn)就是全局極小值點(diǎn)；若目標(biāo)函數(shù)為凹函數(shù)，則駐點(diǎn)就是全局極大值點(diǎn)。定理4(凸充分性定理)：設(shè)f(x)是定義在Rn上的凸函數(shù)，如果Vf(x)=0，則x為函數(shù)f(x)在Rn上的全局極小點(diǎn)。(一階必要條件+凸性)證明利用可微凸函數(shù)的一階判別條件和Vf(x)=0易證。例：利用極值條件求解minf(x)=xeR2解：fdx1f=x2-2x解：fdx1dx 2 22令Vf(x)=0，即x2—1=0，x2—2x=0。得到駐點(diǎn)：x(1)=T，x(2)=，T，x(3)=，"—1-，x(4)=，「-「02022x0Hesse矩陣：V2f(x)= 10 2x—2在點(diǎn)x⑴,x(2),x⑶,x(4)處Hesse矩陣：

v2f3(1))=v2f3(1))=V2f(X(2))=20V2f(x(3))=-20-2V2f(X(4))=-20V2f(X(1))和V2f(X(4))不定，根據(jù)定理2,X(1),X(4)不是極小點(diǎn)；V2f(X(3))負(fù)定，X(3)是極大點(diǎn)；V2f(X(2))正定，根據(jù)定理3,X(2)是局部極小點(diǎn)。§4.3約束問題的極值條件4.3.1—階最優(yōu)性條件引入記號：E={1,…,/}――等式約束指標(biāo)集1={1,…,m} 不等式約束指標(biāo)集定義1:對(2)的任何可行解~eS，若g(~)=0,ieI，稱第i個不等式約束在~處是i緊的，稱集合I(~)={iIgj(~)=0,ieI}為不等式約束中在~處的緊約束指標(biāo)集。稱A(~)=EUI(~)是在~處的積極集合(有效約束指標(biāo)集，或緊約束指標(biāo)集)?？尚屑弦稽c(diǎn)是否為局部極小點(diǎn)，取決于目標(biāo)函數(shù)在該點(diǎn)以及附近其它可行點(diǎn)上的值?？尚蟹较蛟谕茖?dǎo)最優(yōu)性條件中起十分重要的作用。各種可行方向的定義：定義2:設(shè)XeS，0。deRn，如果存在5>0，使得X+人deS，VXe(0,5)則稱d是集合S在x處的可行方向。S在X處的可行方向的集合記為FD(X,S)。問題：問FD(X,Rn)？(FD(X,Rn)=Rn/{0})例1：考慮集合S={xeR21x=x2}，S={xeR21x>x2}1 2 1 2 2 1在點(diǎn)X=(0,0)T處的可行方向集，則0FD(X,S)=01FD(X,S)={(d,d)IdeR,d>0}2 12 1 2定義3:設(shè)XeS，deRn，如果dTVh(X)=0,jeE；dVg.(X)>0,ieI(X)則稱d是集合S在x處的線性化可行方向。S在x處的線性化可行方向的集合記為LFD(X,S)。

定義4:設(shè)元eS,dgRn，如果存在序列{d*}和{8J，其中8疽0,使得x+8dkeS，VkXk-Xd=limk^^^Xk且有dk—d和8*—0，則稱d是集合S在x處的序列可行方向。S在Xk-Xd=limk^^^Xk-Xl注：可行方向為幾何概念，線性化可行方向為代數(shù)概念，序列可行方向是基于極限定義的幾何概念。例2S={xeR21X2=X]2}，取X=(0,0)丁，則FD(X,S)=0LFD(X,S)={(d,0)1deR}SFD(X,S)={(d,0)1deR}上述定義的三個可行方向集有如下關(guān)系：引理1設(shè)XeS，如果所有的約束函數(shù)在X處可微，則有FD(X,S)cSFD(X,S)cLFD(X,S)。注：該結(jié)論條件可以放寬為gj(X)，ieI(X)，h'X)，j=1,???,l在X處可微，其余不等式約束函數(shù)g(X)，i史I(X)在X處連續(xù)。i引理2(幾何最優(yōu)性條件一必要)：設(shè)XeS是(2)的局部極小點(diǎn)，如果f(X)在X處可微，則必有drVf(X)>0,VdeSFD(X,S)證明利用目標(biāo)函數(shù)f(X)在X+8dk處的一階Taylor展開，序列可行方向的定義及局k部極小點(diǎn)的定義可證。注：該定理也可表述為：XeS是(2)的局部極小點(diǎn)，則{dIdTVf(X)<0}nSFD(X,S)=0。第一個集合表示目標(biāo)函數(shù)在X處的一個下降方向的子集，即該下降方向的子集與序列可行方向無公共元素。定理1：設(shè)XeS是(2)的局部極小點(diǎn)，如果目標(biāo)函數(shù)和所有的約束函數(shù)在X處可微，且SFD(X,S)=LFD(X,S) (3)則必存在訂，ieI和V,jeE使得Vf(X)—]EwVg(X)—EvVh(X)=0(梯度條件)(4a)ii jji=1 j=1wi>0,wig(X)=0，i=1,…,m(互補(bǔ)松弛條件)(4b)該定理的另外一種等價表示(基于該等價表示可以看出K-T最優(yōu)性條件的幾何意義)：定理1'：設(shè)XeS是(2)的局部極小點(diǎn)，如果目標(biāo)函數(shù)和所有的約束函數(shù)在X處可微，且

SFD(x,S)=LFD(x,S)則必存在叫20,ig1(x)和七'jgE使得(5)i jjj=1證明思路:(4a)-(4b)由Kuhn,Tuck(1951)給出，一般稱為K-T條件，因Karush(1939)也類似地考慮了約束優(yōu)化的最優(yōu)性條件，所以也稱K-K-T條件。幾何意義：在局部極小點(diǎn)處，若某種約束規(guī)范成立，則目標(biāo)函數(shù)的梯度向量位于不等式積極約束的梯度向量生成的凸錐與等式約束的梯度向量生成的線性空間的和集。即Vf(x)gcone*g(x),igI(x)}+spanVh((5)i jjj=1證明思路:(4a)-(4b)由Kuhn,Tuck(1951)給出，一般稱為K-T條件，因Karush(1939)也類似地考慮了約束優(yōu)化的最優(yōu)性條件，所以也稱K-K-T條件。幾何意義：在局部極小點(diǎn)處，若某種約束規(guī)范成立，則目標(biāo)函數(shù)的梯度向量位于不等式積極約束的梯度向量生成的凸錐與等式約束的梯度向量生成的線性空間的和集。即Vf(x)gcone*g(x),igI(x)}+spanVh(x),jgE)conetVg(x),igIi(x)}=￡wVg(x)w>0,igI(x)_iiIiwI(x)spanVh(x),jgE}=￡vVh(x)vgR,jwEjj<jwE例3考慮問題min(x-2)2+x212s.t. 氣-x；>0—x+x>0驗證點(diǎn)x⑴=(0,0)T,x(2)=(1,1)T是否滿足K-T條件。記/⑴二(氣—2)"頊g(x)=-x+x2(x-2)-1-「-「，Vg(x)=，Vg(x)=2x1- 2」1-2x21,,先驗證X⑴。在此點(diǎn)，g1(x)>0和g2(x)>0都是起作用約束，目標(biāo)函數(shù)和約束函數(shù)的梯度為「一4「T「一「W(x(1))=_0_，腭3⑴)=_0_，Vg2(x(1))=1—4—w1—w—1=0010210設(shè)Vf(x(2))=-2_2，Vg"x(2))=T_—2_，Vg2(x(2))=「一「1—221-w1—2一w2■-「10=0，2設(shè)得到*=0，w2=2。故x⑵是K-T點(diǎn)。例4考慮問題得到*=一4，w2=0。由于*V0，故x⑴不是K-T點(diǎn)。再驗證x⑵。在此點(diǎn)，gjx)>0和g_(x)>0都是起作用約束梯度為目標(biāo)函數(shù)和約束函數(shù)的min(x—1)2+x1 2目標(biāo)函數(shù)和約束函數(shù)的s.t,—尤］—x2+2>0"2(x—1)「1，Vg(x)="—1_，Vg(x)=611—121W(x)求該問題的K-T點(diǎn)。目標(biāo)函數(shù)和約束函數(shù)的梯度:W(x)—22w".(x)=0i=1K-T條件： wg(x)=0,i=1,2w>0,i=1,22(x—1)+w=01+w—w=0即： w(—x—x+2)=0wx=0w,w>0可得上述方程組的一組解：尤］=1,x2=0,w1=0,w2=1由于w1,w2非負(fù)，因此得到K-T點(diǎn)x=(1,0)T。例5考慮問題min(x—2)2+(x—1)2

S.t.—X2+xNO,1 2—x—x+2Z0.1 2求該問題的K-T點(diǎn)。目標(biāo)函數(shù)和約束函數(shù)的梯度:2(x-2)12(x-1)2目標(biāo)函數(shù)和約束函數(shù)的梯度:2(x-2)12(x-1)2W(x)=—2x11-11-1K-T條件:2(x-2)+2wx+w=0TOC\o"1-5"\h\z11 22(x-l)-w+w=01 2W(72+x)=01 2w(—x—x+2)=01 2\o"CurrentDocument"-X2+X>01 2—x—x+2Z01 2w,w>01 2解得：x=1,x=1,w=2/3,w=2/3o1 2 1 2故X=(l,1)t為K-T點(diǎn)，也是全局最優(yōu)點(diǎn)(？)o注1：此定理中目標(biāo)函數(shù)和所有的約束函數(shù)在元處可微，可放寬為g(x\心⑴在工i連續(xù)，/(X),g(x),ie/(x)；h(x),j=1,，/在x可微。1 j注2：(3)式所給條件稱為約束規(guī)范(約束規(guī)格一ConstraintQualification)0若約束規(guī)范不成立，則(2)的局部極小點(diǎn)不一定是K-T點(diǎn)。例6(Flether,1987)minxX頊21s.t.X3—x>0,X>01 2 2貝0無=(0,0)T為局部極小點(diǎn)，且10W)=0,Vg]⑴=-11易驗證： SFD(x.S)=",0)E>0}11LFD(x,S)={(d.0)\deR)

ii

所以約束規(guī)范(3)不成立。易見不存在嗎20,叫20,使得Vf(x)=訂Vg(x)+wVg(x)1 1 2 2注3:(3)所給約束規(guī)范條件不易直接驗證。人們給出一些更強(qiáng)的，但容易驗證的約束規(guī)范條件。線性函數(shù)約束規(guī)范：所有的約束函數(shù)g,(x)(i=1,?..,m)，h.(x)(j=1,???,/)均為線性函數(shù)。(所以二次規(guī)劃和線性規(guī)劃在任一可行解處約束規(guī)范條件均滿足)線性無關(guān)約束規(guī)范:Vg(x),ieI(x)；Vh(x),j=1,…,l線性無關(guān)，即X處緊約束的梯度向量線性無關(guān)。Mangasarian和Fromowitz(1967)約束規(guī)范：Vh(x),j=1,?,l線性無關(guān)；S*={deRn|dTVg.(x)>0,ieI(x),drVh(x)=0,jeE}=0注4:在不作任何約束規(guī)范的假定下，F(xiàn)ritzJohn(1948)給出如下的必要性條件:定理2(FritzJohn條件)：設(shè)xeS是(2)的局部極小點(diǎn)，且下列條件滿足：f(x),gj(x),ieI(x)在x可微；g(x),iWI(x)在x連續(xù)。和V,jeE，使得ZwVg(x)-Zv和V,jeE，使得ZwVg(x)-ZvVh(x)=0ii jjieI jeEWi20,Wig(x)=0，i=1,…,m.定理2'(FritzJohn條件)：設(shè)xeS是(2)的局部極小點(diǎn)，且下列條件滿足：f(x),gj(x),ieI(x)在x可微；g(x),iWI(x)在x連續(xù)。則存在不全為零的非負(fù)數(shù)w0,w,?,ieI(x)和v.,jeE，使得W0Vf(x)-ZwVg(x)-ZvVh(x)=0ieI(x) jeEwVf(x)一(6a)(6b)(7)當(dāng)W=0時，該條件不能刻畫目標(biāo)函數(shù)和約束函數(shù)的關(guān)系，這是該條件沒有受到重視0的原因。注5:與K-T條件密切相關(guān)的一個函數(shù)是L(x,w,v)=f(x)-Zwg(x)-Zvh(x)ii jj，T j=1該函數(shù)的思想可以追索到Lagrange，故它被稱為Lagrange函數(shù)，w=(*，…,w)t,v=(v1，—,v^)T稱為Lagrange乘子。定義5:稱xeS為(2)的K-T點(diǎn)，如果存在非負(fù)數(shù)叫,ieI(x)，和實數(shù)v.j=1,…,l，使得下式成立：

V/*(x)-￡wVg(x)-￡vVh(x)=0_ii jj則稱可,ieI(無)，v，則稱可,ieI(無)，v，j有了K-T點(diǎn)的定義，=1,…,l為Lagrange(\K-T)乘子。則定理1所表述的一階必要條件可重新表述為：設(shè)在(2)的某可行點(diǎn)處某種約束規(guī)范成立，若其為(2)的局部極小點(diǎn)，則必為(2)的K-T點(diǎn)。求問題(2)的K-T點(diǎn)需求解下列系統(tǒng)：Vf(x)-￡wVg(x)-￡vVh(x)=0 (梯度條件)(8a)ii jji=1 j=1(互補(bǔ)松弛條件)(8b)wg(x)=0, i=1,…,m(互補(bǔ)松弛條件)(8b)(乘子的非負(fù)性)(8c)w>0,i=1,…,m(乘子的非負(fù)性)(8c)g,(x)>0,i=1,…,m，hj(x)=0,j=1,…,l(可行性)(8d)上面討論的都是必要條件，下面討論充分條件。引理3(幾何最優(yōu)性條件一充分)：設(shè)xeS，如果目標(biāo)函數(shù)和約束函數(shù)在x處可微，且dTVf(x)>0, V0。deSFD(x,S)。則x是(2)的嚴(yán)格局部極小點(diǎn)。證明類似引理2。定理3:設(shè)xeS，如果目標(biāo)函數(shù)和約束函數(shù)在x處可微，且dTVf(x)>0, V0。deLFD(x,S)。則x是(2)的嚴(yán)格局部極小點(diǎn)。證明：由引理1知SFD(x,S)cLFD(x,S)，再由引理3知結(jié)論成立。K-T點(diǎn)不一定是局部極小點(diǎn)，但對于凸規(guī)劃而言，K-T點(diǎn)即為全局極小點(diǎn)。定理4(充分條件)：設(shè)xeS是(2)的K-T點(diǎn)，如果(2)為凸規(guī)劃，即f(x),-g,(x)，i=1,…,m是凸函數(shù)，hj(x)，j=1,???,l是線性函數(shù)，則x是(2)的全局極小點(diǎn)。例7見例5。4.3.2二階最優(yōu)性條件設(shè)xeS，如果dTVf(x)>0, V0。deSFD(x,S)，則由引理3知x為(2)的嚴(yán)格局部極小點(diǎn)(因為滿足充分條件)；如果3deSFD(x,S)，使得dTVf(x)<0,由引理2知x不是(2)的局部極小點(diǎn)(因為不滿足必要條件)?？紤]約束優(yōu)化問題(2)，如果在x處一階必要條件滿足，即dTVf(x)>0,VdeSFD(x,S) (9a)3deSFD(x,S)，使得dTVf(x)=0 (9b)此時如何判斷x是否為局部極小點(diǎn)?

所得判斷條件稱為二階最優(yōu)性條件。同討論一階最優(yōu)性條件一樣，需要討論更高一階的可行方向集。設(shè)在(2)中，f(x),gj(x),七(x)，i=1,—,m,j=1,…,l二次連續(xù)可微；下面討論(2)的二階最優(yōu)性條件。定義6:設(shè)x為(2)的K-T點(diǎn)，頃應(yīng)),訶>0為其一對應(yīng)Lagrange乘子，如果dgLFD(x,S)，且wdT^g(x)=0,VigI(x)則稱d是集合S在x處的線性化零約束方向。x處的所有線性化零約束方向的集合記為G(x,w,v)=dgLFD(x,S)IwdTG(x,w,v)=dgLFD(x,S)IwdTVg(x)=0,VigI(xJVg(x)Td=0,igI(x)且w.>0Vg(x)Td>0,igI(x)且訂=0>

i iVh(x)Td=0,i=1,—,l

j J線性化零約束方向引入的原因：(10)(11)如果x為(2)的K-T點(diǎn)，則由(9b)知3dgSFD(x,S)0=dTVf(x)=l^wdTVg(x)+l^vdTVh(x)ii jj(10)(11)i=1 j=1又因為SFD(x,S)cLFD(x,S)，故有dTVg.(x)>0,igI(x),dTVh.(x)=0,jgE此外，由(12)w>0,igI(x), w=0,igI/1(x)(12)將(11)和(12)代入(10)得：wdTVg(x)=0,VigI(x)。此時考慮二階最優(yōu)性條件即要考慮集合 idgSFD(x,S)IwdTVg(x)=0,VigI(x)'ii中的方向，而該集合又包含在G(x,w,v)中，故引入了線性零約束方向。線性零約束方向集的特征：VdgG(x,w,v),有Vf(x)Td=0定義7：設(shè)x為(2)的匕丁點(diǎn)，(w,v),w>0為其一對應(yīng)Lagrange乘子，如果存在序列⑷｝和｛8人｝,其中￥>0，使得對Vk，有x+8dkgS

k'ILwg(x+8dk)+2^vh(x+8dk)=0

ii k jj k且有dk—d和8且有dk—d和8k—0，則稱d是集合S在x處的序列零約束方向。S在x處的所有序列零約束方向的集合記為S(x,w,v)。即

ILwg(x+8dk)TOC\o"1-5"\h\zii kS(無,訂成)S(無,訂成)=<deSFD(x,S)+'^vh(x+8dk)=0i=1 J=<deRn=<deRn3dk,8,s.t.x+8dkeS, and^Lwg(x+8dk)+l^vh(x+8dk)=0>k kwg(x+8dk)+i=1dk—d,ki=1據(jù)定義有:S(x,w,v)cSFD(x,S),G(x,w,v)cLFD(x,S)另外，類似于引理1可證下面引理。引理4：S(x,w,V)cG(x,w,V).引理5：若xeS為(2)的滿足K-T條件的局部極小點(diǎn)，(w,v),w>0為其一對應(yīng)Lagrange乘子。則必有dTV2L(x,w,V)d>0，VdeS(x,w,v)其中Vxx2L(x,w,v)是(2)的Lagrange函數(shù)中固定w,v后所得關(guān)于x的函數(shù)L(x,w,v)的Hesse矩陣在元的值(是一n階方陣)，即V2L(x,w,v)=V2f(x)—LwV2g(x)—￡vV2h(x)i=1 j=1證明利用目標(biāo)函數(shù)L(x,w,v)在x+8dk處的二階Taylor展開，序列零約束方向的定義及局部極小點(diǎn)的定義可證。定理5(二階必要條件)：設(shè)xeS為(2)的局部極小點(diǎn)，(w,v),w>0為其一對應(yīng)Lagrange乘子。如果G(無,w,v)=S(x,w,v) (13)則必有dTV2L(x,w,v)d>0,VdeG(x,w,v)。定理6(二階充分條件)：設(shè)xeS是(2)的匕丁點(diǎn)，(w,v),w>0為其一對應(yīng)Lagrange乘子。如果dTV2L(x,w,v)d>0, V0豐deG(x,w,v)xx則xeS是(2)的嚴(yán)格局部極小點(diǎn)。定義8:設(shè)xeS是(2)的K-T點(diǎn)，(w,v),w>0為其一對應(yīng)Lagrange乘子。稱hj(x)(jeE)，或gj(x)(ieI(x)，且叫>0)為x處的強(qiáng)積極約束。稱A(x,w,v)=E{i|ieI(x),w>0}為x處的強(qiáng)積極約束指標(biāo)集。則有

G(X,w,v)=LFD(X,S)<drVg(X)=0,w>0,iGI(X)drG(X,w,v)=LFD(X,S)<推論1：設(shè)XgS是(2)的K-T點(diǎn)，頃,v),訂>0為其一對應(yīng)Lagrange乘子。如果對一切滿足dTVg(X)=0,w>0,igI(X)drVh(X)=0,jgE的非零方向d都有drV2L(X,w,v)d>0則XgS是(2)的嚴(yán)格局部極小點(diǎn)。令L(x,w,v)=f(x)-2Ewg(x)-￡vh(x)ii jjTOC\o"1-5"\h\zi=1 j=1VL(X,w,v)=Vf(X)-]EwVg(X)-l^vVh(X)=0(14)ii jji=1 j=1V2L(X,w,v)=V2f(X)-]EwV2g(X)-]EvV2h(X)(15)i=1 j=1實質(zhì):(2)的Lagrange函數(shù)中固定乘子后，所得函數(shù)的梯度在點(diǎn)XgS的值即為(14)；所得函數(shù)的Hesse矩陣在點(diǎn)XgS的值即為(15)。從而：?一階必要條件定理1即為：XgS為(2)的局部極小點(diǎn)的必要條件是存在Lagrange乘子(w,v),w>0,使得X為函數(shù)L(x,w,v)的駐點(diǎn)(約束規(guī)范LFD(X,S)=SFD(X,S)成立)；?二階必要條件定理5即為：XgS為(2)的局部極小點(diǎn)的必要條件是存在Lagrange乘子(w,v),w>0,使得X為函數(shù)L(x,w,v)的駐點(diǎn)，同時L(x,w,v)的Hesse矩陣在X的值在集合G(X,w,v)上為半正定矩陣(約束規(guī)范G(x,w,v)=S(x,w,v)成立)；?二階充分條件定理6即為：XGS為(2)的局部極小點(diǎn)的充分條件是存在Lagrange乘子(w,v),w>0,使得X為函數(shù)L(x,w,v)的駐點(diǎn)，同時L(x,w,v)的Hesse矩陣在X的值在集合G(X,w,v)上為正定矩陣。注：設(shè)AGRnxn為對稱矩陣，如果對任意的dGDGRn，有drAd>0則稱矩陣A為集合D上的半正定矩陣，或稱矩陣A在集合D上半正定。如果對任意的0。dgDgRn，有drAd>0。則稱矩陣A為集合D上的正定矩陣，或稱矩陣A在集合D上正定。例8考慮下列非線性規(guī)劃問題minX2+(x-2)2s.t.px2—X=0其中p為實參數(shù)，試討論X=(0,0)t是否為該問題的局部最優(yōu)解。目標(biāo)函數(shù)和約束函數(shù)在X=(0,0)t的梯度：5廠、「0]「/一、I0

'(X)=—4，g(X)=一「0]—V「0]=「0]—4—10設(shè)解得u=4，Lagrange函數(shù)為L(X,v)=X2+(x—2)2—v(px2—X)「2—2pv0]它關(guān)于x的Hesse矩陣是：V2L=X02- 「2—8P 。一在點(diǎn)X處，有V2L- 0 2/…d八求集合G的元素d，令(0,—1)」1=0d1-2」,「d],解得d=01，d1可取任何實數(shù)。這時有「2—8p0]「d]「d]dTV2L(X,v)d=(d,0)一1=(d(2—8p),0)一1X 10 2010=2(1-4p)d2當(dāng)P<1/4時，對每一個向量dgG，有dTV2L(X,v)d>0X因此X是局部最優(yōu)解。當(dāng)P>1/4時，對每一個向量dgG，有dTV2L(X,v)d<0在X不滿足局部最優(yōu)的二階必要條件，因此X不是局部最優(yōu)解。原問題即(3)當(dāng)p=1/4時，利用二階條件給不出結(jié)論，可用其它方法進(jìn)行判斷。這時，為原問題即minx2+(x—2)2,1 。 八s.t.4X2一X=0利用約束條件，從目標(biāo)函數(shù)中消去一個變量，轉(zhuǎn)化為無約束優(yōu)化問題min4x+(x—2)222易知X是局部最優(yōu)解。

§4.4約束優(yōu)化問題的鞍點(diǎn)最優(yōu)性條件1.預(yù)備知識考慮具有一般約束的優(yōu)化問題(2)：(2)minf(x)(2)s.t. g(x)>0h(x)=0其中g(shù)(x)=(g(x),…,g(x))T，h(x)=(h(x),...,h(x))T，則(2)的lagrange函數(shù)為:1 m 1 lL(x,w?v)=f(x)—wtg(x)—vTh(x)，其中weRm,veRi令0(w,v)=in^L(x,w,v)IxeRn^貝0(2)的Lagrange對偶為:max0(w,v)s.t.w>0定義1設(shè)xeRn,weRm,veRi，且w>0,若有L(x,w,v)<L(x,w,v)<L(x,w,v),VxeRn,weRm,veRi且w>0，則稱(x,w,v)為(2)的Lagrange函數(shù)的鞍點(diǎn)。注：（x,w,v）為（2）的Lagrange函數(shù)的鞍點(diǎn)當(dāng)且僅當(dāng)xeargmin{L（x,w,v）IxeRn}，且（w,v）eargmax{L（x,w,v）IweRm,veRi,