非凸二次規劃的全局最優性條件


10

我們知道多面體上的凸二次方最大化(最小化!)在頂點上具有全局最優值。

此外,我已經閱讀了一些論文,檢查頂點是否全局最優,可以簡化為簡單條件。我對這種特殊情況很感興趣。您能幫我嗎?無論是演示還是提供參考都很好!

3

In addition to the references already given in the comments, this paper (DOI link) demonstrates that exact solutions to some non-convex quadratic programs are given by semi-definite programming, and whenever the SDP relaxation is tight we can actually solve the SDP via SOCP!

In general the SDP relaxation will of course not be tight, but as shown by Nemirovski et. al. (DOI link) we can provide some constant factor guarantees when the sufficient condition does not hold.


2

With the exception of special cases, this problem is NP-hard. One interesting case is that minimizing a convex or concave function over a simplex can be solved in polynomial time. In other special cases it is also possible to linearise the problem through reformulations. In the general case however this would be solved by relaxing the objective and using branch and bound to find the global optimum.

It is interesting to note that there are two parts to NP-hardness in optimisation: (i) finding a solution, and (ii) verifying the solution. Because verifying the solution cannot be done in polynomial time, even if we have a solution it is still NP-hard to prove that it is globally optimal.

We see this a lot in practice as well. In global optimisation finding a solution is the easy part - the difficult part is to prove/disprove that it is globally optimal.