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

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

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

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

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