罚函数法

No γk+1 = β γk
闸函数法： （续）
求初始内点： 1 x (1) , k 1, 转2 ； 2 令I k {i | g i ( x ( k ) ) 0}
(k ) 若 I , 则 x 为初始内点。 k 转 3 ； (k ) (k ) 否则，取j使g j ( x ) max{ g i ( x ) | i I k }

2 x
0
0
g ( x , ) 2 最优值(原问题)
3.闸函数法： （续）
定义 ( ) inf{ f ( x) B( x) | x S 0 } 有类似于罚函数法的理论结果： 定理： ( fg ), f , g连续，S 0 Φ , 最优解x S 0 则 1 min{ f ( x) | x S} inf{ ( ) | 0} lim ( )
(t ), (t )的典型取法： (t ) [max {0, t}] p (t ) | t | p
p为正整数。
当p 2时，称2次罚函数.(常用：因2次是最低次的光滑函数)
1.罚函数概念 （续）
Ex. min x s.t. x 2 0
2
( x 2) 2 , x 2 二次罚函数 : ( x) [max{ 0, x 2}] 0, x 2 如图 当 时, min 解析解 : 辅助函数 x ( x 2) 2 x 2 (4 1) x 4 , g ( x, ) f ( x) ( x) x ,x 2 4 1 当x 2时, g ( x, )的驻点x 2 2 故x 2 opt. 当x 2时, g ( x, )的最小值点~ x 2 x2 f ( x) ( x) f ( x ) x 2
3.闸函数法： （续）
1 典型取法： (t ) t 或： (t ) | ln( t ) | 0 x S0 惩罚项：B ( x ) x S 0 S 0 由于当x S 0时B ( x ) 0且B ( x ) x 故需要随着 x S 0 , 0 辅助问题 min f ( x ) B ( x )
f : Rn R h : Rn Rl
D R n 是一个集合，常由简单约束构成。
用Lagrange函数代替f ( x) :
5.广义乘子法： （续）
乘子罚函数：
( x, v, ) f ( x) vi hi ( x) i hi2 ( x)
i 1 i 1
l
l
x
2 f ( x ), ( )
关于 0的单调非降函数；
( x )
关于 0的单调非增函数
2.罚函数法： （续） 定理： ( fgh), S {x | g ( x ) 0, h( x ) 0} Φ ,
在引理假设下，设存在单调增加的正数列{ k }
即0 1 2 k .有{x k } k x

罚函数法框图 算法：
初始x(1), σ1>0, β>1, ε >0,k=1
k=k+1 以x(k)为初始点，解 min f(x)+ σ k P(x) 得到，x(k+1)
No
σk+1 = β σk
yes σk P(x(k+1))< ε 停；x(k+1)—l.opt.
3.闸（障碍）函数法： （内罚函数法） min f ( x) f : R n R ( fg ) n m s.t. g ( x) 0 g : R R 记S {x | g ( x) 0}, S 0 {x | g ( x) 0}
那么， 1 inf{ f ( x ) | x S } sup{ ( ) | 0} lim ( )

2 x ~ opt.且 ( ) 0
( x )
推论：在定理条件下，若 0使 ( x ) 0, 则x opt.
调整v ( k ) 及 ( k )。
广义乘子法： （续）
可以证明： 存在 ，当 时 min ( x, v , ) s.t. x D 的最优解，即原问题的解。 一般问题： min f ( x) min f ( x) s.t. g ( x) z 0 ( fghD)s.t. g ( x) 0 引入松弛变量 h( x ) 0 h( x ) 0 x x D { | x D, z 0} x D z 存在v
基本思想： 从S 0中的一个点（内点）出发，在目标函数中加入惩罚项， 使迭代保持在S 0内。 构造闸函数( Barrier Function) : B ( x) ( g i ( x))
i 1 m
使
0, x S 0 B( x) , x S 0 (边界)
为方便应有B ( x)连续。
构造罚函数：
( x) ( g i ( x)) (h j ( x))
i 1 j 1
m
l
目的：使满足约束的x有 ( x) 0 不满足约束的x有 ( x) 0
1.罚函数概念 （续）
0 , 当t 0时 其中： (t ) 0 当t 0时 0 , 当t 0时 (t ) 0 当t 0时 取 0, 可构造 0 可行 ( x) 惩罚项 不可行 f ( x) ( x) 辅助函数 min f ( x) ( x) 辅助问题
3.闸函数法： （续）
min x Ex. min s.t. x 2 0 1 闸函数B ( x ) ,x 2 x2 min g ( x, ) x x 2 解 s.t. x2 目： min g j ( x ) s.t. g i ( x ) 0, i I k 以x ( k ) 为初始内点，得到解x ( k 1) 转4 ；
( k 1) 若 g ( x ) 0, 停，说明S 0 . j 4 否则 置 k k 1 , 转 2 。
图示
外罚函数法 2.外罚函数法： （fgh）
定义：（） inf { f ( x) ( x)}
x
下确界
引理：设f , g , h连续， ( x)为罚函数，连续。 再设 0，x D, 使：（） f ( x ) ( x ) 则 1 inf { f ( x) | x S} sup{（） | 0}
0
2 若 0, x S 0 , 使 ( ) f ( x ) B( x )

那么， {x }的极限点是( fg )的opt.且 lim B( x ) 0
0
闸函数法 算法：
x(1) ∈ S0, γ1>0, β∈ [0,1], ε >0,k=1 k=k+1 min f(x)+ γk B(x) s.t. x∈ S0 从x(k）出发， 求得，x(k+1) yes γk B(x(k+1))< ε 停；x(k+1)—解
4.罚函数法与闸函数法的缺点： 1°当罚函数法（闸函数法）的μ →∞ （ μ → 0+）时，惩罚项 →+ ∞• 0或0• + ∞形式，在计算上有困难； 2°计算一系列无约束问题，故计算量大。 5.乘子法：
( fhD) x D
min f ( x) s.t. h( x) 0
其中：v R l 为乘子， R l 为罚因子。
(k ) (k ) min ( x , v , ) 求解 s.t. x D
得到x ( k 1) , k 0,1,2,
若h( x ( k 1) ) 0 否则
得到解x ( k 1) 及乘子v ( k ) ;
约束最优化方法
罚函数法
序列无约束最优化方法SUMT ( Sequential Unconstrained Minimizati on Technique ) 1.罚函数概念：
n min f ( x) f : R R n m ( fgh) s.t. g ( x) 0 g : R R n l h( x ) 0 h : R R