Kuhn-Tucker條件

1、第二章 優(yōu)化設(shè)計(jì)的數(shù)學(xué)基礎(chǔ)機(jī)械設(shè)計(jì)問(wèn)題一般是非線性規(guī)劃問(wèn)題。實(shí)質(zhì)上是多元非線性函數(shù)的極小化問(wèn)題，因此，機(jī)械優(yōu)化設(shè)計(jì)是建立在多元函數(shù)的極值理論基礎(chǔ)上的。機(jī)械優(yōu)化設(shè)計(jì)問(wèn)題分為：無(wú)約束優(yōu)化約束優(yōu)化無(wú)條件極值問(wèn)題條件極值問(wèn)題第一節(jié) 多元函數(shù)的方向?qū)?shù)與梯度一、方向?qū)?shù) 從多元函數(shù)的微分學(xué)得知，對(duì)于一個(gè)連續(xù)可微函數(shù)f(x)在某一點(diǎn) 的一階偏導(dǎo)數(shù)為：( )kx 1()kf xx 2()kf xx ()knf xx，它表示函數(shù)f(x)值在 點(diǎn)沿各坐標(biāo)軸方向的變化率。( )kx有一個(gè)二維函數(shù)，如圖2-1所示。圖2-1 函數(shù)的方向?qū)?shù)其函數(shù)在 點(diǎn)沿d方向的方向?qū)?shù)為 0 x 000(0)112212211,f

2、xx xxf xxxxx1200limxx 00001221222,f xxxf xxxx 001212coscosf xf xxx 000(0)01122120,limfxx xxfxxfxd 二、二元函數(shù)的梯度對(duì)于二維函數(shù)12,f x x在 0 x點(diǎn)處的梯度 000012,Txf xf xf xxx設(shè)12coscosd為d方向的單位向量，則有00Txff xdd 即00Txff xdd 0cos,Tf xf d 三、多元函數(shù)的梯度 000012,.Tnf xf xf xf xxxx沿d方向的方向向量即00Txff xdd 0cos,Tf xf d 12coscos.cosnd圖2-5 梯度

3、方向與等值面的關(guān)系若目標(biāo)函數(shù)f(x)處處存在一階導(dǎo)數(shù)，則極值點(diǎn)的必要條件一階偏導(dǎo)數(shù)等于零，即*0f x滿(mǎn)足此條件僅表明該點(diǎn)為駐點(diǎn)，不能肯定為極值點(diǎn)，即使為極值點(diǎn)，也不能判斷為極大點(diǎn)還是極小點(diǎn)，還得給出極值點(diǎn)的充分條件設(shè)目標(biāo)函數(shù)在 點(diǎn)至少有二階連續(xù)的偏導(dǎo)數(shù)，則*x在這一點(diǎn)的泰勒二次近似展開(kāi)式為：第二節(jié) 多元函數(shù)的泰勒展開(kāi) *2*1,112nniiijjii jiijf xf xf xf xxxxxxxxx x 2222112122222122222212.kkknkkkknkkknnnf xf xf xxx xx xf xf xf xG xx xxx xf xf xf xxxxxx 為N維函數(shù)f

4、(x)在點(diǎn)( )kx處的Hesse矩陣泰勒展開(kāi)寫(xiě)成向量矩陣形式 *12TTfxfxfxxxxxG xxx *0fx *12TfxfxxxG xxx *0f xf x（1） F(X*)=0； 必要條件（2）Hesse矩陣G(X*)為正定。 充分條件多元函數(shù)f(x)在 處取得極值，則極值的條件為*x*x為無(wú)約束極小點(diǎn)的充分條件其Hesse矩陣G(X*)為正定的。則極小點(diǎn)必須滿(mǎn)足*0TxxG xxx為無(wú)約束優(yōu)化問(wèn)題的極值條件同學(xué)考慮二元函數(shù)在 處取得極值的充分必要條件。*x 120fxf xfx10020 xxx02221120222212xffxx xG xffx xx 各階主子式大于零例：求函數(shù)

5、的 極值22121212,425fx xxxxx第四節(jié) 凸集、凸函數(shù)與凸規(guī)劃前面我們根據(jù)函數(shù)極值條件確定了極小點(diǎn)*x則函數(shù)f(x)在 附近的一切x均滿(mǎn)足不等式*x *f xf x所以函數(shù)f(x)在 處取得局部極小值，稱(chēng) 為局部極小點(diǎn)。*x*x而優(yōu)化問(wèn)題一般是要求目標(biāo)函數(shù)在某一區(qū)域內(nèi)的全局極小點(diǎn)。函數(shù)的局部極小點(diǎn)是不是一定是全局極小點(diǎn)呢？圖2-7 下凸的一元函數(shù)一、凸集的線段都全部包含在該集合內(nèi)，就稱(chēng)該點(diǎn)集為凸集，否則為非凸集。一個(gè)點(diǎn)集（或區(qū)域），如果連接其中任意兩點(diǎn)1x2x2x凸集的性質(zhì)二、凸函數(shù)函數(shù)f(x）為凸集定義域內(nèi)的函數(shù)，若對(duì)任何的011x2x及凸集域內(nèi)的任意兩點(diǎn)存在如下不等式： 12

6、1211fxxfxx稱(chēng) f x是定義在凸集上的一個(gè)凸函數(shù)。三、凸性條件1.根據(jù)一階導(dǎo)數(shù)（函數(shù)的梯度）來(lái)判斷函數(shù)的凸性設(shè)f(x)為定義在凸集R上，且具有連續(xù)的一階導(dǎo)數(shù)的函數(shù)，則f(x)在R上為凸函數(shù)的充要條件是對(duì)凸集R內(nèi)任意不同兩點(diǎn) ，不等式1x2x 21211Tf xf xxxf x恒成立。2.根據(jù)二階導(dǎo)數(shù)（ Hesse矩陣)來(lái)判斷函數(shù)的凸性設(shè)f(x)為定義在凸集R上且具有連續(xù)二階導(dǎo)數(shù)的函數(shù)，則f(x)在R上為凸函數(shù)的充要條件Hesse矩陣在R上處處半正定。四、凸規(guī)劃對(duì)于約束優(yōu)化問(wèn)題 min f x.st 0jgx 1,2,.,jm若 f x jgx都為凸函數(shù)，則此問(wèn)題為凸規(guī)劃。凸規(guī)劃的性質(zhì)：

7、1.若給定一點(diǎn) ，則集合0 x 0f xf xRx為凸集。2.可行域 1,2,.,0jjmgxRx為凸集3.凸規(guī)劃的任何局部最優(yōu)解就是全局最優(yōu)解第五節(jié) 等式約束優(yōu)化問(wèn)題的極值條件約束優(yōu)化等式約束不等式約束求解這一問(wèn)題的方法消元法拉格朗日乘子法 min fx.st 0khx 1,2,.,kl1.消元法（降維法）以二元函數(shù)為例討論。二、拉格朗日乘子法（升維法）對(duì)于具有L個(gè)等式約束的n維優(yōu)化問(wèn)題*x處有*0Tdf xf xdx*10lTkkikiihdhxdxhxdxx將原來(lái)的目標(biāo)函數(shù)作如下改造： 1,lkkkF xf xhx拉格朗日函數(shù)待定系數(shù)新目標(biāo)函數(shù)的極值的必要條件0iFx0kF例2-4 用拉

8、格朗日乘子法計(jì)算在約束條件1212,2360h x xxx的情況下，目標(biāo)函數(shù)221212,45f x xxx的極值點(diǎn)坐標(biāo)。第六節(jié) 不等式約束優(yōu)化問(wèn)題的極值條件在工程中大多數(shù)優(yōu)化問(wèn)題，可表示為不等式約束條件的優(yōu)化問(wèn)題。有必要引出非線性?xún)?yōu)化問(wèn)題的重要理論，是不等式約束的多元函數(shù)的極值的必要條件。庫(kù)恩-塔克（Kuhn-Tucker）條件一、一元函數(shù)在給定區(qū)間上的極值條件一元函數(shù)f(x)在給定區(qū)間a,b上的極值問(wèn)題，可以寫(xiě)成下列具有不等式約束條件的優(yōu)化問(wèn)題： min f x.st 10gxax 20gxxb拉格朗日乘子法，除了可以應(yīng)用于等式的極值問(wèn)題，還可以用于不等式的極值問(wèn)題。需引入松弛變量，將不等

9、式約束變成等式約束。設(shè)a1和b1為兩個(gè)松弛變量，則上述的不等式約束可寫(xiě)為： 2211111,0h x agxaaxa 2221211,0hx bgxbxbb 則該問(wèn)題的拉格朗日函數(shù) 11121 11221,F x a bf xh x ahx b 221121f xaxaxbb1020根據(jù)拉格朗日乘子法，此問(wèn)題的極值條件：1212120dgdgFfdfxxdxdxdx1 1120Fbb1 1120Faa 221212,0Fhx bgxb 211111,0Fh x agxa由1 10a110,0a110,0a 10gxax（起作用約束） 10gxax（不起作用約束）同樣 ，來(lái)分析 起作用何不起作用

10、約束。2 10b 2gx因此，一元函數(shù)在給定區(qū)間的極值條件，可以表示為：12120dgdgdfdxdxdx 220gx 110gx1020多元庫(kù)恩-塔克條件1212120dgdgdfdfdxdxdxdx分析極值點(diǎn) 在區(qū)間的位置，有三種情況*x當(dāng)*axb時(shí)，此時(shí)120，則極值條件為*0dfxdx當(dāng)*xa時(shí)，此時(shí)120,0則極值條件為10dfdx即*0df xdx當(dāng)*xb時(shí) ，此時(shí)120,0，則極值條件為20dfdx*0df xdx即從以上分析可以看出，對(duì)應(yīng)于不起作用的約束的拉格朗日乘子取零值，因此可以引入起作用約束的下標(biāo)集合。 0,1,2jgxjJ xj一元函數(shù)在給定區(qū)間的極值條件，可以改寫(xiě)為：

11、極值條件中只考慮起作用的約束和相應(yīng)的乘子。 000jjj JjjdgdfdxdxgxjJjJ二、庫(kù)恩-塔克條件仿照一元函數(shù)給定區(qū)間上極值條件的推導(dǎo)過(guò)程，可以得到具有不等式約束多元函數(shù)極值條件： *101,2,.,01,2,.,01,2,.,mjjjiijjjdf xdgxindxdxgxjmjm用起作用約束的下標(biāo)集合表示*01,2,.,00jjj Jiijjdf xdgxindxdxgxjJjJ用梯度形式表示，可得*0jjj Jf xgx或*jjj Jf xgx庫(kù)恩-塔克條件的幾何意義：在約束極小點(diǎn)處，函數(shù)的負(fù)梯度一定能表示成所有起作用約束在該點(diǎn)梯度的非負(fù)線性組合。下面以二維問(wèn)題為例，說(shuō)明K-T