On polyhedral approximations of the second-order cone

We demonstrate that a conic quadratic problem, (CQP) minx{e^Tx|Ax ≥ b, ‖ A𝓁 x − b𝓁 ‖2 ≤ c𝓁^Tx − d𝓁, 𝓁 = 1,...,m}, ‖y‖2 = √(y^Ty), is ‘polynomially reducible’ to Linear Programming. We demonstrate this by constructing, for every ε ∈ (0,1/2], an LP program (explicitly given in terms of ε and the data of (CQP)) (LP) minx, u {e^Tx | P (u^x) + p ≥ 0} with the following properties: (i) the number dim x + dim u of variables and the number dim p of constraints in (LP) do not exceed O(1)[dim x + dim b + Σ𝓁=1^m dim b𝓁] ln 1/ε; (ii) every feasible solution x to (CQP) can be extended to a feasible solution (x, u) to (LP); (iii) if (x, u) is feasible for (LP), then x satisfies the ‘ε-relaxed’ constraints of (CQP), namely, Ax ≥ b, ‖A𝓁x − b𝓁‖2 ≤ (1 + ε)[c𝓁^Tx − d𝓁], 𝓁 = 1,...,m.