基于非線性方程組的非單調信賴域算法研究*

唐江花

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

引言

隨著金融、貿易、計算機等方面的發展，越來越多的非線性規劃問題開始出現[1].針對這些最優化問題進行求解，成為數值求解方法的重要研究方向.信賴域算法的設計是以線性規劃為基礎，其核心在于探索試探步長，通過多次計算求解每個信賴域子問題，獲取初始試探步長，再分析函數下降量趨勢，判斷試探步長的合理性[2].非單調信賴域方法因具有較強的收斂性，受到很多研究人員的關注，多種類型的信賴域方法開始得以應用.

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

為了解決上述提出非單調信賴域算法的缺點，文中設計的算法以非線性方程組為基礎.將具有非線性規劃特點的規劃問題，轉化為非線性方程組.通過非線性約束環境下，最大或最小值的提取，搜索到最優目標函數值.同時，運用Hessian矩陣和雙割線折線算法，對現有的試探步長求解過程進行簡化，保證算法求解結果準確性的同時，減少迭代次數.

1 基于非線性方程組的非單調信賴域算法設計

1.1 非線性方程組問題轉換

約束優化問題的求解關鍵環節之一，就是非線性方程組的求解.文中提出的非單調信賴域算法，將非線性方程組問題轉換的研究[6]，作為核心研究問題.依托于非單調技術和信賴域計算理念，完成非線性方程組，與非線性優化之間的互相轉換，降低后續信賴域算法的運算復雜度.

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

F(x)=0,
x∈R

(1)

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

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

(2)

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

(3)

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

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

考慮到向量空間取值無窮大條件下，非線性方程組的函數空間擬合值與參數值之間具有反比例關系.因此，非單調信賴域運算過程中，需要確保向量空間取值夠大，并應用可微函數替換方程組中部分參數，將非線性方程組轉換為易于求解的無約束優化問題，作為最優化求解的基礎.

1.2 設計非單調信賴域模型

非單調信賴域算法設計過程中，融合Hessian矩陣，實現試探步長計算復雜度降低.信賴域方法的運行，對于Hessian矩陣在每個迭代點的正定與否，沒有強制要求.對于不合理的試探步長，可以采用二階校正的方式進行更新，得到優化后的試探步長.同時，以將信賴域內第一個迭代點為核心[8]，形成一個閉球鄰域.再添加一個自然數，判斷信賴域半徑是否成功.

實際操作過程中，信賴域子問題的求解是計算初始試探步長的基礎，文中將信賴域算法數學模型表示為：

(4)

公式中，w表示二次模型，P表示目標函數，jP表示迭代點上對目標函數的恰當模擬，j表示目標函數梯度，?表示Hessian陣.式中：

(5)

運用公式(5)所示的Hessian陣，以近似序列的形式將目標函數與導數函數信息表現出來.

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

圖1 雙割線折線圖示

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

1.3 建立多維過濾集

根據融合Hessian矩陣和雙割線折線算法的非單調信賴域模型，求解出試探步長，作為最優解計算的基礎.為了保證簡化計算結果不會影響最優化求解的準確性，文中依托于包含插值自由度信息的錐模型建立多維過濾集，進一步判斷試探步長的可行性.針對當前迭代點設計一個試探步長，可將二者的關系表示為：

ak+1=ak+φ

(6)

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

(7)

公式中，β表示信賴域子問題，v表示水平向量，B表示子函數在迭代點的Hesse近似，也稱為實對稱矩陣.

由于水平向量條件并非一項苛刻要求，正常情況下該條件可以被滿足，可以直接運用計算出的試探步長，求解非線性方程組，對比方程組求解結果與理論分析值，判斷上述計算出的試探步長的有效性.另外一種情況，就是信賴域子問題求解過程中，水平向量條件沒有得到滿足，無法直接判定試探步長.為此，文中提出將信賴域子問題求解結果劃分為三種狀態，針對不同的情形，設置相對應的最優性條件.綜上所述，將子問題處理模式設置為：

(8)

(9)

公式中，α、δ表示兩個變量，λ表示試探點，g表示過濾點.

針對試探點進行迭代更新后，結合信賴域子問題求解結果，建立多維過濾集，判斷求解出的試探步長是否合理.針對滿足要求的試探點，運用“占優”準則，選取出最優過濾點，生成多維過濾集：

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

(10)

公式中，U表示多維過濾集，N表示過濾點分量.當某一個試探點不存在迭代點占優情況，可以直接將該點添加到過濾集中.反之，則需要采用封套策略，分析函數下降量趨勢,進行過濾點選取，封套策略的具體表達公式為：

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

(11)

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

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

圖2 Nowton校正模型

1.4 完成信賴域算法設計

非單調信賴域算法研究的最后一步，就是驗證所提出算法的全局收斂性，文中考慮無約束優化特點，假設非線性方程組具有連續可微特點，則以此為基礎建立的Jacobian矩陣同樣具有連續性，可得到：

(12)

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

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

(13)

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

‖F(ε)-F(η)-?(ε)(η-ε)‖≤τ1‖η-ε‖

(14)

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

(15)

公式中，part1表示第一階段，part2表示第二階段，lim表示極限符號，∞表示正無窮.

根據公式(15)可知，第一階段和第二階段全局收斂已經達到0，而信賴域算法的收斂性驗證結果主要取決于第三階段收斂驗證結果.當第三階段收斂為0，表明該算法的全局收斂性最強，同樣，計算結果越接近1，表明算法收斂性能越差.考慮到正常運算過程中有一個正常數作為判斷閾值，全局收斂性驗證結果超過判斷閾值，表明該算法不成立，需要重新調整參數信息.當驗證結果低于判斷閾值，表明文中設計算法的全局收斂性達到要求，可以作用于最優化問題求解中.

2 數值實驗

2.1 實驗函數

依托于非線性方程組，完成非單調信賴域算法設計后.為了研究該算法的可行性和有效性，文中運用MATLAB仿真軟件進行數值實驗，針對同一組實驗函數，分別運用文中設計算法，和傳統信賴域算法進行數值分析，對比不同算法計算出的數值結果，判斷文中設計算法的優越性.為了加強實驗結果的說服力，設置數值實驗在同一臺計算機上進行，并在MATLAB 6.5環境下運行非單調信賴域算法.本次實驗所應用的實驗函數為：

(16)

為了便于運算，數值實驗展開之前對實驗函數深入分析，并繪制該函數的三維空間圖像，得到圖3所示的函數圖像.

圖3 函數三維圖像

根據圖3可以看出，本次所應用的實驗函數為典型函數，以該函數為基礎，進行非單調信賴域運算1，并記錄數值運算結果.

2.2 運算結果

運用文中設計算法對實驗函數進行數次迭代計算，從不同初始點開始進行運算，將實驗函數轉化為非線性方程組問題再進行迭代計算，記錄算法運行后，生成最優目標函數值所需的迭代次數，以及相應的最優目標函數值，形成表1所示的數值計算統計表.

表1 數值計算結果

根據表1可知，運用文中提出的非單調信賴域算法進行數值分析，在不同初始點條件下，經過數次迭代，分別求解出了實驗函數的最優目標函數值，表明所提算法具有可行性.

2.3 算法性能分析

為了加強算法性能分析結果的直觀性，運用ANIR算法和MNMTRLS算法，在同樣的實驗環境下，進行數值分析，對不同算法的迭代性能進行分析.為了更好地評估算法的總體性能，分析性能比率的累積分布函數：

(17)

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

圖4 不同算法的迭代次數對比圖

根據圖4可知，文中提出的非單調信賴域算法實際運行后，與ANIR算法和MNMTRLS算法相比，具有更好的迭代次數性能.通過計算可知，以非線性方程組為基礎的算法，大大簡化了試探步長計算步驟，使得該算法的迭代次數減少了40%～57%，在實際優化問題上競爭力更強.

3 結束語

為了更好地求解出無約束優化問題，信賴域方法得到廣泛應用，本文以解決信賴域算法運算復雜度較高的缺點為目標，提出了以非線性方程組為基礎的算法.將所有問題轉換為非線性方程組，再結合Hessian矩陣和雙割線折線算法，簡化了信賴域試探步長計算步驟，形成一種迭代性能更佳的非單調信賴域算法.

經過實驗可知，文中設計算法的應用效果達到了預期目標.但是，隨著最優化要求的不斷提升，還需要進一步完善非單調信賴域算法.一方面需要分析信賴域子問題類型，建立相應的數學模型.另一方面則是依托于智能時代的發展，運用機器學習技術求解大規模無約束優化問題，對非單調信賴域算法進行改進.