Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Eigenvalue Techniques for Convex Objective, Nonconvex Optimization Problems
verfasst von : Daniel Bienstock
Erschienen in: Integer Programming and Combinatorial Optimization
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A fundamental difficulty when dealing with a minimization problem given by a nonlinear, convex objective function over a nonconvex feasible region, is that even if we can efficiently optimize over the convex hull of the feasible region, the optimum will likely lie in the interior of a high dimensional face, “far away” from any feasible point, yielding weak bounds. We present theory and implementation for an approach that relies on (a) the S-lemma, a major tool in convex analysis, (b) efficient projection of quadratics to lower dimensional hyperplanes, and (c) efficient computation of combinatorial bounds for the minimum distance from a given point to the feasible set, in the case of several significant optimization problems. On very large examples, we obtain significant lower bound improvements at a small computational cost.