4
$\begingroup$

I have a quadratically constrained quadratic program (QCQP) 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 program (SOCP) 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$

1 Answer 1

8
$\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$
1
  • $\begingroup$ Why is it not possible to go the other direction? $\endgroup$
    – Apprentice
    Jan 26, 2021 at 9:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .