There are a few questions on this topic already. However, none of them really answer my question. The most relevant are these:

Quadratic optimisation with quadratic equality constraints

Quadratic Equality Constraints via SDP

I have a quadratic problem with quadratic constraints, and my constraints are equalities: $$ \text{mimize}\quad x^TQ_0x+q_0^Tx\\ \text{s. t.}\quad x^TQ_ix+q_i^Tx=0$$ which can be rewritten as: $$ \text{mimize}\quad x^TQ_0x+q_0^Tx\\ \text{s. t.}\quad x^TQ_ix+q_i^Tx\le 0\\ \quad\quad\quad\quad x^T(-Q_i)x-q_i^Tx\le 0$$ On the literature I've read, the only restriction for the problem to be convex are that the matrices $Q$ have to be positive semi-definite, which is satisfied (in my case) for both restrictions.

Does the equality make the problem nonconvex and can someone give me some references about this? Or, since the semi-definiteness is preserved, is my problem is still convex?

Lastlty, if it is nonconvex, does going to a SOCP or SDP help me?

Thank you

  • $\begingroup$ As we know semi-definiteness conclude convexity, so your problem is remained convex. $\endgroup$ – Nosrati Jan 6 '16 at 16:12
  • $\begingroup$ Thank you very much for your comment, so are you saying that the problem is convex if and only if Q is semi-definite? Or in other words the that it is sufficient to guarantee convexity? $\endgroup$ – strangelyput Jan 7 '16 at 10:35
  • $\begingroup$ Your second constraint is $x^T(-Q_i)x - q_i^Tx\leq 0$, hence the matrix in the quadratic constraint is negative semidefinite if $Q_i$ is positive semidefinite. For $x^TAx+b^Tx \leq 0$ to be a convex set, $A$ has to be positive semidefinite. You cannot just disregard the signs $\endgroup$ – Johan Löfberg Jan 7 '16 at 11:58
  • $\begingroup$ Johan, please check the comment to your answer: math.stackexchange.com/questions/1602137/… $\endgroup$ – strangelyput Jan 7 '16 at 13:08

Quadratic equalities are never convex. Simply consider the trivial scalar case $x^2=1$, which has two distinct feasible points $-1$ and $1$.

As it is nonconvex, you cannot convert it to an SOCP, so your final question doesn't really make any sense.

  • $\begingroup$ that might be true but in that case the semi-definiteness is not preserved, so that is not really my question $\endgroup$ – strangelyput Jan 7 '16 at 10:28
  • $\begingroup$ How do you mean semi-definiteness ever could be preserved when writing a quadratic equality as two inequalities. A quadratic constraint is never convex. No equalities beyond affine are convex. $\endgroup$ – Johan Löfberg Jan 7 '16 at 11:54
  • $\begingroup$ To the best of my knowledge, for a matrix to be positive semi-definite its eigenvalues must all be non-negative. So for some particular cases of matrices, both $Q_i$ and $-Q_i$ can be both positive semi-definite. For example, [0 1; 0 0] and [0 -1; 0 0]. $\endgroup$ – strangelyput Jan 7 '16 at 12:09
  • $\begingroup$ Convexity is checked on the hessian, which will be $(Q_i + Q_i^T)/2$, i.e., the $Q_i$ matrix has to be symmetric. If you check eigenvalues on those symmetrized matrices, you will see they are indefinite. $\endgroup$ – Johan Löfberg Jan 7 '16 at 14:29
  • $\begingroup$ Ok, that makes sense, because on the example $Q_i$ is not Hermitian.Its Hermitian version [0 1; 1 0] is indefinite. I was not aware of this requirement. Thank you for your help. Do you see any hope for this problem to be written in a convex framework? $\endgroup$ – strangelyput Jan 7 '16 at 15:16

For the constraints, we normally require that the feasible set be a convex set, while the objective function should be convex. In general, the set of points (or vectors) satisfying a quadratic equality constraint may not be a convex set.

For example, take the scalar case where Q = 1 (positive definite) and the quadratic equation is \begin{equation*} x^T(1)x = 9 \\ \Rightarrow x^2 = 9 \end{equation*} The feasible set, in this case, is {-3,3}. The line joining the elements -3 and 3 does not satisfy the quadratic equality. In particular, taking $\alpha$ as 0.5, the square of zero is clearly not 9. Hence, despite Q being positive definite, the constraint is not convex.

See this answer: Michael Grant (https://math.stackexchange.com/users/52878/michael-grant), Why is the constraint $\|w\| = 1$ non-convex?, URL (version: 2015-05-28): https://math.stackexchange.com/q/1301592.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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