SOCP with a norm constraint

Question

Is it possible to convert this optimization problem into a SOCP:

\begin{eqnarray} \min && c^T x \\ s.t. && \|A_ix + b_i \|_2 \le c_i^T x + d_i \\ && \| Dx \|_2 = g \end{eqnarray}

where $D$ is diagonal. The first constraint is the classic SOCP constraint, but I am not sure whether the second constraint can be converted into a SOCP constraint.

Answer 1

This problem is not convex and therefore cannot be represented as an SOCP. However, it is possible to appriximate it using the convex-concave procedure, as described here. To summarize, you replace your constraint $||Dx||_2 = g$ by two constraints:

1. $||Dx|| \le g$, which is convex
2. $||Dx|| \ge g$, which is nonconvex

You solve a sequence of SOCP problems, where in each one you replace the constraint (2) by an approximation based on the result from the previous iteration. The approximation is: $$q^T(Dx) \ge g$$ where $$q = \frac{(D x^{\text{prev}})}{||D x^{\text{prev}}||_2}$$ You can see that the approximation is linear (and therefore convex) and as the difference between $x$ and $x^\text{prev}$ decreases, the approximation gets closer and closer to approximating the original constraint.

Note, that this method does not find the global solution. It is just a heuristic.