Is solving QP easier than a QCQP with linear objective?

Question

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?

Answer 1

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.