eprintid: 19744 rev_number: 14 eprint_status: archive userid: 2155 dir: disk0/00/01/97/44 datestamp: 2015-11-06 09:33:09 lastmod: 2015-11-10 08:13:59 status_changed: 2015-11-06 09:33:09 type: doctoralThesis metadata_visibility: show creators_name: Diedam, Holger title: Global Optimal Control Using Direct Multiple Shooting subjects: 500 subjects: 510 divisions: 110001 divisions: 708000 adv_faculty: af-11 abstract: The goal of this thesis is the development of a novel and efficient algorithm to determine the global optimum of an optimal control problem. In contrast to previous methods, the approach presented here is based on the direct multiple shooting method for discretizing the optimal control problem, which results in a significant increase of efficiency. To relax the discretized optimal control problems, the so-called alpha-branch-and-bound method in combination with validated integration is used. For the direct comparison of the direct single-shooting-based relaxations with the direct multipleshooting-based algorithm, several theoretical results are proven that build the basis for the efficiency increase of the novel method. A specialized branching strategy takes care that the additionally introduced variables due to the multiple shooting approach do not increase the size of the resulting branch-and-bound tree. An adaptive scaling technique of the commonly used Gershgorin method to estimate the eigenvalues of interval matrices leads to optimal relaxations and therefore leads to a general improvement of the alpha-branch-and-bound relaxations in a single shooting and a multiple shooting framework, as well as for the corresponding relaxations of non-dynamic nonlinear problems. To further improve the computational time, suggestions regarding the necessary second-order interval sensitivities are presented in this thesis, as well as a heuristic that relaxes on a subspace only. The novel algorithm, as well as the single-shooting-based alternative for a direct comparison, are implemented in a newly developed software package called GloOptCon. The new method is used to globally solve both a number of benchmark problems from the literature, and so far in the context of global optimal control still little considered applications. The additional problems pose new challenges either due to their size or due to having its origin in mixed integer optimal control with an integer-valued time-dependent control variable. The theoretically proven increase of efficiency is validated by the numerical results. Compared to the previous approach from the literature, the number of iterations for typical problems is more than halved, meanwhile the computation time is reduced by almost an order of magnitude. This in turn allows the global solution of significantly larger optimal control problems. abstract_translated_text: Das Ziel dieser Dissertation ist die Entwicklung eines neuen Algorithmus zur effizienten Bestimmung des globalen Optimums von Optimalsteuerungsproblemen. Im Unterschied zu bisherigen Methoden basiert dieser hier vorgestellte Ansatz auf dem direkten Mehrzielverfahren zur Diskretisierung des Optimalsteuerungsproblems, was in einer signifikanten Steigerung der Effizienz resultiert. Zur Relaxierung des diskretisierten Optimalsteuerungsproblems wird das sogenannte alpha-Branch-and-Bound Verfahren in Kombination mit validierter Integration verwendet. Zum direkten Vergleich der auf dem direkten Einzielverfahren beruhenden Relaxierungen mit dem auf der direkten Mehrzielmethode basierenden Algorithmus werden mehrere theoretische Resultate bewiesen, die die Basis für die Effizienzsteigerung der neuen Methodik bilden. Eine speziell angepasste Branching-Strategie sorgt außerdem dafür, dass die durch das Mehrzielverfahren zusätzlich eingeführten Variablen den entstehenden Branch-and-Bound Baum nicht vergrößern. Des Weiteren wird eine adaptive Skalierung der verbreiteten Gershgorin Methode zur Abschätzung der Eigenwerte von Intervallmatrizen vorgestellt, die optimierte Relaxierungen liefert und damit allgemein zur Verbesserung der alpha-Branch-and-Bound Relaxierungen sowohl im Einziel- und Mehrzielverfahren beiträgt, als auch auf entsprechende Relaxierungen für nicht dynamische nichtlineare Probleme übertragbar ist. Zur weiteren Verbesserung der Laufzeit werden in dieser Arbeit außerdem noch Vorschläge im Bezug auf die benötigten Intervallsensitivitäten zweiter Ordnnung gemacht und eine Heuristik vorgestellt, welche nur auf einem bestimmten Unterraum relaxiert. Der neu entwickelte Algorithmus ist, ebenso wie die auf dem Einzielverfahren basierte Alternative für den direkten Vergleich, in einem neu entwickelten Softwarepaket mit dem Namen GloOptCon implementiert. Das neue Verfahren wird genutzt um für eine Reihe von Benchmarkproblemen aus der Literatur und für bisher im Rahmen der globalen Optimalsteuerung noch wenig betrachteten Anwendungen das globale Optimum zu bestimmen. Die zusätzlich untersuchten Probleme stellen neue Herausforderungen, sowohl im Sinne der Größe, als auch dadurch, dass eines dieser Probleme seinen Ursprung in den sogenannten gemischt ganzzahligen Optimalsteuerungsproblemen hat, da es eine ganzzahlige zeitabhängige Steuerungsvariable enthält. Der bereits theoretisch bewiesene Effizienzgewinn wird durch die numerischen Ergebnisse bestätigt. Verglichen mit dem bisherigem Ansatz aus der Literatur wird die Anzahl der benötigten Iterationen für typische Probleme mehr als halbiert, während die Rechenzeit sogar um fast eine Größenordnung reduziert werden konnte. Dies wiederum erlaubt die globale Lösung von deutlich größeren Optimalsteuerungsproblemen. abstract_translated_lang: ger date: 2015 id_scheme: DOI id_number: 10.11588/heidok.00019744 ppn_swb: 1658861302 own_urn: urn:nbn:de:bsz:16-heidok-197449 date_accepted: 2015-10-30 advisor: HASH(0x5561209d3df0) language: eng bibsort: DIEDAMHOLGGLOBALOPTI2015 full_text_status: public citation: Diedam, Holger (2015) Global Optimal Control Using Direct Multiple Shooting. [Dissertation] document_url: https://archiv.ub.uni-heidelberg.de/volltextserver/19744/1/Dissertation_Holger_Diedam.pdf