最优化方法及其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 < n. ÿîòÑ5, å H c l 1§ l f› H1 ¥ö¤.. ‚d, Ú H ©¨è H = H1 H2 . - y = (x1, · · · , xl) T , z = (xl+1, · · · , xn) T , øP h(x) = (h1(x), · · · , hl(x))T . Kk h(y ∗ , z∗ ) = 0, Ö h(y, z) 3: (y ∗ , z∗ ) 'u y Jacobi › HT 1 = ∇yh(y ∗ , z∗ ) å_. d¤ºÍ½nå, 3 z ∗ NC3'u z ÎYåáºÍ y = u(z) ¶ h(u(z), z) = 0. È˛™¸>'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.