Deutsche Übersetzung des Titels: Schnelle numerische Methoden zur gemischt-ganzzahligen nichtlinearen modell-prädiktiven Regelung

Vorschau

PDF, Englisch Download (5MB) | Nutzungsbedingungen

Abstract

This thesis aims at the investigation and development of fast numerical methods for nonlinear mixed--integer optimal control and model- predictive control problems. A new algorithm is developed based on the direct multiple shooting method for optimal control and on the idea of real--time iterations, and using a convex reformulation and relaxation of dynamics and constraints of the original predictive control problem. This algorithm relies on theoretical results and is based on a nonconvex SQP method and a new active set method for nonconvex parametric quadratic programming. It achieves real--time capable control feedback though block structured linear algebra for which we develop new matrix updates techniques. The applicability of the developed methods is demonstrated on several applications. This thesis presents novel results and advances over previously established techniques in a number of areas as follows: We develop a new algorithm for mixed--integer nonlinear model- predictive control by combining Bock's direct multiple shooting method, a reformulation based on outer convexification and relaxation of the integer controls, on rounding schemes, and on a real--time iteration scheme. For this new algorithm we establish an interpretation in the framework of inexact Newton-type methods and give a proof of local contractivity assuming an upper bound on the sampling time, implying nominal stability of this new algorithm. We propose a convexification of path constraints directly depending on integer controls that guarantees feasibility after rounding, and investigate the properties of the obtained nonlinear programs. We show that these programs can be treated favorably as MPVCs, a young and challenging class of nonconvex problems. We describe a SQP method and develop a new parametric active set method for the arising nonconvex quadratic subproblems. This method is based on strong stationarity conditions for MPVCs under certain regularity assumptions. We further present a heuristic for improving stationary points of the nonconvex quadratic subproblems to global optimality. The mixed--integer control feedback delay is determined by the computational demand of our active set method. We describe a block structured factorization that is tailored to Bock's direct multiple shooting method. It has favorable run time complexity for problems with long horizons or many controls unknowns, as is the case for mixed- integer optimal control problems after outer convexification. We develop new matrix update techniques for this factorization that reduce the run time complexity of all but the first active set iteration by one order. All developed algorithms are implemented in a software package that allows for the generic, efficient solution of nonlinear mixed-integer optimal control and model-predictive control problems using the developed methods.

Übersetzung des Abstracts (Deutsch)

Das Ziel der vorliegenden Arbeit ist die Untersuchung und Entwicklung numerischer Methoden zur schnellen Lösung nichtlinearer gemischt- ganzzahliger Probleme der optimalen Steuerung und der modell- prädiktiven Regelung. Aufbauend auf einer direkten Methode zur optimalen Steuerung und einer Konvexifizierung und Relaxierung der von ganzzahligen Größen abhängigen Dynamik und Nebenbedingungen wird dazu ein neuer Algorithmus entwickelt. Dieser ist durch theoretische Resultate motiviert und beinhaltet eine nichtkonvexe SQP-Methode, deren Teilprobleme mittels einer neuen nichtkonvexen parametrischen Active- Set-Methode gelöst werden. Es werden neue strukturausnutzende Techniken der linearen Algebra entwickelt, um die echtzeitfähige Berechnung von Steuerungsantworten zu ermöglichen. Die Anwendbarkeit der entwickelten Methoden wird anhand mehrerer Problemstellungen gezeigt. Die vorliegende Arbeit beinhaltet theoretische und algorithmische Neuerungen auf mehreren Gebieten: Auf der Grundlage von Bocks direkter Mehrzielmethode, einer Reformulierung der ganzzahligen Größen mittels Konvexifizierung und Relaxierung, Rundungsheuristiken, sowie eines Echtzeititerationsschemas wird ein neuer Algorithmus zur gemischt-ganzzahligen nichtlinearen modell-prädiktiven Regelung entwickelt. Für diesen Algorithmus wird eine Verbindung zu inexakten Newton- ähnlichen Verfahren hergestellt und lokale Kontraktivität - und damit nominelle Stabilität - bei hinreichend kleinem zeitlichem Abstand der Steuerungsantworten bewiesen. Eine Konvexifizierung der von ganzzahligen Steuergrößen abhängigen Pfad- und Punktbedingungen wird vorgeschlagen, welche die Zulässigkeit der gerundeten gemischt--ganzzahligen Lösung garantiert. Die durch diese Umformulierung erhaltenen nichtlinearen Probleme werden untersucht, und es wird gezeigt, dass sich diese als mathematische Probleme mit verschwindenden Nebenbedingungen, sogenannten MPVCs, behandeln lassen. Hierbei handelt es sich um eine noch junge und anspruchsvolle Klasse nichtkonvexer Probleme. Eine SQP-Methode und eine neue parametrische Active-Set-Methode zur Lösung der entstehenden nichtkonvexen quadratischen Teilprobleme werden beschrieben. Der letztgenannten liegen starke Stationaritätsbedingungen für MPVCs unter gewissen Regularitätsannahmen zugrunde. Eine Heuristik zur Verbesserung der erhaltenen stark stationären Punkte bis zu globaler Optimalität für die quadratischen Teilprobleme wird vorgestellt. Die Verzögerung der Steuerungsantworten des gemischt-ganzzahligen Echtzeititerationsschemas - und damit die Stabilität des gesteuerten Systems - wird entscheidend durch die Laufzeit der Active-Set-Methode bestimmt. Für diese wird eine auf Bocks direkte Mehrzielmethode ausgelegte strukturausnutzende Zerlegung beschrieben. Sie weist eine bei langen Horizonten oder vielen Steuerungsparametern vorteilhafte Laufzeitkomplexität auf und wird erstmals auf Umformulierungen gemischt- ganzzahliger Steuerungsprobleme angewendet. Darüber hinaus werden für die beschriebene Zerlegung neue Update- Techniken entwickelt. Sie ermöglichen die Verbesserung der Laufzeitkomplexität der Active-Set-Methode um eine Ordnung. Alle entwickelten Algorithmen sind in einem neuen Programmpaket umgesetzt. Es erlaubt die effiziente Lösung allgemeiner nichtlinearer gemischt-ganzzahliger Probleme der optimalen Steuerung und der modell- prädiktiven Regelung mittels der vorgestellten Methoden.