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

• 作 者: 张瑞娟
• 机 构: 南开大学
• 出 处: 南开大学
• 发表日期: 2009年期
• 关键词: 线性矩阵 二次规划 规划松弛 矩阵不等式

本文研究了二次规划的精确半定规划松弛问题。一般的二次规划问题不是多项式时间可解的，但是半定规划则是可用内点法在多项式时间求解的。所以如果某个二次规划问题的半定规划松弛问题对于原问题是精确逼近的话，则原二次规划问题是多项式可解的。本研究分为五个部分：　　
第一章介绍了一般的二次规划问题，它的半定规划松弛问题及松弛问题的对偶问题，并介绍了对这类问题他人已经做出的工作及论文中用到的一些记号。　　
第二章讨论了约束条件数≤3的情况。首先说明的是对任意的约束个数，凸二次规划问题总是多项式时间可解的。其次，对于一个约束的情况，把Ben-Tal和Nemirovskiaei对实数域的结果推广到复数域，证明了半定松弛问题对原问题是精确逼近的。再次，对于约束个数等于2的情况，我们分四种情况讨论了半定规划松弛问题逼近的精确性。最后，对于3个约束的情况，我们讨论了齐次二次规划问题的一个特殊的情形。这里使用的方法都属于构造性的方法。　　
第三章研究了齐次半定规划问题的一个性质，从这个性质出发，得到和第二章中一样的结论。　　
第四章从寻找半定规划松弛问题的秩1最优解入手，讨论了线性矩阵不等式的低秩解。这样做的理由是，如果知道了半定规划松弛问题的秩1最优解，我们就能容易得到原二次规划的最优解。　　
第五章中讨论了一类非二次约束的二次规划问题。我们将张树中在实数域中得到的结果，推广到复数域中的情形。