##
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**