二次規(guī)劃及其精確半定規(guī)劃松弛問題.pdf

1、本文研究了二次規(guī)劃的精確半定規(guī)劃松弛問題。一般的二次規(guī)劃問題不是多項式時間可解的，但是半定規(guī)劃則是可用內點法在多項式時間求解的。所以如果某個二次規(guī)劃問題的半定規(guī)劃松弛問題對于原問題是精確逼近的話，則原二次規(guī)劃問題是多項式可解的。本研究分為五個部分：
　　 第一章介紹了一般的二次規(guī)劃問題，它的半定規(guī)劃松弛問題及松弛問題的對偶問題，并介紹了對這類問題他人已經(jīng)做出的工作及論文中用到的一些記號。
　　 第二章討論了約束條件數(shù)≤3

2、的情況。首先說明的是對任意的約束個數(shù)，凸二次規(guī)劃問題總是多項式時間可解的。其次，對于一個約束的情況，把Ben-Tal和Nemirovskiaei對實數(shù)域的結果推廣到復數(shù)域，證明了半定松弛問題對原問題是精確逼近的。再次，對于約束個數(shù)等于2的情況，我們分四種情況討論了半定規(guī)劃松弛問題逼近的精確性。最后，對于3個約束的情況，我們討論了齊次二次規(guī)劃問題的一個特殊的情形。這里使用的方法都屬于構造性的方法。
　　 第三章研究了齊次半定規(guī)劃問