Toward global robust optimization

Beckers, Markus; Naumann, Uwe

doi:urn:nbn:de:hbz:82-opus-51218

Toward global robust optimization = Zur globalen robusten Optimierung

Beckers, Markus (Author)

2014

Verantwortlichkeitsangabevorgelegt von Markus Beckers

ImpressumAachen : Publikationsserver der RWTH Aachen University 2014

Umfang145 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2014

Zsfassung in dt. und engl. Sprache

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Naumann, Uwe (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2014-02-07

Online
URN: urn:nbn:de:hbz:82-opus-51218
URL: https://publications.rwth-aachen.de/record/444988/files/5121.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Optimierung (Genormte SW) ; Globale Optimierung (Genormte SW) ; Wahrscheinlichkeitstheorie (Genormte SW) ; Nichtglatte Analysis (Genormte SW) ; Informatik (frei) ; algorithmisches Diffrentieren (frei) ; algorithmic differentiation (frei) ; global optimization (frei) ; probabiliy theory (frei) ; nonsmooth analysis (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Optimierungsprobleme in den Ingenieurwissenschaften haben oft nichtkonvexe Zielfunktionen und Nebenbedingungen und benötigen globale Optimierungsalgorithmen. Zusätzlich sollte ein gefundenes Optimimum nicht alzu sensitiv gegenüber kleinen Störungen in den Parametern sein. Das heißt das Optimum muß in gewissem Maße robust sein. Wir gehen dieses Problem mit einer Mischung aus drei wissenschaftlichen Bereichen an. Dies sind die nichtglatte Analyse von McCormick Relaxationen und Unsicherheitsanalyse unter Benutzung des Algorithmischen Differenzierens (AD). McCormick Relaxationen sind spezielle konvexe und konkave Unter- bzw. Überschätzer der Zielfunktion und Nebenbedingungen. Da konvexe Funktionen möglicherweise nichtdifferenzierbar sind, benutzen wir Subgradienten statt „gewöhnlicher” Ableitungen. Subgradienten sind deren natürliche Erweiterung die gewisse Ableitungseigenschaften für nichtdifferenzierbare Funktionen erlauben. Zu Ihrer Berechnung können Methoden des algorithmischen Differenzierens eingesetzt werden. Eine erste solche Version, unter Benutzung des tangenten-linearen Modus wurde von Kollegen am MIT Process Systems Engineering Laboratory and Department entwickelt. In dieser Arbeit wird dieser Ansatz unter Benutzung des adjungierten Modus erweitert. Die berechneten Subgradienten werden für einen branch-and-bound Algoritghmus der globalen Optimierung benötigt. Zusätzlich wird die Äquivalenz von AD und der standard Subgradientenberechnung bewiesen. Unsicherheitsanalyse hat die Aufgabe, die Unsicherheit von Ausgaben, die durch Unsicherheiten in den Eingaben eines Programms hervorgerufen werden zu quantifizieren. Für eine bekannte Wahrscheinlichkeitsverteilung der Eingaben, werden wahrscheinlichkeitstheoretische benutzt um Informationen über die Verteilung der Ausgabe zu erhalten. Unser Ansatz basiert auf Taylor-Erweiterungen der implementierten Funktion, die Approximationen des Erwartungswerts und der Varianz der Ausgabe zu erhalten. AD erlaubt deren effiziente Berechnung unter der Benutzung von höheren Ordnungsmethoden. Die Anwendung dieser Methode erlaubt es, das Ausgangsoptimierungsproblem in eine robuste Version zu transformieren, die auch Unsicherheiten berücksichtigt. Dieses neue robuste Optimierungproblem wird dann mit obigem branch-and-bound Algorithmus zur globalen Optimierung gelöst.

Optimization problems in engineering often have nonconvex objectives and constraints and require global optimization algorithms. Furthermore the achieved global optimum is supposed to be insensitive against variations of the influencing parameters, i.e. they have to be robust. We tackle this problem by a combination of three scientific areas, i.e. Nonsmooth Ananlysis of McCormick Relaxations and Uncertainty Quantification using Algorithmic Differentiation. McCormick relaxations are certain convex and concave under- and overestimators of the objective function and constraints. Since convex functions are possibly nonsmooth, subgradients are used instead of usual derivatives. Subgradients are natural extensions of usual derivatives providing similar information for nondifferentiable functions. AD like methods can be used to propagate the values of McCormick Relaxations as well as their subgradients. A first version implementing the tangent-linear mode of AD was developed by colleagues at MIT's Process Systems Engineering Laboratory and Department. This work extended this approach by an adjoint mode which provides the same advantages as usual adjoints. The subgradients, computed either in forward- or reverse-mode, are used in the context of an deterministic branch-and-bound algorithm for global optimization. Furthermore the equivalence of these methods to classical is proven. Uncertainty Quantification aims to determine the imprecision in the outputs of numerical programs caused by (measurement) errors in the inputs. For a known error distribution of the inputs, probabilistic methods are used to get information about the distribution of the outputs. Our approach is based on a Taylor Series Expansion of the function implemented by the simulation, yielding approximations of the mean and variance of the distribution of the output. AD allows the efficient computation of higher order derivatives and therewith more precise approximations. The application of this method allows to transform the given optimization problem into a robust one, also considering uncertainties in certain parameters. This adapted problem is accordingly solved by the above mentioned branch-and-bound algorithm for global optimization delivering the desired robust minimum.

Fulltext:
PDF