约束极值问题的算法 、惩罚函数法(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 xD 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 （ ） 解：构造增广函数 如下：