On polyhedral approximations of the second-order cone

We demonstrate that a conic quadratic problem. (CQP) [GRAPHICS] is "polynomially reducible" to Linear Programming. We demonstrate this by constructing, for every epsilon is an element of (0, 1/2], an LP program (explicitly given in terms of epsilon and the data of (CQP)) (LP) [GRAPHICS] with the following properties: (i) the number dim x + dim u of variables and the number dim p of constrain ts in (LP) do not exceed [GRAPHICS] (ii) every Feasible solution x to (CQP) can be extended to a feasible solut ion (x, u) to (LP); (iii) if (x, u) is feasible for (LP), then x satisfies the "epsilon -relaxe d" constraints of (CQP), namely, Ax greater than or equal to b, parallel toA(l)x - b(l)parallel to (2) less than or equal to (1 + epsilon)[c(l)(t)x - d(l)], l = 1.....m.