All-at-once multigrid methods for optimality systems arising from optimal control problems

In dieser Arbeit konstruieren und analysieren wir Mehrgittermethoden zur Lösung gewisser Klassen von Optimalsteuerungsproblemen. Ursprünglich wurden Mehrgittermethoden zur Lösung elliptischer Probleme konstruiert. Die Optimalsteuerungsprobleme jedoch werden durch ein lineares System notwendiger Bedingungen beschrieben (Optimalitätssystem), das nicht elliptisch ist. Wir machen uns jedoch zunutze, dass das Optimalitätssystem eine Block-Matrix ist, das eine Sattelpunktstruktur aufweist: Einerseits haben wir die beiden Blöcke von Variablen, die bereits Teil des Optimalsteuerungsproblems sind: die Variablen, die den Zustand beschreiben, und die Variablen, die die Kontrolle beschreiben. Ferner bilden die Lagrange-Multiplikatoren einen dritten Block von Variablen, der beim Übergang zum Optimalitätssystem eingeführt wird. Es gibt nun mehrere Möglichkeiten, in diesem Kontext Mehrgitterverfahren zu verwenden. Eine Möglichkeit besteht darin, das Mehrgitterverfahren als Teil eines Vorkonditionierers jeweils auf einzelne Blöcke des Gesamtsystems anzuwenden. Dazu müsste die Mehrgittermethode in jedem Schritt des jeweils gewählten äußeren Iterationsverfahrens angewandt werden. Eine andere Möglichkeit, der wir in dieser Arbeit folgen, ist es, die Methode direkt auf das Gesamtsystem anzuwenden. Ein solcher Zugang wird auch als all-at-once approach bezeichnet. Für einen solchen Ansatz ist der wesentlichse Punkt die Wahl eines passenden Glätters. Wir werden Glätter konstruieren, deren Konvergenzraten vom Grad der Verfeinerung der Diskretisierung unabhängig sind. Da in diesem Fall der Gesamtaufwand der Methode linear von der Anzahl der Unbekannten abhängt, sprechen wir auch von einer optimalen Konvergenzrate. Für eine Teilklasse der betrachteten Probleme gehen wir einen Schritt weiter und konstruieren auch Lösungsmethoden, deren Konveregnzraten robust in einem Kosten- oder Regularisierungsparameter sind, der Teil der Problemstellung ist. Methoden, die auf eine solche Robustheit nicht Rücksicht nehmen, zeigen für kleine Werte dieses Parameters typischerweise sehr langsame Konveregenz. Die Konvergenztheorie wird auf einen allgemeinen Konvergenzsatz aufgebaut, der auf eine große Klasse von Methoden anwendbar ist. Der Konvergenzbeweis selbst folgt klassischen Ideen und ist auf der von Hackbusch eingeführten Aufspaltung in Glättungs- und Approximationseigenschaft aufgebaut. Danach wenden wir noch eine zweite Art der Konvergenzanalyse an: lokale Fourieranalyse. Dieser Ansatz erlaubt uns, scharfe Abschätzungen der Konveregenzrate zu bestimmen.In this thesis we construct and analyze multigrid methods for solving the optimality system characterizing the solution of an optimal control problem. Originally multigrid methods were constructed for elliptic problems. However, the (discretized) optimality system is not elliptic. We make use of the fact that the matrix is a block-matrix with saddle point structure: on the one hand we have two blocks of variables representing state and control. These two blocks are already part of the optimal control problem itself. On the other hand, the conversion to the optimality system requires the introduction of Lagrange multipliers, which form the third block of variables. There are several possibilities to use multigrid methods for constructing solvers for such saddle point problems. One approach to solve such problems is to apply multigrid methods in every step of an overall block-structured iterative method to equations in just one of these blocks of variables. Another approach, which we will follow here, is to apply the multigrid idea directly to the (reduced or not reduced) optimality system, which is called an all-at-once approach. The choice of an appropriate smoother is the key issue in constructing such a multigrid method. The other part of the method - the coarse-grid correction - can be set up in a canonical way because we will use a framework of conforming geometric multigrid method. In this framework the smoother will be constructed such that the convergence rates are independent of the grid level. This leads to an overall computational complexity that is linear in the number of unknowns which is called an optimal convergence. For a sub-class of the class of problems we will introduce in a first point, we will go one step further and construct methods where the convergence rates are also robust in a certain regularization or cost parameter which is part of the problem. Moreover, we will show this fact. ^Methods that do not take this into account typically show quite poor convergence rates if this parameter attains small values. For the analysis, we will introduce a general framework that is based on Hackbusch's splitting of the analysis into smoothing and approximation property. This allows to give general convergence theorems for the methods under investigation. A second point we consider is local Fourier analysis which allows to compute sharp bounds of the convergence rates.eingereicht von: Stefan TakacsLinz, Univ., Diss., 2012OeBB(VLID)456592