约束极值问题的算法 、惩罚函数法(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 =