從算法的性能指標(biāo)看數(shù)值優(yōu)化算法的創(chuàng)新性設(shè)計

王宜舉 陳海濱

[摘 要] 最優(yōu)化問題的數(shù)值算法是運(yùn)籌學(xué)專業(yè)研究生專業(yè)課“最優(yōu)化方法”的核心。為提高研究生數(shù)值優(yōu)化方法的學(xué)習(xí)效果和創(chuàng)新設(shè)計能力，對該教學(xué)內(nèi)容，我們給出了數(shù)值優(yōu)化算法的若干性能分析，并指出了設(shè)計高效數(shù)值優(yōu)化算法時需注意的一些問題。

[關(guān)鍵詞] 最優(yōu)化算法;性能分析;創(chuàng)新性設(shè)計

一、引言

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

二、最優(yōu)化問題數(shù)值算法的性能分析

眾所周知，最優(yōu)化問題的一個數(shù)值方法要被認(rèn)可，既要有一定的理論保證，又要有滿意的數(shù)值效果。對此，我們給出數(shù)值方法的有關(guān)性能指標(biāo)。

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

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

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

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

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

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

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

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

三、最優(yōu)化方法的創(chuàng)新性設(shè)計

根據(jù)前一節(jié)給出的數(shù)值算法的性能分析，下面給出在進(jìn)行最優(yōu)化問題的數(shù)值算法設(shè)計時的注意要點(diǎn)。

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

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

3.充分挖掘問題的結(jié)構(gòu)性質(zhì)。不同的問題有不同的結(jié)構(gòu)，不同的結(jié)構(gòu)有不同的算法。如果套用一種算法求解不同的最優(yōu)化問題，數(shù)值效果會很差。反之，如果我們能充分挖掘問題的結(jié)構(gòu)性質(zhì)，并在算法設(shè)計時充分利用問題的結(jié)構(gòu)特點(diǎn)，設(shè)計針對該問題的數(shù)值算法，效率就會高。

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

參考文獻(xiàn)

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

[2]袁亞湘.非線性最優(yōu)化數(shù)值方法[M].上海：上?？茖W(xué)技術(shù)出版社，1993.

[3]倪勤.最優(yōu)化方法與程序設(shè)計[M].北京：科學(xué)出版社，2009.

[4]王宜舉，修乃華.非線性最優(yōu)化理論與方法[M].北京：科學(xué)出版社，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.