2
$\begingroup$

I have a quadratically constrained quadratic programming problem that I massaged into the form $$ \begin{aligned} & \underset{x}{\text{minimize}} & & x^T Q x \\ & \text{subject to} & & x^T P x < \sigma^2 \\ &&& 0 \leq x_i \leq x_i^* \\ &&& Ax=b \end{aligned} $$ where $Q$ and $P$ are positive semi-definite, $\sigma \geq 0$ and $x_i^* \geq 0 \, \forall i$.

Is this problem still convertible to a second-order cone problem so that I can use efficient solvers even with the linear constraint $Ax=b$? If so, what new variables would I need to add to the minimization to convert the problem?

$\endgroup$
3
$\begingroup$

It is always possible to convert a convex QCQP into an SOCP. It is not always possible to go the other direction, however. Just express this problem as follows: \begin{array}{ll} \text{minimize} & y \\ \text{subject to} & \|F x\|_2 \leq y \\ & \|G x\|_2 \leq \sigma \\ & 0 \preceq x \preceq x_i^* \\ & A x = b \end{array} where $F$ and $G$ are right square roots of $Q$ and $P$, respectively; that is, $F^TF=Q$ and $G^TG=P$. It really doesn't matter how you compute them; a Cholesky or will do, or a symmetric square root will do.

The first reference you've linked to should not be taken as the only form an SOCP can take. Just about any convex optimization problem whose nonlinearities can be converted to linear equations, linear inequalities, and convex Euclidean norm inequalities can be cast as an SOCP.

$\endgroup$

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.