凸約束的非線性方程系統(tǒng)的仿射內(nèi)點(diǎn)信賴域法.pdf

1、最優(yōu)化問題是在有限種或無限種可行方案中挑選出最優(yōu)的方案。它在工農(nóng)業(yè)、國(guó)防、交通、金融、通信等領(lǐng)域都有著廣泛的應(yīng)用。伴隨著計(jì)算機(jī)的高度發(fā)展和軟件的完善，解決最優(yōu)化問題在生產(chǎn)和生活的各個(gè)方面變得越來越重要，也成為現(xiàn)實(shí)。 求解最優(yōu)化問題的方法有很多種，其中線搜索技術(shù)與信賴域策略是保證算法的全局收斂性的兩個(gè)重要手段。本文主要針對(duì)凸約束，尤其是有界變量約束的非線性方程系統(tǒng)，將其轉(zhuǎn)換成最優(yōu)化問題，提出了各類結(jié)合非單調(diào)線搜索技術(shù)的內(nèi)點(diǎn)信賴域法

2、。 現(xiàn)代信賴域方法的基本思想是在當(dāng)前迭代點(diǎn)的某個(gè)鄰域(稱為信賴域)內(nèi)極小化目標(biāo)函數(shù)的一個(gè)合適的二次模型，并反復(fù)校正信賴域半徑，得到可接受方向步。對(duì)于僅帶有線性不等式的約束優(yōu)化問題，Coleman和Li在[6]提出了“雙信賴域方法”，巧妙地構(gòu)造了一個(gè)仿射變換矩陣，以及合理的近似二次函數(shù)和信賴域子問題，克服了不等式約束帶來的困難。Heinkenschloss et al.在文獻(xiàn)[20]中提出了一類仿射矩陣，得到了與此有關(guān)的一階必要條

3、件。而文獻(xiàn)[13]中給出的仿射矩陣則幫助我們?cè)谇蠼庑刨囉蜃訂栴}時(shí)不涉及有界約束。 本文給出了求解有界約束的非線性方程組的非單調(diào)信賴域內(nèi)點(diǎn)算法。在求解子問題的過程中，通過引入一個(gè)仿射矩陣巧妙的去掉了有界約束，從而將原子問題轉(zhuǎn)換成一個(gè)只具有橢球約束的信賴域子問題。解此子問題即得嚴(yán)格位于可行域內(nèi)部的點(diǎn)，通過非單調(diào)線搜索獲得下一迭代點(diǎn)并保證其有足夠下降量。在合理的假設(shè)條件下，所給出的這類算法具有全局收斂性和超線性收斂速率。數(shù)值結(jié)果表明了

4、算法的有效性。 共軛梯度法是解優(yōu)化問題時(shí)的一類常用方法，由于具有算法簡(jiǎn)便，只需一階信息，易于編程以及存儲(chǔ)空間小等優(yōu)點(diǎn)，共軛梯度法已經(jīng)成為求解大規(guī)模問題的一種主要方法。Bulteau與Vial在[3]中構(gòu)造了無約束最優(yōu)化問題的共軛梯度路徑，其基本思想是將標(biāo)準(zhǔn)共軛方向法應(yīng)用于無約束優(yōu)化目標(biāo)函數(shù)的局部二次近似函數(shù)，得到一組共軛方向序列。共軛梯度路徑即為該共軛方向序列的線性組合。在本文中，我們引入另一類仿射變化矩陣，構(gòu)造了共軛梯度路徑。

5、考慮將信賴域子問題中的信賴域約束去掉，沿著這條路徑搜索得到迭代方向。當(dāng)該迭代方向步不嚴(yán)格可行時(shí)。利用非單調(diào)回代線搜索技術(shù)得到可接受的步長(zhǎng)因子，并且此步長(zhǎng)因子保證了新的迭代點(diǎn)有足夠的下降量并且位于可行域的內(nèi)部。證明了當(dāng)共軛梯度路徑中的參數(shù)趨于無窮時(shí)，產(chǎn)生的搜索方向即為牛頓步或擬牛頓步從而具有超線性收斂速率。數(shù)值測(cè)試表明算法的可行性與有效性。 Lanczos方法和共軛梯度路徑法的思想啟迪我們，對(duì)優(yōu)化問題的近似二次模型應(yīng)用Lanczo

6、s方法過程中同時(shí)應(yīng)用共軛梯度法，即對(duì)問題三對(duì)角化的同時(shí)也計(jì)算出了共軛方向序列，這樣我們可以得到Lanczos方向序列和共軛方向序列，由此生成一條新的路徑，這里命名為L(zhǎng)anczos路徑。這條路徑有類似于共軛梯度路徑的一些重要性質(zhì)，這對(duì)于算法的整體收斂性和超線性收斂性的分析很重要。利用仿射Lanczos路徑法求解有界變量約束非線性方程組能大大的減少計(jì)算量，在合理的假設(shè)下，本文也證明了這類算法具有整體收斂性和局部超線性收斂速率。數(shù)值測(cè)試結(jié)果表

7、明了算法的有效性和穩(wěn)定性。投影梯度法是解決最優(yōu)化問題的又一類方法[4，5]，算法雖然具有較快的收斂速度，但每次迭代可能要計(jì)算幾次投影，這樣大大增加了工作量。文獻(xiàn)[9]與[36]給出了每次只需計(jì)算一次投影的算法。在求解問題的最優(yōu)化方法中，在最優(yōu)點(diǎn)x*處的非奇異假設(shè)是一個(gè)常用的條件([36])，文獻(xiàn)[24，40]中，用Levenberg-Marquardt法求解凸約束非線性方程組時(shí)把非奇異假設(shè)用一個(gè)較弱的條件——局部誤差界條件來代替。受此啟

8、發(fā)，改變[36]中所提供的投影牛頓法中的投影區(qū)域類似的得到投影牛頓步并結(jié)合局部誤差界這一條件，本文給出了局部誤差界的有界約束非線性方程組的非單調(diào)信賴域算法。證明了算法全局收斂性并且證明了在局部誤差界這一較弱條件下算法具有超線性收斂速率。數(shù)值實(shí)驗(yàn)表明了以上所給算法的可行性和有效性。 對(duì)于具有一般凸約束的非線性方程組。[9]給出了求一般凸約束的投影梯度算法，參考此文得到搜索方向，并通過求解一個(gè)簡(jiǎn)單的信賴域子問題得到搜索步長(zhǎng)，得到求解

9、凸約束非線性方程組的非單調(diào)信賴域算法，證明了算法在合理假設(shè)下全局收斂且在滿足增長(zhǎng)條件(局部誤差界的特殊形式)下算法超線性收斂。本文給出的凸約束非線性方程組的投影信賴域算法主要參考了文獻(xiàn)[4]與[42]中的算法，避免直接求解信賴域子問題，通過近似求解滿足兩個(gè)與信賴域相關(guān)條件的步進(jìn)而得到搜索方向，再通過一維搜索得到下一迭代點(diǎn)。所提供的投影信賴域算法全局收斂且在局部誤差界條件下算法具有1.5階的收斂速率。算法的數(shù)值測(cè)試將作為進(jìn)一步研究工作。