On polyhedral approximations of the second-order cone

• 成果类型: Article
• 署名作者: Ben-Tal, A; Nemirovski, A
• 署名单位: Technion Israel Institute of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.26.2.193.10561
• 发表日期: 2001
• 页码: 193-205
• 关键词: interior-point methods

摘要

We demonstrate that a conic quadratic problem. (CQP) [GRAPHICS] is polynomially reducible to Linear Programming. We demonstrate this by constructing, for every epsilon is an element of (0, 1/2], an LP program (explicitly given in terms of epsilon and the data of (CQP)) (LP) [GRAPHICS] with the following properties: (i) the number dim x + dim u of variables and the number dim p of constraints in (LP) do not exceed [GRAPHICS] (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 epsilon -relaxed constraints of (CQP), namely, Ax greater than or equal to b, parallel toA(l)x - b(l)parallel to (2) less than or equal to (1 + epsilon)[c(l)(t)x - d(l)], l = 1.....m.