Function Space Complementarity Methods for Optimal Control Problems

Abstract

For the solution of optimal control problems, either direct or indirect methods are currently used. Indirect methods require insight into the problem structure and cumbersome analytic preparation, whereas direct methods lose the firm grip on the continuous problem due to premature discretization. This thesis is intended to close the gap by combining ideas of both direct and indirect methods.

Interior point methods turned out to be very efficient methods for solving linear programs, in particular for large scale problems. Therefore, this type of method seems to be very attractive for formulating function space algorithms. For this work, closely related complementarity methods are chosen, since they permit infeasible iterates.

The central path, which is defined by the complementarity method, can be followed by a continuation method up to the solution. It turns out that the nonlinear equations that must be solved by the Newton corrector are continuously differentiable only with respect to the L? norm, while the central path converges to the solution only in the weaker L2 norm. For this reason, both norms must be considered in theory and implementation.

Formulating the continuation method in function space requires the development of an inexact pathfollowing method due to the inevitable discretization errors. The adaptive stepsize selection is based on a problem-adapted norm that takes the special affine invariance of optimization problems into account.

The proposed method is robust and able to solve intricate problems to high accuracy. The main advantage is, that neither a-priori knowledge of the switching structure nor analytic preparation are necessary.

Für Probleme der optimalen Steuerung werden gegenwärtig entweder direkte oder indirekte Verfahren eingesetzt. Während die indirekten Methoden Einsicht in die Problemstruktur und eine aufwendige analytische Vorarbeit erfordern, lassen direkte Methoden durch die frühzeitige Diskretisierung die Einbettung in das kontinuierliche Problem vermissen. Die vorliegende Arbeit ist ein Ansatz, diese Lücke zu schließen.

Da sich Innere-Punkte-Methoden zur Lösung linearer Programme gerade bei hochdimensionalen Problemen bewähren, erscheint diese Verfahrensklasse für die Formulierung eines Algorithmus im Funktionenraum besonders attraktiv. Dabei fällt die Wahl auf Komplementaritätsmethoden, die auch nichtzulässige Iterierte erlauben.

Dem durch die Komplementaritätsmethoden definierten zentralen Pfad kann mittels eines Pfadverfolgungsalgorithmus bis zur Lösung gefolgt werden. Dabei stellt sich heraus, daß die durch einen Newton-Korrektor zu lösenden Gleichungen nur in der L?-Norm stetig differenzierbar sind, der zentrale Pfad jedoch nur in der schwächeren L2-Norm konvergiert. Daher muß in Theorie und Implementierung mit beiden Normen gearbeitet werden.

Die Formulierung der Homotopiemethode im Funktionenraum erfordert wegen der unvermeidlichen Diskretisierungsfehler die Entwicklung eines inexakten Newtonverfahrens als Korrektor und ebenso eines inexakten tangentialen Prädiktors. Die adaptive Steuerung verwendet dabei eine problemangepaßte Norm, die die spezielle Affin-Invarianzstruktur von Optimierungsproblemen berücksichtigt.

Die vorgeschlagene Methode ist robust und in der Lage, auch schwierige Probleme zu lösen. Dabei ist ein besonderer Vorteil, daß weder Vorwissen über die Lösungsstruktur noch analytische Vorarbeit erforderlich sind.