錐規(guī)劃基于寬鄰域的內(nèi)點(diǎn)算法.pdf

1、本文針對(duì)半定規(guī)劃和對(duì)稱(chēng)錐規(guī)劃問(wèn)題,提出基于寬鄰域的可行內(nèi)點(diǎn)算法,分析其理論上的優(yōu)越性,并得出其具有當(dāng)前最好的迭代復(fù)雜性。
　　首先給出了錐規(guī)劃的基本內(nèi)容與理論知識(shí),以及相關(guān)符號(hào)與專(zhuān)業(yè)術(shù)語(yǔ)。為了便于后面工作的展開(kāi),先從整體上認(rèn)識(shí)錐規(guī)劃的發(fā)展與現(xiàn)狀。
　　接著給出了半定規(guī)劃上基于寬鄰域的Mehrotra型預(yù)估-矯正算法。該寬鄰域是基于常用的負(fù)無(wú)窮鄰域而來(lái),這一鄰域保證了迭代點(diǎn)的中心性。劉長(zhǎng)河博士給出了一種帶保障的Mehrotra

2、型預(yù)估-矯正算法。在此算法的基礎(chǔ)上,對(duì)其矯正步進(jìn)行改進(jìn),并結(jié)合矩陣V,作者給出了新的二階預(yù)估-矯正算法。通過(guò)一些重要引理的證明,使得算法迭代復(fù)雜性為O(nL),n代表問(wèn)題的維數(shù),L是輸入數(shù)據(jù)的長(zhǎng)度。這是目前內(nèi)點(diǎn)算法當(dāng)中最好的復(fù)雜性。
　　最后研究了對(duì)稱(chēng)錐規(guī)劃的Mehrotra型預(yù)估-矯正算法。本章提出了一種新的Mehrotra型預(yù)估-矯正算法。該算法是基于新的寬鄰域,該鄰域是在劉長(zhǎng)河博士給出的負(fù)無(wú)窮鄰域的基礎(chǔ)上提出的。該算法是在劉