Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1026.90065
Ben-Tal, A.; Nemirovski, A.; Roos, C.
Robust solutions of uncertain quadratic and conic-quadratic problems. (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:: *90C20 Quadratic programming
90C08 Special problems of linear programming

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

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]