Writing a convex quadratic constraint in SOC form

linear algebramatrix decompositionoptimizationpositive definite

I am trying to apply the following transformation for a problem:

Consider a quadratic constraint of the form

$$ x^TA^TAx+b^Tx+c\leq0. $$

This is equivalent to the SOC constraint

$$ \left\| \begin{array}{c}(1+b^Tx+c)/2\\Ax\end{array}\right\|_2 \leq (1-b^Tx-c)/2. $$

The challenge for me is, my problem is in the form $x^T Q x + bx +c \leq 0$ where $Q$ is not positive definite (it is semidefinite). So I can't apply Cholesky decomposition $Q = L^T L$ and I can't use the transformation above.

I am now trying to find another method. I tried eigenvalue-eigenvector decomposition: $Q = VDV^T$ where $D$ is a diagonal matrix. But that doesn't give the same solution as Cholesky does.

How can I write the constraint in SOC form?

Best Answer

As mentioned in the comments, your approach using the eigenvalue decomposition is correct. In this case, we have that

$$ Q=VDV^T$$

which can be written as

$$ Q=(VD^{1/2})(VD^{1/2})^T. $$

(As noted in the comments, other decompositions could work as well, but I'll use this one, since it's the one you mention). Your concern is that, if $Q$ is a positive definite matrix, then the matrix $L$ obtained by taking the Cholesky decomposition isn't the same as the matrix $VD^{1/2}$ obtained above. However, this doesn't mean that the resulting reformulation doesn't yield the same result in both cases.

Consider your example

$$ Q=\begin{pmatrix}2&-5/2\\-5/2&4\end{pmatrix}.$$

If we take the Cholesky decomposition, then, to a few digits of accuracy,

$$ L=\begin{pmatrix}1.414&0\\-1.768&0.935\end{pmatrix}. $$

If we take the eigenvalue decomposition, then, to a few digits of accuracy,

$$ VD^{1/2}=\begin{pmatrix}-0.459&1.338\\-0.311&-1.976\end{pmatrix}. $$

Indeed, $L\neq{VD^{1/2}}$. However, let's look at the plots of the level sets for all three formulations:

All three feasible regions are the same

Voilà

Edit: A note on why this is true: essentially, we are employing this theorem:

Theorem: Let $Q\in\mathbb{R}^{n\times{n}}$ be positive semidefinite, and let $b\in\mathbb{R}^n$, $c\in\mathbb{R}$. Let $L\in\mathbb{R}^{n\times{n}}$ be any matrix such that $Q=L^TL$. Then the sets $$ S_1=\bigg\{x\in\mathbb{R}^n\ \bigg|\ x^TQx+b^Tx+c\leqslant0\bigg\} $$ and $$ S_2=\bigg\{x\in\mathbb{R}^n\ \bigg|\ \left\|\begin{array}{c}(1+b^Tx+c)/2\\Lx\end{array}\right\|_2\leqslant(1-b^Tx-c)/2\bigg\} $$ are equal.

This result makes no reference to the form of $L$, only that $Q=L^TL$. Hence, if there exist $L_1$ and $L_2$ such that $Q=L_1^TL_1$ and $Q=L_2^TL_2$, then the sets

$$ F_i=\bigg\{x\in\mathbb{R}^n\ \bigg|\ \left\|\begin{array}{c}(1+b^Tx+c)/2\\L_ix\end{array}\right\|_2\leqslant(1-b^Tx-c)/2\bigg\} $$

for $i=1,2$ are the same (as illustrated above), even though $L_1\neq{L_2}$.

Related Question