最優(yōu)化在航空航天、生命科學、水利科學、地球科學、工程技術等自然科學領域和經(jīng)濟金融等社會科學領域有著廣泛和重要的應用, 它的研究和發(fā)展一直得到廣泛的關注. 最優(yōu)化的研究包含理論、方法和應用.最優(yōu)化理論主要研究問題解的最優(yōu)性條件、靈敏度分析、解的存在性和一般復雜性等.而最優(yōu)化方法研究包括構(gòu)造新算法、證明解的收斂性、算法的比較和復雜性等.最優(yōu)化的應用研究則包括算法的實現(xiàn)、算法的程序、軟件包及商業(yè)化、在實際問題的應用. 這里簡介一下線性和非線性最優(yōu)化理論、方法及應用研究的發(fā)展狀況。

1. 線性最優(yōu)化

線性最優(yōu)化, 又稱線性規(guī)劃, 是運籌學中應用最廣泛的一個分支.這是因為自然科學和社會科學中許多問題都可以近似地化成線性規(guī)劃問題. 線性規(guī)劃理論和算法的研究及發(fā)展共經(jīng)歷了三個高潮, 每個高潮都引起了社會的極大關注. 線性規(guī)劃研究的第一高潮是著名的單純形法的研究. 這一方法是Dantzig在1947年提出的,它以成熟的算法理論和完善的算法及軟件統(tǒng)治線性規(guī)劃達三十多年. 隨著60年代發(fā)展起來的計算復雜性理論的研究, 單純形法在七十年代末受到了挑戰(zhàn). 1979年前蘇聯(lián)數(shù)學家Khachiyan提出了第一個理論上優(yōu)于單純形法的所謂多項式時間算法--橢球法, 曾成為轟動一時的新聞, 并掀起了研究線性規(guī)劃的第二個高潮. 但遺憾的是廣泛的數(shù)值試驗表明, 橢球算法的計算比單純形方法差。

1984年Karmarkar提出了求解線性規(guī)劃的另一個多項式時間算法. 這個算法從理論和數(shù)值上都優(yōu)于橢球法, 因而引起學術界的極大關注, 并由此掀起了研究線性規(guī)劃的第三個高潮. 從那以后, 許多學者致力于改進和完善這一算法,得到了許多改進算法.這些算法運用不同的思想方法均獲得通過可行區(qū)域內(nèi)部的迭代點列, 因此統(tǒng)稱為解線性規(guī)劃問題的內(nèi)點算法.目前內(nèi)點算法正以不可抗拒的趨勢將超越和替代單純形法。

線性規(guī)劃的軟件, 特別是由單純形法所形成的軟件比較成熟和完善.這些軟件不僅可以解一般線性規(guī)劃問題, 而且可以解整數(shù)線性規(guī)劃問題、進行靈敏度分析, 同時可以解具有稀疏結(jié)構(gòu)的大規(guī)模問題.CPLEX是Bixby基于單純形法研制的解線性和整數(shù)規(guī)劃的軟件 。此外,這個軟件也可以用來解凸二次規(guī)劃問題, 且特別適合解大規(guī)模問題. PROC LP是SAS軟件公司研制的SAS商業(yè)軟件中OR模塊的一個程序。

這個程序是根據(jù)兩階段單純形法研制的,可以用來解線性和整數(shù)規(guī)劃問題并可進行靈敏度分析, 是一個比較完善的程序.用戶可以根據(jù)需要選擇不同的參數(shù)來滿足不同的要求。關于內(nèi)點法的軟件也在研制之中.BPMPD是Cs.Mzos基于原始對偶內(nèi)點法研制的解線性和整數(shù)規(guī)劃的軟件。

此外,在互聯(lián)網(wǎng)上能訪問到的解線性和整數(shù)規(guī)劃問題的軟件還有:EQPS（線性，整數(shù)和非線性規(guī)劃）,FMP（線性和混合整數(shù)規(guī)劃），HS/LPLO（線性規(guī)劃），KORBX（線性規(guī)劃），LAMPS（線性和整數(shù)規(guī)劃），LPBLP（線性規(guī)劃），MILP（混合整數(shù)規(guī)劃），MINTO（混合整數(shù)規(guī)劃）， MPSIII（線性和混合整數(shù)規(guī)劃），OML（線性和混合整數(shù)規(guī)劃）， OSL（線性，二次和混合整數(shù)規(guī)劃），PROCLP（線性和整數(shù)規(guī)劃），WB（線性和混合整數(shù)規(guī)劃），WHIZARD（線性和混合整數(shù)規(guī)劃），XPRESSMP（線性和混合整數(shù)規(guī)劃）等。

2.非線性最優(yōu)化

在實際研究工作和生產(chǎn)實踐中存在大量非線性最優(yōu)化問題, 把它們完全簡化成線性問題來處理是不妥當?shù)?隨著科學技術和計算機的發(fā)展, 這些實際問題具有這樣一些特點.一是問題的變量比較多, 因為問題涉及的因素越來越多; 二是問題的規(guī)模越來越大;三是問題越來越復雜, 問題的非線性程度越來越高. 這類問題通常描述成在一組非線性約束條件下尋求某一非線性目標函數(shù)的最小或最大值。

非線性規(guī)劃的一個重要理論是1951年Kuhn-Tucker最優(yōu)條件(簡稱KT條件)的建立.此后的50年代主要是對梯度法和牛頓法的研究.以Davidon(1959), Fletcher和Powell(1963)提出的DFP方法為起點, 60年代是研究擬牛頓方法活躍時期, 同時對共軛梯度法也有較好的研究. 在1970年由Broyden,Fletcher,Goldfarb 和Shanno從不同的角度共同提出的BFGS方法是目前為止最有效的擬牛頓方法. 由于Broyden, Dennis 和More的工作使得擬牛頓方法的理論變得很完善. 70年代是非線性規(guī)劃飛速發(fā)展時期, 約束變尺度(SQP)方法(Han和Powell為代表)和Lagrange乘子法(代表人物是Powell 和Hestenes)是這一時期主要研究成果.計算機的飛速發(fā)展使非線性規(guī)劃的研究如虎添翼.80年代開始研究信賴域法、稀疏 擬牛頓法、大規(guī)模問題的方法和并行計算, 90年代研究解非線性規(guī)劃問題的內(nèi)點法和有限儲存法. 可以毫不夸張的說, 這半個世紀是最優(yōu)化發(fā)展的黃金時期。

與線性規(guī)劃相比，非線性規(guī)劃軟件還不夠完善. 但是已有大量解非線性規(guī)劃問題的軟件, 其中有相當一部分可從互聯(lián)網(wǎng)上免費下載.BTN是利用線搜索技術的塊截斷牛頓方法解無約束問題的軟件，近似牛頓方向是通過塊共軛梯度法解牛頓方程得到. 塊狀結(jié)構(gòu)比較方便對線性代數(shù)方程和函數(shù)計算進行并行化處理. BTN有兩個版本: 簡本和用戶版本. 簡本不需并行化技術, 而用戶版本允許多種復雜運算，包含并行化處理。

BQPD是Fletcher研制的解二次規(guī)劃的軟件, 所使用的基本方法是零空間積極集法. DONLP2是Spellucci研制的用SQP方法解一般非線性約束問題的軟件，適合解小規(guī)模優(yōu)化問題，HOOKE是解無約束最優(yōu)化問題的一個直接方法的軟件，LANCELOT是由Conn,Gould和Toint研制的解大規(guī)模最優(yōu)化問題的軟件包,適合解無約束最優(yōu)化、非線性最小二乘、邊界約束最優(yōu)化和一般約束最優(yōu)化問題.這個軟件的基本思想是利用增廣Lagrange函數(shù)來處理約束條件, 在每步迭代中解一個邊界約束優(yōu)化子問題, 其所用的方法結(jié)合信賴域和投影梯度等技術。

MINPACK是美國Argonne國家實驗室研制的軟件包，適合求解非線性方程組和非線性最小二乘問題, 所用的基本方法是阻尼最小二乘法, 此軟件可以從網(wǎng)上圖書館獲得. PROC NLP是SAS軟件公司研制的SAS商業(yè)軟件中OR模塊的一個程序，這個程序適合解無約束最優(yōu)化、非線性最小二乘、線性約束最優(yōu)化、二次規(guī)劃和一般約束最優(yōu)化問題.TENMIN是Schnabel等研制的解中小規(guī)模問題的張量方法軟件。在互聯(lián)網(wǎng)上能訪問到的解非線性最優(yōu)化問題的軟件還有:CONOPT（非線性規(guī)劃），DOT（優(yōu)化設計工具箱），Excel and Quattro Pro Solvers（線性，整數(shù)和非線性規(guī)劃），F(xiàn)SQP（非線性規(guī)劃和極小極大問題），GRG2（非線性規(guī)劃)， LBFGS（有限儲存法），LINDO（線性、二次和混合整數(shù)規(guī)劃），LSSOL（最小二乘和二次規(guī)劃），MINOS（線性和非線性規(guī)劃），NLPJOB（非線性多目標規(guī)劃）， OPTPACK（約束和無約束最優(yōu)化）,PETS（解非線性方程組和無約束問題的并行算法），QPOPT（線性和二次規(guī)劃）,SQOPT（大規(guī)模線性和凸二次規(guī)劃），SNOPT（大規(guī)模線性、二次和非線性規(guī)劃），SPRNLP（稀疏最小二乘,稀疏和稠密非線性規(guī)劃），SYSFIT（非線性方程組的參數(shù)估計），TENSOLVE（非線性方程組和最小二乘），VE10(非線性最小二乘)等。

3.最優(yōu)化的應用

最優(yōu)化的應用是非常廣泛的, 下面僅就最優(yōu)化在金融和航空方面的應用作一點介紹。

3.1金融和最優(yōu)化

隨著世界經(jīng)濟的發(fā)展和知識經(jīng)濟的到來, 金融數(shù)學已變成一個熱門研究課題,普遍得到各國政府的重視和支持. 而金融數(shù)學的一個重要方面是與優(yōu)化理論及算法相聯(lián)系的. 諾貝爾經(jīng)濟學獎得主馬爾柯維茨提出證券組合選擇的均值--方差模型(MV模型)便是一個二次規(guī)劃問題. 這個模型使得證券組合選擇方法實現(xiàn)了從定性描述到定量描述質(zhì)的飛躍,使得人們可以科學而準確地分析與選擇投資策略。

3.2 航空和最優(yōu)化

最優(yōu)化在航空方面的應用也很多.從90年代引起國際學術界重視的"氣動數(shù)值優(yōu)化設計"是計算流體力學和優(yōu)化設計技術相結(jié)合來研究飛行器氣動性能及其它流動問題的方法. 這一方法的研究包含了大量的最優(yōu)化算法和應用研究。

在航空航天廣泛應用的結(jié)構(gòu)優(yōu)化設計是最近三十多年來發(fā)展起來的一門新興的現(xiàn)代化科學技術它的發(fā)展是與最優(yōu)化理論和方法的發(fā)展是密不可分的從60年代起, 結(jié)構(gòu)設計問題開始用一般非線性規(guī)劃問題來處理. 此后, 一種新的優(yōu)化理論和方法一出現(xiàn)并被用到結(jié)構(gòu)設計問題上來, 從而推動了結(jié)構(gòu)優(yōu)化設計的快速發(fā)展.目前處于優(yōu)化研究熱點的信賴域法被用于解飛機設計中顫振問題模型, 收到了良好效果。

編輯：fqj