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 \]

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: DOI