惩罚.σ>0越大，受到的惩罚越重.当σ>0充分大时，要使P(x,σ) 算 达到极小，罚函数P(x)应充分小才可以.从而P(x,σ)的极小点充分 逼近可行域D,而其极小值自然充分逼近f(x)在D上的极小值.这 样求解一般约束优化问题(91)就可以化为求解一系列无约束的优化 问题 min P(x,k), 其中{σk}是正数序列，且Ok→十o 从例91可以看出，当o0时，P(x,o)的极小点x(o)→x*, 但 1 x1(0)+x2(o）-1= 20+2 20+1 -1 2+1≠0， 即x(o)￠D,也就是说x(σ)是从可行域的外部趋于x*的.因此上述 的罚函数法也称为外罚函数法（或外点法） 下面给出外罚函数法的详细算法步骤. Back Close
é{ 9.1 6/50 JJ II J I Back Close ®v. σ > 0 å, .®v. σ > 0 ø©åû, ᶠP(x, σ) à4, vºÍ P¯(x) Aø©‚å±. l P(x, σ) 4:ø© %Cå1ç D, Ÿ4äg,ø©%C f(x) 3 D ˛4ä. ˘ ¶)òÑÂ`zØK (9.1) “å±zè¶)òXÃÂ`z ØK min P(x, σk), Ÿ• {σk} ¥ÍS, Ö σk → +∞. l~ 9.1 å±w—, σ → ∞ û, P(x, σ) 4: x(σ) → x ∗ , x1(σ) + x2(σ) − 1 = 2σ + 2 2σ + 1 − 1 = 1 2σ + 1 6= 0, = x(σ) 6∈ D, è“¥` x(σ) ¥lå1ç ‹™u x ∗ . œd˛„ vºÍ{è°è vºÍ{ (½ :{). e°â— vºÍ{ç[é{⁄½.
(外罚函数法) 步0给定初始点x0∈R”,终止误差0≤e<1.01>0,Y>1. 令k=1. 步1以xk-1为初始点求解子问题 min P(x,Ok)=f(x)+kP(x). (9.4) x∈Rn 令其极小点为xk 步2若OkP(xk)≤E,停算，输出x*≈xk作为近似极小点。 步3令0k+1=Y0k,k:=k+1,转步1. 注由上述算法可知，外罚函数法结构简单，可以直接调用无约束 优化算法的通用程序，因而容易编程实现.缺点是：(1)x往往不是可 行点，这对于某些实际问题是难以接受的；(2)罚参数σk的选取比较 困难，取的过小，可能起不到“惩罚”的作用，而取得过大则可能造成 Back Close
7/50 JJ II J I Back Close ( vºÍ{) ⁄ 0 â½–©: x0 ∈ R n , ™éÿ 0 ≤ ε 1. σ1 > 0, γ > 1. - k := 1. ⁄ 1 ± xk−1 è–©:¶)fØK min x∈Rn P(x, σk) = f(x) + σkP¯(x). (9.4) -Ÿ4:è xk. ⁄ 2 e σkP¯(xk) ≤ ε, é, —— x ∗ ≈ xk äèCq4:. ⁄ 3 - σk+1 := γσk, k := k + 1, =⁄ 1. 5 d˛„é{å, vºÍ{({¸, å±ÜN^à`zé{œ^ßS, œ N¥?ߢy. ":¥: (1) xk ÿ¥å 1:, ˘Èu, ¢SØK¥J±.; (2) vÎÍ σk ¿' (J, L, åUÂÿ/®v0ä^, LåKåUE§
P(x,o)的Hesse阵的条件数很大，从而带来数值技术上的困难；(3) 注意到P(x)一般是不可微的，因而难以直接使用利用导数的优化算 法，从而收敛速度缓慢 下面讨论算法9.1的收敛性.我们首先证明下面的引理 引理9.1设{xk}是由算法91产生的迭代序列.若xk是子问 题(9.4)的全局极小点，则有下述结论成立： P(Ck+1,Ok+1）≥P(x,Ok): (9.5) P(xk+1）≤P(x), (9.6) f(ck+1）≥f(xk). (9.7) Back Close
8/50 JJ II J I Back Close P(x, σk) Hesse ^áÍÈå, l ë5ÍäE‚˛(J; (3) 5ø P¯(x) òÑ¥ÿåá, œ J±Ü¶^|^Í`zé {, l ¬ÒÑ›Ö˙. e°?ÿé{ 9.1 ¬Ò5. ·Çƒky²e°⁄n. ⁄n 9.1 {xk} ¥dé{ 9.1 )SìS. e xk ¥fØ K (9.4) ¤4:, Kke„(ÿ§·: P(xk+1, σk+1) ≥ P(xk, σk), (9.5) P¯(xk+1) ≤ P¯(xk), (9.6) f(xk+1) ≥ f(xk). (9.7)
证(1)注意到0k+1≥0k>0,因此有 P(Ck+1,Ok+1）=f(xk+1)+Ok+1P(xk+1), ≥f(xk+1)+OkP(xk+1), =P(Ck+1;Ok)P(Tk,Ok), 即(9.5)成立.由题设ck,xk+1分别是P(x,ok)和P(x,Ok+1)的全局极 小点，故有 f(x+1)+OP(x+1）≥f(cx)+OP(cx), (9.8) f(E)+O+1P(cK)≥f(k+1）+Ok+1P(xk+1): (9.9) 上面两式相加并整理可得 (Ok+1-Ok)P(Zk)(Ok+1-Gk)P(k+1), Back Close
9/50 JJ II J I Back Close y (1) 5ø σk+1 ≥ σk > 0, œdk P(xk+1, σk+1) = f(xk+1) + σk+1P¯(xk+1), ≥ f(xk+1) + σkP¯(xk+1), = P(xk+1, σk) ≥ P(xk, σk), = (9.5) §·. dK xk, xk+1 ©O¥ P(x, σk) ⁄ P(x, σk+1) ¤4 :, k f(xk+1) + σkP¯(xk+1) ≥ f(xk) + σkP¯(xk), (9.8) f(xk) + σk+1P¯(xk) ≥ f(xk+1) + σk+1P¯(xk+1). (9.9) ˛°¸™É\ønå (σk+1 − σk)P¯(xk) ≥ (σk+1 − σk)P¯(xk+1),
即 (Ok+1-O)[P()-P(x+1】≥0， 从而必有P(ak)-P(xk+1)≥0，即(9.6)成立.最后，由(9.8)立即可得 f(Ek+1)-f(xk)≥O[P(xk)-P(xk+1)≥0. 证毕， 下面我们给出算法91的收敛性定理. 定理9.1设{x}和{ok}是由算法9.1产生的序列，x*是约束 优化问题(9.1)的全局极小点.若xk为无约束子问题(9.4)的全局极 小点，且罚参数Ok→十心，则{xk}的任一聚点元都是(9.1)的全局 极小点. 证设x°是序列{xk}的一个聚点，不失一般性，设xk→x°，k→ +o.由题设x*是原问题的全局极小点，因而必为可行点，故有P(x*)= Back Close
10/50 JJ II J I Back Close = (σk+1 − σk)[P¯(xk) − P¯(xk+1)] ≥ 0, l 7k P¯(xk) − P¯(xk+1) ≥ 0, = (9.6) §·. Å, d (9.8) ·=å f(xk+1) − f(xk) ≥ σk[P¯(xk) − P¯(xk+1) ≥ 0. y. e°·Çâ—é{ 9.1 ¬Ò5½n. ½n 9.1 {xk} ⁄ {σk} ¥dé{ 9.1 )S, x ∗ ¥Â `zØK (9.1) ¤4:. e xk èÃÂfØK (9.4) ¤4 :, ÖvÎÍ σk → +∞, K {xk} ?ò‡: x¯ —¥ (9.1) ¤ 4:. y x ∞ ¥S {xk} òá‡:, ÿîòÑ5, xk → x ∞, k → +∞. dK x ∗ ¥ØK ¤4:, œ 7èå1:, k P¯(x ∗ ) =