库恩塔克条件证明

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

2、(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*) (iÎEÈI*)线性无关, 那么存在实数li使得Ñf(x*) = , (2a)li ³ 0, i Î I*. (2b)其中E = 1, 2, , l, I*是关于x*的紧不等式约束的指标集, 即I* = i | gi(x*) = 0, i Îl+1, l+

3、2, , m.证 (i) 首先证明(2a)成立, 即Ñf(x*)可以表示为Ñgi(x*) (iÎEÈI*)的线性组合. 用反证法, 假设Ñf(x*)不可以表示为Ñgi(x*) (iÎEÈI*)的线性组合. 用p表示Ñf(x*)在Ñgi(x*) (iÎEÈI*)的零空间上的直交投影, 那么p ¹ 0,Ñgi(x)Tp = 0, iÎEÈI*, (3)ZTp ¹ 0, (4)其中 Z是由Ñgi(x*) (iÎE

4、ÈI*)的零空间的一组基构成的n´| EÈI*|矩阵.考虑方程组F(x, t) º =, (5)其中g(x)是由gi(x) (iÎEÈI*)构成的列向量, t是实数.由于F(x*, 0) = 0, DxF(x*, 0) = 非奇异, 其中Dg(x*)是g(x)在x*处的Jacobi矩阵, 根据隐函数定理6, 在(x*, 0)的一个邻域内方程组(5)将x确定为t的(单值)可微函数x = x(t). 设是任何一个趋于0的正数序列. 那么对于充分小的tk, 由(5)确定的解x = x(tk) º x(k)是(1)的可行解, t =

5、 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. 于是= .在Taylor展开式,f(x(k) - f(x*) = Ñf(x*)T(x(k) - x*) + o(| x(k) - x* |).两边除以| x(k) - x* |, 取极限, 考虑到

6、09;f(x*)Tp = | p |2 (直交投影的性质), 有=Ñf(x*)T = -| p | < 0.所以对于充分接近x*的x(k)有f(x(k) < f(x*), 这与x*是(1)的局部极小点相矛盾. (ii) 证明(2b)成立. 根据4p27定理6，(2a)中的 li = , i Î E È I*. (7)其中pi是Ñgi(x*)在零空间x Î Rn | Ñgj(x*)Tx = 0, j Î EÈI*i上的直交投影, | · |为欧氏范数. 由于Ñgi(x*) (i

7、6;EÈI*)线性无关, | pi | ¹ 0, i Î E È I*.对于任一sÎI*, 用表示gi(x) (iÎEÈI*s)构成的列向量; 仍用Z表示Ñgi(x*) (iÎEÈI*)的零空间的一组基构成的n´| EÈI*| 矩阵. 考虑方程组G(x, t) º =, (8)由于G(x*, 0) = 0, DxG(x*, 0) = 非奇异, 根据隐函数定理, 在(x*, 0)的一个邻域内, 方程组(8)将x确定为t的可微函数x = x(t). 根据直交投影的性质,

8、 (8)中的Ñgs(x*)Tps = | ps |2 > 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, sÎI*.于是li = ³ 0, i Î I*. 参 考 文 献1 薛嘉庆. 最优化原理与方法. 北京: 冶金工业出版社, 1983.2 赵瑞安, 吴方. 非线性最优化理论和方法. 杭州：浙江科学技术出版社, 1992.3 袁亚湘, 孙文瑜. 最优化理论与方法. 北京：科学出版社, 2003.4 张忠桢. 线性方程组和线性规划的新算法. 香港中华科技出版社, 1992.5 张