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

最优化方法及其Matlab程序设计 第八章最优性条件 Back Close

1/37 JJ II J I Back Close Å`zê{9Ÿ Matlab ßSO 1lŸ Å`5^á

§8.1等式约束问题的最优性条件 本节讨论的最优性条件适合于下面的等式约束问题 min f(x), (8.1) s.t.h(x=0,i=1,2,.,l. 为了研究问题的方便，我们作问题(81)的所谓拉格朗日函数 L(z,)=f(a)-h(, (8.2) =1 其中入=(1,2，·，)T称为乘子向量， 下面的拉格朗日定理描述了问题(8.1)取极小值的一阶必要条件， 也就是所谓的KT条件(Kuhn-Tucker条件). 定理8.1（拉格朗日定理)假设x*是问题(8.1)的局部极小 点，f(x)和h(c)(i=1,2,·,l)在x*的某邻域内连续可微.若 Back Close

2/37 JJ II J I Back Close §8.1 ™ÂØKÅ`5^á !?ÿÅ`5^á·‹ue°™ÂØK min f(x), s.t. hi(x) = 0, i = 1, 2, · · · , l. (8.1) è ÔƒØKêB, ·ÇäØK (8.1) §¢.ÇKFºÍ L(x, λ) = f(x) − X l i=1 λihi(x), (8.2) Ÿ• λ = (λ1, λ2, · · · , λl) T °è¶fï˛. e°.ÇKF½n£„ ØK (8.1) 4äò7á^á, è“¥§¢ KT ^á (Kuhn-Tucker ^á). ½n 8.1 ( .ÇKF½n ) b x ∗ ¥ØK (8.1) ¤‹4 :, f(x) ⁄ hi(x) (i = 1, 2, · · · , l) 3 x ∗ ,çSÎYåá. e

向量组Vh(x*)(i=1,2,·,)线性无关，则存在乘子向量入*= (,遭，.，)T使得 7xL(x*,入*)=0， 即 /e)-∑va(e=0 证记 H=(Vh(x"),Vh2(),.,Vhi(*)). 由定理的假设知H列满秩.因此，若l=几，则H是可逆方阵，从而矩 阵H的列构成Rm中的一组基，故存在入*∈R'(亿=n)使得 Vf)=∑vi( Back Close

3/37 JJ II J I Back Close ï˛| ∇hi(x ∗ ) (i = 1, 2, · · · , l) Ç5Ã', K3¶fï˛ λ ∗ = (λ ∗ 1 , λ∗ 2 , · · · , λ∗ l ) T ¶ ∇xL(x ∗ , λ∗ ) = 0, = ∇f(x ∗ ) − X l i=1 λ ∗ i ∇hi(x ∗ ) = 0. y P H = ￾ ∇h1(x ∗ ), ∇h2(x ∗ ), · · · , ∇hl(x ∗ )
. d½nb H ˜ù. œd, e l = n, K H ¥å_ê , l › H § R n •ò|ƒ, 3 λ ∗ ∈ R l (l = n) ¶ ∇f(x ∗ ) = X l i=1 λ ∗ i ∇hi(x ∗ )

此时结论得证， 下面设l<n.不失一般性，可设H的前（行构成的l阶子矩阵 H1是非奇异的.据此，将H分块为 H H 令y=(c1,.,r),之=(c+1,.,xn)T,并记h(c)=(h(c),.,hu(c) 则有h(y*,z*)=0,且h(y,z)在点(y*,z*)关于y的Jacobi矩阵 H=V,h(y*,z)可逆.故由隐函数定理可知，在z*附近存在关于 z的连续可微函数y=u(z)使得 h(u(z),z=0. 对上式两边关于之求导得 Back Vyh(u(z);2)Vu(2)+V2h(u(2);2)=0, Close

4/37 JJ II J I Back Close dû(ÿy. e° l 'u z ¶ ∇yh(u(z), z)∇u(z) + ∇zh(u(z), z) = 0

故 Vu(z*）=-HTH (8.3) 在z*附近，由h(u(z),z)=0知z*是无约束优化问题 min f(u(z),2) 2∈Rm-1 的局部极小点，故有 7zf(u(z*),z*)=0, 即 Vu(z)Vyf(y",z*)+V:f(y",z*)=0. 注意到x*=(y*,2*),将(8.3)代入上式得 -H2HVuf(x*)+V2f(x*)=0. Back Close

5/37 JJ II J I Back Close  ∇u(z ∗ ) = −H −T 1 H T 2 . (8.3) 3 z ∗ NC, dh(u(z), z) = 0  z ∗ ¥ÃÂ`zØK min z∈Rn−l f(u(z), z) ¤‹4:, k ∇zf(u(z ∗ ), z∗ ) = 0, = ∇u(z ∗ ) T∇yf(y ∗ , z∗ ) + ∇zf(y ∗ , z∗ ) = 0. 5ø x ∗ = (y ∗ , z∗ ), Ú (8.3) ì\˛™ −H2H −1 1 ∇yf(x ∗ ) + ∇zf(x ∗ ) = 0.

令入*=H1Vf(x*),则有 Vyf(x*)=H1入*，Vzf(x*)=H2入*. 两式合起来即 f(r)= X-∑vh(r） i=1 至此已经证明了定理的结论 为了讨论等式约束问题的二阶必要条件，需要用到(82)定义的 拉格朗日函数L(x,入)的梯度和关于x的Hesse阵.下面，我们计算出 Back Close

6/37 JJ II J I Back Close - λ ∗ = H−1 1 ∇yf(x ∗ ), Kk ∇yf(x ∗ ) = H1λ ∗ , ∇zf(x ∗ ) = H2λ ∗ . ¸™‹Â5= ∇f(x ∗ ) =   ∇yf(x ∗ ) ∇zf(x ∗ )   =   H1 H2   λ ∗ = X l i=1 λi∇hi(x ∗ ). ñdƲy² ½n(ÿ. è ?ÿ™ÂØK7á^á, Iá^ (8.2) ½¬ .ÇKFºÍ L(x, λ) F›⁄'u x  Hesse . e°, ·ÇOé—

它们的表达式如下： L.) (,0=2fa-∑vh 如果目标函数和约束函数都是二阶连续可微的，则可考虑二阶充 分性条件。 定理8.2对于等式约束问题(8.1)，假设f(xc)和h(x)(i=1,2, 都是二阶连续可微的，并且存在(x*,入*)∈R”XR使得VL(x*,入*)= 0.若对任意的0≠d∈Rm,Vh(x*)Td=0(i=1,2,·,l),均有 d严V2L(x*,入*)d>0,则x*是问题(8.1)的一个严格局部极小点 证用反证法.若x*不是严格局部极小点，则必存在邻域N(x*,δ) Back Close

7/37 JJ II J I Back Close ßÇLà™Xe: ∇L(x, λ) =   ∇xL(x, λ) ∇λL(x, λ)   =   ∇f(x) − P l i=1 λi∇hi(x) −h(x)   , ∇2 xxL(x, λ) = ∇2 f(x) − X l i=1 λi∇2hi(x). XJ8IºÍ⁄º͗¥ÎYåá, Kåƒø ©5^á. ½n 8.2 Èu™ÂØK (8.1), b f(x) ⁄ hi(x) (i = 1, 2, · · · , l) —¥ÎYåá, øÖ3 (x ∗ , λ∗ ) ∈ R n ×R l ¶ ∇L(x ∗ , λ∗ ) = 0. eÈ?ø 0 6= d ∈ R n , ∇hi(x ∗ ) T d = 0 (i = 1, 2, · · · , l), ˛k d T∇2 xxL(x ∗ , λ∗ )d > 0, K x ∗ ¥ØK (8.1) òáÓǤ‹4:. y ^áy{. e x ∗ ÿ¥ÓǤ‹4:, K73ç N(x ∗ , δ)

及收敛于c*的序列{xk},使得xk∈N(x*,δ)，xk卡x*,且有 f(c*)≥f(ck),h(xk)=0,i=1,2,·,l,k=1,2, 令ck=x*+Qk,其中ak>0,‖‖=1，序列{(@k,k}有子列收敛 于(0，z*)且lz*‖=1. 由泰勒中值公式得 0=h(x)-h,(x)=a2XVh,(*+0kak2k), 其中0∈(0,1).上式两边同除以α，并令k)0得 Vh(x*Tz*=0,i=1,2,.,l. (8.4) 再由泰勒展开式得 L(EX)=Lr',X)+arV.L(r',X)zx+jojfVL(c,X)sxHol). Back 2 Close

8/37 JJ II J I Back Close 9¬Òu x ∗ S {xk}, ¶ xk ∈ N(x ∗ , δ), xk 6= x ∗ , Ök f(x ∗ ) ≥ f(xk), hi(xk) = 0, i = 1, 2, · · · , l, k = 1, 2, · · · - xk = x ∗ + αkzk, Ÿ• αk > 0, kzkk = 1, S {(αk, zk)} kf¬Ò u (0, z∗ ) Ö kz ∗k = 1. dV•ä˙™ 0 = hi(xk) − hi(x ∗ ) = αkz T k ∇hi(x ∗ + θikαkzk), Ÿ• θik ∈ (0, 1). ˛™¸>”ÿ± αk, ø- k → ∞  ∇hi(x ∗ ) T z ∗ = 0, i = 1, 2, · · · , l. (8.4) 2dV–m™ L(xk, λ∗ ) = L(x ∗ , λ∗ )+αk∇xL(x ∗ , λ∗ ) T zk+ 1 2 α 2 k z T k ∇2 xxL(x ∗ , λ∗ )zk+o(α 2 k )

由于xk都满足等式约束，故有 0≥f(x)-f(x*)=L(ak,入)-L(x*,入*) 2呢4v2Le,'+oa. 上式两边同除以Q/2,可得 vL,+o2a≤0. a 对上式取极限(k→∞)即得 (z*)TV2L(x*,入*)z*≤0. 由于之*满足(8.4)，故得出矛盾.因此x*一定严格局部极小点 Back Close

9/37 JJ II J I Back Close du xk —˜v™Â, k 0 ≥ f(xk) − f(x ∗ ) = L(xk, λ∗ ) − L(x ∗ , λ∗ ) = 1 2 α 2 k z T k ∇2 xxL(x ∗ , λ∗ )zk + o(α 2 k ). ˛™¸>”ÿ± αk/2, å z T k ∇2 xxL(x ∗ , λ∗ )zk + o(2α 2 k ) α 2 k ≤ 0. È˛™4Å (k → ∞) = (z ∗ ) T∇2 xxL(x ∗ , λ∗ )z ∗ ≤ 0. du z ∗ ˜v (8.4), —gÒ. œd x ∗ ò½ÓǤ‹4:.

§8.2不等式约束问题的最优性条件 本小节我们考虑不等式约束优化问题的最优性条件： min f(x), (8.5) s.t.g(c)≥0，i=1,2,·,m. 记可行域为D={x∈R叫g(x)≥0，i=1,2,·,m},指标集I= {1,.,m} 不等式约束问题的最优性条件需要用到所谓的有效约束和非有 效约束的概念.对于一个可行点元，即元∈D.此时可能会出现两 种情形.即有些约束函数满足9（元）=0，而另一些约束函数则满足 9()>0.对于后一种情形，在元的某个邻域内仍然保持：（⑦）>0成 立，而前者则不具备这种性质.因此有必要把这两种情形区分开来 定义8.1若问题(8.5)的一个可行点元∈D使得9（⑦）=0，则 称不等式约束9(x)≥0为元的有效约束.反之，若有9（⑦）>0，则称 Back Close

10/37 JJ II J I Back Close §8.2 ÿ™ÂØKÅ`5^á !·Çƒÿ™Â`zØKÅ`5^á: min f(x), s.t. gi(x) ≥ 0, i = 1, 2, · · · , m. (8.5) På1çè D = {x ∈ R n | gi(x) ≥ 0, i = 1, 2, · · · , m}, çI8 I = {1, · · · , m}. ÿ™ÂØKÅ`5^áIá^§¢kÂ⁄ök ÂVg. Èuòáå1: x¯, = x¯ ∈ D. dûåU¨—y¸ ´ú/. =k º͘v gi(x¯) = 0, ,ò ºÍK˜v gi(¯x) > 0. Èu￾ò´ú/, 3 x¯ ,áçSE,± gi(¯x) > 0 § ·, cˆKÿ‰˘´5ü. œdk7ár˘¸´ú/´©m5. ½¬ 8.1 eØK (8.5) òáå1: x¯ ∈ D ¶ gi(¯x) = 0, K °ÿ™ gi(x) ≥ 0 è x¯ kÂ. áÉ, ek gi(x¯) > 0, K°