1、最優(yōu)化理論與方法講義(下-續(xù))第六章 常用約束最優(yōu)化方法考慮一般的約束最優(yōu)化問題，其數(shù)學模型為求解約束優(yōu)化問題，就是要在可行域中，找一個可行點使目標函數(shù)取得最小值。此時稱為問題的最優(yōu)解。由處理約束條件的辦法不同，約束優(yōu)化方法也可分為直接法和間接法兩大類。間接法的基本思想是將約束優(yōu)化問題首先轉(zhuǎn)換為一系列的無約束優(yōu)化問題，然后利用無約束優(yōu)化方法來求解，逐漸逼近約束問題的最優(yōu)解。這些算法一般比較復雜，但由于它們可以采用計算效率高、穩(wěn)定性好的無約束優(yōu)化方法，故可用于求解高維的優(yōu)化問題。直接法的基本思想是構(gòu)造一迭代過程，使每次迭代點都在可行域D中，且一步一步地降低目標函數(shù)值，直到求得最優(yōu)解。這類方法很多

2、，如約束坐標輪換法，復合形法等。這類方法一般是算法簡單，對目標函數(shù)和約束函數(shù)無特殊要求，但計算量大，需用機時較多，不適用維數(shù)較高的問題，而且一般用于求解只含不等式約束的優(yōu)化問題。6.1 外點罰函數(shù)法對于問題，本節(jié)所述方法的基本策略是，根據(jù)約束特點(等式或不等式)構(gòu)造某種“罰函數(shù)”，然后把它加到目標函數(shù)中去，使得對約束最優(yōu)化問題的求解轉(zhuǎn)化為對一系列無約束問題極小點或者無限地向可行域靠近，或者一直保持在可行集內(nèi)移動，直到收斂于原來約束最優(yōu)化問題極小點。一、外點罰函數(shù)法基本原理對問題，構(gòu)造一函數(shù)為其中 在式中，又稱為懲罰函數(shù)。，是一個逐漸增大的參數(shù)，稱為懲罰因子，又稱為問題的增廣目標函數(shù)。顯然，增廣

3、目標函數(shù)是定義在上的一個無約束函數(shù)。由增廣目標函數(shù)的構(gòu)造知：當時，此時的最優(yōu)解就是問題的最優(yōu)解；當時，的最優(yōu)解就不一定是問題的最優(yōu)解。但是研究當時，的最優(yōu)解我們是不感興趣的。為此規(guī)定：當時，在點處的函數(shù)值迅速增大。換句話說，可行域外的任一點處的函數(shù)值都相當大。此時要求在中的最優(yōu)解，只能讓點回到內(nèi)才有可能求得 在中的最優(yōu)解，然而一旦當點回到內(nèi)，即，此時就與問題就有相同的最優(yōu)解。當時，迅速變大是通過罰因子M來實現(xiàn)。簡言之，外點罰函數(shù)法的思想是：當點時，設(shè)法加大不可行點處的函數(shù)值，使不可行點不能成為在中的最優(yōu)解。一般地，在用外點罰函數(shù)法求解問題時，首先構(gòu)造增廣目標函數(shù)，然后按照無約束優(yōu)化方法求解。如

4、果求出的最優(yōu)解為，則判斷是否屬于。如果，則是問題的最優(yōu)解；如果，則不是問題的最優(yōu)解。此時說明原來的罰因子給小了，需加大罰因子，使得，然后再重新計算的最優(yōu)解。二、外點罰函數(shù)法迭代步驟已知問題，構(gòu)造增廣目標函數(shù)其中懲罰函數(shù)按式構(gòu)造，給定終止限(可取)。Step1 選定初始點，初始罰因子(可取)，罰因子放大系數(shù)，置；Step2 假設(shè)已獲迭代點，以為初始點，求解無約束問題，設(shè)其極小點為；Step3 若，則就是所要求的最優(yōu)解，輸出打印，停機；否則，轉(zhuǎn)Step4；Step4 置，轉(zhuǎn)Step2。三、舉例 例1 求解解：可以看出，本題的約束最優(yōu)解為現(xiàn)用外點罰函數(shù)法解這個約束優(yōu)化問題。構(gòu)造增廣目標函數(shù)由此 解得

5、 給定一個罰因子，即可求得極小點，可以看出 不是可行點，且有右圖給出了不同時的的軌跡。它有助于進一步理解用外點罰函數(shù)法求極小點序列時怎樣收斂于約束最優(yōu)點。 例2 用外點罰函數(shù)法求解: 增廣目標函數(shù)為按階躍函數(shù)的定義，對于，下圖畫出了的圖形由圖可以看出，的極小點全不屬于可行域。因此只須考慮的情況。實際上，對于固定的，令由此解得 這就是對于固定的，求得的極小點。例如，當時，；當時，；當時，。若令時，則。這里的，就是本例的極小點。四、外點罰函數(shù)法有關(guān)說明在外點罰函數(shù)中，是通過一系列懲罰因子求的極小點來逼近原約束問題的最優(yōu)點。這一系列的無約束極小點將從約束可行域外部向約束邊界運動，實際上，隨著罰因子的

6、增大，迫使懲罰項的值逐漸減小，從而使的極小點沿著某一運動軌跡逐漸接近等式約束面與起作用的不等式約束面上的最優(yōu)點。當趨于無窮大時，的極小點就是原問題的最優(yōu)點。容易提出這樣的問題：既然越大越好，那么迭代一開始就把取得很大，似乎求解一次無約束問題就可以求得到約束問題的最優(yōu)解，可以少解幾次無約束問題。但是可以證明，越大，增廣目標函數(shù) 的Hesse矩陣的條件數(shù)越壞，給無約束問題求解增加越來越大的困難，甚至無法求解。因此，在迭代開始時又不得不把取得小一些。無疑，這增加了計算量，這正是外點罰函數(shù)法的弱點。此外，當在處無定義時，的性質(zhì)變得很復雜。另一方面，由于外點罰函數(shù)法是從外迭代點逼近內(nèi)最優(yōu)解，所以在尋優(yōu)的

7、過程中不能直接觀察到內(nèi)點的變化情況，也無法求得近似最優(yōu)解。6.2 內(nèi)點罰函數(shù)法內(nèi)點罰函數(shù)法剛好克服了外點罰函數(shù)法的不足之處，內(nèi)點罰函數(shù)法的迭代過程均在可行域內(nèi)進行，它是通過在內(nèi)尋找一串點列來逼近最優(yōu)解。一、內(nèi)點罰函數(shù)法基本原理首先在的邊界設(shè)置一道障礙，當從可行域中的某點出發(fā)進行迭代時，每當?shù)c靠近的邊界時，便被此邊界上的障礙(形如絕壁)阻擋碰回，這種阻擋碰回實質(zhì)上也是一種懲罰，換句話說，所謂阻擋碰回就是當?shù)c靠近的邊界時，離邊界越近函數(shù)值增加越大，特別當?shù)c到達邊界上時，函數(shù)值變?yōu)闊o窮大。由此可以想象不可能在靠近的邊界上取得最優(yōu)解，只能在遠離的邊界內(nèi)找到最優(yōu)解。按照這種想法，對于構(gòu)造如下

8、增廣目標函數(shù)其中，稱為障礙因子，稱為障礙函數(shù)。下面我們來分析是否符合內(nèi)點罰函數(shù)法的構(gòu)造設(shè)想。顯然和都定義在內(nèi)，取值較小時，當?shù)c遠離邊界，此時的最優(yōu)解可作為問題的近似最優(yōu)解；但當?shù)c靠近的邊界時，由的構(gòu)造知，即使取值很小，但，即使得的函數(shù)值變得很大，此時顯然不可能在區(qū)域的邊界附近求得的最優(yōu)解，于是迫使迭代點被阻擋碰回到遠離區(qū)域的邊界去尋優(yōu)。用式子表示即是當障礙因子逐漸減小時，有 且 式中為的極小值點序列，為問題的最優(yōu)解。二、內(nèi)點罰函數(shù)法迭代步驟已知對問題，構(gòu)造增廣目標函數(shù)給定終止條件(可取)。Step1 選定初始點，初始障礙因子，障礙因子的縮小系數(shù)(可取)，置；Step2 假設(shè)已獲迭代點，

9、以為初始點，求解，設(shè)其最優(yōu)解為；Step3 若，則是問題的最優(yōu)解，打印輸出，停機；否則，轉(zhuǎn)Step4；Step4 置，轉(zhuǎn)Step2。二、舉例用內(nèi)點罰函數(shù)法求解: 構(gòu)造增廣目標函數(shù) 由 解得 給定一個罰因子，即可求得一極小點。右圖給出不同罰因子時的軌跡。可看出在可行域內(nèi)，且隨著逐漸逼近于0，逐漸逼近理論最優(yōu)點。三、內(nèi)點罰函數(shù)法有關(guān)說明內(nèi)點罰函數(shù)法的優(yōu)點在于每次迭代都是可行點，當?shù)揭欢ù螖?shù)時，盡管可能沒有達到約束最優(yōu)點，但可以被接受為一個較好的近似最優(yōu)點。在實際應用中，按該點求得的解可能比初始解有很大的改進，因而被工程技術(shù)人員接受，作為一種最優(yōu)設(shè)計方案。然而，內(nèi)點罰函數(shù)法要求初始點位于可行域內(nèi)

10、部，即所有的約束需按嚴格不等式滿足。這對于簡單的優(yōu)化問題是不難解決的，因為原設(shè)計方案可能是用常規(guī)設(shè)計方法求得的，雖然不是最優(yōu)，但一般是可行的，因此就可將原方案作為初始點。但對復雜的優(yōu)化問題，由于變量和約束較多，要想得到一個可行的初始點，并不十分容易，這時就要采用求解可行點的算法。在內(nèi)點罰函數(shù)法中，障礙函數(shù)的定義域是約束可行域。因此，在求的最優(yōu)解時，并不是求它在整個維歐氏空間中的最優(yōu)解，而是求在約束可行域上的極小點。這是因為障礙函數(shù)在D 的邊界上無定義，而在 的外部某些項為負，并且可取絕對值任意大的負值，從而使趨于，所以在全空間內(nèi)的極小點是不存在的。因此，在用無約束優(yōu)化方法求的最優(yōu)解時，要防止越

11、過約束邊界而搜索到非可行域中去，這就要求在一維搜索時，要適當控制步長，保證搜索在可行域內(nèi)進行。6.3 混合罰函數(shù)法前面介紹了外點罰函數(shù)法和內(nèi)點罰函數(shù)法。外點罰函數(shù)法的初始點可以任選，適用于求解具有等式約束與不等式約束的優(yōu)化問題；而內(nèi)點罰函數(shù)法要求初始點在可行域內(nèi)，適用于求解不等式約束優(yōu)化問題。為了綜合外點罰函數(shù)法與內(nèi)點罰函數(shù)法的優(yōu)點，常將兩種算法結(jié)合起來使用，這樣便形成了混合罰函數(shù)法。一、混合罰函數(shù)法基本原理對于同時具有不等式約束和等式約束的優(yōu)化問題，混合罰函數(shù)法采用的罰函數(shù)形式又分為內(nèi)點形式和外點形式兩種。下面介紹內(nèi)點形式的混合罰函數(shù)，即采用內(nèi)點形式的混合罰函數(shù)時，混合初始點應選為滿足各個不

12、等式約束條件的點，障礙因子亦應按內(nèi)點罰函數(shù)法取為遞減序列，即在混合罰函數(shù)中，的作用是限制搜索跳出不等式約束確定的區(qū)域，相當于內(nèi)點罰函數(shù)法。而的作用是迫使搜索點向等式約束面靠近，相當于外點罰函數(shù)法。二、混合罰函數(shù)法迭代步驟已知問題，構(gòu)造增廣目標函數(shù)給定終止準則(可取)。Step1 選定初始點，要求滿足不等式約束，初始障礙因子，懲罰因子縮小系數(shù)，置；Step2 假設(shè)已獲迭代點，以為初始點，求，設(shè)其最優(yōu)解為；Step3 若，則是問題的最優(yōu)解，輸出打印，停機；否則轉(zhuǎn)Step4；Step4 置，轉(zhuǎn)Step2。三、混合罰函數(shù)法有關(guān)說明為了加速罰函數(shù)法的收斂速度，可以采用外插技術(shù)。我們知道，在罰函數(shù)法中，給

13、定一個罰因子(可以是障礙因子，也可以是懲罰因子)就可以求的一個極小點，因此的極小點可以看作是的函數(shù)，記為。前面講過，當時，趨于約束最優(yōu)點。因此可以設(shè)想，只要能將的函數(shù)表達式寫出來，就可通過求極限的方法求得約束最優(yōu)點。為求的表達式，自然會想到利用前幾點，通過曲線的擬合來近似地予以反映，這就是外插技術(shù)基本思想。假定對于罰因子，已求得的極小點 則可用高次多項式來擬合極小點的軌跡曲線，即，則可用高次多項式來擬合極小點的軌跡曲線，即式中為系數(shù)向量，其值可由個線性方程組求得令，則得 它是約束最優(yōu)點的一個更好的逼近，可將其作為的極小點的初始點，這將有利于加速收斂。在實際應用中，常采用兩點外插法或三點外插法。

14、兩點外插法就是利用前兩次求得的的極小點和來外插求得。通常采用的外插公式為式中均為維向量。用已知和兩點，而且，代入上式可求得在式中令，即可求得外插點，也就是6.4 約束坐標輪換法約束坐標輪換法是在無約束坐標輪換法的基礎(chǔ)上，加入由約束函數(shù)構(gòu)成的可行性限制，使每次迭代都必須在可行域內(nèi)進行。它的基本思想是將一個維的約束優(yōu)化問題轉(zhuǎn)化為依次沿個坐標軸方向輪流進行迭代的一維搜索問題。一、約束坐標輪換法基本原理對于維約束優(yōu)化問題，依次沿坐標向量的方向進行搜索時，由于只能在可行域內(nèi)進行搜索，故不宜采用最優(yōu)步長，以免越出可行域。為此，通常利用加步搜索法來確定搜索步長，以求得一系列可行點，使目標函數(shù)值逐次下降，直至

15、收斂到最優(yōu)解?，F(xiàn)以下圖所示的二維情況進行說明。設(shè)已知初始點且滿足約束條件，用步長沿坐標軸方向的正方向搜索到點時；因目標函數(shù)的值增大(這意味著試探失敗)，故改為自點沿的負方向搜索得點，該點在可行域內(nèi)，且使目標函數(shù)值有所下降(這意味著試探成功)，說明該點同時滿足可行性與適用性兩個條件，于是再由點出發(fā)，按加速步長搜索至點，此點仍在可行域內(nèi)，且該點的目標函數(shù)值繼續(xù)下降；于是再按加速步長搜索至點，但此點已越出了可行域，即不滿足可行性條件，故舍棄點退回到點并記其為。再由該點出發(fā)，轉(zhuǎn)為用步長沿坐標軸方向搜索，得點，該點在可行域內(nèi)，且使目標函數(shù)值下降；當加速步長為后，所得的點雖在可行域內(nèi)，但不能使目標函數(shù)值下

16、降，故予以舍棄，仍退回到點，并記其為。至此，第一輪搜索完畢。如點已能滿足計算精度，則停止搜索；否則，視該點為初始點，轉(zhuǎn)入第二輪搜索，如果所求的最終點與初始點相同，則將步長縮小，即取步長為，然后重新進行搜索，直至求得滿足計算精度的最優(yōu)點。二、 約束坐標輪換法迭代步驟已知目標函數(shù)，約束函數(shù)，終止限，步長縮放因子。Step1 選取初始點，初始步長，置；Step2 由出發(fā)，按步長，沿坐標軸的正方向進行搜索，取如果且，則取，即加速向前搜索，直到不滿足可行性條件或適用性條件，然后退回前一搜索點，將其作為該方向的最終點。如果沿的正方向搜索不到能同時滿足可行性條件和適用性條件的點，則改為沿的負方向搜索，即取搜

17、索步長為，仿照沿正方向的搜索過程，求得該方向的最終點。如果沿的正、負兩方向搜索均失敗，則將點作為該方向的最終點，然后轉(zhuǎn)向下一個坐標軸方向繼續(xù)進行搜索。Step3 由出發(fā)，沿坐標軸方向進行搜索，按Step2的做法，求得該方向的最終點；以此類推，直到沿第n個坐標軸方向進行一維搜索完畢，得到設(shè)計點。至此，完成了第 k輪搜索，記第 k輪搜索得到的最優(yōu)點為。Step4 若轉(zhuǎn)Step5；否則需要進行下一輪搜索，即令，轉(zhuǎn)Step2；Step5 進行步長判別，如果步長已縮短到足夠小時，即滿足時，則為最優(yōu)點，輸出，停機結(jié)束。否則，收縮步長，即令，轉(zhuǎn)Step2。三、約束坐標輪換法有關(guān)說明約束坐標輪換法具有算法明了

18、，迭代簡單，便于使用者掌握運用等優(yōu)點。但是，它的收斂速度較慢，對于維數(shù)較高的優(yōu)化問題很費機時。另外，這種方法在某些情況下還會出現(xiàn)“死點”的病態(tài)，導致輸出偽最優(yōu)點。為了辨別輸出最優(yōu)點的真?zhèn)?，可用條件來檢驗。通常的做法是輸入多個初始點，并給出各種不同的初始步長進行多次運算，再從眾多的輸出解中進行比較而排除偽最優(yōu)點。6.5 乘子法乘子法的提出克服了罰函數(shù)法中增廣目標函數(shù)的病態(tài)性質(zhì)等缺點，同時構(gòu)造的增廣目標函數(shù)具有較好的光滑性質(zhì)。乘子算法是從問題的Lagrange函數(shù)出發(fā)，考慮它的精確懲罰，從而將約束優(yōu)化問題轉(zhuǎn)化為單個函數(shù)的無約束優(yōu)化問題。此方法具有較好的收斂速度和數(shù)值穩(wěn)定性，是求解約束優(yōu)化問題的主要

19、而有效的算法。一、等式約束的非線性優(yōu)化問題的乘子法考慮下面僅含等式約束的非線性規(guī)劃問題(Nonlinear Equality constraint programming，NEP)： 設(shè)為該問題的最優(yōu)解，其Lagrange函數(shù)為 其中是與相應的Lagrange乘子向量。在一定條件下存在使為Lagrange函數(shù)式的駐點(或稱穩(wěn)定點)，即一個自然的問題是，能否找到使得是Lagrange函數(shù)的極小點。如果這樣的話，約束問題就轉(zhuǎn)化為無約束問題。例如：求解約束問題此問題的最優(yōu)解為。而Lagrange函數(shù)為對于任何，關(guān)于的極小點不存在。 通常，的極小解往往是不存在的，為避免此情況的發(fā)生，對于等式約束問題，

20、我們構(gòu)造了增廣的Lagrange函數(shù)由得到即是的一個穩(wěn)定點。定理6.5.1 設(shè)是NEP問題的最優(yōu)解，且滿足二階充分條件，其相應的Lagrange乘子為，則當充分大時，是無約束優(yōu)化問題的最優(yōu)解，且滿足二階充分條件。定理6.5.2 對給定的和，設(shè)是無約束優(yōu)化問題的最優(yōu)解，且滿足二階充分條件。如果，則也是NEP問題的最優(yōu)解，且滿足二階充分條件。由定理6.5.1可知，若能找到和一個充分大的，則的最優(yōu)解就是NEP問題的最優(yōu)解。然而，這是一個非常困難的事情。定理6.5.3 設(shè)在NEP問題中，和滿足二階充分條件，則存在一個數(shù)，對所有的，是增廣目標函數(shù)的嚴格局部極小點；反之，若且對某個是增廣目標函數(shù)的局部極小

21、點，則是等式約束問題的局部極小點。由定理6.5.3可知，乘子法并不要求趨于無窮大。只要大于某個正數(shù)，就能保證無約束問題的最優(yōu)解為原問題的最優(yōu)解。問題一：如何確定?采用迭代的方法求出。首先以某個參數(shù)代替，求解無約束問題，得到其解為；然后修正為，再求解，得到兩個點列，希望。問題二：如何對進行修正?設(shè)已有和，由的定義即 則當充分大時，有 又由于乘子滿足一階必要條件 比較式和式，得到 這就推導出了乘子的迭代公式 若收斂，則有；若，則有，即為可行解。舉例：用乘子法求解下列非線性優(yōu)化問題解：令增廣Lagrange函數(shù)則 取，初始乘子，令，得到設(shè)第次迭代的乘子為，則的極小值點為由修正公式，則由于序列單調(diào)有界

22、，故其收斂。令，兩邊同取極限，得到最優(yōu)Lagrange乘子。同時，這樣就得到問題的最優(yōu)解。等式約束問題的乘子法步驟Step1選定初始點，初始乘子向量，初始參數(shù)，輔助無約束優(yōu)化問題的精度，令；Step2 以為初始點，求解無約束優(yōu)化問題的解，使得Step3 修正乘子；Step4 如果，最優(yōu)解，停止計算；否則，令，轉(zhuǎn)Step2。二、不等式約束的非線性優(yōu)化問題的乘子法以下考慮僅含不等式約束的非線性規(guī)劃問題： 對于不等式約束問題，引進輔助變量，則問題可改為等式約束問題 定義其增廣Lagrange函數(shù)為 從而將問題轉(zhuǎn)化為求解。求解思路：先考慮對這一函數(shù)關(guān)于求極小，由此解出，并代入式；然后將其化為只關(guān)于求極

23、小值的問題。具體方法：由配方法得到 為使關(guān)于取極小，取值如下：l 當時，；l 當時，。綜合以上兩種情形，即 將式代入式，得到新的增廣Lagrange函數(shù) 這樣就將問題轉(zhuǎn)化為求解無約束問題。乘子迭代公式： 終止準則： 舉例：用乘子法求解下列非線性優(yōu)化問題解：增廣Lagrange函數(shù)則 令，得到的無約束極小值點取，令初始乘子，得到的極小值點。然后修正，令，求得的極小值點。依次類推，設(shè)在第次迭代的乘子為，求得的極小值點 由修正公式得到顯然序列收斂，且，以及，求得問題的最優(yōu)解 。三、一般形式的約束非線性優(yōu)化問題的乘子法一般形式的約束非線性優(yōu)化問題的增廣Lagrange函數(shù)定義為 Lagrange乘子的

24、修正公式如下： 6.6 投影梯度法1960年Rosen提出了用梯度投影法可以求出一個可行下降方向，用這種方法來解具有線性約束的非線性規(guī)劃?？紤]問題： 其中是矩陣，是矩陣，是維向量，是維向量，連續(xù)可微。6.6.1 下降可行方向及其性質(zhì)定義1 設(shè)為矩陣，若且，則稱為投影矩陣。引理1 設(shè)為矩陣 (1)若為投影矩陣，則必半正定；(2) 為投影矩陣的充要條件是為投影矩陣，其中為單位矩陣；(3) 若為投影矩陣，記，則和是互補的正交線性子空間，并且對，可唯一地表示為。證明：(1) 對于，由可知為半正定。(2)必要性。設(shè)為投影矩陣，顯然 由定義知：為投影矩陣。 充分性。設(shè)為投影矩陣，則，由必要性所證為投影矩陣

25、，即為投影矩陣。(3)由于都是子空間，并且故 又，所以是的直和，因此是互補的正交線性子空間。此外，這種表示法顯然是唯一的，若不然，則 由于，正交，那么，則有 故有 定義2 由引理，可唯一地分解成，其中稱為在子空間中的投影，稱為在子空間中的投影，稱為到子空間的投影矩陣，為到子空間的投影矩陣。在可行點處，將分解為并要求 因此，全部起作用約束的系數(shù)矩陣為假定矩陣是行滿秩的(否則可以刪去多余的線性相關(guān)的行向量使之為滿秩)。設(shè)，再將的行向量重新記為，且分別是點的這個起作用約束的超平面的法向量。顯然，它們都與這個起作用約束超平面的交集正交。如果把張成的子空間記為，那么，起作用約束超平面的交集恰好是的正交補

26、空間，記為。又由于并且為行滿秩，則滿秩。故為投影矩陣，記為(即由到子空間的投影矩陣)。由前面的引理知， 也為投影矩陣(即由到子空間的投影矩陣)。下面證明：只要，則的方向就是點的一個可行下降方向。定理1 假設(shè)(1) 是式的某個可行點；(2) 適當調(diào)換的行向量與的相應分量并設(shè)所得矩陣以及向量仍用和表示，然后分解，相應地分解，使得 那么，非零向量為點出發(fā)的可行方向向量的充要條件是 證明：必要性。 若非零向量是從點出發(fā)的可行方向向量，則存在，對于，有 又由于，則由式得充分性。對任意，利用，由式可推出式。又由，存在，當時，使得將上式與式合并知，當時，是可行點，因此是可行方向向量。定理2 在式中，假設(shè)：(

27、1) 是式的某個可行點；(2) 分解，相應地分解，使得 ；(3) 是滿秩矩陣；(4) 且，則的方向是下降可行方向。證明：由于所以，是在點處的一個下降方向。 由因由(3)可知 則由定理1可知可行方向向量。綜上所述，我們得到的方向是下降可行方向。6.6.2 直線搜索及終止準則 從點出發(fā)沿可行下降方向作直線搜索得到新的迭代點，步長因子的上界可按如下方式確定： 其中都是與維數(shù)(設(shè)為)相等的向量。 然后再求解：設(shè)其最優(yōu)解為，則得到新的迭代點：由于當時，的方向是可行下降方向；而當時，因其中。因是階矩陣，那么是維向量，與的分解相對應，分解為。當時，由點定義可知，是點，計算終止。結(jié)論：終止準則是在的前提下，。當，但時，可從中刪去與的某個負分量相對應的行向量，將改變?yōu)橹匦聵?gòu)造下降可行方向。定理3 在式中，假設(shè)：(1) 是某個可行點；(2) 分解，相應地分解，使得 ；(3) 是滿秩矩陣，記，與的分解相對應，將分解為；(4) ，其中；(5) ，假定它的第個分量；從中刪去第行向量得到，并設(shè)。那么，的方向是點處的一個可行下降方向。以上可見，在每次迭代中都要重新計算正交投影矩陣及求逆。但在迭代中僅有