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

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

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