第五章 约束最优化方法 本章介绍一般约束最优化问题的算法，内容包括最优性条件，罚函数法，障碍函数法和 乘子法 §1 最优性条件 考虑如下一般约束最优化问题 ⎪⎩⎪⎨⎧===≥ljxhmixgxfGOPji ,, 2 , 1, 0)(,,, 2 , 1, 0)(s.t.)(min)(LL 的最优性条件，其中和),, 2 , 1(,migfiL=),, 2 , 1(ljhjL=都是连续可微函数 所谓最优性条件，是指(GOP)的最优解所要满足的必要条件和充分条件，这些条件对最 优化算法的设计和理论推导至关重要 记(GOP)的可行域为，对任意SSx∈，令 },1, 0)(|{)(mixgixIi≤≤== 则有如下最优性条件成立，称之为 Kuhn-Tucker 条件，简称 K-T 条件 定理定理 1.1（Kuhn-Tucker 条件条件） 设是(GOP)的局部最优解，如果向量组 *xljxhxIixgji,, 2, 1),(),(),(***L=∇∈∇ 线性无关，则存在常数),, 2, 1(0miiL=≥λ和),, 2, 1(ljjL=μ，使得 ⎪⎩⎪⎨⎧===∇+∇−∇∑∑ ==.,, 2, 1, 0)(, 0)()()(*1*1**mixgxhxgxfiiljjjmiiiLλμλ（1.1） 定理 1.1 中的常数),, 2, 1(0miiL=≥λ和),, 2, 1(ljjL=μ称为最优化问题(GOP)对应于最优解的最优乘子。
另外，容易看出条件（1.1）等价于 *x. 0)()()(1*)(***=∇+∇−∇∑∑ =∈ljjj xIiiixhxgxfμλ 定义定义 1.1 设，如果存在常数Sx ∈*),, 2, 1(0miiL=≥λ和),, 2, 1(ljjL=μ，使得（1.1）成立，则称是(GOP)的 K-T 点 *x1例例 1.1 设有最优化问题 ⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=−++=≥=≥=≥=≥+−=−−−=, 03)(, 0)(, 0)(, 0)(, 0)(s.t.23)(min2 32 22 113423122112 32 22 1xxxxhxxgxxgxxgxxxgxxxxf验证是 K-T 点 Tx) 1, 1, 1 (*=解解 由于，所以 01)()()(, 0)(* 4* 3* 2* 1>====xgxgxgxg}.1{}41, 0)(|{)(**=≤≤==ixgixIi经计算，知 ,222 )(,011 )(,426 )(* 1* 1*⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛ =∇ ⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛−=∇ ⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛−−− =∇xhxgxf 取2, 0, 214321=====μλλλλ，则有 , 0)()()(* 1141**=∇+∇−∇∑ =xhxgxfiiiμλ 且。
因此是 K-T 点 4, 3, 2, 1, 0)(*==ixgiiλTx) 1, 1, 1 (*=定理定理 1.2 设是凸函数，f),, 2 , 1(migiL=是凹函数，),, 2 , 1(ljhjL=是线性函数，如果是 K-T 点，则是(GOP)的全局最优解 Sx ∈**x证明证明 由的凸性，的凹性和的线性性，对任意figjhSx∈，有 ).()()()(),()()()(),()()()(*********xxxhxhxhxxxgxgxgxxxfxfxfT iiiT iiiT−∇+=−∇+≤−∇+≥由于是 K-T 点，所以存在常数*x),, 2, 1(0miiL=≥λ和),, 2, 1(ljjL=μ，使得 ⎪⎩⎪⎨⎧===∇+∇−∇∑∑ ==.,, 2, 1, 0)(, 0)()()(*1*1**mixgxhxgxfiiljjjmiiiLλμλ于是对任意，有 Sx∈2),()(] )()()([)()()()]()()([)]()()([)()()()()()()(**1*1**1*1**1***1******11xfxxxhxgxfxhxgxfxxxhxhxxxgxgxxxfxfxhxgxfxfTljjjmiiiljjjmiiiljT iijmiT iiiTljjjmiii=−∇+∇−∇++−=−∇++−∇+−−∇+≥+−≥∑∑∑∑∑∑∑∑========μλμλμλμλ即是(GOP)的全局最优解。
*x根据定理 1.2，如果能够求出凸优化问题的 K-T 点，则可以求出其全局最优解这种通 过求最优化问题的 K-T 点，进而达到求出其最优解的方法称为 K-T 法 例例 1.2 用 K-T 法求解最优化问题： ⎪⎩⎪⎨⎧=+≥+=. 1, 0s.t.,)(min2112 22 1xxxxxxf解解 设1)(,)(211−+==xxxhxxg，则 .11)(,01)(,22)(21⎟⎟ ⎠⎞ ⎜⎜ ⎝⎛=∇⎟⎟ ⎠⎞ ⎜⎜ ⎝⎛=∇⎟⎟ ⎠⎞ ⎜⎜ ⎝⎛=∇xhxgxxxf 解方程组 ⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎨⎧=−+=≥=≥==⎟⎟ ⎠⎞ ⎜⎜ ⎝⎛=⎟⎟ ⎠⎞ ⎜⎜ ⎝⎛+⎟⎟ ⎠⎞ ⎜⎜ ⎝⎛−⎟⎟ ⎠⎞ ⎜⎜ ⎝⎛, 01)(, 0)(, 0, 0)(,00 11 01 22211121xxxhxxgxxgxxλλλμλ解得TTxx) 1, 0,21,21(),,,(21−=μλ，于是Tx)21,21(*=是问题的 K-T 点由于所考虑的问题是凸优化问题，所以Tx)21,21(*=是该问题的全局最优解 对于凸优化问题，其 K-T 点就是全局最优解；对于一般约束最优化问题，其 K-T 点虽 然不再是全局最优解，但是仍然有可能是局部最优解。
考虑等式约束最优化问题 3⎩⎨⎧ ==.,, 2 , 1, 0)(s.t.)(min)(ljxhxfEOPjL其中和二阶连续可微对任意fjhSx∈和，记 lR∈λ}.,, 2, 1, 0)(|{)(, )()(),(1ljdxhRdxKxhxfxLT jnljjjL==∇∈=+=∑ =λλ定理定理 1.3 设，如果存在常数向量，使得 Sx ∈*T l),,,(21λλλλL=, 0)()(),(1***=∇+∇=∇∑ =ljjjxhxfxLλλ 且对任意，有 0),(*≠∈dxKd, 0))()((),(1*2*2*2>∇+∇=∇∑ =ljjjTTdxhxfddxLdλλ 则是(EOP)的严格局部最优解 *x证明证明 不妨设，即1=l)()(1xhxh=如果不是(EOP)的严格局部最优解，则存在序列，使得，且令 *x*)()(,}{xxSxkk≠⊆*)(xxk→)()(*)(xfxfk≤,*)(*)( )( xxxxdkk k −−= 则有解，所以存在收敛的子序列，不妨设为 }{)(kd. 0limlim*)(*)( )(≠=−−= ∞→∞→dxxxxdkkkkk根据中值定理，有 ),()()()()(*)(*)(**)(xxxxxhxhxhkkTk−+−∇=−ο 从而 )].()([1)()(*)(*)(*)(*)()(*xhxhxxxxxxdxhkkkkkT−−=−−+∇ο上式令取极限，有，即。
根据 Taylor 公式，有 ∞→k0)(*=∇dxhT)(*xKd ∈4, 0)()()())(()(21)()(*)(2*)(*)(*2*)(*)(*≤−=−+−∇−+−∇xfxfxxxxxfxxxxxfkkkTkkTο, 0)()()())(()(21)()(*)(2*)(*)(*2*)(*)(*=−=−+−∇−+−∇xhxhxxxxxhxxxxxhkkkTkkTο由于，所以 0),(*=∇λxL, 0)()]()([2*)(2*)(*)(*)( *2*2*)(*)( ≤ −−+−−∇+∇⎟⎟⎠⎞⎜⎜⎝⎛−−xxxxxxxxxhxfxxxxkkkkTkkολ 上式令取极限，有 ∞→k, 0),()]()([*2*2*2≤∇=∇+∇dxLddxhxfdTTλλ 这与已知条件相矛盾因此是(EOP)的严格局部最优解 *x例例 1.3 用 K-T 法求解最优化问题： ⎩⎨⎧==−−=. 0)(s.t.,3)(min22 222 1 xxhxxxxf解解 设，则 22 222 13),(xxxxxLλλ+−−=.10)(,2002),(,322),(221⎟⎟ ⎠⎞ ⎜⎜ ⎝⎛=∇⎟⎟ ⎠⎞ ⎜⎜ ⎝⎛ −=∇⎟⎟ ⎠⎞ ⎜⎜ ⎝⎛ +−−=∇xhxLxxxLλλλ 令 ⎪⎩⎪⎨⎧===⎟⎟ ⎠⎞ ⎜⎜ ⎝⎛ +−−=∇, 0)(, 0322),(221xxhxxxLλλ解得 K-T 点且Tx)0, 0(*=3=λ。
由于 },|)0 ,({}0)(|{)(11**RddddxhRdxKTTn∈===∇∈= 所以对任意，有 0),(*≠∈dxKd. 0202002)0 ,(),(2 11 12>=⎟⎟ ⎠⎞ ⎜⎜ ⎝⎛ ⎟⎟ ⎠⎞ ⎜⎜ ⎝⎛ −=∇ddddxLdTλ 根据定理 1.3，是问题的严格局部最优解 Tx)0, 0(*=5§2 罚函数法 考虑如下一般约束最优化问题 ⎪⎩⎪⎨⎧===≥,,, 2 , 1, 0)(,,, 2 , 1, 0)(s.t.)(min )(ljxhmixgxf GOPji LL 其中和都是连续函数，(GOP)的可行域记为 ),, 2 , 1(,migfiL=),, 2 , 1(ljhjL=S罚函数法的特点是把约束最优化问题转化为求解一系列无约束最优化问题， 它的主要思 想是，对违反约束条件的点在目标函数中加入相应的“惩罚” ，即增大其目标函数值，直至 趋于无穷；反之，则不予“惩罚” 具体地说，对问题(GOP)构造增广目标函数 ),()(),(xpxfxFσσ+= 其中0>σ为常数，称为罚因子，为非负连续函数，满足条件 )(xp, 0)(=⇔∈xpSx )(xp称为罚函数。
显然，函数),(σxF具有以下性质： （1）);(),(xfxFSx=⇔∈σ （2）);(),(+∞→+∞→⇔∉σσxFSx （3）如果是Sx ∈*),(σxF的极小点，则是(GOP)的最优解 *x由于增广目标函数的这些性质，所以自然想到选取数列∞→kkσσ:}{，进而把求解(GOP)的问题归结为求解如下一系列无约束最优化问题 ),,(minkxFσ 设其最优解是，最后以点列去逼近(GOP)的最优解这就是罚函数法的基本过程 )(kx}{)(kx目前常用的罚函数形式一般为 . )())(, 0(min)(1212∑∑ ==+=ljjmiixhxgxp 罚函数法罚函数法 Step1 取初始点， 初始罚因子)0(x01>σ， 增长因子1>β， 允许误差0>ε， 令； 0:=k6Step2 以为初始点，求解无约束最优化问题 )1(−kx),()(),(minxpxfxFkkσσ+= 设其最优解为； )(kxStep3 若，则取为(GOP)的近似最优解；否则，令 εσ≤)()(k kxp)(kx, 1:,1+==+kkkkβσσ 转 Step2 引理引理 2.1 在罚函数法中，设 ,, 2, 1),,(min),()(L== ∈kxFxFkRxkknσσ （2.1） 则 （1） );,(),(1)1()( ++≤kk kkxFxFσσ（2） );()()1()(+≥kkxpxp（3） ).()()1()(+≤kkxfxf证明证明 （1）由（2.1）并且注意到kσ单调增加，有 ).,()()()()(),(),(1)1()1( 1)1()1()1()1()(+++ +++++=+≤+=≤kkk kkk kk kk kkxFxpxfxpxfxFxFσσσσσ（2）由于 ⎪⎩⎪⎨⎧≤≤++++),,(),(),,(),(1)( 1)1()1()(kk kkkk kkxFxFxFxFσσσσ即 ⎪⎩⎪⎨⎧+≤++≤++++++),()()()(),()()()()( 1)()1()1()1()1()()(k kkk kkk kkk kkxpxfxpxfxpxfxpxfσσσσ所以 ),()()()()( 1)。