最優(yōu)化理論 第九章 約束優(yōu)化問題的最優(yōu)性條件

從本章起，將用幾章的內(nèi)容來討論約束最優(yōu)化問題.我們考察的約束最優(yōu)化問題的一般形式為s.t.

f(x)

(9.0.1)c(x)0,iI{m ,m ,,m}i e1 e2I(x){i|ci(x)0,iI}EI(x為約束最優(yōu)化問題(9.0.1)xX處的積極約束指標(biāo)集，積極約束又稱為有效約束、起作用的約束或緊約束(activeconstraintsorbindingconstraints).x*EI(x*)，則約束最優(yōu)化問題(9.0.1)可以轉(zhuǎn)化為等式約束最優(yōu)化問題minf(x)s.t.

ci(x)0,iEI(x*)

(9.0.2)§9.1一階最優(yōu)性條件記i e i D{xRn|c(x)0,i1,2,,m;c(x)i e i

.x*DdRn是一個非零向量.如果存在0，對任意t[0,]，都有x*tdD，則稱dx*x*FD(x*D.x*D.若dRn滿足Tc(x*)0,iE，dTc(x*)0,iI(x*)，i id為點(diǎn)x*處的線性化可行方向，點(diǎn)x*處的所有線性化可行方向的集合記為LFD(x*,D).kx*D.若存在趨向于d的序列{dk和趨向于零的正數(shù)列{}，使對每個k，都有kkx*dkD，k則稱dx*x*SFD(x*D.引理9.1.1 設(shè)x*D且所有約束函數(shù)都在x*處均可微，則有FD(x*,D)SFD(x*,D)LFD(x*,D). (9.1.1)證如果dFD(x*D)0t[0,x*tdDk12,，則顯然有kk x*dkDdkd(k(k，dSFD(x*DFD(x*DSFD(x*Dk

dkd，kdSFDx*D，由序列可行方向的定義可知，存在序列{dk和正數(shù)列{}，k滿足k x*dkDdkd(k(kk x*處均可微，故有0c(x*dk)c(x*)Tdko(||

dk||),

iE，i k k i k0c(x*dk)c(x*)Tdko(||dk||),

iI(x*)，i k k i k在上兩式的左右兩端除以k，并令k，可得c(x*)0,iE，dTc(x*)0,iI(x*)，i idLFD(x*DSFD(x*DLFD(x*D.引理9.1.2 設(shè)x*D是約束最優(yōu)化問題(9.0.1)的局部極小點(diǎn)，若f(x)和ci(x)(i12,mx*處可微，則對任意dSFD(x*D，都有f(x*)Td0.k證任給dSFD(x*D{dk和正數(shù)列{}，k滿足k x*dkDdkd(k(kk kx*dkx*(kx*是局部極小點(diǎn)，故對充分大的k，有kkk k f(x*f(x*dkf(x*f(x*)Tdko(||dk||)，在上式的左右兩端除以，并令k，可得f(x*)Tdkk k 注引理9.1.2表明在約束最優(yōu)化問題(9.0.1是目標(biāo)函數(shù)的下降方向.9.1.3（Karush-Kuhn-Tucker定理）x*D是約束最優(yōu)化問題(9.0.1)的局部極小點(diǎn)，f(x和ci(x)(i12,mx*處可微.若SFD(x*,D)LFD(x*,D)， (9.1.2)m則存在i*(i12,m，滿足mf()i*i()， 9.1.3)i1ci(x*)0,

iE， (9.1.4)i*0,

ci(x*)0,i*ci(x*)0,

iI. (9.1.5)9.1.2及條件(9.1.2)可知，對任意dLFD(x*D，有f(x*)Td0.而由LFD(x*,D)的定義又知，dTc(x*)0,iE，dTc(x*)0,iI(x*).i i這表明不等式組

iTc(x*)0,i

iE，idTc(x*)0,iEiidTc(x*)0,iI(x*)，if(x*)Td0Farkas1*0(iE和2*0(iE以及0(iI(x，i i i使得f()1*2c()*c()，i i i i iE x*)再令*1*2*(iE，*0(iI\I(x*x*D，我們得到等式i i i i(9.1.3)(9.1.4)和(9.1.5).m注（1）稱mL(x,)f(x)Tc(x)f(x)c(x)ii為稱為ii

i1（2）(9.1.3)(9.1.5)通常稱為約束最優(yōu)化問題(9.0.1)的K-K-T（Karush-Kuhn-Tucker條件9.1.)-(9.5)的點(diǎn)*DKKT91.）條件(9.1.2)稱為約束規(guī)范性條件，簡稱約束規(guī)范(ConstraintQualification).當(dāng)條件(9.1.2)不成立時，局部極小點(diǎn)不一定是K-K-T點(diǎn).例如，考察

minx11 1 s.t.c(x)x3xc2(x)x21 1

0,(x*10)T不可能是1 2的線性組合，更不用說非負(fù)線性組合. 究其原因，原來D)，Dxx|c(xx3x0c(xx

0}.1 2 1 1 2 2 2如果不要求約束規(guī)范性條件(9.1.2Fritz-John設(shè)f(x和ci(x)(i12,mx*x*D是約束最優(yōu)化問題(9.0.1)的m局部極小點(diǎn)，則必存在0*0i*Ri12,m，使得m0*f()i*i()0，i1*0,*c(x*)0,iI;(*)20.i i i iiI如果00Fritz-John點(diǎn)不是極小點(diǎn)的可能性增大，這也是Fritz-JohnKarush-Kuhn-Tucker條件使用廣泛的原因.Lagrange對于等式約束情形min{f(x|c(x)0}，設(shè)x*和*是其最優(yōu)解及對應(yīng)的乘子.下面考察這個約束優(yōu)化問題的擾動問題min{f(x|c(x)}，假設(shè)其最優(yōu)解及其乘子x*()和*(x*(0)x*，*(0)*.由于c(x*())(9.1.3),我們有dx*()ddx*()ddx*()df(x*())d

(x*)

0

*c(x*)

，0*dd

c(x*())

*.對于等式約束情形min{f

(x|c(x0，如果c(x*0，則對充分小的，也有c(x*))，這時，由上面的討論可知

df(x*())d

*；如果c(x*)0，這時，x*是無約束最優(yōu)化問題minf(x的一個局部極小點(diǎn)，故對充分小的有x*()x*，因xRn此，仍有

df(x*())d

f(x*)T

dx*ddx*d

0*.線性約束規(guī)范，LCQ）若所有的ci(x)(iEI(x*都是線性函數(shù)，則約束規(guī)范條件(9.1.2)成立.k證對任意dLFD(x*D)，取dkd，1k2k

，由于ci(x)(iEI(x*是線性x*D且dTc(x*)0,iE，dTc(x*)0,iI(x*)，i i故有ci(x*k

i k dk)c(x*)c(x*)Td0，ii k ci(x*k

dk)c(x*)c(x*)Td0，iI(x*).i k 而對iI\I(x*c(x*)0及0kc(x*dki k i k i kk即有x*dkD，這表明dSFD(x*DLFD(x*DSFD(x*D.再結(jié)合(9.1.1)可知(9.1.2)成立.k約束規(guī)范，MFCQ）如果（1）ci(x*)(iE線性無關(guān)，i （2）S*ddTc(x*0,iE;dTc(x*0,iI(x*)i (9.1.2)成立.i 證設(shè)dSd(i12,ni

1是子空間ed}e1的正交補(bǔ)中的標(biāo)準(zhǔn)正交基.由于dS，故d與c(x*)(iE)正交，因而上述生成子空間的維數(shù)為me1. 考慮下面以為參數(shù)的非線性方程組1ci(x)0,dT(xx*)0,

（9.1.6）i edT(xx*)0,它將確定以xx(.xx*處，非線性方程組（9.1.6）的0x*是方程組的解.根據(jù)隱函數(shù)定理，對充分小，必存x()且滿足x()d/||d||2. 事實(shí)上，將方程組確定的隱函數(shù)對求導(dǎo)，有0c(x)Tx()0, i edTx()0,

1,

（9.1.7）i edTx()1,令0，則方程組(9.1.7)d||d||2是其解，故有x()0d/||d||2.ix(是由方程組(9.1.6)ci(x())0(iE)iI(x*時，S的定義，有dTc(x*0，故當(dāng)充分小時，有ii i i i i c(x())c(x(c(x*)c(x(c(x(0))c(x())Tx()i i i i i i i c(x())Tx()c(x*)Tx(0)c(x*)Td/||d||2i i 故ci(x(0；當(dāng)iI\I(x*時，由于ci(x*0，故當(dāng)充分小時，有ci(x(0.因此當(dāng)x(D.k k 對充分小的0，取dkx(x*k1k k k k dk[x()x*]/x'(0)d/||d||2(k k k x*dkx(DSFD(x*D定義知d||d||2SFD(x*Dk 故dSFD(x*D.SSFD(x*D.SFD(x*D是閉集，有cl(S)SFD(x*,D).由于i cl(S)ddTc(x*)0,iE;dTc(x*)0,iI(x*)LFD(x*,D)i 故等式(9.1.2)成立.9.1.6（線性無關(guān)約束規(guī)范，LICQ）x*處ci(x*)(iEI(x*線性無關(guān)，則約束規(guī)范條件(9.1.2)成立.I(x*9.1.5可知結(jié)論成立.I(x*EI(x*12,k.jI(x*，由于ci(x*)(i12,k線性無關(guān)，記a1,aj1aj1,ak是span{c1(x*),,cj1(x*),cj1(x*),,ck(x*)}

(9.1.8)的一組標(biāo)準(zhǔn)正交基.dc(x*c(x*)Taa

，則d與ai

j)均正交，從而與生成空間(9.1.8)j正交，且有

j ii iijdTc(x*)dT(dc(x*)Taa)||d||2.jjdd||d||2，則有j

j iiijj j

1，c(x*)Td

0i

j). (9.1.9)i jI(x*，均可構(gòu)造出具有性質(zhì)(9.1.9)的dji S9.1.5可知結(jié)論成立.

ddjjI(x)

，易見dS，9.1.7（一階充分性條件）x*Df(x和ci(xx*處都可微，且對任意dSFD(x*D)，都有dTf(x*)0， （9.1.10）x*是約束最優(yōu)化問題(9.0.1)的嚴(yán)格局部極小點(diǎn).x*xkDxkx*(kxkx*(k12,，且滿足f(xk)f(x*). （9.1.11）令xx*kkd ||xkx*||,k||xkk

x*||，limdkd（dSFD(x*D.（9.1.11）kLagrange中值定理，對任意k，有f(xk)T(xkx*)0，xkxkx*確定的線段上，進(jìn)而對任意k，有f(x

(xkx*)

0，k，即得dTf(x*0，這與條件（9.1.10）矛盾，矛盾表明定理結(jié)論成立.§9.2二階最優(yōu)性條件若對任意0dSFD(x*D，都有dTf(x*09.1.7x*是約束最優(yōu)化問題(9.0.1)0dSFD(x*DdTf(x*0dx*x*不是極小點(diǎn).但若這兩種情形都不出現(xiàn)，即對任意dSFD(x*D)，都有dTf(x*)0， （9.2.1）且存在0dSFD(x*D，使得dTf(x*0， （9.2.2）9.1.3x*K-K-T點(diǎn).記*Lagrange乘子，顯然對使（9.2.2）成立的d，有mdTf(x*)*dTc(x*)0.mi ii1SFD(x*DLFD(x*D知，dLFD(x*DLFD(x*D的定義和上式可得，對任意iI(x*，有*dTc(x*)0.i ix*是K-K-T*是相應(yīng)的LagrangedLFD(x*D滿足：對任意iI(x*，有*dTc(x*)0，則稱dx*x*處所有線性i i化零約束方向的集合記為G(x**).x*Lagrange乘子*唯一，則簡記為G(x*.kx*是K-K-T點(diǎn)，*是相應(yīng)的Lagrange{dk和正數(shù)列{}，k使得x*

dkD，*c(x*

dk)0，mk i i kmi1k且有dkd(k0(kdx*x*處所S(x**.k由定義顯然有G(x*,*)LFD(x*,D)，S(x*,*)SFD(x*,D).SFD(x*DLFD(x*DS(x**G(x**.kk i 事實(shí)上，任取dS(x**)S(x**)的定義知，存在序列{dk和正數(shù)列{}，使得dkd(k0(kx*dkkk i ci(x*k

dk)0，iEI(x*)；c(x*

dk)0，iI(x*)\I(x*)，iiI(x*|*0.i當(dāng)iEIx*時，有0c(x*dk)c(x*)c(x*)Tdk(dk

)c(x*)Tdk(dk)，i k i k i k k i k兩邊除，并令k，得dTc(x*)0.k i當(dāng)iI(x*)\Ix*時，有0c(x*dk)c(x*)Tdk(dk)，i k k i ki類似可得dTc(x*)0，故有dG(x**S(x**)G(x**.i定理9.2.1（二階必要條件）x*是約束最優(yōu)化問題(9.0.1)*是對應(yīng)LagrangedS(x**，必有dT2L(x*,*)d0. （9.2.3）證給dS(x*,若d0則然成. 故妨設(shè)d0由Sk的定義知，存在向量序列{dk和正數(shù)列{}，使得kx*

dkD，*c(x*

dk)0，mk i i kmi1k且有dkd(k0(k，因此，有kk f(x*dk)L(x*dk,k L(x*,*)L(x*,*)Tdk12dT2L(x*,*)dko(2)k 2kk kf(x*)12dT2L(x*,*)dko(2)， （9.2.4）2kk kx*是(9.0.1)k

f(x*dkf(x*.從而由(9.2.4)，k有k12dT2L(x*,*)dko(2)0，2kk kk不等號兩邊除以2并令k，可得到不等式(9.2.3).k9.2.2（二階充分條件）x*是約束最優(yōu)化問題(9.0.1)K-K-T*是對Lagrange乘子.如果對任意0dG(x**，都有x*是嚴(yán)格局部極小點(diǎn).

dT2L(x*,*)d0， （9.2.5）證假設(shè)x*是嚴(yán)格局部極小點(diǎn)，則存在xkDxkxf(xkf(x*，.xkx*

d(k)，9.1.7的證明看到，

dTf(x*)0，dS(x*,D).而由dS(x*DL(x*D)，我們有ddf(x*)*dc(x*)0.T Ti ii1i dTf(x*0且對任意iI(x*有*dTc(x*)0，即dG(x**).而f(xkf(x*i L(x*,*)L(xk,*)L(x*,*)12dT2L(x*,*)dko(2)，2kk kk其中||xkx*||.由此可得dT2L(x**)d0，與不等式(9.2.5)x*是約束最優(yōu)化問題(9.0.1)的嚴(yán)格局部極小點(diǎn).k的邏輯蘊(yùn)含關(guān)系.（9.1.0dSFD(,D)dTf()0，這時一階充分條件無效，可以轉(zhuǎn)而考察二階充分條件.§9.3 凸規(guī)劃問題化問題minf(x)為凸規(guī)劃問題. 特別地，約束最優(yōu)化問題xD