約束極值問題課件

四*、非線性規(guī)劃

第6章無約束問題第7章約束極值問題清華大學(xué)出版社第7章約束極值問題

第1節(jié)最優(yōu)性條件第2節(jié)二次規(guī)劃第3節(jié)可行方向法第4節(jié)制約函數(shù)法清華大學(xué)出版社第1節(jié)最優(yōu)性條件大多數(shù)極值問題其變量的取值都會(huì)受到一定限制，這種限制由約束條件來體現(xiàn)。帶有約束條件的極值問題稱為約束極值問題。非線性規(guī)劃的一般形式為或 問題(7-2)也常寫成(7-1)(7-2)(7-3)清華大學(xué)出版社第1節(jié)最優(yōu)性條件1.1起作用約束和可行下降方向的概念現(xiàn)考慮上述一般非線性規(guī)劃，假定f(X)、hi(X)和具有一階連續(xù)偏導(dǎo)數(shù)。設(shè)是非線性規(guī)劃的一個(gè)可行解。現(xiàn)考慮某一不等式約束條件滿足它有兩種可能：其一為，這時(shí)，點(diǎn)不是處于由這一約束條件形成的可行域邊界上，因而這一約束對(duì)點(diǎn)的微小攝動(dòng)不起限制作用，從而稱這個(gè)約束條件是點(diǎn)的不起作用約束(或無效約束)；其二是，這時(shí)點(diǎn)處于該約束條件形成的可行域邊界上，它對(duì)的攝動(dòng)起到了某種限制作用，故稱這個(gè)約束是點(diǎn)的起作用約束(有效約束)。

顯而易見，等式約束對(duì)所有可行點(diǎn)來說都是起作用約束。清華大學(xué)出版社第1節(jié)最優(yōu)性條件假定X(0)是非線性規(guī)劃(7-3)式的一個(gè)可行點(diǎn)，現(xiàn)考慮此點(diǎn)的某一方向D，若存在實(shí)數(shù)，使對(duì)任意均有

就稱方向D是X(0)點(diǎn)的一個(gè)可行方向。

清華大學(xué)出版社第1節(jié)最優(yōu)性條件若D是可行點(diǎn)X(0)處的任一可行方向，則對(duì)該點(diǎn)的所有起作用約束均有其中J為這個(gè)點(diǎn)所有起作用約束下標(biāo)的集合。另一方面，由泰勒公式對(duì)所有起作用約束，當(dāng)λ>0足夠小時(shí)，只要

就有此外，對(duì)X(0)點(diǎn)的不起作用約束，由約束函數(shù)的連續(xù)性，當(dāng)λ>0足夠小時(shí)亦有上式成立。從而，只要方向D滿足(7-6)式，即可保證它是X(0)點(diǎn)的可行方向。

圖7-1（7-5）（7-6）清華大學(xué)出版社第1節(jié)最優(yōu)性條件1.2庫恩－塔克條件假定X*是非線性規(guī)劃(7-3)式的極小點(diǎn)，該點(diǎn)可能位于可行域的內(nèi)部，也可能處于可行域的邊界上。若為前者，這事實(shí)上是個(gè)無約束問題，X*必滿足條件若為后者，情況就復(fù)雜得多了。下面討論當(dāng)極小點(diǎn)位于可行域邊界的情形。清華大學(xué)出版社第1節(jié)最優(yōu)性條件不失一般性，設(shè)X*位于第一個(gè)約束條件形成的可行域邊界上，即第一個(gè)約束條件是X*點(diǎn)的起作用約束()。若X*是極小點(diǎn)，則必與在一條直線上且方向相反。否則，在該點(diǎn)就一定存在可行下降方向(圖7-2中的X*點(diǎn)為極小點(diǎn)；X點(diǎn)不滿足上述要求，它不是極小點(diǎn)，角度β表示了該點(diǎn)可行下降方向的范圍)。上面的論述說明，在上述條件下，存在實(shí)數(shù)，使

清華大學(xué)出版社第1節(jié)最優(yōu)性條件若X*點(diǎn)有兩個(gè)起作用約束，例如說有在這種情況下，必處于和的夾角之內(nèi)。和線性無關(guān)，則可將表示成和的非負(fù)線性組合。也就是說，在這種情況下存在實(shí)數(shù)和，使

如若不然，在X*點(diǎn)必有可行下降方向，它就不會(huì)是極小點(diǎn)(圖7-3)。由此可見，如果X*是極小點(diǎn)，而且X*點(diǎn)的起作用約束條件的梯度清華大學(xué)出版社第1節(jié)最優(yōu)性條件圖7-2如上類推，可以得到

圖7-3清華大學(xué)出版社第1節(jié)最優(yōu)性條件為了把不起作用約束也包括進(jìn)式(7-9)中，增加條件當(dāng)時(shí)，可不為零；當(dāng)時(shí)，必有如此即可得到著名的庫恩－塔克(Kuhn－Tucker,簡(jiǎn)寫為K-T)條件。庫恩－塔克條件是非線性規(guī)劃領(lǐng)域中最重要的理論成果之一，是確定某點(diǎn)為最優(yōu)點(diǎn)的必要條件。只要是最優(yōu)點(diǎn)(而且該點(diǎn)起作用約束的梯度線性無關(guān)。滿足這種要求的點(diǎn)稱為正則點(diǎn))，就必須滿足這個(gè)條件。但一般說它并不是充分條件，因而滿足這個(gè)條件的點(diǎn)不一定就是最優(yōu)點(diǎn)(對(duì)于凸規(guī)劃，它既是最優(yōu)點(diǎn)存在的必要條件，同時(shí)也是充分條件)。清華大學(xué)出版社第1節(jié)最優(yōu)性條件庫恩-塔克條件：設(shè)X*是非線性規(guī)劃(7-3)式的極小點(diǎn)，而且在X*點(diǎn)的各起作用約束的梯度線性無關(guān)，則存在向量，使下述條件成立：條件(7-10)式常簡(jiǎn)稱為K-T條件。滿足這個(gè)條件的點(diǎn)(它當(dāng)然也滿足非線性規(guī)劃的所有約束條件)稱為庫恩-塔克點(diǎn)(或K-T點(diǎn))。(7-10)清華大學(xué)出版社第1節(jié)最優(yōu)性條件現(xiàn)考慮帶有等約束非線性規(guī)劃(7-1)式的庫恩－塔克條件，我們用代替約束條件即可使用條件(7-10)，得到庫恩-塔克條件如下：設(shè)X*是非線性規(guī)劃(7-1)式的極小點(diǎn)，而且X*點(diǎn)的所有起作用約束的梯度和線性無關(guān)，則存在向量使下述條件成立：(7-10)式和(7-11)式中的以及稱為廣義拉格朗日乘子。(7-11)清華大學(xué)出版社第1節(jié)最優(yōu)性條件例1用庫恩－塔克條件解非線性規(guī)劃

解：先將該非線性規(guī)劃問題寫成以下形式寫出其目標(biāo)函數(shù)和約束函數(shù)的梯度：對(duì)第一個(gè)和第二個(gè)約束條件分別引入廣義拉格朗日乘子，設(shè)K-T點(diǎn)為X*，則可以得到該問題的K-T條件。清華大學(xué)出版社第1節(jié)最優(yōu)性條件該問題的K-T條件為：為解上述方程組，考慮以下幾種情形：(1)令(2)令，解之，得，不是K-T點(diǎn)。(3)令，解之，得，不是K-T點(diǎn)。(4)令，解之，得，此為K-T點(diǎn)，其目標(biāo)函數(shù)值由于該非線性規(guī)劃問題為凸規(guī)劃，故就是其全局極小點(diǎn)。該點(diǎn)是可行域的內(nèi)點(diǎn)，它也可直接由梯度等于零的條件求出。，無解。清華大學(xué)出版社第2節(jié)二次規(guī)劃若非線性規(guī)劃的目標(biāo)函數(shù)為自變量X的二次函數(shù)，約束條件全是線性的，稱這種規(guī)劃為二次規(guī)劃。二次規(guī)劃的數(shù)學(xué)模型為：(7-12)式右端的第二項(xiàng)為二次型。如果該二次型正定(或半正定)，則目標(biāo)函數(shù)為嚴(yán)格凸函數(shù)(或凸函數(shù))；此外，二次規(guī)劃的可行域?yàn)橥辜?，因而，上述?guī)劃屬于凸規(guī)劃。第6章已指出：凸規(guī)劃的局部極值即為全局極值。對(duì)于這種問題，庫恩-塔克條件不但是極值點(diǎn)存在的必要條件，而且也是充分條件。（7-12）（7-13）

（7-14）清華大學(xué)出版社第2節(jié)二次規(guī)劃將庫恩－塔克條件(7-10)式中的第一個(gè)條件應(yīng)用于二次規(guī)劃(7-12)式至(7-14)式，并用y代替庫恩-塔克條件中的γ，即可得到在(7-13)式中引入松弛變量，(7-13)式即變?yōu)?假定)

（7-16）

（7-15）再將庫恩－塔克條件中的第二個(gè)條件應(yīng)用于上述二次規(guī)劃，并考慮到(7-16)式，這就得到此外還有 （7-18）

（7-17）清華大學(xué)出版社第2節(jié)二次規(guī)劃聯(lián)立求解(7-15)式和(7-16)式，如果得到的解也滿足(7-17)式和(7-18)式，則這樣的解就是原二次規(guī)劃問題的解。但是，在(7-15)式中，cj可能為正，也可能為負(fù)。為了便于求解，先引入人工變量zj(zj≥0)，其前面的符號(hào)可取正或負(fù)，以便得出可行解)，這樣(7-15)式就變成了 （7-19）為符號(hào)函數(shù)，當(dāng)時(shí)，；當(dāng)時(shí)，。這樣一來，可立刻得到初始基本可行解如下：其中清華大學(xué)出版社第2節(jié)二次規(guī)劃但是，只有當(dāng)zj=0時(shí)才能得到原來問題的解，故必須對(duì)上述問題進(jìn)行修正，從而得到如下線性規(guī)劃問題：該線性規(guī)劃尚應(yīng)滿足(7-17)式。這相當(dāng)于說，不能使xj和yj(對(duì)每一個(gè)j)同時(shí)為基變量。

（7-20）清華大學(xué)出版社第2節(jié)二次規(guī)劃

解線性規(guī)劃(7-20)式，若得到最優(yōu)解：則就是原二次規(guī)劃問題的最優(yōu)解。清華大學(xué)出版社第2節(jié)二次規(guī)劃例2求解二次規(guī)劃

解：將上述二次規(guī)劃改寫為可知目標(biāo)函數(shù)為嚴(yán)格凸函數(shù)。此外清華大學(xué)出版社第2節(jié)二次規(guī)劃由于c1和c2小于零，故引入的人工變量z1和z2前面取負(fù)號(hào)，這樣就得到線性規(guī)劃問題如下：

或

此外尚應(yīng)滿足清華大學(xué)出版社第2節(jié)二次規(guī)劃用線性規(guī)劃的單純形法解之(注意，在轉(zhuǎn)換過程中應(yīng)滿足條件xjyj=0)，得該線性規(guī)劃問題的解如下：由此得到原二次規(guī)劃問題的解為

可以驗(yàn)證，

以及滿足庫恩－塔克條件。

清華大學(xué)出版社第3節(jié)可行方向法現(xiàn)考慮非線性規(guī)劃(7-3)式，設(shè)X(k)是它的一個(gè)可行解，但不是要求的極小點(diǎn)。為了求它的極小點(diǎn)或近似極小點(diǎn)，根據(jù)以前所說，應(yīng)在X(k)點(diǎn)的可行下降方向中選取某一方向D(k)，并確定步長(zhǎng)λk，使若滿足精度要求，迭代停止，X(k+1)就是所要的點(diǎn)。否則，從X(k+1)出發(fā)繼續(xù)進(jìn)行迭代，直到滿足要求為止。上述方法稱為可行方向法，其特點(diǎn)是：迭代過程中采用的搜索方向?yàn)榭尚蟹较?，所產(chǎn)生的迭代點(diǎn)列｛X(k)｝始終在可行域內(nèi)，目標(biāo)函數(shù)值單調(diào)下降。（7-21）清華大學(xué)出版社第3節(jié)可行方向法設(shè)X(k)點(diǎn)的起作用約束集非空，為求X(k)點(diǎn)的可行下降方向，可由下述不等式組確定向量D：這等價(jià)于由下面的不等式組求向量D和實(shí)數(shù)η：若使和(對(duì)所有即可將上述選取搜索方向的工作，轉(zhuǎn)換為求解下述線性規(guī)劃問題：式中為向量D的分量。

（7-22）（7-23）（7-24）)的最大值極小化，清華大學(xué)出版社第3節(jié)可行方向法在(7-24)中加入最后一個(gè)限制條件，為的是使該線性規(guī)劃有有限最優(yōu)解；由于我們的目的在于尋找搜索方向D，只需知道D的各分量的相對(duì)大小即可。將線性規(guī)劃(7-24)式的最優(yōu)解記為，如果求出的，說明在點(diǎn)不存在可行下降方向，在(此處）線性無關(guān)的條件下，為一K-T點(diǎn)。若解出的，則得到可行下降方向，這就是我們所要的搜索方向。清華大學(xué)出版社第3節(jié)可行方向法可行方向法的迭代步驟如下：確定允許誤差，選初始近似點(diǎn)，并令(2)確定起作用約束指標(biāo)集若，而且，停止迭代，得點(diǎn)②若，但，則取搜索方向，然后轉(zhuǎn)向第(5)步。，轉(zhuǎn)下一步。③若清華大學(xué)出版社第3節(jié)可行方向法(3)求解線性規(guī)劃設(shè)它的最優(yōu)解是(4)檢驗(yàn)是否滿足若滿足則停止迭代，得到點(diǎn)X(k)；否則，以D(k)為搜索方向，并轉(zhuǎn)下一步。清華大學(xué)出版社第3節(jié)可行方向法(5)解下述一維極值問題此處

(6)令轉(zhuǎn)回第(2)步。

清華大學(xué)出版社第3節(jié)可行方向法例3用可行方向法解下述非線性規(guī)劃問題解：先將該非線性規(guī)劃問題寫成取初始可行點(diǎn)

從而(空集)。由于所以X(0)不是(近似)極小點(diǎn)。清華大學(xué)出版社第3節(jié)可行方向法現(xiàn)取搜索方向從而

將其代入約束條件，并令，解得令對(duì)λ的導(dǎo)數(shù)等于零，解得λ=1/2。因λ大于故取清華大學(xué)出版社第3節(jié)可行方向法構(gòu)造在下述線性規(guī)劃問題：為便于用單純形法求解，令

從而得到：清華大學(xué)出版社第3節(jié)可行方向法引入剩余變量y4，松弛變量y5,y6,y7以及人工變量y8，得線性規(guī)劃問題如下：

其最優(yōu)解為：從而得到，，搜索方向 清華大學(xué)出版社第3節(jié)可行方向法由此

令，得到?，F(xiàn)暫用該步長(zhǎng)，算出因，上面算出的為可行點(diǎn)，說明選取繼續(xù)迭代下去，可得最優(yōu)解為原來問題的最優(yōu)解不變，其目標(biāo)函數(shù)值

正確。清華大學(xué)出版社第4節(jié)制約函數(shù)法本節(jié)介紹求解非線性規(guī)劃問題的制約函數(shù)法。使用這種方法，可將非線性規(guī)劃問題的求解，轉(zhuǎn)化為求解一系列無約束極值問題，因而也稱這種方法為序列無約束極小化技術(shù)，簡(jiǎn)記為SUMT(sequentialunconstrainedminimizationtechnique)。常用的制約函數(shù)基本上有兩類：懲罰函數(shù)(或稱罰函數(shù)(penaltyfunction))：外點(diǎn)法障礙函數(shù)(barrierfunction)：內(nèi)點(diǎn)法。清華大學(xué)出版社4.1外點(diǎn)法考慮非線性規(guī)劃問題(7-3)式，為求其最優(yōu)解，構(gòu)造一個(gè)函數(shù)（7-25）視為t，顯然時(shí)，當(dāng)時(shí)，再構(gòu)造函數(shù)

（7-26）現(xiàn)把當(dāng)現(xiàn)求解無約束問題（7-27）清華大學(xué)出版社4.1外點(diǎn)法若該問題有解，假定其解為，則由(7-25)式應(yīng)有這就是說點(diǎn)。因而，不僅是問題(7-27)式的極小解，它也是原問題(7-3)式的極小解。這樣一來，就把有約束問題(7-3)式的求解化成了求解無約束問題(7-27)式。清華大學(xué)出版社4.1外點(diǎn)法用上述方法構(gòu)造的函數(shù)Ψ(t)在t=0處不連續(xù)，更沒有導(dǎo)數(shù)。為此，將該函數(shù)修改為修改后的函數(shù)Ψ(t)，當(dāng)t=0時(shí)導(dǎo)數(shù)等于零，而且Ψ(t)和Ψ’(t)對(duì)任意t都連續(xù)。當(dāng)時(shí)仍有 當(dāng)時(shí) （7-28）清華大學(xué)出版社4.1外點(diǎn)法取一個(gè)充分大的數(shù)M>0，將改為 或等價(jià)地

從而可使的解為原問題的極小解或近似極小解。，則它必定是原問題的極小解。事實(shí)上，對(duì)于所有即當(dāng)時(shí)，有（7-29）（7-30）若求得的清華大學(xué)出版社4.1外點(diǎn)法函數(shù)P(X,M)稱為懲罰函數(shù)，其中的第二項(xiàng)若對(duì)于某一個(gè)(懲)罰因子M，例如，就加大罰因子的值；的解與約束集R的“距離”就越來越近。當(dāng)趨于無窮大時(shí)，點(diǎn)列從可行域R外趨于原問題(7-3)的極小點(diǎn)稱懲罰項(xiàng)。隨著M值的增加，懲罰函數(shù)中的懲罰項(xiàng)所起的作用隨之增大，圖7-4

清華大學(xué)出版社4.1外點(diǎn)法外點(diǎn)法的經(jīng)濟(jì)解釋：將目標(biāo)函數(shù)f(X)看成“價(jià)格”，約束條件看成某種“規(guī)定”，采購人可在規(guī)定范圍內(nèi)購置最便宜的東西。此外對(duì)違反規(guī)定制定了一種“罰款”政策，若符合規(guī)定，罰款為零；否則，要收罰款。此時(shí)，采購人付出的總代價(jià)應(yīng)是價(jià)格和罰款的總和。采購者的目標(biāo)是使總代價(jià)最小，這就是上述的無約束問題。當(dāng)罰款規(guī)定得很苛刻時(shí)，違反規(guī)定支付的罰款很高，這就迫使采購人符合規(guī)定。在數(shù)學(xué)上表現(xiàn)為當(dāng)罰因子Mk足夠大時(shí)，上述無約束問題的最優(yōu)解應(yīng)滿足約束條件，而成為約束問題的最優(yōu)解。

清華大學(xué)出版社4.1外點(diǎn)法外點(diǎn)法迭代步驟：(1)取(例如取)，允許誤差，并令(2)求無約束極值問題的最優(yōu)解：

其中

(3)若對(duì)某一個(gè)有

則取(例如，或10)，令并轉(zhuǎn)向第2步。否則，停止迭代，得清華大學(xué)出版社4.1外點(diǎn)法例4求解非線性規(guī)劃解：構(gòu)造罰函數(shù)對(duì)于不滿足約束條件的點(diǎn)，有

令

得的解為

清華大學(xué)出版社4.1外點(diǎn)法取，可得出以下結(jié)果：可知從R的外面逐步逼近R的邊界，當(dāng)時(shí)，趨于原問題的極小解圖7-5

清華大學(xué)出版社4.2內(nèi)點(diǎn)法內(nèi)點(diǎn)法的提出如果要求每次迭代得到的近似解都在可行域內(nèi)，以便觀察目標(biāo)函數(shù)值的變化情況；或者，如果f(X)在可行域外的性質(zhì)比較復(fù)雜，甚至沒有定義，這時(shí)就無法使用外點(diǎn)法。內(nèi)點(diǎn)法的特點(diǎn)和外點(diǎn)法不同的是，內(nèi)點(diǎn)法要求迭代過程始終在可行域內(nèi)部進(jìn)行。為此，我們把初始點(diǎn)取在可行域內(nèi)部(既不在可行域外，也不在可行域邊界上，這種可行點(diǎn)稱為內(nèi)點(diǎn))，并在可行域的邊界上設(shè)置一道“障礙”，使迭代點(diǎn)靠近可行域邊界時(shí)，給出的新目標(biāo)函數(shù)值會(huì)迅速增大，從而使迭代點(diǎn)始終留在可行域內(nèi)。清華大學(xué)出版社4.2內(nèi)點(diǎn)法內(nèi)點(diǎn)法中障礙函數(shù)的構(gòu)造仿照外點(diǎn)法，通過函數(shù)疊加的辦法來改造原目標(biāo)函數(shù)，使得改造后的目標(biāo)函數(shù)(稱為障礙函數(shù))具有這種性質(zhì)：在可行域R的內(nèi)部與其邊界面較遠(yuǎn)的地方，障礙函數(shù)與原來的目標(biāo)函數(shù)f(X)盡可能相近；而在接近R的邊界面時(shí)可以有任意大的值?？梢韵胍?，滿足這種要求的障礙函數(shù)，其極小解自然不會(huì)在R的邊界上達(dá)到。這就是說，用障礙函數(shù)來代替(近似)原目標(biāo)函數(shù)，并在可行域R內(nèi)部使其極小化，雖然R是一個(gè)閉集，但因極小點(diǎn)不在閉集的邊界上，因而實(shí)際上是具有無約束性質(zhì)的極值問題，可借助于無約束最優(yōu)化的方法進(jìn)行計(jì)算。清華大學(xué)出版社4.2內(nèi)點(diǎn)法根據(jù)上述分析，即可將非線性規(guī)劃(7-3)式轉(zhuǎn)化為一系列無約束極小化問題其中

或

（7-33） (7-32)式和(7-33)式右端第二項(xiàng)稱為障礙項(xiàng)。易見，在R的邊界上(即至少有一個(gè))，為正無窮大。

（7-31）（7-32）

（7-34）清華大學(xué)出版社4.2內(nèi)點(diǎn)法如果從可行域內(nèi)部的某一點(diǎn)X(0)出發(fā)，按無約束極小化方法對(duì)(7-31)式進(jìn)行迭代(在進(jìn)行一維搜索時(shí)要適當(dāng)控制步長(zhǎng)，以免迭代點(diǎn)跑到R0之外)，則隨著障礙因子r

k的逐步減小，即障礙項(xiàng)所起的作用也越來越小，因而，求出的的解也逐步逼近原問題(7-3)式的極小解若原來問題的極小解在可行域的邊界上，則隨著r

k的的減小，障礙作用逐步降低，所求出的障礙函數(shù)的極小解不斷靠近邊界，直至滿足某一精度要求為止。清華大學(xué)出版社4.2內(nèi)點(diǎn)法內(nèi)點(diǎn)法的迭代步驟：(1)取(例如取)，允許誤差(2)找出一可行內(nèi)點(diǎn)，并令(3)構(gòu)造障礙函數(shù)，障礙項(xiàng)可采用倒數(shù)函數(shù)((7-32)式)，也可采用對(duì)數(shù)函數(shù)(例如(7-33)式)。(4)以為初始點(diǎn)，對(duì)障礙函數(shù)進(jìn)行無約束極小化:其中見(7-32)式或(7-33)式。（7-35）

清華大學(xué)出版社4.2內(nèi)點(diǎn)法(5)檢驗(yàn)是否滿足收斂準(zhǔn)則

或

如滿足上述準(zhǔn)則，則以為原問題的近似極小解；否則，取(例如取或)，令根據(jù)情況，收斂準(zhǔn)則也可采用不同形式，如：

或

，轉(zhuǎn)向第（3）步。清華大學(xué)出版社4.2內(nèi)點(diǎn)法例5試用內(nèi)點(diǎn)法求解

解：構(gòu)造障礙函數(shù)

聯(lián)立解上述兩個(gè)方程，得

如此得最優(yōu)解：清華大學(xué)出版社4.2內(nèi)點(diǎn)法例6試用內(nèi)點(diǎn)法解解：障礙項(xiàng)采用自然對(duì)數(shù)函數(shù)，得障礙函數(shù)如下：各次迭代結(jié)果為：

障礙因子rx1(r)x2(r)r11.0000.5001.250r20.5000.3090.595r30.2500.1830.283r40.1000.0850.107r50.00010.0000.000清華大學(xué)出版社4.2內(nèi)點(diǎn)法下面討論初始內(nèi)