Generating Valid Linear Inequalities for Nonlinear Programs via Sums of Squares

Behrends S, Schoebel A (2020)

Publication Type: Journal article

Publication year: 2020

Journal

Journal of Optimization Theory and Applications Springer Verlag (Germany)

Book Volume: 186

Pages Range: 911-935

Journal Issue: 3

DOI: 10.1007/s10957-020-01736-4

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.

Involved external institutions

Georg-August-Universität Göttingen DE Germany (DE) Technische Universität Kaiserslautern DE Germany (DE)

How to cite

APA:

Behrends, S., & Schoebel, A. (2020). Generating Valid Linear Inequalities for Nonlinear Programs via Sums of Squares. Journal of Optimization Theory and Applications, 186(3), 911-935. https://dx.doi.org/10.1007/s10957-020-01736-4

MLA:

Behrends, Soenke, and Anita Schoebel. "Generating Valid Linear Inequalities for Nonlinear Programs via Sums of Squares." Journal of Optimization Theory and Applications 186.3 (2020): 911-935.

BibTeX: Download