第六章 约束优化问题的最优性条件.pptxVIP

第六章约束优化问题的最优性条件;本章内容：

/5.1约束最优化问题的最优性条件;6.1约束最优化问题的最优性条件

信息与计算科学系

邵建峰办;本节内容:;约束最优化问题的一般形式;下面研究约束优化问题的最优解应该满足什么条件:;=J;定理1(Lagrange)设;证明对n=3,I=2证明。

如果/=2,约束曲线为三维空间中曲面h1(x)=0和曲面h2(x)=0的交线.;这个定理是等式约束最优化问题的局部最优解的

一阶必要条件。

下面不予证明而给出相应的二阶充分条件。;定理2(二阶充分条件)设在问题(I)中

(1)f(x),hi(x),h2(x),…,hl(x)二阶连续可微；

(2)存在x*gRn,aLRl使得Lagrange函数的梯度为零，即

VL(x*,a*)=Nf{x*)—(a*)T-Vh(x*)=0

(3)对任意VgRn，且使得vT.Vh(x*)=0的非零向量v，总有

vTVLx2(x*,A^)v0;例1试用最优性条件求

min卜］2+x22的最优解。;且;而且对使yT?V7z(x*)=。的任意非零向量

v=(k,-k)L(SO),都有

(2一2\yrVx2L(x*92*)v=vrv=8^0

1-22)

从而r二(A扼y是原问题的严格局部最优点。;二.不等式约束最优化问题的最优性条件;定义1设xcD。Vi，若gi(x)=0,则称第i?个约束是起作用约束或积极约束。并记

I(x)=(i|gi(x)=0i=1,2,…,m}

叫起作用约束集或积极约束集。

例2设约束sI(x)=1-x12-x2220

s2(x)=x1一x220;定义2设集合CuR〃,x.C。若VpeRn，有x+peCnx+1-peCVt0

则称集合C是一个以x为顶点的锥。;1、下降方向与可行方向;定义3设DuR〃非空，xcD。对于非零向量p,

若巡＞0,使Vtc（0M），必有（工）光（工）＞°

x+t?pcD\仃弋

则称p叫集合D在x处的一个

可行（容许）方向。而集合

G（x）={p丰013S＞0,s.t.Vtc（0,5）,x+1?pcD};I(x)={i|gj(x)=0i=1,2,…,m};I(x)={i|gj(x)=0i=1,2,…,m};和VgQ),-P0(ieI(x))可知，存在d0,;定理3（几何性最优条件）设;2、Farkas引理与FritzJohn条件;引理2(Farkas)设a1,a2?—,av和b是n维向量。

则所有满足不等式组

a：p0,i=1,2,???,v

的向量p,同时也满足不等式：bp0的充要条件是:;引理3(Gardon)设a1,a2,???,av是n维向量。

则不存在向量p使得

T

atpv0,i=1,2,…，v;定理4（FritzJohn一阶必要条件）设;证明因为(在x*处)CcS=中(空集)，即不等式组

JNf(x*)Tpv0

-Ngi(x)T-pv0ieI(x)

无解。由Gordan引理，知：

存在不全为零的数A),兀,ieI(x＞，使

m

(x*)-￡几-Vgz(x*)=0;定理结论的几何意义是:;例3对问题min(x]_1)2+(x2_1)2T

(1一X1_X2)3。/

s.t.X10r

X20;Fritz-John条件的缺点：厂

即三角形斜边上的点都是可行的(0)

Fritz-John点，但只有(1/2,1/2)7是最优点.,对于上面的例子，可行的Fritz-John点对应的人0*=0.

这表明在这些点处的有效约束函数的梯度是线性相关的.但是目标函数的信息并未出现在其中，这样对判断是否为最优解就不起作用了.

因为只要约束函数不变，改变目标函数，Fritz-John条件始终是成立的.

Kuhn-Tucker条件针对这一缺点作了改进.;I(x*)=|gi(X*)=0i=1,2,…,m}

定理5(KuhnTucker一阶必要条件)设

①x?是