二階錐規(guī)劃和二階錐互補(bǔ)問題的算法研究.pdf

1、二階錐規(guī)劃是在一個仿射空間和有限個二階錐的笛卡爾積的交集上極小化或者極大化一個線性函數(shù)問題.其約束是非線性的,但卻是凸的,因此二階錐規(guī)劃屬于凸規(guī)劃.二階錐規(guī)劃是半定規(guī)劃的特例,而線性規(guī)劃、凸二次規(guī)劃和二次約束的凸二次優(yōu)化等可作為它的特例.由于其寬廣的應(yīng)用范圍、特殊的錐結(jié)構(gòu)和計(jì)算上的方便性,所以它有其獨(dú)立的研究價值.由于它的廣泛應(yīng)用和原始一對偶內(nèi)點(diǎn)法的迅速發(fā)展,二階錐規(guī)劃已經(jīng)成為數(shù)學(xué)規(guī)劃領(lǐng)域的一個重要研究方向.
　　 二階錐互補(bǔ)問

2、題是一類均衡優(yōu)化問題.近幾年,人們借助歐幾里得約當(dāng)代數(shù)技術(shù),在對稱錐互補(bǔ)問題的研究方面取得了突破性進(jìn)展并使之逐漸受到重視.二階錐互補(bǔ)問題是二階錐規(guī)劃的推廣,它包括線性二階錐互補(bǔ)問題和非線性二階錐互補(bǔ)問題.近幾年來,人們對它的研究呈上升趨勢,主要研究內(nèi)容包括:解的存在性與特征,勢函數(shù)和誤差界,各種光滑化方法和優(yōu)化方法,以及各種實(shí)際應(yīng)用.關(guān)于非線性二階錐規(guī)劃及其互補(bǔ)問題的理論和算法,其研究方興未艾,是當(dāng)今人們關(guān)注的熱點(diǎn)課題之一.
　　

3、 本文主要研究二階錐規(guī)劃及其互補(bǔ)問題的算法.論文共分八個部分:
　　 第一部分,介紹二階錐規(guī)劃和二階錐互補(bǔ)問題的模型,研究背景、意義和現(xiàn)狀,并對現(xiàn)有算法加以總結(jié),從而引出需要進(jìn)一步解決的問題及本文所作的主要工作.
　　 第二部分,簡要介紹有關(guān)預(yù)備知識.主要介紹歐幾里得約當(dāng)代數(shù)、二階錐規(guī)劃的最優(yōu)性條件、中心路徑條件、互補(bǔ)條件和原始-對偶內(nèi)點(diǎn)算法.
　　 第三部分,定義了中心路徑的一個寬鄰域,并給出二階錐規(guī)劃問題的

4、一個寬鄰域原始-對偶路徑跟蹤內(nèi)點(diǎn)算法,使得所有迭代點(diǎn)都跟蹤這個寬領(lǐng)域,得到目前為止寬鄰域路徑跟蹤內(nèi)點(diǎn)算法最好的迭代復(fù)雜性界.
　　 第四部分,給出一個與二階錐關(guān)聯(lián)的光滑函數(shù),并研究該光滑函數(shù)的性質(zhì).基于此光滑函數(shù),給出二階錐規(guī)劃問題的一個光滑牛頓類型算法.該算法把擾動最優(yōu)性條件重新表述成-個線性方程組進(jìn)行求解,得到比相應(yīng)的內(nèi)點(diǎn)法更強(qiáng)的結(jié)果.它可以始于任意初始點(diǎn)；每步迭代只需求解一個線性方程組,執(zhí)行一次線搜索；在較弱的假設(shè)下,算法

5、所產(chǎn)生的序列全局收斂,并且在無嚴(yán)格互補(bǔ)條件的情況下Q-二次收斂于問題的最優(yōu)解.
　　 第五部分,受求解變分不等式問題的交替方向法的啟發(fā),給出二階錐規(guī)劃的一個帶完全牛頓步的非內(nèi)點(diǎn)全局收斂算法.該算法的主要思想是把原始-對偶最優(yōu)性條件中的互補(bǔ)條件重新表述成一個投影方程.所給算法對初始點(diǎn)的可行性不作任何要求；每步迭代只需求解一個系數(shù)矩陣固定的線性方程組,執(zhí)行兩次簡單的投影運(yùn)算；無需執(zhí)行任何線搜索；不要求約束系數(shù)矩陣的行向量組線性獨(dú)立；

6、算法所產(chǎn)生的序列全局收斂到問題的最優(yōu)解,無需嚴(yán)格互補(bǔ)條件,這一結(jié)果強(qiáng)于相應(yīng)的內(nèi)點(diǎn)法和光滑算法.
　　 第六部分,研究一類特殊的二階錐規(guī)劃問題一帶有P0函數(shù)的非線性互補(bǔ)問題.基于一個新的帶有懲罰項(xiàng)的光滑函數(shù),把問題近似成參數(shù)化的光滑方程組,并且給出一個新的非內(nèi)部連續(xù)化方法.所給算法在每步迭代只需求解一個線性方程組,執(zhí)行一次Armijo類型的線搜索.在不需要嚴(yán)格互補(bǔ)條件的情況下,證明了該算法是全局收斂和超線性收斂的.并且,在一個較弱