3
$\begingroup$

Is solving a $QP$ (i.e.: quadratic program, hence a quadratic objective function with linear constraints) easier than solving a $QCQP$ (ie.: quadratic constrained quadratic problem) with linear objective?

I am aware that $QP \subseteq QCQP$ and that $QCQP$ is generally harder than $QP$. Moreover, i am aware that a linear matrix is a special case of a quadratic matrix. Consequently, a problem with linear objectives and quadratic constraints would lie in $QCQP$, but not in $QP$. On the other hand, it seems almost equivalent and my intuition is that it can not be harder to solve than a $QP$.

However, I am studying modern portfolio theory, where usually a (quadratic) variance term is optimized together with a (linear) return term. Among 2 famous reformulations, the variance can either enter the objectives or the constraints. However, for some reason i almost always see the quadratic term in the objective, even when this is not the most natural way to write the problem.

I am wondering wether this is merely convention or is there maybe some subtle computational advantage im missing.

So in summary i would like to ask:

How does the special case of a quadratic constrained quadratic problem with a linear objective function and a single quadratic constraint relate to a quadratic program? Is it equivalent or harder?

$\endgroup$
10
  • 4
    $\begingroup$ fwiw: I think this is a lovely question. $\endgroup$
    – Richard
    Nov 8, 2021 at 21:02
  • 1
    $\begingroup$ @AntonMenshov i have tried to summarize the question once more in an endit. Hopefully, this is clearer. However, if it is possible to get in touch with the reviewer i would be happy about a more specific critique, as im not very clear in howfar the question is flawed. $\endgroup$
    – ckrk
    Nov 10, 2021 at 13:23
  • 1
    $\begingroup$ I think both QP (say min risk subject to return constraint) as QCP (say max return subject to risk constraint) models are nowadays solved as cone programming models. I looked at this a while ago. Continuous models (for my data set) were about the same speed. When I added binary variables (cardinality constrained portfolios), the MIQP was significantly faster than the MIQCP model (maybe the MIP part is the cause of this, not the relaxations). $\endgroup$ Nov 11, 2021 at 4:45
  • 3
    $\begingroup$ I guess the reason for MIQP being much faster than MIQCP is that the MIQP allows you to use a fast dual simplex to warm-start in nodes, while MIQCP is harder to warm-start being interior-point based. $\endgroup$ Nov 12, 2021 at 11:47
  • 1
    $\begingroup$ @JohanLöfberg The speed difference was more caused by way fewer explored nodes. $\endgroup$ Nov 16, 2021 at 2:19

1 Answer 1

4
$\begingroup$

Quadratically constrained problems are fundamentally more complicated than linearly constrained problems because the feasible set is not necessarily convex (unless, of course, you are specific about what kinds of constraints you allow).

To give just one example, consider the problem $$ \min_{x,y} -y \\ \text{such that } -1 \le x \le 1 \\ \qquad\qquad \quad 0 \le y \le x^2+1. $$ If you plot the feasible set, you will see that it is not convex. Indeed, the problem has two solutions: $x=\pm 1, y=2$.

On the other hand, a convex quadratic objective function with linear constraints has only one solution, and it can be found using active set methods. These methods are not vastly more complex than the simplex algorithm for linear programs.

$\endgroup$
1
  • 1
    $\begingroup$ this example really nails down my question! $\endgroup$
    – ckrk
    Nov 16, 2021 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.