幾類優(yōu)化問題的數(shù)值算法分析.pdf

1、設(shè)計(jì)有效的算法是數(shù)值最優(yōu)化中的重要研究課題。本碩士論文考察無約束優(yōu)化問題、互補(bǔ)問題、多項(xiàng)式規(guī)劃問題、張量規(guī)劃問題等優(yōu)化領(lǐng)域內(nèi)的重點(diǎn)問題和近年來的熱點(diǎn)問題，主要是從算法的設(shè)計(jì)、收斂性分析、數(shù)值計(jì)算效果、實(shí)際應(yīng)用等方面進(jìn)行研究。所設(shè)計(jì)的算法分別使用CUTEr、MCPLIB等標(biāo)準(zhǔn)的測試題庫以及天津市第一中心醫(yī)院的核磁共振影像數(shù)據(jù)來進(jìn)行測試，并分別與SOSTOOLS、OptimizationTools(MatLab)等成熟的優(yōu)化軟件包進(jìn)行了數(shù)值

2、比較，實(shí)際計(jì)算效果是令人滿意的。具體地，論文討論的主要內(nèi)容分成如下三個(gè)方面：
　　 本文的第二章主要考慮無約束優(yōu)化問題，首先提出了一個(gè)新的非單調(diào)線搜索算法，在適當(dāng)?shù)臈l件下證明它的全局收斂性和局部R-線性收斂性。對于所提出的算法，用測試題庫CUTEr中的問題進(jìn)行了測試，并與兩個(gè)流行的非單調(diào)線搜索框架進(jìn)行了比較。數(shù)值實(shí)驗(yàn)表明新提出的算法是有效的。其次，將一個(gè)非單調(diào)線搜索算法推廣到了求解一類約束優(yōu)化問題上，并且證明：如果所考慮的目標(biāo)函

3、數(shù)是擬凸的，而且相應(yīng)的約束集合所定義的流形具有非負(fù)的截面曲率，那么所設(shè)計(jì)的算法是全局收斂的，并且收斂到問題的全局最優(yōu)解。
　　 第三章主要考慮互補(bǔ)問題?；パa(bǔ)函數(shù)在互補(bǔ)問題的重構(gòu)理論中起到了關(guān)鍵性的作用。本章首先提出了一族新的互補(bǔ)函數(shù)，該互補(bǔ)函數(shù)包含了眾多流行的互補(bǔ)函數(shù)作為特例，并討論了其若干性質(zhì)，包括連續(xù)可微、Lipschitz連續(xù)、(強(qiáng))半光滑、LC1、SC1等.利用這族互補(bǔ)函數(shù)，討論了一個(gè)無導(dǎo)數(shù)的算法，使用測試題庫MCPLI

4、B來進(jìn)行數(shù)值實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明新提出的函數(shù)是有價(jià)值的。其次，討論了絕對值方程組與線性互補(bǔ)問題之間的關(guān)系：無需任何條件證明了Rn上的絕對值方程組等價(jià)于標(biāo)準(zhǔn)的線性互補(bǔ)問題，并給出了絕對值方程組的解集的一些性質(zhì)；同時(shí)也提出了二階錐上的絕對值方程組模型，設(shè)計(jì)了一個(gè)求解它的廣義Newton算法，證明了算法的收斂性，一些數(shù)值計(jì)算表明該算法是有效的。作為一個(gè)應(yīng)用，該算法為求解二階錐上的互補(bǔ)問題提供了一個(gè)全新的方法。再次，對于互補(bǔ)問題的光滑Newton

5、算法，現(xiàn)存的都是基于單調(diào)線搜索進(jìn)行分析的，而實(shí)際計(jì)算中都用了非單調(diào)線搜索，缺乏相應(yīng)的理論分析。本章第三部分引入了Kanzow-Kleinmichel光滑函數(shù)并證明了其Jacobian相容性，設(shè)計(jì)了一個(gè)求解非線性互補(bǔ)問題的具有新的非單調(diào)線搜索的光滑Newton算法并證明了其全局收斂性與局部二次收斂性，使用測試題庫MCPLAB進(jìn)行了數(shù)值實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明新設(shè)計(jì)的算法是有效的.最后，考慮對稱錐互補(bǔ)問題，它為很多類互補(bǔ)問題提供了一個(gè)統(tǒng)一的框架，

6、是近十幾年優(yōu)化領(lǐng)域研究的熱點(diǎn)之一.本章第四部分給出了一個(gè)具有非單調(diào)線搜索的光滑Newton算法，在目前最弱的假設(shè)條件下證明了算法的全局收斂性.
　　 第四章主要是考慮多項(xiàng)式規(guī)劃問題.首先，對于雙二次規(guī)劃問題，在不同于傳統(tǒng)多項(xiàng)式時(shí)間算法的思路下給出了雙二次規(guī)劃的一個(gè)目前最好的近似率，而且對于所給的松弛問題，提出了一個(gè)交互方向法，證明了算法的全局收斂性，數(shù)值計(jì)算表明：該方法可以為雙二次規(guī)劃問題提供一個(gè)很好的近似解，在與已知方法的數(shù)值

7、比較中占有絕對優(yōu)勢.同時(shí)，通過提出和分析一種張量特征值的方法，也得到了一些雙二次規(guī)劃的結(jié)論.其次，將帶秩約束的二次規(guī)劃的近似率從目標(biāo)函數(shù)矩陣為半正定推廣到了一般情況.再次，對于多項(xiàng)式系統(tǒng)，給出了兩個(gè)新的矩陣分解定理，并且在此基礎(chǔ)上給出了一些新的多項(xiàng)式系統(tǒng)的擇一定理.特別地，在一定條件下，將S-引理推廣到了高次多項(xiàng)式系統(tǒng).作為一個(gè)應(yīng)用，給出了Z-特征值極值問題的(充分必要)最優(yōu)性條件.最后，提出了一個(gè)用序列SDP方法逼近空間張量錐規(guī)劃的的

8、數(shù)值算法，并對隨機(jī)構(gòu)造的問題進(jìn)行了數(shù)值計(jì)算，數(shù)值結(jié)果與SOSTOOLS得到的計(jì)算結(jié)果作了比較，結(jié)果顯示：提出的方法是有效的.基于空間張量錐規(guī)劃，提出了一個(gè)更廣的張量錐規(guī)劃并給出了對偶理論，把序列SDP方法推廣到張量錐規(guī)劃上，稱這個(gè)方法為TCOSS.對于核磁共振醫(yī)學(xué)影像中的彌散陡度張量模型，用錐規(guī)劃的方法作了正定性分析，提出了一個(gè)新的錐規(guī)劃算法，用此算法與傳統(tǒng)的OptimizationTools(MatLab)中的最小二乘方法對模擬數(shù)據(jù)與