库恩塔克条件证明

1、-作者xxxx-日期xxxx库恩塔克条件证明【精品文档】线性无关约束规范下Kuhn-Tucker条件的一个简洁证明张忠桢 刘燕武约束最优化问题局部极小点的一阶必要条件, 即通常所称的Kuhn-Tucker条件, 是最优化领域最重要的研究成果. 在线性约束的情形很容易直接证明2, 5, 但是在非线性约束的情形, 其证明很复杂. 例如6p329有这样一句话: ”The proof of Theorem 12.1 is quite complex”. 这里的Theorem 12.1便是指下面即将证明的定理1. 这一定理假设紧约束(或有效约束)函数的梯度向量线性无关(LICQ), 由于容易验证而倍受关

2、注, 本文将提供一种简洁的证明.考虑最优化问题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)和gi(x)是实值的至少1阶可微的函数.定理1 设x*是(1)的局部极小点, gi(x*) (iEI*)线性无关, 那么存在实数li使得f(x*) = , (2a)li 0, i I*. (2b)其中E = 1, 2, , l, I*是关于x*的紧不等式约束的指标集, 即I* = i | gi(x*) = 0, i l+1, l+2, , m.证 (i) 首先证明(2a)成立, 即f(x*

3、)可以表示为gi(x*) (iEI*)的线性组合. 用反证法, 假设f(x*)不可以表示为gi(x*) (iEI*)的线性组合. 用p表示f(x*)在gi(x*) (iEI*)的零空间上的直交投影, 那么p 0,gi(x)Tp = 0, iEI*, (3)ZTp 0, (4)其中 Z是由gi(x*) (iEI*)的零空间的一组基构成的n| EI*|矩阵.考虑方程组F(x, t) =, (5)其中g(x)是由gi(x) (iEI*)构成的列向量, t是实数.由于F(x*, 0) = 0, DxF(x*, 0) = 非奇异, 其中Dg(x*)是g(x)在x*处的Jacobi矩阵, 根据隐函数定理6

4、, 在(x*, 0)的一个邻域内方程组(5)将x确定为t的(单值)可微函数x = x(t). 设是任何一个趋于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)可得到DxF(x, t)+ = 0,在(x*, 0)处为DxF(x*, 0)+ = 0. (6)由于DxF(x*, 0) = 非奇异, Dg(x*)p = 0 (即(3)式), = , 方程组(6)的唯一解为= -p. 于是=

5、 .在Taylor展开式,f(x(k) - f(x*) = f(x*)T(x(k) - x*) + o(| x(k) - x* |).两边除以| x(k) - x* |, 取极限, 考虑到f(x*)Tp = | p |2 (直交投影的性质), 有=f(x*)T = -| p | 0.所以对于充分接近x*的x(k)有f(x(k) 0, 所以当 t 是充分小的正数时, x是(1)的可行解. 利用隐函数求导法, 由方程组(8)可得DxG(x*, 0)+ = 0. (9)由于=，= 0, 方程组(9)的唯一解为= ps. f(x(t)是t的一元函数(t 0, t充分小), f(x(0) = f(x*). 由于x*是f(x)的局部极小点, 所以0 = f(x*)T= f(x*)Tps, sI*.于是li = 0, i I*. 参 考 文 献1 薛嘉庆. 最优化原理与方法. 北京: 冶金工业出版社, 1983.2 赵瑞安, 吴方. 非线性最优化理论和方法. 杭州：浙江科学技术出版社, 1992.3 袁亚湘, 孙文瑜. 最优化理论与方法. 北京：科学出版社, 2003.4 张忠桢. 线性方程组和线性规划的新算法. 香港中华科技出版社, 1992.5 张忠桢. 二次规划非线性规划与投资组合的算法. 武汉大学出版社, 200