Detailansicht
A feasible second order bundle algorithm for nonsmooth, nonconvex optimization problems with inequality constraints and its application to certificates of infeasibility
Hannes Fendl
Art der Arbeit
Dissertation
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Betreuer*in
Hermann Schichl
DOI
10.25365/thesis.17383
URN
urn:nbn:at:at-ubw:1-29294.00720.557364-8
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Diese Arbeit erweitert den SQP-Zugang des Bundle-Newton-Verfahrens für nichtglatte, unrestringierte
Optimierungsprobleme zu einem zulässigen Bundle-Algorithmus zweiter Ordnung für nichtglatte,
nichtkonvexe Optimierungsprobleme mit Ungleichungsnebenbedingungen. An Stelle der Verwendung
einer Straffunktion oder eines Filters oder einer Improvement-Funktion zur Behandlung der Nebenbedingungen,
wird die Suchrichtung durch Lösen eines konvexen quadratischen Optimierungsproblems
mit quadratischen Nebenbedingungen bestimmt, um gute Iterationspunkte zu erhalten. Außerdem untersuchen
wir einige Varianten des Suchrichtungsproblems, wir geben eine numerische Rechtfertigung
für die Anwendbarkeit des vorgestellten Zugangs, indem wir die Effektivität von verschiedener Lösungssoftware
für die Berechnung der Suchrichtung vergleichen, und wir weisen die globale Konvergenz der
Methode unter bestimmten Voraussetzungen nach.
Weiters stellen wir eine wichtige Anwendung der nichtglatten Optimierung für Zulässigkeitsprobleme
vor: Dazu führen wir ein Unzulässigkeitszertifikat ein, welches das Auffinden von Ausschlussboxen
durch Lösen eines nichtglatten Optimierungsproblems mit linearen Nebenbedingungen ermöglicht. Zusätzlich
kann dieses Zertifikat verwendet werden, um eine Ausschlussbox durch Lösen eines nichtglatten
Optimierungsproblems mit nichtlinearen Nebenbedingungen zu vergrößern.
Schließlich besprechen wir noch die im Vergleich zu anderer Lösungssoftware guten Testergebnisse von
unserem Bundle-Algorithmus zweiter Ordnung für einige Hock-Schittkowski-Beispiele, für Beispiele die
im Zusammenhang mit der Auffindung von Ausschlussboxen in Zulässigkeitsproblemen auftreten und
für höher dimensionale stückweise quadratische Beispiele.
Abstract
(Englisch)
This thesis extends the SQP-approach of the well-known bundle-Newton method for nonsmooth unconstrained
minimization to a feasible second order bundle algorithm for nonsmooth, nonconvex optimization
problems with inequality constraints: Instead of using a penalty function or a filter or an
improvement function to deal with the presence of constraints, the search direction is determined by
solving a convex quadratically constrained quadratic program to obtain good iteration points. Moreover,
we investigate certain versions of the search direction problem, we justify the applicability of
this approach numerically by using different solvers for the computation of the search direction and
we show global convergence of the method under certain assumptions.
Furthermore, we present an important application of nonsmooth optimization to constraint satisfaction
problems: We introduce a certificate of infeasibility for finding exclusion boxes by solving a linearly
constrained nonsmooth optimization problem. Additionally, the constructed certificate can be used to
enlarge an exclusion box by solving a nonlinearly constrained nonsmooth optimization problem.
Finally, the good performance of the second order bundle algorithm is demonstrated by comparison
with test results of other solvers on examples of the Hock-Schittkowski collection, on custom examples
that arise in the context of finding exclusion boxes for constraint satisfaction problems, and on higher
dimensional piecewise quadratic examples.
Schlagwörter
Schlagwörter
(Englisch)
nonsmooth optimization bundle algorithm certificate of infeasibility
Schlagwörter
(Deutsch)
Nichtglatte Optimierung Bundle-Algorithmus Unzulässigkeitszertifikat
Autor*innen
Hannes Fendl
Haupttitel (Englisch)
A feasible second order bundle algorithm for nonsmooth, nonconvex optimization problems with inequality constraints and its application to certificates of infeasibility
Paralleltitel (Deutsch)
Ein zulässiger Bundle-Algorithmus zweiter Ordnung für nichtglattte, nichtkonvexe Optimierungsprobleme mit Ungleichungsnebenbedingungen und dessen Anwendung auf Unzulässigkeitszertifikate
Publikationsjahr
2011
Umfangsangabe
IX, 237 S. : graph. Darst.
Sprache
Englisch
Beurteiler*innen
Marko Mäkelä ,
Arnold Neumaier
Klassifikationen
31 Mathematik > 31.76 Numerische Mathematik ,
31 Mathematik > 31.80 Angewandte Mathematik
AC Nummer
AC08877748
Utheses ID
15580
Studienkennzahl
UA | 091 | 405 | |