In this master thesis we have examined the possibility of pricing multiple American options, on an underlying asset with discrete dividends, with a finite difference method. We have found a good and stable way to price one American option by solving the BSM PDE backwards, while also calculating the Greeks of the option with automatic differentiation. The list of Greeks for an option is quite extensive since we have been using a local volatility surface. We have also tried to find a way to price several American options simultaneously by solving a forward PDE. Unfortunately, we haven't found any previous work that we could use with our local volatility surface, while still keeping down the computational time. The closest we got was to calculate the value of a compound option in a forward mode, but in order to use this to value an American option, we needed to go through an iterative process which calculated a forward or backward European PDE in every step.

In modern aerospace engineering, the physics-based computational design method is becoming more important. However, high-fidelity models require longer computational time, so the advantage of efficiency is partially lost. This problem has been overcome with the development of the approximation management framework (AMF). In the AMF, objective and constraint functions of a low-fidelity model are scaled at a design point so that the scaled functions, referred to as gsurrogate functions, h match those of a high-fidelity model. Since scaling functions and the low-fidelity model constitutes surrogate functions, evaluating the surrogate functions is faster than evaluating the high-fidelity model. Therefore, in the optimization process of the AMF, the surrogate functions are used to obtain a new design point. However, the author found that 1) the AMF is very vulnerable when the computational analysis models have numerical noise, and that 2) the AMF terminates optimization prematurely when the optimization problems have constraints. In order to solve the first problem, automatic differentiation (AD) technique is applied. If derivatives are computed with the generated derivative code, they are analytical, and the computational time is independent of the number of design variables. However, if analysis models implement iterative computations such as computational fluid dynamics (CFD), computing derivatives through the AD requires a massive memory size. The author solved this deficiency by modifying the AD approach and developing a more efficient implementation with CFD. In order to solve the second problem, the governing equation of the trust region ratio is modified so that it can accept the violation of constraints within some tolerance. By accepting violations of constraints during the optimization process, the AMF can continue optimization without terminating immaturely and eventually find the true optimum design point. With these modifications, the AMF is referred to as gRobust AMF, h and it is applied to airfoil and wing designs using Euler CFD software. The proposed AD method computes derivatives more accurately and faster than the finite differentiation method, and the Robust AMF successfully optimizes shapes of the airfoil and the wing in a much shorter time than the sequential quadratic programming with only high-fidelity models.

Orientador: Margarida Pinheiro Mello / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-18T06:57:47Z (GMT). No. of bitstreams: 1 Gower_RobertMansel_M.pdf: 908087 bytes, checksum: f8067f63c68dadafecf74e1387966331 (MD5) Previous issue date: 2011 / Resumo: Dentro do contexto de programação não linear, vários algoritmos resumem-se à aplicação do método de Netwon aos sistemas constituídos pelas condições de primeira ordem de Lagrange. Nesta classe de métodos é necessário calcular a matriz hessiana. Nosso foco é o cálculo exato, dentro da precisão da máquina, de matrizes hessianas usando diferenciação automática. Para esse fim, exploramos o cálculo da matriz hessiana sob dois pontos de vista. O primeiro é um modelo de grafo que foca nas simetrias que ocorrem no processo do cálculo da hessiana. Este ângulo propicia a intuição de como deve ser calculada a hessiana e leva ao desenvolvimento de um novo método de modo reverso para o cálculo de matrizes hessianas denominado edge pushing. O segundo ponto de vista é uma representação puramente algébrica que reduz o cálculo da hessiana à avaliação de uma expressão. Esta expressão pode ser usada para demonstrar algoritmos já existentes e projetar novos. Para ilustrar, deduzimos dois novos algoritmos, edge pushing e um novo algoritmo de modo direto, e uma série de outros métodos conhecidos [1], [20, p.157] e [9]. Apresentamos estudos teóricos e empíricos sobre o algoritmo edge pushing. Analisamos sua complexidade temporal e de uso de memória. Implementamos o algoritmo como um driver do pacote ADOL-C [19] e efetuamos testes computacionais, comparando sua performance com à de dois outros drivers em dezesseis problemas da coleção CUTE [5]. Os resultados indicam que o novo algoritmo é muito promissor. Pequenas modificações em edge pushing produzem um novo algoritmo, edge pushing sp, para o cálculo da esparsidade de matrizes hessianas, um passo necessário de uma classe de métodos que calculam a matriz hessiana usando colorações de grafos, [14, 19, 30]. Estudos de complexidade e testes numéricos são realizados comparando o novo método contra um outro recentemente desenvolvido [30] e os testes favorecem o novo algoritmo edge pushing sp. No capítulo final, motivado pela disponibilidade crescente de computadores com multiprocesadores, investigamos o processamento em paralelo do cálculo de matrizes hessianas. Examinamos o cálculo em paralelo de matrizes hessianas de funções parcialmente separáveis. Apresentamos uma abordagem desenvolvida para o cômputo em paralelo que pode ser usando em conjunto com qualquer método de cálculo de hessiana e outra estratégia específica para métodos de modo reverso. Testes são executados em um computador com memória compartilhada usando a interface de programação de aplicativo OpenMP / Abstract: In the context of nonlinear programming, many algorithms boil down to the application of Newton's method to the system constituted by the first order Lagrangian conditions. The calculation of Hessian matrices is necessary in this class of solvers. Our focus is on the exact calculation, within machine precision, of Hessian matrices through automatic differentiation. To this end, we detail the calculations of the Hessian matrix under two points of view. The first is an intuitive graph model that focuses on what symmetries occur throughout the Hessian calculation. This provides insight on how one should calculate the Hessian matrix, and we use this enlightened perspective to deduce a new reverse Hessian algorithm called edge pushing. The second viewpoint is a purely algebraic representation of the Hessian calculation via a closed formula. This formula can be used to demonstrate existing algorithms and design new ones. In order to illustrate, we deduce two new algorithms, edge pushing and a new forward algorithm, and a series of other known Hessian methods [1], [20, p.157] and [9]. We present theoretical and empirical studies of the edge pushing algorithm, establishing memory and temporal bounds, and comparing the performance of its computer implementation against that of two algorithms available as drivers of the software ADOL-C [14, 19, 30] on sixteen functions from the CUTE collection [5]. Test results indicate that the new algorithm is very promising. As a by-product of the edge pushing algorithm, we obtain an efficient algorithm, edge pushing sp, for automatically obtaining the sparsity pattern of Hessian matrices, a necessary step in a class of methods used for computing Hessian matrices via graph coloring, [14, 19, 30]. Complexity bounds are developed and numerical tests are carried out comparing the new sparsity detection algorithm against a recently developed method [30] and the results favor the new edge pushing sp algorithm. In the final chapter, motivated by the increasing commercial availability of multiprocessors, we investigate the implementation of parallel versions of the edge pushing algorithm. We address the concurrent calculation of Hessian matrices of partially separable functions. This includes a general approach to be used in conjunction with any Hessian software, and a strategy specific to reverse Hessian methods. Tests are carried out on a shared memory computer using the OpenMP paradigm / Mestrado / Analise Numerica / Mestre em Matemática Aplicada

In this dissertation we investigate methods of solving various optimization problems with PDE constraints, i.e. optimization problems that have a system of partial differential equations in the set of constraints, and develop frameworks for a number of practically inspired problems that were not considered in the literature before. Such problems arise in areas like fluid mechanics, chemical engineering, finance, and other areas where a physical system needs to be optimized. In most of the literature sources on PDE-constrained optimization only relatively simple systems of PDEs are considered, they are either linear, or the size of the system is small. On the contrary, in our case, we search for solution methods to problems constrained by large (8 to 10 equations) and non-linear systems of PDEs. More specifically, in the first part of the dissertation we consider a multiphysics phenomenon where electromagnetic and mechanical fields interact within an electrically conductive body, and develop the optimization framework to find an efficient way to control one field through another. We also apply the developed PDE-constrained optimization framework to a financial options portfolio optimization problem, and more specifically consider the case that to the best of our knowledge is not covered in the literature.

No description available.

<p>Current indirect optimal control problem (IOCP) solvers, like beluga or PINs, use symbolic math to derive the necessary conditions to solve the IOCP. This limits the capability of IOCP solvers by only admitting symbolically representable functions. The purpose of this thesis is to present a framework that extends those solvers to derive the necessary conditions of an IOCP with fully numeric methods. With fully numeric methods, additional types of functions, including conditional logic functions and look-up tables can now be easily used in the IOCP solver.</p> <p><br></p> <p>This aim was achieved by implementing algorithmic differentiation (AD) as a method to derive the IOCP necessary conditions into a new solver called Giuseppe. The Brachistochrone problem was derived analytically and compared Giuseppe to validate the automatic derivation of necessary conditions. Two additional problems are compared and extended using this new solver. The first problem, the maximum cross-range problem, demonstrates a trajectory can be optimized indirectly while utilizing a conditional density function that switches as a function of height according to the 1976 U.S. atmosphere model. The second problem, the minimum time to climb problem, demonstrates a trajectory can be optimized indirectly while utilizing 6 interpolated look up tables for lift, drag, thrust, and atmospheric conditions. The AD method yields the exact same precision as the symbolic methods, rather than introducing numeric error as finite difference derivatives would with the benefit of admitting conditional switching functions and look-up tables. </p>

Ordinary differential equations (ODEs) play an important role in mathematics. Although intrinsically, the setting for describing ODEs is the continuous framework, where differential operators are considered as maps from one function space to another, common numerical algorithms for ODEs discretise problems early on in the solution process. This thesis is about continuous analogues of such discrete algorithms for the numerical solution of ODEs. This thesis shows how Newton's method for finite dimensional system can be generalised to function spaces, where it is known as Newton-Kantorovich iteration. It presents affine invariant damping strategies for increasing the chance of convergence for the Newton-Kantorovich iteration. The derivatives required in this continuous setting are Fr&eacute;chet derivatives, the continuous analogue of Jacobian matrices. In this work, we present how automatic differentiation techniques can be applied to compute Fr&eacute;chet derivatives. We introduce chebop, a Matlab solver for nonlinear boundary-value problems, which combines damped Newton iteration in function space and automatic Fr&eacute;chet differentiation. By proving that affine operators have constant Fr&eacute;chet derivatives, it is demonstrated how automatic linearity detection of computed quantities can be implemented. This is valuable for black-box solvers, which can use the information to determine whether an iteration scheme has to be employed for solving a problem. Like nonlinear systems of equations, nonlinear boundary-value problems can have multiple solutions. This thesis present two techniques for obtaining multiple solutions of operator equations: deflation and path-following. An algorithm combining the two techniques is proposed.

The technique of automatic differentiation provides directional derivatives and discrete adjoints with working accuracy. A complete complexity analysis of the basic modes of automatic differentiation is available. Therefore, the research activities are focused now on different aspects of the derivative calculation, as for example the efficient implementation by exploitation of structural information, studies of the theoretical properties of the provided derivatives in the context of optimization problems, and the development and analysis of new mathematical algorithms based on discrete adjoint information. According to this motivation, this habilitation presents an analysis of different checkpointing strategies to reduce the memory requirement of the discrete adjoint computation. Additionally, a new algorithm for computing sparse Hessian matrices is presented including a complexity analysis and a report on practical experiments. Hence, the first two contributions of this thesis are dedicated to an efficient computation of discrete adjoints. The analysis of discrete adjoints with respect to their theoretical properties is another important research topic. The third and fourth contribution of this thesis focus on the relation of discrete adjoint information and continuous adjoint information for optimal control problems. Here, differences resulting from different discretization strategies as well as convergence properties of the discrete adjoints are analyzed comprehensively. In the fifth contribution, checkpointing approaches that are successfully applied for the computation of discrete adjoints, are adapted such that they can be used also for the computation of continuous adjoints. Additionally, the fifth contributions presents a new proof of optimality for the binomial checkpointing that is based on new theoretical results. Discrete adjoint information can be applied for example for the approximation of dense Jacobian matrices. The development and analysis of new mathematical algorithms based on these approximate Jacobians is the topic of the sixth contribution. Is was possible to show global convergence to first-order critical points for a whole class of trust-region methods. Here, the usage of inexact Jacobian matrices allows a considerable reduction of the computational complexity.

Bei der Berechnung von Adjungierten, zum Debuggen und für ähnliche Anwendungen kann man die Umkehr der entsprechenden Programmauswertung verwenden. Der einfachste Ansatz, nämlich das Mitschreiben einer kompletten Mitschrift der Vorwärtsrechnung, welche anschließend rückwärts gelesen wird, verursacht einen enormen Speicherplatzbedarf. Als Alternative dazu kann man die Mitschrift auch stückweise erzeugen, indem die Programmauswertung von passend gewählten Checkpoints wiederholt gestartet wird. Das Ziel der Arbeit ist die Minimierung des von der Programmumkehr verursachten Zeit- und Speicherplatzbedarfs. Dieser wird gemessen in Auswertungswiederholungen bzw. verwendeten Checkpoints. Optimale Umkehrschemata werden für Ein- und Mehr-Schritt-Verfahren entwickelt, welche zum Beispiel bei der Diskretisierung einer gewöhnlichen Differentialgleichung Verwendung finden. Desweiteren erfolgte die Entwicklung von parallelen Umkehrschemata, d. h. mehrere Prozessoren werden für die Umkehrung der Programmauswertung eingesetzt. Diese zusätzlichen Prozessoren dienen dazu, die wiederholten Berechnungen des Programms zu parallelisieren, so daß ein Prozessor die Rückwartsrechnung ohne Unterbrechung durchführen kann. Sowohl für die seriellen als auch für die parallelen Umkehrschemata wurde gezeigt, daß die Länge der umzukehrenden Programmauswertung exponentiell in Abhängigkeit von der Zahl der verwendeten Checkpoints und der Zahl der wiederholten Auswertungen bzw. verwendeten Prozessoren wächst. / For adjoint calculations, parameter estimation, and similar purposes one may need to reverse the execution of a computer program. The simplest option is to record a complete execution log and then to read it backwards. This requires massive amounts of storage. Instead one may generate the execution log piecewise by restarting the ``forward'' calculation repeatedly from suitably placed checkpoints. The basic structure of the resulting reversal schedules is illustrated. Various strategies are analysed with respect to the resulting temporal and spatial complexity on serial and parallel machines. For serial machines known optimal compromises between operations count and memory requirement are explained, and they are extended to more general situations. For program execution reversal on multi-processors the new challenges and demands on an optimal reversal schedule are described. We present parallel reversal schedules that are provably optimal with regards to the number of concurrent processes and the total amount of memory required.

Neste trabalho buscou-se consolidar aspectos referentes à otimização de problemas envolvidos na mecânica dos meios contínuos, envolvendo diferentes áreas do conhecimento, tais como: otimização matemática, diferenciação automática, análise estrutural, análise aerodinâmica, parametrização de curvas, superfícies e sólidos do tipo B-spline racionais não-uniformes (NURBS, acrônimo do inglês), análise IsoGeométrica (IGA, acrônimo do inglês) e análise por Elementos Finitos (FEA, acrônimo do inglês). Como objetivo final busca-se otimizar formas de cascas estruturais e formas de corpos aerodinâmicos imersos em escoamentos compressíveis. No que concerne à análise estrutural, esta é realizada via análise IsoGeométrica utilizando elementos sólidos para modelar cascas. Uma cinemática co-rotacional abrangente e precisa baseada na exata decomposição polar é desenvolvida, para lidar com problemas estáticos e dinâmicos altamente não lineares. Na análise estática foram implementados o método de Newton-Raphson e controle de deslocamentos generalizado, para problemas dinâmicos foram implementados o método -generalizado (G) e o método energia momento generalizado (GEMM+). A análise aerodinâmica é realizada via análise por Elementos Finitos para modelar escoamentos compressíveis viscosos e não viscosos em regimes transônicos e supersônicos. Um esquema característico baseado na separação da equação de momento (CBS, acrônimo do inglês) é utilizado para obter uma adequada integração temporal. No que concerne à otimização matemática, é utilizado um método baseado em gradientes, conhecido por programação quadrática sequencial (SQP, acrônimo do inglês), onde a avaliação as derivadas de Fréchet são levadas a cabo via diferenciação automática (AD, acrônimo do inglês). No que concerne aos resultados finais é realizada a otimização estrutural de forma de cascas modeladas como sólidos são apresentados, evidenciando um desempenho ótimo com respeito à energia de deformação interna. Os resultados de otimização aerodinâmica bidimensionais apresentam perfis aerodinâmicos ótimos com respeito à relação arrasto/sustentação para uma ampla gama de número de Mach, enquanto um resultado tridimensional é apresentado evidenciando a robustez e eficiência da implementação proposta. Pretendese estabelecer com este trabalho as bases para pesquisas em problemas de otimização aeroelástica. / Consolidation of the link among optimization problems in continuum mechanics, involving different fields, such as mathematical optimization, automatic differentiation, structural analysis, aerodynamic analysis, curves, surfaces and solids parameterization using Non Uniform Rational B-spline (NURBS), IsoGeometric Analysis (IGA), Finite Element Analysis (FEA) is looked for. Structural shape optimization of shell structures and aerodynamic shape optimization of immersed bodies in compressible flows are the main goals of this work. Concerning structural analysis, the so-called IsoGeometric analysis is employed. An accurate and comprehensive corotational kinematic based on the exact polar decomposition is developed in order to study highly nonlinear static and dynamic problems. Static analysis is carried out with Newton-Raphson and Generalized Displacement Control Method, while dynamic analysis is carried out with Generalized- (G) and Generalized Energy-Momentum Method (GEMM+). Aerodynamic analysis is carried out via Finite Element Analysis (FEA) in order to solve compressible flows in transonic and supersonic regimes. A Characteristic Based Split (CBS) method is employed to obtain an accurate time integration, which is based on the splitting of the momentum equation. Concerning mathematical optimization, the so-called Sequential Quadratic Programming (SQP) is employed, which is a gradient-based method, where the Fréchet derivatives are evaluated using Automatic Differentiation (AD). Final results consisting in structural optimization shown an optimal behaviour with respect to internal strain energy. While, results concerning aerodynamic bi-dimensional shape optimization exhibit a optimal behaviour with respect drag/lift ratio, for a large range of Mach number, and a simple result for tri-dimensional case is presented in order to show the efficiency and robustness of the implementation. Bases for future research in aeroelastic optimization problems are established in this work.