《最优化方法》课程教学资源（PPT课件）约束最优化问题的最优性条件（刘二永）

理论部分 约束最优性条件

理论部分 约束最优性条件

等式约束问题 minf(x)x∈R"(1) st c,(x)=0i∈E

等式约束问题 min ( ) (1) n f x xR st. ci (x) = 0 iE = 1,2, l

一阶必要条件 定理1:若(1)x*是等式约束问题的局部最优解; (2)f(x)与c(x)(i=1,2,)在x的某邻域内 连续可微; (3)c,(x)(i=1,2,)线性无关; 则存在一组不全为零的实数x,使得: vf(x*)-v x)=0 i=1

一阶必要条件 定理1: 若(1) * x 是等式约束问题的局部最优解； (2) f (x) 与 c (x)(i l) i =1,2,  在 * x 的某邻域内 连续可微； (3) c (x)(i l)  i =1,2,  线性无关； 则存在一组不全为零的实数 * * 2 * 1 , ,   l 使得： ( ) ( ) 0 * 1 * *  −  = = f x c x l i i i

二阶充分条件 定理2:对等式约束问题,若 (1)f(x)与c;(xⅪ1≤i≤是二阶连续可微函数; (2)3x∈R"与x∈R使vL(x,x)=0; (3)s∈R且s≠0,且sVe1(x)=0,;=1,2,…t 均有V2L(x,x)>0 则x*是等式约束问题的严格局部极小点

二阶充分条件 定理2: 对等式约束问题，若： (1) f (x) 与 c (x)( i l) i 1  是二阶连续可微函数； (2) n x  R * 与 l  R *  使： ( , ) 0; * * L x  = (3) n s R 且 s  0, 且 s c (x ) i l i T  * = 0, =1,2,  均有 ( , ) 0 2 * * s xxL x s  T  则 * x 是等式约束问题的严格局部极小点．

不等式约束问题 minf(x)x∈Rn(2) st c;(x)≥0i={2,m}

不等式约束问题 min ( ) (2) n f x xR st. ci (x)  0 i = 1,2, m

定义1有效约束若(2)中的一个可行点x使得 某个不等式约束c(x)≥0变成等式即c,(x)=0, 则c(x)≥0称为关于x的有效约東 非有效约束若对c(x)>0,则ck(x)≥0称为 关于x的非有效约束 有效集:7=/(x)={c:(x)=0 定义2锥:R"的子集如果它关于正的数乘运算 是封闭的如果锥也是凸集,则称为凸锥 凸锥关于加法和正的数乘运算是封闭的

定义1:有效约束：若(2)中的一个可行点 x 使得 某个不等式约束 cj (x)  0 变成等式，即 c (x) = 0, j 则 cj (x)  0 称为关于 x 的有效约束． 非有效约束：若对 c (x)  0, k 则 ck (x)  0 称为 关于 x 的非有效约束． 有效集： I = I(x) = i ci (x) = 0 定义2:锥： n R 的子集，如果它关于正的数乘运算 是封闭的．如果锥也是凸集，则称为凸锥． 凸锥关于加法和正的数乘运算是封闭的．

定理3:在(2)中,假设: (1)x为(2)的局部最优解且 I 0.1≤i0,∈r 交为空

定理3: 在(2)中，假设： (1) * x 为(2)的局部最优解且 I * = i ci (x * )= 0,1 i  m； (2) f (x) 与 ( )( ) * c x i I i  在 * x 点可微； (3) ( )( ) * c x i I \ I i  在 * x 点连续； 则  ( ) 0 * S = d  R f x d  T n 与  ( )  * * G d R c x d 0,i I T i n =     交为空．

例1:确定 minf(x)=(x1-6)+(x2-2) S.tx1-2x,+4≥0 3x,-2x+12≥0 x1,x2≥0 在点x=(2,3)处的可行下降方向 解:x=(2,3)(x)={,2} VG(x) Vc,(x)= 2 32

例1：确定： ( ) ( ) ( ) , 0 3 2 12 0 . 2 4 0 min 6 2 1 2 1 2 1 2 2 2 2 1  − − +  − +  = − + − x x x x st x x f x x x 在点 ( ) T x = 2,3 处的可行下降方向. 解： ( ) T x = 2,3 I(x) = 1,2 ( ) ( )         − −  =         −  = 2 3 2 1 1 2 c x c x

v()/2x1-12 Vf() 设 d'Vc1(x)≥0d1-2d2≥0 dvc2(x)≥0-31-2a2≥0 dVf(x)<0-81+2d2<0

( ) ( )        −  =         − −  = 2 8 2 4 2 12 2 1 f x x x f x 设 ( ) T d d1 d2 = , d c1 (x)  0 T d1 − 2d2  0 d c2 (x)  0 T −3d1 − 2d2  0 d f (x)  0 T −8d1 + 2d2  0

阶必要条件 定理4(Ftz-John-阶必要条件)(1948) 设x*为问题(2)的局部最优解且f(x)c(x) 1≤i≤m)在x点可微则存在非零向量 x=(x,x,…,)使得 7/(x)-∑vc(x)=0 xc(x)=0i=1,2…,m A,≥0i=0,1,2,…,m

一阶必要条件 定理4: (Fritz-John一阶必要条件)(1948) 设 * x 为问题(2)的局部最优解且 f (x) c (x) i , (1 i  m) 在 * x 点可微，则存在非零向量 ( ) * * 1 * 0 * , , ,  =    m 使得： ( ) ( ) 0 1 * * * * 0  −  = = m i i i  f x  c x i ci (x ) 0 i 1,2, ,m  * * = =  i 0 i 0,1,2, ,m  *  = 