库恩塔克条件证明.doc

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