Journal
SIAM JOURNAL ON OPTIMIZATION
Volume 13, Issue 2, Pages 535-560Publisher
SIAM PUBLICATIONS
DOI: 10.1137/S1052623401392354
Keywords
semidefinite relaxation of NP-hard problems; (conic) quadratic programming; robust optimization
Categories
Ask authors/readers for more resources
We consider a conic-quadratic (and in particular a quadratically constrained) optimization problem with uncertain data, known only to reside in some uncertainty set U. The robust counterpart of such a problem leads usually to an NP-hard semidefinite problem; this is the case, for example, when U is given as the intersection of ellipsoids or as an n-dimensional box. For these cases we build a single, explicit semidefinite program, which approximates the NP-hard robust counterpart, and we derive an estimate on the quality of the approximation, which is essentially independent of the dimensions of the underlying conic-quadratic problem.
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