On polyhedral approximations of the second-order cone

Aharon Ben-Tal and Arkadi Nemirovski

We demonstrate that a conic quadratic program $$ e^T x \to \min s.t. Ax \geq b, \| A_\ell x - b_\ell \|_2 \leq c_\ell^T x - d_\ell, \ell = 1,...,m (CQP) $$ \| \cdot \|_2 being the standard Euclidean norm, is ``polynomially reducible'' to LP: for every $\epsilon \in (0,{1\over 2}]$ there exists an LP program $$ e^T x \to \min s.t. P(x,u) \geq 0 (LP) $$ with the number of variables and constraints not exceeding $$ O(1) [dim(x) + rdim(A) + \sum_{\ell=1}^m rdim(A_\ell)] \times \ln(1/\epsilon) $$ ($rdim(B)$ is the number of rows of a matrix $B$) such that every feasible solution of (CQP) can be extended to a feasible solution of (LP), and the $x$-component of every feasible solution $(x,u)$ of (LP) satisfies the ``$\epsilon$-relaxed'' constraints of (CQP), namely, $$ Ax \geq b, \|A_\ell x - b_\ell \|_2 \leq (1+\epsilon) \times [c_\ell^T x - d_\ell], \ell=1,...,m. $$ The data of (LP) are readily given by the data of (CQP).

Research Report #3/98, Optimization Laboratory, Faculty of Indistrial Angineering and Management, Technion -- Israel Institute of Technology, Technion City, Haifa 32000, Israel

Contact: nemirovs@ie.technion.ac.il

Link to postscript file broken; contact author