处的积极约束或称紧约束、起用作约束。
积极约束指标的全体组成的集合，称为 x 处的积极约束
指标集，记为 I ( x)，
I (x ) {i | gi (x ) 0,i 1, 2,L , m}.
起作用约束的判断
min f (x) s.t. gi (x) 0, i 1, 2,..., m (1)
约束优化问题
约束优化问题的一般形式
min f (x)
s.t. gi (x) 0, i 1, 2,..., m
(1)
hj (x) 0, j 1, 2,...,l
因为
hj
(
x)
0
hj h
(x) 0 j (x) 0
一般形式也可写为
min f (x)
s.t. g(x) 0
(*)
一般约束优化的一阶最优性条件
第 6 章 约束最优化方法
约束优化问题的最优性条件 ➢ 等式约束 ➢ 不等式约束 ➢ 一般约束问题
惩罚函数法 ➢ 外点法 ➢ 内点法 ➢ 乘子法
可行方向法 ➢ 投影梯度法
约束优化问题
约束优化问题的一般形式 min f (x)
s.t. gi (x) 0, i 1, 2,..., m
(1)
hj (x) 0, j 1, 2,...,l
与(3)中的第一个式子密切相关的是下面一个函数：
m
l
L(x, w, v) f (x) wi gi (x) v jhj (x)
(4)
i 1
j 1
m
l
0 xL(x, w, v) f (x ) wigi (x ) v jhj (x )
i 1
j 1
函数(4)的思想可追溯到Lagrange，故常被称为Lagrange函数，
令 x ( 2 , 2 )T , 求在 x 的起作用约束集。
22
解：因为 g1(x )
2(
2 )2 2
2 2
0,
g2 (x )
(
2 )2 ( 2
2 )2 1 0, 2
2 g3(x ) 2 0,
I (x) {1, 2}.
一般约束优化的一阶最优性条件
定理 (一阶必要条件)
min f (x) s.t. gi (x) 0, i 1, 2,..., m (1)
f (x)
l
wigi (x ) v jhj (x ) 0
iI ( x )
j 1
(2)
wi 0, i I (x )
f (x ) m wigi (x ) l v jhj (x ) 0
i 1
j 1
wi 0, i 1,..., m
wi gi (x ) 0, i 1,..., m
hj (x) 0, j 1, 2,...,l
x 为(1)的可行点，I (x) i gi (x) 0, f , gi (i I (x )) 在 x
处可微，gi (i I (x )) 在 x 处连续,hj ( j 1,.., l) 在 x 处连续
可微，向量集 gi (x),hj (x) i I (x), j 1,L ,l 线性无关。
若 x 是(1)的局部最优解，则存在 wi (i I (x )) 和 v j ( j 1,L ,l)
使得
f (x)
l
wigi (x ) v jhj (x ) 0
iI ( x )
j 1
(2)
wi 0, i I (x )
证明：参见陈宝林书 P253.
一般约束优化的一阶最优性条件
定理中的条件gi (i I (x )) 在 x 处连续变为连续可微，则
(3)
当 i I (x ) 时，gi (x ) 0，由(3)可知，wi 0,
wig(x ) 0(i I (x )) 从(3)中自然消失,得到(2).
一般约束优化的一阶最优性条件
(1)的一阶必要条件是由Kuhn和Tuchker与1951年提出， 故一阶必要条件称为K-T条件，满足(2)或(3)的点是K-T点。
回顾：无约束优化的一阶必要条件
设 f : Rn R，若 x为 f ( x) 的局部极小点，且在 N ( x*) 内连续可微，则f (x*) 0.
约束优化问题的一般形式
min f (x)
s.t. g(x) 0
(1)
h(x) 0
在约束优化问题中，自变量的取值受到限制，
目标函数在无约束情况下的驻点很可能不在可行域内，
hj (x) 0, j 1, 2,...,l
x D, 若 gi ( x) 0 ，则称 gi ( x) 0 是在 x 处的积极约束或称紧约束、 起用作约束。 在 x 积极约束指标集I (x ) {i | gi (x ) 0, i 1, 2,L , m}.
例1：设 g1(x) 2x12 x2 0, g2(x) x12 x22 1 0, g3(x) x1 0.
互补松弛条件
1939年，Karush也类似考虑了约束优化的最优性条件，故一
阶必要条件称作K-K-T条件，将K-T点称作K-K-T点。
一般约束优化的一阶最优性条件
m
l
f (x) wigi (x) vjhj (x) 0
i 1
j 1
wi 0, i 1,..., m
(3)
wi gi (x) 0, i 1,..., m
f (x)
l
wigi (x ) v jhj (x ) 0
iI ( x )
j 1
wi (x ) m wigi (x ) l v jhj (x ) 0
i 1
j 1
wi 0, i 1,..., m
(3)
wi gi (x ) 0, i 1,..., m
一般不能用无约束优化的方法处理约束优化问题。
一般约束优化的一阶最优性条件
定义(起作用约束)
min f (x) s.t. gi (x) 0, i 1, 2,..., m (1)
hj (x) 0, j 1, 2,...,l
设可行解x D, 若 gi ( x) 0，则称 gi ( x) 0 是在 x 处的
记 g(x) ( g1(x) , g2 (x) ,..., gm (x) )T ,
h(x) ( h1(x) , h2 (x) ,..., hl (x) )T ,
则约束优化问题可表示为 min f (x)
s.t. g(x) 0
(1)
h(x) 0
令D { x| g(x) 0, h(x) 0}, 是约束优化问题的可行域。