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

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

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

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

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

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

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

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

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