How to convert Quadratically Constrained Quadratic Program (QCQP) with indefinite constraints into Second Order Cone Program (SOCP)?

930 Views Asked by At

In their paper, "Applications of Second Order Cone Programming," Boyd, Vandenberghe et al introduce the following procedure to convert a quadratic constraint into a second order cone constraint.

For $P_i$ positive semidefinite the constraint,

\begin{equation} x^TP_ix + 2q_i^Tx+r_i\le0 \end{equation}

may be transformed to

\begin{equation} ||P_i^{.5}x+P_i^{-.5}q_i||\le(q_i^TP^{-1}q_i-r_i)^{.5} \end{equation}

In the paper the following assertion is made

We will assume for simplicity that the matrices are positive definite, although the problem can be reduced to an SOCP in general.

So, my question: How is this transformation extended to support a constraint with indefinite $P_i$?

For the PSD case,

\begin{equation} ||P_i^{.5}x+P_i^{-.5}q_i||^2 = (P_i^{.5}x+P_i^{-.5}q_i)^T(P_i^{.5}x+P_i^{-.5}q_i) \end{equation}

or

\begin{equation} x^T(P_i^{.5})^TP_i^{.5}x+2(P_i^.5)^TP_i^{-.5}q_i^Tx+q_i^T(P_i^{-.5})^TP_i^{-.5}q_i \end{equation}

which simplifies to

\begin{equation} x^TP_ix+2q_i^Tx+q_i^TP^{-1}q_i \end{equation}

However, I can't figure out how to extend this to an indefinite matrix where the matrix square root would have complex components...

In the case of an indefinite $P_i$, I think the norm on the right hand side would now be the square root of a vector times its complex conjugate transpose, something like,

\begin{equation} ||P_i^{.5}x+P_i^{-.5}q_i|| = \sqrt{(P_i^{.5}x+P_i^{-.5}q_i)^*(P_i^{.5}x+P_i^{-.5}q_i)} \end{equation}

but I am struggling to figure out the formulation to understand how this would work. It seems like instead of the matrix square root, I need a formulation where

\begin{equation} P_i = A^*A \end{equation}

for some square matrix $A$, but I have been unable to find such a decomposition and have seen several places that a matrix times it's conjugate transpose will be positive semidefinite (in which case there wouldn't be a way to construct an indefinite matrix from such a decomposition).

Apologies for any confusion in this explanation, but thanks in advance for any help!