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