Detailansicht
Analysis of several derivative-free methods for local optimization
Stefan Scheer
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Mathematik
Betreuer*in
Hermann Schichl
DOI
10.25365/thesis.70178
URN
urn:nbn:at:at-ubw:1-11175.49803.374515-4
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
In dieser Arbeit untersuchen wir insgesamt fünf Algorithmen zur unbeschränkten lokalen Optimierung. Probleme, bei denen die Zielfunktion das Normquadrat einer vektorwertigen Funktion ist, kommen sehr häufig in Anwendungen wie zum Beispiel der Datenanpassung und der Regressionsanalyse vor. Wir beschreiben zwei
der populärsten Löser für diese Probleme, das Gauß-Newton-Verfahren und den Levenberg-Marquardt-Algorithmus. Diese Methoden profitieren von der speziellen Struktur der Hesse-Matrix solcher Zielfunktionen, die es ihnen erlaubt die aufwendige Berechnung von Ableitungen zweiter Ordnung zu unterlassen. Dennoch kann es sehr herausfordernd oder numerisch teuer sein, die erforderliche Jacobi-Matrix in jedem iterativen Schritt des jeweiligen Verfahrens zu erhalten. Daher analysieren wir drei ableitungsfreie Methoden, die stattdessen verwendet werden können. Die Finite-Differenzen-Analoga des Gauß-Newton-Verfahrens und des Levenberg-Marquardt-Algorithmus von Brown und Dennis verwenden Vorwärts-Differenzenquotienten als Approximation der Jacobi-Matrizen. Wir beweisen die lokale Konvergenz der Methoden und zeigen, dass für Funktionen, deren Wert am Minimum Null ist, quadratische Konvergenz garantiert werden kann. Der DUD-Algorithmus von Ralston und Jennrich ist ein Sekantenverfahren, das Funktionsauswertungen effizient nutzt. Wie bei den anderen vorgestellten Algorithmen muss in jeder Iteration ein lineares Kleinste-Quadrate-Problem gelöst werden. Aber anstelle der Methode der
Normalengleichungen verwendet DUD ein Verfahren zur schrittweisen Regression, welches auf dem Gauß-Jordan-Algorithmus basiert. Das optionale Liniensuchverfahren von DUD erhöht zwar nicht die algorithmische Zuverlässigkeit, kann aber aktiviert werden, um alternative Lösungspfade zu ermöglichen.
Ergebnisse von Computerexperimenten zeigen, wie sich die angeführten Methoden in Bezug auf Effizienz und Zuverlässigkeit unterscheiden. Wir kommen zum Schluss, dass unsere ableitungsfreien Optimierungsverfahren zur Lösung niedrigdimensionaler
Probleme mit mittlerer relativer Genauigkeit meist besser geeignet sind als die beiden etablierten Gradientenmethoden.
Abstract
(Englisch)
In this thesis, we examine a total of five algorithms for unconstrained local optimization. Problems where the objective function is in the nonlinear least squares sense are very common in applications such as data fitting and regression analysis. The presented Gauss-Newton and Levenberg-Marquardt algorithms are among the most popular solvers for these problems. They benefit from the special structure of the Hessian matrix of such objective functions, which allows them to omit the costly computation of second-order derivatives. However, it can still be very challenging or numerically expensive to obtain the required Jacobian matrix in each iterative step of the respective procedure. Therefore, we analyze three derivative-free methods which may be used instead. The finite difference analogues of the Gauss-Newton and
Levenberg-Marquardt algorithms by Brown and Dennis use forward differences to approximate the Jacobians. We prove local convergence of the methods and show that quadratic convergence can be guaranteed for functions that are zero at the minimum. The DUD algorithm by Ralston and Jennrich is a secant method that makes efficient use of function evaluations. As with the other depicted procedures, a linear least square problem has to be solved in each iteration. But instead of invoking a method for normal equations, DUD employs a stepwise regression procedure that is based on the Gauss-Jordan algorithm. DUD’s optional line search does not increase the
algorithmic reliability, but can be activated to enable alternative solution paths.
The results of computer experiments show how the mentioned methods differ in terms of efficiency and reliability. We conclude that our derivative-free optimization algorithms are mostly superior to the two established gradient methods when it comes to solving low-dimensional problems with medium relative accuracy.
Schlagwörter
Schlagwörter
(Englisch)
Derivative-Free Optimization Nonlinear Optimization Local Optimization Unconstrained Optimization Least Squares Problems Gauss-Newton Method Levenberg-Marquardt Algorithm Finite-Difference Analogues DUD Gauss-Jordan Algorithm Stepwise Regression
Schlagwörter
(Deutsch)
Ableitungsfreie Optimierung Nichtlineare Optimierung Lokale Optimierung Uneingeschränkte Optimierung Methode der Kleinsten Quadrate Gauß-Newton Methode Levenberg-Marquardt Algorithmus Finite-Differenzen-Analoga DUD Gauß-Jordan Algorithmus Schrittweise Regression
Autor*innen
Stefan Scheer
Haupttitel (Englisch)
Analysis of several derivative-free methods for local optimization
Paralleltitel (Deutsch)
Analyse mehrerer ableitungsfreier Methoden zur lokalen Optimierung
Publikationsjahr
2021
Umfangsangabe
IX, 178 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*in
Hermann Schichl
AC Nummer
AC16463921
Utheses ID
60091
Studienkennzahl
UA | 066 | 821 | |