從算法的性能指標看數值優化算法的創新性設計

王宜舉 陳海濱

[摘 要] 最優化問題的數值算法是運籌學專業研究生專業課“最優化方法”的核心。為提高研究生數值優化方法的學習效果和創新設計能力，對該教學內容，我們給出了數值優化算法的若干性能分析，并指出了設計高效數值優化算法時需注意的一些問題。

[關鍵詞] 最優化算法;性能分析;創新性設計

一、引言

最優化問題的數值算法是運籌學專業研究生專業課“最優化方法”的基礎和核心，最優化問題的數值算法種類繁多，而要學習好這些算法并能設計新的有效算法，首先要掌握好算法的性能分析[1-6]。那么，對最優化問題的數值算法，我們從哪些方面進行比較？如何在此基礎上設計更有效的數值算法？對此，我們先給出最優化問題數值算法的一些評價指標，然后指出設計最優化問題數值算法時的一些注意事項，以期提高研究生數值優化算法的學習能力和創新設計能力。

二、最優化問題數值算法的性能分析

眾所周知，最優化問題的一個數值方法要被認可，既要有一定的理論保證，又要有滿意的數值效果。對此，我們給出數值方法的有關性能指標。

1.收斂性與收斂速度。除非問題特殊，對最優化問題的數值算法，很難保證在有限步驟內得到優化問題的最優解。因此，人們寄希望于該算法產生的迭代點列能一步步靠近最優化問題的最優解，這便引出了算法收斂性的概念。

具體地，如果從任意的初始點出發，算法產生的迭代點列都收斂到最優化問題的最優解，則稱該算法具有全局收斂性。若算法只有在初始點和最優解具有某種程度靠近時才能保證算法產生的迭代點列收斂到最優解，則稱該算法具有局部收斂性。特別地，若算法產生的迭代點列的某聚點為最優化問題的最優解，則稱該算法弱收斂。

在上述兩收斂速度中，超線性收斂比線性收斂速度快。若一個迭代點列Q-（超）線性收斂，則它必R-（超）線性收斂。

2.算法穩定性，也就是算法的可靠性。眾所周知，在數值計算時，初始數據的舍入誤差會通過系列數據運算進行遺傳和傳播。如果起始數據的誤差對最終結果的影響較小，即在運算過程中舍入誤差增長緩慢，則稱該算法是穩定的。若輸出結果的誤差隨起始數據的舍入誤差呈惡性增長，則稱該算法是不穩定的。對后者，算法的舍入誤差需要適當控制，否則就會像蝴蝶效應一樣，使風和日麗的地區幾個月后出現狂風暴雨。

3.計算復雜性和存儲消耗。一個算法要保持高的計算效率，每一迭代步的計算量和存儲量是一重要因素。為此，一個快速高效的數值算法，每一迭代步的計算量或存儲量不應過大，否則會導致算法的迭代進程變緩，從而影響算法的效率。

上述三指標主要側重算法的理論分析，如最壞情況分析和最好情況分析。它一方面使我們清楚算法對良態問題所具有的誘人性質和對病態問題可能呈現的最壞結果，從而找到算法所適用的問題類;另一方面使我們明白怎樣取初始點，怎樣取參數，同時幫助我們發現算法中的缺陷，進而改進之。需要說明的是，人們在進行最優化問題的數值算法的理論分析時，一般要對問題或其最優解做些某些假設，而這些假設多數難于驗證。

4.數值效果。對最優化問題的數值方法進行數值實驗是算法設計的重要一環。因為，最優化問題的數值算法最終能否被接受和認可關鍵在于其數值效果。其次，數值試驗有時會很可靠地顯露出某些可能的理論結果。只是在進行數值計算的時候，參數的取值和初始點的選取對數值效果的影響較大，同時，也要注意到，對同一算法，在程序的編制過程中，子程序和函數的調用、數據的調取和存儲、數據運算的簡化等對算法的數值結果影響較大。

一般地，一個好的數值優化算法不但要有好的理論性質，同時還要有誘人的數值效果。遺憾的是，如同線性規劃問題的單純形算法和Karmarkar算法，最優化問題的很多數值算法很難在數值效果和理論分析方面達到完美的統一。截至目前，人們還未找到一個理論性質和數值效果都令人滿意的通用算法。一般情況下，人們只能宣稱某個算法對某類問題有效。這也是非線性最優化問題的數值方法研究中多種方法并存的主要原因。

三、最優化方法的創新性設計

根據前一節給出的數值算法的性能分析，下面給出在進行最優化問題的數值算法設計時的注意要點。

1.嚴格控制每一迭代步的計算量。數值算法在每一迭代步的計算量是算法效率的保障。如果每一迭代步的計算量太大，必然導致算法在迭代過程中步履蹣跚，緩慢向前。

2.充分利用已產生迭代點的信息。除初始點外，一個算法在迭代過程中，已產生迭代點的信息是一寶貴的資源。它一方面顯示迭代點列的大致走向，另一方面自覺不自覺地預示著迭代點附近最優值點的信息。所以，只有充分利用這些信息，才能保障算法的穩定性。

3.充分挖掘問題的結構性質。不同的問題有不同的結構，不同的結構有不同的算法。如果套用一種算法求解不同的最優化問題，數值效果會很差。反之，如果我們能充分挖掘問題的結構性質，并在算法設計時充分利用問題的結構特點，設計針對該問題的數值算法，效率就會高。

4.算法的不斷更新。一個新設計的數值算法在進行數值計算時數值效果可能不令人滿意，但這并不意味著算法完全不可取，有時候只要我們對算法適當修正就可以大幅度提高算法的效率。

參考文獻

[1]陳寶林.最優化理論與方法[M].北京：清華大學出版社，1989.

[2]袁亞湘.非線性最優化數值方法[M].上海：上海科學技術出版社，1993.

[3]倪勤.最優化方法與程序設計[M].北京：科學出版社，2009.

[4]王宜舉，修乃華.非線性最優化理論與方法[M].北京：科學出版社，2012.

[5]Bazaraa MS，Sherali HD，Shetty CM.Nonlinear Programming Theory and Algorithms[M].John Wiley and Sons，New York，1993.

[6]Bertsekas DP.Nonlinear Programming[M].Athena Scientific，1999.