《数值最优化方法》课程教学课件（讲稿，打印版）罚函数法

最优化方法及其Matlab程序设计 第九章罚函数法 Back Close

1/50 JJ II J I Back Close Å`zê{9Ÿ Matlab ßSO 1 Ÿ vºÍ{

从本章开始，我们讨论约束优化问题的求解方法.首先介绍求解 约束优化问题的经典算法一罚函数法.其基本思想是：根据约束条件 的特点将其转化为某种惩罚函数加到目标函数中去，从而将约束优化 问题转化为一系列的无约束优化问题来求解.本章主要介绍外罚函数 法、内点法和乘子法 §9.1外罚函数法 我们首先通过一个简单的例子来说明罚函数的构造 例9.1求解约束优化问题： minf(x=(x1-1)2+(x2-1)2, s.t.x1+c2=1. 解由等式约束得x2=1一x1,代入目标函数得到一个无约束的 Back Close

2/50 JJ II J I Back Close lŸm©, ·Ç?ÿÂ`zØK¶)ê{. ƒk0¶) Â`zØK²;é{—vºÍ{. Ÿƒgé¥: ä‚Â^á A:ÚŸ=zè,´®vºÍ\8IºÍ•, l ÚÂ`z ØK=zèòXÃÂ`zØK5¶). ŸÃá0 vºÍ {!S:{⁄¶f{. §9.1 vºÍ{ ·ÇƒkœLòá{¸~f5`²vºÍE. ~ 9.1 ¶)Â`zØK: min f(x) = (x1 − 1)2 + (x2 − 1)2 , s.t. x1 + x2 = 1. ) d™Â x2 = 1 − x1, ì\8IºÍòáÃÂ

单变量极小化问题 min(c1)=(c1-1)2+c 其全局极小点为x=0.5,从而得到原问题的全局极小点为x*= (0.5,0.5)T.现在要使构造的罚函数P(x)满足 只要令P(x)=(x1+x2-1)2即可.现在考察目标函数和上述罚函数 的组合 P(x,a)-f(x)+oP(x) = (x1-1)2+(2-1)2+o(x1+2-1)2, 其中σ>0是充分大的正数，称为罚参数或罚因子.求这个组合函数 Back Close

3/50 JJ II J I Back Close ¸C˛4zØK min φ(x1) = (x1 − 1)2 + x 2 1 , Ÿ¤4:è x ∗ 1 = 0.5, l ØK¤4:è x ∗ = (0.5, 0.5)T . y3á¶EvºÍ P¯(x) ˜v P¯(x)    = 0, x1 + x2 − 1 = 0, > 0, x1 + x2 − 1 6= 0, êá- P¯(x) = (x1 + x2 − 1)2 =å. y3 8IºÍ⁄˛„vºÍ |‹ P(x, σ) = f(x) + σP¯(x) = (x1 − 1)2 + (x2 − 1)2 + σ(x1 + x2 − 1)2 , Ÿ• σ > 0 ¥ø©åÍ, °èvÎͽvœf. ¶˘á|‹ºÍ

的极小点.由 0P(x,o）8P(x,o) 0x1 0x2 得 (1+0)x1+0x2=1+0, 0x1+(1+0)x2=1+0. 求解上述方程组得 1(o）=x2(o)= 0+1 20+1 令0〉十0，有 ao.o)r→(5》 =t D 这样，我们就从无约束优化问题极小点的极限得到了原问题的极小点 Back Close

4/50 JJ II J I Back Close 4:. d ∂P(x, σ) ∂x1 = ∂P(x, σ) ∂x2 = 0,     (1 + σ)x1 + σx2 = 1 + σ, σx1 + (1 + σ)x2 = 1 + σ. ¶)˛„êß| x1(σ) = x2(σ) = σ + 1 2σ + 1 . - σ → +∞, k ￾ x1(σ), x2(σ)
T → 1 2 , 1 2 T = x ∗ . ˘, ·Ç“lÃÂ`zØK4:4Å ØK4:.

下面我们将这种思想方法推广到一般约束的优化问题.考虑 minf(c),x∈Rn, s.t.h(x)=0,i∈E={1,.,l}, (9.1) g(x)≥0，i∈I={1,.,m} 记可行域为D={x∈Rm|h,(x)=0(i∈E),g:(x)≥0(i∈I)}.构造 罚函数 P()=∑()+∑Imin0,g.(rP (9.2) 和增广目标函数 P(x,o)=f(x)+P(x), (9.3) 其中σ>0是罚参数或罚因子.不难发现，当x∈D时，即x为可行 点时，P(x,σ)=f(x),此时，目标函数没有受到额外惩罚；而当xD 时，即x为不可行点时，P(x,σ)>f(x),此时，目标函数受到了额外的 Back Close

5/50 JJ II J I Back Close e°·ÇÚ˘´géê{Ì2òÑÂ`zØK. ƒ    min f(x), x ∈ R n , s.t. hi(x) = 0, i ∈ E = {1, · · · , l}, gi(x) ≥ 0, i ∈ I = {1, · · · , m}. (9.1) På1çè D = {x ∈ R n | hi(x) = 0 (i ∈ E), gi(x) ≥ 0 (i ∈ I)}. E vºÍ P¯(x) = X l i=1 h 2 i (x) +X m i=1 [min{0, gi(x)}] 2 (9.2) ⁄O28IºÍ P(x, σ) = f(x) + σP¯(x), (9.3) Ÿ• σ > 0 ¥vÎͽvœf. ÿJuy,  x ∈ D û, = x èå1 :û, P(x, σ) = f(x), dû, 8IºÍvk. ®v;  x 6∈ D û, = x èÿå1:û, P(x, σ) > f(x), dû, 8IºÍ. 

惩罚.σ>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≤e0,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 ∗ ) =