Geometric and algebraic approaches to mixed-integer polynomial optimization using sos programming

von Sönke Behrends
Dissertation
Datum der mündl. Prüfung:2017-10-23
Erschienen:2017-12-05
Betreuer:Prof. Dr. Anita Schöbel
Gutachter:Prof. Dr. Anita Schöbel
Gutachter:Prof. Dr. Oliver Stein
Zum Verlinken/Zitieren: http://dx.doi.org/10.53846/goediss-6621

 

 

Dateien

Name:dissertation.pdf
Size:1.16Mb
Format:PDF

Lizenzbestimmungen:

Zusammenfassung

Englisch

We consider geometric approaches that assist in the solution process of mixed-integer nonlinear programming (MINLP). Amongst others, we compute half-spaces, seminorm balls and ellipsoids that contain the relaxed feasible set. We also compute norm balls that contain all optimal solutions, which is formalized in the concept of norm bounds. We then investigate how integrality arguments can be used to shrink these sets and potentially cut off continuously feasible points. The norm and seminorm balls as well as the ellipsoids make the integer part of the problem (given some assumptions) accessible to branch and bound. For the branch and bound part, we also propose a class of underestimators that yield tight lower bounds. The approaches always involve the task to optimally choose a geometric object out of a whole class of similar geometric objects – for example, to choose an ellipsoid of minimal volume containing the relaxed feasible set out of the collection of all axis-parallel ellipsoids. For polynomial objective and constraint functions, these auxiliary problems, or approximations thereof, become tractable by using sum of squares programming and tools from real algebra. These auxiliary problems can then be implemented and assist in the solution process of a given problem. We also present results that guarantee that the approximate solutions converge eventually to the optimal solution of the auxiliary problem. A subset of the approaches has been implemented and we demonstrate that they work in computer experiments.
Keywords: Mixed-Integer Nonlinear Programming; Sos programming; Geometric approaches to MINLP; Nonlinear cutting planes; Norm bounds; Branch and bound; Coercivity; Valid linear inequalities; Real algebra
 
Statistik