Rewriting sum of norms as a SOC constraint

Question

I'm trying to compute the complexity of the following convex problem: \begin{align} \underset{y}{\mathop{\text{minimize} }} \quad & v^Ty \\ \text{s}\text{.t}\text{.} \quad\quad\quad\,\,& \left\| {Ay - a} \right\| + \left\| {Ay - b} \right\| \le {c^T}y, \\ & \ldots \end{align} where the remaining constraints are all affine. To accomplish this task, I have tried to find the equivalent SOCP of the given problem since in convex optimization related references, the worst-case arithmetic complexity of SOCP's and SDP's have already been calculated. The problem is that the constraint $\left\| {Ay - a} \right\| + \left\| {Ay - b} \right\| \le {c^T}y$, although convex, does not have the form of a SOC constraint. My question is can this constraint be somehow converted to a SOC constraint(s) or is there a SOCP equivalent to the original problem?

Answer 1

Introduce auxiliary variables $f, g$

Then replace

$\|Ay - a\| + \|Ay - ab\| \le c^Ty$

with the new SOC formulation

+++++++++++++++

$\|Ay - a\| \le f$

$\|Ay - b\| \le g$

$f + g \le c^Ty$

++++++++++++++++

Note that the linear constraint is considered to be consistent with an SOCP.

To show equivalence:

1) Assume the original constraint is satisfied. By choosing $f = \|Ay - a\|$ and $g = \|Ay - b\|$, the SOC formulation constraints are all satisfied

2) Conversely, assume all the SOC formulation constraints are satisfied, then clearly $\|Ay - a\| + \|Ay - ab\| \le c^Ty$ is satisfied as well.