《最优化方法》课程教学资源（题解）第九次 惩罚函数法

约束极值问题的算法 、惩罚函数法(SUMT 1.问题:min∫(x) St.g;(x)≥0i=l,…,m e min f(r) st.g(x)≥0这里g(x)=(g;(x)…,gn(x) 冷>minf(x) St.x∈D D={x|g(x)≥0}:可行点集或可行解集

一、惩罚函数法（SUMT） 约束极值问题的算法 s t g x i m f x i ， 问题： . . ( ) 0 1, 1. min ( )  = { | ( ) 0}:可行点集或可行解集 . . min ( ) =    D x g x s t x D f x T m s t g x g x g x g x f x . . ( ) 0 这 里 ( ) （ ( )， ， ( )） min ( )  = 1  

2、算法思想: 将有约束优化问题转化为一系列无约束优化问题进 行求解。( Sequential Unconstrained minimization Technique-SUMT) 3、算法类型 口外点法(外惩法) 内点法(内惩法

将有约束优化问题转化为一系列无约束优化问题进 行求解。（Sequential Unconstrained Minimization Technique - SUMT） 2、算法思想： 3、算法类型： ❑ 外点法（外惩法） ❑ 内点法（内惩法）

4、外点法(外部惩罚函数法) (1)几何解释 Pr(x) p2(x) ∫(

4、外点法（外部惩罚函数法） ( x ) 1 ( x ) 2 f ( x ) ( x ) k   D x * x （1）几何解释

(2)算法分析 ninf(x)→minq1(x)→minq2(x)→…→minφ(x) x∈D x∈Rn x∈Rn x∈Rn ∞+……>>,人 如何构造q(x)? (x)满足:q(x)=∫(x)x∈D q(x)>f(x)xgD且g(x)↑(k↑) 则可取:(x)=∫(x)+p(x), 其中p(x)满足 (1p(x)=0x∈D; (2)p(x)>0xgD

min f ( x ) min ( x ) min ( x ) min ( x ) k x D x R x R x R n n n            1 2  如何构造k (x)? 且 （ ） 满足：     =  x f x x D x k x x f x x D k k k k ( ) ( ) ( ) ( ) ( ) ( )     则可取： （ ） 。 （ ） 其 中 满 足 p x x D p x x D p x k x f x k p x   =  = + 2 ( ) 0 1 ( ) 0 ; ( )  ( ) ( )  ( ), （2）算法分析 + →k   2  1 

这样一来,我们只需构告p(x),事实上, 因为g,(x)≥0 分min8(x),0}=0分min{g(x),0}=0 所以可设 p(x)=∑(min{g1(x),0})2=∑min2{g,(x),0 显然p(x)满足恰前面的条件(1)和(2)。 结论1:如果g(x)G=1,2,…,m)连续,那么p(x)也连续。 事实上,只须注意: min(x),2(x)3 f(x)+f2(x)-f(x)-f2(x)

这样一来，我们只需构造 p(x)，事实上， 因为 g j (x)  0   = = = = m j j m j p x gj x g x 1 2 2 1 ( ) (min{ ( ),0}) min { ( ),0} 所以可设 显然 p(x) 满足恰前面的条件（1）和（2）。 结论1：如果 gj (x)（j = 1,2,  ,m）连续，那么p(x)也连续。 2 ( ) ( ) ( ) ( ) min{ ( ), ( )} 1 2 1 2 1 2 f x f x f x f x f x f x + − − = 事实上，只须注意： min{ ( ),0} 0 min { ( ),0} 0 2  gj x =  gj x =

结论2:如果(1)问题(B):minq(x)有最优解x(); ∈R (2)x(λ)∈D,即g,(x(λ)≥0G=1,2,…,m)。 则x‘(λ1)也是问题(A):minf(x)的最优解 x∈D 证明:因为x'()是(B):min(x)的最优解。 ∈R 所以φ(x(λ2)≤φ4(x),Vx∈R"。 又x(x)∈D,即g(x()≥0G=1,2,…,m), 所以p(x'(A)=0。 所以vx∈D,有f(x()=f(x(4)+p(x() q(x(λ) ≤q(x)

则 ）也是问题（ ）： 的最优解。 ，即 （ ）。 结论 ：如果 问题（ ） 有最优解 ( min ( ) (2) ( ) ( ( )) 0 1,2, , 2 (1) :min ( ) ( ); * * * * x A f x x D g x j m B x x x D k k j k k k x R n     =       所以 。 证明：因为 是（ ） 的最优解。 n k k k k x R k x x x R x B x n     ( ( )) ( ), ( ) :min ( ) * *      所以 。 又 即 （ ） ( ( )) 0 ( ) , ( ( )) 0 1,2, , , * * * =   = k k j k p x x D g x j m     , ( ( )) ( ( )) ( ( )) * * * k x k k p x k 所以x  D 有 f x  = f  +   ( ( )) * = k x k (x)  k

f()+n p(r) =f(x) 所以x(λ3)是问题maxf(x)的最优解

所 以 x * (k )是问题max xD f (x)的最优解。 f (x) p(x) = + k = f ( x)

(3)算法步骤(外点法 stepl给定初始点x",初始怎罚因子λ1>0(可取x1=1) 精度>0,k:=0。 step2以x为初始点,求解无约束化问题 min(x)=f(x)+λp(x)=f(x)+x∑mn2(g、(x),0) 得到极小点为x(λ),记为x+ ste3:如果x()∈D,即g,(x(λ1)≥EG=1,2,…,m), 则x(λ)就是问题(A):minf(x)的最优解,stop; x∈D 否则转step4. ste4:给定Ax>1(可取孔=a这里a>1为惩罚 因子的放大系数)k:=k+1,转stp2

（3）算法步骤（外点法）： 精 度 。 给定初始点 ，初始惩罚因子 （可取 ） ， 0, : 0 1. 1 0 1 1 0  =  = k step x    ( ) . min ( ) ( ) ( ) ( ) min ( ( ) ,0) 2. * 1 1 2 + =  = + = +  k k m j k k k j x R k x x x f x p x f x g x step x n 得到极小点为 ，记为 以 为初始点，求解无约束优化问题     4. ( min ( ) ; 3 ( ) , ( ( )) 1,2, , , * * * step x A f x stop step x D g x j m x D k k j k 否则转 则 ）就是问题（ ）： 的最优解， ：如果 即 （ ）    =      , : 1, 2. 4 1 1 1 k k step step k k k k 因子的放大系数） 转 ：给定 （可取 这里 为惩罚 = +  +    + =    

(4)应注意的问题 (a)在sep2中,可用无约束优化问题的算法求解 minφ(x)=f(x)+^kD(x) x∈R (b)在实际计算中,判断x(4)∈D用g(x(x)≥E (j=1,2,…,m)或λp(x)<E (c)在算法中,一开始λ不宜取的过大。否则会造成 无约束优化问题minφ(x)求解困难(λ越大, x∈R φ(x)的Hes矩阵的条件数越坏)

min ( x ) f ( x ) p( x ) step k k x R n  = +   (a) 在 2中 ，可用无约束优化问题的算法求解 的 矩阵的条件数越坏）。 无约束优化问题 求解困难（ 越大， 在算法中，一开始 不宜取的过大。否则会造 成 ( x ) Hesse min ( x ) k k k x R k n      (c) 1,2, , ( ) . (b) ( ) ( ( )) * *      =    j m p x x D g x k k j k （ ）或 在实际计算中，判断 用  （4）应注意的问题

(d)通常称: φ(x):增广函数,p(x)惩罚函数 λ:惩罚因子,λp(x)惩罚项 (6)例:试用外点法(外部罚函数法)求解如下化问题 min f(x=(x-1) st.x-2≥0 解:构造增广函数φ(x)如下: p(x)=(x-1)2+xmin2{x-2,0} jx≥2 1)2+( xr-2) if x<2

. . 2 0 min ( ) ( 1) (6) 2 −  = − s t x f x x 例：试用外点法（外部惩罚函数法）求解如下优化问题 ： 惩罚因子 ：惩罚项 ：增广函数 ： 惩罚函数 通常称： , ( ) ( ) , ( ) ( ) p x x p x d k k k       − + −  −  = 1 ( 2) 2 ( 1) 2 2 2 2 x x if x x if x （ ） k ( ) 1 min { 2,0} ( ) 2 2 x = x − + x − x k k k    （ ） 解：构造增广函数 如下：