Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 1026.90065
Ben-Tal, A.; Nemirovski, A.; Roos, C.
(English)
[J] SIAM J. Optim. 13, No.2, 535-560 (2002). ISSN 1052-6234; ISSN 1095-7189/e

Summary: We consider a conic-quadratic (and in particular a quadratically constrained) optimization problem with uncertain data, known only to reside in some uncertainty set ${\cal U}$. The robust counterpart of such a problem leads usually to an NP-hard semidefinite problem; this is the case, for example, when ${\cal 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.
MSC 2000:
90C08 Special problems of linear programming

Keywords: semidefinite relaxation of NP-hard problems; (conic) quadratic programming; robust optimization

Highlights
Master Server