錐規(guī)劃基于寬鄰域的內點算法.pdf

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

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