求解 QP 是否比具有线性目标的 QCQP 更容易?

计算科学 优化 二次规划 qcqp
2021-12-05 22:34:45

求解(即:二次程序,因此是具有线性约束的二次目标函数)是否比求解(即:二次约束二次问题)更容易?QPQCQP

我知道并且通常比更难。此外,我知道线性矩阵是二次矩阵的特例。因此,线性目标和二次约束的问题在于,而不是另一方面,它似乎几乎等价,我的直觉是它不会比更难解决。QPQCQPQCQPQPQCQPQPQP

但是,我正在研究现代投资组合理论,其中通常将(二次)方差项与(线性)收益项一起优化。在 2 个著名的重新表述中,方差可以输入目标或约束。然而,由于某种原因,我几乎总是在目标中看到二次项,即使这不是写问题的最自然方式。

我想知道这仅仅是惯例还是我缺少一些微妙的计算优势。

所以总而言之,我想问:

具有线性目标函数和单个二次约束的二次约束二次问题的特殊情况如何与二次规划相关?是同等的还是更难?

1个回答

从根本上说,二次约束问题比线性约束问题更复杂,因为可行集不一定是凸的(当然,除非您具体说明允许的约束类型)。

仅举一个例子,考虑问题 如果你绘制可行集,你会发现它不是凸的。事实上,这个问题有两个解决方案:

minx,yysuch that 1x10yx2+1.
x=±1,y=2

另一方面,具有线性约束的凸二次目标函数只有一个解,并且可以使用活动集方法找到。这些方法并不比线性规划的单纯形算法复杂得多。