二階錐規(guī)劃的若干算法研究.pdf

1、二階錐規(guī)劃是一個(gè)凸優(yōu)化問題，它是在一個(gè)仿射子空間和有限個(gè)二階錐的笛卡爾乘積的交集上極大化或極小化一個(gè)線性函數(shù)。許多數(shù)學(xué)規(guī)劃問題，如線性規(guī)劃、凸二次規(guī)劃和二次約束的凸二次規(guī)劃等，都可轉(zhuǎn)化為二階錐規(guī)劃求解。近年來，由于其在工程、控制與設(shè)計(jì)、機(jī)器學(xué)習(xí)、組合優(yōu)化等諸多領(lǐng)域的廣泛應(yīng)用，二階錐規(guī)劃已成為數(shù)學(xué)規(guī)劃領(lǐng)域的一個(gè)重要的研究方向。
　　本文主要研究求解二階錐規(guī)劃的內(nèi)點(diǎn)算法和光滑算法。全文共分八章。首先在第一章，我們簡要介紹二階錐規(guī)劃的模

2、型，研究背景、意義和現(xiàn)狀，并概述了本文的主要工作。
　　第二章，給出一個(gè)求解二階錐規(guī)劃的非精確不可行內(nèi)點(diǎn)算法。算法不要求初始點(diǎn)及其迭代點(diǎn)的可行性，只要求每次迭代產(chǎn)生的點(diǎn)位于不可行中心路徑的某個(gè)鄰域內(nèi)。通過選取適當(dāng)?shù)牟介L，證明了算法是全局收斂的多項(xiàng)式時(shí)間算法。
　　第三章，給出了一個(gè)新的增長項(xiàng)是線性的核函數(shù)?；诖撕撕瘮?shù)給出了一個(gè)求解二階錐規(guī)劃的原始-對偶內(nèi)點(diǎn)算法，分析了算法的復(fù)雜性，并得到了一個(gè)關(guān)于大步校正方法的迭代界O(r

3、log r/ε)，這里r表示二階錐規(guī)劃中二階錐的個(gè)數(shù)。這個(gè)界與典型的基于對數(shù)障礙函數(shù)的原始-對偶內(nèi)點(diǎn)算法的界相同。此外，我們還給出了一個(gè)數(shù)值例子，并探討了核函數(shù)中的參數(shù)對算法運(yùn)行的影響。
　　第四章，將求解線性規(guī)劃的加權(quán)路徑跟蹤內(nèi)點(diǎn)算法推廣求解二階錐規(guī)劃。該方法在每步迭代時(shí)采用完全牛頓步，不需要做任何線搜索，并且具有局部二次收斂速度和目前所知的最好的多項(xiàng)式時(shí)間算法復(fù)雜性。
　　第五章，通過對稱擾動(dòng)Fischer-Burmei

4、ster函數(shù)，給出一個(gè)新的光滑函數(shù)?；谠摴饣瘮?shù)，把二階錐規(guī)劃問題轉(zhuǎn)化成一個(gè)參數(shù)化的光滑方程組，并給出了一個(gè)非內(nèi)部連續(xù)化算法。該算法對初始點(diǎn)的選取沒有任何限制，不要求初始點(diǎn)及所產(chǎn)生的迭代點(diǎn)嚴(yán)格可行。算法在每步迭代中只需解一個(gè)線性方程組并進(jìn)行一次線性搜索。即使不滿足嚴(yán)格互補(bǔ)假設(shè)條件，所給算法也具有全局收斂和局部二階收斂性。數(shù)值試驗(yàn)表明新算法是有效的。
　　第六章，提出一類含有單參數(shù)的光滑函數(shù)，它包含一些已知的光滑函數(shù)作為特殊情況。

5、基于此類光滑函數(shù)，給出一個(gè)求解二階錐規(guī)劃的光滑牛頓法，在較弱條件下證明了算法具有全局和局部二階收斂性。此外，我們還利用隨機(jī)產(chǎn)生的一些二階錐規(guī)劃問題做數(shù)值試驗(yàn)。數(shù)值結(jié)果不但表明算法是有效的，還表明光滑函數(shù)中的參數(shù)在算法的運(yùn)行過程中起著重要作用。
　　第七章，基于一個(gè)非對稱擾動(dòng)的Fischer-Burmeister光滑函數(shù)，給出了一個(gè)新的求解二階錐規(guī)劃的光滑算法。該算法所產(chǎn)生的迭代點(diǎn)列的任何聚點(diǎn)都是二階錐規(guī)劃的解。進(jìn)一步，算法產(chǎn)生的迭