Generating Valid Linear Inequalities for Nonlinear Programs via Sums of Squares
- PDF / 628,017 Bytes
- 25 Pages / 439.37 x 666.142 pts Page_size
- 92 Downloads / 170 Views
Generating Valid Linear Inequalities for Nonlinear Programs via Sums of Squares Sönke Behrends1 · Anita Schöbel2 Received: 26 January 2020 / Accepted: 30 July 2020 / Published online: 12 August 2020 © The Author(s) 2020
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 Mathematics Subject Classification 90C30 · 90C11 · 90C10 · 14P10
1 Introduction The problem we want to solve is the following: Given a subset S of Rn and a point q in S, find a valid linear inequality for S which is as close as possible to q (a formal definition is given in Sect. 2). Our motivation stems from the fact that valid linear inequalities play an important role in solving mixed-integer linear and mixed-integer convex programs. It is thus a natural task to study valid inequalities for the more general class of mixed-integer nonlinear programs (MINLP). More specifically, we search for
B
Sönke Behrends [email protected]
1
University of Goettingen, Goettingen, Germany
2
University of Kaiserslautern and Fraunhofer Institute for Industrial Mathematics ITWM, Kaiserslautern, Germany
123
912
Journal of Optimization Theory and Applications (2020) 186:911–935
valid inequalities for the feasible set FI and its continuous relaxation F. We also consider the special case where we require the objective and constraint functions to be polynomials, which we refer to as mixed-integer polynomial programming (MIPP). To avoid unnecessary clutter, we state our results for the set S which can be thought of being equal to F or FI . In mixed-integer linear and convex programming, one is interested in finding valid inequalities for FI . One reason for this interest is that the convex hull of FI can be described by finitely many valid inequalities for rational data in the mixed-integer linear case [1]. This result does not generalize to the convex case; however, in mixedinteger convex programming, a common solution approach is the generation of cuts. A cut is a valid linear inequality for the feasible set that is violated at some point of the relaxed feasible set. A second motivation to find valid linear
Data Loading...
