第4章 最优性条件

第4章最优性条件§4.1最优性条件的预备知识极小点的定义无约束问题：1 (1)定义1(全局极小点)若存在XGRn使得f(X)Zf(x), VxgRn则称X为问题(1)的全局极小点。如果有f(x)>f(X), VxgRn,X丰X则称X为问题(1)的严格全局极小点。定义2(局部极小点)设XGRn，如果存在5>0使得f(x)>f(X), VxgN5(X)则称X为问题(1)的局部极小点。如果有f(X)>f(X), VxgN5(X)/{X}则称X为问题(1)的严格局部极小点。约束问题：minf(x) (2)s.t.g(x)>0,i=1,…,mh(x)=0,j=1,…,l其中f(x),g,(x),h/(x)都是定义在Rn上的实值连续函数，且至少有一个是非线性的。称f(x)为目标函数，g,(x)为不等式约束函数，七(x)为等式约束函数。(i)如果m=0,称(2)为等式约束优化问题；如果l=0,称(2)为不等式约束优化问题；如果g,(x)(i=1,…,m),h\x)(j=1,...,l)都为线性函数，f(x)是二次函数，则称(2)为二次规划问题。若xgRn满足(2)的所有约束条件，称X为(2)的可行点(或可行解)。可行集(可行域)：S=g.(x)>0,i=1,...,m,可行集(可行域)：S=Xhj(x)>0,j=1,・・・,l.定义3(全局极小点)设XgS使得f(x)>f(X), VxgS成立，则称x为问题(2)的全局极小点。如果有f(x)>f(x), VxgS,x。x

成立，则称无为问题(2)的严格全局极小点。定义4(局部极小点)设%eS，如果存在5>0使得f⑴>f(%), VxeN5(%)AS成立，则称％为问题(2)的局部极小点。如果有f(%)>f(%), V%eN5(%)AS,%。%成立，则称%为问题(2)1的严格局部极小点。内容安排■求全局极小点一般来说相当困难。实际上可行的只是求一个局部(或严格局部)极小点。故本课程后面所指极小点，通常指求局部极小点。■仅当问题为凸规划(即目标函数f(%)为凸函数，不等式约束函数一g(%),i='•••,m为凸函数，等式约束函数hj(%),j=1,…,l为线性函数)时，局部极小点才是全局极小点。■按定义验证最优解是不可能的。因此有必要给出只依赖于在％处目标函数和约束函数信息的、且与定义等价的条件。这样的条件称其为最优性条件，它们是各种基于梯度算法的理论基础。§4.2无约束问题的最优性条件Max单变量优化问题必要f(%)=0Max单变量优化问题必要f(%)=0充分*3f(%)=0f(%)凹必要f(%)=0f(%)<0充分*4f(%)=0以%)<0多变量优化问题Vf(%)=0f(%)凹V2f(%)半负定V2f(%)负定考虑无约束问题(1)，回忆当%eR时，即单变量函数极值问题的最优性条件：必要条件：若%eR且f(%)在％处取到极值，如果f(%)在％可微，则％为f(%)的驻点，即满足f'(%)=0。充分条件：若%eR且f(%)在%处可微，如果f,(%)=0且f"(%)>0，则f(%)在%处取到极小值；如果f,(%)=0且f,(%)<0，则f(%)在元处取到极大值。Min一阶条件必要二阶条件充分*2必要充分知单变量优化问题f(%)=0f(%)=0f(%)凸f(%)=0f(%)>0f(元)=0f(%)>0多变量优化问题Vf(%)=0*1：%为全局极小点；Vf(%)=0 Vf(%)=0f⑴凸 V2f(%)半正定*2：%为严格局部极小点。Vf(%)=0V2f(%)正定一阶条件二阶条件

*3：元为全局极大点； *4：x为严格局部极大点。定理1(一阶必要条件):设无eRn为函数f(x)在Rn的局部极小点，且f(x)在x可微，则W(X)=0。证明利用§4.0中的定理1可证。几何解释:若X为局部极小点，则f(x)在X处不能有下降方向。从而，当Nf(x)。0时，-Vf(x)为f(x)在x处的一个下降方向，故若xeRn为函数f(x)在Rn的极值点，必有Nf(x)=0。定理2(二阶必要条件)：设xeRn为函数f(x)在Rn的局部极小点，且f(x)在x二阶可微，则有Vf(x)=0，且V2f(x)半正定证明：利用f(x)在x的二阶Taylor展开及局部极小点的定义可得。几何解释：由x为局部极小点及Vf(x)=0所确定。定理3(二阶充分条件)：设f(x)是定义在Rn上的二次可微函数，如果Vf(x)=0，且V2f(x)正定，则x为函数f(x)在Rn的严格局部极小点。证明利用f(x)在x的二阶Taylor展开及正定矩阵的定义可得。注：满足Vf(x)=0的点称为f(x)的平稳点或驻点。驻点可能是极大值点，也可能是极小值点，也可能不是极值点。但若目标函数为凸函数，则驻点就是全局极小值点；若目标函数为凹函数，则驻点就是全局极大值点。定理4(凸充分性定理)：设f(x)是定义在Rn上的凸函数，如果Vf(x)=0，则x为函数f(x)在Rn上的全局极小点。(一阶必要条件+凸性)证明利用可微凸函数的一阶判别条件和Vf(x)=0易证。例：利用极值条件求解minf(x)=xeR2解：fdx1f=x2-2x解：fdx1dx 2 22令Vf(x)=0，即x2—1=0，x2—2x=0。得到驻点：x(1)=T，x(2)=，T，x(3)=，"—1-，x(4)=，「-「02022x0Hesse矩阵：V2f(x)= 10 2x—2在点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))不定，根据定理2,X(1),X(4)不是极小点；V2f(X(3))负定，X(3)是极大点；V2f(X(2))正定，根据定理3,X(2)是局部极小点。§4.3约束问题的极值条件4.3.1—阶最优性条件引入记号：E={1,…,/}――等式约束指标集1={1,…,m} 不等式约束指标集定义1:对(2)的任何可行解~eS，若g(~)=0,ieI，称第i个不等式约束在~处是i紧的，称集合I(~)={iIgj(~)=0,ieI}为不等式约束中在~处的紧约束指标集。称A(~)=EUI(~)是在~处的积极集合(有效约束指标集，或紧约束指标集)。可行集上一点是否为局部极小点，取决于目标函数在该点以及附近其它可行点上的值。可行方向在推导最优性条件中起十分重要的作用。各种可行方向的定义：定义2:设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在点X=(0,0)T处的可行方向集，则0FD(X,S)=01FD(X,S)={(d,d)IdeR,d>0}2 12 1 2定义3:设XeS，deRn，如果dTVh(X)=0,jeE；dVg.(X)>0,ieI(X)则称d是集合S在x处的线性化可行方向。S在x处的线性化可行方向的集合记为LFD(X,S)。

定义4:设元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注：可行方向为几何概念，线性化可行方向为代数概念，序列可行方向是基于极限定义的几何概念。例2S={xeR21X2=X]2}，取X=(0,0)丁，则FD(X,S)=0LFD(X,S)={(d,0)1deR}SFD(X,S)={(d,0)1deR}上述定义的三个可行方向集有如下关系：引理1设XeS，如果所有的约束函数在X处可微，则有FD(X,S)cSFD(X,S)cLFD(X,S)。注：该结论条件可以放宽为gj(X)，ieI(X)，h'X)，j=1,・・・,l在X处可微，其余不等式约束函数g(X)，i史I(X)在X处连续。i引理2(几何最优性条件一必要)：设XeS是(2)的局部极小点，如果f(X)在X处可微，则必有drVf(X)>0,VdeSFD(X,S)证明利用目标函数f(X)在X+8dk处的一阶Taylor展开，序列可行方向的定义及局k部极小点的定义可证。注：该定理也可表述为：XeS是(2)的局部极小点，则{dIdTVf(X)<0}nSFD(X,S)=0。第一个集合表示目标函数在X处的一个下降方向的子集，即该下降方向的子集与序列可行方向无公共元素。定理1：设XeS是(2)的局部极小点，如果目标函数和所有的约束函数在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(互补松弛条件)(4b)该定理的另外一种等价表示(基于该等价表示可以看出K-T最优性条件的几何意义)：定理1'：设XeS是(2)的局部极小点，如果目标函数和所有的约束函数在X处可微，且

SFD(x,S)=LFD(x,S)则必存在叫20,ig1(x)和七'jgE使得(5)i jjj=1证明思路:(4a)-(4b)由Kuhn,Tuck(1951)给出，一般称为K-T条件，因Karush(1939)也类似地考虑了约束优化的最优性条件，所以也称K-K-T条件。几何意义：在局部极小点处，若某种约束规范成立，则目标函数的梯度向量位于不等式积极约束的梯度向量生成的凸锥与等式约束的梯度向量生成的线性空间的和集。即Vf(x)gcone*g(x),igI(x)}+spanVh((5)i jjj=1证明思路:(4a)-(4b)由Kuhn,Tuck(1951)给出，一般称为K-T条件，因Karush(1939)也类似地考虑了约束优化的最优性条件，所以也称K-K-T条件。几何意义：在局部极小点处，若某种约束规范成立，则目标函数的梯度向量位于不等式积极约束的梯度向量生成的凸锥与等式约束的梯度向量生成的线性空间的和集。即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验证点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⑴。在此点，g1(x)>0和g2(x)>0都是起作用约束，目标函数和约束函数的梯度为「一4「T「一「W(x(1))=_0_，腭3⑴)=_0_，Vg2(x(1))=1—4—w1—w—1=0010210设Vf(x(2))=-2_2，Vg"x(2))=T_—2_，Vg2(x(2))=「一「1—221-w1—2一w2■-「10=0，2设得到*=0，w2=2。故x⑵是K-T点。例4考虑问题得到*=一4，w2=0。由于*V0，故x⑴不是K-T点。再验证x⑵。在此点，gjx)>0和g_(x)>0都是起作用约束梯度为目标函数和约束函数的min(x—1)2+x1 2目标函数和约束函数的s.t,—尤］—x2+2>0"2(x—1)「1，Vg(x)="—1_，Vg(x)=611—121W(x)求该问题的K-T点。目标函数和约束函数的梯度: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非负，因此得到K-T点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点。目标函数和约束函数的梯度:2(x-2)12(x-1)2目标函数和约束函数的梯度: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点，也是全局最优点(？)o注1：此定理中目标函数和所有的约束函数在元处可微，可放宽为g(x\心⑴在工i连续，/(X),g(x),ie/(x)；h(x),j=1,，/在x可微。1 j注2：(3)式所给条件称为约束规范(约束规格一ConstraintQualification)0若约束规范不成立，则(2)的局部极小点不一定是K-T点。例6(Flether,1987)minxX顼21s.t.X3—x>0,X>01 2 2贝0无=(0,0)T为局部极小点，且10W)=0,Vg]⑴=-11易验证： SFD(x.S)=",0)E>0}11LFD(x,S)={(d.0)\deR)

ii

所以约束规范(3)不成立。易见不存在吗20,叫20,使得Vf(x)=订Vg(x)+wVg(x)1 1 2 2注3:(3)所给约束规范条件不易直接验证。人们给出一些更强的，但容易验证的约束规范条件。线性函数约束规范：所有的约束函数g,(x)(i=1,・..,m)，h.(x)(j=1,•••,/)均为线性函数。(所以二次规划和线性规划在任一可行解处约束规范条件均满足)线性无关约束规范:Vg(x),ieI(x)；Vh(x),j=1,…,l线性无关，即X处紧约束的梯度向量线性无关。Mangasarian和Fromowitz(1967)约束规范：Vh(x),j=1,•,l线性无关；S*={deRn|dTVg.(x)>0,ieI(x),drVh(x)=0,jeE}=0注4:在不作任何约束规范的假定下，FritzJohn(1948)给出如下的必要性条件:定理2(FritzJohn条件)：设xeS是(2)的局部极小点，且下列条件满足：f(x),gj(x),ieI(x)在x可微；g(x),iWI(x)在x连续。和V,jeE，使得ZwVg(x)-Zv和V,jeE，使得ZwVg(x)-ZvVh(x)=0ii jjieI jeEWi20,Wig(x)=0，i=1,…,m.定理2'(FritzJohn条件)：设xeS是(2)的局部极小点，且下列条件满足：f(x),gj(x),ieI(x)在x可微；g(x),iWI(x)在x连续。则存在不全为零的非负数w0,w,・,ieI(x)和v.,jeE，使得W0Vf(x)-ZwVg(x)-ZvVh(x)=0ieI(x) jeEwVf(x)一(6a)(6b)(7)当W=0时，该条件不能刻画目标函数和约束函数的关系，这是该条件没有受到重视0的原因。注5:与K-T条件密切相关的一个函数是L(x,w,v)=f(x)-Zwg(x)-Zvh(x)ii jj，T j=1该函数的思想可以追索到Lagrange，故它被称为Lagrange函数，w=(*，…,w)t,v=(v1，—,v^)T称为Lagrange乘子。定义5:称xeS为(2)的K-T点，如果存在非负数叫,ieI(x)，和实数v.j=1,…,l，使得下式成立：

V/*(x)-£wVg(x)-£vVh(x)=0_ii jj则称可,ieI(无)，v，则称可,ieI(无)，v，j有了K-T点的定义，=1,…,l为Lagrange(\K-T)乘子。则定理1所表述的一阶必要条件可重新表述为：设在(2)的某可行点处某种约束规范成立，若其为(2)的局部极小点，则必为(2)的K-T点。求问题(2)的K-T点需求解下列系统：Vf(x)-£wVg(x)-£vVh(x)=0 (梯度条件)(8a)ii jji=1 j=1(互补松弛条件)(8b)wg(x)=0, i=1,…,m(互补松弛条件)(8b)(乘子的非负性)(8c)w>0,i=1,…,m(乘子的非负性)(8c)g,(x)>0,i=1,…,m，hj(x)=0,j=1,…,l(可行性)(8d)上面讨论的都是必要条件，下面讨论充分条件。引理3(几何最优性条件一充分)：设xeS，如果目标函数和约束函数在x处可微，且dTVf(x)>0, V0。deSFD(x,S)。则x是(2)的严格局部极小点。证明类似引理2。定理3:设xeS，如果目标函数和约束函数在x处可微，且dTVf(x)>0, V0。deLFD(x,S)。则x是(2)的严格局部极小点。证明：由引理1知SFD(x,S)cLFD(x,S)，再由引理3知结论成立。K-T点不一定是局部极小点，但对于凸规划而言，K-T点即为全局极小点。定理4(充分条件)：设xeS是(2)的K-T点，如果(2)为凸规划，即f(x),-g,(x)，i=1,…,m是凸函数，hj(x)，j=1,・・・,l是线性函数，则x是(2)的全局极小点。例7见例5。4.3.2二阶最优性条件设xeS，如果dTVf(x)>0, V0。deSFD(x,S)，则由引理3知x为(2)的严格局部极小点(因为满足充分条件)；如果3deSFD(x,S)，使得dTVf(x)<0,由引理2知x不是(2)的局部极小点(因为不满足必要条件)。考虑约束优化问题(2)，如果在x处一阶必要条件满足，即dTVf(x)>0,VdeSFD(x,S) (9a)3deSFD(x,S)，使得dTVf(x)=0 (9b)此时如何判断x是否为局部极小点?

所得判断条件称为二阶最优性条件。同讨论一阶最优性条件一样，需要讨论更高一阶的可行方向集。设在(2)中，f(x),gj(x),七(x)，i=1,—,m,j=1,…,l二次连续可微；下面讨论(2)的二阶最优性条件。定义6:设x为(2)的K-T点，顷应),诃>0为其一对应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点，则由(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)。此时考虑二阶最优性条件即要考虑集合 idgSFD(x,S)IwdTVg(x)=0,VigI(x)'ii中的方向，而该集合又包含在G(x,w,v)中，故引入了线性零约束方向。线性零约束方向集的特征：VdgG(x,w,v),有Vf(x)Td=0定义7：设x为(2)的匕丁点，(w,v),w>0为其一对应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据定义有: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条件的局部极小点，(w,v),w>0为其一对应Lagrange乘子。则必有dTV2L(x,w,V)d>0，VdeS(x,w,v)其中Vxx2L(x,w,v)是(2)的Lagrange函数中固定w,v后所得关于x的函数L(x,w,v)的Hesse矩阵在元的值(是一n阶方阵)，即V2L(x,w,v)=V2f(x)—LwV2g(x)—£vV2h(x)i=1 j=1证明利用目标函数L(x,w,v)在x+8dk处的二阶Taylor展开，序列零约束方向的定义及局部极小点的定义可证。定理5(二阶必要条件)：设xeS为(2)的局部极小点，(w,v),w>0为其一对应Lagrange乘子。如果G(无,w,v)=S(x,w,v) (13)则必有dTV2L(x,w,v)d>0,VdeG(x,w,v)。定理6(二阶充分条件)：设xeS是(2)的匕丁点，(w,v),w>0为其一对应Lagrange乘子。如果dTV2L(x,w,v)d>0, V0丰deG(x,w,v)xx则xeS是(2)的严格局部极小点。定义8:设xeS是(2)的K-T点，(w,v),w>0为其一对应Lagrange乘子。称hj(x)(jeE)，或gj(x)(ieI(x)，且叫>0)为x处的强积极约束。称A(x,w,v)=E{i|ieI(x),w>0}为x处的强积极约束指标集。则有

G(X,w,v)=LFD(X,S)<drVg(X)=0,w>0,iGI(X)drG(X,w,v)=LFD(X,S)<推论1：设XgS是(2)的K-T点，顷,v),订>0为其一对应Lagrange乘子。如果对一切满足dTVg(X)=0,w>0,igI(X)drVh(X)=0,jgE的非零方向d都有drV2L(X,w,v)d>0则XgS是(2)的严格局部极小点。令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实质:(2)的Lagrange函数中固定乘子后，所得函数的梯度在点XgS的值即为(14)；所得函数的Hesse矩阵在点XgS的值即为(15)。从而：♦一阶必要条件定理1即为：XgS为(2)的局部极小点的必要条件是存在Lagrange乘子(w,v),w>0,使得X为函数L(x,w,v)的驻点(约束规范LFD(X,S)=SFD(X,S)成立)；♦二阶必要条件定理5即为：XgS为(2)的局部极小点的必要条件是存在Lagrange乘子(w,v),w>0,使得X为函数L(x,w,v)的驻点，同时L(x,w,v)的Hesse矩阵在X的值在集合G(X,w,v)上为半正定矩阵(约束规范G(x,w,v)=S(x,w,v)成立)；♦二阶充分条件定理6即为：XGS为(2)的局部极小点的充分条件是存在Lagrange乘子(w,v),w>0,使得X为函数L(x,w,v)的驻点，同时L(x,w,v)的Hesse矩阵在X的值在集合G(X,w,v)上为正定矩阵。注：设AGRnxn为对称矩阵，如果对任意的dGDGRn，有drAd>0则称矩阵A为集合D上的半正定矩阵，或称矩阵A在集合D上半正定。如果对任意的0。dgDgRn，有drAd>0。则称矩阵A为集合D上的正定矩阵，或称矩阵A在集合D上正定。例8考虑下列非线性规划问题minX2+(x-2)2s.t.px2—X=0其中p为实参数，试讨论X=(0,0)t是否为该问题的局部最优解。目标函数和约束函数在X=(0,0)t的梯度：5厂、「0]「/一、I0

'(X)=—4，g(X)=一「0]—V「0]=「0]—4—10设解得u=4，Lagrange函数为L(X,v)=X2+(x—2)2—v(px2—X)「2—2pv0]它关于x的Hesse矩阵是：V2L=X02- 「2—8P 。一在点X处，有V2L- 0 2/…d八求集合G的元素d，令(0,—1)」1=0d1-2」,「d],解得d=01，d1可取任何实数。这时有「2—8p0]「d]「d]dTV2L(X,v)d=(d,0)一1=(d(2—8p),0)一1X 10 2010=2(1-4p)d2当P<1/4时，对每一个向量dgG，有dTV2L(X,v)d>0X因此X是局部最优解。当P>1/4时，对每一个向量dgG，有dTV2L(X,v)d<0在X不满足局部最优的二阶必要条件，因此X不是局部最优解。原问题即(3)当p=1/4时，利用二阶条件给不出结论，可用其它方法进行判断。这时，为原问题即minx2+(x—2)2,1 。 八s.t.4X2一X=0利用约束条件，从目标函数中消去一个变量，转化为无约束优化问题min4x+(x—2)222易知X是局部最优解。

§4.4约束优化问题的鞍点最优性条件1.预备知识考虑具有一般约束的优化问题(2)：(2)minf(x)(2)s.t. g(x)>0h(x)=0其中g(x)=(g(x),…,g(x))T，h(x)=(h(x),...,h(x))T，则(2)的lagrange函数为: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设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函数的鞍点。注：（x,w,v）为（2）的Lagrange函数的鞍点当且仅当xeargmin{L（x,w,v）IxeRn}，且（w,v）eargmax{L（x,w,v）IweRm,veRi,