Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Generating Valid Linear Inequalities for Nonlinear Programs via Sums of Squares

: Behrends, S.; Schöbel, A.

Volltext ()

Journal of optimization theory and applications 186 (2020), Nr.3, S.911-935
ISSN: 0022-3239
ISSN: 1573-2878
Zeitschriftenaufsatz, Elektronische Publikation
Fraunhofer ITWM ()

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.