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

1、o 重點(diǎn)重點(diǎn)學(xué)習(xí)庫(kù)恩庫(kù)恩-塔克條件塔克條件(Kuhn Tucker, K-T條件)，學(xué)會(huì)學(xué)會(huì)計(jì)算庫(kù)恩庫(kù)恩-塔克塔克點(diǎn)點(diǎn)(K-T點(diǎn))。其他次要。 第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)性條件。看兩個(gè)例子：不等式約

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可見滿足： 非負(fù)條件非負(fù)條件 * 0 叫做松弛互補(bǔ)條件松弛互補(bǔ)條件 對(duì)應(yīng)不等式約束。對(duì)應(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)的點(diǎn)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 滿足非負(fù)條件非負(fù)條件 滿足松弛互補(bǔ)條件松弛互補(bǔ)條件 對(duì)應(yīng)不等式約束。對(duì)應(yīng)不等式約束。起作用約束和不起作用約束(對(duì)不

4、等式約束)在可行點(diǎn)x處起作用約束起作用約束：使得ci (x) = 0, i I的不等式約束ci(x)。不起作用約束不起作用約束：使得ci(x) 0, i I的不等式約束ci(x)。（這是由局部解的局部性決定的，只考慮x的鄰域。）引入符號(hào)I(x)：表示在可行點(diǎn)x處的所有起作用的不等式約束的下標(biāo)，即I(x)=i | iI,ci(x)=0。綜合等式約束、不等式約束情況一般約束優(yōu)化的局部解的必要條件一般約束優(yōu)化的局部解的必要條件庫(kù)恩庫(kù)恩-塔克定理塔克定理 對(duì)于一般約束問題對(duì)于一般約束問題(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式稱為庫(kù)恩庫(kù)恩-塔克條件塔克條件(Kuhn-Tucker) ，由二人于1951給出。o 其中的第4式稱為非負(fù)條件非負(fù)條件，只對(duì)不等式約束對(duì)應(yīng)只對(duì)不等式約束對(duì)應(yīng)的拉格朗日乘子的

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

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

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