基于非線性方程組的非單調(diào)信賴域算法研究*

唐江花

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

引言

隨著金融、貿(mào)易、計(jì)算機(jī)等方面的發(fā)展，越來(lái)越多的非線性規(guī)劃問(wèn)題開始出現(xiàn)[1].針對(duì)這些最優(yōu)化問(wèn)題進(jìn)行求解，成為數(shù)值求解方法的重要研究方向.信賴域算法的設(shè)計(jì)是以線性規(guī)劃為基礎(chǔ)，其核心在于探索試探步長(zhǎng)，通過(guò)多次計(jì)算求解每個(gè)信賴域子問(wèn)題，獲取初始試探步長(zhǎng)，再分析函數(shù)下降量趨勢(shì)，判斷試探步長(zhǎng)的合理性[2].非單調(diào)信賴域方法因具有較強(qiáng)的收斂性，受到很多研究人員的關(guān)注，多種類型的信賴域方法開始得以應(yīng)用.

文獻(xiàn)[3]針對(duì)不等式約束優(yōu)化問(wèn)題進(jìn)行研究，引入指數(shù)型增廣Lagrange函數(shù)計(jì)算理念，將最初的優(yōu)化求解問(wèn)題，轉(zhuǎn)換為信賴域子問(wèn)題，形成一個(gè)可以應(yīng)用于問(wèn)題求解的信賴域算法.但是，該算法計(jì)算復(fù)雜度較高.文獻(xiàn)[4]以加強(qiáng)最優(yōu)化求解準(zhǔn)確度為目標(biāo)，提出融合了多維濾子算法的信賴域算法.分別計(jì)算目標(biāo)函數(shù)分量，以及函數(shù)投影梯度的分量信息，提取可以判斷信賴域半徑合理性的過(guò)濾點(diǎn).同時(shí)，需要驗(yàn)證提取出的多維濾子可以接受試探點(diǎn)，確保整體收斂性達(dá)到要求.但是，該算法的計(jì)算時(shí)間較長(zhǎng).文獻(xiàn)[5]設(shè)計(jì)了一種一類序列、二次規(guī)劃同時(shí)存在的信賴域算法，且該算法具有不相容性特點(diǎn).參考傳統(tǒng)算法設(shè)置參數(shù)變量，并更新目標(biāo)函數(shù)相關(guān)的參數(shù).應(yīng)用多維濾子算法，選擇最優(yōu)迭代步作為試探步長(zhǎng).最后，利用二階校正策略，校正算法運(yùn)行過(guò)程中存在的maratos效應(yīng).但是，該算法運(yùn)算迭代次數(shù)較多.

為了解決上述提出非單調(diào)信賴域算法的缺點(diǎn)，文中設(shè)計(jì)的算法以非線性方程組為基礎(chǔ).將具有非線性規(guī)劃特點(diǎn)的規(guī)劃問(wèn)題，轉(zhuǎn)化為非線性方程組.通過(guò)非線性約束環(huán)境下，最大或最小值的提取，搜索到最優(yōu)目標(biāo)函數(shù)值.同時(shí)，運(yùn)用Hessian矩陣和雙割線折線算法，對(duì)現(xiàn)有的試探步長(zhǎng)求解過(guò)程進(jìn)行簡(jiǎn)化，保證算法求解結(jié)果準(zhǔn)確性的同時(shí)，減少迭代次數(shù).

1 基于非線性方程組的非單調(diào)信賴域算法設(shè)計(jì)

1.1 非線性方程組問(wèn)題轉(zhuǎn)換

約束優(yōu)化問(wèn)題的求解關(guān)鍵環(huán)節(jié)之一，就是非線性方程組的求解.文中提出的非單調(diào)信賴域算法，將非線性方程組問(wèn)題轉(zhuǎn)換的研究[6]，作為核心研究問(wèn)題.依托于非單調(diào)技術(shù)和信賴域計(jì)算理念，完成非線性方程組，與非線性優(yōu)化之間的互相轉(zhuǎn)換，降低后續(xù)信賴域算法的運(yùn)算復(fù)雜度.

將最初非線性方程組表示為：

F(x)=0,
x∈R

(1)

公式中，x表示變量，F(xiàn)(x)表示函數(shù)，R表示連續(xù)可微的實(shí)值函數(shù).其中：

F(x)=(f1(x),f2(x),…,fm(x))

(2)

公式中，f(x)表示子函數(shù)，m表示非線性方程組中包含的子函數(shù)數(shù)量.再結(jié)合向量空間范數(shù)，可以將原始方程組表示為：

(3)

公式中，min表示最小值，e表示向量空間，‖·‖e表示向量空間范數(shù).

當(dāng)向量空間取值為2時(shí)，可以將非線性方程組求解問(wèn)題，看作最小二乘問(wèn)題，選取最優(yōu)方法進(jìn)行后續(xù)求解.但是，當(dāng)向量空間取值范圍為正無(wú)窮狀態(tài)時(shí)，可以將最初的問(wèn)題看作求解優(yōu)化問(wèn)題[7].這種情況下，函數(shù)具有不可微特性，造成數(shù)值計(jì)算難度較大.針對(duì)該問(wèn)題，文中提出在非線性方程組問(wèn)題轉(zhuǎn)換過(guò)程中，融入極大熵函數(shù)，有效控制參數(shù)值.文中所應(yīng)用的極大熵函數(shù)為凝聚函數(shù)，根據(jù)原始函數(shù)的指數(shù)函數(shù)，并獲取范數(shù)的自然對(duì)數(shù).其中，指數(shù)計(jì)算過(guò)程中，需要保證向量為正分量，對(duì)數(shù)的計(jì)算，是為了保證函數(shù)值恢復(fù)成最初模樣.

考慮到向量空間取值無(wú)窮大條件下，非線性方程組的函數(shù)空間擬合值與參數(shù)值之間具有反比例關(guān)系.因此，非單調(diào)信賴域運(yùn)算過(guò)程中，需要確保向量空間取值夠大，并應(yīng)用可微函數(shù)替換方程組中部分參數(shù)，將非線性方程組轉(zhuǎn)換為易于求解的無(wú)約束優(yōu)化問(wèn)題，作為最優(yōu)化求解的基礎(chǔ).

1.2 設(shè)計(jì)非單調(diào)信賴域模型

非單調(diào)信賴域算法設(shè)計(jì)過(guò)程中，融合Hessian矩陣，實(shí)現(xiàn)試探步長(zhǎng)計(jì)算復(fù)雜度降低.信賴域方法的運(yùn)行，對(duì)于Hessian矩陣在每個(gè)迭代點(diǎn)的正定與否，沒(méi)有強(qiáng)制要求.對(duì)于不合理的試探步長(zhǎng)，可以采用二階校正的方式進(jìn)行更新，得到優(yōu)化后的試探步長(zhǎng).同時(shí)，以將信賴域內(nèi)第一個(gè)迭代點(diǎn)為核心[8]，形成一個(gè)閉球鄰域.再添加一個(gè)自然數(shù)，判斷信賴域半徑是否成功.

實(shí)際操作過(guò)程中，信賴域子問(wèn)題的求解是計(jì)算初始試探步長(zhǎng)的基礎(chǔ)，文中將信賴域算法數(shù)學(xué)模型表示為：

(4)

公式中，w表示二次模型，P表示目標(biāo)函數(shù)，jP表示迭代點(diǎn)上對(duì)目標(biāo)函數(shù)的恰當(dāng)模擬，j表示目標(biāo)函數(shù)梯度，?表示Hessian陣.式中：

(5)

運(yùn)用公式(5)所示的Hessian陣，以近似序列的形式將目標(biāo)函數(shù)與導(dǎo)數(shù)函數(shù)信息表現(xiàn)出來(lái).

依托于非線性方程組進(jìn)行子問(wèn)題求解，需要對(duì)目標(biāo)函數(shù)曲率進(jìn)行修正[9]，得到最優(yōu)解.根據(jù)近似序列構(gòu)建近似矩陣，完成矩陣正定處理后，提取出最優(yōu)曲線，從初始點(diǎn)延伸出一條平行于牛頓方向的切線，形成雙割線，如圖1所示.運(yùn)用雙割線法快速計(jì)算出信賴域子問(wèn)題的最優(yōu)解.

圖1 雙割線折線圖示

根據(jù)圖1所示的雙割線折線算法，對(duì)子問(wèn)題求解模式進(jìn)行改進(jìn)，其核心思想是運(yùn)用低階歐拉方法求解出以最優(yōu)曲線為基礎(chǔ)構(gòu)建的微分方程模型[10].通過(guò)正常、平均和隱式歐拉折線，取代最優(yōu)曲線求解子問(wèn)題的模式，保證近似矩陣正定的基礎(chǔ)上，克服詳細(xì)數(shù)值的奇異性，簡(jiǎn)單而快速地完成信賴域子問(wèn)題的求解，得到試探步長(zhǎng).

1.3 建立多維過(guò)濾集

根據(jù)融合Hessian矩陣和雙割線折線算法的非單調(diào)信賴域模型，求解出試探步長(zhǎng)，作為最優(yōu)解計(jì)算的基礎(chǔ).為了保證簡(jiǎn)化計(jì)算結(jié)果不會(huì)影響最優(yōu)化求解的準(zhǔn)確性，文中依托于包含插值自由度信息的錐模型建立多維過(guò)濾集，進(jìn)一步判斷試探步長(zhǎng)的可行性.針對(duì)當(dāng)前迭代點(diǎn)設(shè)計(jì)一個(gè)試探步長(zhǎng)，可將二者的關(guān)系表示為：

ak+1=ak+φ

(6)

公式中，k表示迭代次數(shù)，a表示迭代點(diǎn)，φ表示試探步長(zhǎng).為了便于非線性方程組求解效率的提升，將信賴域子問(wèn)題表示為：

(7)

公式中，β表示信賴域子問(wèn)題，v表示水平向量，B表示子函數(shù)在迭代點(diǎn)的Hesse近似，也稱為實(shí)對(duì)稱矩陣.

由于水平向量條件并非一項(xiàng)苛刻要求，正常情況下該條件可以被滿足，可以直接運(yùn)用計(jì)算出的試探步長(zhǎng)，求解非線性方程組，對(duì)比方程組求解結(jié)果與理論分析值，判斷上述計(jì)算出的試探步長(zhǎng)的有效性.另外一種情況，就是信賴域子問(wèn)題求解過(guò)程中，水平向量條件沒(méi)有得到滿足，無(wú)法直接判定試探步長(zhǎng).為此，文中提出將信賴域子問(wèn)題求解結(jié)果劃分為三種狀態(tài)，針對(duì)不同的情形，設(shè)置相對(duì)應(yīng)的最優(yōu)性條件.綜上所述，將子問(wèn)題處理模式設(shè)置為：

(8)

(9)

公式中，α、δ表示兩個(gè)變量，λ表示試探點(diǎn)，g表示過(guò)濾點(diǎn).

針對(duì)試探點(diǎn)進(jìn)行迭代更新后，結(jié)合信賴域子問(wèn)題求解結(jié)果，建立多維過(guò)濾集，判斷求解出的試探步長(zhǎng)是否合理.針對(duì)滿足要求的試探點(diǎn)，運(yùn)用“占優(yōu)”準(zhǔn)則，選取出最優(yōu)過(guò)濾點(diǎn)，生成多維過(guò)濾集：

U=(gk,1,gk,2,gk,3,…,gk,N)

(10)

公式中，U表示多維過(guò)濾集，N表示過(guò)濾點(diǎn)分量.當(dāng)某一個(gè)試探點(diǎn)不存在迭代點(diǎn)占優(yōu)情況，可以直接將該點(diǎn)添加到過(guò)濾集中.反之，則需要采用封套策略，分析函數(shù)下降量趨勢(shì),進(jìn)行過(guò)濾點(diǎn)選取，封套策略的具體表達(dá)公式為：

|gk,n|≤|gk+1,n|-?‖gk+1‖

(11)

公式中，?表示封套系數(shù).將滿足公式(11)的試探點(diǎn)，添加到過(guò)濾集中，反之則將其擋在過(guò)濾集之外.最后，采用Nowton校正策略對(duì)實(shí)對(duì)稱矩陣進(jìn)行校正，Nowton校正模型如圖2所示.

運(yùn)用圖2所示的Nowton校正模型，對(duì)實(shí)對(duì)稱矩陣進(jìn)行校正，將子函數(shù)在迭代點(diǎn)的Hesse近似值替換為實(shí)際值.通過(guò)上述計(jì)算完成多維過(guò)濾集的整體建立，運(yùn)用過(guò)濾集對(duì)初步求解出的試探步長(zhǎng)進(jìn)行處理，采用符合要求的試探步長(zhǎng)進(jìn)行非線性方程組的求解.

圖2 Nowton校正模型

1.4 完成信賴域算法設(shè)計(jì)

非單調(diào)信賴域算法研究的最后一步，就是驗(yàn)證所提出算法的全局收斂性，文中考慮無(wú)約束優(yōu)化特點(diǎn)，假設(shè)非線性方程組具有連續(xù)可微特點(diǎn)，則以此為基礎(chǔ)建立的Jacobian矩陣同樣具有連續(xù)性，可得到：

(12)

公式中，η表示因變量，ε表示自變量，τ1、τ2表示正常數(shù).根據(jù)公式(12)可以得出：

‖F(xiàn)(ε)‖=‖F(xiàn)(η+r)‖≤‖F(xiàn)+r‖+τ1‖r‖2
≤‖F(xiàn)‖+τ2‖r‖+τ1‖r‖2

(13)

公式中，r表示連續(xù)收斂系數(shù).通過(guò)上述計(jì)算，得到具有連續(xù)性的迭代序列，生成如下所示收斂函數(shù)：

‖F(xiàn)(ε)-F(η)-?(ε)(η-ε)‖≤τ1‖η-ε‖

(14)

根據(jù)非線性方程組的變量信息，應(yīng)用反證法驗(yàn)證非單調(diào)信賴域算法的全局收斂性.考慮到算法運(yùn)行時(shí)存在兩種狀態(tài)，其一是有限迭代次數(shù)情況，其二是無(wú)限迭代次數(shù)情況.前者可以根據(jù)計(jì)算結(jié)果進(jìn)行直接判斷，文中主要針對(duì)后者進(jìn)行分析，結(jié)合迭代次數(shù)值的屬性特點(diǎn)，提出極限條件下第一階段和第二階段函數(shù)收斂性驗(yàn)證結(jié)果為：

(15)

公式中，part1表示第一階段，part2表示第二階段，lim表示極限符號(hào)，∞表示正無(wú)窮.

根據(jù)公式(15)可知，第一階段和第二階段全局收斂已經(jīng)達(dá)到0，而信賴域算法的收斂性驗(yàn)證結(jié)果主要取決于第三階段收斂驗(yàn)證結(jié)果.當(dāng)?shù)谌A段收斂為0，表明該算法的全局收斂性最強(qiáng)，同樣，計(jì)算結(jié)果越接近1，表明算法收斂性能越差.考慮到正常運(yùn)算過(guò)程中有一個(gè)正常數(shù)作為判斷閾值，全局收斂性驗(yàn)證結(jié)果超過(guò)判斷閾值，表明該算法不成立，需要重新調(diào)整參數(shù)信息.當(dāng)驗(yàn)證結(jié)果低于判斷閾值，表明文中設(shè)計(jì)算法的全局收斂性達(dá)到要求，可以作用于最優(yōu)化問(wèn)題求解中.

2 數(shù)值實(shí)驗(yàn)

2.1 實(shí)驗(yàn)函數(shù)

依托于非線性方程組，完成非單調(diào)信賴域算法設(shè)計(jì)后.為了研究該算法的可行性和有效性，文中運(yùn)用MATLAB仿真軟件進(jìn)行數(shù)值實(shí)驗(yàn)，針對(duì)同一組實(shí)驗(yàn)函數(shù)，分別運(yùn)用文中設(shè)計(jì)算法，和傳統(tǒng)信賴域算法進(jìn)行數(shù)值分析，對(duì)比不同算法計(jì)算出的數(shù)值結(jié)果，判斷文中設(shè)計(jì)算法的優(yōu)越性.為了加強(qiáng)實(shí)驗(yàn)結(jié)果的說(shuō)服力，設(shè)置數(shù)值實(shí)驗(yàn)在同一臺(tái)計(jì)算機(jī)上進(jìn)行，并在MATLAB 6.5環(huán)境下運(yùn)行非單調(diào)信賴域算法.本次實(shí)驗(yàn)所應(yīng)用的實(shí)驗(yàn)函數(shù)為：

(16)

為了便于運(yùn)算，數(shù)值實(shí)驗(yàn)展開之前對(duì)實(shí)驗(yàn)函數(shù)深入分析，并繪制該函數(shù)的三維空間圖像，得到圖3所示的函數(shù)圖像.

圖3 函數(shù)三維圖像

根據(jù)圖3可以看出，本次所應(yīng)用的實(shí)驗(yàn)函數(shù)為典型函數(shù)，以該函數(shù)為基礎(chǔ)，進(jìn)行非單調(diào)信賴域運(yùn)算1，并記錄數(shù)值運(yùn)算結(jié)果.

2.2 運(yùn)算結(jié)果

運(yùn)用文中設(shè)計(jì)算法對(duì)實(shí)驗(yàn)函數(shù)進(jìn)行數(shù)次迭代計(jì)算，從不同初始點(diǎn)開始進(jìn)行運(yùn)算，將實(shí)驗(yàn)函數(shù)轉(zhuǎn)化為非線性方程組問(wèn)題再進(jìn)行迭代計(jì)算，記錄算法運(yùn)行后，生成最優(yōu)目標(biāo)函數(shù)值所需的迭代次數(shù)，以及相應(yīng)的最優(yōu)目標(biāo)函數(shù)值，形成表1所示的數(shù)值計(jì)算統(tǒng)計(jì)表.

表1 數(shù)值計(jì)算結(jié)果

根據(jù)表1可知，運(yùn)用文中提出的非單調(diào)信賴域算法進(jìn)行數(shù)值分析，在不同初始點(diǎn)條件下，經(jīng)過(guò)數(shù)次迭代，分別求解出了實(shí)驗(yàn)函數(shù)的最優(yōu)目標(biāo)函數(shù)值，表明所提算法具有可行性.

2.3 算法性能分析

為了加強(qiáng)算法性能分析結(jié)果的直觀性，運(yùn)用ANIR算法和MNMTRLS算法，在同樣的實(shí)驗(yàn)環(huán)境下，進(jìn)行數(shù)值分析，對(duì)不同算法的迭代性能進(jìn)行分析.為了更好地評(píng)估算法的總體性能，分析性能比率的累積分布函數(shù)：

(17)

公式中，t表示問(wèn)題，φ表示測(cè)試問(wèn)題的集合，u表示算法的性能比，ξ表示最佳可能比率因子，γ表示測(cè)試問(wèn)題數(shù)量，σ表示非單調(diào)信賴域算法，T表示性能比率的累積分布函數(shù).基于公式(17)，結(jié)合不同算法的運(yùn)行結(jié)果，得出圖4所示的迭代次數(shù)對(duì)比圖.

圖4 不同算法的迭代次數(shù)對(duì)比圖

根據(jù)圖4可知，文中提出的非單調(diào)信賴域算法實(shí)際運(yùn)行后，與ANIR算法和MNMTRLS算法相比，具有更好的迭代次數(shù)性能.通過(guò)計(jì)算可知，以非線性方程組為基礎(chǔ)的算法，大大簡(jiǎn)化了試探步長(zhǎng)計(jì)算步驟，使得該算法的迭代次數(shù)減少了40%～57%，在實(shí)際優(yōu)化問(wèn)題上競(jìng)爭(zhēng)力更強(qiáng).

3 結(jié)束語(yǔ)

為了更好地求解出無(wú)約束優(yōu)化問(wèn)題，信賴域方法得到廣泛應(yīng)用，本文以解決信賴域算法運(yùn)算復(fù)雜度較高的缺點(diǎn)為目標(biāo)，提出了以非線性方程組為基礎(chǔ)的算法.將所有問(wèn)題轉(zhuǎn)換為非線性方程組，再結(jié)合Hessian矩陣和雙割線折線算法，簡(jiǎn)化了信賴域試探步長(zhǎng)計(jì)算步驟，形成一種迭代性能更佳的非單調(diào)信賴域算法.

經(jīng)過(guò)實(shí)驗(yàn)可知，文中設(shè)計(jì)算法的應(yīng)用效果達(dá)到了預(yù)期目標(biāo).但是，隨著最優(yōu)化要求的不斷提升，還需要進(jìn)一步完善非單調(diào)信賴域算法.一方面需要分析信賴域子問(wèn)題類型，建立相應(yīng)的數(shù)學(xué)模型.另一方面則是依托于智能時(shí)代的發(fā)展，運(yùn)用機(jī)器學(xué)習(xí)技術(shù)求解大規(guī)模無(wú)約束優(yōu)化問(wèn)題，對(duì)非單調(diào)信賴域算法進(jìn)行改進(jìn).