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

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

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