求解非線性方程組的信賴域算法

唐江花

(安徽新華學(xué)院 通識(shí)教育部，安徽 合肥 230088)

非線性方程組的求解在金融、貿(mào)易、航空航天、工業(yè)、計(jì)算機(jī)等領(lǐng)域中有廣泛的應(yīng)用，在這些領(lǐng)域中所遇到的非線性規(guī)劃問(wèn)題都可以轉(zhuǎn)化為非線性方程組的求解問(wèn)題.非線性方程組的求解實(shí)際上就是從眾多解中尋找最優(yōu)解，例如研究問(wèn)題解的最優(yōu)條件、解是否存在以及復(fù)雜性等，這種最優(yōu)化理論也叫作“數(shù)學(xué)規(guī)劃”，在實(shí)際生活中是一門應(yīng)用性較強(qiáng)的學(xué)科[1-2].非線性方程組中的最優(yōu)化解法在工作和生產(chǎn)實(shí)踐中應(yīng)用到的頻率很高，實(shí)際的工作中算法結(jié)構(gòu)復(fù)雜，變量眾多，具有規(guī)模大、結(jié)構(gòu)復(fù)雜的特點(diǎn)，如果將其完全轉(zhuǎn)換為線性問(wèn)題，得到的結(jié)果會(huì)遠(yuǎn)遠(yuǎn)脫離實(shí)際情況.因此非線性方程組的求解問(wèn)題也成為人們重視與研究的問(wèn)題，將具有上述特點(diǎn)的問(wèn)題描述成非線性方程函數(shù)，并在一定的非線性約束條件下尋找其最大或最小解，成為了解決該類問(wèn)題的最優(yōu)方法.

但是傳統(tǒng)求解非線性方程組的算法中，雖然最終得到的非線性方程組的解比較準(zhǔn)確，但是求解過(guò)程中迭代次數(shù)過(guò)多，導(dǎo)致運(yùn)算的時(shí)間較長(zhǎng)，因此本文提出一種求解非線性方程組的信賴域算法.信賴域算法是一種重要的優(yōu)化算法，它起源于線性規(guī)劃，最早應(yīng)用在無(wú)約束的優(yōu)化問(wèn)題中，其最大的特點(diǎn)是確定步長(zhǎng)的方法，傳統(tǒng)步長(zhǎng)確定方法一般為線性搜索，但是信賴域算法是通過(guò)求解信賴域的子問(wèn)題，初步得到試探步長(zhǎng)，并根據(jù)實(shí)際的計(jì)算函數(shù)的下降量情況對(duì)試探步長(zhǎng)進(jìn)行判斷[3-4].本文將這種算法應(yīng)用到非線性方程組的求解過(guò)程中，以期能夠簡(jiǎn)化傳統(tǒng)算法求解過(guò)程，提高非線性方程組的求解效率.

1 求解非線性方程組的信賴域算法

1.1 建立信賴域算法模型

對(duì)于非線性方程組：

F(x)=0，

(1)

(2)

信賴域不要求Hessian矩陣在每個(gè)迭代點(diǎn)處均正定，因此，試探步不成功時(shí)，可以加入二階校正步，沿著試探步的方向，利用固定步長(zhǎng)公式產(chǎn)生步長(zhǎng)，因此，當(dāng)試探步長(zhǎng)為lk且在信賴域內(nèi)時(shí)，可設(shè)置當(dāng)前迭代初始點(diǎn)為xk，且在以該點(diǎn)為中心，半徑為λk的閉球鄰域內(nèi)，在步長(zhǎng)迭代過(guò)程中需要有一自然數(shù)ζk且存在‖lk‖<ζk，用評(píng)價(jià)函數(shù)決定lk是否被接受，當(dāng)試探失敗，信賴域的半徑會(huì)縮小，試探成功半徑將視具體情況增大或保持不變，這就是改進(jìn)之后信賴域算法子問(wèn)題中的非單調(diào)技術(shù)[5-6].信賴域算法的模型問(wèn)題為：

(3)

(4)

在求解非線性方程組的過(guò)程中，利用目標(biāo)函數(shù)及其相應(yīng)的導(dǎo)數(shù)函數(shù)信息在Hessian矩陣中構(gòu)造近似序列[7-8]，并對(duì)由該公式生成的目標(biāo)函數(shù)的曲率近似進(jìn)行修正.在保持矩陣序列正性的同時(shí)，也考慮了邊值問(wèn)題的正解存在性，有助于克服詳細(xì)數(shù)值的奇異性.至此，完成了信任域算法模型的建立.

1.2 收斂性分析

在收斂性的討論與分析中，首先進(jìn)行假設(shè)，待研究的函數(shù)F(x)是二階連續(xù)可微，并且和矩陣JacobianJ(x)是連續(xù)的[9-10]，那么存在：

‖J(y)-J(x)‖≤L1‖y-x‖ ‖F(xiàn)(y)-F(x)‖≤L2‖y-x‖，?x,y∈Rn,

(5)

式中，L1與L2為正常數(shù).根據(jù)式(5)可知：

‖F(xiàn)(yk)‖=‖F(xiàn)(xk+dk)‖≤‖F(xiàn)n+dk‖+L1‖dk‖2≤‖F(xiàn)k‖+L2‖dk‖+L1‖dk‖2,

(6)

式中，dk為連續(xù)收斂系數(shù).在上述的情況下，產(chǎn)生的迭代序列存在：

(7)

根據(jù)以上條件，可以得到收斂函數(shù)：

(8)

(9)

(10)

為了證明假設(shè)正確，需要證明：

(11)

(12)

2 仿真實(shí)驗(yàn)

2.1 實(shí)驗(yàn)設(shè)計(jì)

為了驗(yàn)證本文提出的求解非線性方程組的信賴域算法的有效性，需要設(shè)計(jì)實(shí)驗(yàn)，對(duì)算法的性能進(jìn)行測(cè)試.選取以下金融案例作為研究對(duì)象：

某金融投資者想要進(jìn)行長(zhǎng)期投資，因此選擇5支目前業(yè)績(jī)較好的股票型基金A、B、C、D、E進(jìn)行組合投資.在進(jìn)行投資之前，對(duì)選擇的5種股票型基金進(jìn)行市場(chǎng)分析，并得到統(tǒng)計(jì)預(yù)測(cè)的相關(guān)數(shù)據(jù)如表1所示.

表1 5種股票型基金的數(shù)據(jù)統(tǒng)計(jì)預(yù)測(cè)

在實(shí)驗(yàn)過(guò)程中，假設(shè)5種股票型基金的購(gòu)買金額占所有投資中的占比分別為xA、xB、xC、xD、xE，那么交易成本可以表示為：

ci(xi)=0.002xi+0.002(1-e-xi),

(13)

(14)

式中，rp表示投資組合中的預(yù)期收益；Q表示協(xié)方差矩陣；V表示投資風(fēng)險(xiǎn).在計(jì)算機(jī)中，使用軟件Matlab分別對(duì)本文算法和傳統(tǒng)算法進(jìn)行編寫，并設(shè)定算法中相關(guān)參數(shù)的值，令η1的值為0.000 1，η2為0.56，β1為0.27，β2為0.7.在軟件中，可以將上述的相關(guān)問(wèn)題模型帶入具體數(shù)值：

(15)

根據(jù)分析可知，該模型為凸規(guī)劃，因此可以將上式轉(zhuǎn)化為非線性方程組問(wèn)題.并分別使用本文設(shè)計(jì)的信賴域算法和傳統(tǒng)算法進(jìn)行求解.按照上述的實(shí)驗(yàn)方法，選擇相似的非線性案例進(jìn)行求解，并將兩種方法的求解結(jié)果進(jìn)行統(tǒng)計(jì)與分析.

2.2 實(shí)驗(yàn)結(jié)果對(duì)比與分析

分別得到兩種求解算法的計(jì)算結(jié)果，如表2所示.

表2 計(jì)算結(jié)果對(duì)比分析

從表2中可以看出，利用本文設(shè)計(jì)的算法和傳統(tǒng)算法得到的3個(gè)案例的求解結(jié)果基本相似，驗(yàn)證了本文算法的準(zhǔn)確性和可靠性.

為了證明本文算法在求解的過(guò)程中能夠表現(xiàn)出優(yōu)異的性能，對(duì)兩種算法在實(shí)驗(yàn)過(guò)程中得到的相關(guān)參數(shù)進(jìn)行統(tǒng)計(jì)，如表3所示.

表3 計(jì)算過(guò)程參數(shù)對(duì)比分析

從表3可以看出，在相同的測(cè)試環(huán)境下，3個(gè)不同的案例中，本文算法的迭代次數(shù)都是相對(duì)傳統(tǒng)算法更少的，CPU時(shí)間方面也更加省時(shí)，得到的函數(shù)值也更為精準(zhǔn).

3 結(jié) 論

在非線性方程組現(xiàn)有解法的基礎(chǔ)上，對(duì)求解非線性組的信賴域算法進(jìn)行了進(jìn)一步探討.以非線性方程為基礎(chǔ)建立信賴域模型，在其中融入改進(jìn)了的非單調(diào)技術(shù)，在每一次的計(jì)算過(guò)程迭代中，完成信賴域子問(wèn)題的分析與求解，分析了設(shè)計(jì)算法的全局收斂性.并在仿真實(shí)驗(yàn)的3個(gè)案例中，驗(yàn)證了本文算法的可靠性和性能優(yōu)越性.

本文雖然取得了一定的成績(jī)，但是由于水平和時(shí)間的限制，還有很多不足之處，例如，算法的收斂性分析方面，只能在理論上證明算法具有收斂性，且應(yīng)用的是反證法，但是對(duì)于收斂速度無(wú)法進(jìn)行量化計(jì)算，這一問(wèn)題在今后的研究中具有重要的理論意義和應(yīng)用價(jià)值，也是今后對(duì)于非線性方程組求解方法研究的重要方向.