Options
A rigorous lower bound for the optimal value of convex optimization problems
Publikationstyp
Journal Article
Date Issued
2004-01
Sprache
English
Author(s)
Institut
TORE-URI
Journal
Volume
28
Issue
1
Start Page
121
End Page
137
Citation
Journal of Global Optimization 28 (1): 121-137 (2004)
Publisher DOI
Scopus ID
Publisher
Kluwer
In this paper, we consider the computation of a rigorous lower error bound for the optimal value of convex optimization problems. A discussion of large-scale problems, degenerate problems, and quadratic programming problems is included. It is allowed that parameters, which define the convex constraints and the convex objective functions, may be uncertain and may vary between given lower and upper bounds. The error bound is verified for the family of convex optimization problems which correspond to these uncertainties. It can be used to perform a rigorous sensitivity analysis in convex programming, provided the width of the uncertainties is not too large. Branch and bound algorithms can be made reliable by using such rigorous lower bounds.
Subjects
Convex programming
Convex relaxations
Global optimization
Interval arithmetic
Large-scale problems
Quadratic programming
Rigorous error bounds
Sensitivity analysis
DDC Class
510: Mathematik