二次规划及其精确半定规划松弛问题

来源 :南开大学 | 被引量 : 0次 | 上传用户:huangfei1117
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文研究了二次规划的精确半定规划松弛问题。一般的二次规划问题不是多项式时间可解的,但是半定规划则是可用内点法在多项式时间求解的。所以如果某个二次规划问题的半定规划松弛问题对于原问题是精确逼近的话,则原二次规划问题是多项式可解的。本研究分为五个部分:   第一章介绍了一般的二次规划问题,它的半定规划松弛问题及松弛问题的对偶问题,并介绍了对这类问题他人已经做出的工作及论文中用到的一些记号。   第二章讨论了约束条件数≤3的情况。首先说明的是对任意的约束个数,凸二次规划问题总是多项式时间可解的。其次,对于一个约束的情况,把Ben-Tal和Nemirovskiaei对实数域的结果推广到复数域,证明了半定松弛问题对原问题是精确逼近的。再次,对于约束个数等于2的情况,我们分四种情况讨论了半定规划松弛问题逼近的精确性。最后,对于3个约束的情况,我们讨论了齐次二次规划问题的一个特殊的情形。这里使用的方法都属于构造性的方法。   第三章研究了齐次半定规划问题的一个性质,从这个性质出发,得到和第二章中一样的结论。   第四章从寻找半定规划松弛问题的秩1最优解入手,讨论了线性矩阵不等式的低秩解。这样做的理由是,如果知道了半定规划松弛问题的秩1最优解,我们就能容易得到原二次规划的最优解。   第五章中讨论了一类非二次约束的二次规划问题。我们将张树中在实数域中得到的结果,推广到复数域中的情形。
其他文献
有限环上纠错码的研究始于上世纪70年代Blake和Speigel等学者首先研究了整数剩余类环Zm,上的码.接着,Calderbank和Sloane研究了p进制整数环上的码.进一步,Dougherty, Liu和Park定
无网格方法是求解微分方程定解问题的一类新的数值方法,它采用基于点的近似,可以彻底或部分地消除网格,不仅可以保证计算的精度,而且可以减少计算难度。径向基函数配点法实施