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

 dc.contributor.advisor Schöbel, Anita Prof. Dr. dc.contributor.author Behrends, Sönke dc.date.accessioned 2017-12-05T09:55:44Z dc.date.available 2017-12-05T09:55:44Z dc.date.issued 2017-12-05 dc.identifier.uri http://hdl.handle.net/11858/00-1735-0000-0023-3F9C-9 dc.identifier.uri http://dx.doi.org/10.53846/goediss-6621 dc.language.iso eng de dc.rights.uri http://creativecommons.org/licenses/by-nc-nd/4.0/ dc.subject.ddc 510 de dc.title Geometric and algebraic approaches to mixed-integer polynomial optimization using sos programming de dc.type doctoralThesis de dc.contributor.referee Schöbel, Anita Prof. Dr. dc.date.examination 2017-10-23 dc.description.abstracteng 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 de 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. dc.contributor.coReferee Stein, Oliver Prof. Dr. dc.subject.eng Mixed-Integer Nonlinear Programming de dc.subject.eng Sos programming de dc.subject.eng Geometric approaches to MINLP de dc.subject.eng Nonlinear cutting planes de dc.subject.eng Norm bounds de dc.subject.eng Branch and bound de dc.subject.eng Coercivity de dc.subject.eng Valid linear inequalities de dc.subject.eng Real algebra de dc.identifier.urn urn:nbn:de:gbv:7-11858/00-1735-0000-0023-3F9C-9-0 dc.affiliation.institute Fakultät für Mathematik und Informatik de dc.subject.gokfull Mathematics (PPN61756535X) de dc.identifier.ppn 1007232838
﻿