第7章优性条件

minf(x

其中决策变量xRn，目标函数f:RnR1。 定义 设函数f:RnR1，xRn，dRn。若存在>0，f(xd)f(x)，(0,则称dfx注 1.1.1fxxdRn。若fx)Td<0，则dfx处的下降方向。f(xd)T

f(x)f(x)Tdo()

f(x)[f(x)Tdo()/ 根据条件f(x)d<0和lim 0知，存在>0，使 代入(1.1.1)并由>0

f(x)d 0，(0,f(xd)f(x)，(0,由此知dfx1.2.1(一阶必要条件)fxx*x*是(UNP)的局部最优解，则fx*0。证明：(反证)假设fx*0。令d*fx*)，则f(x*)Td*f(x*)2由此知f(x*)=0。证毕。满足条件f(x*)=0的点x*称为f(x)的平稳点。定理1.2.1告 1.2.2(一阶充分条件)fxRnx*fx*0x*是(UNP)f(x)f(x*)+f(x*)T(xx*)=f(x*)，x 设f(x)在x*处二阶可微。若x*是(UNP)的局部最优解，则f(x*)任取dRnfxx*fx*处的二阶Taylor展开式并由fx*0 T

f(xd)f(x) df(x)do()f(x) [dTf(x)do()/ f(x*d)f(x*

1dT2f(x*)d2

令

，则利用

o(2

=0得

fx*)d0。最后由d的任意性证得2fx* 设f(x)在x*处二阶可微。若f(x*)=0，2f(x*)正定，则x*是证明：由2fx*正定知2fx*的最小特征值min0xRnxx*fxx*fx*Taylorf(x)f(x*)1(xx*)T2f(x*)(xx*)o(xx*2) *

* 1 o(xx*)

* f(x) x

o(x )f(x)

x2

2

x 利用min0和xx*

o(xx*o(xx*2

=0得，存在>0，使0

x

min

x

1.3.1 minf(x)x3x33x 3x26x解：由f(x) 1=0得x0,2，x1,1，因此f(x)的平稳点23x23 2 0 0 2 2x ，

，11

，

1 0由于f(x) 6x，因 2 0 0f(x) f(x) 6，f(x) f(x) 6

minf( s.t.xxRnSRnfRnR1定义 设集合SRn，xS，dRn。若存在>0，xdS，(0,则称dSxxSD(SxdRn|d是Sx处的可行方向}为SxD(S,x)2.1.2对问题(CNP)xSdRn。若dD(Sx，并且dfx处的下降方向，则称d是(CNP)在x处的可行下降方向。否则，设d*D(Sx*，并且d*fx*处的下降方向，则存在>0x*d*S，f(x*d*)

f(x*)，(0,FxdRn|fx)Td<0}Fxfx2.1.1 定理 设SRn，f(x)在x*S处可微。若x*是(CNP)的局部最优解，F0(x*)D(S,x*)SxRn|Axb1Axb2ARmn，b1RmARpn，b2RpxS

A

b11

A111，b b12 定理 设S{xRn|Axb1,Axb2}，若xS，并且(2.1.1)成立， D(S,x){dRn|Ad0,Ad 证明：设dD(Sx2.1.1知，存在>0，使(0,xdSA(xd)AxAdb11，A(xd)AxAd Axb11Axb2Ad0Ad0 Ad0Ad0Axb11Axb12Axb2知，当0 A(xd)AxAdb1，A(xd)AxAd A2(xd)A2xA2dxdS，于是dD(SxSxRn|gx0,i1,m}I1,m}gxgx),gx))T xSIxiI|gix0}，当iIxgix0Sx处的起作用(积G(x){dRn|g(x)Td>0,iI(x)}，G(x){dRn|g(x)Td0,iI(x) gxAxb1GxdRn|Ad0} 定理 设S{xRn|gi(x)0,i1,,m}，xS。若iI(x)时gi(x)在x处可微iI\Ix)gix)x处连续，则G0xD(SxG0x)。当gix)(iI)为线性函数时，D(Sx)G0x证明：设dGx。当iIx，由gx)Td>0知，dgix处的上升方向，于是存在0使(0,1

gi(xd)gi(x)0，iI(

当iIIxgix)0gixx处连续知，存在2>0，使(0,2gi(xd)0，iI\I( 令min{1,2，则当(0,时，(2.1.1)和(2.1.2)xdS。于是dD(S,x。设dD(Sx，则存在>0，使(0,xdSgixd0(i1,mg(xd)g(x)g(x)T 0()g(x)Tdo() 即gx)Tdo()0。令0得gx)Td0。由此得dG0x D(SxdRn|Ad0Gx 推论 F0(x*)G0(x*)gx)(iIFx*Gx* 定义 设集合SRn，xS，dRn。若存在序列{},{dk}：0,0,dkd， 则称dSx

xkdkS，k1,SD(SxdRn|d是Sx处的序列可行方向}为Sx

SD(S,xD(SxSDSx取k2kdkd注2.2.3 设x*S。若x*是(CNP)的局部最优解，则(CNP)在x*处不存在序列可行的下降方向。否则，设d是序列可行的下降方向。由dSD(S,x*)知，存在{k},{dk}：k0,k0,dkd使x*kdkS，k1, 由d是下降方向知，存在0故由dkd得，k

f(x*d)f(x*),(0,于是由k0,k0

f(x*dk)f(x*),(0,f(x*kdk)f(x*)，k充分大 因为x*kdkx*，故根据(2.2.1)和(2.2.2)知x*不是(CNP)的局部最优解， 定理2.2.1 设x*S，f在x*处可微。若x*是(CNP)的局部最优解，则F0(x*)SD(S,x*)。现在考虑S{xRn|gi(x)0,i1,,m,hj(x)0,j1,,l}时的序列可行方向集。J1,l}hxhx),hx))TxSHxdRn|hx)Td=0 显然，当hxAxb2HxdRn|Ad0} 2.2.2SxRn|gix0,i1,mhjx0,j1,lxSiIx时gixxjJhjx)x处可微，则SD(S,x)G0xH0xgix)(iI)和hjxjJD(S,xSDS,x)G0xH0x。证明：设dSD(Sx，则存在{k},{dk}k0,k0dkdxkdkS，k1,

(x

对任意的iIx)，由Taylorg(xd

)g(x)g(x)Td

o(d

)

g(x)Tdk

k 即g(x)Tdk dk0。令k得g(x)Td0。由此得d jJ，由Taylorh(xdk)h(x)h(x)Tdko(dk)h(x)Tdk k

dk即hj

dk0。令k得hx)Td0。由此得dHx) )于是dG0xH0xG0(x)H0(x)D(S,x)SD(S,x)G0(x)H0(定理 设S{xRn|gi(x)0,i1,,m,hj(x)0,j1,,l}，xS。若iI(x)gixxiIIxgixxjJhjxxhjx),jJ无关，则G0xH0xSD(Sx*证明：设dG0xH0xx(0)x，x(0) φφR ())，则φ在(0,0)连续可微，并()()由隐函数存在定理，方程φ(y,0存在连续可微解yy([0,0]，使y(0)0φ(y,(0,[0,0]hxdhx)y())0,[0,0] 上式两边对求导，并代入=0，得hx)T(dhxy(0))0，由dHx)得0h(x)Th(x)y(0)0，再由h(x),jJ线性无关即h(x)秩得y(0)0jx(xdhxy([0,0，则xx([0,0是可微曲线，x(0)xx(0)dhxy(0)d，因此(2.2.3)成立。下面证明由(2.2.5)知hx(0[0,0。当iIx时，由(2.2.3)和dG0x

gi(x(0))Tx(0)gi(x)Td因此[0,0gix(gix(0gix0。当iIIxgix(0gix0（2）再证明dSD(S,x取(0,0dkx(kx，则由(2.2.4)xdkx(S，再由(2.2.3) k由此得dSD(S,x

dkx(k)xx(k)x(0)x(0) 2.2.4SxRn|gix0i1,mhjx0,j1,l}，x*S是(CNP)的局部最fxx*处可微，iIx*gixx*处可微，iIIx*gixx*jJhjxx* SFx*Gx*Hx* 若hjx*jJ F(x*)G(x*)H(x*) minf(

gi(x)0,i1,,hj(x)0,j1,,

2.3.1(FritzJohn条件)x*Sfx)x*iIx*)gixx*处可微，在不全为零的uuiIx*)和v,j

uigi(x*)vjhj(x*)

0,ui0,iI(hjx*jJ线性相关，则存在不全为零的vj,jJvjhjx*)0。令u00,ui0iIx*，则(2.3.1)若hjx*jJ2.2.4/(2)f(x*)Td0,gi(x*)Td0,iI(x*),hj(x*)Td0,j

f(x*)Td0,gi(x*)Td0,iI(x*),hj(x*)Td0,j4.3.3(Mortzkin定理)知，存在不全为零的u0uiiIx*和vj,jJ，使(2.3.1)成2.3.1书P2107.2.1（FJ点）2.3.2书P211FritzJohn条件中，不排除目标函数梯度的系数为零的情形（这时目标函数的信息从(2.3.1)这，为保证该系数不为零，需对可行域施加一定的约束规格，由此得到(CNP1)的K-T条件。 x*SS的正则点，即gx*iIx*hx*),jJ 2.3.2(Kuhn-Tucker条件)x*Sfxx*iIx*)gixx*处可微，约束规格成立，则存在uiIx*)和v,j

uigi(x*)

vjhj(x*)

)f(x*)Td0,gi(x*)Td0,iI(x*),hj(x*)Td0,j

f(x*)Td0,g(x*)Td0,iI(x*),h(x*)Td0,j 4.3.3(Mortzkin定理)知，存在uiiIx*和vj,jJ，使(2.3.2)第一式两边除以u0即得到(2.3.2)。注2.3.1 事实上，在约束规格下，有SD(S,x)G0(x)H0(x)。当g(iI)在x*处可微时，(2.3.2)可写成if(x*)ug(x*)vh(x*)iug(xug(x*) 0,i iu0,i可行解称为K-T点。例 书P212例7.2.3(验证K-T点，用条件例 书P214例7.2.3(求K-T点，用条件f(x*)ug(x*)，u0,iI( 即fx*可表示为gix*iIx*gxgx),gx))Thxhx),hx))Tuu,u)Tvv,v)T LxuvfxuTgxvThx称为(CNP)Lagrange函数，这时，(2.3.3)uTg(x*)u

其中u和vLagrangej 2.4.1x*SxRn|gix0,iIhjx0iJfxgixiIx*))和hx)(jJ)x*是j 证明x*是(CNP1)K-T点知，存在uiIx*和v,jJ，使 xSf(x)f(x*)f(x*)T(xx*)0gi(x)gi(x*)gi(x*)T(xx*)gi(x*)T(xx*)，iI(于是由

0hj(x)hj(x*)hj(x*)T(xx*)hj(x*)T(xx*)

jf(x)f(x*)f(x*)T(xx*)ug(x*)T(xx*)vh(x*)T(x

=f(x*)[f(x*)x*是(CNP1)的最优解。证毕。2.4.1书P222例7.2.6。

uigi(x*)vjhj(x*)]T(xx*)=f(**2.5二阶最优性条件对(CNP1)K-TxSLagrange乘子u和vG1(x)dRngi(x)Td0,iI(x):ui0,gi(x)Td0,iI(x):ui G(x)dRng(x)Td0,iI(x):u0,g(x)Td0,iI(x):u j定理 设x*S，f(x)、gi(x)(iI)和h(x)(jJ)在x*处具有二阶连续偏导数。若x*j(CNP1)x*SLagrange乘子u和v，使(CNP1)K-T条件成立，dT2L(x*,u,v)d0,dG(x*)H( j2.5.2x*SfxgixiI)hxjJ)x*x*j(CNP1)SLagrange乘子u和v，使(CNP1)K-T条件成立，dT2L(x*,u,v)d0,dG(x*)H( j定理 设x*S，f(x)、gi(x)(iI)和h(x)(jJ)在x*处具有二阶连续偏导数。若x*jdT2L(x*,u,v)d0,dG(x*)H(x*) 2.5.1书P227例7.2.7例 书P230例*2.6二次规划问题的最优性条件minf(x)1xTHxcT2

Ax1A2x1(a,,a)TRmn，

SxRn|Axb1Axb2}x*S是(QP)K-Tu和vLagrangeA

A b11

A111，b ，A11xb，A12x b12ii

0dRnA11d0,(u