On Polyhedral Approximations of the Second-Order Cone

Abstract

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]