## Mathematisches Institut

### Refine

#### Document Type

- Doctoral Thesis (9)
- Lecture (1)

#### Keywords

- optimal control (2)
- Codierungstheorie (1)
- Computermodell (1)
- Decodierung (1)
- Evacuation modeling (1)
- Flow decomposition (1)
- Informationstheorie (1)
- Kanalcodierung (1)
- Kryptographie (1)
- Lendenwirbelsäule (1)

The formulation of the decoding problem for linear block codes as an integer program (IP) with a rather tight linear programming (LP) relaxation has made a central part of channel coding accessible for the theory and methods of mathematical optimization, especially integer programming, polyhedral combinatorics and also algorithmic graph theory, since the important class of turbo codes exhibits an inherent graphical structure. We present several novel models, algorithms and theoretical results for error-correction decoding based on mathematical optimization. Our contribution includes a partly combinatorial LP decoder for turbo codes, a fast branch-and-cut algorithm for maximum-likelihood (ML) decoding of arbitrary binary linear codes, a theoretical analysis of the LP decoder's performance for 3-dimensional turbo codes, compact IP models for various heuristic algorithms as well as ML decoding in combination with higher-order modulation, and, finally, first steps towards an implementation of the LP decoder in specialized hardware. The scientific contributions are presented in the form of seven revised reprints of papers that appeared in peer-reviewed international journals or conference proceedings. They are accompanied by an extensive introductory part that reviews the basics of mathematical optimization, coding theory, and the previous results on LP decoding that we rely on afterwards.

Scientific and public interest in epidemiology and mathematical modelling of disease spread has increased significantly due to the current COVID-19 pandemic. Political action is influenced by forecasts and evaluations of such models and the whole society is affected by the corresponding countermeasures for containment. But how are these models structured?
Which methods can be used to apply them to the respective regions, based on real data sets? These questions are certainly not new. Mathematical modelling in epidemiology using differential equations has been researched for quite some time now and can be carried out mainly by means of numerical computer simulations. These models are constantly being refinded and adapted to corresponding diseases. However, it should be noted that the more complex a model is, the more unknown parameters are included. A meaningful data adaptation thus becomes very diffcult. The goal of this thesis is to design applicable models using the examples of COVID-19 and dengue, to adapt them adequately to real data sets and thus to perform numerical simulations. For this purpose, first the mathematical foundations are presented and a theoretical outline of ordinary differential equations and optimization is provided. The parameter estimations shall be performed by means of adjoint functions. This procedure represents a combination of static and dynamical optimization. The objective function corresponds to a least squares method with L2 norm which depends on the searched parameters. This objective function is coupled to constraints in the form of ordinary differential equations and numerically minimized, using Pontryagin's maximum (minimum) principle and optimal control theory. In the case of dengue, due to the transmission path via mosquitoes, a model reduction of an SIRUV model to an SIR model with time-dependent transmission rate is performed by means of time-scale separation. The SIRUV model includes uninfected (U) and infected (V ) mosquito compartments in addition to the susceptible (S), infected (I) and recovered (R) human compartments, known from the SIR model. The unknwon parameters of the reduced SIR model are estimated using data sets from Colombo (Sri Lanka) and Jakarta (Indonesia). Based on this parameter estimation the predictive power of the model is checked and evaluated. In the case of Jakarta, the model is additionally provided with a mobility component between the individual city districts, based on commuter data. The transmission rates of the SIR models are also dependent on meteorological data as correlations between these and dengue outbreaks have been demonstrated in previous data analyses. For the modelling of COVID-19 we use several SEIRD models which in comparison to the SIR model also take into account the latency period and the number of deaths via exposed (E) and deaths (D) compartments. Based on these models a parameter estimation with adjoint functions is performed for the location Germany. This is possible because since the beginning of the pandemic, the cumulative number of infected persons and deaths
are published daily by Johns Hopkins University and the Robert-Koch-Institute. Here, a SEIRD model with a time delay regarding the deaths proves to be particularly suitable. In the next step, this model is used to compare the parameter estimation via adjoint functions with a Metropolis algorithm. Analytical effort, accuracy and calculation speed are taken into account. In all data fittings, one parameter each is determined to assess the estimated number of unreported cases.

In summary, this study revealed the widespread occurrence of antiviral drugs in the aquatic environment. Furthermore, it could be shown that the elimination of pharmaceuticals in both biological and oxidative treatment do not necessarily result in their mineralization but rather leads to the formation of a variety of transformation and oxidation products.
This is one of the first studies in which the fate and in particular the transformation of pharmaceuticals has been comprehensively investigated in almost the complete water cycle, from biological wastewater treatment to advanced oxidation processes via ozone. It was shown that the transformation of pharmaceuticals in the urban water cycle can ultimately result in the formation of toxic transformation products.

Die Wirbelsäule als tragende Säule des menschlichen Körpers ist bei vielen Bewegungsabläufen hohen Belastungen ausgesetzt. Fehl- und Überbelastungen rufen dabei oft dauerhafte Schädigungen hervor. Daher ist es von Interesse, die innerhalb der Wirbelsäule auftretenden Belastungen zu bestimmen. Eine moderne und zuverlässige Methode zur Belastungsbestimmung ist der Aufbau eines Berechnungsmodells.
In der vorliegenden Arbeit wurde ein Mehr-Körper-System (MKS) Modell der Lendenwirbelsäule erstellt. Mit Hilfe des Modells können sowohl die übertragenen Kräfte und Momente in allen inneren Strukturen berechnet als auch die Kinematik des Bewegungsablaufs simuliert werden. Die Grundstruktur des Modells bilden die als Starrkörper angenommenen knöchernen Strukturen der fünf Lendenwirbel L1 bis L5, des Os Sacrums und des Os iliums, die über die Segmentierung eines CT-Datensatzes des Abgusses der Wirbeloberflächen eines durchschnittlich großen Europäers gewonnen wurden. Die elastischen Elemente der Wirbelsäule wurden unter Berücksichtigung ihrer physikalischen Eigenschaften in das Modell implementiert. Grundlage für die Modellierung der Zwischenwirbelscheiben waren dabei eigens durchgeführte experimentelle Messungen. Das charakteristische Kraft-Deformations-Verhalten der Ligamente wurde der Literatur entnommen.
Die Umsetzung im Computermodell berücksichtigt neben dem physikalischen Verhalten eines einzelnen Ligamentes zusätzlich durch einen Gewichtungsfaktor das Zusammenspiel aller Ligamente im komplex aufgebauten Ligamentapparat. Die Facettengelenke wurden durch Kontaktmodellierung in den Knorpelschichten realisiert. Daneben wurde ein Modell eines Implantatsystems entwickelt, das zur dynamischen Stabilisierung der Lendenwirbelsäule genutzt wird. Die Validierung der erstellten Modelle erfolgte über den Vergleich mit In-Vitro erhobenen Daten. Betrachtet wurden neben der intakten Wirbelsäule zudem degenerative Schädigungen der Zwischenwirbelscheibe und deren operative Versorgung durch Nukleotomie und dynamische Stabilisierung. Die Ergebnisse der Simulationen zeigen dabei eine sehr gute Näherung an die experimentell ermittelten Messwerte. Durch Anwendung der Computermodelle konnten die Auswirkungen verschiedener operativer Eingriffe, wie Interlaminotomie, Hemilaminektomie und Laminektomie auf die unterschiedlichen Strukturen der Lendenwirbelsäule berechnet werden. Ein weiteres Anwendungsgebiet lag in der Untersuchung des momentanen Drehzentrums. Neben der Bestimmung der Drehpunktbahn bei intakter Wirbelsäule konnten die Effekte einer degenerativ geschädigten und operativ versorgten Zwischenwirbelscheibe auf den Verlauf des momentanen Drehzentrums berechnet und simuliert werden.

While reading this sentence, you probably gave (more or less deliberately) instructions to approximately 100 to 200 muscles of your body. A sceptical face or a smile, your fingers scrolling through the text or holding a printed version of this work, holding your head, sitting, and much more.
All these processes take place almost automatically, so they seem to be no real achievement. In the age of digitalization it is a defined goal to transfer human (psychological and physiological) behavior to machines (robots). However, it turns out that it is indeed laborious to obtain human facial expression or walking from robots. To optimize this transfer, a deeper understanding of a muscle's operating principle is needed (and of course an understanding of the human brain, which will, however, not be part of this thesis).
A human skeletal muscle can be shortened willingly, but not lengthened, thereto it takes an antagonist. The muscle's change in length is dependent on the incoming stimulus from the central nervous system, the current length of the muscle itself, and certain muscle--specific quantities (parameters) such as the maximum force. Hence, a muscle can be mathematically described by a differential equation (or more exactly a coupled differential--algebraic system, DAE), whose structure will be revealed in the following chapters. The theory of differential equations is well-elaborated. A multitude of applicable methods exist that may not be known by muscle modelers. The purpose of this work is to link the methods from applied mathematics to the actual application in biomechanics.
The first part of this thesis addresses stability theory. Let us remember the prominent example from middle school physics, in which the resting position of a ball was obviously less susceptible towards shoves when lying in a bowl rather than balancing at the tip of a hill. Similarly, a dynamical (musculo-skeletal) system can attain equilibrium states that react differently towards perturbations.
We are going to compute and classify these equilibria.
In the second part, we investigate the influence of individual parameters on model equations or more exactly their solutions. This method is known as sensitivity analysis.
Take for example the system "car" containing a value for the quantity "pressure on the break pedal while approaching a traffic light". A minor deviation of this quantity upward or downward may lead to an uncomfortable, abrupt stop or even to a collision, instead of a smooth stop with a sufficient gap.
The considered muscle model contains over 20 parameters that, if changed slightly, have varying effects on the model equation solutions at different instants of time. We will investigate the sensitivity of those parameters regarding different sub--models, as well as the whole model among different dynamical boundary conditions.
The third and final part addresses the \textit{optimal control} problem (OCP).
The muscle turns a nerve impulse (input or control) into a length change and therefore a force response (output). This forward process is computable by solving the respective DAE. The reverse direction is more difficult to manage. As an everyday example, the OCP is present regarding self-parking cars, where a given path is targeted and the controls are the position of the
steering wheel as well as the gas pedal.
We present two methods of solving OCPs in muscle modeling: the first is a conjunction of variational calculus and optimization in function spaces, the second is a surrogate-based optimization.

In Part I: "The flow-decomposition problem", we introduce and discuss the flow-decomposition problem. Given a flow F, this problem consists of decomposing the flow into a set of paths optimizing specific properties of those paths. We introduce different types of decompositions, such as integer decompositions and alpha-decompositions, and provide two formulations of the set of feasible decompositions.
We show that the problem of minimizing the longest path in a decomposition is NP-hard, even for fractional solutions. Then we develop an algorithm based on column generation which is able to solve the problem.
Tight upper bounds on the optimal objective value help to improve the performance.
To find upper bounds on the optimal solution for the shortest longest path problem, we develop several heuristics and analyze their quality. On pearl graphs we prove a constant approximation ratio of 2 and 3 respectively for all heuristics. A numerical study on random pearl graphs shows that the solutions generated by the heuristics are usually much better than this worst-case bound.
In Part II: "Construction and analysis of evacuation models using flows over time", we consider two optimization models in the context of evacuation planning. The first model is a parameter-based quickest flow model with time-dependent supply values. We give a detailed description of the network construction and of how different scenarios are modeled by scenario parameters. In a second step we analyze the effect of the scenario parameters on the evacuation time. Understanding how the different parameters influence the evacuation time allows us to provide better advice for evacuation planning and allows us to predict evacuation times without solving additional optimization problems. To understand the effect of the time-dependent supply values, we consider the quickest path problem with time-dependent supply values and provide a solution algorithm. The results from this consideration are generalized to approximate the behavior of the evacuation times in the context of quickest flow problems.
The second model we consider is a path-based model for evacuation in the presence of a dynamic cost function. We discuss the challenges of this model and provide ideas for how to approach the problem from different angles. We relate the problem to the flow-decomposition problem and consider the computation of evacuation paths with dynamic costs for large capacities. For the latter method we provide heuristics to find paths and compare them to the optimal solutions by applying the methods to two evacuation scenarios. An analysis shows that the paths generated by the heuristic yield close to optimal solutions and in addition have several desirable properties for evacuation paths which are not given for the optimal solution.

Gegeben sei eine Basis b>=10 und eine Ziffer a0 aus der Menge {0,..., b − 1}. Wir untersuchen, ob es unendlich viele Primzahlen gibt, die in ihrer b-adischen Zifferndarstellung die Ziffer a0 nicht besitzen. Ferner schätzen wir die Anzahl dieser Primzahlen, die kleiner sind als X = b^k, nach oben und unten ab.
Damit gelingt uns eine Verallgemeinerung von Maynards Beweis für den Fall b = 10 und wir nutzen hierzu auch die in seiner Arbeit verwendeten Werkzeuge. Unter Anderem benötigen wir die Hardy-Littlewoodsche Kreismethode sowie diverse Siebmethoden, um die Minor Arcs zu kontrollieren.
Schließlich sehen wir, dass wir Maynard's Aussage vor allem dann auf beliebige Basen b>= 10 und ausgeschlossene Ziffern a0 aus {0, ..., b − 1} übertragen können, wenn zwei betragsmäßig größte Eigenwerte von Matrizen, die von b und a0 parametrisiert werden, bestimmte Abschätzungen erfüllen. Dass diese Abschätzungen im Fall b>=102 erfüllt sind, beweisen wir im letzten Kapitel. Für die Fälle b = 10 und b = 11 liegt ebenfalls ein Mathematica-Code vor, der die Abschätzungen bestätigt.

This thesis addresses the reduced basis methods for parametrized quasilinear elliptic and parabolic partial differential equations with strongly monotone differential operator. It presents all of the ingredients of the reduced basis method: basis generation for reduced basis approximation, certification of the approximation error by suitable a-posteriori error control and an Offine-Online decomposition. The methodology is further applied to the magnetostatic and magnetoquasistatic approximations of Maxwell’s equations and its validity is confirmed by numerical examples.

We consider variational discretization of three different optimal control problems.
The first being a parabolic optimal control problem governed by space-time measure controls. This problem has a nice sparsity structure, which motivates our aim to achieve maximal sparsity on the discrete level. Due to the measures on the right hand side of the partial differential equation, we consider a very weak solution theory for the state equation and need an embedding into the continuous functions for the pairings to make sense. Furthermore, we employ Fenchel duality to formulate the predual problem and give results on solution theory of both the predual and the primal problem. Later on, the duality is also helpful for the derivation of algorithms, since the predual problem can be differentiated twice so that we can apply a semismooth Newton method. We then retrieve the optimal control by duality relations.
For the state discretization we use a Petrov-Galerkin method employing piecewise constant states and piecewise linear and continuous test functions in time. For the space discretization we choose piecewise linear and continuous functions. As a result the controls are composed of Dirac measures in space-time, centered at points on the discrete space-time grid. We prove that the optimal discrete states and controls converge strongly in L^q and weakly-* in Μ, respectively, to their smooth counterparts, where q ϵ (1,min{2,1+2/d}] is the spatial dimension. The variational discrete version of the state equation with the above choice of spaces yields a Crank-Nicolson time stepping scheme with half a Rannacher smoothing step.
Furthermore, we compare our approach to a full discretization of the corresponding control problem, precisely a discontinuous Galerkin method for the state discretization, where the discrete controls are piecewise constant in time and Dirac measures in space. Numerical experiments highlight the sparsity features of our discrete approach and verify the convergence results.
The second problem we analyze is a parabolic optimal control problem governed by bounded initial measure controls. Here, the cost functional consists of a tracking term corresponding to the observation of the state at final time. Instead of a regularization term for the control in the cost functional, we consider a bound on the measure norm of the initial control. As in the first problem we observe a sparsity structure, but here the control resides only in space at initial time, so we focus on the space discretization to achieve maximal sparsity of the control. Again, due to the initial measure in the partial differential equation, we rely on a very weak solution theory of the state equation.
We employ a dG(0) approximation of the state equation, i.e. we choose piecewise linear and continuous functions in space, which are piecewise constant in time for our ansatz and test space. Then, the variational discretization of the problem together with the optimality conditions induce maximal discrete sparsity of the initial control, i.e. Dirac measures in space. We present numerical experiments to illustrate our approach and investigate the sparsity structure
As third problem we choose an elliptic optimal control governed by functions of bounded variation (BV) in one space dimension. The cost functional consists of a tracking term for the state and a BV-seminorm in terms of the derivative of the control. We derive a sparsity structure for the derivative of the BV control. Additionally, we utilize the mixed formulation for the state equation.
A variational discretization approach with piecewise constant discretization of the state and piecewise linear and continuous discretization of the adjoint state yields that the derivative of the control is a sum of Dirac measures. Consequently the control is a piecewise constant function. Under a structural assumption we even get that the number of jumps of the control is finite. We prove error estimates for the variational discretization approach in combination with the mixed formulation of the state equation and confirm our findings in numerical experiments that display the convergence rate.
In summary we confirm the use of variational discretization for optimal control problems with measures that inherit a sparsity. We are able to preserve the sparsity on the discrete level without discretizing the control variable.