Directly to content
  1. Publishing |
  2. Search |
  3. Browse |
  4. Recent items rss |
  5. Open Access |
  6. Jur. Issues |
  7. DeutschClear Cookie - decide language by browser settings

Sequential quadratic programming with indefinite Hessian approximations for nonlinear optimum experimental design for parameter estimation in differential–algebraic equations

Janka, Dennis

[img]
Preview
PDF, English
Download (2MB) | Terms of use

Citation of documents: Please do not cite the URL that is displayed in your browser location input, instead use the DOI, URN or the persistent URL below, as we can guarantee their long-time accessibility.

Abstract

In this thesis we develop algorithms for the numerical solution of problems from nonlinear optimum experimental design (OED) for parameter estimation in differential–algebraic equations. These OED problems can be formulated as special types of path- and control- constrained optimal control (OC) problems. The objective is to minimize a functional on the covariance matrix of the model parameters that is given by first-order sensitivities of the model equations. Additionally, the objective is nonlinearly coupled in time, which make OED problems a challenging class of OC problems. For their numerical solution, we propose a direct multiple shooting parameterization to obtain a structured nonlinear programming problem (NLP). An augmented system of nominal and variational states for the model sensitivities is parameterized on multiple shooting intervals and the objective is decoupled by means of additional variables and constraints. In the resulting NLP, we identify several structures that allow to evaluate derivatives at greatly reduced costs compared to a standard OC formulation. For the solution of the block-structured NLPs, we develop a new sequential quadratic programming (SQP) method. Therein, partitioned quasi-Newton updates are used to approximate the block-diagonal Hessian of the Lagrangian. We analyze a model problem with indefinite, block-diagonal Hessian and prove that positive definite approximations of the individual blocks prevent superlinear convergence. For an OED model problem, we show that more and more negative eigenvalues appear in the Hessian as the multiple shooting grid is refined and confirm the detrimental impact of positive definite Hessian approximations. Hence, we propose indefinite SR1 updates to guarantee fast local convergence. We develop a filter line search globalization strategy that accepts indefinite Hessians based on a new criterion derived from the proof of global convergence. BFGS updates with a scaling strategy to prevent large eigenvalues are used as fallback if the SR1 update does not promote convergence. For the solution of the arising sparse and nonconvex quadratic subproblems, a parametric active set method with inertia control within a Schur complement approach is developed. It employs a symmetric, indefinite LBL T -factorization for the large, sparse KKT matrix and maintains and updates QR-factors of a small and dense Schur complement. The new methods are complemented by two C++ implementations: muse transforms an OED or OC problem instance to a structured NLP by means of direct multiple shooting. A special feature is that fully independent grids for controls, states, path constraints, and measurements are maintained. This provides higher flexibility to adapt the NLP formulation to the characteristics of the problem at hand and facilitates comparison of different formulations in the light of the lifted Newton method. The software package blockSQP is an implementation of the new SQP method that uses a newly developed variant of the quadratic programming solver qpOASES. Numerical results are presented for a benchmark collection of OED and OC problems that show how SR1 approximations improve local convergence over BFGS. The new method is then applied to two challenging OED applications from chemical engineering. Its performance compares favorably to an available existing implementation.

Translation of abstract (German)

In dieser Arbeit entwickeln wir Algorithmen zur numerischen Lösung von Problemen der nichtlinearen optimalen Versuchsplanung zur Parameterschätzung in differential–algebraischen Gleichungen. Diese Probleme können als spezielle, steuerungs- und pfadbeschränkte Probleme der optimalen Steuerung formuliert werden. Als Zielfunktion wird ein Funktional auf der Kovarianzmatrix der Modellparameter minimiert, wobei die Kovarianzmatrix durch Sensitivitäten erster Ordnung der Modellgleichungen gegeben ist. Zusätzlich ist die Zielfunktion nichtlinear in der Zeit gekoppelt, weshalb Probleme der optimalen Versuchsplanung eine schwierige Klasse von Optimalsteuerungsproblemen darstellen. Zur numerischen Lösung schlagen wir eine Parametrisierung mittels der direkten Mehrzielmethode vor, die auf ein strukturiertes Problem der nichtlinearen Programmierung (NLP) führt. Ein erweitertes System von Nominal- und Variationszuständen für die Modellsensitivitäten wird auf Mehrzielintervallen parametrisiert und die Zielfunktion mit Hilfe von zusätzlichen Variablen und Nebenbedingungen entkoppelt. Im resultierenden NLP identifizieren wir verschiedene Strukturen, die eine wesentlich effizientere Auswertung von Ableitungen erlauben im Vergleich zu einem Ansatz für herkömmliche Optimalsteuerungsprobleme. Zur Lösung der blockstrukturierten NLPs entwickeln wir eine neue Methode der sequentiellen quadratischen Programmierung (SQP). In dieser werden partitionierte quasi-Newton Updates verwendet um die Hessematrix der Lagrange-Funktion zu approximieren, welche Blockdiagonalstruktur besitzt. Wir analysieren ein Modellproblem mit indefiniter blockdiagonaler Hessematrix und beweisen, dass positiv definite Approximationen der einzelnen Blöcke superlineare Konvergenz verhindern. Für ein Modellproblem der optimalen Versuchsplanung zeigen wir, dass, wenn das Mehrzielgitter verfeinert wird, in der Hessematrix immer mehr negative Eigenwerte auftauchen und bestätigen die negativen Auswirkungen positiv definiter Hessematrix Approximationen auf die Konvergenzgeschwindigkeit. Wir schlagen daher vor, indefinite SR1 Updates zu verwenden, die schnelle lokale Konvergenz garantieren. Wir entwickeln eine Filter-Liniensuche Globalisierungsstrategie, welche indefinite Hessematrizen akzeptiert. Dies basiert auf einem Kriterium, das aus dem globalen Konvergenzbeweis der Liniensuche abgeleitet ist. BFGS Updates mit einer Skalierungsstrategie, die zu große Eigenwerte verhindert, werden als Ausweichstrategie eingesetzt, falls die SR1 Updates die Konvergenz nicht begünstigen. Zur Lösung der anfallenden dünnbesetzten und nichtkonvexen quadratischen Teilprobleme wird eine parametrische Aktive-Mengen-Methode mit einer Steuerung des Trägheitsindex innerhalb eines Schur Komplement Ansatzes entwickelt. Die Methode benutzt eine symmetrische, indefinite LBL T -Faktorisierung der großen, dünnbesetzten KKT Matrix und verwaltet und modifiziert QR-Faktoren eines kleinen, dichtbesetzten Schur Komplements. Die neuen Methoden werden durch zwei C++ Implementierungen ergänzt: muse transformiert ein Problem der optimalen Versuchsplanung oder der optimalen Steuerung in ein strukturiertes NLP mittels der direkten Mehrzielmethode. Ein spezielles Merkmal der neuen Implementierung ist, dass vollständig unabhängige Gitter für die Parametrisierung derSteuerungen, Zustände, Pfadbeschränkungen und Messzeitpunkte eingesetzt werden. Dies bietet eine höhere Flexibilität um die NLP Formulierung den Charakteristiken des konkreten Problems anzupassen und ermöglicht es, verschiedene Formulierungen im Lichte des Lifted Newton Verfahrens zu untersuchen. Das Softwarepaket blockSQP ist eine Implementierung der neuen SQP Methode und benutzt eine neu entwickelte Variante des quadratischen Lösers qpOASES. Numerische Ergebnisse für eine Kollektion von Testbeispielen der optimalen Versuchsplanung und optimalen Steuerung werden präsentiert, die zeigen, dass SR1 Approximationen die lokale Konvergenz gegenüber BFGS verbessern. Die neue Methode wird dann auf zwei schwierige Probleme der optimalen Versuchsplanung aus der chemischen Verfahrenstechnik angewandt und erweist sich als schneller als eine erhältliche vorhandene Implementierung.

Item Type: Dissertation
Supervisor: Körkel, Dr. Stefan
Date of thesis defense: 23 July 2015
Date Deposited: 31 Jul 2015 08:20
Date: 2015
Faculties / Institutes: The Faculty of Mathematics and Computer Science > Department of Applied Mathematics
Subjects: 510 Mathematics
Controlled Keywords: Sequentielle quadratische Optimierung, Optimale Versuchsplanung
About | FAQ | Contact | Imprint |
OA-LogoDINI certificate 2013Logo der Open-Archives-Initiative