【正文】 行域）且。若此時已滿足精度要求，迭代結(jié)束，就是所求的極小點；否則，從出發(fā)繼續(xù)迭代，直到滿足精度要求為止。此種方法稱為可行方向法，其特點是“迭代所采用的搜索方向為可行方向，所產(chǎn)生的迭代點序列始終在可行域的內(nèi)部，目標函數(shù)單調(diào)下降”。由此可見，許多方法可歸入可行方向法這一類別；但人們通常所講的可行方向法，一般指的是Zoutendijk在1960年提出的算法及其變形，下面就來介紹一下Zoutendijk的可行方向法。設(shè)點的有效約束集非空，為求點的可行下降方向，可由下述不等式組來確定向量： （對于所有的）這等價于由下面的不等式組來求向量和實數(shù)： （對于所有的）現(xiàn)使和（對于所有的）的最大值極小化（同時必須限制向量的模），即可將上述選取搜索方向的工作轉(zhuǎn)化為求解下述線性規(guī)劃問題： （627） （對于所有的） 式中是向量的各個分量。式（627）中加入最后一個約束條件，為的是使該線性規(guī)劃問題有有限最優(yōu)解。此外，由于我們的目的在于尋找搜索向量，所以只要知道的各分量的相對大小即可?，F(xiàn)將式（627）所示的線性規(guī)劃的最優(yōu)解記為，如果求得的，說明在點處不存在可行下降方向，在（對于所有的）線性獨立的條件下，點即為一個KT點；如果求得的，則得到可行下降方向，這就是點處所要的搜索方向。下面通過例題來說明利用可行方向法求解非線性規(guī)劃的一般步驟。[例616] 用可行方向法求解解：取初始點，于是有由于，于是有由于，故約束不是初始點的有效約束。取，從而：令，可得。令，；取，于是：，。構(gòu)造線性規(guī)劃：為便于求解，令，，于是：用單純形法求解，可得最優(yōu)解，即：，所以，現(xiàn)暫時用該步長計算，有。因為，說明是可行點，選取是可行的。繼續(xù)迭代下去，可得最優(yōu)解，最優(yōu)值。64 制約函數(shù)法制約函數(shù)法是通過加到非線性規(guī)劃目標函數(shù)上的某種制約函數(shù)，將約束極值問題轉(zhuǎn)化為無約束極值問題的一類算法。由于制約函數(shù)需要求解一系列無約束極值問題，故也稱為序列無約束極小化技術(shù)，簡記為SUMT （Sequential Unconstrained Minimization Technique）。常用的制約函數(shù)有兩種基本類型，一類為懲罰函數(shù)（也稱為外點法），另一類為障礙函數(shù)（也稱為內(nèi)點法）。1． 外點法考慮非線性規(guī)劃，為求其最優(yōu)解，構(gòu)造一個函數(shù)，現(xiàn)把當作所構(gòu)造函數(shù)的自變量來看待，顯然當（代表可行域）時，（）；當時。再構(gòu)造一個函數(shù)，求解，假設(shè)該問題有最優(yōu)解，則（），即最優(yōu)解一定是可行解。因此，不僅是的極小解，同時也是原函數(shù)的極小解。這樣一來，就把約束極值問題轉(zhuǎn)化成了無約束極值問題。用上述方法構(gòu)造的函數(shù)在處不連續(xù)，更不存在導(dǎo)數(shù)。為此，將修改為：修改后的在處連續(xù)且導(dǎo)數(shù)為“0”；而且及其導(dǎo)數(shù)對任何都連續(xù)。當時，仍有；當時。取一個充分大的正數(shù)，將修改為： （628）或從而可使的解為原問題的極小解或近似極小解。若，則必定是原問題的極小解。事實上，對于所有的都有：即當時，有。式（628）中的函數(shù)稱為懲罰函數(shù)，第二項稱為懲罰項，稱為懲罰因子。若對于某一懲罰因子，如果，就加大懲罰因子的值。隨著懲罰因子數(shù)值的增加，懲罰函數(shù)中的懲罰項所起的作用隨之增大，的解與約束集的“距離”也就越來越近。當序列“”趨于無窮時，點列就從可行域的外部趨于原問題的極小點，這里假設(shè)點列收斂。下面通過例題來展示外點法求解非線性規(guī)劃的基本步驟。[例617] 求解非線性規(guī)劃解：構(gòu)造懲罰函數(shù)對于不滿足約束條件的點，可以有或。令，得的解為：取可得如下結(jié)果：：，：：，：常數(shù)0圖618從此結(jié)果可知從的外部逐步逼近的邊界，當趨于無窮時，趨于原問題的極小解，見圖618。2．內(nèi)點法外點法的最大特點是其初始點可以任意選擇（不要求是可行點），這雖然給計算帶來了很大的方便；但是如果目標函數(shù)在可行域外比較復(fù)雜，甚至根本沒有定義，外點法就無法使用了。內(nèi)點法與外點法不同，它要求迭代過程始終建立在可行的基礎(chǔ)之上；即在可行域的內(nèi)部選取一個初始點，并在可行域的邊界上設(shè)置一道“屏障”，當?shù)^程靠近可行域的邊界時，新的目標函數(shù)值迅速增大，從而使迭代點始終保持在可行域的內(nèi)部。仿照外點法，通過函數(shù)疊加的辦法來改造原有目標函數(shù)，使改造后的目標函數(shù)（稱為障礙函數(shù)）具有這樣的性質(zhì)：在可行域的內(nèi)部與邊界面較遠的點上，障礙函數(shù)與原目標函數(shù)應(yīng)盡可能地接近；而在接近邊界面的點上，障礙函數(shù)取相當大的數(shù)值?？梢韵胂螅瑵M足這種要求的障礙函數(shù)，其極小值自然不會在可行域的邊界上達到；這就是說，用障礙函數(shù)來代替（近似）原目標函數(shù)，并在可行域的內(nèi)部使其極小化。雖然可行域是一個閉集，但因極小點不在閉集的邊界上，因而障礙函數(shù)實際上已使約束極值問題轉(zhuǎn)化為了無約束極值問題。根據(jù)上述分析，一個約束非線性規(guī)劃問題，可以轉(zhuǎn)化為下述一系列無約束非線性規(guī)劃問題： ， （629）其中， （630）或， (631）式（630）和式（631）右端第二項稱為障礙項，稱為障礙因子。從障礙項的構(gòu)成不難看出，在可行域的邊緣上，至少有一個，從而有為無窮大。如果從可行域內(nèi)部的某一點出發(fā)，按無約束極小化方法對式（629）進行迭代（注意：在進行一維搜索時要適當控制步長，以免迭代跨越的邊界），則隨著的逐步減少（）障礙項所起到的作用也越來越小，因而所求出的的解也逐步逼近原問題的極小解。若原問題的極小解在可行域的邊界上，則隨著的逐步減少（障礙作用越來越?。┧蟪龅恼系K函數(shù)極小解不斷靠近邊界，直到滿足某一特定的精度要求。[例618] 試用內(nèi)點法求解解：構(gòu)造障礙函數(shù)，求解方程組，可得：，如此得最優(yōu)解：此例可以通過上述解析法進行求解，但并非所有問題都能適用于解析法；如果問題不便用解析法，我們只能采用迭代法來進行求解。[例619] 試用內(nèi)點法求解解：采用自然對數(shù)構(gòu)造障礙函數(shù)各步迭代結(jié)果列于表65并繪制于圖619中。表65常數(shù)圖619內(nèi)點法必須從某一內(nèi)點出發(fā)才能開始其迭代過程；如果不能找到某個內(nèi)點作為初始點，迭代過程就無法開始。求初始內(nèi)點本身也是一個迭代的過程，這一迭代過程可概括如下：（1）任取一點，令如果為空集，則為初始內(nèi)點；如果為非空，則以中的約束函數(shù)為虛擬的目標函數(shù)，并以中的約束函數(shù)為障礙項，構(gòu)成一個無約束極值問題，對這一問題進行極小化，可得一個新的點。然后檢驗，若仍然不是內(nèi)點，減小障礙因子繼續(xù)迭代，直到求得一個內(nèi)點為止。（2）指定下標集及：（3）構(gòu)造函數(shù)，以為初始點，在保持對集合可行的情況下，極小化；即在的情況下，求。作為極小化的結(jié)果，我們可以得到一個新的內(nèi)點，即。令（比如說?。?，重復(fù)上述迭代過程，直到得到一個滿足收斂準則的內(nèi)點。判斷內(nèi)點的收斂性通常采用如下準則： 或 如果滿足準則，內(nèi)點為原問題的極小解或近似極小解。思考題：1． 判斷函數(shù)的凸凹性（1），（2）（3）2． 分別用斐波那契法和黃金分割法求下述函數(shù)的極小值，初始的搜索區(qū)間為，要求。3． 試計算出下述函數(shù)的梯度和海賽矩陣（1） （2）（3） （4）4． 用梯度法（最速下降法）求函數(shù)的極大點，初始點。5． 用牛頓法求解，初始點，分別用最佳步長和固定步長進行計算。6． 用變尺度法求解，初始點，要求近似極小點梯度的模不大于。7． 寫出下述非線性規(guī)劃問題的KT條件（1） （2） 8． 分析下述非線性規(guī)劃在、和各點處的可行下降方向。9． 二次規(guī)劃 （1） 用KT條件求解；（2） 寫出等價的線性規(guī)劃問題并求解。10．試用可行方向法求解非線性規(guī)劃，初始點。11．分別用內(nèi)點法和外點法求解下述非線性規(guī)劃問題（1） （2） ，12．試用內(nèi)點法求解非線性規(guī)劃問題 （1） 障礙項采用倒數(shù)函數(shù)；（2） 障礙項采用對數(shù)函數(shù)。151