库恩塔克条件证明.pdf

1 线性无关约束规范下Kuhn-Tucker 条件的一个简洁证明张忠桢刘燕武约束最优化问题局部极小点的一阶必要条件, 即通常所称的Kuhn-Tucker 条件 , 是最优化领域最重要的研究成果. 性约束的情形很容易直接证明[2, 5], 但是在非线性约束的情形, 其证明很复杂. 例如 [6]p329 有这样一句话 : ” The proof of Theorem 12.1 is quite complex” . 这里的 Theorem 12.1 便是指下面即将证明的定理1. 这一定理假设紧约束(或有效约束 )函数的梯度向量线性无关(LICQ), 由于容易验证而倍受关注, 本文将提供一种简洁的证明. 考虑最优化问题min f(x) s.t. gi(x) = 0, i = 1, 2, ⋯ , l, gi(x) 0, i = l+1, l+2, ⋯, m. (1) 其中 x Rn, f(x)和 g i(x)是实值的至少1 阶可微的函数 . 定理 1 设 x*是(1)的局部极小点, gi(x*) (iEI*)线性无关 , 那么存在实数 i使得f(x*) = *)(*IEiiixg, (2a) i 0, iI*. (2b) 其中 E = {1, 2, ⋯ , l}, I*是关于 x*的紧不等式约束的指标集, 即I* = { i | g i(x*) = 0, i{l+1, l+2, ⋯, m}}. 证 (i) 首先证明 (2a)成立 , 即f(x*)可以表示为gi(x*) (iEI*)的线性组合. 用反证法 , 假设f(x*)不可以表示为gi(x*) (iEI*)的线性组合 . 用 p 表示f(x*)在gi(x*) (iEI*)的零空间上的直交投影, 那么 p0, gi(x)Tp = 0, iEI*, (3) ZTp0, (4) 其中Z 是由gi(x*) (iEI*)的零空间的一组基构成的n | EI*|矩阵 . 考虑方程组F(x, t) )()( *TtpxxZxg=00 , (5) 其中 g(x)是由 gi(x) (iEI*)构成的列向量, t 是实数 . 由于 F(x*, 0) = 0, DxF(x*, 0) = T*)(ZxDg非奇异 , 其中 Dg(x*)是 g(x)在 x*处的 Jacobi 矩阵, 根据隐函数定理[6], 在(x*, 0)的一个邻域内方程组(5)将 x 确定为 t 的(单值 )可微函数x = x(t). 设0}{kkt是任何一个趋于0 的正数序列 . 那么对于充分小的tk, 由(5)确定的解 x = x(tk) x(k)是(1)的可行解 , t = 0 时 x = x*, 并且 x(k)x*, 否则将 (x, t) = (x*, 0)代入 (5)将有 ZTp = 0, 与(4) 矛盾 . 根据隐函数求导法,由(5)可得到2 DxF(x, t)dttdx )(+ttxF),(= 0, 在(x*, 0)处为DxF(x*, 0) dtdx)0(+txF)0,(*= 0. (6) 由于 DxF(x*, 0) = T*)(ZxDg非奇异 , Dg(x*)p = 0 (即(3)式), txF)0,(*= pZT0, 方程组 (6)的唯一解为 dtdx)0(= p. 于是*)(*)( lim xxxxkkk=kkkkktxtxtxtx)0()()0()(lim=dtdxdtdx)0()0(= pp. 在 Taylor 展开式 , f(x(k)) f(x*) = f(x*)T(x(k)x*) + o(|| x(k)x*||). 两边除以 || x(k)x* ||, 取极限 , 考虑到f(x*)Tp = || p ||2 (直交投影的性质), 有*)(*)()()(lim xxxfxfkkk=*)(*)( T*)(lim xxxxxfkkk=f(x*)T pp = || p || 0, 所以当t 是充分小的正数时, x 是(1)的可行解 . 利用隐函数求导法, 由方程组 (8)可得3 DxG(x*, 0)dtdx)0(+txG) 0,(* = 0. (9) 由于 txG) 0,(* =ssspZpxgTT*0)(，spxgDT*)(= 0, 方程组 (9)的唯一解为dtdx)0(= ps. f(x(t))是 t 的一元函数 (t 0, t 充分小 ), f(x(0)) = f(x*). 由于 x*是 f(x)的局部极小点 , 所以0 dtxdf))0((= f(x*)T dtdx)0(= f(x*)Tp s, s I*. 于是i = 2T*||||)(ii ppxf0, i I*. 参 考 文 献[1] 薛嘉庆 . 最优化原理与方法 . 北京 : 冶金工业出版社, 1983. [2] 赵瑞安 , 吴方 . 非线性最优化理论和方法.杭州：浙江科学技术出版社, 1992. [3] 袁亚湘 , 孙文瑜 . 最优化理论与方法. 北京：科学出版社, 2003. [4] 张忠桢 . 线性方程组和线性规划的新算法. 香港中华科技出版社, 1992. [5] 张忠桢 . 二次规划非线性规划与投资组合的算法. 武汉大学出版社, 2006.[6] Jorge Nocedal, Stephen J. Wright. Numerical Optimization ( 数值最优化 ). 北京 : 科学出版社 , 2006. 。