淺析半定規(guī)劃在組合優(yōu)化中的應(yīng)用.pdf

1、半定規(guī)劃是線性規(guī)劃的一種推廣，是在滿足約束“對(duì)稱矩陣的仿射組合半正定”的條件下使線性函數(shù)極大（極小化）的問(wèn)題，這個(gè)約束是非線性的，非光滑的，凸的[1][2][3][4]。半定規(guī)劃之所以引起人們廣泛的關(guān)注，使越來(lái)越多的學(xué)者投入進(jìn)來(lái)，主要源于兩個(gè)方面:一是半定規(guī)劃擁有廣泛的應(yīng)用領(lǐng)域，例如組合優(yōu)化[5]、統(tǒng)計(jì)學(xué)、結(jié)構(gòu)設(shè)計(jì)、電子工程6（濾波器的設(shè)計(jì)和移動(dòng)通信）等;第二是因?yàn)榫€性規(guī)劃的內(nèi)點(diǎn)算法成功的推廣到了半定規(guī)劃上，并且隨著研究的日益成熟，半定

2、規(guī)劃的內(nèi)點(diǎn)算法的性能也是越來(lái)越良好，而且已經(jīng)證明內(nèi)點(diǎn)算法是求解中小規(guī)模問(wèn)題的可靠的有效的算法[7][8]。這對(duì)于半定規(guī)劃的研究具有重要的理論意義和應(yīng)用價(jià)值。
　　 半定規(guī)劃近幾年來(lái)在算法領(lǐng)域得到了廣泛的研究，為NP-hard問(wèn)題設(shè)計(jì)多項(xiàng)式時(shí)間內(nèi)的近似算法提供了一種新的思路，并且具有良好的近似性能比。通過(guò)研究生期間的研究，應(yīng)用這種思想，分別針對(duì)頂點(diǎn)覆蓋問(wèn)題[8]，環(huán)狀基因排列問(wèn)題設(shè)計(jì)了兩種多項(xiàng)式時(shí)間內(nèi)的近似算法。
　　 在

3、論文中，首先概述了半定規(guī)劃的內(nèi)容，對(duì)其基本的定義和公式進(jìn)行了簡(jiǎn)要的介紹，并且根據(jù)半定規(guī)劃作用的定義域不同，將其分為了實(shí)數(shù)半定規(guī)劃SDP和復(fù)數(shù)半定規(guī)劃CSDP，論證了SDP和CSDP可以相互轉(zhuǎn)換，而且等價(jià)。在導(dǎo)師朱大銘教授的指引下，分別應(yīng)用此方法對(duì)兩個(gè)NP-hard問(wèn)題進(jìn)行了分析:應(yīng)用SDP隨機(jī)算法思想對(duì)組合優(yōu)化中的頂點(diǎn)覆蓋問(wèn)題設(shè)計(jì)了一個(gè)多項(xiàng)式時(shí)間內(nèi)的近似算法，近似性能比為2;應(yīng)用CSDP思想針對(duì)環(huán)狀基因排列問(wèn)題設(shè)計(jì)了另外的一個(gè)多項(xiàng)式近似