非線性規(guī)劃的理論與算法

第五章非線性規(guī)劃：理論和算法5.5約束優(yōu)化我們現(xiàn)在繼續(xù)討論更一般的有約束的線性優(yōu)化問題。特別的,我們考慮一個具有非線性目標函數(shù)和（或者）非線性約束的優(yōu)化問題。我們可以將這種問題表示為下面的一般形式：(5.10)在本節(jié)的末尾，我們假設(shè)和，全部是連續(xù)可微的。拉格朗日函數(shù)是研究有約束的優(yōu)化問題的一個重要工具。為了定義這個函數(shù)，我們結(jié)合每個約束的乘子——稱作拉格朗日乘子。對于問題（5.10）拉格朗日函數(shù)如下定義：（5.11）本質(zhì)上，我們考慮的是目標函數(shù)違反了可行約束時的懲罰函數(shù)。選擇合適的，最小化無約束函數(shù)等價于求解約束問題（5.10）。這就是我們對拉格朗日函數(shù)感興趣的最根本的原因。與這個問題相關(guān)的最重要問題之一是求解最優(yōu)問題的充要條件?？傊?，這些條件稱為最優(yōu)性條件，也是本節(jié)的目的。在給出問題（5.10）最優(yōu)性條件之前，我們先討論一個叫做正則性的條件，由下面的定義給出：定義5.1：設(shè)向量滿足和。設(shè)是使得等號成立的指標集。是問題（5.10）約束條件的正則點，如果梯度向量（）相互線性無關(guān)。在上述定義中與對應的約束，即滿足的約束稱為在點處的有效約束。我們討論第一章提到的兩個優(yōu)化的概念，局部和全局?；仡櫍?.10）的全局最優(yōu)解向量，它是可行的而且滿足對于所有的都成立。相比之下，局部最優(yōu)解是可行的而且滿足對于（）成立。因此局部解一定是它鄰域的可行點中最優(yōu)的。下面我們考慮的最優(yōu)性條件僅僅判別局部解，則可能是全局最優(yōu)解，也可能不是。幸運的是，這里存在一類局部最優(yōu)解和全局解一致的問題——凸優(yōu)化問題。附錄A中討論的就是基于凸集的凸優(yōu)化問題。定理5.1（一階必要條件）設(shè)是問題（5.10）的局部最小值，假設(shè)是這個問題的約束的正則點。則存在，使得：（5.12）（5.13）（5.14）注意，（5.12）左邊表達的意思是拉格朗日函數(shù)對每個變量的梯度。一階條件在局部最小值，局部最大值及鞍點處滿足。當目標函數(shù)和約束函數(shù)是二次連續(xù)可微的時候，可以用函數(shù)的曲率排除最大值和鞍點。根據(jù)定理5.1，我們考慮拉格朗日函數(shù)和這個函數(shù)對每個變量的海森矩陣，來計算目標函數(shù)和約束函數(shù)在當前點處的曲率。定理5.2（二階必要條件）假設(shè)函數(shù)和（）都是二次連續(xù)可微的。假設(shè)是問題（5.10）局部最小值而且是這個問題的約束正則點。則存在，滿足（5.12）—（5.14）及下面的條件：（5.15）在處有效約束的切線子空間處是半正定的。定理后半部分可以改寫為含有效約束的雅閣比矩陣的形式。設(shè)表示處有效約束的雅閣比矩陣，設(shè)表示基于的零空間。則定理的最后一個條件等價于下面的條件：（5.16）是半正定的。二階必要條件并非常常保證給出的解的局部最優(yōu)性。局部最優(yōu)性的充分條件更加嚴格和復雜，因為要考慮到退化的可能性。定理5.3（二階充分條件）假設(shè)函數(shù)和，都是連續(xù)二次可微的。同時假設(shè)是問題（5.10）可行點而且是這個問題的約束正則點。設(shè)表示處有效約束的雅閣比矩陣，設(shè)表示基于的零空間。如果存在，滿足（5.12）—（5.14）及下面的條件：暗示（5.17）和（5.18）if(Fu<=Fv)b=v;v=u;u=a+0.382*(b-a);k=k+1;elseif(Fu>Fv)a=u;u=v;v=a+0.618*(b-a);k=k+1;endarray(k+1,1)=a;array(k+1,2)=b;endMini=(a+b)/2;輸入：[R,n]=steel(0,1,0.0001)R=1.999994136676423.99999120501463n=1非線性等式約束現(xiàn)在考慮用一個線性方程去逼近一個擁有非線性約束問題的可能性，而線性問題就可以像上面的例子那樣解決。要了解如何工作的，考慮下面的例子，它和前面提到的例子類似，但是它的約束是非線性的。在當前點我們用Taylor級數(shù)逼近約束方程：于是：和廣義簡約梯度法（GRG）的思想是求解一系列子問題，每個子問題可以利用約束的線性逼近。在算法的每一步迭代中，利用先前獲得的點重新計算線性化約束的點。一般來說，即使約束是線性逼近的，但每一步迭代獲得值也是逐步逼近最優(yōu)點的。線性化的一個性質(zhì)是在最優(yōu)點，線性化的問題和原問題有相同的解。使用GRG的第一步是選擇一個初值。假設(shè)我們開始設(shè)，而這個值恰好逼近公式，我們構(gòu)造的首個逼近問題如下：程序思路與例1相似，具體參考例1程序。5.5約束優(yōu)化現(xiàn)在我們這個逼近問題的等式約束，用其他變量表示其中的兩個變量。不妨選擇和，即得：和把這些表達式代入目標函數(shù)，獲得簡化的問題：求解這個無約束的最小化問題，得到再代入上面表達式，得：。因此GRG方法的第一步迭代產(chǎn)生了一個新點繼續(xù)這個求解過程，在新點上我們重新線性化約束函數(shù)，利用獲得的線性方程組，把其中兩個變量用其他變量表示，然后代入目標函數(shù)，就可以得到新的簡化問題，求解這個新的簡化問題得到新的點，依此類推。利用停止準則其中。我們得到結(jié)果如下表5.7.把這個結(jié)果同最優(yōu)解比較，其目標值是。觀察表5.7，注意到當或時，函數(shù)的值有時比最小值小，這是怎么回事呢？原因是通過GRG方法計算獲得的點通常不滿足約束條件。它們只對這些約束條件的線性逼近可行?，F(xiàn)在我們討論如何在一個不可行的點使用GRG方法：第一階段問題是構(gòu)建一個滿足約束條件的點。第一階段的目標函數(shù)是違反約束的絕對值總和。而第一階段問題的約束都是不違反約束的。假設(shè)我們在點開始計算，這個點不滿足第一個約束，但滿足第二個約束，所以第一階段問題是：一旦通過解決第一階段問題獲得一個適宜的解，那么上面闡述的方法就可以用來求最優(yōu)解。線性不等式約束最后，我們討論GRG是怎樣像解決等式問題那樣解決有不等式約束的問題。在每次迭代中，只有嚴格滿足不等式約束的量才能進入線性方程組，以消除變量（這些不等式約束通常被認為是有效的）。這個過程是復雜的，由于為了得到好的結(jié)果，在當前點的每一個不等式約束都有被舍棄的可能。我們在下面的例子中說明了這一點。圖5.5廣義簡約梯度算法的過程這個問題的可行集合顯示在圖5.5中。圖中的可行箭頭表示由每個約束指向的可行的超平面。假設(shè)我們從開始。這一點滿足所有約束條件。從圖5.5可以看出：,,三個約束條件是無效的，而約束是有效的。我們必須決定是否應該留在它的下界還是允許它離開邊界。。這表明如果我們沿方向移動，減少的最多，即減少增大。因為這個方向朝向可行區(qū)域內(nèi)部，我們決定從邊界釋放。新的點變成其中。這個約束引入了的一個上限，也就是。接下來我們通過線性搜索來確定在這個范圍之內(nèi)的最優(yōu)值。結(jié)果是，從而；參見圖5.5?，F(xiàn)在，我們重復這個過程：約束開始起作用，其他約束失效。因為活動約束不是一個簡單的上下限約束，我們引入一個剩余變量，然后將其中之一用其余變量表示。代入，我們得到如下化簡的優(yōu)化問題在簡約梯度為因此在方向降幅最大，也就是要增大并減小。但是已經(jīng)到達其下界，我們無法再減小它。因此我們保持在它的下界處，即我們沿方向到達新的點。沿這個方向的線性搜索給出，。接下來仍然是該約束有效，所以我們?nèi)匀辉诤偷目臻g中。在處的梯度與當前解的邊界線垂直，且指向可行區(qū)域的外部，因而不可能進一步減小。于是我們找到了最優(yōu)解。對應于最初的變量空間，這個最優(yōu)解就是和。這就是一些廣泛使用的非線性規(guī)劃求解方法，例如Excel的SOLVER,GINO,CONOPT,GRG2以及一些其他的方法用來求解非線性規(guī)劃問題的方法。具體求解時只需附加一些額外細節(jié)，例如線性搜索時的Newton-Raphson方向等。同線性規(guī)劃相比，能夠在一個合理的計算時間內(nèi)解決的問題通常規(guī)模比較小，并且求得的結(jié)果也可能不是特別精確。另外，可行集合或目標函數(shù)潛在的非凸性會導致求解結(jié)果是局部最優(yōu)的而遠非全局解。因此在解釋非線性規(guī)劃的結(jié)果時需要更加小心。5.5.2序列二次規(guī)劃考慮一般的非線性最優(yōu)化問題（5.20）為了解決這個問題，有人試圖利用可得到的較好的算法解決更有條理、更簡單的二次規(guī)劃（參見第七章）。這是連續(xù)二次方程背后的思想。在當前可行點，問題（5.20）是由一個二次規(guī)劃來近似的：拉格朗日函數(shù)的近似二次方程可以像近似的線性約束一樣計算。可以得到如下的二次方程規(guī)劃問題：其中，是拉格朗日函數(shù)（5.11）的海森矩陣，為當前估計的拉格朗日乘數(shù)。這個問題可以用解決二次方程規(guī)劃問題的一種特殊算法來解，例如我們在第七章討論的內(nèi)點方法。二次規(guī)劃的最優(yōu)解是用來確定搜索方向。那么線性搜索或信賴域程序是為了確定下一個迭代。也許思考序列二次規(guī)劃的最好方式是將其作為求解有約束條件問題的牛頓法的優(yōu)化版的擴展?；叵胍幌?，牛頓方法的優(yōu)化版使用目標函數(shù)的二次逼近，定義這個逼近的最小值作為下一次迭代值，這很像我們描述的SQP方法。的確，對于一個無約束問題，二次規(guī)劃與牛頓法是相同的。對于約束問題，在解決SQP時的二次規(guī)劃問題的最優(yōu)性條件相當于在當前迭代下牛頓法直接指向的原來問題的最優(yōu)化條件。序列二次規(guī)劃迭代直到該問題收斂。就像牛頓法一樣，二次規(guī)劃方法是非常強大，尤其是當運用線性搜索或信賴域方法來處理非線性和非凸性。我們推薦讀者翻閱BoggsandTolle[14]和NocedalandWright[55]來進一步了解二次規(guī)劃方法。5.6非光滑優(yōu)化：次梯度方法在這一部分，我們考慮無約束非線性規(guī)劃的形式當并且是一個不可微的凸函數(shù)。由于在此情況下沒有定義梯度，所以無法獲得基于梯度的最優(yōu)條件。然而，梯度的概念可被推廣如下。在點的次梯度是向量使對任意都成立。當函數(shù)是可微的，次梯度和梯度是相同的；當函數(shù)在點處不可微，通常在處有許多次梯度。例如，考慮含有一個變量的凸函數(shù) 從圖5.6可明顯看出這個函數(shù)在處是不可微的，并且很容易驗證任意使得的向量是在點處的次梯度。其中的一些次梯度以及它們所定義的線性逼近可由圖5-6所示。請注意每個函數(shù)的次梯度在一點處定義了一個函數(shù)的切線，而這些切線永遠待在函數(shù)圖像的下邊——這是次梯度定義的屬性?？紤]一個不可微的凸函數(shù)。在點處取得最小值當且僅當在點有一個為零的次梯度。在上述例子中，0是在點處的一個次梯度，因此我們得到的最小值點。圖5.6最速下降法可以通過計算任何次梯度方向且使用相反的方向擴展到不可微的凸函數(shù)來進行下一步。盡管次梯度方向不總是上升的方向，不過可以選擇適當?shù)牟介L保證收斂到最佳點。一般的次梯度方法可以表述為如下：1.初始化：從任一點開始，設(shè)；2.迭代：計算函數(shù)在點處的一個次梯度。如果或趨近于0，停止。否則，讓（表示一個步長，并進行下一次迭代。幾種選取步長的方法已在文獻中講過。為了保證收斂到最優(yōu)點，步長需要非常緩慢的遞減（例如