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

重點(diǎn)學(xué)習(xí)庫(kù)恩-塔克條件(Kuhn–Tucker,K-T條件)，學(xué)會(huì)計(jì)算庫(kù)恩-塔克點(diǎn)(K-T點(diǎn))。其他次要。第2章最優(yōu)化的基礎(chǔ)理論和基本方法

§2有約束最優(yōu)化

§2.2一般約束情況問題：minf(x),x∈Rn

(2-1)stci(x1,x2,...,xn)=0,iEci(x1,x2,...,xn)0,iI其中E和I分別表示等式和不等式約束的指標(biāo)集,

E={1,2,...,l}I={l+1,l+2,...,l+m}EI=

（空集）考慮問題的局部解?？紤]最優(yōu)性條件。看兩個(gè)例子：不等式約束。例1minf(x)=x1+x2

stc1(x)=x12

+x22-

2

≤0f(x*)c1(x*)x*f(x)f(x)=x1+x2=-2c1(x)c1(x)≤0D:O例1minf(x)=x1+x2

stc1(x)=x12

+x22-

2

≤0可見滿足：

非負(fù)條件λ*≥0

叫做松弛互補(bǔ)條件—對(duì)應(yīng)不等式約束。1.由圖解法，x*為最優(yōu)解，當(dāng)然也是局部解。2.局部解x*在D的邊界上，約束C1起作用:c1(x*)=0。f(x*)+λ*

c1(x*)=0λ*>0λ*

c1(x*)=0f(x*)=0f(x)=

(x1-1)2

+x22

c1(x*)Dx*O例2minf(x)=(x1-1)2

+x22

stc1(x)=x12

+x22-

2

≤01.D內(nèi)的點(diǎn)x*=(1,0)T為最優(yōu)解，當(dāng)然也是局部解。2.約束C1不起作用:c1(x*)<0。3.x*是無(wú)約束問題局部解。所以：f(x*)=0。f(x*)+λ*

c1(x*)=0

λ*=0

λ*

c1(x*)=0

滿足非負(fù)條件滿足松弛互補(bǔ)條件—對(duì)應(yīng)不等式約束。起作用約束和不起作用約束(對(duì)不等式約束)在可行點(diǎn)x處起作用約束：使得ci(x)=0,iI的不等式約束ci(x)。不起作用約束：使得ci(x)<0,iI的不等式約束ci(x)。（這是由局部解的局部性決定的，只考慮x的鄰域。）引入符號(hào)I(x)：表示在可行點(diǎn)x處的所有起作用的不等式約束的下標(biāo)，即I(x)={i|i∈I,ci(x)=0}。綜合等式約束、不等式約束情況

一般約束優(yōu)化的局部解的必要條件庫(kù)恩-塔克定理

對(duì)于一般約束問題(2-1)，設(shè)x=x*為問題的局部解。又設(shè)f(x)、ci(x)在x*處有連續(xù)偏導(dǎo)數(shù)，n維向量組ci(x*),iE∪I(x*)線性無(wú)關(guān)。則存在常數(shù)向量*=(1*,2*,…,l+m*)T，使如下條件成立：令說(shuō)明上述5式稱為庫(kù)恩-塔克條件(Kuhn-Tucker)

，由二人于1951給出。其中的第4式稱為非負(fù)條件，只對(duì)不等式約束對(duì)應(yīng)的拉格朗日乘子成立。(等式約束對(duì)應(yīng)的可正可負(fù)，正像在前面等式約束的例題中的那樣)。第5式稱為互補(bǔ)松弛條件，針對(duì)不等式約束的（實(shí)際上對(duì)等式約束也成立，但把等式情況包括進(jìn)來(lái)是多余的）。第1式中的和式對(duì)應(yīng)等式約束和不等式約束兩部分.滿足庫(kù)恩-塔克條件的點(diǎn)x*簡(jiǎn)稱為K-T點(diǎn)。例求k-T點(diǎn)(p252)該點(diǎn)是問題可能的局部解。該點(diǎn)是問題的最優(yōu)解(下頁(yè)圖)(根據(jù)其他方法可知)K-T點(diǎn)：（0，-3）Tλ=μ=0，矛盾方程。λ=0，必須μ=-1，不滿足非負(fù)條件。λ≠0，μ≠0，由松弛互補(bǔ)條件可解得—見書p253，這時(shí)讓2L

=0的兩個(gè)式子相減，可見總是λ<0，不滿足非負(fù)條件。λ≠0，μ=0，有一個(gè)（1+λ

）x1=0，由此只有x1=0（否則不滿足非負(fù)條件）?？芍獂2=+3或-3。前者不滿足c2約束。故x2=-3.所以，x=(0，-3）)T為該優(yōu)化問題的K-T點(diǎn)。該點(diǎn)是最優(yōu)解。f=0f=-5對(duì)于凸優(yōu)化問題定理如果問題(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)化的基本理論和基本方法5個(gè)重要定理—最優(yōu)化的基本理論。無(wú)約束3個(gè)，有約束2個(gè)。歷史上的最優(yōu)化3個(gè)重要成果。凸優(yōu)化：駐點(diǎn)/K-T點(diǎn)是最優(yōu)解。是理論指導(dǎo)和基本方法。準(zhǔn)確方法，但不夠?qū)嵱?，?duì)規(guī)模大的或復(fù)雜的問題。（以后將講實(shí)用方法，即優(yōu)化算法，為近似方法。）有時(shí)不能確定是否為局部解（充分條件不滿足時(shí)）。費(fèi)馬定理1629拉格朗日定理1788庫(kù)恩塔克定理1951大約相隔150年。作業(yè)求K-T點(diǎn)：minx12+x22-14x1-6x2-7s