In this thesis we consider constrained systems of equations. The focus is on local Newton-type methods for the solution of constrained systems which converge locally quadratically under mild assumptions implying neither local uniqueness of solutions nor differentiability of the equation function at solutions. The first aim of this thesis is to improve existing local convergence results of the constrained Levenberg-Marquardt method. To this end, we describe a general Newton-type algorithm. Then we prove local quadratic convergence of this general algorithm under the same four assumptions which were recently used for the local convergence analysis of the LP-Newton method. Afterwards, we show that, besides the LP-Newton method, the constrained Levenberg-Marquardt method can be regarded as a special realization of the general Newton-type algorithm and therefore enjoys the same local convergence properties. Thus, local quadratic convergence of a nonsmooth constrained Levenberg-Marquardt method is proved without requiring conditions implying the local uniqueness of solutions. As already mentioned, we use four assumptions for the local convergence analysis of the general Newton-type algorithm. The second aim of this thesis is a detailed discussion of these convergence assumptions for the case that the equation function of the constrained system is piecewise continuously differentiable. Some of the convergence assumptions seem quite technical and difficult to check. Therefore, we look for sufficient conditions which are still mild but which seem to be more familiar. We will particularly prove that the whole set of the convergence assumptions holds if some set of local error bound conditions is satisfied and in addition the feasible set of the constrained system excludes those zeros of the selection functions which are not zeros of the equation function itself, at least in a sufficiently small neighborhood of some fixed solution. We apply our results to constrained systems arising from complementarity systems, i.e., systems of equations and inequalities which contain complementarity constraints. Our new conditions are discussed for a suitable reformulation of the complementarity system as constrained system of equations by means of the minimum function. In particular, it will turn out that the whole set of the convergence assumptions is actually implied by some set of local error bound conditions. In addition, we provide a new constant rank condition implying the whole set of the convergence assumptions. Particularly, we provide adapted formulations of our new conditions for special classes of complementarity systems. We consider Karush-Kuhn-Tucker (KKT) systems arising from optimization problems, variational inequalities, or generalized Nash equilibrium problems (GNEPs) and Fritz-John (FJ) systems arising from GNEPs. Thus, we obtain for each problem class conditions which guarantee local quadratic convergence of the general Newton-type algorithm and its special realizations to a solution of the particular problem. Moreover, we prove for FJ systems of GNEPs that generically some full row rank condition is satisfied at any solution of the FJ system of a GNEP. The latter condition implies the whole set of the convergence assumptions if the functions which characterize the GNEP are sufficiently smooth. Finally, we describe an idea for a possible globalization of our Newton-type methods, at least for the case that the constrained system arises from a certain smooth reformulation of the KKT system of a GNEP. More precisely, a hybrid method is presented whose local part is the LP-Newton method. The hybrid method turns out to be, under appropriate conditions, both globally and locally quadratically convergent.

Motivation and background The enormous amount of capabilities that every human learns throughout his life, is probably among the most remarkable and fascinating aspects of life. Learning has therefore drawn lots of interest from scientists working in very different fields like philosophy, biology, sociology, educational sciences, computer sciences and mathematics. This thesis focuses on the information theoretical and mathematical aspects of learning. We are interested in the learning process of an agent (which can be for example a human, an animal, a robot, an economical institution or a state) that interacts with its environment. Common models for this interaction are Markov decision processes (MDPs) and partially observable Markov decision processes (POMDPs). Learning is then considered to be the maximization of the expectation of a predefined reward function. In order to formulate general principles (like a formal definition of curiosity-driven learning or avoidance of unpleasant situation) in a rigorous way, it might be desirable to have a theoretical framework for the optimization of more complex functionals of the underlying process law. This might include the entropy of certain sensor values or their mutual information. An optimization of the latter quantity (also known as predictive information) has been investigated intensively both theoretically and experimentally using computer simulations by N. Ay, R. Der, K Zahedi and G. Martius. In this thesis, we develop a mathematical theory for learning in the sensorimotor loop beyond expected reward maximization. Approaches and results This thesis covers four different topics related to the theory of learning in the sensorimotor loop. First of all, we need to specify the model of an agent interacting with the environment, either with learning or without learning. This interaction naturally results in complex causal dependencies. Since we are interested in asymptotic properties of learning algorithms, it is necessary to consider infinite time horizons. It turns out that the well-understood theory of causal networks known from the machine learning literature is not powerful enough for our purpose. Therefore we extend important theorems on causal networks to infinite graphs and general state spaces using analytical methods from measure theoretic probability theory and the theory of discrete time stochastic processes. Furthermore, we prove a generalization of the strong Markov property from Markov processes to infinite causal networks. Secondly, we develop a new idea for a projected stochastic constraint optimization algorithm. Generally a discrete gradient ascent algorithm can be used to generate an iterative sequence that converges to the stationary points of a given optimization problem. Whenever the optimization takes place over a compact subset of a vector space, it is possible that the iterative sequence leaves the constraint set. One possibility to cope with this problem is to project all points to the constraint set using Euclidean best-approximation. The latter is sometimes difficult to calculate. A concrete example is an optimization over the unit ball in a matrix space equipped with operator norm. Our idea consists of a back-projection using quasi-projectors different from the Euclidean best-approximation. In the matrix example, there is another canonical way to force the iterative sequence to stay in the constraint set: Whenever a point leaves the unit ball, it is divided by its norm. For a given target function, this procedure might introduce spurious stationary points on the boundary. We show that this problem can be circumvented by using a gradient that is tailored to the quasi-projector used for back-projection. We state a general technical compatibility condition between a quasi-projector and a metric used for gradient ascent, prove convergence of stochastic iterative sequences and provide an appropriate metric for the unit-ball example. Thirdly, a class of learning problems in the sensorimotor loop is defined and motivated. This class of problems is more general than the usual expected reward maximization and is illustrated by numerous examples (like expected reward maximization, maximization of the predictive information, maximization of the entropy and minimization of the variance of a given reward function). We also provide stationarity conditions together with appropriate gradient formulas. Last but not least, we prove convergence of a stochastic optimization algorithm (as considered in the second topic) applied to a general learning problem (as considered in the third topic). It is shown that the learning algorithm converges to the set of stationary points. Among others, the proof covers the convergence of an improved version of an algorithm for the maximization of the predictive information as proposed by N. Ay, R. Der and K. Zahedi. We also investigate an application to a linear Gaussian dynamic, where the policies are encoded by the unit-ball in a space of matrices equipped with operator norm.

Tikhonov-type regularization of linear and nonlinear ill-posed problems in abstract spaces under sparsity constraints gained relevant attention in the past years. Since under some weak assumptions all regularized solutions are sparse if the l1-norm is used as penalty term, the l1-regularization was studied by numerous authors although the non-reflexivity of the Banach space l1 and the fact that such penalty functional is not strictly convex lead to serious difficulties. We consider the case that the sparsity assumption is narrowly missed. This means that the solutions may have an infinite number of nonzero but fast decaying components. For that case we formulate and prove convergence rates results for the l1-regularization of nonlinear operator equations. In this context, we outline the situations of Hölder rates and of an exponential decay of the solution components.

In this thesis we consider constrained systems of equations. The focus is on local Newton-type methods for the solution of constrained systems which converge locally quadratically under mild assumptions implying neither local uniqueness of solutions nor differentiability of the equation function at solutions. The first aim of this thesis is to improve existing local convergence results of the constrained Levenberg-Marquardt method. To this end, we describe a general Newton-type algorithm. Then we prove local quadratic convergence of this general algorithm under the same four assumptions which were recently used for the local convergence analysis of the LP-Newton method. Afterwards, we show that, besides the LP-Newton method, the constrained Levenberg-Marquardt method can be regarded as a special realization of the general Newton-type algorithm and therefore enjoys the same local convergence properties. Thus, local quadratic convergence of a nonsmooth constrained Levenberg-Marquardt method is proved without requiring conditions implying the local uniqueness of solutions. As already mentioned, we use four assumptions for the local convergence analysis of the general Newton-type algorithm. The second aim of this thesis is a detailed discussion of these convergence assumptions for the case that the equation function of the constrained system is piecewise continuously differentiable. Some of the convergence assumptions seem quite technical and difficult to check. Therefore, we look for sufficient conditions which are still mild but which seem to be more familiar. We will particularly prove that the whole set of the convergence assumptions holds if some set of local error bound conditions is satisfied and in addition the feasible set of the constrained system excludes those zeros of the selection functions which are not zeros of the equation function itself, at least in a sufficiently small neighborhood of some fixed solution. We apply our results to constrained systems arising from complementarity systems, i.e., systems of equations and inequalities which contain complementarity constraints. Our new conditions are discussed for a suitable reformulation of the complementarity system as constrained system of equations by means of the minimum function. In particular, it will turn out that the whole set of the convergence assumptions is actually implied by some set of local error bound conditions. In addition, we provide a new constant rank condition implying the whole set of the convergence assumptions. Particularly, we provide adapted formulations of our new conditions for special classes of complementarity systems. We consider Karush-Kuhn-Tucker (KKT) systems arising from optimization problems, variational inequalities, or generalized Nash equilibrium problems (GNEPs) and Fritz-John (FJ) systems arising from GNEPs. Thus, we obtain for each problem class conditions which guarantee local quadratic convergence of the general Newton-type algorithm and its special realizations to a solution of the particular problem. Moreover, we prove for FJ systems of GNEPs that generically some full row rank condition is satisfied at any solution of the FJ system of a GNEP. The latter condition implies the whole set of the convergence assumptions if the functions which characterize the GNEP are sufficiently smooth. Finally, we describe an idea for a possible globalization of our Newton-type methods, at least for the case that the constrained system arises from a certain smooth reformulation of the KKT system of a GNEP. More precisely, a hybrid method is presented whose local part is the LP-Newton method. The hybrid method turns out to be, under appropriate conditions, both globally and locally quadratically convergent.

Zur Simulation technischer Prozesse ist eine hinreichend genaue Beschreibung des Materialverhaltens notwendig. Die hierfür häufig verwendeten phänomenologischen Ansätze, wie im vorliegenden Fall die HILLsche Fließbedingung, enthalten materialspezifische Parameter, welche nicht direkt messbar sind. Die Identifikation dieser Materialparameter erfolgt in der Regel durch Minimierung eines Fehlerquadratfunktionals, welches Differenzen von Messwerten und zugehörigen numerisch berechneten Vergleichswerten enthält. In diesem Zusammenhang haben sich zur Lösung dieser Minimierungsaufgabe die Trust-Region Verfahren als gut geeignet herausgestellt. Die Aufgabe besteht darin, die verschiedenen Möglichkeiten zur Steuerung eines Trust-Region Verfahrens, im Hinblick auf die Eignung für das vorliegende Identifikationsproblem, zu untersuchen. Dazu werden die Quadratmittelprobleme und deren Lösungsverfahren überblicksmäßig betrachtet. Danach wird näher auf die Trust-Region Verfahren eingegangen, wobei sich im Weiteren auf Verfahren mit positiv definiten Ansätzen für die Hesse-Matrix, den Levenberg-Marquardt Verfahren, beschränkt wird. Danach wird ein solcher Levenberg-Marquardt Algorithmus in verschiedenen Ausführungen implementiert und an dem vorliegenden Identifikationsproblem getestet. Als Ergebnis stellt sich eine gute Kombination aus verschiedenen Teilalgorithmen des Levenberg-Marquardt Algorithmus mit einer hohen Konvergenzgeschwindigkeit heraus, welche für das vorliegende Problem gut geeignet ist.:1 Einleitung 8 2 Nichtlineare Quadratmittelprobleme 9 2.1 Herkunft der Residuen: Das Prinzip der kleinsten Fehlerquadrate 10 2.2 Auftretende Differentialmatrizen 11 2.2.1 Lipschitzbedingung für die Unterscheidung der Aufgabenklasse im Hinblick auf die Residuen 12 2.3 Aufgabenklassen 13 2.3.1 Kleine und Null-Residuen 13 2.3.2 Große Residuen 13 2.3.3 Große Probleme 14 2.4 Modellstufen für f(x) um eine lokale Konstellation xk 15 2.5 Eigenschaften der Gauß-Newton Approximation der Hesse-Matrix 16 3 Identifikation der Materialparameter der HILLschen Fließbedingung für die plastische Verformung anisotroper Werkstoffe 17 4 ¨Ubersicht über monoton fallende Optimierungsverfahren für nichtlineare Funktionen 19 4.1 Die Idee der Line-Search Verfahren 19 4.2 Die Idee der Trust-Region Verfahren 20 4.3 Übersichtstabelle Über die Verfahren zur unrestringierten Optimierung 21 4.4 Ermittlungsmethoden fÜr die Suchrichtung sk bei Line-Search Methoden 22 4.4.1 Gradientenverfahren 22 4.4.2 Das Newton Verfahren 22 4.4.3 Quasi-Newton Verfahren 23 4.4.4 Gauß-Newton Verfahren 24 4.4.5 Methode der konjugierten Gradienten 25 4.4.6 Koordinatenabstiegsmethode nach Ahlers,Schwartz,Waldmann [1] 25 4.5 Modelle für die Trust-Region Verfahren 26 4.5.1 Der Cauchy Punkt 26 4.5.2 Das Newton Trust-Region Verfahren 27 4.5.3 Quasi-Newton Trust-Region Verfahren 27 4.5.4 Gauß-Newton Trust-Region: Levenberg-Marquardt Verfahren 27 4.6 Vergleich der Hauptstrategien 27 5 Die Trust-Region Verfahren 29 5.1 Die Konvergenz des Trust-Region Algorithmus zu stationären Punkten 34 5.2 Die Berechnung des Trust-Region Schrittes 35 5.3 Der Cauchy Punkt 37 5.4 Die Lösungsverfahren 38 5.5 Nahezu exakte Lösung des Trust-Region Problems, Regularisierung . 38 5.6 Struktur und Lösung der nahezu exakten Methode für den Normalfall 42 5.6.1 Ermitteln des Minimums s( lambda) des aktuellen Modells 46 5.6.1.1 Lösung mittels Cholesky Faktorisierung 47 5.6.1.2 Lösung mittels QR-Faktorisierung 47 5.6.1.3 Lösung mittels Singulärwertzerlegung 47 5.6.2 Das Ermitteln des Regularisierungsparameters 48 5.6.3 Ermitteln der Ableitung 0i( ) 51 5.6.4 Abbruch der -Iteration 52 5.6.5 Absichern der -Iteration 52 5.6.6 Ermitteln des Verhältnisses k 52 5.6.7 Auffrischen der Schrittnebenbedingung k 53 5.6.8 Startwerte für den Trust-Region Algorithmus 56 5.6.8.1 Startwerte 0 für den Trust-Region Radius 56 5.6.8.2 Startwerte für den Regularisierungsparameter 0 56 5.6.9 Konvergenz von Algorithmen, basierend auf nahezu exakten Lösungen 57 5.7 Approximation des Trust-Region Problems 57 5.7.1 Die Dogleg Methode 58 5.7.2 Die zweidimensionale Unterraumminimierung 60 5.7.3 Das Steihaug Vorgehen 61 5.7.4 Konvergenz der Approximationsverfahren 62 6 Trust-Region Verfahren mit positiv definiter Approximation der Hesse-Matrix: Das Levenberg-Marquardt Verfahren 63 6.1 Vorhandene Matrizen und durchführbare Methoden 64 6.2 Lösen des Levenberg-Marquardt Problems 66 6.2.1 Ermitteln von s( ) 68 6.2.1.1 Cholesky Faktorisierung 68 6.2.1.2 QR-Faktorisierung 68 6.2.1.3 Singulärwertzerlegung 68 6.2.2 Ermittlung des Regularisierungsparameter 69 6.2.3 Absichern der -Iteration 71 6.2.3.1 Absichern für die Strategie von Hebden 71 6.2.3.2 Absichern für die Newtonmethode 72 6.2.4 Weitere Teilalgorithmen 73 6.3 Ein prinzipieller Levenberg-Marquardt Algorithmus 73 7 Skalierung der Zielparameter 74 8 Abbruchkriterien für die Optimierungsalgorithmen 76 8.1 Abbruchkriterien bei Erreichen eines lokalen Minimums 76 8.2 Abbruchkriterien bei Erreichen der Maschinengenauigkeit für Trust-Region Verfahren 77 9 Test der Implementation des Levenberg-Marquardt Verfahrens 78 9.1 Test der Leistung für einzelne Parameter 79 9.2 Test der Leistung für Optimierungen mit mehreren Parametern 80 9.3 Test des Moduls 1 80 9.4 Test Modul 2 und Modul 3 81 9.5 Test des Moduls 4 81 9.6 Test des Moduls 5 81 9.7 Test des Modul 6 82 9.8 Test des Modul 7 83 9.9 Test des Modul 8 84 9.10 Modul 9 und Modul 10 84 9.11 Test mit verschiedenen Verfahrensparametern 85 9.12 Optimale Konfiguration 86 10 Zusammenfassung 87 11 Ausblick 88 11.1 Weiterführendes zu dem bestehenden Levenberg-Marquardt Verfahren 88 11.2 Weiterführendes zu den Trust-Region Verfahren 88 11.3 Weiterführendes zu den Line-Search Verfahren 89 11.4 Weiterführendes zu den Gradientenverfahren 89 Literaturverzeichnis 93 A Implementation: Das skalierte Levenberg-Marquardt Verfahren 95 A.1 Modul 1.x: 0-Wahl 95 A.1.1 Modul 1.1 95 A.1.2 Modul 1.2 96 A.1.3 Modul 1.3 96 A.1.4 Programmtechnische Umsetzung Modul 1 96 A.2 Modul 2.x: Wahl der Skalierungsmatrix 96 A.2.1 Modul 2.1 96 A.2.2 Modul 2.2 97 A.2.3 Programmtechnische Umsetzung Modul 2 97 A.3 Modul 3.x: Wahl der oberen und unteren Schranke l0, u0 für die - Iteration 97 A.3.1 Modul 3.1 97 A.3.2 Modul 3.2 97 A.3.3 Programmtechnische Umsetzung Modul 3 98 A.4 Modul 4.x: Wahl des Startwertes für den Regularisierungsparameter 0 98 A.4.1 Modul 4.1 98 A.4.2 Modul 4.2 99 A.4.3 Modul 4.3 99 A.4.4 Modul 4.4 99 A.4.5 Programmtechnische Umsetzung Modul 4 100 A.5 Modul 5.x: Die abgesicherte -Iteration 100 A.5.1 Modul 5.1 Die Iteration nach dem Schema von Hebden für 1 101 A.5.2 Modul 5.2 Die abgesicherte Iteration mit dem Newtonverfahren für 2 101 A.5.3 Die abgesicherte Iteration mit dem Newtonverfahren für 2 mittels Cholesky Zerlegung 102 A.5.4 Programmtechnische Umsetzung Modul 5 102 A.6 Modul 6.x: Die Ermittlung des Verhältnisses k 103 A.6.1 Modul 6.1: Herkömmliche Ermittlung 103 A.6.2 Modul 6.2: Numerisch stabile Ermittlung 104 A.6.3 Programmtechnische Umsetzung Modul 6 104 A.7 Modul 7.x: Auffrischen der Schrittnebenbedingung 105 A.7.1 Modul 7.1: Einfache Wahl 105 A.7.2 Modul 7.2: Wahl mit Berücksichtigung von Werten k < 0 105 A.7.3 Modul 7.3: Wahl mit Approximation von ffl 105 A.7.4 Programmtechnische Umsetzung Modul 7 106 A.8 Modul 8.x: Entscheidung über Akzeptanz des nächsten Schrittes sk . 107 A.8.1 Modul 8.1: Eine Akzeptanzbedingung 107 A.8.2 Modul 8.2: Zwei Akzeptanzbedingungen 107 A.8.3 Programmtechnische Umsetzung Modul 8 107 A.9 Modul 9.x: Abbruchbedingungen für den gesamten Algorithmus 107 A.9.1 Programmtechnische Umsetzung Modul 9 108 A.10 Modul 10.x: Berechnung des Schrittes s( ) 108 A.10.1 Modul 10.1 108 A.10.2 Modul 10.2 108 A.10.3 Programmtechnische Umsetzung Modul 10 108 A.11 Benötigte Prozeduren 109 A.11.1 Vektormultiplikation 109 A.11.2 Matrixmultiplikation 109 A.11.3 Matrixaddition 109 A.11.4 Cholesky Faktorisierung 110 A.11.5 Transponieren einer Matrix 111 A.11.6 Invertieren einer Matrix 111 A.11.6.1 Determinante einer Matrix 111 A.11.7 Normen 112 A.11.7.1 Euklidische Vektornorm 112 A.11.7.2 Euklidische Matrixnorm 112 A.11.8 Ermittlung von 1 112 A.11.9 Ermittlung von 2 112 A.11.10Ermittlung von 01 112 A.11.11Ermittlung von 02 .112 A.11.12Ermittlung von mk(s) 113 A.12 Programmablauf 113 A.13 Fehlercodes 114 B Weiterführendes: Allgemeines 116 B.1 Total Least Squares, Orthogonal distance regression 116 B.2 Lipschitz Konstante und Lipschitz Stetigkeit in nichtlinearen Quadratmittelproblemen 116 B.3 Beweis für das Prinzip der kleinsten Fehlerquadrate als beste Möglichkeit der Anpassung von Modellgleichungen an Messwerte 117 B.4 Konvergenzraten 119 B.5 Betrachtung der Normalengleichung als äquivalente Extremalbedingung 119 B.6 Der Cauchy Punkt 120 B.7 Minimumbedingungen 122 C Weiterführendes: Matrizen 123 C.1 Reguläre und singuläre Matrizen 123 C.2 Rang einer Matrix 123 C.3 Definitheit von quadratischen Matrizen 124 C.4 Kondition einer Matrix 125 C.5 Spaltenorthonormale und orthogonale Matrizen 125 C.6 Singulärwertzerlegung einer Matrix, SVD 126 C.7 Der Lanczos Algorithmus 127 C.8 Die QR Zerlegung einer Matrix 127 C.8.1 Gram Schmidt Orthogonalisierung 127 C.8.2 Householder Orthogonalisierung 127 C.9 Die Cholesky Faktorisierung 130 C.10 Die LINPACK Technik 131 D Daten und Bilder zum Levenberg-Marquardt Verfahren 132 D.1 Wichtige Funktionsverläufe des LM-Verfahrens 134 D.2 Einzelne Parameteroptimierungen 136 D.3 Kombinierte Parameteroptimierungen, P1,P2,P3 139 D.4 Vergleich Ableitungsgüte, Konvergenzproblem 142 D.5 Test des Modul 1 145 D.6 Test Modul 4 und 5 146 D.7 Test des Modul 6 147 D.8 Test des Modul 7 148 D.9 Test des Modul 8 151 D.10 Test verschiedener Algorithmusparameter 152 D.11 Standartalgorithmus und Verbesserter 155

Die kontinuierliche Weiterentwicklung und Verbesserung technischer Prozesse erfolgt heute auf der Basis stochastischer und deterministischer Optimierungsstrategien in Kombination mit der numerischen Simulation dieser Abläufe. Da die FE-Simulation von Umformvorgängen in der Regel sehr zeitintensiv ist, bietet sich für die Optimierung solcher Prozesse der Einsatz deterministischer Methoden an, da hier weniger Optimierungsschritte und somit auch weniger FE-Simulationen notwendig sind. Eine wichtige Anforderung an solche Optimierungsverfahren ist globale Konvergenz zu lokalen Minima, da die optimalen Parametersätze nicht immer näherungsweise bekannt sind. Die zwei wichtigsten Strategien zum Ausdehnen des beschränkten Konvergenzradius der natürlichen Optimierungsverfahren (newtonschrittbasierte Verfahren und Gradientenverfahren) sind die Line-Search-Strategie und die Trust-Region-Strategie. Die Grundlagen der Line-Search-Strategie werden aufgearbeitet und die wichtigsten Teilalgorithmen implementiert. Danach wird dieses Verfahren auf eine effiziente Kombination der Teilalgorithmen und Verfahrensparameter hin untersucht. Im Anschluss wird die Leistung eines Optimierungsverfahrens mit Line-Search-Strategie verglichen mit der eines ebenfalls implementierten Optimierungsverfahrens mit skalierter Trust-Region-Strategie. Die Tests werden nach Einfügen der implementierten Verfahren in das Programm SPC-Opt anhand der Lösung eines Quadratmittelproblems aus der Materialparameteridentifikation sowie der Formoptimierung eines Umformwerkzeugs vorgenommen.:1 Einleitung 7 2 Verfahren zur unrestringierten Optimierung 9 2.1 Vorbemerkungen 9 2.2 Der Schrittvektor sk 10 2.3 Natürliche Schrittweite und Konvergenz der Verfahren 11 2.4 Richtung des steilsten Abstiegs 12 2.5 Newtonschrittbasierte Verfahren 13 2.5.1 Newton-Verfahren 15 2.5.2 Quasi-Newton-Verfahren der Broyden-Klasse 15 2.5.3 Der BFGS-Auffrisch-Algorithmus 18 2.5.4 Die SR1-Auffrisch-Formel 19 2.5.5 Die DFP-Auffrisch-Formel 20 2.5.6 Gauß-Newton-Verfahren 20 2.6 Erzwingen der Bedingung der positiven Definitheit von Gk 21 3 Übersicht über die Verfahren zum Stabilisieren der natürlichen Schrittweiten 24 3.1 Das Prinzip der Line-Search-Verfahren 24 3.2 Das Prinzip der Trust-Region-Verfahren 26 3.3 Vergleich der Trust-Region- und der Line-Search-Strategien 27 4 Line-Search-Strategien 30 4.1 Vorbemerkungen 30 4.2 Ein prinzipieller Line-Search-Algorithmus 33 5 Die Akzeptanzkriterien für die Line-Search-Strategien 36 5.1 Die exakte Schrittweite 37 5.2 Das Armijo-Kriterium, ein Abstiegskriterium 39 5.2.1 Das klassische Armijo-Kriterium 39 5.2.2 Armijo-Kriterium mit unterer Schranke fflo > 0 40 5.3 Die Goldstein-Kriterien 42 5.4 Die Wolfe-Kriterien 44 5.4.1 Die einfachen Wolfe-Kriterien 44 5.4.2 Die starken Wolfe-Kriterien 46 5.5 Näherungsweiser Line-Search basierend auf Armijo, ff-Methode 47 6 Ermittlung der nächsten Testschrittweite ffj+1 49 6.1 Die Startschrittweite ffj=1 51 6.2 Verfahren mit konstanten Faktoren 52 6.3 Verfahren mit konstanten Summanden 53 6.4 Verfahren mit quadratischen Polynomen 54 6.5 Verfahren mit kubischen Polynomen 56 6.6 Sektionssuche mit goldenem Schnitt 58 7 Absicherung und Abbruchbedingungen des Line-Search-Verfahrens 60 7.1 Die drei Konvergenzpunkte eines Line-Search-Verfahrens 60 7.1.1 Lokales Minimum in f 60 7.1.2 Algorithmus konvergiert gegen −1 61 7.1.3 Der Winkel zwischen sk und −rfk wird 90° 61 7.2 Weitere Absicherungen 62 7.2.1 Abstiegsrichtung 62 7.2.2 Der gradientenbezogene Schrittvektor 62 7.2.3 Zulässige Schrittweiten in der Extrapolationsphase 63 7.2.4 Intervalle bei der Interpolation 63 7.2.5 Maximale Durchlaufzahlen 63 8 Implementierung 65 8.1 Grundlegende Struktur der Implementierung 65 8.2 Anwendungsgebiete 67 8.2.1 Identifikation der Materialparameter der isotropen Verfestigung und der HILLschen Fließbedingung 67 8.2.2 Optimierung der Form eines Umformwerkzeugs 70 8.3 Test des Programms anhand der Identifikation der Parameter der isotropen Verfestigung und der HILLschen Fließbedingung 71 8.3.1 Einfluss der Funktionsumgebung 71 8.3.2 Test der Line-Search-Verfahrensparameter 74 8.3.3 Einfluss der Startwerte und der Qualität der Ableitungsermittlung 77 8.3.4 Test der Quasi-Newton-Strategien 77 8.3.5 Test der Trust-Region-Skalierung 79 8.3.6 Vergleich der Trust-Region- und der Line-Search-Strategie 80 8.3.7 Tests mit den HILLschen Anisotropieparametern und drei Vorwärtsrechnungen 81 9 Zusammenfassung und Ausblick 83 9.1 Zusammenfassung 83 9.2 Ausblick 84 Liste häufig verwendeter Formelzeichen 85 Literaturverzeichnis 88 A Zusätzliches zur Implementierung 90 A.1 Parametervorschläge für die Line-Search-Verfahren 90 A.2 Fehlercode-Liste 92 A.3 Programmablaufpläne 94 A.3.1 Ablauf in main.cpp 94 A.3.2 Ablauf in OneOptLoop 95 A.3.3 Ablauf während des Trust-Region-Verfahrens 96 A.3.4 Ablauf während des Line-Search-Verfahrens 97 A.4 Steuerung der Optimierungsoptionen über OptInputData.dat 98 A.4.1 Übergeordnete Algorithmen 98 A.4.1.1 Quasi-Newton-Verfahren 98 A.4.1.2 Absichern der positiven Definitheit von Gk 99 A.4.1.3 Auswahl des Optimierungsverfahrens, Auswahl der Schrittweitensteuerung 100 A.4.1.4 Abbruchbedingungen für die Lösungsfindung 100 A.4.1.5 Wahl des Startvektors x0 101 A.4.2 Die Trust-Region-Algorithmen 102 A.4.2.1 Wahl des Anfangsradius 0 des Vertrauensbereichs 102 A.4.2.2 Wahl des Skalierungsverfahrens 102 A.4.2.3 Wahl des Startwertes l=0 für die Regularisierungsparameteriteration 103 A.4.2.4 Regularisierungsparameteriteration 103 A.4.2.5 Wahl des Verfahrens zum Auffrischen des Radius des Vertrauensbereichs 103 A.4.2.6 Bedingungen für einen akzeptablen Schritt 104 A.4.2.7 Absicherungen des Trust-Region-Verfahrens 104 A.4.3 Die Line-Search-Algorithmen 105 A.4.3.1 Die Akzeptanzkriterien 105 A.4.3.2 Die Verfahren zur Extrapolation 105 A.4.3.3 Die Verfahren zur Interpolation 106 A.4.3.4 Verfahren zur Wahl von ffj=2 106 A.4.3.5 Absicherung des Line-Search-Verfahrens 106 B Testrechnungen 107 B.1 Ausgewählte Versuchsreihen 107 B.2 Bilder der Funktionsumgebung der Materialparameteridentifikation 109 B.3 Beschreibung der digitalen Anlagen 112 Eidesstattliche Erklärung und Aufgabenstellung 113

This thesis is concerned with the development of novel numerical methods for solving nondifferentiable convex optimization problems in real Hilbert spaces and with the investigation of their asymptotic behavior. To this end, we are also making use of monotone operator theory as some of the provided algorithms are originally designed to solve monotone inclusion problems. After introducing basic notations and preliminary results in convex analysis, we derive two numerical methods based on different smoothing strategies for solving nondifferentiable convex optimization problems. The first approach, known as the double smoothing technique, solves the optimization problem with some given a priori accuracy by applying two regularizations to its conjugate dual problem. A special fast gradient method then solves the regularized dual problem such that an approximate primal solution can be reconstructed from it. The second approach affects the primal optimization problem directly by applying a single regularization to it and is capable of using variable smoothing parameters which lead to a more accurate approximation of the original problem as the iteration counter increases. We then derive and investigate different primal-dual methods in real Hilbert spaces. In general, one considerable advantage of primal-dual algorithms is that they are providing a complete splitting philosophy in that the resolvents, which arise in the iterative process, are only taken separately from each maximally monotone operator occurring in the problem description. We firstly analyze the forward-backward-forward algorithm of Combettes and Pesquet in terms of its convergence rate for the objective of a nondifferentiable convex optimization problem. Additionally, we propose accelerations of this method under the additional assumption that certain monotone operators occurring in the problem formulation are strongly monotone. Subsequently, we derive two Douglas–Rachford type primal-dual methods for solving monotone inclusion problems involving finite sums of linearly composed parallel sum type monotone operators. To prove their asymptotic convergence, we use a common product Hilbert space strategy by reformulating the corresponding inclusion problem reasonably such that the Douglas–Rachford algorithm can be applied to it. Finally, we propose two primal-dual algorithms relying on forward-backward and forward-backward-forward approaches for solving monotone inclusion problems involving parallel sums of linearly composed monotone operators. The last part of this thesis deals with different numerical experiments where we intend to compare our methods against algorithms from the literature. The problems which arise in this part are manifold and they reflect the importance of this field of research as convex optimization problems appear in lots of applications of interest.

Diese Arbeit beschäftigt sich mit Coarse-Graining (dt. ``Vergröberung", ``Zusammenfassung von Zuständen") für Gradientensysteme und Markov-Prozesse. Coarse-Graining ist ein etabliertes Verfahren in der Mathematik und in den Naturwissenschaften und hat das Ziel, die Komplexität eines physikalischen Systems zu reduzieren und effektive Modelle herzuleiten. Die mathematischen Probleme in dieser Arbeit stammen aus der Theorie der Systeme interagierender Teilchen. Hierbei werden zwei Ziele verfolgt: Erstens, Coarse-Graining mathematisch rigoros zu beweisen, zweitens, mathematisch äquivalente Beschreibungen für die effektiven Modelle zu formulieren. Die ersten drei Teile der Arbeit befassen sich mit dem Grenzwert schneller Reaktionen für Reaktionssysteme und Reaktions-Diffusions-Systeme. Um effektive Modelle herzuleiten, werden nicht nur die zugehörigen Reaktionsratengleichungen betrachtet, sondern auch die zugrunde liegende Gradientenstruktur. Für Gradientensysteme wurde in den letzten Jahren eine strukturelle Konvergenz, die sogenannte ``EDP-Konvergenz", entwickelt. Dieses Coarse-Graining-Verfahren wird in der vorliegenden Arbeit auf folgende Systeme mit langsamen und schnellen Reaktionen angewandt: lineare Reaktionssysteme (bzw. Markov-Prozesse auf endlichem Zustandsraum), nichtlineare Reaktionssysteme, die das Massenwirkungsgesetz erfüllen, und lineare Reaktions-Diffusions-Systeme. Für den Grenzwert schneller Reaktionen wird eine mathematisch rigorose und strukturerhaltende Vergröberung auf dem Level des Gradientensystems inform von EDP-Konvergenz bewiesen. Im vierten Teil wird der Zusammenhang zwischen Gleichungen mit Gedächtnis und Markov-Prozessen untersucht. Für Gleichungen mit Gedächtnisintegralen wird explizit ein größer Markov-Prozess konstruiert, der die Gleichung mit Gedächtnis als Teilsystem enthält. Der letzte Teil beschäftigt sich mit verschieden Diskretisierungen für den Fokker-Planck-Operator. Dazu werden numerische und analytische Eigenschaften untersucht. / This thesis deals with coarse-graining for gradient systems and Markov processes. Coarse-graining is a well-established tool in mathematical and natural sciences for reducing the complexity of a physical system and for deriving effective models. The mathematical problems in this work originate from interacting particle systems. The aim is twofold: first, providing mathematically rigorous results for physical coarse-graining, and secondly, formulating mathematically equivalent descriptions for the effective models. The first three parts of the thesis deal with fast-reaction limits for reaction systems and reaction-diffusion systems. Instead of deriving effective models by solely investigating the associated reaction-rate equation, we derive effective models using the underlying gradient structure of the evolution equation. For gradient systems a structural convergence, the so-called ``EDP-convergence", has been derived in recent years. In this thesis, this coarse-graining procedure has been applied to the following systems with slow and fast reactions: linear reaction systems (or Markov process on finite state space), nonlinear reaction systems of mass-action type, and linear reaction-diffusion systems. For the fast-reaction limit, we perform rigorous and structural coarse-graining on the level of the gradient system by proving EDP-convergence. In the fourth part, the connection between memory equations and Markov processes is investigated. Considering linear memory equations, which can be motivated from spatial homogenization, we explicitly construct a larger Markov process that includes the memory equation as a subsystem. The last part deals with different discretization schemes for the Fokker–Planck operator and investigates their analytical and numerical properties.

Limit-Orderbücher sind das Standardinstrument der Preisbildung in modernen Finanzmärkten. Während Strom traditionell in Auktionen gehandelt wird, gibt es Intraday Strommärkte wie beispielsweise den SIDC-Markt, in welchem Käufer und Verkäufer über Limit-Orderbücher zusammentreffen. In dieser Arbeit werden wir stochastische Modelle von Limit-Orderbüchern auf der Grundlage der zugrundeliegenden Marktmikrostruktur entwickeln. Einen besonderen Schwerpunkt legen wir dabei auf die Berücksichtigung besonderer Merkmale der Intraday-Strommärkte, die sich zum Teil deutlich von denen der Finanzmärkte unterscheiden. Die in dieser Arbeit entwickelten Modelle beginnen mit einer realistischen und mikroskopischen Beschreibung der Marktdynamik. Große Preisänderungen über kurze Zeiträume werden ebenso berücksichtigt wie begrenzte grenzüberschreitende Aktivitäten. Diese mikroskopischen Modelle sind im Allgemeinen zu rechenintensiv für praktische Anwendungen. Das Hauptziel dieser Arbeit ist es daher, geeignete Approximationen dieser mikroskopischen Modelle durch sogenannte Skalierungsgrenzprozesse herzuleiten. Zu diesem Zweck werden sorgfältig Skalierungsannahmen formuliert und in die mikroskopischen Modelle eingebaut. Diese Annahmen ermöglichen es uns, ihr Hochfrequenzverhalten zu untersuchen, vorausgesetzt, dass die Größe eines einzelnen Auftrags gegen Null konvergiert, während die Auftragseingangsrate gegen unendlich tendiert. Die Kalibrierung mathematischer Modelle ist aus Anwendersicht eines der Hauptanliegen. Dabei ist bekannt, dass Änderungspunkte (abrupte Schwankungen) in hochfrequenten Finanzdaten vorhanden sind. Falls sie durch endogene Effekte verursacht wurden, muss bei der Schätzung solcher Änderungspunkte die Abhängigkeit von den zugrundeliegenden Daten berücksichtigt werden. Daher erweitern wir im letzten Teil dieser Arbeit die bestehende Literatur zur Erkennung von Änderungspunkten, so dass auch zufällige, von den Daten abhängige Änderungspunkte gehandhabt werden können. / Limit order books are the standard instrument for price formation in modern financial markets. While electricity has traditionally been traded through auctions, there are intraday electricity markets, such as the SIDC market, in which buyers and sellers meet via limit order books. In this thesis, stochastic models of limit order books are developed based on the underlying market microstructure. A particular focus is set on incorporating unique characteristics of intraday electricity markets, some of which are quite different from those of financial markets. The developed models in this thesis start with a realistic and microscopic description of the market dynamics. Large price changes over short time periods are considered, as well as limited cross-border activities. These microscopic models are generally computationally too intensive for practical applications. The main goal of this thesis is therefore to derive suitable approximations of these microscopic models by so-called scaling limits. For this purpose, appropriate scaling assumptions are carefully formulated and incorporated into the microscopic models which allow us to study their high-frequency behavior when the size of an individual order converges to zero while the order arrival rate tends to infinity. Calibration of mathematical models is one of the main concerns from a practitioner’s point of view. It is well known that change points (abrupt variations) are present in high-frequency financial data. If they are caused by endogenous effects, the dependence on the underlying data must be considered when estimating such change points. In the final part of this thesis, we extend the existing literature on change point detection so that random change points depending on the data can also be handled.

Infimalfolgen nichtkonvexer Variationsprobleme haben aufgrund feiner Oszillationen häufig keinen starken Grenzwert in Sobolevräumen. Diese Oszillationen haben eine physikalische Bedeutung; Finite-Element-Approximationen können sie jedoch im Allgemeinen nicht auflösen. Relaxationsmethoden ersetzen die nichtkonvexe Energie durch ihre (semi)konvexe Hülle. Das entstehende makroskopische Modell ist degeneriert: es ist nicht strikt konvex und hat eventuell mehrere Minimalstellen. Die fehlende Kontrolle der primalen Variablen führt zu Schwierigkeiten bei der a priori und a posteriori Fehlerschätzung, wie der Zuverlässigkeits- Effizienz-Lücke und fehlender starker Konvergenz. Zur Überwindung dieser Schwierigkeiten erweitern Stabilisierungstechniken die relaxierte Energie um einen diskreten, positiv definiten Term. Bartels et al. (IFB, 2004) wenden Stabilisierung auf zweidimensionale Probleme an und beweisen dabei starke Konvergenz der Gradienten. Dieses Ergebnis ist auf glatte Lösungen und quasi-uniforme Netze beschränkt, was adaptive Netzverfeinerungen ausschließt. Die vorliegende Arbeit behandelt einen modifizierten Stabilisierungsterm und beweist auf unstrukturierten Netzen sowohl Konvergenz der Spannungstensoren, als auch starke Konvergenz der Gradienten für glatte Lösungen. Ferner wird der sogenannte Fluss-Fehlerschätzer hergeleitet und dessen Zuverlässigkeit und Effizienz gezeigt. Für Interface-Probleme mit stückweise glatter Lösung wird eine Verfeinerung des Fehlerschätzers entwickelt, die den Fehler der primalen Variablen und ihres Gradienten beschränkt und so starke Konvergenz der Gradienten sichert. Der verfeinerte Fehlerschätzer konvergiert schneller als der Fluss- Fehlerschätzer, und verringert so die Zuverlässigkeits-Effizienz-Lücke. Numerische Experimente mit fünf Benchmark-Tests der Mikrostruktursimulation und Topologieoptimierung ergänzen und bestätigen die theoretischen Ergebnisse. / Infimising sequences of nonconvex variational problems often do not converge strongly in Sobolev spaces due to fine oscillations. These oscillations are physically meaningful; finite element approximations, however, fail to resolve them in general. Relaxation methods replace the nonconvex energy with its (semi)convex hull. This leads to a macroscopic model which is degenerate in the sense that it is not strictly convex and possibly admits multiple minimisers. The lack of control on the primal variable leads to difficulties in the a priori and a posteriori finite element error analysis, such as the reliability-efficiency gap and no strong convergence. To overcome these difficulties, stabilisation techniques add a discrete positive definite term to the relaxed energy. Bartels et al. (IFB, 2004) apply stabilisation to two-dimensional problems and thereby prove strong convergence of gradients. This result is restricted to smooth solutions and quasi-uniform meshes, which prohibit adaptive mesh refinements. This thesis concerns a modified stabilisation term and proves convergence of the stress and, for smooth solutions, strong convergence of gradients, even on unstructured meshes. Furthermore, the thesis derives the so-called flux error estimator and proves its reliability and efficiency. For interface problems with piecewise smooth solutions, a refined version of this error estimator is developed, which provides control of the error of the primal variable and its gradient and thus yields strong convergence of gradients. The refined error estimator converges faster than the flux error estimator and therefore narrows the reliability-efficiency gap. Numerical experiments with five benchmark examples from computational microstructure and topology optimisation complement and confirm the theoretical results.