庫恩塔克條件證明

1、-作者xxxx-日期xxxx庫恩塔克條件證明【精品文檔】線性無關(guān)約束規(guī)范下Kuhn-Tucker條件的一個(gè)簡潔證明張忠楨 劉燕武約束最優(yōu)化問題局部極小點(diǎn)的一階必要條件, 即通常所稱的Kuhn-Tucker條件, 是最優(yōu)化領(lǐng)域最重要的研究成果. 在線性約束的情形很容易直接證明2, 5, 但是在非線性約束的情形, 其證明很復(fù)雜. 例如6p329有這樣一句話: ”The proof of Theorem 12.1 is quite complex”. 這里的Theorem 12.1便是指下面即將證明的定理1. 這一定理假設(shè)緊約束(或有效約束)函數(shù)的梯度向量線性無關(guān)(LICQ), 由于容易驗(yàn)證而倍受關(guān)

2、注, 本文將提供一種簡潔的證明.考慮最優(yōu)化問題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)是實(shí)值的至少1階可微的函數(shù).定理1 設(shè)x*是(1)的局部極小點(diǎn), gi(x*) (iEI*)線性無關(guān), 那么存在實(shí)數(shù)li使得f(x*) = , (2a)li 0, i I*. (2b)其中E = 1, 2, , l, I*是關(guān)于x*的緊不等式約束的指標(biāo)集, 即I* = i | gi(x*) = 0, i l+1, l+2, , m.證 (i) 首先證明(2a)成立, 即f(x*

3、)可以表示為gi(x*) (iEI*)的線性組合. 用反證法, 假設(shè)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*)的零空間的一組基構(gòu)成的n| EI*|矩陣.考慮方程組F(x, t) =, (5)其中g(shù)(x)是由gi(x) (iEI*)構(gòu)成的列向量, t是實(shí)數(shù).由于F(x*, 0) = 0, DxF(x*, 0) = 非奇異, 其中Dg(x*)是g(x)在x*處的Jacobi矩陣, 根據(jù)隱函數(shù)定理6

4、, 在(x*, 0)的一個(gè)鄰域內(nèi)方程組(5)將x確定為t的(單值)可微函數(shù)x = x(t). 設(shè)是任何一個(gè)趨于0的正數(shù)序列. 那么對(duì)于充分小的tk, 由(5)確定的解x = x(tk) x(k)是(1)的可行解, t = 0時(shí)x = x*, 并且x(k) x*, 否則將(x, t) = (x*, 0)代入(5)將有ZTp = 0, 與(4)矛盾.根據(jù)隱函數(shù)求導(dǎo)法,由(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 (直交投影的性質(zhì)), 有=f(x*)T = -| p | 0.所以對(duì)于充分接近x*的x(k)有f(x(k) 0, 所以當(dāng) t 是充分小的正數(shù)時(shí), x是(1)的可行解. 利用隱函數(shù)求導(dǎo)法, 由方程組(8)可得DxG(x*, 0)+ = 0. (9)由于=，= 0, 方程組(9)的唯一解為= ps. f(x(t)是t的一元函數(shù)(t 0, t充分小), f(x(0) = f(x*). 由于x*是f(x)的局部極小點(diǎn), 所以0 = f(x*)T= f(x*)Tps, sI*.于是li = 0, i I*. 參 考 文 獻(xiàn)1 薛嘉慶. 最優(yōu)化原理與方法. 北京: 冶金工業(yè)出版社, 1983.2 趙瑞安, 吳方. 非線性最優(yōu)化理論和方法. 杭州：浙江科學(xué)技術(shù)出版社, 1992.3 袁亞湘, 孫文瑜. 最優(yōu)化理論與方法. 北京：科學(xué)出版社, 2003.4 張忠楨. 線性方程組和線性規(guī)劃的新算法. 香港中華科技出版社, 1992.5 張忠楨. 二次規(guī)劃非線性規(guī)劃與投資組合的算法. 武漢大學(xué)出版社, 200