Journal
MATHEMATICS OF OPERATIONS RESEARCH
Volume 26, Issue 2, Pages 193-205Publisher
INFORMS
DOI: 10.1287/moor.26.2.193.10561
Keywords
second-order cone programming; linear programming; polynomial-time reducibility
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available