German Title: Effiziente numerische Methoden für die hierarchische dynamische Optimierung mit Anwendung bei der Modellierung von Zerebralparese-Gangarten

Preview

PDF, English Download (17MB) | Terms of use

Abstract

This thesis aims at developing efficient mathematical methods for solving hierarchical dynamic optimization problems. The main motivation is to model processes in nature, for which there is evidence to assume that they run optimally. We describe models of such processes by optimal control problems (called optimal control models (OCMs)). However, an OCM typically includes unknown parameters that cannot be derived entirely on a theoretical basis, which is in particular the case for the cost function. Therefore, we develop parameter estimation techniques to estimate the unknowns in an OCM from observation data of the process. Mathematically, this leads to a hierarchical dynamic optimization problem with a parameter estimation problem on the upper level and an optimal control problem on the lower level. We focus on multi-stage equality and inequality constrained optimal control problems based on nonlinear ordinary differential equations. The main goal of this thesis is to derive numerically efficient mathematical methods for solving hierarchical dynamic optimization problems, and to use these methods to estimate parameters in high-dimensional OCMs from real-world measurement data. We develop parameter-dependent OCMs for the gait of cerebral palsy patients and able-bodied subjects. The unknown parameters in the OCMs are then estimated from real-world motion capture data provided by the Heidelberg MotionLab of the Orthopedic University Clinic Heidelberg by using the mathematical methods developed within this work.

The main novelties and contributions of this thesis to the field of hierarchical dynamic optimization are summarized herein.

- We establish a novel mathematical method, a so-called direct all-at-once approach, for solving hierarchical dynamic optimization problems based on the direct multiple shooting method and first-order optimality conditions.

- Furthermore, we propose an efficient numerical algorithm for large-scale hierarchical dynamic optimization problems, which fully exploits the structures inherited from both the hierarchical setting and the discretization.

- Pontryagin's maximum principle is used to analyze solution properties of hierarchical dynamic optimization problems like second-order optimality conditions of the lower-level problem.

- In addition, we propose and discuss alternative methods for hierarchical dynamic optimization that are based on derivative-free optimization and a bundle approach. These methods keep the hierarchical problem setting and do not reformulate the lower-level problem using first-order optimality conditions.

- We establish a novel lifting method for regularizing mathematical programs with complementarity constraints, which is discussed and numerically investigated by means of a well-known collection of benchmark problems.

- Proofs of regularity and convergence results for sequential quadratic programming methods applied to lifted mathematical programs with complementarity constraints are provided.

- Efficient state-of-the-art implementations of all mathematical methods derived in this thesis, as well as a benchmark collection of hierarchical dynamic optimization problems are presented.

- High-dimensional optimal control gait models for cerebral palsy patients and able-bodied subjects are developed. The mathematical methods derived in this thesis are used to estimate the unknown model parameters from real-world motion capture data provided by the Heidelberg MotionLab of the Orthopedic University Clinic Heidelberg.

The theoretical and practical results presented in this thesis can be considered an initial motivating step towards answering open questions in current medical research in fields like treatment planning, classification of gaits, or the evaluation of surgeries by means of hierarchical dynamic optimization.

Translation of abstract (German)

Das Ziel der vorliegenden Arbeit ist die Entwicklung effizienter mathematischer Methoden zum Lösen von hierarchischen dynamischen Optimierungsproblemen. Hierbei ist die zugrundeliegende Motivation die Modellierung von dynamischen Prozessen in der Natur, welche der begründeten Annahme unterliegen, dass sie optimal ablaufen. Modelle solcher Prozesse beschreiben wir durch Optimalsteuerungsprobleme (sogenannte Optimalsteuerungsmodelle (OSM)). Jedoch enthalten OSM häufig Parameter, die nicht vollständig auf theoretischer Ebene hergeleitet werden können, was insbesondere für die Kostenfunktion gilt. Daher werden in der vorliegenden Arbeit Parameterschätztechniken zur Bestimmung der unbekannten Größen des OSM aus Beobachtungsdaten des Prozesses entwickelt. Mathematisch führt dies zu einem hierarchischen dynamischen Optimierungsproblem, das aus einem Parameterschätzproblem auf der oberen Ebene und einem parameterabhängigen Optimalsteuerungsproblem auf der unteren Ebene besteht. Hierbei betrachten wir mehrphasige gleichungs- und ungleichungsbeschränkte Optimalsteuerungsprobleme basierend auf nichtlinearen gewöhnlichen Differentialgleichungen.

Die wesentlichen Ziele dieser Arbeit umfassen die Entwicklung numerisch effizienter mathematischer Methoden zum Lösen von hierarchischen dynamischen Optimierungsproblemen und die Anwendung dieser Methoden zur Schätzung von Parametern in hochdimensionalen OSM aus realen Messdaten. Genauer werden parameterabhängige OSM für den Gang von Zerebralparesepatienten und nicht behinderten Probanden entwickelt. Die in den OSM enthaltenen unbekannten Parameter werden dann aus realen Bewegungserfassungsdaten des Ganganalyselabors Heidelberg MotionLab der Orthopädischen Universitätsklinik Heidelberg mit den entwickelten mathematischen Methoden geschätzt.

Die wesentlichen Neuerungen und Beiträge dieser Arbeit im Gebiet der hierarchischen dynamischen Optimierung sind im Folgenden zusammengefasst.

- Basierend auf der direkten Mehrzielmethode und Optimalitätsbedingungen erster Ordnung wird eine neuartige mathematische Methode, ein sogenannter direkter simultaner Ansatz, zum Lösen von hierarchischen dynamischen Optimierungsproblemen entwickelt.

- Zusätzlich wird ein effizienter numerischer Algorithmus für große hierarchische nichtlineare dynamische Optimierungsprobleme vorgestellt, der die von Diskretisierung und Mehrstufigkeit vererbten Strukturen vollständig ausnutzt.

- Pontrjagins Maximumprinzip dient als Basis für die Analyse von Eigenschaften der Lösungen von hierarchischen dynamischen Optimierungsproblemen, wie beispielsweise die Erfüllung von Optimalitätsbedingungen zweiter Ordnung auf der unteren Problemebene.

- Des Weiteren werden alternative Methoden zur hierarchischen dynamischen Optimierung vorgestellt und diskutiert, die die zweistufige Problemstellung beibehalten und das unterliegende Problem nicht durch Optimalitätsbedingungen erster Ordnung charakterisieren. Die Methoden basieren auf ableitungsfreier Optimierung und einem Subgradientenverfahren.

- Eine neuartige Liftingmethode zur Regularisierung von mathematischen Programmen mit Komplementaritätsnebenbedingungen wird entwickelt, ausführlich diskutiert und mithilfe einer anerkannten Kollektion an Testproblemen numerisch untersucht.

- Beweise für Regularitäts- und Konvergenzresultate für die sequentielle quadratische Programmierung angewendet auf geliftete mathematische Programme mit Komplementaritätsnebenbedingungen werden vorgestellt.

- Effiziente state-of-the-art Implementierungen aller im Rahmen dieser Arbeit entwickelten Algorithmen, sowie eine als Benchmark dienende Problemsammlung von hierarchischen dynamischen Optimierungsproblemen werden erstellt.

- Hochdimensionale OSM für den Gang von Zerebralparesepatienten und nicht behinderten Probanden werden entwickelt. Basierend auf den in dieser Arbeit hergeleiteten mathematischen Methoden werden unbekannte Modellparameter aus echten Bewegungserfassungsdaten des Ganganalyselabors Heidelberg MotionLab der Orthopädischen Universitätsklinik Heidelberg geschätzt.

Die in dieser Arbeit vorgestellten theoretischen und praktischen Resultate können als erster und motivierender Schritt in Richtung der Beantwortung offener aktueller Forschungsfragen der Medizin in Bereichen wie der Behandlungsplanung, der Klassifizierung von Gangarten, oder der Evaluation von Behandlungsresultaten durch die hierarchische dynamische Optimierung gesehen werden.