Show simple item record

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

dc.contributor.advisorSchöbel, Anita Prof. Dr.
dc.contributor.authorBehrends, Sönke
dc.titleGeometric and algebraic approaches to mixed-integer polynomial optimization using sos programmingde
dc.contributor.refereeSchöbel, Anita Prof. Dr.
dc.description.abstractengWe 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
dc.contributor.coRefereeStein, Oliver Prof. Dr.
dc.subject.engMixed-Integer Nonlinear Programmingde
dc.subject.engSos programmingde
dc.subject.engGeometric approaches to MINLPde
dc.subject.engNonlinear cutting planesde
dc.subject.engNorm boundsde
dc.subject.engBranch and boundde
dc.subject.engValid linear inequalitiesde
dc.subject.engReal algebrade
dc.affiliation.instituteFakultät für Mathematik und Informatikde
dc.subject.gokfullMathematics (PPN61756535X)de

Files in this item


This item appears in the following Collection(s)

Show simple item record