 |
|
||||||||||
Generalized Newton-type methods for nonsmooth equations
IFOR Events
Seminar:
'Optimization & Applications'
(see information & program)
Feb 20 - May 28, 2012
IFOR Mitteilungen
This booklet informs about ongoing projects and future events at the IFOR and appears once at the end of the year.
| Author | Stephan Bütikofer |
| Abstract |
Several problems in variational analysis for e.g. necessary optimality conditions for nonlinear programs, solutions of variational inequalities with explicit equality/inequality constraints and nonlinear complementarity problems, can be analyzed and solved by reformulating the original problem as an equation or generalized equation (inclusion). However, even if the original problem is completely described by smooth functions, nonsmoothness of the resulting equation may appear in a very natural way. This requires methods, which may handle nonsmoothness. The focus of this work is on equations defined by locally Lipschitz functions having a special structure, the so called generalized Kojima functions. This structure is suitable to describe and compute standard generalized (directional) derivatives and to develop generalized Newton-type methods (so called nonsmooth Newton methods) for solving the related Lipschitz equation. This work is divided in three parts: The identification of a suited local nonsmooth Newton method, the globalization of this method and the application and numerical testing of the globalized method. In a first part we review the class of generalized Kojima functions and different generalized derivatives. We compute these generalized derivatives for generalized Kojima functions and obtain exact formulas, especially for our main application class resulting from nonlinear programs with data, which are not twice differentiable, but differentiable with locally Lipschitzian derivative. We consider a local nonsmooth Newton method introduced by Bernd Kummer, which can handle different generalized derivatives and allows inexact solutions of the Newton equation. We work out the abstract convergence conditions from this method for generalized Kojima functions. In a second part a globalization of this local method by a path search with non-monotone backtracking is described in a rather general framework. We discuss and analyze the causes for a possible premature termination. Under the assumptions of feasibility we give a global convergence theorem. We show that the globalized method inherits the convergence properties from the local Newton method. We also present a modification of the globalized method, which enables the integration of a suited first order method. A third part is devoted to the applications and numerical testing of the globalized method. We specify the single steps of our method for finite dimensional optimization problems and complementarity problems. The numerical results on a set of test problems from (generalized) semi-infinite optimization and nonlinear complementarity problems are very satisfying. They confirm the theoretical convergence results derived in the second part. |
| Download |
Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne
graphische Elemente dargestellt. Die Funktionalität der
Website ist aber trotzdem gewährleistet. Wenn Sie diese
Website regelmässig benutzen, empfehlen wir Ihnen, auf
Ihrem Computer einen aktuellen Browser zu installieren. Weitere
Informationen finden Sie auf
folgender
Seite.
Important Note:
The content in this site is accessible to any browser or
Internet device, however, some graphics will display correctly
only in the newer versions of Netscape. To get the most out of
our site we suggest you upgrade to a newer browser.
More
information
