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

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

——庫恩-塔克條件

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

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

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

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

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

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

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