Search

The master thesis is focused on how a local volatility surfaces can be extracted by optimization with respectto smoothness and price error. The pricing is based on utility based pricing, and developed to be set in arisk neutral pricing setting. The pricing is done in a discrete multinomial recombining tree, where the timeand price increments optionally can be equidistant. An interpolation algorithm is used if the option that shallbe priced is not matched in the tree discretization. Power utility functions are utilized, where the log-utilitypreference is especially studied, which coincides with the (Kelly) portfolio that systematically outperforms anyother portfolio. A fine resolution of the discretization is generally a property that is sought after, thus a seriesof derivations for the implementation are done to restrict the computational encumbrance and thus allow finer discretization. The thesis is mainly focused on the derivation of the method rather than finding optimal parameters thatgenerate the local volatility surfaces. The method has shown that smooth surfaces can be extracted, whichconsider market prices. However, due to lacking available interest and dividend data, the pricing error increasessymmetrically for longer option maturities. However, the method shows exponential convergence and robustnessto different initial (flat) volatilities for the optimization initiation. Given an optimal smooth local volatility surface, an arbitrary payoff function can then be used to price thecorresponding option, which could be path-dependent, such as barrier options. However, only vanilla optionswill be considered in this thesis. Finally, we find that the developed

Parallele Umkehr-Ablaufpläne (Parallel reversal schedules) beschreiben, wie die Zustände eines evolutionären Systems, etwa einer atmosphärischen oder ozeanographischen Simulation, in umgekehrter Reihenfolge berechnet werden können, ohne dass alle Zustände im Speicher gehalten werden müssen. Auf einem Mehrprozessorsystem ist das ohne Anstieg der benötigten Rechenzeit möglich, indem Zwischenergebnisse zwar mehrfach berechnet werden, aber gleichzeitig auf mehreren Prozessoren. Diese Ablaufpläne werden nicht nur verwendet, um Simulationen rückwärts abzuspielen, sondern auch in der algorithmischen Differenzierung, die wiederum in der nichtlinearen Optimierung sowie beim Lösen von partiellen Differentialgleichungen eingesetzt wird. Die bisherige Forschung ermittelte optimale Pläne für den Fall, dass folgende zentrale Annahme erfüllt ist: Können k Zustände gleichzeitig im Speicher gehalten werden, so sind stets etwa k/2 Prozessoren verfügbar, die die Berechnung von k/2 Zuständen fortsetzen. Die übrigen k/2 Zustände werden in reinen Speicherpunkten (Checkpoints) vorgehalten. In dieser Diplomarbeit wird die zentrale Annahme gelockert und so die Forschung fortgesetzt. Es ist nun möglich, dass deutlich weniger als k/2 Prozessoren verfügbar sind, oder gleichbedeutend, dass viel mehr Speicherpunkte genutzt werden können. Für diese neue Aufgabenstellung wird eine symbolische Herangehensweise an parallele Umkehr-Ablaufpläne vorgestellt. Es wird eine umfassende Algebra entwickelt, die einen direkten Zugang zu den Profilen der Pläne bietet und so deren Analyse erleichtert. Diese Algebra ist sehr generisch und könnte weitere Anwendungen haben. Es werden neue Pläne entwickelt, die in Situationen anwendbar sind, in denen die bisher bekannten Pläne ungeeignet waren. In einigen Fällen sind sie optimal, für alle übrigen Fälle werden suboptimale Pläne vorgestellt, die ebenfalls eine deutliche Verbesserung zu den bisherigen Plänen darstellen., Parallel reversal schedules describe how to calculate the states of an evolutionary system, such as atmospheric and oceanographic simulations, in reverse order without having to keep all states in memory. This is possible without any increase in computation time, by recalculating intermediate results using multiple processors on a parallel computer system. These schedules are not only applied physical simulations that need to run in reverse, but also in algorithmic differentiation, which in turn is used, among others, in nonlinear optimization and to solve partial differential equations. Earlier research led to optimal schedules under the central assumption that if k states can be kept in memory, there are enough processors to run computations on roughly half of them in parallel, while the other half can only be used for holding checkpoints. This diploma thesis is an attempt to continue the research by relaxing the central assumption, such that memory for a large number of plain checkpoints can be used with a comparatively small number of processors. To cope with this challenge, a symbolic approach to reversal schedules is proposed, and a comprehensive algebra is developed to analyze schedules via their profiles. This algebra is very generic and could have applications outside parallel reversal schedules. Using that instrument, new optimal schedules are developed, to be applied in situations where the earlier schedules are not applicable. Moreover, suboptimal schedules are provided where optimal schedules could not be found in a systematic way.

Parallele Umkehr-Ablaufpläne (Parallel reversal schedules) beschreiben, wie die Zustände eines evolutionären Systems, etwa einer atmosphärischen oder ozeanographischen Simulation, in umgekehrter Reihenfolge berechnet werden können, ohne dass alle Zustände im Speicher gehalten werden müssen. Auf einem Mehrprozessorsystem ist das ohne Anstieg der benötigten Rechenzeit möglich, indem Zwischenergebnisse zwar mehrfach berechnet werden, aber gleichzeitig auf mehreren Prozessoren. Diese Ablaufpläne werden nicht nur verwendet, um Simulationen rückwärts abzuspielen, sondern auch in der algorithmischen Differenzierung, die wiederum in der nichtlinearen Optimierung sowie beim Lösen von partiellen Differentialgleichungen eingesetzt wird. Die bisherige Forschung ermittelte optimale Pläne für den Fall, dass folgende zentrale Annahme erfüllt ist: Können k Zustände gleichzeitig im Speicher gehalten werden, so sind stets etwa k/2 Prozessoren verfügbar, die die Berechnung von k/2 Zuständen fortsetzen. Die übrigen k/2 Zustände werden in reinen Speicherpunkten (Checkpoints) vorgehalten. In dieser Diplomarbeit wird die zentrale Annahme gelockert und so die Forschung fortgesetzt. Es ist nun möglich, dass deutlich weniger als k/2 Prozessoren verfügbar sind, oder gleichbedeutend, dass viel mehr Speicherpunkte genutzt werden können. Für diese neue Aufgabenstellung wird eine symbolische Herangehensweise an parallele Umkehr-Ablaufpläne vorgestellt. Es wird eine umfassende Algebra entwickelt, die einen direkten Zugang zu den Profilen der Pläne bietet und so deren Analyse erleichtert. Diese Algebra ist sehr generisch und könnte weitere Anwendungen haben. Es werden neue Pläne entwickelt, die in Situationen anwendbar sind, in denen die bisher bekannten Pläne ungeeignet waren. In einigen Fällen sind sie optimal, für alle übrigen Fälle werden suboptimale Pläne vorgestellt, die ebenfalls eine deutliche Verbesserung zu den bisherigen Plänen darstellen., Parallel reversal schedules describe how to calculate the states of an evolutionary system, such as atmospheric and oceanographic simulations, in reverse order without having to keep all states in memory. This is possible without any increase in computation time, by recalculating intermediate results using multiple processors on a parallel computer system. These schedules are not only applied physical simulations that need to run in reverse, but also in algorithmic differentiation, which in turn is used, among others, in nonlinear optimization and to solve partial differential equations. Earlier research led to optimal schedules under the central assumption that if k states can be kept in memory, there are enough processors to run computations on roughly half of them in parallel, while the other half can only be used for holding checkpoints. This diploma thesis is an attempt to continue the research by relaxing the central assumption, such that memory for a large number of plain checkpoints can be used with a comparatively small number of processors. To cope with this challenge, a symbolic approach to reversal schedules is proposed, and a comprehensive algebra is developed to analyze schedules via their profiles. This algebra is very generic and could have applications outside parallel reversal schedules. Using that instrument, new optimal schedules are developed, to be applied in situations where the earlier schedules are not applicable. Moreover, suboptimal schedules are provided where optimal schedules could not be found in a systematic way.

The master thesis is focused on how a local volatility surfaces can be extracted by optimization with respectto smoothness and price error. The pricing is based on utility based pricing, and developed to be set in arisk neutral pricing setting. The pricing is done in a discrete multinomial recombining tree, where the timeand price increments optionally can be equidistant. An interpolation algorithm is used if the option that shallbe priced is not matched in the tree discretization. Power utility functions are utilized, where the log-utilitypreference is especially studied, which coincides with the (Kelly) portfolio that systematically outperforms anyother portfolio. A fine resolution of the discretization is generally a property that is sought after, thus a seriesof derivations for the implementation are done to restrict the computational encumbrance and thus allow finer discretization. The thesis is mainly focused on the derivation of the method rather than finding optimal parameters thatgenerate the local volatility surfaces. The method has shown that smooth surfaces can be extracted, whichconsider market prices. However, due to lacking available interest and dividend data, the pricing error increasessymmetrically for longer option maturities. However, the method shows exponential convergence and robustnessto different initial (flat) volatilities for the optimization initiation. Given an optimal smooth local volatility surface, an arbitrary payoff function can then be used to price thecorresponding option, which could be path-dependent, such as barrier options. However, only vanilla optionswill be considered in this thesis. Finally, we find that the developed

This contribution concerns the development of generic methods and tools for robust optimal control of high-pressure liquid chromatographic separation processes. The proposed methodology exploits a deterministic robust formulation, that employs a linearization of the uncertainty set, based on Lyapunov differential equations to generate optimal elution trajectories in the presence of uncertainty. Computational tractability is obtained by casting the robust counterpart problem in the framework of bilevel optimal control where the upper level concerns forward simulation of the Lyapunov differential equation, and the nominal open-loop optimal control problem augmented with the robustified target component purity inequality constraint margin is considered in the lower level. The lower-level open-loop optimal control problem, constrained by spatially discretized partial differential equations, is transcribed into a finite dimensional nonlinear program using direct collocation, which is then solved by a primal-dual interior point method. The advantages of the robustification strategy are highlighted through the solution of a challenging ternary complex mixture separation problem for a hydrophobic interaction chromatography system. The study shows that penalizing the changes in the zero-order hold control gives optimal solutions with low sensitivity to uncertainty. A key result is that the robustified general elution trajectories outperformed the conventional linear trajectories both in terms of recovery yield and robustness.

In dieser Arbeit werden Techniken beschrieben, die es erlauben (höhere) Ableitungen und Taylorapproximationen solcher Computerprogramme effizient zu berechnen. Auch inbesondere dann, wenn die Programme Algorithmen der numerischen linearen Algebra (NLA) enthalten. Im Gegensatz zur traditionellen algorithmischen Differentiation (AD), bei der die zugrunde liegenden Algorithmen um zusätzliche Befehlere erweitert werden, sind in dieser Arbeit die Zerlegungen durch definierende Gleichungen charakterisiert. Basierend auf den definierenden Gleichungen werden Strukturausnutzende Algorithmen hergeleitet. Genauer, neuartige Algorithmen für die Propagation von Taylorpolynomen durch die QR, Cholesky und reell-symmetrischen Eigenwertzerlegung werden präsentiert. Desweiteren werden Algorithmen für den Rückwärtsmodus der AD hergeleitet, welche im Wesentlichen nur die Faktoren der Zerlegungen benötigen. Im Vergleich zum traditionellen Ansatz, bei dem alle Zwischenergebnisse gespeichert werden, ist dies eine Reduktion von O(N^3) zu O(N^2) für Algorithmen mit O(N^3) Komplexität. N ist hier die Größe der Matrix. Zusätzlich kann bestehende, hoch-optimierte Software verwendet werden. Ein Laufzeitvergleich zeigt, dass dies im Vergleich zum traditionellen Ansatz zu einer Beschleunigung in der Größenordnung 100 führen kann. Da die NLA Funktionen als Black Box betrachtet werden, ist desweiteren auch der Berechnungsgraph um Größenordnungen kleiner. Dies bedeutet, dass Software, welche Operator Overloading benutzt, weniger Overhead hervorruft und auch weniger Speicher benötigt., This thesis provides a framework for the evaluation of first and higher-order derivatives and Taylor series expansions through large computer programs that contain numerical linear algebra (NLA) functions. It is a generalization of traditional algorithmic differentiation (AD) techniques in that NLA functions are regarded as black boxes where the inputs and outputs are related by defining equations. Based on the defining equations, structure-exploiting algorithms are derived. More precisely, novel algorithms for the propagation of Taylor polynomials through the QR, Cholesky,- and real-symmetric eigenvalue decomposition are shown. Recurrences for the reverse mode of AD, which require essentially only the returned factors of the decomposition, are also derived. Compared to the traditional approach where all intermediates of an algorithm are stored, this is a reduction from O(N^3) to O(N^2) for algorithms with O( N^3) complexity. N denotes the matrix size. The derived algorithms make it possible to use existing high-performance implementations. A runtime comparison shows that the treatment of NLA functions as atomic can be more than one order of magnitude faster than an automatic differentiation of the underlying algorithm. Furthermore, the computational graph is orders of magnitudes smaller. This reduces the additional memory requirements, as well as the overhead, of operator overloading techniques to a fraction.

In dieser Arbeit werden Techniken beschrieben, die es erlauben (höhere) Ableitungen und Taylorapproximationen solcher Computerprogramme effizient zu berechnen. Auch inbesondere dann, wenn die Programme Algorithmen der numerischen linearen Algebra (NLA) enthalten. Im Gegensatz zur traditionellen algorithmischen Differentiation (AD), bei der die zugrunde liegenden Algorithmen um zusätzliche Befehlere erweitert werden, sind in dieser Arbeit die Zerlegungen durch definierende Gleichungen charakterisiert. Basierend auf den definierenden Gleichungen werden Strukturausnutzende Algorithmen hergeleitet. Genauer, neuartige Algorithmen für die Propagation von Taylorpolynomen durch die QR, Cholesky und reell-symmetrischen Eigenwertzerlegung werden präsentiert. Desweiteren werden Algorithmen für den Rückwärtsmodus der AD hergeleitet, welche im Wesentlichen nur die Faktoren der Zerlegungen benötigen. Im Vergleich zum traditionellen Ansatz, bei dem alle Zwischenergebnisse gespeichert werden, ist dies eine Reduktion von O(N^3) zu O(N^2) für Algorithmen mit O(N^3) Komplexität. N ist hier die Größe der Matrix. Zusätzlich kann bestehende, hoch-optimierte Software verwendet werden. Ein Laufzeitvergleich zeigt, dass dies im Vergleich zum traditionellen Ansatz zu einer Beschleunigung in der Größenordnung 100 führen kann. Da die NLA Funktionen als Black Box betrachtet werden, ist desweiteren auch der Berechnungsgraph um Größenordnungen kleiner. Dies bedeutet, dass Software, welche Operator Overloading benutzt, weniger Overhead hervorruft und auch weniger Speicher benötigt., This thesis provides a framework for the evaluation of first and higher-order derivatives and Taylor series expansions through large computer programs that contain numerical linear algebra (NLA) functions. It is a generalization of traditional algorithmic differentiation (AD) techniques in that NLA functions are regarded as black boxes where the inputs and outputs are related by defining equations. Based on the defining equations, structure-exploiting algorithms are derived. More precisely, novel algorithms for the propagation of Taylor polynomials through the QR, Cholesky,- and real-symmetric eigenvalue decomposition are shown. Recurrences for the reverse mode of AD, which require essentially only the returned factors of the decomposition, are also derived. Compared to the traditional approach where all intermediates of an algorithm are stored, this is a reduction from O(N^3) to O(N^2) for algorithms with O( N^3) complexity. N denotes the matrix size. The derived algorithms make it possible to use existing high-performance implementations. A runtime comparison shows that the treatment of NLA functions as atomic can be more than one order of magnitude faster than an automatic differentiation of the underlying algorithm. Furthermore, the computational graph is orders of magnitudes smaller. This reduces the additional memory requirements, as well as the overhead, of operator overloading techniques to a fraction.

We present an approach for determining the tractability index using truncated polynomial arithmetic. In particular, computing the index this way generates a sequence of matrices that contains itself derivatives. We realize the time differentiations using Algorithmic Differentiation techniques, specially by using the standard ADOL-C package with which calculating the derivatives becomes a simple shift and scaling of coefficients. We present the theory supporting the procedure we propose, as well as the implementation issues behind it to provide a convenient interface to the standard ADOL-C functionality. We give also examples of academic and practical problems and report several experimental results we have obtained with them.

We present an approach for determining the tractability index using truncated polynomial arithmetic. In particular, computing the index this way generates a sequence of matrices that contains itself derivatives. We realize the time differentiations using Algorithmic Differentiation techniques, specially by using the standard ADOL-C package with which calculating the derivatives becomes a simple shift and scaling of coefficients. We present the theory supporting the procedure we propose, as well as the implementation issues behind it to provide a convenient interface to the standard ADOL-C functionality. We give also examples of academic and practical problems and report several experimental results we have obtained with them.

Für den Einsatz von ableitungsbasierten Optimierungsverfahren für die Verbesserung von Zielgrößen industrieller Produkte, wie z.B. dem Wirkungsgrad einer Turbine, werden exakte Ableitungen benötigt, um die letzten Prozent an möglicher Effizienz-steigerung zu erhalten. Dafür ist es notwendig, dass die Ableitungen immer konsistent zu den Lösungsverfahren in der eingesetzten Lösersoftware sind. Problematisch ist dabei die fortlaufende Weiterentwicklung an der Lösersoftware, die meist dazu führt, dass approximative Ableitungsverfahren eingesetzt werden oder die Ableitungsberechnung in der Software nicht erneuert wird und somit veraltet und inkonsistent ist. In dieser Arbeit wird ein universeller Ansatz vorgeschlagen, der zum einen die gesamte Software mittels Algorithmischen Differenzierens (AD) ableitet und zum anderem eine korrekte und konsistente Ableitung nach jeder Änderung sicherstellt. Um die Korrektheit und Konsistenz zu garantieren, wird die Technik des Variable Tagging entwickelt. Diese überprüft zur Laufzeit ob alle Abhängigkeiten von den eingesetzten Ableitungsmethoden korrekt berücksichtigt werden. Für die generelle Überprüfung, ob eine Ableitungsmethode korrekt implementiert ist, wird ein Theorem für die Vergleichbarkeit von AD Ableitungen entwickelt. Aus diesem Theorem ergeben sich Techniken, wie eine Implementierung getestet werden kann. Durch Analyse von vorliegenden industriellen Fällen wird die praktische Anwendbarkeit der entwickelten Techniken erfolgreich bestätigt. Die so erzeugten Ableitungen sind damit bereits konsistent und korrekt, jedoch kann die Effizienz des Verfahrens noch gesteigert werden. Dazu werden neue Ablei-tungsalgorithmen entwickelt. Eine konsistente Herleitung mit einem Fix-Punkt-Iterator beinhaltet alle dem Stand der Technik entsprechenden Algorithmen und ergibt zwei neue Algorithmen, die alle implementationstechnischen Details mitberücksichtigen und damit die Konsistenz der Ableitungsergebnisse nicht verletzen. Des Weiteren werd, If gradient based derivative algorithms are used to improve industrial products by reducing their target functions, the derivatives need to be exact. The last percent of possible improvement, like the efficiency of a turbine, can only be gained if the derivatives are consistent with the solution process that is used in the simulation software. It is problematic that the development of the simulation software is an ongoing process which leads to the use of approximated derivatives. If a derivative computation is implemented manually, it will be inconsistent after some time if it is not updated. This thesis presents a generalized approach which differentiates the whole simulation software with Algorithmic Differentiation (AD), and guarantees a correct and consistent derivative computation after each change to the software. For this purpose, the variable tagging technique is developed. The technique checks at run-time if all dependencies, which are used by the derivative algorithms, are correct. Since it is also necessary to check the correctness of the implementation, a theorem is developed which describes how AD derivatives can be compared. This theorem is used to develop further methods that can detect and correct errors. All methods are designed such that they can be applied in real world applications and are used within industrial configurations. The process described above yields consistent and correct derivatives but the efficiency can still be improved. This is done by deriving new derivative algorithms. A fixed-point iterator approach, with a consistent derivation, yields all state of the art algorithms and produces two new algorithms. These two new algorithms include all implementation details and therefore they produce consistent derivative results. For detecting hot spots in the application, the state of the art techniques are presented and extended. The data management is changed such that the performance of the software is affected only marginally when qu