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

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

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

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

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

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

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