線性和非線性最優(yōu)化理論、方法、軟件及應(yīng)用

最優(yōu)化在航空航天、生命科學(xué)、水利科學(xué)、地球科學(xué)、工程技術(shù)等自然科學(xué)領(lǐng)域和經(jīng)濟(jì)金融等社會(huì)科學(xué)領(lǐng)域有著廣泛和重要的應(yīng)用，它的研究和發(fā)展一直得到廣泛的關(guān)注.最優(yōu)化的研究包含理論、方法和應(yīng)用.最優(yōu)化理論主要研究問(wèn)題解的最優(yōu)性條件、靈敏度分析、解的存在性和一般復(fù)雜性等.而最優(yōu)化方法研究包括構(gòu)造新算法、證明解的收斂性、算法的比較和復(fù)雜性等.最優(yōu)化的應(yīng)用研究則包括算法的實(shí)現(xiàn)、算法的程序、軟件包及商業(yè)化、在實(shí)際問(wèn)題的應(yīng)用.這里簡(jiǎn)介一下線性和非線性最優(yōu)化理論、方法及應(yīng)用研究的發(fā)展?fàn)顩r.1.線性最優(yōu)化線性最優(yōu)化，又稱線性規(guī)劃，是運(yùn)籌學(xué)中應(yīng)用最廣泛的一個(gè)分支.這是因?yàn)樽匀豢茖W(xué)和社會(huì)科學(xué)中許多問(wèn)題都可以近似地化成線性規(guī)劃問(wèn)題.線性規(guī)劃理論和算法的研究及發(fā)展共經(jīng)歷了三個(gè)高潮，每個(gè)高潮都引起了社會(huì)的極大關(guān)注.線性規(guī)劃研究的第一高潮是著名的單純形法的研究.這一方法是Dantzig在1947年提出的，它以成熟的算法理論和完善的算法及軟件統(tǒng)治線性規(guī)劃達(dá)三十多年.隨著60年代發(fā)展起來(lái)的計(jì)算復(fù)雜性理論的研究，單純形法在七十年代末受到了挑戰(zhàn).1979年前蘇聯(lián)數(shù)學(xué)家Khachiyan提出了第一個(gè)理論上優(yōu)于單純形法的所謂多項(xiàng)式時(shí)間算法--橢球法，曾成為轟動(dòng)一時(shí)的新聞，并掀起了研究線性規(guī)劃的第二個(gè)高潮.但遺憾的是廣泛的數(shù)值試驗(yàn)表明，橢球算法的計(jì)算比單純形方法差.1984年Karmarkar提出了求解線性規(guī)劃的另一個(gè)多項(xiàng)式時(shí)間算法.這個(gè)算法從理論和數(shù)值上都優(yōu)于橢球法,因而引起學(xué)術(shù)界的極大關(guān)注，并由此掀起了研究線性規(guī)劃的第三個(gè)高潮.從那以后，許多學(xué)者致力于改進(jìn)和完善這一算法，得到了許多改進(jìn)算法.這些算法運(yùn)用不同的思想方法均獲得通過(guò)可行區(qū)域內(nèi)部的迭代點(diǎn)列，因此統(tǒng)稱為解線性規(guī)劃問(wèn)題的內(nèi)點(diǎn)算法.目前內(nèi)點(diǎn)算法正以不可抗拒的趨勢(shì)將超越和替代單純形法.線性規(guī)劃的軟件，特別是由單純形法所形成的軟件比較成熟和完善.這些軟件不僅可以解一般線性規(guī)劃問(wèn)題，而且可以解整數(shù)線性規(guī)劃問(wèn)題、進(jìn)行靈敏度分析，同時(shí)可以解具有稀疏結(jié)構(gòu)的大規(guī)模問(wèn)題.CPLEX是Bixby基于單純形法研制的解線性和整數(shù)規(guī)劃的軟件，CPLEX的網(wǎng)址是/.此外,這個(gè)軟件也可以用來(lái)解凸二次規(guī)劃問(wèn)題，且特別適合解大規(guī)模問(wèn)題.PROCLP是SAS軟件公司研制的SAS商業(yè)軟件中OR模塊的一個(gè)程序.這個(gè)程序是根據(jù)兩階段單純形法研制的,可以用來(lái)解線性和整數(shù)規(guī)劃問(wèn)題并可進(jìn)行靈敏度分析，是一個(gè)比較完善的程序.用戶可以根據(jù)需要選擇不同的參數(shù)來(lái)滿足不同的要求。關(guān)于內(nèi)點(diǎn)法的軟件也在研制之中.BPMPD是Cs.Mzos基于原始對(duì)偶內(nèi)點(diǎn)法研制的解線性和整數(shù)規(guī)劃的軟件，其FTP地址是ftp://ftp.sztaki.hu/pub/oplab/SOFTWARE/BPMPD/，可以自由下載.此外，在互聯(lián)網(wǎng)上能訪問(wèn)到的解線性和整數(shù)規(guī)劃問(wèn)題的軟件還W:EQPS（線性，整數(shù)和非線性規(guī)劃），F(xiàn)MP（線性和混合整數(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ī)劃）等.在實(shí)際研究工作和生產(chǎn)實(shí)踐中存在大量非線性最優(yōu)化問(wèn)題，把它們完全簡(jiǎn)化成線性問(wèn)題來(lái)處理是不妥當(dāng)?shù)?隨著科學(xué)技術(shù)和計(jì)算機(jī)的發(fā)展，這些實(shí)際問(wèn)題具有這樣一些特點(diǎn).一是問(wèn)題的變量比較多，因?yàn)閱?wèn)題涉及的因素越來(lái)越多；二是問(wèn)題的規(guī)模越來(lái)越大;三是問(wèn)題越來(lái)越復(fù)雜，問(wèn)題的非線性程度越來(lái)越高.這類問(wèn)題通常描述成在一組非線性約束條件下尋求某一非線性目標(biāo)函數(shù)的最小或最大值。非線性規(guī)劃的一個(gè)重要理論是1951年Kuhn-Tucker最優(yōu)條件（簡(jiǎn)稱KT條件）的建立.此后的50年代主要是對(duì)梯度法和牛頓法的研究.以Davidon（1959）,Fletcher和Powell（1963）提出的DFP方法為起點(diǎn)，60年代是研究擬牛頓方法活躍時(shí)期，同時(shí)對(duì)共軛梯度法也有較好的研究.在1970年由Broyden,Fletcher,Goldfarb和Shanno從不同的角度共同提出的BFGS方法是目前為止最有效的擬牛頓方法.由于Broyden,Dennis和More的工作使得擬牛頓方法的理論變得很完善.70年代是非線性規(guī)劃飛速發(fā)展時(shí)期，約束變尺度（SQP）方法（Han和Powell為代表）和Lagrange乘子法（代表人物是Powell和Hestenes）是這一時(shí)期主要研究成果.計(jì)算機(jī)的飛速發(fā)展使非線性規(guī)劃的研究如虎添翼.80年代開(kāi)始研究信賴域法、稀疏擬牛頓法、大規(guī)模問(wèn)題的方法和并行計(jì)算，90年代研究解非線性規(guī)劃問(wèn)題的內(nèi)點(diǎn)法和有限儲(chǔ)存法.可以毫不夸張的說(shuō)，這半個(gè)世紀(jì)是最優(yōu)化發(fā)展的黃金時(shí)期.與線性規(guī)劃相比，非線性規(guī)劃軟件還不夠完善.但是巳有大量解非線性規(guī)劃問(wèn)題的軟件，其中有相當(dāng)一部分可從互聯(lián)網(wǎng)上免費(fèi)下載.BTN是利用線搜索技術(shù)的塊截?cái)嗯ｎD方法解無(wú)約束問(wèn)題的軟件，近似牛頓方向是通過(guò)塊共軛梯度法解牛頓方程得到.塊狀結(jié)構(gòu)比較方便對(duì)線性代數(shù)方程和函數(shù)計(jì)算進(jìn)行并行化處理.BTN有兩個(gè)版本：簡(jiǎn)本和用戶版本.簡(jiǎn)本不需并行化技術(shù)，而用戶版本允許多種復(fù)雜運(yùn)算，包含并行化處理.此軟件可以通過(guò)/opt獲得。BQPD是Fletcher研制的解二次規(guī)劃的軟件，所使用的基本方法是零空間積極集法.DONLP2是Spellucci研制的用SQP方法解一般非線性約束問(wèn)題的軟件，適合解小規(guī)模優(yōu)化問(wèn)題，可以從網(wǎng)址/opt/donlp2/上免費(fèi)下載。HOOKE是解無(wú)約束最優(yōu)化問(wèn)題的一個(gè)直接方法的軟件，可以通過(guò)ftp:///opt/hooke.c獲得。LANCELOT是由Conn,Gould和Toint研制的解大規(guī)模最優(yōu)化問(wèn)題的軟件包,適合解無(wú)約束最優(yōu)化、非線性最小二乘、邊界約束最優(yōu)化和一般約束最優(yōu)化問(wèn)題.這個(gè)軟件的基本思想是利用增廣Lagrange函數(shù)來(lái)處理約束條件，在每步迭代中解一個(gè)邊界約束優(yōu)化子問(wèn)題，其所用的方法結(jié)合信賴域和投影梯度等技術(shù).MINPACK是美國(guó)Argonne國(guó)家實(shí)驗(yàn)室研制的軟件包，適合求解非線性方程組和非線性最小二乘問(wèn)題，所用的基本方法是阻尼最小二乘法，此軟件可以從網(wǎng)上圖書(shū)館獲得.PROCNLP是SAS軟件公司研制的SAS商業(yè)軟件中OR模塊的一個(gè)程序，這個(gè)程序適合解無(wú)約束最優(yōu)化、非線性最小二乘、線性約束最優(yōu)化、二次規(guī)劃和一般約束最優(yōu)化問(wèn)題.TENMIN是Schnabel等研制的解中小規(guī)模問(wèn)題（$n<100$）的張量方法軟件。在互聯(lián)網(wǎng)上能訪問(wèn)到的解非線性最優(yōu)化問(wèn)題的軟件還有:CONOPT（非線性規(guī)劃），DOT（優(yōu)化設(shè)計(jì)工具箱），ExcelandQuattroProSolvers（線性，整數(shù)和非線性規(guī)劃），F(xiàn)SQP（非線性規(guī)劃和極小極大問(wèn)題），GRG2（非線性規(guī)劃），LBFGS（有限儲(chǔ)存法），LINDO（線性、二次和混合整數(shù)規(guī)劃），LSSOL（最小二乘和二次規(guī)劃），MINOS（線性和非線性規(guī)劃），NLPJOB（非線性多目標(biāo)規(guī)劃），OPTPACK（約束和無(wú)約束最優(yōu)化），PETS（解非線性方程組和無(wú)約束問(wèn)題的并行算法），QPOPT（線性和二次規(guī)劃），SQOPT（大規(guī)模線性和凸二次規(guī)劃），SNOPT（大規(guī)模線性、二次和非線性規(guī)劃），SPRNLP（稀疏最小二乘,稀疏和稠密非線性規(guī)劃），SYSFIT（非線性方程組的參數(shù)估計(jì)），TENSOLVE（非線性方程組和最小二乘），VE10（非線性最小二乘）等.最優(yōu)化的應(yīng)用是非常廣泛的，下面僅就最優(yōu)化在金融和航空方面的應(yīng)用作一點(diǎn)介紹.3.1金融和最優(yōu)化隨著世界經(jīng)濟(jì)的發(fā)展和知識(shí)經(jīng)濟(jì)的到來(lái)，金融數(shù)學(xué)巳變成一個(gè)熱門研究課題，普遍得到各國(guó)政府的重視和支持.而金融數(shù)學(xué)的一個(gè)重要方面是與優(yōu)化理論及算法相聯(lián)系的.諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)得主馬爾柯維茨提出證券組合選擇的均值--方差模型（MV模型）便是一個(gè)二次規(guī)劃問(wèn)題.這個(gè)模型使得證券組合選擇方法實(shí)現(xiàn)了從定性描述到定量描述質(zhì)的飛躍，使得人們可以科學(xué)而準(zhǔn)確地分析與選擇投資策略.3.2航空和最優(yōu)化最優(yōu)化在航空方面的應(yīng)用也很多.從90年代引起國(guó)際學(xué)術(shù)界重視的"氣動(dòng)數(shù)值優(yōu)化設(shè)計(jì)"是計(jì)算流體力學(xué)和優(yōu)化設(shè)計(jì)技術(shù)相結(jié)合來(lái)研究飛行器氣動(dòng)性能及其它流動(dòng)問(wèn)題的方法.這一方法的研究包含了大量的最優(yōu)化