第2章 最優(yōu)化的基本理論和基本方法 最優(yōu)性條件 2.2一般約束優(yōu)化 庫塔定理和庫塔條件

1、o 重點重點學(xué)習(xí)庫恩庫恩-塔克條件塔克條件(Kuhn Tucker, K-T條件)，學(xué)會學(xué)會計算庫恩庫恩-塔克塔克點點(K-T點)。其他次要。 第2章 最優(yōu)化的基礎(chǔ)理論和基本方法2 有約束最優(yōu)化2.2 一般約束情況一般約束情況問題：min f(x), xRn (2-1) st ci(x1, x2, ., xn) = 0, i E ci(x1, x2, ., xn) 0, i I其中E和I分別表示等式和不等式約束的指標(biāo)集, E= 1, 2, ., l I= l+1, l+2, ., l+m E I = （空集）考慮問題的局部解?？紤]最優(yōu)性條件考慮問題的局部解。考慮最優(yōu)性條件。看兩個例子：不等式約

2、束不等式約束。o 例1 min f(x) = x1 + x2 st c1(x) = x12 + x2 2 - 2 0 f(x*) c1(x*)x* f(x)f(x) = x1 + x2 = -2 c1(x)c1(x) 0D:O例例1 min f(x) = x1 + x2 st c1(x) = x12 + x2 2 - 2 0可見滿足： 非負條件非負條件 * 0 叫做松弛互補條件松弛互補條件 對應(yīng)不等式約束。對應(yīng)不等式約束。1. 由圖解法， x*為最優(yōu)解，當(dāng)然也是局部解。局部解。2. 局部解局部解x*在在D的邊界上，約束C1起作用起作用: c1(x*) = 0。 f(x*) + * c1(x*)

3、 =0* 0* c1(x*) = 0 f(x*)=0f(x) = (x1 -1)2 + x22 c1(x*)Dx*O例例2 min f(x) = (x1 -1)2 + x22 st c1(x) = x12 + x2 2 - 2 01. D內(nèi)的點x* = (1,0)T為最優(yōu)解，當(dāng)然也是局部解。局部解。2. 約束C1不起作用不起作用: c1(x*)0。 3. x*是無約束問題局部解。所以：f(x*) =0。 f(x*) + * c1(x*) =0 * = 0 * c1(x*) = 0 滿足非負條件非負條件 滿足松弛互補條件松弛互補條件 對應(yīng)不等式約束。對應(yīng)不等式約束。起作用約束和不起作用約束(對不

4、等式約束)在可行點x處起作用約束起作用約束：使得ci (x) = 0, i I的不等式約束ci(x)。不起作用約束不起作用約束：使得ci(x) 0, i I的不等式約束ci(x)。（這是由局部解的局部性決定的，只考慮x的鄰域。）引入符號I(x)：表示在可行點x處的所有起作用的不等式約束的下標(biāo)，即I(x)=i | iI,ci(x)=0。綜合等式約束、不等式約束情況一般約束優(yōu)化的局部解的必要條件一般約束優(yōu)化的局部解的必要條件庫恩庫恩-塔克定理塔克定理 對于一般約束問題對于一般約束問題(2-1)，設(shè)，設(shè)x=x*為問題的局部解。為問題的局部解。又設(shè)又設(shè)f(x)、 ci(x)在在x*處有連續(xù)偏導(dǎo)數(shù)，處有

5、連續(xù)偏導(dǎo)數(shù)，n維向量維向量組組 ci(x*), i EI(x*) 線性無關(guān)。則存在常數(shù)向量線性無關(guān)。則存在常數(shù)向量 * =( 1*, 2*, , l+m*)T，使如下條件成立：，使如下條件成立：0*)(*)(*)*,(1mliiixxcxfxL,.,2 , 10*)(lEixci,.,2, 10*)(mlllIixciIii 0*Iixcii 0*)(*乘數(shù)。拉imliiixcxfxL, )()(),(1令令說明o 上述5式稱為庫恩庫恩-塔克條件塔克條件(Kuhn-Tucker) ，由二人于1951給出。o 其中的第4式稱為非負條件非負條件，只對不等式約束對應(yīng)只對不等式約束對應(yīng)的拉格朗日乘子的

6、拉格朗日乘子 成立成立。 (等式等式約束對應(yīng)的約束對應(yīng)的 可正可負可正可負，正像在前面等式約束的例題中的那樣) 。o 第5式稱為互補松弛條件互補松弛條件，針對不等式約束的（實際上對等式約束也成立，但把等式情況包括進來是多余的）。o 第1式中的和式對應(yīng)等式約束和不等式約束兩部分.o 滿足庫恩-塔克條件的點x*簡稱為K-T點。點。例 求k-T點(p252),252(01)(09)()(min21222211221薛毅薛毅點。點。的的求約束優(yōu)化問題求約束優(yōu)化問題pTKxxxcxxxcstxxxf) 1()9(),(212221221xxxxxxxL點。唯一的為該問題TK)3, 0(T種情況討論，分為

7、是否求解過程可以按40,該點是問題可能的局部解。該點是問題的最優(yōu)解(下頁圖)(根據(jù)其他方法可知)K-T點：（0，-3）To=0，矛盾方程。，矛盾方程。o=0，必須，必須=-1，不滿足非負條件。，不滿足非負條件。o0，0，由松弛互補條件可解得，由松弛互補條件可解得見書見書p253，這時讓這時讓2L =0的兩個式子相減，可見總是的兩個式子相減，可見總是0 ，不，不滿足非負條件。滿足非負條件。o0，=0，n 有一個（1+ ）x1 = 0，由此只有x1 = 0（否則不滿足非負條件）。n 可知x2= +3或 -3。前者不滿足c2約束。故x2=-3. 所以，x=(0，-3）)T 為該優(yōu)化問題的 K-T點。

8、該點是最優(yōu)解。f=0f=-5對于凸優(yōu)化問題o 定理定理 如果問題(2-1)為一個凸優(yōu)化問題（即 可行域D是凸集，目標(biāo)函數(shù)f是D上的凸函數(shù)），又設(shè)目標(biāo)函數(shù)f(x)和約束函數(shù)ci(x)都存在一階連續(xù)偏導(dǎo)數(shù)，則問題的K-T點是問題的最優(yōu)解。例子：上例。所以，該點是最優(yōu)解。最優(yōu)化的基本理論和基本方法o 5個重要定理最優(yōu)化的基本理論。n 無約束 3個，有約束 2個。n 歷史上的最優(yōu)化3個重要成果。n 凸優(yōu)化：駐點凸優(yōu)化：駐點/K-T點是最優(yōu)解是最優(yōu)解。o 是理論指導(dǎo)和基本方法。n 準(zhǔn)確方法，但不夠?qū)嵱?，對?guī)模大的或復(fù)雜的問題。 （以后將講實用方法，即優(yōu)化算法，為近似方法。）n 有時不能確定是否為局部解（充分條件不滿足時）。費馬定理費馬定理1629拉格朗日定理拉格朗日定理1788庫恩塔克定理庫恩塔克定理1951大約相隔大約相隔150年。年。作業(yè)o求