解半正定規(guī)劃問題的基于參數(shù)化對數(shù)障礙函數(shù)的內點算法.pdf

1、解線性規(guī)劃問題的具有多項式時間內點算法已顯示出強大的功效和廣泛的應用，研究者們試圖將它推廣到凸非線性規(guī)劃問題上去。從上世紀九十年代中期到現(xiàn)在，研究的熱點集中于兩種凸非線性規(guī)劃模型，即半正定規(guī)劃和二階錐規(guī)劃問題。具有多項式時間內點算法主要應用于解大規(guī)模優(yōu)化問題，并可分析算法的計算復雜性。 在眾多的內點算法中，基于對數(shù)(logarithm)障礙函數(shù)的內點算法是一類最為有效和最為廣泛應用的內點算法。在已有的基于障礙函數(shù)的原始-對偶內點

2、算法的研究工作中，對障礙函數(shù)的研究基本局限于對障礙函數(shù)的障礙性的分析，很少考慮障礙函數(shù)中所含參數(shù)對障礙性的影響，也沒有對參數(shù)作具體的分析。然而，有些數(shù)值結果顯示，障礙函數(shù)中所含參數(shù)對障礙性起很大的作用，比如有限障礙函數(shù)就是一個典型的例子[5]。 在本文，我們所做的工作集中在以下三個方面。首先，我們考慮對一般障礙函數(shù)的參數(shù)化問題，其目的是為了擴大障礙函數(shù)的種類。我們研究了參數(shù)化障礙函數(shù)和它的的核函數(shù)的性質，以及參數(shù)化核函數(shù)的導數(shù)性

3、質，比較了參數(shù)化核函數(shù)的各階導數(shù)。并分析了參數(shù)和算法復雜性的關系。進一步我們給出了參數(shù)化對數(shù)障礙函數(shù)，并根據(jù)參數(shù)化對數(shù)障礙函數(shù)設計了解半正定規(guī)劃問題的原始一對偶內點算法，應用參數(shù)化對數(shù)障礙函數(shù)的性質分析了算法的復雜性，得到了一個理論迭代界，這個迭代界與解線性規(guī)劃問題的算法的迭代界一致。最后，我們通過數(shù)值算例闡明參數(shù)化對數(shù)障礙函數(shù)和算法復雜性的關系．數(shù)值結果表明和基于經典對數(shù)障礙的原始一對偶內點算法相比，我們的算法的迭代界與參數(shù)的不同取值

4、有關．當參數(shù)取某個值時，算法的迭代界比經典的算法好。 全文共分五章，在第一章里，我們簡單介紹半正定規(guī)劃問題、原始-對偶內點算法與障礙函數(shù)、以及本文的主要工作．在第二章里，我們主要討論了參數(shù)化障礙函數(shù)和的參數(shù)化核函數(shù)的性質，以及參數(shù)和算法的關系。在第三章，我們給出了一個基于參數(shù)化對數(shù)障礙函數(shù)的解半正定規(guī)劃問題的原始-對偶內點算法，分析了算法的計算復雜性．在第四章給出了基于參數(shù)化障礙函數(shù)原始-內點算法的線性規(guī)劃算例和基于參數(shù)化對數(shù)障