On Polyhedral Approximations of the Second-Order Cone

We demonstrate that a conic quadratic problem,

is “polynomially reducible” to Linear Programming. We demonstrate this by constructing, for every ϵ ∈ (0, ½], an LP program (explicitly given in terms of ϵ and the data of (CQP)) with the following properties:

• the number dim x + dim u of variables and the number dim p of constraints in (LP) do not exceed

  $O\left(1\right)[dimx+dimb+\sum _{\ell =1}^{m}dim{b}_{\ell }]ln\frac{1}{ϵ};$

• every feasible solution x to (CQP) can be extended to a feasible solution (x, u) to (LP);

• if (x, u) is feasible for (LP), then x satisfies the “ϵ-relaxed” constraints of (CQP), namely,

  $\mathrm{Ax}\ge b,{\Vert A_{\ell }x-b_{\ell }\Vert }_2\le (1+ϵ)[c_{\ell }^{T}x-d_{\ell }],\ell =1,\dots ,m.$