Generating Valid Linear Inequalities for Nonlinear Programs via Sums of Squares

Sönke Behrends () and Anita Schöbel
Additional contact information
Sönke Behrends: University of Goettingen
Anita Schöbel: University of Kaiserslautern and Fraunhofer Institute for Industrial Mathematics ITWM

Journal of Optimization Theory and Applications, 2020, vol. 186, issue 3, No 10, 935 pages

Abstract: 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.

Keywords: Valid inequalities; Nonlinear optimization; Polynomial optimization; Semi-infinite programming; Sum of squares (sos); Hyperplane location; 90C30; 90C11; 90C10; 14P10 (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-020-01736-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:186:y:2020:i:3:d:10.1007_s10957-020-01736-4

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-020-01736-4

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().