期刊
MATHEMATICS OF OPERATIONS RESEARCH
卷 26, 期 2, 页码 193-205出版社
INFORMS
DOI: 10.1287/moor.26.2.193.10561
关键词
second-order cone programming; linear programming; polynomial-time reducibility
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据