非線性最優化理論與演算法
第一章引論
本章首先給出了一些常見的最優化問題和非線性最優化問題解的定義，並且根據不同的條件對其進行了劃分。接著給出了求解非線性優化問題的方法，如**法等，同時又指出乙個好的數值方法應對一些指標有好的特性，如收斂速度與二次終止性、穩定性等。隨後給出了在非線性最優化問題的理論分析中常用到的凸集和凸函式的定義和有關性質。
最後給出了無約束優化最優性條件。
第二章線搜尋方法與信賴域方法
無約束優化的演算法有兩類，分別是線搜尋方法和信賴域方法。本章首先給出了兩種線搜尋方法即精確線搜尋方法和非精確線搜尋方法。線搜尋方法最重要的兩個要素是確定搜尋方向和計算搜尋步長，搜尋步長可確保下降方法的收斂性，而搜尋方向決定方法的收斂速度。
精確線搜尋方法和非精確線搜尋方法
對於精確線搜尋方法，步長滿足
這一線搜尋可以理解為是)在正整數區域性極小點，則不論怎樣理解精確線搜尋，它都滿足正交性條件：
)=0但是精確搜尋方法一般需要花費很大的工作量，特別是當迭代點遠離問題的解時，精確的求解問題通常不是有效的。而且有些最優化方法，其收斂速度並不依賴於精確搜尋過程。對於非精確搜尋方法，它總體希望收斂快，每一步不要求達到精確最小，速度快，雖然步數增加，則整個收斂達到快速。
書中給出了三種常用的非精確線搜尋步長規則，分別是armijo步長規則、goldstein步長規則、wolfe步長規則。第乙個步長規則的不等式要求目標函式有乙個滿意的下降量，第二個不等式控制步長不能太小，這一步長規則的第二式可能會將最優步長排除在步長的候選範圍之外，也就是步長因子的極小值可能被排除在可接受域之外。但wolfe步長規則在可接受的步長範圍內包含了最優步長。
在實際計算時，前兩種步長規則可以用進退試探法求得，而最後一種步長規則需要借助多項式插值等方法求得。緊接著，又介紹了armijo和wolfe步長規則下的下降演算法的收斂性。
信賴域方法
線性搜尋方法都是先方向再步長，即先確定乙個搜尋方向，然後再沿著這個搜尋方向選擇適當的步長因子，新的迭代點定義為=+。與線搜尋方法不同，信賴域方法是先步長再方向,此方法首先在當前點附近定義目標函式的乙個近似二次模型，然後利用目標函式在當前點的某鄰域內與該二次模型的充分近似，取二次模型在該鄰域內的最優值點來產生下一迭代點。它把最優化問題轉化為一系列相對簡單的區域性尋優問題。
信賴域方法的思想為：設當前點的鄰域定義為
=其中，稱為信賴域半徑。
目標函式在極值點附近近似乙個二次函式，因此對於無約束優化問題，利用二次逼近，構造如下信賴域模型。一般的，信賴域模型的目標函式取為
=+d+d
其中，對稱，是在處hesse陣或者其近似。這個問題就是信賴域方法模型的子問題。
設是信賴域子問題的解，我們稱目標函式在第k步的實下降量
=- 函式的預下降量
=-定義比值
=它衡量了二次模型與目標函式的逼近程度。一般的，。若0， +不能作為下一迭代點，需要縮小信賴域半徑，重新計算；若且靠近1，說明二次模型與目標函式在信賴域內有很好的近似，在下一迭代時可以擴大信賴域半徑；對其他情況信賴域半徑不變。
隨後又給出了信賴域演算法，只是由於信賴域模型利用負梯度方向為搜尋方向，演算法的效率很低，然後就給出了建立信賴域方法超線性收斂性的子問題的三種求解方法，分別是折線法、二維子空間方法和精確解方法。
信賴域方法和線性搜尋方法是求解非線性優化問題的兩類主要的數值方法。與線性搜尋方法相比，信賴域方法思想新穎，具有可靠性、有效性和很強的收斂性。
第三章最速下降法與牛頓方法
本章主要介紹最速下降法和牛頓方法，最速下降法又稱為梯度法，是根據目標函式的線性近似得到的，但是它的收斂速度並不快。相比之下，牛頓方法具有快的收斂速度，它是根據目標函式的二次近似得到的，是沒有步長搜尋的演算法。
最速下降法
最速下降法從目標函式的負梯度方向一直前進，直到達到目標函式的最低點。書中首先給出了最速下降法的演算法和演算法的性質，然後討論了最速下降法的收斂速度。
最速下降方法的迭代公式是：
=+其中=-為最速下降方向， =+)為最優步長。
在最速下降法中，兩個相鄰的搜尋方向是正交的，即
=0最速下降法具有鋸齒現象，即在極小點附近，目標函式可以用二次函式近似，其等值面近似於橢圓面，長軸和短軸分別位於對應最小特徵值和最大特徵值的特徵向量的方向。其大小與特徵值的平方根成反比。
最速下降法有一定的優點，如計算量小，儲存量小，對初始點沒有特殊要求，有著很好的全域性收斂性。但是最速下降法是線性收斂的，當接近最優解時，收斂速度很慢，原因是=-僅反映在處的區域性性質，以及相繼兩次迭代中搜尋方向是正交的。
牛頓方法
牛頓方法是用目標函式的二階展開式來近似的，並用其最小值點來產生下一迭代點得到的。
設函式二階連續可微。在點的二階近似展開式為
++s若正定，則是凸函式。利用一階最優性條件
s=-可得二次函式的最小值點=-
根據目標函式在當前點附近與二次函式的近似，將作為下一迭代點就得到牛頓演算法，其中-稱為牛頓方向。
牛頓演算法最終得到的是目標函式的穩定點。對於嚴格凸二次函式，牛頓演算法一步就可以得到目標函式的全域性最優值點，而對一般的非二次函式，該演算法也可以很快地搜尋到最優值點。它是借助目標函式在當前點的二階taylor展開式的最小值點逐步逼近目標函式的最小值點，它有很快的收斂速度。
牛頓演算法雖然有很快的收斂速度，但是它嚴重依賴於初始點的選擇，而且在每次迭代過程中需要計算目標函式的梯度和hesse矩陣，這就導致演算法效率降低。第四章共軛梯度法
共軛梯度法是介於最速下降法和牛頓方法之間的一種無約束優化演算法，它具有超線性收斂速度。它跟最速下降法相類似，共軛梯度法只用到了目標函式及其梯度值，避免了hesse矩陣的計算。因此，它是求解無約束優化問題的一種比較有效而實用的演算法。
本章首先講述了線性共軛方向法，接著給出了線性共軛梯度法和非線性共軛梯度法，最後講述了共軛梯度法的收斂性。
線性共軛方向法
共軛方向法的基本思想是在求解n維正定二次目標函式極小點時產生一組共軛方向作為搜尋方向。在精確線搜尋條件下演算法最多迭代n步，即能求得極小點。書中首先給出了線性共軛方向法。
對於二次規劃問題
關於係數矩陣構造共軛方向，再沿之進行線搜尋，這樣便得到線性共軛方向法。
接著書中給出了共軛方向的定義和具體的線性共軛方向法及演算法的收斂定理。對於凸二次函式，無論共軛方向法從哪點出發，至多次迭代後都終止於目標函式的最優值點。這個演算法具有二次終止性，但是它僅是乙個概念性演算法，實現它的關鍵在於如何選取共軛方向，不同的選取會產生不同的共軛方向法。
而且該性質與搜尋方向的次序無關。
對於線性共軛方向法，若係數矩陣為正的對角陣，則該方法相當於依次沿個正座標軸方向進行精確線搜尋。這種演算法克服了最速下降法的慢收斂性，又避免了牛頓法的計算量大和區域性收斂性的缺點。演算法簡單，易於程式設計，需儲存空間小等優點，是求解大規模問題的主要方法。
線性共軛梯度法
**性共軛方向法中，取便得到線性共軛梯度法。對於嚴格凸二次函式，僅利用，而無需利用前-1個搜尋方向，，…，就可得到與前個搜尋方向，，…，共軛的搜尋方向。
首先給出了共軛梯度法的迭代公式為
其中， =0，由=來決定。對於凸二次函式，最優步長
=-接著給出了完整的線性共軛梯度法和共軛梯度法的性質定理，通過它的性質，我們可以得到最優步長的計算公式可簡化為，利用=和和式，引數的計算公式可化簡
由共軛梯度法的迭代公式，容易發現其迭代過程僅比最速下降法稍微複雜一點，但卻具有二次終止性。由於該方法源於線性方程組求解，而且取負梯度方向，故它被稱為線性共軛梯度法。
對嚴格的凸二次函式，牛頓演算法具有一步終止性，共軛梯度法具有步終止性。對凸二次函式。共軛梯度法至多步終止。實際上，若矩陣a有r個相異特徵值，則它至多r步迭代後終止。
並且還有設是凸二次函式的最優值點，則
則最後通過一系列的分析證明，我們可知線性共軛梯度法的效率與矩陣a的條件數密切相關。為降低矩陣a的條件數，如果引入線性變換（其中t為一非奇異矩陣），則原凸二次規劃問題轉化為
通過以上的分析我們不難發現，對於大規模線性方程組問題，線性共軛梯度法往往成為首選，不過，對於小規模的線性方程組問題，gauss消元法更簡便。
非線性共軛梯度法
線性共軛梯度法在求凸二次函式的最小值點時有良好的性質，將其應用於無約束非線性最優化問題就得到非線性共軛梯度法。
對於共軛梯度法的搜尋方向，引數有多種表達形式。
下面為常見的幾種：
（cw公式）
（fr公式）
(pr公式)
（dixon公式）
（dy公式）
在最優步長規則下，對凸二次函式，這些表示式是等價的。但目標函式為非二次函式時，效果就不一樣了，從而匯出不同的演算法。對於fr方法，若採用強wolfe步長規則，則是下降方向。
對於pr方法，強wolfe步長規則不能保證的下降性。對於dixon方法，若採用下面的非精確線搜尋條件
， 則搜尋方向滿足下降條件。所以該公式又稱為共軛下降公式。
線性共軛梯度法具有二次終止性，但對於非線性共軛梯度法，即使採用最優步長規則，搜尋方向的共軛性質也不一定成立，從而難以在有限步內得到目標函式的最優值點。即使這樣，非線性共軛梯度法仍優於最速下降演算法，而且非線性共軛梯度法的收斂速度高於線性收斂。
共軛梯度法的收斂性
書中通過一系列的性質定理講述了共軛梯度法的收斂性。通過這些性質定理，我們不難發現共軛梯度法的收斂速度優於最速下降法，而且計算量小計算簡單。適合於優化變數數目較多的中等規模優化問題。
但是它也有一定的缺點，在某些情況下，它的收斂速度是線性的，收斂速度不如牛頓方法快。
通過書中的定理證明，我們知道對fr演算法，設強wolfe步長規則下的fr方法在第k步產生乙個下降性質不好的搜尋方向和由此產生乙個較短的步長。如果是乙個下降性質不好的搜尋方向，即與幾乎正交，則與非常靠近，從而。雖然pr方法的數值效果比fr方法好，但powell給出的反例說明，即使目標函式二次可微，水平集有界，並且採用精確線搜尋，pr方法會產生乙個任一聚點均不是穩定點的迭代點列。
儘管如此，當目標函式一致凸並採用最優步長時，pr方法全域性收斂。
非線性規劃
習題六6.1 試計算函式f x x12 x1x2 x22 的梯度和hesse矩陣。6.2 試證明下述函式f x 2x1x2x3 4x1x3 2x2x3 x12 x22 x32 2x1 4x2 4x3具有駐點 0，3，1 0，1，1 1，2，0 2，1，1 2，3，1 再應用充分性條件找出其極點。6....
非線性規劃的粒子群演算法1
xx大學 智慧型優化演算法課內實驗報告書 非線性規劃問題的粒子群演算法 1.1 背景介紹 1.1.1 非線性規劃簡介 具有非線性約束條件或目標函式的數學規劃，是運籌學的乙個重要的分支，目標函式和約束條件都是線性函式的情形則屬於線性規劃。非線性規劃是20世紀50年代才開始形成的一門新興學科。1951年...
求解非線性規劃
非線性規劃的例項與定義 如果目標函式或約束條件中包含非線性函式，就稱這種規劃問題為非線性規劃問題。一般說來，解非線性規劃要比解線性規劃問題困難得多。而且，也不象線性規劃有單純形法這一通用方法，非線性規劃目前還沒有適於各種問題的一般演算法，各個方法都有自己特定的適用範圍。1.2 線性規劃與非線性規劃的...