Levenberg-Marquardt algorithms for nonlinear equations, multi-objective optimization, and complementarity problems [Elektronische Ressource] / von Shukla, Pradyumn Kumar

Sujets

• Mathematics

Informations

• Publié par: technische_universitat_dresden
• Publié le: 01 janvier 2010
• Nombre de lectures: 25
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Levenberg-Marquardt Algorithms for
Nonlinear Equations, Multi-objective
Optimization, and Complementarity
Problems
DISSERTATAION
zur Erlangung des akademischen Grades
Doctor rerum naturalium
(Dr. rer. nat.)
vorgelegt
der Fakult¨at Mathematik und Naturwissenschaften
der Technischen Universit¨at Dresden
von
M.Tech., Shukla, Pradyumn Kumar
geboren am 04.03.1981 in Gonda (Indien)
Gutachter Prof. Dr. Matthias Ehrgott
Prof. Dr. Andreas Fischer
Eingereicht am: 10.12.2009
Tag der Disputation: 25.02.2010Acknowledgements
First and foremost I would like to thank Prof. Andreas Fischer for
introducing me to this subject and guiding me throught the course of
my PhD. He has been a very attentive supervisor and I learned a lot
during long discussions with him. It has been a long journey for me
from correctly writing the Levenberg-Marquardt subproblem for the
first time till writing the thesis in its final shape. I would also like to
thank Prof. Matthias Ehrgott for taking his time to review my PhD
thesis and give valuable comments.
The financial support from the Daimler Benz foundation is gratefully
acknowledged.
I would also like to thank my friends and colleagues who made my
stay atDresden amemorable one. They were always there forme and
I will never forget the the nice time I had with them.
Finally, I would never have made this thesis to the end without the
loving and caring support of my wife Irina and my daughter Priya.Abstract
The Levenberg-Marquardt algorithm is a classical method for solving
nonlinear systems of equations that can come from various
applications in engineering and economics.
Recently, Levenberg-Marquardt methods turned out to be a valuable
principle for obtaining fast convergence to a solution of the
nonlinear system if the classical nonsingularity assumption is replaced by a
weaker error bound condition. In this way also problems with
nonisolatedsolutionscanbetreatedsuccessfully. Suchproblemsincreasingly
arise in engineering applications and in mathematical programming.
In this thesis we use Levenberg-Marquardt algorithms to deal with
nonlinear equations, multi-objective optimization and
complementarity problems. We develop new algorithms for solving these problems
and investigate their convergence
properties.
ForsufficientlysmoothnonlinearequationsweprovideconvergenceresultsforinexactLevenberg-Marquardttypealgorithms. Inparticular,
asharpboundonthemaximallevelofinexactness thatissufficientfor
a quadratic (or a superlinear) rate of convergence is derived.
Moreover, the theory developed is used to show quadratic convergence of
a robust projected Levenberg-Marquardt algorithm.
The use of Levenberg-Marquardt type algorithms for unconstrained
multi-objectiveoptimizationproblemsisinvestigatedindetail.
Inparticular, two globally and locally quadratically convergent algorithms
fortheseproblemsaredeveloped. Moreover,assumptionsunderwhich
the error bound condition for a Pareto-critical system is fulfilled are
derived.
We also treat nonsmooth equations arising from reformulating
complementarityproblemsbymeansofNCPfunctions.
Forthesereformulations, we show that existing smoothness conditions are not satisfied
atdegeneratesolutions. Moreover, wederivenewresultsforpositively
homogeneous functions. The latter results are used to show that
appropriateweaker smoothness conditions(enablingalocalQ-quadratic
rate of convergence) hold for certain reformulations.Zusammenfassung
Der Levenberg-Marquardt-Algorithmus ist ein klassisches Verfahren
zur L¨osung nichtlinearer Gleichungssysteme. Diese findet man u.a. in
vielen Anwendungen der Ingenieur-und Wirtschaftswissenschaften.
Ku¨rzlich erwiesen sich Levenberg-Marquardt-Methoden als wichtiges
Prinzip zur Erreichung schneller Konvergenz gegen eine L¨osung des
nichtlinearen Systems, wenn die klassische Regularit¨atsbedingung
durcheineschw¨achereFehlerschrankeersetztwird. Solassensichauch
Probleme mit nicht isolierten Lo¨sungen erfolgreich behandeln. Solche
Probleme treten zunehmend in ingenieurwissenschaftlichen
Anwendungen und in der mathematischen Optimierung auf.
In dieser Arbeit werden Levenberg-Marquardt-Methoden fu¨r
nichtlineare Gleichungen, multikriterielle Optimierung und
Komplementarita¨tsprobleme verwendet. Neue Algorithmen werden entwickelt
und ihre Konvergenzeigenschaften untersucht.
Fu¨r nichtlineare Gleichungssysteme mit hinreichend glatten
FunktionenwerdenKonvergenzergebnisse
fu¨rinexakteLevenberg-MarquardtAlgorithmengezeigt. Insbesonderewirdeineverbessertescharfeobere
Schranke fu¨rdas Maß der Inexaktheit hergeleitet, die noch
quadratische (oder superlineare) Konvergenz erlaubt. Außerdem wird die
entwickelte Theorie benutzt, um die quadratische Konvergenz eines
robusten projizierten Levenberg- Marquardt-Algorithmus zu
zeigen.
DieVerwendungvonLevenberg-Marquardt-Algorithmenfu¨runrestringierte multikriterielle Optimierungsprobleme wird im Detail
untersucht. Insbesondere wurdenzweiglobalundlokalquadratisch
konvergenteAlgorithmenfu¨rdieseOptimierungsproblemeentwickelt.
AußerdemkonntenBedingungenhergeleitetwerden,
unterdenendieFehlerschranke fu¨r ein Pareto-kritisches System gilt.
Die Arbeit behandelt auch nichtglatte Gleichungssysteme, die aus
der Umformulierung von Komplementarit¨atsproblemen durch
NCPFunktionen entstehen. Dafu¨r wird gezeigt, dass u¨bliche
Glattheitsvoraussetzungen im Falle degenerierter L¨osungen nicht erfu¨llt sind.
Außerdem werden neue Ergebnisse fu¨r positiv homogene Funktionen
hergeleitet. Diese Ergebnisse werden verwendet um zu zeigen, dass
fu¨r einige Umformulierungen bestimmte (fu¨r die lokal schnelle
Konvergenz ausreichende) schw¨achere Glattheitsvoraussetzungen gelten.Contents
1 Introduction 1
1.1 Overview. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Problems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Algorithmic Principles and Preliminaries . . . . . . . . . . . . . . 5
2 Robust Levenberg-Marquardt Algorithms for Nonlinear
Equations 7
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Local Convergence Analysis . . . . . . . . . . . . . . . . . . . . . 10
2.3 A Projected Robust Levenberg-Marquardt Algorithm . . . . . . . 18
2.4 Computational Results . . . . . . . . . . . . . . . . . . . . . . . . 21
2.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3
ALevenberg-MarquardtAlgorithmforMulti-objectiveOptimization 25
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Existence of a Local Error bound . . . . . . . . . . . . . . . . . . 27
3.3 Convergence of a Constrained Levenberg-Marquardt Method . . . 29
3.4 Results under Convexity Assumptions . . . . . . . . . . . . . . . . 32
3.5 Computational Results . . . . . . . . . . . . . . . . . . . . . . . . 33
3.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4 A Simultaneous Descent Levenberg-Marquardt Algorithm for
Multi-objective Optimization 37
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 The Levenberg-Marquardt Algorithm with Simultaneous Descent 38
4.3 Convergence of Algorithm 4.1 . . . . . . . . . . . . . . . . . . . . 46
4.4 A Duality Based Method for Solving (P(z)) . . . . . . . . . . . . 58
4.5 Results under Convexity/ Non-singularity Assumptions . . . . . . 63
4.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
viiiCONTENTS
5 Levenberg-Marquardt Algorithms for Nonlinear
Complementarity Problems 80
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.3 Existing Smoothness Assumption . . . . . . . . . . . . . . . . . . 93
5.4 Fundamental Identities for Nonsmooth Homogeneous Functions . 100
5.5 New Smoothness Assumption . . . . . . . . . . . . . . . . . . . . 104
5.5.1 Discussion of Condition 5.5.1 . . . . . . . . . . . . . . . . 106
5.5.2 Discussion of Condition 5.5.2 . . . . . . . . . . . . . . . . 126
6 Conclusions and Outlook 135
6.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
6.2 Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
References 145
ix