Fast numerical methods for mixed-integer nonlinear model-predictive control [Elektronische Ressource] / vorgelegt von Christian Kirches

Sujets

• Mathematics

Informations

• Publié par: ruprecht-karls-universitat_heidelberg
• Publié le: 01 janvier 2010
• Nombre de lectures: 22
• Langue: Deutsch
• Poids de l'ouvrage: 4 Mo

Extrait

I N A U G U R A L – D I S S E R TAT I O N
zur
Erlangung der Doktorwürde
der
Naturwissenschaftlich–Mathematischen Gesamtfakultät
der
R U P R E C H T– K A R L S – U N I V E R S I T Ä T
H E I D E L B E R G
vorgelegt von
Dipl.–Math. Christian Kirches
aus Kandel in Rheinland–Pfalz
Tag der mündlichen Prüfung
2. November 2010Fast Numerical Methods for
Mixed–Integer Nonlinear Model–Predictive Control
Gutachter
PROFESSOR DR. DR. H.C. HANS GEORG BOCK
PROFESSOR DR. GERHARD REINELTivZusammenfassung
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 Neben-
bedingungen 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 strukturausnutzen-
de Techniken der linearen Algebra entwickelt, um die echtzeitfähige Berechnung von Steuerungsant-
worten zu ermöglichen. Die Anwendbarkeit der entwickelten Methoden wird anhand mehrerer Pro-
blemstellungen 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 Echtzeit-
iterationsschemas 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 her-
gestellt 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 Punktbedin-
gungen 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 verschwinden-
den 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 entstehen-
den nichtkonvexen quadratischen Teilprobleme werden beschrieben. Der letztgenannten liegen
starke Stationaritätsbedingungen für MPVC unter gewissen Regularitätsannahmen zugrunde.
Eine Heuristik zur Verbesserung der erhaltenen stark stationären Punkte bis zu globaler Opti-
malität für die quadratischen Teilprobleme wird vorgestellt.
Die Verzögerung der Steuerungsantworten des gemischt–ganzzahligen Echtzeititerationssche-
mas — 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 aus-
gelegte strukturausnutzende Zerlegung beschrieben. Sie weist eine bei langen Horizonten oder
vielen Steuerungsparametern vorteilhafte Laufzeitkomplexität auf und wird erstmals auf Um-
formulierungen 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 Ord-
nung.
Alle entwickelten Algorithmen sind in einem neuen Programmpaket umgesetzt. Es erlaubt die ef-
fiziente Lösung allgemeiner nichtlinearer gemischt–ganzzahliger Probleme der optimalen Steu-
erung und der modell–prädiktiven Regelung mittels der vorgestellten Methoden.
vviAbstract
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 Sequential
Quadratic Programming 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 Mathematical Program with
Vanishing Constraints, a young and challenging class of nonconvex problems.
We describe a Sequential Quadratic Programming method and develop a new parametric ac-
tive set method for the arising nonconvex quadratic subproblems. This method is based on
strong stationarity conditions for Mathematical Program with Vanishing Constraints under cer-
tain 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 com-
plexity 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, ef-
ficient solution of nonlinear mixed–integer optimal control and model–predictive control prob-
lems using the developed methods.
viiviiiDanksagung
Mein tief empfundener Dank gilt meinen Lehrern und Mentoren Professor Dr. Dr. h.c. Hans
Georg Bock, Professor Dr. Gerhard Reinelt, Dr. Sebastian Sager und Dr. Johannes P. Schlöder für
ihre jederzeit hervorragende Unterstützung. Ihr umfangreiches Wissen bildet die unverzicht-
bare Grundlage dieser Dissertation. Durch ihren offenen und herzlichen Umgang sowie die
freundschaftliche und kooperative Atmosphäre in ihren Arbeitsgruppen war meine Arbeit in
den vergangenen drei Jahren ein Vergnügen.
Zahlreiche Mitglieder der Arbeitsgruppe Simulation und Optimierung haben zum Entstehen
und Gelingen dieser Arbeit beigetragen. Unter ihnen möchte ich besonders Jan Albersmeyer,
Dörte Beigel, Chris Hoffmann, Andreas Potschka und Leo Wirsching hervorheben, die bei unzäh-
ligen Tassen Kaffee mit ihren Ideen in vielen Diskussionen am Fortschritt dieser Arbeit beteiligt
waren. Auch Alexander Buchner und Florian Kehrle haben während ihrer Diplomarbeiten in der
Nachwuchsforschungsgruppe Mathematical and Computational Optimization wertvolle Beiträ-
ge geleistet.
Für ihre ausführliche Unterstützung beim Korrekturlesen dieser Arbeit danke ich Sebastian
Sager und Johannes Schlöder. Die Verantwortung für eventuell verbliebene Unzulänglichkeiten
liegt bei mir. Margret Rothfuss und Thomas Klöpfer danke ich herzlich für ihre wertvolle Hilfe
in allen organisatorischen und technischen Belangen.
Die Ruprecht–Karls–Universität Heidelberg, das Steinbeis–Transferzentrum 582 „Simulation und
Optimierung“, die Heidelberger Graduiertenschule der mathematischen und computergestützten
Methoden für die Wissenschaften sowie das 7. Forschungsrahmenprogramm der Europäischen
Union unter Antrag FP7-ICT-2009-4 248940 haben diese Arbeit finanziell unterstützt.
Meinen Eltern Claus und Ulrike sowie meinen Geschwistern Michael und Anja danke ich für
ihre Liebe und Unterstützung, mit der sie mich durch Studium und Doktorarbeit begleitet
haben.
Von Herzen danke ich meiner Freundin Simone Evke für ihre Liebe und ihre Geduld, wenn
ihr Freund einmal wieder nur Dreiecke im Ko