0.下面分两步证明本定理的结论 (1)先证x°是原问题的可行点，亦即P(x)=0.事实上，由引 理91知{P(xk,Ok)}是单调递增有上界的序列，因此极限存在，设为 P∞.此外，注意到{f(x)})也是单调递增的，且 f(xk)≤P(xk,O)≤f(x*), 即序列{f(x)}也收敛，记其极限为f°.于是有 lim akP(k)=lim [P(k,0k)-f(k)=poo-foo. ko× 因ok→+o,故必有limP(ck)=0.由P的连续性知P(x)=0, 即x°是可行点 (2)再证x°是全局极小点，亦即f(x)=f(x*).由f(x)的连续 性及xk→x°可知 f()=lim f(r)<f(c*). Back Close
11/50 JJ II J I Back Close 0. e°©¸⁄y² ½n(ÿ. (1) ky x ∞ ¥ØKå1:, ½= P¯(x ∞) = 0. Ø¢˛, d⁄ n 9.1 {P(xk, σk)} ¥¸N4Ok˛.S, œd4Å3, è P ∞. d , 5ø {f(xk)}) 襸N4O, Ö f(xk) ≤ P(xk, σk) ≤ f(x ∗ ), =S {f(xk)} è¬Ò, PŸ4Åè f ∞. u¥k lim k→∞ σkP¯(xk) = lim k→∞ P(xk, σk) − f(xk) = P ∞ − f ∞. œ σk → +∞, 7k lim k→∞ P¯(xk) = 0. d P¯ ÎY5 P¯(x ∞) = 0, = x ∞ ¥å1:. (2) 2y x ∞ ¥ ¤4:, ½= f(x ∞) = f(x ∗ ). d f(x) ÎY 59 xk → x ∞ å f(x ∞) = lim k→∞ f(xk) ≤ f(x ∗ ).
注意到x*是问题的全局极小点，故显然有f(x)≤f(x).从而 f(c)=f(x*),从而x°为原问题的全局极小点.证毕 注上述定理要求算法的每一迭代步求解子问题得到的xk必须 是无约束问题minP(x,ok)的全局极小点.这一点在实际计算中是很 难操作的，因为求无约束优化问题全局极小点至今仍然是一个很困难 的问题.故算法91（外罚函数法）经常遇到迭代失败的情形是很正常 的.此外，算法91之所以选用okP(ck)≤e作为终止条件，是因为 lim ok P(k)=lim [P(k,Ck)-f(k)]=poo-foo=0 k 的缘故 $9.2内点法 1.不等式约束问题的内点法 Back Close
12/50 JJ II J I Back Close 5ø x ∗ ¥ØK ¤4:, w,k f(x ∗ ) ≤ f(x ∞). l f(x ∞) = f(x ∗ ), l x ∞ èØK ¤4:. y. 5 ˛„½ná¶é{zòSì⁄¶)fØK xk 7L ¥ÃÂØK min P(x, σk) ¤4:. ˘ò:3¢SOé•¥È Jˆä, œè¶ÃÂ`zØK ¤4:ñ8E,¥òáÈ(J ØK. é{ 9.1 ( vºÍ{) ²~ëSìî}ú/¥È~ . d , é{ 9.1 ɧ±¿^ σkP¯(xk) ≤ ε äè™é^á, ¥œè lim k→∞ σkP¯(xk) = lim k→∞ [P(xk, σk) − f(xk)] = P ∞ − f ∞ = 0 . §9.2 S:{ 1. ÿ ™ÂØKS:{
内点法一般只适用于不等式约束的优化问题： min f(x), x∈Rn, (9.10) s.t.g(x）≥0，i=1,.,m. 记可行域D={x∈Rm:9(x)≥0，i=1,·,m}.内点法也属于罚 方法的范畴，其基本思想是保持每一个迭代点xk是可行域D的内点， 可行域的边界被筑起一道很高的“围墙”作为障碍，当迭代点靠近边 界时，增广目标函数值骤然增大，以示“惩罚”，并阻止迭代点穿越边 界.因此，内点法也称为内罚函数法或障碍函数法，它只是用于可行域 的内点集非空的情形，即 D0={x∈R”:g(x)>0,i=1,·,m}卡0. 类似于外罚函数法，我们需要构造如下的增广目标函数 H(x,T)=f(x)+TH(x), Back Close
13/50 JJ II J I Back Close S:{òÑê·^uÿ ™Â`zØK: min f(x), x ∈ R n , s.t. gi(x) ≥ 0, i = 1, · · · , m. (9.10) På1ç D = {x ∈ R n : gi(x) ≥ 0, i = 1, · · · , m}. S:{è·uv ê{âÆ, Ÿƒ g饱zòáSì: xk ¥å1ç D S:, å1ç>.”ÂòÈp/åp0äèÊN, Sì:ÇC> .û, O28IºÍä½,Oå, ±´/®v0 , ø{éSì:B> . œd, S:{è°èSvºÍ{½ÊNºÍ{, ßê¥^uå1ç S:8öòú/, = D0 = {x ∈ R n : gi(x) > 0, i = 1, · · · , m} 6= ∅. aqu vºÍ{, ·ÇIáEXeO28IºÍ H(x, τ ) = f(x) + τH¯ (x),
其中H(x)是障碍函数，它需要满足如下性质：当x在Do趋向于边界 时，至少有一个g(x)趋向于0，而H(x)要趋向于无穷大.因此可以取 约束函数的倒数之和为障碍函数可满足要求，即 H(x) 1 (9.11) 或者取对数障碍函数 m H(x)=- ∑mlga(x刃 (9.12) i=1 参数T>0称为罚因子或罚参数.这样，当x在D0中时，H(x)>0是 有限的；当x接近边界时，H(x)→十0，从而增广目标函数的值也趋 向于无穷大，因此得到了严重的“惩罚” 由于约束优化问题的极小点一般在可行域的边界上达到，因此与 外罚函数法中的罚因子σk)十∞相反，内点法中的罚因子则要求 Back Close
14/50 JJ II J I Back Close Ÿ• H¯ (x) ¥ÊNºÍ, ßIá˜vXe5ü: x 3 D0 ™ïu>. û, ñkòá gi(x) ™ïu 0, H¯ (x) á™ïuðå. œdå± ÂºÍÍÉ⁄èÊNºÍå˜vá¶, = H¯ (x) = X m i=1 1 gi(x) , (9.11) ½ˆÈÍÊNºÍ H¯ (x) = − X m i=1 ln[gi(x)]. (9.12) ÎÍ τ > 0 °èvœf½vÎÍ. ˘, x 3 D0 •û, H¯ (x) > 0 ¥ kÅ; x C>.û, H¯ (x) → +∞, l O28IºÍäè™ ïuðå, œd Ó/®v0. duÂ`zØK4:òÑ3å1ç>.˛à, œdÜ vºÍ{•vœf σk → +∞ Éá, S:{•vœfKá¶
k→0.于是，求解问题(9.10)就可以转化为求解序列无约束优化子 问题： min H(,Tk)=f()+TkH(x) (9.13) 现在我们来看一个简单的例子： 例9.2用内点法求解下面的优化问题： min 2x1+3x2, st.1-2ax2-≥0. 解给出增广目标函数为 H(x,T）=2x1+3x2-Tln(1-2x-x) Back Close
15/50 JJ II J I Back Close τk → 0. u¥, ¶)ØK (9.10) “å±=zè¶)SÃÂ`zf ØK: min H(x, τk) = f(x) + τkH¯ (x). (9.13) y3·Ç5wòá{¸~f. ~ 9.2 ^S:{¶)e°`zØK: min 2x1 + 3x2, s.t. 1 − 2x 2 1 − x 2 2 ≥ 0. ) â—O28IºÍè H(x, τ ) = 2x1 + 3x2 − τ ln(1 − 2x 2 1 − x 2 2 )