Ben-Tal, Aharon; Nemirovski, Arkadi On polyhedral approximations of the second-order cone. (English) Zbl 1082.90133 Math. Oper. Res. 26, No. 2, 193-205 (2001). Summary: We demonstrate that a conic quadratic problem,\[ \min_x \{e^T x \mid \text{A}x \geq b,\;||A_{\ell}x - b_{\ell}||_2 \leq c_{\ell}^T x - d_{\ell},\;\ell = 1,\dots, m\}, ||y||_2 = \sqrt{y^Ty}, \]is “polynomially reducible” to Linear Programming. We demonstrate this by constructing, for every \(\varepsilon \in (0,{1 \over 2}]\), an LP program (explicitly given in terms of \(\varepsilon\) and the data of (CQP))\[ \min_{x,u}\{e^Tx\mid P{\binom xu} +p \geq 0\} \]with the following properties: (i) the number \(\text{dim} \,x + \text{dim}\,u\) of variables and the number \(\text{dim} \,p\) of constraints in (LP) do not exceed\[ O(1)[\text{dim}\, x + \text{dim} \,b + \sum_{\ell =1}^m b_{\ell}] \ln {1\over {\varepsilon}}; \](ii) every feasible solution \(x\) to (CQP) can be extended to a feasible solution \((x, u)\) to (LP); (iii) if \((x, u)\) is feasible for (LP), then \(x\) satisfies the “\(\varepsilon\)-relaxed” constraints of (CQP), namely,\[ Ax \geq b,\;||A_{\ell}x - b_{\ell}||_2 \leq (1+ \epsilon)[c_{\ell}^T x - d_{\ell}],\;\ell = 1,\dots,m \] Cited in 8 ReviewsCited in 89 Documents MSC: 90C46 Optimality conditions and duality in mathematical programming 90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) 90C25 Convex programming Keywords:Second-order cone programming, linear programming, polynomial-time reducibility PDFBibTeX XMLCite \textit{A. Ben-Tal} and \textit{A. Nemirovski}, Math. Oper. Res. 26, No. 2, 193--205 (2001; Zbl 1082.90133) Full Text: DOI