惩罚函数法

1 ∑ 例如： 例如： q( x ) = 或 q( x ) = j =1 g ( x ) j
m m
1 等; 2 j =1 g ( x )
∑
m
j
m 1 q( x ) = ∑ ln 或 q( x ) = − ∑ ln g j ( x ) 等。 j =1 j =1 g j ( x)
通常称： 通常称：
ψ k ( x )：增广函数 , q( x )： 障碍函数 , 惩罚因子 , µ k q( x )： 惩罚项。 µ k：
2 j =1 j =1 m m
显然 p( x) 满恰足前面的条件（1）和（2）。
连续， 也连续。 结论 1 ： 如果 g j ( x ) j = 1,2, L , m ） （ 连续，那么 p( x ) 也连续。
事实上，只须注意： 事实上，只须注意： f1 ( x ) + f 2 ( x ) − f1 ( x ) − f 2 ( x ) min { f 1 ( x ), f 2 ( x )} = 2
x∈ R n j =1 m
得到极小点为 x * (λ k )，记为 x k +1 .
step 3 ： , 如果 x * ( λ k ) ∈ D ,即 g j ( x * (λ k )) ≥ ε（j = 1,2,L , m ） 就是问题（ 的最优解， 则 x * (λ k） 就是问题（ A）：min f ( x ) 的最优解， stop;
2 j =1 k =1
m
l
算法步骤相同
(8) 算法收敛性：
结论 1. 若点列 {x k } 是由外点法产生的，则有
ϕk +1 x k +1） ϕ（x k） （ ≥ k
（x k +1） （x k） p ≤p （x k +1） （x k） f ≥ f
结论 2. 设 f ( x)、g（x） j = 1,L , m)和hk x）k = 1,L , l ) ( （ ( j 都是 R n 上的连续函数，则由外点法产生的点 列 {x k }的任何极限点一定是所求问题的极小点。
问题（ : 结论 2 ： 如果 (1) 问题（B） min ϕ k ( x ) 有最优解 x * (λ k ) ;
x∈ R n
(2) x * (λ k ) ∈ D ，即g j ( x * (λ k )) ≥ 0 j = 1,2,L, m ） （ 。 也是问题（ min 的最优解。 则 x * (λ k） 也是问题（ A）： f ( x ) 的最优解。
⇔ min f ( x ) s .t . x ∈ D D = { x | g ( x ) ≥ 0} : 可行点集或可行解集
2、算法思想： 算法思想：
将有约束优化问题转化为一系列无约束优化问题进 行求解。 行求解。（Sequential Unconstrained Minimization Technique - SUMT） ）
x∈ R
(b) 在实际计算中，判断 x * ( λ k ) ∈ D 用 g j ( x * ( λ k )) ≥ ε 在实际计算中， （ j = 1,2,L , m ）或 λ k p( x ) < ε .
在算法中， 一开始 λ k 不宜取的过大。否则会 造成 不宜取的过大。 (c) 在算法中， 求解困难（ 越大， 无约束优化问题 min ϕ k ( x )求解困难（ λ k 越大， n
3、算法类型： 算法类型：
外点法（外惩法） 外点法（外惩法） 内点法（内惩法） 内点法（内惩法）
4、外点法（外部惩罚函数法） 外点法（外部惩罚函数法） （1）几何解释
M
ϕk ( x )
Mห้องสมุดไป่ตู้
ϕ2 ( x ) ϕ1 ( x ) f(x)
x
D
x*
（2）算法分析
min f ( x ) ⇒ min ϕ1 ( x ) ⇒ min ϕ 2 ( x ) ⇒ L ⇒ min ϕ k ( x ) n n n
内点法（障碍函数法）的迭代点是在可行域 内点法（障碍函数法） 点集内部移动的， 点集内部移动的，对接近可行域边界上的点施加 越来越大的惩罚， 越来越大的惩罚，对可行域边界上的点施加无限 大的惩罚，这好比边界是一道障碍物， 大的惩罚，这好比边界是一道障碍物，阻碍迭代 点穿越边界。 点穿越边界。 内点法要求可行点集的内点集合非空， 内点法要求可行点集的内点集合非空，否则 算法无法运行。 算法无法运行。这样一来内点法只对不等式约束 的优化问题才可能有效。 的优化问题才可能有效。
x∈ R n
1 + 2λ k lim x = lim x (λ k ) = lim = 2 = x* ， k →∞ k →∞ k →∞ 1 + λ k
k *
x *就是所求原问题的最优 解。
ϕk λ1 = 1 λ0 = 0 λ 2 = 10 L
f ( x)
x*
O
1
2
x
（7）一般模型的外点法
min f ( x ) g i ( x ) ≥ 0 i = 1,L，m s .t . h j ( x ) = 0 j = 1,L，p
(4) 例子：试用内点法（内 部惩罚函数法）求解如 下优化问题 例子：试用内点法（ 部惩罚函数法） 1 min f ( x ) = x 3 3 s .t . x − 1 ≥ 0
构造增广函数 ψ k ( x )如下： 如下： 解： 1 ψ k ( x ) = x + µk x −1
（3）算法步骤（外点法）： 算法步骤（外点法）：
0 step1. 给定初始点 x 0，初始惩罚因子 λ1 > （可取 λ1 = 1）， 精度ε > 0, k := 0。
step2. 以 x k 为初始点，求解无约束 优化问题 为初始点， min ϕ k ( x ) = f ( x ) + λ k p( x ) = f ( x ) + λ k ∑ min 2 ( g j ( x ),0)
if x ≥ 2 if x < 2
dϕ k ( x ) 可得： 由 = 0 可得： dx 2 （x − 1） 2λ k ( x − 2) = 0 +
1 + 2λ k 所以 x = x ( λ k ) = ∉D 1 + λk
k *
的最优解。 这就是对于固定的 λ k，问题 min ϕ k ( x )的最优解。
x∈ R
矩阵的条件数越坏）。 ϕ k ( x ) 的Hesse矩阵的条件数越坏）。
(d ) 通常称： 通常称：
ϕ k ( x )：增广函数 , p( x )： 惩罚函数 惩罚因子 , λ k p( x )： 惩罚项 λ k：
(6) 例：试用外点法（外部 惩罚函数法）求解如下 优化问题 惩罚函数法） 试用外点法（ min f ( x ) = ( x − 1) 2 s .t . x − 2 ≥ 0
约束极值问题的算法
一、惩罚函数法（SUMT） 惩罚函数法（SUMT）
1. 问题： 问题： min f ( x ) s .t . g i ( x ) ≥ 0 i = 1,L，m
⇔ min f ( x )
T s .t . g( x ) ≥ 0 这里 g( x ) = g1 ( x )， ，g m ( x )） L （
( 3) 算法分析
考虑如下优化问题： 考虑如下优化问题： min f ( x ) s .t . g i ( x ) ≥ 0 , i = 1,L，m
转化为无约束优化问题 : minψ k ( x ) = f ( x ) + µ k q( x )
x∈ R n
µ1 > µ2 > L > µk ↓ 0
构造函数 ψ k (x) = f ( x ) + µ k q( x ) , 其中 q( x ) 满足 : q if x ∈ int D （1） ( x ) > 0 q （2） ( x ) ↑ +∞ if x → ∂D
所以 ∀x ∈ D, 有 f ( x * ( λ k )) = f ( x * (λ k )) + λ k p( x * ( λ k )) = ϕ k ( x * (λ k ))
≤ ϕ k ( x)
= f ( x ) + λ k p( x )
= f ( x)
的最优解。 所以 x * ( λ k )是问题 max f ( x ) 的最优解。 x∈ D
5、内点法（障碍函数法） 内点法（障碍函数法） （1）集合结构
∂D
int D
D = ∂D ∪ int D = 边界点集 ∪ 内点集
∂D = { x | 至少存在一个 j , 使得 g j ( x ) = 0} ;
int D = { x | g j ( x ) < 0 , ∀ j }。
（2）算法思想
x∈ D
否则转 step 4.
step 4 ： 给定 λ k +1 > λ k（可取 λ k + 1 = αλ k 这里 α > 1 为惩罚 因子的放大系数） 因子的放大系数）, k := k + 1, 转 step 2.
（4）应注意的问题
(a) 在step 2中， 可用无约束优化问题的 算法求解 min ϕ k ( x ) = f ( x ) + λ k p( x ) n
⇔
min f ( x ) g( x ) ≥ 0 s .t . h( x ) = 0
我们不难想到构造如下 的惩罚函数 p( x ) = ∑ (min{ g j ( x ),0 } ) + ∑ ( hk ( x ) )2
2 j =1 k =1 m l
= ∑ min { g j ( x ),0 } + ∑ h 2 ( x ) k
x∈ D x∈ R x∈ R x∈ R
λ1 < λ2 < L < λk ↑ → + ∞