最優(yōu)化問題的其他主題

最優(yōu)化問題的其他主題第1頁，共47頁，2023年，2月20日，星期五第一節(jié)帶不等式約束的極值問題

——庫恩-塔克條件

研究目標(biāo)函數(shù)在帶有等式和不等式約束條件下最優(yōu)化的數(shù)學(xué)分支稱為數(shù)學(xué)規(guī)劃。數(shù)學(xué)規(guī)劃可分為兩類：目標(biāo)函數(shù)及約束條件均為線性方程時(shí)，稱為線性規(guī)劃；目標(biāo)函數(shù)或約束條件中出現(xiàn)非線性方程時(shí)，稱為非線性規(guī)劃。第2頁，共47頁，2023年，2月20日，星期五一、變量非負(fù)性約束條件下單變量函數(shù)的最值問題或第3頁，共47頁，2023年，2月20日，星期五情形2：且情形1：且情形3：且第4頁，共47頁，2023年，2月20日，星期五若為方程的解，如下三個(gè)條件成立：條件1條件2條件3這為

取得極大值的一階條件，并稱此一階條件為該問題的Kuhn-Tucker條件（簡稱K－T條件）。第5頁，共47頁，2023年，2月20日，星期五情形2：且情形1：且情形3：且第6頁，共47頁，2023年，2月20日，星期五若為方程的解，如下三個(gè)條件成立：條件1條件2條件3這為

取得極小值的一階條件，并稱此一階條件為該問題的Kuhn-Tucker條件（簡稱K－T條件）。第7頁，共47頁，2023年，2月20日，星期五例：考慮問題解：若為方程的解，必滿足：條件1條件2條件3解得：第8頁，共47頁，2023年，2月20日，星期五二、不等式約束效應(yīng)為簡單起見，首先討論三個(gè)選擇變量和兩個(gè)約束條件的情況：利用兩個(gè)虛擬變量和，可把上述問題轉(zhuǎn)變?yōu)榈葍r(jià)的形式：第9頁，共47頁，2023年，2月20日，星期五如果沒有非負(fù)約束，與等式約束的解法一樣：作出拉格朗日函數(shù)：寫出一階條件為：第10頁，共47頁，2023年，2月20日，星期五但因?yàn)樽兞亢捅仨殲榉秦?fù)，因此，對(duì)于這些變量的一階條件應(yīng)當(dāng)按照非負(fù)實(shí)值約束的實(shí)值函數(shù)的最優(yōu)化條件加以修正：注意，導(dǎo)致仍被確定為零。（為什么？）拉格朗日函數(shù)：第11頁，共47頁，2023年，2月20日，星期五由于,第二行變?yōu)椋河忠驗(yàn)榈谌?，把該式代入上式，第二行和第三行合并為：不用虛擬變量可以把一階條件用等價(jià)形式表示出來：以上一階條件：第12頁，共47頁，2023年，2月20日，星期五忽略了非負(fù)限制和約束中的不等式，寫出拉格朗日函數(shù)Z的純古典形式：我們規(guī)定：（1）偏導(dǎo)數(shù)，但（2）對(duì)和加上非負(fù)限制；（3）要求每個(gè)變量和對(duì)該變量的偏導(dǎo)數(shù)之間有互補(bǔ)松弛條件，即要求它們的積為零。則：第13頁，共47頁，2023年，2月20日，星期五三、n個(gè)變量m個(gè)約束的情況拉格朗日函數(shù)以下列更為一般的形式出現(xiàn)：庫恩-塔克條件的極大化形式：庫恩-塔克條件的極小化形式：第14頁，共47頁，2023年，2月20日，星期五四個(gè)非負(fù)條件：四個(gè)互補(bǔ)松弛條件：一階條件的解為：解：它包含四個(gè)邊際條件：例1解最小化問題第15頁，共47頁，2023年，2月20日，星期五第二節(jié)約束規(guī)范只有滿足特定條件時(shí)，庫恩-塔克條件才是必要條件，這條件叫做約束規(guī)范（Constraintqualification）。約束規(guī)范是對(duì)非線性規(guī)劃中的約束函數(shù)施加的某些限制，目的是為了排除可行集邊界上的某些不規(guī)則性，這些不規(guī)則性可能會(huì)違背能夠產(chǎn)生最優(yōu)解的庫恩-塔克條件。第16頁，共47頁，2023年，2月20日，星期五例1

要使x1最大,最優(yōu)解（1,0）,但是該解不滿足庫恩-塔克條件。

為了檢驗(yàn)這一點(diǎn)，我們可以寫出拉格朗日函數(shù)：

作為第一邊際條件，我們得到：

把（1，0）代入得，不滿足庫恩-塔克條件。第17頁，共47頁，2023年，2月20日，星期五第18頁，共47頁，2023年，2月20日，星期五例2對(duì)于例1，附加新的約束條件：寫出新的拉格朗日函數(shù)：邊際條件為：歧點(diǎn)滿足以上邊際條件、非負(fù)條件和互補(bǔ)松馳條件。說明盡管存在歧點(diǎn)，庫恩-塔克條件仍可以成立。例1第19頁，共47頁，2023年，2月20日，星期五測(cè)試向量的定義令是可行區(qū)域邊界上的一個(gè)（可能的解）點(diǎn)，并令表示由所提到的邊界點(diǎn)移動(dòng)的特定方向。令如果向量滿足以下兩個(gè)條件，則稱為測(cè)試向量：第一，如果第j個(gè)選擇變量在點(diǎn)取零值，那么只允許在軸上有非負(fù)變化，即：第二，如果在點(diǎn)處恰好滿足第i個(gè)約束條件的等式約束，那么只允許的取值使約束函數(shù)值不增加（對(duì)極大化問題）或不減少（對(duì)極小化問題），即：第20頁，共47頁，2023年，2月20日，星期五規(guī)范弧的定義如果滿足下列條件的可微弧，稱為該測(cè)試向量的規(guī)范弧：（1）從點(diǎn)出發(fā)；（2）整個(gè)包含在可行區(qū)域內(nèi)；（3）與已知測(cè)試向量相切。如果對(duì)可行區(qū)域邊界上的任意點(diǎn)，對(duì)每一測(cè)試向量，存在一規(guī)范弧，那么，就滿足約束規(guī)范。第21頁，共47頁，2023年，2月20日，星期五在該點(diǎn)，于是測(cè)試向量滿足①在點(diǎn)（1，0），唯一約束條件的等式恰好得到滿足，所以：綜合①和②，得。②另外，取值可為任意值。我們選，該測(cè)試向量存在規(guī)范弧。我們選，該測(cè)試向量不存在規(guī)范弧。例1的最優(yōu)點(diǎn)（1，0）不滿足庫恩-塔克條件，也不滿足約束規(guī)范。例1第22頁，共47頁，2023年，2月20日，星期五第23頁，共47頁，2023年，2月20日，星期五在連續(xù)可微的情況下，一階微分等于零是極值的一階必要條件。在存在間斷點(diǎn)的情況下，一階微分等于零不是極值的一階必要條件。滿足約束規(guī)范，庫恩-塔克條件是極值的必要條件。不滿足約束規(guī)范，庫恩-塔克條件不是極值的必要條件。不等式約束最優(yōu)化無約束最優(yōu)化第24頁，共47頁，2023年，2月20日，星期五線性約束條件如果可行區(qū)域是僅由線性約束形成的凸集，那么約束規(guī)范總是滿足，且?guī)於?塔克條件在最優(yōu)解處成立，即庫恩-塔克條件是必要條件。第25頁，共47頁，2023年，2月20日，星期五以上討論了非線性規(guī)劃中極大值或極小值的必要條件。如果某點(diǎn)滿足必要條件，我們不能作出是最優(yōu)解和結(jié)論；如果某點(diǎn)不滿足必要條件，則該點(diǎn)不可能是最優(yōu)解。如果點(diǎn)滿足極大值的最優(yōu)條件，那么該點(diǎn)必使目標(biāo)函數(shù)達(dá)到極大值。但是充分條件也有自己的缺點(diǎn)，即充分條件本身可能不是必要條件，因而真正的最優(yōu)解仍然可以不滿足這個(gè)充分條件。第三節(jié)非線性規(guī)劃的充分性定理第26頁，共47頁，2023年，2月20日，星期五(a)目標(biāo)函數(shù)在非負(fù)正交分劃體中可微，且為凹函數(shù)；(b)每個(gè)約束函數(shù)在非負(fù)正交分劃體中可微，且為凸函數(shù)；(c)點(diǎn)滿足庫恩-塔克極大化條件。那么，為的整體極大值點(diǎn)。給定非線性規(guī)劃：二、庫恩-塔克充分性定理：凹規(guī)劃（極大值）第27頁，共47頁，2023年，2月20日，星期五(a)目標(biāo)函數(shù)在非負(fù)正交分劃體中可微，且為凸函數(shù)；(b)每個(gè)約束函數(shù)在非負(fù)正交分劃體中可微，且為凹函數(shù)；(c)點(diǎn)滿足庫恩-塔克極小化條件。那么，為的整體極小值點(diǎn)。給定非線性規(guī)劃：二、庫恩-塔克充分性定理：凹規(guī)劃（極小值）第28頁，共47頁，2023年，2月20日，星期五我們可以得到結(jié)論：如果給定條件(a)和(b)，那么庫恩-塔克條件就是極大值（極小值）的充分條件。當(dāng)滿足約束規(guī)范時(shí)，庫恩-塔克條件就是極大值（極小值）的必要條件。如果滿足約束規(guī)范，且實(shí)現(xiàn)條件(a)和(b)，那么庫恩-塔克條件就是極大值（極小值）的充分必要條件。第29頁，共47頁，2023年，2月20日，星期五庫恩-塔克充分性定理的證明因?yàn)闉榘己瘮?shù)，每個(gè)為凸函數(shù)，而每個(gè)為凹函數(shù)，因此為凹函數(shù)。凹函數(shù)存在以下性質(zhì)：對(duì)于極大化問題，拉格朗日函數(shù)表示為：第30頁，共47頁，2023年，2月20日，星期五庫恩-塔克充分性定理的證明（續(xù)）把表達(dá)式分為兩項(xiàng)。和對(duì)于，可以選擇和滿足庫恩-塔克條件，從而：，對(duì)于來說，第31頁，共47頁，2023年，2月20日，星期五所以表示為：庫恩-塔克充分性定理的證明（續(xù)）因?yàn)楦鶕?jù)庫恩-塔克條件，得：又因?yàn)樗缘玫?，即點(diǎn)是極大值。第32頁，共47頁，2023年，2月20日，星期五二、阿羅-恩索文充分性定理：擬凹規(guī)劃(b)在非負(fù)正交規(guī)劃體中每個(gè)約束函數(shù)可微且為擬凸函數(shù)；(c)點(diǎn)滿足庫恩-塔克極大化條件。那么，為的整體極大值點(diǎn)。(d)滿足下列諸條件中任意一個(gè)：給定非線性規(guī)劃：(a)在非負(fù)正交規(guī)劃體中可微且為擬凹函數(shù)；(d-i)至少對(duì)某個(gè)變量有。(d-ii)對(duì)某個(gè)可取正值而不違背約束的變量有。(d-iii)n個(gè)導(dǎo)數(shù)不全為零，函數(shù)在的鄰域內(nèi)二階可微。第33頁，共47頁，2023年，2月20日，星期五二、阿羅-恩索文充分性定理：擬凹規(guī)劃(b)在非負(fù)正交規(guī)劃體中每個(gè)約束函數(shù)可微且為擬凹函數(shù)；(c)點(diǎn)滿足庫恩-塔克極小化條件。那么，為的整體極小值點(diǎn)。(d)滿足下列諸條件中任意一個(gè)：給定非線性規(guī)劃：(a)在非負(fù)正交規(guī)劃體中可微且為擬凸函數(shù)；(d-i)至少對(duì)某個(gè)變量有。(d-ii)對(duì)某個(gè)可取正值而不違背約束的變量有。(d-iii)n個(gè)導(dǎo)數(shù)不全為零，函數(shù)在的鄰域內(nèi)二階可微。第34頁，共47頁，2023年，2月20日，星期五我們可以得到結(jié)論：如果給定條件(a)、(b)和(d)，那么庫恩-塔克條件就是極大值（極小值）的充分條件。當(dāng)滿足約束規(guī)范時(shí)，庫恩-塔克條件就是極大值（極小值）的必要條件。如果滿足約束規(guī)范，且實(shí)現(xiàn)條件(a)、(b)和(d)，那么庫恩-塔克條件就是極大值（極小值）的充分必要條件。第35頁，共47頁，2023年，2月20日，星期五本章小結(jié)第36頁，共47頁，2023年，2月20日，星期五一、庫恩-塔克條件（n個(gè)變量m個(gè)約束）拉格朗日函數(shù)以下列更為一般的形式出現(xiàn)：庫恩-塔克條件的極大化形式：庫恩-塔克條件的極小化形式：第37頁，共47頁，2023年，2月20日，星期五(a)目標(biāo)函數(shù)在非負(fù)正交分劃體中可微，且為凹函數(shù)；(b)每個(gè)約束函數(shù)在非負(fù)正交分劃體中可微，且為凸函數(shù)；(c)點(diǎn)滿足庫恩-塔克極大化條件。那么，為的整體極大值點(diǎn)。給定非線性規(guī)劃：二、庫恩-塔克充分性定理：凹規(guī)劃（極大值）第38頁，共47頁，2023年，2月20日，星期五(a)目標(biāo)函數(shù)在非負(fù)正交分劃體中可微，且為凸函數(shù)；(b)每個(gè)約束函數(shù)在非負(fù)正交分劃體中可微，且為凹函數(shù)；(c)點(diǎn)滿足庫恩-塔克極小化條件。那么，為的整體極小值點(diǎn)。給定非線性規(guī)劃：二、庫恩-塔克充分性定理：凹規(guī)劃（極小值）第39頁，共47頁，2023年，2月20日，星期五如果給定條件(a)和(b)，那么庫恩-塔克條件就是極大值（極小值）的充分條件。當(dāng)滿足約束規(guī)范時(shí)，庫恩-塔克條件就是極大值（極小值）的必要條件。如果滿足約束規(guī)范，且實(shí)現(xiàn)條件(a)和(b)，那么庫恩-塔克條件就是極大值（極小值）的充分必要條件。第40頁，共47頁，2023年，2月20日，星期五(a)在非負(fù)正交分劃體中目標(biāo)函數(shù)可微且為擬凹函數(shù)；(b)在非負(fù)正交分劃體中每個(gè)約束函數(shù)可微且為擬凸函數(shù)；(c)點(diǎn)滿足庫恩-塔克極大值條件。給定非線性規(guī)劃：三、阿羅-恩索文充分性定理：擬凹規(guī)劃（極大值）第41頁，共47頁，2023年，2月20日，星期五(d)滿足下列諸條件中任意一個(gè)：(d-i)至少對(duì)某個(gè)變量有。那么，為的整體極大值點(diǎn)。(d-ii)對(duì)某個(gè)可取正值而不違背約束的變量有。(d-iii)個(gè)導(dǎo)數(shù)不全為零，函數(shù)在的鄰域內(nèi)二階可微。(d-iv)函數(shù)為凹函數(shù)。第42頁，共47頁，2023年，2月20日，星期五(a)在非負(fù)正交分劃體中目標(biāo)函數(shù)可微且為擬凸函數(shù)；(b)在非負(fù)正交分劃體中每個(gè)約束函數(shù)可微且為擬凹函數(shù)；(c)點(diǎn)滿足庫恩-塔克極小值條件。給定非線性規(guī)劃：三、阿羅-恩索文充分性定理：擬凹規(guī)劃（極小值）第43頁，共47頁，2023年，2月20日，星期五(d)滿足下列諸條件中任意一個(gè)：(d-i)至少對(duì)某個(gè)變量有