Optimization methods in economics and finance: exploring Hotelling’s model and parallel processing in HMMs

June 2, 2025

Esta tese está dividida em duas partes com dois tópicos diferentes: A linha Hotelling e Hidden Markov Models. Para a linha Hotelling abordamos dois problemas. O primeiro é um verdadeiro problema de opções, para uma empresa monopolista que pretenda introduzir um novo produto no mercado, partindo do princípio de que já o tem. A dinâmica subjacente é a linha Hotelling e resolvemos o problema de paragem ideal resultante. O segundo problema está relacionado com a procura do equilíbrio no caso de um duopólio. Aqui relaxamos a suposição de que o consumidor sempre compra um produto, resultando em um problema significativamente diferente. Encontramos múltiplos equilíbrios para alguns parâmetros e também casos em que é ideal que as empresas estejam mais próximas do centro do que dos extremos, o que contradiz o princípio da diferenciação máxima. Para os Modelos Markov Ocultos abordamos a paralelização dos seus algoritmos habituais. Para o problema de inferência, o algoritmo de Baum-Welch é a abordagem estabelecida, mas este algoritmo não pode tirar proveito da computação paralela devido à sua natureza recursiva. Para superar isso, modificamos a iteração de ponto fixo com variáveis fictícias, o que resulta em um algoritmo que se comporta muito próximo ao Baum-Welch, mas pode ser paralelizado. Encontramos acelerações de mais de 200 vezes em alguns casos, economizando uma quantidade significativa de tempo. Outro dos problemas básicos dos HMM é a descodificação dos dados. O algoritmo Viterbi é a abordagem usual, mas enfrenta os mesmos desafios que o Baum-Welch. Para permitir a paralelização, desenvolvemos uma forma de calcular as quantidades do algoritmo Viterbi sem ter que recorrer à recursão completa, permitindo a paralelização. Usando a computação paralela, vemos uma aceleração significativa. This thesis is divided into two parts with two different topics: The Hotelling line and Hidden Markov Models. For the Hotelling line we address two problems. The first is a real options problem, for a monopoly firm wanting to introduce a new product in the market, assuming it already has one. The underlying dynamics are the Hotelling line and we solve the resulting optimal stopping problem. The second problem is related to finding the equilibria in the case of a duopoly. Here we relax the assumption that the consumer always buys a product, resulting in a significantly different problem. We find multiple equilibria for some parameters and also cases where it is optimal for firms to be closer to the centre than the extremes, which contradicts the principle of maximum differentiation. For Hidden Markov Models we approach the parallelization of its usual algorithms. For the inference problem, the Baum-Welch algorithm is the established approach, but this algorithm can’t take advantage of parallel computation due to its recursive nature. To overcome this, we modify the fixed-point iteration with dummy variables, which results in an algorithm that behaves very closely to the Baum-Welch but can be parallelized. We find speed-ups of over 200 times in some cases, saving a significant amount of time. Another of the basic problems of HMM’s is the decoding of the data. The Viterbi algorithm is the usual approach, but it faces the same challenges as the Baum-Welch. To allow parallelization, we develop a way to compute the quantities of the Viterbi algorithm without having to resort to the full recursion, allowing parallelization. Using parallel computing, we see a significant speed-up.

Authors in the community:

• 

  D

  Diogo Alexandre Pereira

  ist1101163

  Affiliations and sources

  IST > CEMAT

  Centro de Matemática Computacional e Estocástica

Supervisors of this institution:

• 

  C

  Cláudia Rita Ribeiro Coelho Nunes Philippart

  ist12953

101823886

Doutoramento em Matemática

mathematics - Mathematics

Keywords

• Hotelling line
• Real Options
• Duopoly
• Hidden Markov Models
• Parallel computation
• Linha de Hotelling
• Opções Reais
• Duopólio
• Modelos de Markov Ocultos
• Computação em Paralelo

eng - English

Instituto Superior Técnico

Financing entity

Fundação para a Ciência e a Tecnologia

Identifier for the funding entity: https://doi.org/10.13039/501100001871

Type of identifier of the funding entity: Crossref Funder

Number for the project, award or grant: 2020.04832.BD