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

Behrends, Sönke

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 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.	de
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

Dateien

Name:dissertation.pdf

Größe:1.165Mb

Format:PDF

Öffnen

Name:: dissertation.pdf
Größe:: 1.165Mb
Format:: PDF

Öffnen

Das Dokument erscheint in:

Fakultät für Mathematik und Informatik (inkl. GAUSS) [518]

Zur Kurzanzeige