非線性方程組求解器全局優(yōu)化求解能力對(duì)比研究

程培澄 程培聰 王 萌 邵宇辰 亓路寬

1(北京工業(yè)大學(xué)材料科學(xué)與工程學(xué)院 北京 100124) 2(北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 北京100044) 3(北京工業(yè)大學(xué)生命科學(xué)與生物工程學(xué)院 北京 100124) 4(北京工業(yè)大學(xué)建筑工程學(xué)院 北京 100124)

0 引 言

非線性方程組的求解是科學(xué)計(jì)算領(lǐng)域里最基本也是最重要問(wèn)題之一，不論是理工科類還是社會(huì)人文科學(xué)類，很多問(wèn)題都最終歸結(jié)為方程組求解問(wèn)題。方程組求解一般分解析解和數(shù)值解兩種類型，能得到解析解自然是最好的結(jié)果。但現(xiàn)實(shí)中，基于問(wèn)題的復(fù)雜性和目前的技術(shù)，很多時(shí)候非線性方程組都是無(wú)法得到解析解的，此時(shí)只能通過(guò)數(shù)值計(jì)算方法得到數(shù)值解。當(dāng)前非線性方程組數(shù)值計(jì)算最常用的方法有牛頓算法、共軛梯度算法、最速下降法等，這些算法實(shí)際上都是一種優(yōu)化迭代算法，因此方程組數(shù)值求解問(wèn)題也可以視為優(yōu)化求解問(wèn)題，式(1)可以轉(zhuǎn)換成等價(jià)的優(yōu)化問(wèn)題，即求函數(shù)最小值問(wèn)題，式(2)為一標(biāo)準(zhǔn)的無(wú)約束函數(shù)最小值優(yōu)化問(wèn)題。

(1)

(2)

非線性優(yōu)化問(wèn)題所涉及到的優(yōu)化算法一般可分為局部和全局最優(yōu)算法兩種。局部最優(yōu)算法效率高但對(duì)參數(shù)初值依賴嚴(yán)重，迭代起始初值的質(zhì)量好壞決定了計(jì)算是否收斂從而得到正確結(jié)果，而要猜測(cè)給出合理的初值并非易事，基本是運(yùn)氣加經(jīng)驗(yàn)，對(duì)復(fù)雜點(diǎn)的優(yōu)化問(wèn)題很多時(shí)候即使經(jīng)過(guò)多次嘗試，計(jì)算仍然無(wú)法收斂，因此初值依賴癥是局部最優(yōu)算法的最大缺點(diǎn)，前述牛頓算法等均屬局部最優(yōu)算法；相對(duì)局部最優(yōu)算法的則是全局最優(yōu)算法，其最大特點(diǎn)是不依賴于初值，也即無(wú)須再猜測(cè)初值，即可獲得全局最優(yōu)解，典型代表算法有遺傳算法[1]、模擬退火算法[2]及一大批啟發(fā)式仿生智能算法如粒子群算法[3]、蟻群算法[4]等。如果僅從上述概念描述來(lái)看，全局優(yōu)化算法相比局部最優(yōu)算法無(wú)疑有巨大的優(yōu)勢(shì)，但實(shí)際卻并非如此。全局優(yōu)化算法有兩大不足，一是計(jì)算量大，其尋優(yōu)特性決定了計(jì)算資源的高消耗，雖然硬件能力的提升及并行算法等可以進(jìn)行一些彌補(bǔ)；二是任何全局最優(yōu)算法，至少到目前為止也僅是從理論上證明可以不依賴初值而全局收斂，而實(shí)際應(yīng)用當(dāng)中卻與理論相差甚遠(yuǎn)，很難保證每個(gè)優(yōu)化問(wèn)題都百分之百收斂到全局最優(yōu)。

正因?yàn)槿肿顑?yōu)算法在理論層面完美而實(shí)際表現(xiàn)差強(qiáng)人意，存在改進(jìn)完善的巨大空間，因此國(guó)內(nèi)外眾多研究者都投入其中[5]。僅國(guó)內(nèi)看，從同方知網(wǎng)分別以“遺傳算法”全文檢索并含“優(yōu)化”以及“優(yōu)化算法”全文檢索并含“全局”關(guān)鍵字進(jìn)行查詢，如圖1所示。從2008年至2018年這11年間，以遺傳算法或全局優(yōu)化算法為研究?jī)?nèi)容的論文數(shù)每年平均都上萬(wàn)篇，并呈逐年增加的趨勢(shì)。在全局優(yōu)化算法研究中，尤其以啟發(fā)式智能仿生優(yōu)化算法最為熱門，如粒子群算法、蟻群算法、蛙跳算法、蝙蝠算法、布谷鳥(niǎo)算法、根生算法、魚(yú)群算法等，共有數(shù)百種之多，每一種算法的提出者均稱該算法相對(duì)于其他算法取得了更好的全局優(yōu)化結(jié)果，然而這些算法要么沒(méi)有編譯成通用軟件求解器而導(dǎo)致用戶無(wú)法應(yīng)用驗(yàn)證，要么用戶按介紹自己實(shí)現(xiàn)原算法編譯求解，但計(jì)算結(jié)果卻遠(yuǎn)達(dá)不到原作者所宣稱的效果。同時(shí)通過(guò)調(diào)研了解，國(guó)外被眾多用戶廣泛認(rèn)可的著名通用優(yōu)化計(jì)算平臺(tái)如GAMS[6]和AMPL[7]等，其內(nèi)含的數(shù)十種知名優(yōu)化求解器幾乎都沒(méi)有采用上述任何一種智能仿生進(jìn)化優(yōu)化算法，著名的數(shù)值和符號(hào)計(jì)算軟件MATLAB及Mathematical，在其附帶的全局優(yōu)化工具箱中雖然包含有一些基于上述啟發(fā)式仿生進(jìn)化算法如粒子群算法的全局優(yōu)化求解器，但其實(shí)際應(yīng)用效果遠(yuǎn)不如專業(yè)優(yōu)化計(jì)算的GAMS或AMPL平臺(tái)所包含的求解器，尤其是全局優(yōu)化求解器Baron、Antigone、Couenne和Lingo，這4種求解器均已被證明在全局優(yōu)化求解方面處于世界頂級(jí)[8-10]，然而遺憾的是國(guó)內(nèi)卻少有研究涉及對(duì)這些全局優(yōu)化求解器相對(duì)全面的對(duì)比研究，因此本次研究選擇這4款全局優(yōu)化求解器，再外加唯一國(guó)產(chǎn)優(yōu)化數(shù)值計(jì)算軟件1stOpt共5款軟件作為研究的對(duì)比對(duì)象，而數(shù)學(xué)領(lǐng)域應(yīng)用極廣的MATLAB和Mathematical雖然都有現(xiàn)成的非線性方程求解功能，但都是基于局部最優(yōu)算法的，而其附帶的全局優(yōu)化求解功能與選擇的5款專用優(yōu)化軟件相比，不論效果還是易用性方面都有很大的差距，因此不在本次評(píng)價(jià)之列。

Baron求解器是現(xiàn)任美國(guó)卡耐基梅隆大學(xué)教授Sahinidis最先于1996年在伊利諾伊大學(xué)任教時(shí)研發(fā)出的全局優(yōu)化求解器，歷經(jīng)二十余年的持續(xù)改進(jìn)升級(jí)，已被公認(rèn)為當(dāng)今最先進(jìn)強(qiáng)大的全局優(yōu)化求解器[11]。Antigone求解器是美國(guó)普林斯頓大學(xué)Floudas教授和英國(guó)帝國(guó)理工學(xué)院Misener教授共同研發(fā)并于2013年首次發(fā)表的優(yōu)化求解器，專注于連續(xù)及整數(shù)規(guī)劃全局求解，業(yè)界享有極高的聲譽(yù)。Couenne求解器是美國(guó)COIN-OR公司開(kāi)發(fā)的非線性全局最優(yōu)化求解器，起源于2006年IBM與卡耐基梅隆大學(xué)的一個(gè)合作項(xiàng)目，該求解器開(kāi)源，有多種不同編程語(yǔ)言接口，方便使用。Lingo是美國(guó)Lindo公司于1981年開(kāi)發(fā)出的優(yōu)化計(jì)算平臺(tái)，具有自己的模型語(yǔ)言，使用簡(jiǎn)單且用戶廣，世界500強(qiáng)公司中的一半以上都在使用。該軟件國(guó)內(nèi)知名度也很高，幾乎是國(guó)內(nèi)各種數(shù)模競(jìng)賽的缺省推薦軟件。1stOpt是唯一一款國(guó)產(chǎn)通用數(shù)值優(yōu)化計(jì)算軟件，國(guó)內(nèi)各大高校、科研院所及許多公司都在使用，該軟件最大特點(diǎn)就是其特有的UGO全局優(yōu)化算法以及其易用性，短時(shí)間內(nèi)就贏得了眾多用戶的認(rèn)可與推崇[12-13]。

GAMS是通用的優(yōu)化計(jì)算平臺(tái)，上述四款全局優(yōu)化求解器Baron、Antigone、Couenne和LingoGlobal均包含在GAMS優(yōu)化計(jì)算平臺(tái)之中。GAMS提供統(tǒng)一的應(yīng)用界面和語(yǔ)言，底層調(diào)用上述求解器，用戶只需掌握GAMS語(yǔ)言而不需分別了解各個(gè)求解器的特有語(yǔ)言，極大提升易用性。本次采用的GAMS版本是25.1.3，最新試用版可從GAMS官方網(wǎng)站免費(fèi)下載；1stOpt使用的版本是8.0。各求解器都有眾多的選項(xiàng)設(shè)置，不同的設(shè)置對(duì)計(jì)算結(jié)果會(huì)有一定的影響[8]，方便起見(jiàn)本次研究中各求解器均采用適合于大多數(shù)情況的缺省設(shè)置。

1 非線性方程組研究案例

檢驗(yàn)全局優(yōu)化算法或全局優(yōu)化求解器的最佳方法就是采用相應(yīng)的測(cè)試題進(jìn)行實(shí)際計(jì)算比較。國(guó)內(nèi)不少學(xué)者采用典型案例在全局優(yōu)化算法求解非線性方程組方面進(jìn)行了不少有益的探索[14-17]，此外目前世界上已有不少經(jīng)典的全局優(yōu)化測(cè)試題集,如著名的GLOBALLib[18]和MINLPLib[19]。然而采用上述已有經(jīng)典測(cè)試題集存在以下三個(gè)問(wèn)題：1) 這些測(cè)試題集已被眾多相關(guān)研究者進(jìn)行了廣泛和深入的研究對(duì)比，并在此基礎(chǔ)上對(duì)優(yōu)化算法進(jìn)行了針對(duì)性的改進(jìn)，這有可能會(huì)導(dǎo)致這些算法或求解器對(duì)這些測(cè)試題集產(chǎn)生一定的“免疫”功效，由此導(dǎo)致無(wú)法對(duì)各種優(yōu)化求解器進(jìn)行嚴(yán)謹(jǐn)、客觀及公正的測(cè)評(píng)。2) 這些經(jīng)典測(cè)試題集不少都是五年甚至十多年前提出的，在當(dāng)時(shí)確實(shí)具有一定的難度和代表性，是開(kāi)發(fā)檢驗(yàn)優(yōu)化算法的極佳案例，但隨著科技的快速發(fā)展，這些測(cè)試題集中的不少問(wèn)題對(duì)當(dāng)今優(yōu)秀的最優(yōu)化求解器來(lái)說(shuō)已過(guò)于簡(jiǎn)單，獲得正解已是非常輕松簡(jiǎn)單的事，因此也基本失去了其算法測(cè)試、驗(yàn)證與挑戰(zhàn)的功能。3) 相對(duì)于局部?jī)?yōu)化算法，全局最優(yōu)算法主要側(cè)重于效果，一般而言計(jì)算消耗較大，因此維數(shù)低但難度高的問(wèn)題才是測(cè)試驗(yàn)證全局最優(yōu)化算法的最佳選擇，而已有的測(cè)試問(wèn)題要么維數(shù)太高導(dǎo)致計(jì)算時(shí)間太長(zhǎng)，不利于對(duì)問(wèn)題的高效驗(yàn)證，要么難度太低而無(wú)法有效檢驗(yàn)不同優(yōu)化求解器的優(yōu)劣。

基于上述分析，本次研究沒(méi)有選擇已有的測(cè)試題集，而是采用了作者收集整理或?qū)嶋H應(yīng)用所遇到的14道非線性方程組問(wèn)題，均屬首次公開(kāi)發(fā)表。這些問(wèn)題求解規(guī)模都不大，求解參數(shù)在3到6個(gè)之間，屬于低維小規(guī)模優(yōu)化求解問(wèn)題，但求解難度卻非常高，比之絕大部分流行的優(yōu)化測(cè)試題集難度要大很多，但正如前述，規(guī)模小但求解難度大，這正是驗(yàn)證全局最優(yōu)化算法或軟件求解器的最佳案例。這14道測(cè)試題案例分述如下。

案例1:五元非線性方程組。

(3)

式中：n=5，a=[80.003 1,202.536 7,251.145 5,340.013 0,352.013 6]，b=[0.55,1.45,1.55,2.75,3.15]。

案例2：四元非線性方程組。

i=1,2,…,n

(4)

式中：n=4，a=[283.15,298.15,313.15,328.15]，b=[0.208 7,0.205 9,0.203 4,0.200 8]。

案例3：五元非線性方程組。

x1exp(-x2(ai-x3)2)+x1exp(-x4(ai-x5)2)-

bi=0i=1,2,…,n

(5)

式中：n=5，a=[50.86,25.17,8.53,4.39,3.15]，b=[48.24,96.53,274.65,508.44,683.08]。

案例4：六元非線性方程組。

(6)

式中：n=6，a=[9,18,36,54,72,108]，b=[1,0.89,0.84,0.78,0.6,0.39]。

案例5：三元非線性方程組。

(7)

式中：n=3，a=[1 990,2 002,2 005]，b=[0.22,0.31,0.33]。

案例6：五元非線性方程組。

(8)

案例7：三元非線性方程組。

(9)

案例8：五元非線性方程組。

(10)

式中：c=1.300 5。

案例9：四元非線性方程組。

(11)

式中：n=4，a=[915,909,898,895]，b=[1 200,1 212,1 234,1 240]，c=[1.6,3.54,5.43,5.683]。

案例10：六元非線性方程組。

(12)

案例11：三元非線性方程組。

(13)

案例12：六元非線性方程組。

(14)

案例13：三元非線性方程組。

(15)

式中：b0=0.029 2,b1=6.17,b2=7.86,u=5 028。

案例14：四元非線性方程組。

ai=x1(1-exp(x2bi))+x3(exp(x4ci)-1)

i=1,2,…,n

(16)

式中：n=4，a=[3.8,27.9,23.5,13.7]，b=[8.2,63,59.5,35.7]，c=[8.1,35.667,59.5,35.7]。

2 優(yōu)化求解器測(cè)試對(duì)比

2.1 測(cè)試環(huán)境及設(shè)定

所有非線性方程求解案例問(wèn)題均轉(zhuǎn)換成如式(2)的最小值優(yōu)化問(wèn)題。Baron、Antigone、Couenne和Lingo Global四個(gè)求解器均在GAMS平臺(tái)執(zhí)行，除了求解器選擇不同，其他代碼均相同；1stOpt采用其獨(dú)立的桌面平臺(tái)實(shí)現(xiàn)。每個(gè)求解器均采用缺省設(shè)置，系統(tǒng)運(yùn)行環(huán)境及硬件配置相同；對(duì)每個(gè)測(cè)試題都獨(dú)立運(yùn)行10次；對(duì)不同的求解器結(jié)果評(píng)估時(shí)，如果具體參數(shù)值基本一樣而目標(biāo)函數(shù)值雖都趨近于0，但比值相差較大，仍視為結(jié)果相同，如案例4中Couenne與1stOpt，二者目標(biāo)函數(shù)值分別為5.12495E-7和7.482169E-14，比值相差巨大但都趨近于0，而且參數(shù)組具體值基本一樣，因此視為相同結(jié)果。

測(cè)試指標(biāo)主要有兩個(gè)：一是目標(biāo)函數(shù)值，對(duì)解方程問(wèn)題而言，獲得正解時(shí)的目標(biāo)函數(shù)值理論上應(yīng)該為0，實(shí)際數(shù)值計(jì)算中一般為趨近于0；二是計(jì)算時(shí)間。這兩個(gè)指標(biāo)也分別代表效果和效率，是判斷一個(gè)優(yōu)化求解器好壞的兩個(gè)最重要指標(biāo)。

2.2 測(cè)試結(jié)果

對(duì)于優(yōu)化計(jì)算而言，非線性方程組的目標(biāo)函數(shù)是非常復(fù)雜和高度非線性的，圖2和圖3是典型的兩個(gè)示意圖。圖2展示最優(yōu)點(diǎn)位于整體梯度平緩的“深井”之中，而圖3則是在“起伏山坡的密林”之中搜索最低點(diǎn)，全局求解難度非常大。詳細(xì)計(jì)算結(jié)果見(jiàn)表1及表2。

表1 案例1-案例7測(cè)試結(jié)果

續(xù)表1

表2 案例8-案例14測(cè)試結(jié)果

續(xù)表2

案例1，它是一個(gè)方程形式完全一樣的四元四次方程組，1stOpt能以超過(guò)90%的概率得到最優(yōu)解，且用時(shí)短；其他求解器均只能獲得局部最優(yōu)解，同時(shí)計(jì)算時(shí)間很長(zhǎng)。

案例2，雖然從目標(biāo)函數(shù)值看五種求解器的結(jié)果均趨近于零，但只有1stOpt結(jié)果精度最高且穩(wěn)定，其余四種求解器所得參數(shù)結(jié)果千差萬(wàn)別。

案例3，Antigone和1stOpt均取得了相同的正解，Antigone用時(shí)較長(zhǎng)，是1stOpt的7倍之多，其他三個(gè)求解器的結(jié)果與目標(biāo)函數(shù)值為0的理論正解相比，誤差巨大。

案例4，求解難度較大，1stOpt能以約50%的概率求得正解，Baron、Antigone和Lingo結(jié)果與正解相差甚遠(yuǎn)，反而是開(kāi)源的Couenne表現(xiàn)最為出色，幾乎能以百分之百概率得到正解，令人驚嘆。

案例5，雖然只有三個(gè)未知參數(shù)，但想得到最優(yōu)解卻十分不易。Baron很快能得出結(jié)果，但卻是錯(cuò)誤的；Antigone和Couenne計(jì)算時(shí)間很長(zhǎng)但最終結(jié)果也不對(duì)；1stOpt能以40%的概率得到最優(yōu)解；Lingo結(jié)果從目標(biāo)函數(shù)值看相對(duì)Baron、Antigone和Couenne好一些，但具體參數(shù)值與1stOpt的相比，明顯也只是一個(gè)局部最優(yōu)解。

案例6，Antigone和1stOpt都可以很快得出正確結(jié)果，二者目標(biāo)函數(shù)值雖然有較大差距，但應(yīng)該是參數(shù)取值精度引起的。Lingo目標(biāo)函數(shù)值雖然也較小，但具體參數(shù)值與最優(yōu)解相比完全不對(duì)；Baron和Couenne耗時(shí)長(zhǎng)但計(jì)算結(jié)果也不對(duì)，僅是局部最優(yōu)解。

案例7，雖然只有三個(gè)未知參數(shù)，所有5個(gè)求解器，不論計(jì)算時(shí)間長(zhǎng)短，所得結(jié)果基本一致，但可判斷都不是目標(biāo)函數(shù)趨近于0的正解，難道該方程本身就無(wú)解？

案例8，Lingo和1stOpt都可求出正解，但前者耗時(shí)較長(zhǎng)；Antigone、Baron和Couenne所得結(jié)果誤差很大。

案例9，1stOpt結(jié)果最好且穩(wěn)定唯一，其余求解器雖然目標(biāo)函數(shù)都趨近于0，但具體參數(shù)值差別巨大，應(yīng)該均為局部最優(yōu)解。

案例10，所有求解器的結(jié)果都差強(qiáng)人意，從目標(biāo)函數(shù)值看Baron結(jié)果最好，1stOpt的結(jié)果次之，但有的參數(shù)值達(dá)到了1E+305的數(shù)量級(jí)，令人困惑；其他三個(gè)求解器結(jié)果均與理想值0相差甚遠(yuǎn)。難道該方程組也無(wú)精確解？

案例11，Baron、Lingo和1stOpt均可獲得正解，Antigone和Couenne結(jié)果僅為局部最優(yōu)且與正解相差甚遠(yuǎn)。

案例12，方程組從形式上看非常簡(jiǎn)單，但實(shí)際求解計(jì)算，Antigone無(wú)法給出結(jié)果，其余四款求解器所得結(jié)果也均非正解，難道該方程組本身同樣無(wú)解？

案例13，1stOpt僅能以大約10%的概率得到正解(有兩組解，另一組x=[0.149 818 6,-0.329 753 6,-4 626.947 171 4])，其余求解器均無(wú)法獲得正解，雖然Couenne的目標(biāo)函數(shù)值趨近于0。如何提高正解獲得率？

案例14源自于美國(guó)Matlab官方論壇一個(gè)問(wèn)題，該論壇里的解答是該方程組無(wú)實(shí)數(shù)解，從Baron、Antigone、Couenne和Lingo所得結(jié)果看的確是無(wú)精確解，但1stOpt的結(jié)果顯示解是存在的。

2.3 求解器評(píng)估

基于前述計(jì)算結(jié)果，從效果(目標(biāo)函數(shù)值)與效率(計(jì)算時(shí)間)兩方面可對(duì)五種求解器的總體優(yōu)劣進(jìn)行綜合量化評(píng)估，具體是每個(gè)案例如果有解，則目標(biāo)函數(shù)值和計(jì)算時(shí)間按從小到大，對(duì)應(yīng)評(píng)分按5到1賦分；如果無(wú)解則得分均按0計(jì)。五種求解器的賦分表及最終得分見(jiàn)表3。綜合得分越高表明該求解器綜合能力越強(qiáng)。

一共14道測(cè)試題，滿分最高分是140分，由上面賦分表可看出，綜合得分最高的是1stOpt，其后依次為Antigone、Baron、Couenne和Lingo。五種求解器求解效果、求解效率及綜合求解能力示意圖分別見(jiàn)圖4、圖5及圖6。

表3 求解器綜合賦分表

2.4 方程簡(jiǎn)化與除法陷阱問(wèn)題

(17)

A=BC

(18)

(19)

60x=2 664(x-0.85)

(20)

(21)

(22)

通過(guò)上述案例可以看出，導(dǎo)致理論上正確但實(shí)際錯(cuò)誤的“罪魁禍?zhǔn)住本褪恰俺ā保瑢?duì)比式(17)、式(19)和式(21)以及等效轉(zhuǎn)換后的式(18)、式(20)和式(22)，前者均含有未知數(shù)在分母的除法，后者經(jīng)過(guò)等效乘法轉(zhuǎn)換后消去了除法項(xiàng)。

再看前面測(cè)試案例7、10、12和13。其中案例7、10和12的式(9)、式(12)和式(14)，通過(guò)等式乘除法變換，去掉方程中含有待求參數(shù)的分母項(xiàng)，修改后等價(jià)方程分別如式(23)、式(24)和式(25)所示。

(23)

(24)

(25)

表4 案例7、10、12、13形式變換后測(cè)試結(jié)果

上述方程五種求解器計(jì)算結(jié)果如表4所示。案例7的方程進(jìn)行形式變換成式(23)形式后，Antigone和1stOpt可分別以100%和50%的概率得到正解；Couenne所得具體參數(shù)值與正解近似，但目標(biāo)函數(shù)值相差巨大；Baron和Lingo維持原狀，相比方程形式變換前沒(méi)有任何改進(jìn)。該方程組的特點(diǎn)就是其中一個(gè)參數(shù)值x3的數(shù)值非常小，達(dá)到1E-25的量級(jí)，但又不能等于0。

案例10方程形式變換后，1stOpt能以幾乎100%概率獲得正解，Baron和Antigone的結(jié)果也可視為正解雖然精度稍差；Couenne和Lingo結(jié)果仍然不對(duì)。此方程組最大的特點(diǎn)就是，不論哪個(gè)求解器，計(jì)算出的參數(shù)x4均等于-1.47，而在變換前的方程組中有分母項(xiàng)x4+1.47，因此會(huì)導(dǎo)致被0除的邏輯錯(cuò)誤，從而導(dǎo)致無(wú)法得到正確結(jié)果。

案例12方程形式變換后全部五種求解器均可快速得到正解(該方程組是多解)。

案例13原方程組中不存在除法項(xiàng)，但仔細(xì)觀察可發(fā)現(xiàn)方程中有“冗余”項(xiàng)，比如方程組中第二個(gè)方程可以通過(guò)等式兩邊同除以x1x2，同樣第三個(gè)方程等式兩邊同除x3，簡(jiǎn)化后方程如下：

(26)

上述方程組1stOpt和Antigone求得正解的成功率分別從去除“冗余”項(xiàng)前的20%和0%提升至100%，其余3個(gè)求解器仍然無(wú)法獲得正解。

通過(guò)上述四個(gè)實(shí)際案例可看出，方程組中如果存在除法項(xiàng)且除法項(xiàng)分母含有待求解未知參數(shù)時(shí)，應(yīng)盡可能通過(guò)等效乘法變換去掉除法項(xiàng)，從而避免除法可能引起的“陷阱”；此外如果公式中存在“冗余”項(xiàng)也盡量將其消除簡(jiǎn)化。通過(guò)這樣的變換，方程組正解求解率可大幅提高。

2.5 確定性算法與隨機(jī)算法

Baron、Antigone、Couenne和Lingo均采用基于分支定界的確定性優(yōu)化算法(Deterministic Global Optimization Algorithms)。采用確定性優(yōu)化算法的求解器的特點(diǎn)之一就是每次計(jì)算都能得到穩(wěn)定相同的結(jié)果，同時(shí)號(hào)稱在一般情況下均能保證輸出結(jié)果為全局最優(yōu)，但在本文實(shí)際應(yīng)用測(cè)試中卻遠(yuǎn)遠(yuǎn)達(dá)不到所稱結(jié)果為全局最優(yōu)的水準(zhǔn)；1stOpt采用自行研發(fā)的全局通用優(yōu)化算法(Universal Global Optimization-UGO)，大部分情況都能得到比前述四個(gè)求解器更好的結(jié)果，雖然不清楚UGO算法的具體實(shí)現(xiàn)方法，但從實(shí)際計(jì)算看，該算法明顯不同于確定性算法，而是含有“隨機(jī)”因子，其具體表現(xiàn)為：雖然對(duì)大多數(shù)問(wèn)題都能計(jì)算獲得穩(wěn)定最優(yōu)結(jié)果，但對(duì)少部分非常復(fù)雜或多解的問(wèn)題，每次計(jì)算結(jié)果有可能不同或得到不同的解。

3 結(jié) 語(yǔ)

論文中首次提出的14道非線性方程組測(cè)試題集，具有規(guī)模小但非線性程度高及求解難度大的特點(diǎn)，非常適合用于檢驗(yàn)測(cè)試和評(píng)估全局優(yōu)化算法及相關(guān)求解器的計(jì)算效果和效率。

科學(xué)數(shù)值計(jì)算軟件傳統(tǒng)上基本是歐美產(chǎn)品占絕對(duì)統(tǒng)治壟斷地位，但本次測(cè)試對(duì)比研究結(jié)果表明，至少在非線性全局優(yōu)化求解領(lǐng)域，五款優(yōu)化求解器中，測(cè)試綜合排名由高到低依次為1stOpt、Antigone、Baron、Couenne和Lingo。開(kāi)源免費(fèi)的Couenne并非最差，反而是非常人氣的商業(yè)求解器Lingo排名最后，而整體綜合表現(xiàn)最好的是國(guó)產(chǎn)的1stOpt，不論是效果還是效率，均綜合排名第一。

對(duì)比研究的五款求解器，除1stOpt為唯一的國(guó)產(chǎn)外，其余四款均來(lái)自美國(guó)，而令人驚訝的是這四款軟件中的三款又都與卡耐基梅隆大學(xué)有關(guān)，Baron的創(chuàng)始人是現(xiàn)任卡耐基梅隆大學(xué)的Sahinidis教授，Antigone求解器的兩位主要?jiǎng)?chuàng)始人之一的普林斯頓大學(xué)Floudas教授其博士學(xué)位于1986年在卡耐基梅隆大學(xué)獲得，開(kāi)源的Couenne求解器起源于2006年IBM與卡耐基梅隆大學(xué)的一個(gè)合作項(xiàng)目。卡耐基梅隆大學(xué)的計(jì)算機(jī)學(xué)科常年排行美國(guó)第一，僅通過(guò)本次研究的求解器也可窺一斑。

Baron的開(kāi)發(fā)者Sahinidis教授和Antigone的開(kāi)發(fā)者Floudas教授，他們本身的專業(yè)都是化學(xué)工程而非計(jì)算機(jī)或應(yīng)用數(shù)學(xué)類，Lingo所屬公司的CEO專業(yè)是環(huán)境工程，1stOpt的主要開(kāi)發(fā)者據(jù)了解是土木工程，優(yōu)秀的數(shù)學(xué)類計(jì)算軟件卻都是由非計(jì)算機(jī)和非數(shù)學(xué)專業(yè)的“行業(yè)外”人士開(kāi)發(fā)或掌控，這一“跨行業(yè)”現(xiàn)象非常值得思考。

除了算法和求解器外，非線性方程組全局優(yōu)化求解過(guò)程中一定要注意盡量避免“除法陷阱”這一問(wèn)題，同時(shí)方程形式能簡(jiǎn)化的一定要先簡(jiǎn)化，只有這樣才能確保大概率獲得最優(yōu)正解。此外，鑒于非線性全局優(yōu)化問(wèn)題的多樣性和復(fù)雜性，測(cè)試所得五款求解器的綜合求解能力僅僅基于本文的案例題集，期待將來(lái)更多研究者基于更多案例問(wèn)題的測(cè)試結(jié)果。

最后還有兩點(diǎn)需要說(shuō)明，一是本次研究?jī)H探討了低維無(wú)約束非線性方程組全局優(yōu)化求解問(wèn)題，更高維數(shù)且含有約束條件的情況有待下一步實(shí)施進(jìn)行；二是五款求解器均使用缺省設(shè)置，對(duì)于基于GAMS平臺(tái)的四款求解器，參數(shù)求解的起始初值均為0，有可能導(dǎo)致被0除的錯(cuò)誤現(xiàn)象發(fā)生，應(yīng)特別注意。