第13章 惩罚函数法 惩罚函数法的基本思想是：借助惩罚函数把约束问题转化为无约 束问题，进而用无约束最优化方法来求解。 §13.1 外点罚函数法 13.1.1 罚函数的概念 考虑约束问题 min f(x) S.t 8,(x)≥0，i=1,,m (13.1.1) h,(x)=0,j=1,,1 其中f(x),8,(xi=1,,m)和h,（x(j=1,,)是R”上的连续函数
第13章 惩罚函数法 惩罚函数法的基本思想是:借助惩罚函数把约束问题转化为无约 束问题,进而用无约束最优化方法来求解. §13.1 外点罚函数法 13.1.1 罚函数的概念 考虑约束问题 h x j l st g x i m f x j i ( ) 0, 1,..., . ( ) 0, 1,..., min ( ) = = = (13.1.1) 其中 f (x), gi (x)(i = 1,...,m)和hj (x)( j = 1,...,l)是 R n上的连续函数
在求解时必须同时照顾到即使目标函数值下降又要满足约 束条件这两个方面. 一种途径是由目标函数和约束函数组成辅助函数，把原来的 约束问题转化为极小化辅助函数的无约束问题 比如，对于等式约束问题 min f(x) (13.1.2) s.t h(x)=0j=1,,1 可定义辅助函数 F(xo)=fx)+o∑(x) (13.1.3)
在求解时必须同时照顾到即使目标函数值下降又要满足约 束条件这两个方面. 一种途径是由目标函数和约束函数组成辅助函数,把原来的 约束问题转化为极小化辅助函数的无约束问题. 比如,对于等式约束问题 st h x j l f x j . ( ) 0 1,..., min ( ) = = 可定义辅助函数 (13.1.2) = = + l j j F x f x h x 1 2 1 ( ,) ( ) ( ) (13.1.3)
参数0是很大的正数.这样就能够把(13.1.2)转化为无约束问题 n F(x,o) (13.1.4 显然，(13.1.4)的最优解必使得h,（x)接近零，因为如若不然，(13.1.3) 的第2项将是很大的正数，现行点必不是极小点由此可见，求解问 题(13.1.4)能够得到问题(13.1.2)的近似解 对于不等式约束问题 min f(x) S.t 8(x)≥0，i=1,.,m (13.1.5) 辅助函数的形式与等式约束情形不同，但构造辅助函数的基本思 想是一致的，这就是在可行点辅助函数值等于原来的目标函数值， 在不可行点，辅助函数值等于原来的目标函数值加上一个很大的 正数.根据这样的原则，对于不等式约束问题(13.1.5)，我们定义
参数 是很大的正数.这样就能够把(13.1.2)转化为无约束问题 min ( , ) F1 x (13.1.4) 显然,(13.1.4)的最优解必使得 接近零,因为如若不然,(13.1.3) 的第2项将是很大的正数,现行点必不是极小点.由此可见,求解问 题(13.1.4)能够得到问题(13.1.2)的近似解. h (x) j 对于不等式约束问题 st g x i m f x i . ( ) 0, 1,..., min ( ) = (13.1.5) 辅助函数的形式与等式约束情形不同,但构造辅助函数的基本思 想是一致的,这就是在可行点辅助函数值等于原来的目标函数值, 在不可行点,辅助函数值等于原来的目标函数值加上一个很大的 正数.根据这样的原则,对于不等式约束问题(13.1.5), 我们定义
函数 F2(x,o)=f(x)+o∑[max{0,-g,(x)}]2 (13.1.6) 其中o是很大的正数 当X为可行点时， max{0,-8,(x)}=0 当x不是可行点时， max{0,-g,(x)}=-8,(x) 这样，可将(13.1.5)转化为无约束问题 min F(x,o) (13.1.7) 通过(13.1.7)求得(13.1.5)的近似解
函数 = = + − m i i F x f x g x 1 2 2 ( , ) ( ) [max{0, ( )}] (13.1.6) 其中 是很大的正数. 当 x 为可行点时, max{0,−gi (x)} = 0 当 x 不是可行点时, max{0, g (x)} g (x) − i = − i 这样,可将(13.1.5)转化为无约束问题 min ( , ) F2 x (13.1.7) 通过(13.1.7)求得(13.1.5)的近似解
对于一般情形13.1.1)，可定义函数 F(x,o)=f(x)+oP(x) (13.1.8) 其中P(x)具有下列性质： Px)=∑(g,(x》+∑oh,(w》 (13.1.9) i=1 和0是满足下列条件的连续函数： 当y≥0时，(y)=0, 当y0, 当y=0时，p(y)=0, 当y≠0时，p(y)>0. 函数和p的典型取法如
对于一般情形(13.1.1),可定义函数 F(x, ) = f (x) +P(x) (13.1.8) 其中 P(x) 具有下列性质: = = = + m i l j i j P x g x h x 1 1 ( ) ( ( )) ( ( )) (13.1.9) 和 是满足下列条件的连续函数: 0 , ( ) 0. 0 , ( ) 0, 0 , ( ) 0, 0 , ( ) 0, = = = y y y y y y y y 当 时 当 时 当 时 当 时 函数和 的典型取法如
p=[max{0,-8,(x)}]9 =h,(x)" 其中a≥1，B≥1，均为给定常数.通常取作a=B=2. 这样，把约束问题(13.1.1)转化为无约束问题 min F(x,o)=f(x)+oP(x) (13.1.10) 其中O是很大的正数，P(x)是连续函数 根据定义，当x为可行点时，P(x)=0,从而有F(x,o)=f(x) 当x不是可行点时，在X处，OP(x)是很大的正数，它的存在是对点 脱离可行域的一种惩罚，其作用是在极小化过程中迫使迭代点靠 近可行域.因此，求解问题(13.1.10)能够得到约束问题(13.1.1)的近 似解，而可越大，近似程度越好.通常将σP(x)称为罚项，可称为罚 因子，F(x,o)称为罚函数
其中 1, 1, ,均为给定常数.通常取作 . ( ) [max{0, ( )}] h x g x j i = = − = = 2 这样,把约束问题(13.1.1)转化为无约束问题 min F(x,)= f (x) +P(x) (13.1.10) 其中 是很大的正数, P(x) 是连续函数. 根据定义,当 为可行点时, ,从而有 当 不是可行点时,在 处, 是很大的正数,它的存在是对点 脱离可行域的一种惩罚,其作用是在极小化过程中迫使迭代点靠 近可行域.因此,求解问题(13.1.10)能够得到约束问题(13.1.1)的近 似解,而 越大,近似程度越好.通常将 称为罚项, 称为罚 因子, 称为罚函数. x x x P(x) = 0 F(x, ) = f (x); P(x) P(x) F(x, )
例13.1.1 考虑下列问题： min X (13.1.11) s.t x-2≥0 令 P(x)=[max{0,-g(x)}]2 当x≥2 2当x<2 例13.1.2 求解下列非线性规划问题： △ min f(x)=(x,-1)2+x s.t 8(x)=x2-1≥0
例13.1.1 考虑下列问题: . 2 0 min st x − x 令 − = = − ( 2) 2 0 2 ( ) [max{0, ( )}] 2 2 x x x P x g x 当 当 (13.1.11) 例13.1.2 求解下列非线性规划问题: . ( ) 1 0 min ( ) ( 1) 2 2 2 2 1 = − = − + st g x x f x x x
例 用罚函数法求解 mm)-(》 s.t.x≤0 解：构造罚函数 F(x,o)=f(x)+o[max{-g(x),0}]2 x-+a(maxtx.0g) 令 dr)+2o(max(.0
例 用罚函数法求解 2 ( , ) 1 2 2 [max{ ,0}] 0 2 dF x x x dx = − + = 2 F x f x g x ( , ) ( ) [max{ ( ),0}] = + − 2 1 2 (max{ ,0}) 2 x x = − + 2 1 min ( ) 2 . . 0 f x x s t x = − 解：构造罚函数 令
对不满足约束条件的点x,有 2-2+2ax=0 得极小点 $(o) 20+0) 当a=0时，a,)=2 当0-1时，a,) 当a=10时，(a,）2方
1 ( ) 2(1 ) x = + 对不满足约束条件的点x，有 1 2 2 0 2 x x − + = 得极小点 当 (3) 3 1 ( ) ; 22 x = 1 = 0 (1) 1 1 ( ) ; 2 x = 2 =1 (2) 2 1 ( ) ; 4 x = 3 =10 时， 当 时， 当 时
f(x) o=100=1 F(x,o) 0→00 σ=0 0 0.51 x 图13.1.1 当Ok→0时，xk(ok)→0
k → ( ) ( ) 0 k k x → 。 x f x( )o 0.5 1 → F x( , ) = 0 =10 =1 图13.1.1 当 时