半定規(guī)劃的兩類原始對偶內(nèi)點(diǎn)算法.pdf

1、重慶師范大學(xué)碩士學(xué)位論文半定規(guī)劃的兩類原始對偶內(nèi)點(diǎn)算法碩士研究生指導(dǎo)教師學(xué)科專業(yè)所在學(xué)院楊洋羅洪林副教授運(yùn)籌學(xué)與控制論數(shù)學(xué)科學(xué)學(xué)院重慶師范大學(xué)二〇_七年五月中文摘要半定規(guī)劃的兩類原始對偶內(nèi)點(diǎn)算法摘要半定規(guī)劃也稱為帶有半正定錐約束的線性規(guī)劃，其退化情形包括線性規(guī)劃和凸二次規(guī)劃.半定規(guī)劃廣泛地存在于系統(tǒng)與控制理論、金融工程、量子化學(xué)和信號(hào)處理等諸多領(lǐng)域.半定規(guī)劃的多項(xiàng)式內(nèi)點(diǎn)算法為求解組合優(yōu)化領(lǐng)域的某些中小規(guī)模的NP難問題（如著名的旅行商問題

2、和最大割問題）提供了有效的解決途徑.如何為大規(guī)模的半定規(guī)劃問題的求解設(shè)計(jì)有效的算法？從上世紀(jì)九十年代初至今，大量優(yōu)化界的學(xué)者圍繞這一核心問題，對半定規(guī)劃的各種算法，尤其是內(nèi)點(diǎn)算法展開了深入廣泛的研宄.在此基礎(chǔ)上，本文主要考慮半定規(guī)劃的寬鄰域不可行內(nèi)點(diǎn)算法和預(yù)估矯正內(nèi)點(diǎn)算法，具體地：1.針對寬鄰域不可行內(nèi)點(diǎn)算法，進(jìn)一步拓寬文獻(xiàn)[2526]中的寬鄰域并增大迭代步長a設(shè)計(jì)出一種精確的寬鄰域不可行內(nèi)點(diǎn)算法，在適當(dāng)?shù)募僭O(shè)條件下，證明了該算法具有O

3、(nL)的迭代復(fù)雜界.利用文獻(xiàn)[29]中的寬鄰域和文獻(xiàn)[3644]中的修正牛頓方向，提出一個(gè)新的寬鄰域不可行內(nèi)點(diǎn)算法證明了該算法的迭代復(fù)雜界為OW)且該算法無需在每一迭代步求解牛頓方向的正部和負(fù)部.最后，利用MATLAB編程，給出算法基于NT方向的數(shù)值實(shí)驗(yàn)結(jié)果.2.對于預(yù)估矯正內(nèi)點(diǎn)算法，通過引入矩陣V對給定的寬鄰域N(t3)類似文獻(xiàn)[4445]中的搜索方向，提出一種新的預(yù)估內(nèi)點(diǎn)算法，當(dāng)尺度矩陣選用KM方向時(shí)，證明該算法的迭代復(fù)雜界為0(