Authors:	Hans, Esther
Title:	Globally convergent B-semismooth Newton methods for l1-Tikhonov regularization
Online publication date:	10-May-2017
Year of first publication:	2017
Language:	english
Abstract:	We are concerned with the globalization of a semismooth Newton method for l1-Tikhonov regularization. This regularization strategy for inverse problems with sparsity constraints leads to a nonsmooth minimization problem. Based on the generalized derivative concept of Newton differentiability, a locally superlinearly convergent, semismooth Newton method has been proposed in the literature. However, the convergence of local Newton methods is not guaranteed in general for an arbitrary initial guess. In order to globalize the algorithm, we consider a B(ouligand)-Newton method. We discuss the feasibility of the B-Newton method. The resulting algorithm is called a B-semismooth Newton method because it can also be interpreted as a semismooth Newton method. The algorithm converges locally superlinearly and the Newton equations are finite-dimensional. The B-Newton directions satisfy a descent property with respect to the square norm of the residual. We globalize the algorithm in a finite-dimensional setting by inexact line search. A drawback of this approach is that the sequence of iterates might begin to stagnate. Therefore, by a modification of the Newton equation, a globally convergent algorithm is proposed. We recommend a locally superlinearly convergent, hybrid algorithm that combines both methods. We present numerical results that demonstrate the efficiency of the methods. Diese Arbeit behandelt die Globalisierung eines halbglatten Newtonverfahrens für die l1-Tikhonovregularisierung. Dieses Regularisierungsverfahren für inverse Probleme mit dünnbesetzten Lösungen führt zu einem nichtglatten Minimierungsproblem. Die Optimalitätsbedingungen der in dieser Arbeit betrachteten Minimierungsaufgabe führen zu einem Nullstellenproblem einer nichtlinearen, lokal Lipschitz-stetigen Abbildung. Basierend auf dem verallgemeinerten Ableitungskonzept der Newton-Ableitung wurde in der Literatur ein lokal superlinear konvergentes, halbglattes Newtonverfahren vorgeschlagen. Die Konvergenz lokaler Newtonverfahren ist jedoch im Allgemeinen nicht für jede Startnäherung gesichert. Mit dem Ziel der Globalisierung des Verfahrens betrachten wir in dieser Arbeit ein B(ouligand)-Newtonverfahren. Wir diskutieren die Durchführbarkeit des B-Newtonverfahrens. Es stellt sich heraus, dass es sich hierbei ebenfalls um ein halbglattes Newtonverfahren, also um ein B-halbglattes Newtonverfahren, handelt. Der Algorithmus konvergiert lokal superlinear und die Newtongleichungen sind endlich-dimensional. Die B-Newtonrichtungen besitzen eine Abstiegseigenschaft bezüglich der Quadratnorm des Residuums. Mit Hilfe dieser Eigenschaft wird der Algorithmus im Endlichdimensionalen durch inexakte Liniensuche globalisiert. Ein Schwachpunkt des globalisierten Algorithmus ist, dass die Folge der Iterierten zu stagnieren beginnen kann. Durch eine Abwandlung der Newtongleichung wird ein modifiziertes Verfahren hergeleitet, das ohne Zusatzannahmen global konvergiert. Außerdem wird ein hybrides Verfahren vorgeschlagen. Dieser Algorithmus kombiniert beide Verfahren und ist lokal superlinear und global konvergent. Numerische Resultate demonstrieren die Effizienz der Verfahren.
DDC:	510 Mathematik 510 Mathematics
Institution:	Johannes Gutenberg-Universität Mainz
Department:	FB 08 Physik, Mathematik u. Informatik
Place:	Mainz
ROR:	https://ror.org/023b0x485
DOI:	http://doi.org/10.25358/openscience-3888
URN:	urn:nbn:de:hebis:77-diss-1000012921
Version:	Original work
Publication type:	Dissertation
License:	In Copyright
Information on rights of use:	https://rightsstatements.org/vocab/InC/1.0/
Extent:	vii, 108 Seiten
Appears in collections:	JGU-Publikationen