Fritz John 最优性条件—一阶必要条件 (1948) 最优性条件— 定理3.3.3: 为问题(3.3.1) (3.3.1)的局部最优解且 定理3.3.3: 设 x*为问题(3.3.1)的局部最优解且 点可微， 在 x* 点可微， 则存在非零 ( ) f ( x),ci ( x) 1≤ i ≤ m
的非有效约束g (x)≥0对 处的可行方向没有影响， x的非有效约束g3(x)≥0对 x 处的可行方向没有影响，
故非有效约束也称为不起作用的约束. 故非有效约束也称为不起作用的约束. 不起作用的约束
不等式约束最优化问题的最优性条件
几何最优性条件— 几何最优性条件—一阶必要条件
定理3.3.1: 定理3.3.1: 考虑约束最优化问题 m f (x), in (3.3 .2)
几何最优性条件— 几何最优性条件—一阶必要条件 确定： 例 1： 确定
s.t m f ( x) = ( x −6) +( x2 −2) in 1
2 2
x −2x2 +4 ≥ 0 1 2 −3x −2x2 +1 ≥ 0 1 x , x2 ≥ 0 1
在点 x = (2 3)T处的可行下降方向. , 处的可行下降方向. 解：x = (2,3)T，I( x) ={1 2 . , }
1 2
d d ; dT∇ 2( x) ≥ 0 −3 1 −2 2 ≥ 0 c , d d . dT∇ ( x) < 0 −8 1 +2 2 < 0 f ,
该 题 x 的 行 降 向 合 故 问 在处 可 下 方 集 为 2 2 1 F ={d ∈R | d2 < d1 ≤ − d2,d2 < 0}. D 4 3 由 F ≠φ 故 一 不 问 的 小 . 于D ， x 定 是 题 极 点
不等式约束最优化问题的最优性条件
可行方向锥与下降方向锥的几何解释
F0 在极小点处，任何 在极小点处， 下降方向都不是可 行方向， 行方向，而任何可 行方向也不是下降 方向， 方向，即，不存在 可行下降方向. 可行下降方向.
x
∇ (x) f
S
D
不等式约束最优化问题的最优性条件
定义
(3.3.1)中的一个可行点 设(3.3.1)中的一个可行点 x 满足 有效约束： 有效约束 cj ( x) = 0, 则称约束 cj ( x) ≥ 0 为在
不等式约束最优化问题的最优性条件
不等式约束最优化问题
m in
s.t.
f ( x)
ci ( x) ≥ 0 i =1 2 L , , , , m
(3.3.1)
n 中 ,c n (i ) 其 f : R →R i:R →R =1,2,...,m .
不等式约束最优化问题的最优性条件
定 义
闭包： 闭包
Closure
{Hale Waihona Puke }* 条 λi ci ( x* ) = 0 i =1 2,L m , , * 件 , , λi ≥ 0 i =1 2,L m
i= 1
K-T ∇ ( x* ) −∑ *∇ i ( x* ) = 0 f λi c
m
互补 松弛 条件
不等式约束最优化问题的最优性条件
KuhnKuhn-Tucker 最优性条件—一阶必要条件 最优性条件—
Active Constraint
处的有效约束或紧约束． x 处的有效约束或紧约束．
非有效约束： 非有效约束 inactive 在
Constraint
若有 ck ( x) > 0, 则 称 ck ( x) ≥ 0为
x 处的非有效约束或松约束． 处的非有效约束或松约束．
处的有效约束的指标集： x处的有效约束的指标集：
不等式约束最优化问题的最优性条件
几何最优性条件— 几何最优性条件—一阶必要条件
几何最优性条件直观, 几何最优性条件直观,但难以在实际 计算中应用. 计算中应用. ???
将几何最优性条件转化为代数 最优性条件. 最优性条件.
(1) Fritz John 条件 (2) Kuhn-Tucker 条件
不等式约束最优化问题的最优性条件
x S ∈
其 S ⊆ R 是 空 合 f : S →R 且在 中 , f 非 集 ， x处 微若 是 题3.3 2)的 部 小 ,则 可 . x 问 ( . 局 极 点 F ∩D=φ. 0
n
不等式约束最优化问题的最优性条件
几何最优性条件— 几何最优性条件—一阶必要条件
仅考虑在某点起作用的约束
定理3.3.2: 在问题(3.3.1)中 假设： 定理3.3.2: 在问题(3.3.1)中，假设： (3.3.1) (1) x*为局部最优解且I* = i c ( x* ) = 0,1≤ i ≤ m ；
定 下降方向(descent direction)： 下降方向 义设 ⊆Rn, x∈S,d∈Rn,d ≠ 0,且 : S →R在 x处 微 S f 点 可 ，
f d f 点 的 降 向 ∇ (x)T d < 0,则 为在 x处 下 方 .
下降方向锥：f在点 下降方向锥
x处的下降方向锥
F ={d | ∇ (x)T d < 0}. f 0
* * * * 则存在非 则存在非零的向量λ = (λ0,λ ,L λm), 使得： , 使得： 1
* λ0∇ ( x* ) −∑ *∇ i ( x* ) = 0 f λi c m
* λi ci ( x* ) = 0 i =1 2,L m , , * , , λi ≥ 0 i = 0,1 2,L m
不等式约束最优化问题的最优性条件
KuhnKuhn-Tucker 最优性条件—一阶必要条件 (1951) 最优性条件— 定理3.3.4 定理3.3.4 (3.3.1)局部最优解 局部最优解, 设 x* 为 (3.3.1)局部最优解, I* = i ci ( x* ) = 0 ; ) f ( x),ci ( x) (1≤ i ≤ m 在 x* 点可微， 点可微， 对于 i ∈I* 线性无关， 的∇ i ( x* )线性无关，则存在非零向量 c * * λ = (λ ,L λm) 使得： , * 使得： 1
KuhnKuhn-Tucker 最优性条件—一阶必要条件 最优性条件— 例 3：
m f ( x , x2 ) = x in 1 1 s.t
*
验证 x = (0,0) 处kuhn-Tucker条件是否成立？ kuhn-Tucker条件是否成立 条件是否成立？
T
c2( x , x2 ) = x2 ≥ 0 1
n S 设 ⊆R , S 闭 定 为 的 包 义 ：
clS ={x | S ∩N (x) ≠φ,∀ > 0 δ }. δ
设 ⊆ Rn, x∈clS,d ∈Rn,d ≠ 0,若 在 〉 使 存 δ 0 ， 得 可行方向： 可行方向 S x +λd ∈S,∀ ∈(0,δ ), λ 则 d为 合 在 x处 可 方 ( feasible direction 称 集 S 点 的 行 向 ).
f ∇ x* = ∑ *∇ i x* λi g
i=1
( )
m
( )
(a )
(a)的几何意义 的几何意义: 式(a)的几何意义:在局部
极小点 xk 处,目标函数的梯度 能表示成有效约束梯度的 非负组合, 非负组合,即目标函数的 梯度属于有效约束的梯度 所生成的凸锥内. 所生成的凸锥内.
不等式约束最优化问题的最优性条件
可行方向锥： 可行方向锥 S在点 x处的可行方向锥 D={d | d ≠ 0,∃δ > 0,使 +λd∈S,∀ ∈(0,δ)}. x λ
Feasible direction cone
t 注:当 x∈in S时, S在 当 在
处的可行方向锥是全空间R x 处的可行方向锥是全空间 n .
不等式约束最优化问题的最优性条件
f ( x)与ci ( x) i ∈I* 在 x* 点可微； 点可微； (2)
(3) ci ( x)(i ∈I \ I*) 在 x* 点连续； 点连续； 则
中 0 其 G =
(
)
{
i
}
{ d∈R ∇c (x ) d > 0,i ∈I }
n * T * i
F ∩G =φ, 0 0
不等式约束最优化问题的最优性条件
c ( x , x2 ) = x3 − x2 ≥ 0 1 1 1
解： ∀ = (λ ,λ2 )T ,有 对 λ 1
1 f c , ∇ x −λ ∇ 1 x −λ2∇ 2 x = 1 c λ −λ ≠ 0 2 1 T * , 不是K-T点． 点 所以 x =(0 0) 不是
T
*
* T
c2( x , x2 ) = x2 ≥ 0 1
*
c ( x , x2 ) = x3 − x2 ≥ 0 1 1 1
T
*
T
1
2
.
不等式约束最优化问题的最优性条件
Fritz John 最优性条件—一阶必要条件 最优性条件—
上例说明在Fritz John条件中有可能 0=0. 此时，目 条件中有可能λ 此时， 注: (1)上例说明在 上例说明在 条件中有可能 函数的梯度就会从Fritz John中消失 即Fritz John 中消失, 标 函数的梯度就会从 中消失 条件实际上不包含目标函数的任何信息， 条件实际上不包含目标函数的任何信息，仅仅表明 起作用约束函数的梯度线性相关， 起作用约束函数的梯度线性相关，而这对表述最优 点没有什么实际价值. 点没有什么实际价值
1 −3 c c ∇ 1( x) = −2, ∇ 2( x) = −2.
不等式约束最优化问题的最优性条件
几何最优性条件— 几何最优性条件—一阶必要条件
2 2x −1 −8 1 f f ∇ ( x) = 2x −4 , ∇ ( x) = 2 . 2 T d ; dT∇ 1( x) ≥ 0 d1 −2 2 ≥ 0 , 设 d = (d , d ) ,则 c