Generating Valid Linear Inequalities for Nonlinear Programs via Sums of Squares
2020 | journal article. A publication with affiliation to the University of Göttingen.
Jump to: Cite & Linked | Documents & Media | Details | Version history
Documents & Media
Details
- Authors
- Behrends, Sönke; Schöbel, Anita
- Abstract
- Valid linear inequalities are substantial in linear and convex mixed-integer programming. This article deals with the computation of valid linear inequalities for nonlinear programs. Given a point in the feasible set, we consider the task of computing a tight valid inequality. We reformulate this geometrically as the problem of finding a hyperplane which minimizes the distance to the given point. A characterization of the existence of optimal solutions is given. If the constraints are given by polynomial functions, we show that it is possible to approximate the minimal distance by solving a hierarchy of sum of squares programs. Furthermore, using a result from real algebraic geometry, we show that the hierarchy converges if the relaxed feasible set is bounded. We have implemented our approach, showing that our ideas work in practice.
- Issue Date
- 2020
- Journal
- Journal of Optimization Theory and Applications
- Project
- RTG 2088: Research Training Group 2088 Discovering structure in complex data: Statistics meets Optimization and Inverse Problems
- ISSN
- 0022-3239
- eISSN
- 1573-2878
- Language
- English
- Sponsor
- DFG