【正文】 11．分別用內(nèi)點法和外點法求解下述非線性規(guī)劃問題（1） （2） ，12．試用內(nèi)點法求解非線性規(guī)劃問題 （1） 障礙項采用倒數(shù)函數(shù)；（2） 障礙項采用對數(shù)函數(shù)。9． 二次規(guī)劃 （1） 用KT條件求解；（2） 寫出等價的線性規(guī)劃問題并求解。6． 用變尺度法求解，初始點，要求近似極小點梯度的模不大于。3． 試計算出下述函數(shù)的梯度和海賽矩陣（1） （2）（3） （4）4． 用梯度法（最速下降法）求函數(shù)的極大點，初始點。判斷內(nèi)點的收斂性通常采用如下準(zhǔn)則： 或 如果滿足準(zhǔn)則，內(nèi)點為原問題的極小解或近似極小解。作為極小化的結(jié)果，我們可以得到一個新的內(nèi)點，即。然后檢驗，若仍然不是內(nèi)點，減小障礙因子繼續(xù)迭代，直到求得一個內(nèi)點為止。表65常數(shù)圖619內(nèi)點法必須從某一內(nèi)點出發(fā)才能開始其迭代過程；如果不能找到某個內(nèi)點作為初始點，迭代過程就無法開始。[例618] 試用內(nèi)點法求解解：構(gòu)造障礙函數(shù)，求解方程組，可得：，如此得最優(yōu)解：此例可以通過上述解析法進(jìn)行求解，但并非所有問題都能適用于解析法；如果問題不便用解析法，我們只能采用迭代法來進(jìn)行求解。如果從可行域內(nèi)部的某一點出發(fā)，按無約束極小化方法對式（629）進(jìn)行迭代（注意：在進(jìn)行一維搜索時要適當(dāng)控制步長，以免迭代跨越的邊界），則隨著的逐步減少（）障礙項所起到的作用也越來越小，因而所求出的的解也逐步逼近原問題的極小解。根據(jù)上述分析，一個約束非線性規(guī)劃問題，可以轉(zhuǎn)化為下述一系列無約束非線性規(guī)劃問題： ， （629）其中， （630）或， (631）式（630）和式（631）右端第二項稱為障礙項，稱為障礙因子?？梢韵胂螅瑵M足這種要求的障礙函數(shù)，其極小值自然不會在可行域的邊界上達(dá)到；這就是說，用障礙函數(shù)來代替（近似）原目標(biāo)函數(shù)，并在可行域的內(nèi)部使其極小化。內(nèi)點法與外點法不同，它要求迭代過程始終建立在可行的基礎(chǔ)之上；即在可行域的內(nèi)部選取一個初始點，并在可行域的邊界上設(shè)置一道“屏障”，當(dāng)?shù)^程靠近可行域的邊界時，新的目標(biāo)函數(shù)值迅速增大，從而使迭代點始終保持在可行域的內(nèi)部。令，得的解為：取可得如下結(jié)果：：，：：，：常數(shù)0圖618從此結(jié)果可知從的外部逐步逼近的邊界，當(dāng)趨于無窮時，趨于原問題的極小解，見圖618。下面通過例題來展示外點法求解非線性規(guī)劃的基本步驟。隨著懲罰因子數(shù)值的增加，懲罰函數(shù)中的懲罰項所起的作用隨之增大，的解與約束集的“距離”也就越來越近。式（628）中的函數(shù)稱為懲罰函數(shù)，第二項稱為懲罰項，稱為懲罰因子。若，則必定是原問題的極小解。當(dāng)時，仍有；當(dāng)時。用上述方法構(gòu)造的函數(shù)在處不連續(xù)，更不存在導(dǎo)數(shù)。因此，不僅是的極小解，同時也是原函數(shù)的極小解。1． 外點法考慮非線性規(guī)劃，為求其最優(yōu)解，構(gòu)造一個函數(shù)，現(xiàn)把當(dāng)作所構(gòu)造函數(shù)的自變量來看待，顯然當(dāng)（代表可行域）時，（）；當(dāng)時。由于制約函數(shù)需要求解一系列無約束極值問題，故也稱為序列無約束極小化技術(shù)，簡記為SUMT （Sequential Unconstrained Minimization Technique）。繼續(xù)迭代下去，可得最優(yōu)解，最優(yōu)值。構(gòu)造線性規(guī)劃：為便于求解，令，于是：用單純形法求解，可得最優(yōu)解，即：，所以，現(xiàn)暫時用該步長計算，有。取，從而：令，可得。下面通過例題來說明利用可行方向法求解非線性規(guī)劃的一般步驟。此外，由于我們的目的在于尋找搜索向量，所以只要知道的各分量的相對大小即可。設(shè)點的有效約束集非空，為求點的可行下降方向，可由下述不等式組來確定向量： （對于所有的）這等價于由下面的不等式組來求向量和實數(shù)： （對于所有的）現(xiàn)使和（對于所有的）的最大值極小化（同時必須限制向量的模），即可將上述選取搜索方向的工作轉(zhuǎn)化為求解下述線性規(guī)劃問題： （627） （對于所有的） 式中是向量的各個分量。此種方法稱為可行方向法，其特點是“迭代所采用的搜索方向為可行方向，所產(chǎn)生的迭代點序列始終在可行域的內(nèi)部，目標(biāo)函數(shù)單調(diào)下降”。為了求解出它的極小點或近似極小點，應(yīng)在點的可行下降方向中選取某一方向并確定步長，使（代表可行域）且。表64cj0 0 0 0 0 0 1 1CBXBx1 x2 l1 g1 g2 s1 R1 R2000x1l1x21 0 0 1/3 1/6 0 1/3 1/60 0 1 0 1/2 1 0 1/20 1 0 1/6 1/12 1/2 1/6 1/121/315/6sj0 0 0 0 0 0 1 10表64給出了第一階段的最優(yōu)解，由于，所以此解對于原二次規(guī)劃不僅是可行的而且是最優(yōu)的，即最優(yōu)解，最優(yōu)值。表62cj0 0 0 0 0 0 1 1CBXBx1 x2 l1 g1 g2 s1 R1 R2010x1R2s11 1/2 1/4 1/4 0 0 1/4 00 3 3/2 1/2 1 0 1/2 10 3/2 1/4 1/4 0 1 1/4 0141sj0 3 3/2 1/2 1 0 3/2 04第二次迭代：，可以讓入基，按最小比值確定出基，見表63。[例615] 求解二次規(guī)劃問題這一問題可以用矩陣形式表示為：這就形成了式（626）所需要的全部信息：引入人工變量和得到第一階段的初始單純形表，見表61。因此，問題等價于求解一組滿足附加條件的線性方程組。二次規(guī)劃屬于凸規(guī)劃，其局部極值即為全局極值，同時庫恩塔克條件是極值點存在的充分必要條件。如果問題極大化，假設(shè)為負(fù)定；如果問題極小化，假設(shè)為正定。二次規(guī)劃是非線性規(guī)劃中較為簡單的一種，許多方面的問題都可以抽象為二次規(guī)劃，而且它和線性規(guī)劃有著非常直接的關(guān)系。參照圖617，很容易得到此題的最優(yōu)解，最優(yōu)值。[例614] 求解下述非線性規(guī)劃問題解：設(shè)KT點為，目標(biāo)函數(shù)極小化，各函數(shù)的梯度分別為：，對兩個約束條件分別引入拉格朗日乘子和，則有如下KT條件：，為求解該方程組，需要考慮以下幾種情況：（1），時，無解；（2），時，；（3），時，；（4），時。[例613] 求解下述非線性規(guī)劃問題.：解：由于是正定矩陣，所以是嚴(yán)格的凸函數(shù)，又由于約束條件是線性函數(shù)，所以此非線性規(guī)劃是凸規(guī)劃，即此時庫恩塔克條件是極值點存在的充分必要條件。庫恩塔克條件是非線性規(guī)劃領(lǐng)域中最重要的理論成果之一，是確定某點為極值點的必要條件；但一般來講它并不是充分條件，因此滿足這一條件的點并非一定就是極值點。如此即可得到式（623）所示的庫恩塔克條件（KuhnTucker，簡稱KT條件，滿足這一條件的點稱為KT點）。在這種情況下，必處于和的夾角之內(nèi)；如若不然，點必存在可行下降方向，這與是極小點的相矛盾，如圖616所示。既然與在同一直線上，且方向相反，則必存在一個實數(shù)，使。若是極小點，則必與在同一直線上，且方向相反（這里假定和皆不為“0”）；否則，在點處就一定存在可行下降方向，如圖615所示。若為前者，該規(guī)劃問題實質(zhì)是一個無約束極值問題，必滿足；若為后者，情況就復(fù)雜多了，接下來我們就對這一復(fù)雜情況進(jìn)