On Polyhedral Approximations of the Second-Order Cone

We demonstrate that a conic quadratic problem, Formula: see text 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)) Formula: see text with the following properties: the number dim x + dim u of variables and the number dim p of constraints in (LP) do not exceed Formula: see text 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, Formula: see text