# zbMATH — the first resource for mathematics

On polyhedral approximations of the second-order cone. (English) Zbl 1082.90133
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$

##### 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
Full Text: