<p dir="ltr">Constrained optimization plays a crucial role in numerous scientific and engineering fields, where solutions must satisfy specific constraints while optimizing an objective function. The complexity of these problems has driven the development of efficient algorithms. Primal-dual methods, particularly, have been a powerful class of algorithms capable of tackling constrained optimization problems. This dissertation introduces and analyzes new Lagrangian-based primal-dual methods, exploring their applications in the equilibrium computation of generalized Nash games and non-convex constrained optimization problems. </p><p dir="ltr">Generalized Nash games, also known as generalized Nash equilibrium problems, expand the concept of classical Nash games by incorporating coupled constraints, which substantially increase their computational complexity. These games are prevalent in a variety of real-world applications, such as electricity markets, economic markets, transportation networks, and various multi-agent systems, where decision-makers are required to engage in strategic actions while also considering coupled constraints. We develop a primal-dual first-order method for efficient computation of generalized Nash equilibrium, providing its theoretical foundations and practical implementation. </p><p dir="ltr">Non-convex constrained optimization problems often emerge across various application domains, presenting significant theoretical and computational challenges due to the presence of non-convex constraints and objective functions. To address these challenges, we propose and analyze novel Lagrangian-based primal-dual methods designed to manage non-convex constraints and establish their convergence properties. We perform extensive numerical experiments to demonstrate the practicality and versatility of our proposed methods. The results show the efficacy of our methods in tackling the computational challenges associated with generalized Nash games and non-convex constrained optimization.</p>

This thesis is a computational study of recently developed algorithms which aim to overcome degeneracy in the simplex method. We study the following algorithms: the non-negative least squares algorithm, the least-squares primal-dual algorithm, the least-squares network flow algorithm, and the combined-objective least-squares algorithm. All of the four algorithms use least-squares measures to solve their subproblems, so they do not exhibit degeneracy. But they have never been efficiently implemented and thus their performance has also not been proved. In this research we implement these algorithms in an efficient manner and improve their performance compared to their preliminary results. For the non-negative least-squares algorithm, we develop the basis update technique and data structure that fit our purpose. In addition, we also develop a measure to help find a good ordering of columns and rows so that we have a sparse and concise representation of QR-factors. The least-squares primal-dual algorithm uses the non-negative least-squares problem as its subproblem, which minimizes infeasibility while satisfying dual feasibility and complementary slackness. The least-squares network flow algorithm is the least-squares primal-dual algorithm applied to min-cost network flow instances. The least-squares network flow algorithm can efficiently solve much bigger instances than the least-squares primal-dual algorithm. The combined-objective least-squares algorithm is the primal version of the least-squares primal-dual algorithm. Each subproblem tries to minimize true objective and infeasibility simultaneously so that optimality and primal feasibility can be obtained together. It uses a big-M to minimize the infeasibility. We developed the techniques to improve the convergence rates of each algorithm: the relaxation of complementary slackness condition, special pricing strategy, and dynamic-M value. Our computational results show that the least-squares primal-dual algorithm and the combined-objective least-squares algorithm perform better than the CPLEX Primal solver, but are slower than the CPLEX Dual solver. The least-squares network flow algorithm performs as fast as the CPLEX Network solver.

The minimum cost bipartite matching problem is a well-studied optimization problem in computer science and operations research, with wide-ranging applications in fields such as machine learning, economics, transportation, logistics and biology. A special instance of this problem is the computation of the p-Wasserstein distance which we define next. Given a complete bipartite graph with two disjoint sets of n points in d-dimensional Euclidean space and an integer p ≥ 1, let the cost of an edge be the p-th power of the Euclidean distance between its endpoints. The objective of this problem is to find a minimum-cost matching in this complete bipartite graph. The Hungarian algorithm is a classical method that solves this problem in O(n^3) time. There are many algorithms that have a run time better than that of the Hungarian algorithm if the graphs have non-negative integer edge costs bounded by C. Since the input points have real-valued coordinates and the Euclidean distances can be irrational, such algorithms only return an approximate matching. Thus, the Hungarian algorithm remains the fastest known algorithm to compute an exact matching. In this thesis, we implement a new algorithm in the divide and conquer framework that computes the exact p-Wasserstein distance and has a run time asymptotically better than the Hungarian algorithm for stochastic point sets. Inspired by the techniques used in the algorithm, we also design an alternate version of the Hungarian algorithm that uses a grid- based approach. Our experimental analysis shows that both of our algorithms significantly outperform the classical Hungarian algorithm. / Master of Science / Suppose we have two sets of equal number of items and a list of compatible pairs of items, where a pair is considered compatible if its items belong to different sets. A perfect matching is a subset of compatible pairs where each item is paired with exactly one other item. When trying to find a perfect matching, there may be multiple options, and minimizing the cost of the perfect matching is often desired. This is referred to as the minimum cost bipartite matching problem, which is extensively studied due to its importance in algorithmic theory and operations research. A special instance of this problem is the calculation of the p- Wasserstein distance. It has many practical applications in fields such as machine learning, economics, transportation, logistics and biology. The Hungarian algorithm is the only known algorithm that can compute the exact p-Wasserstein distance. Therefore, our focus is to develop exact algorithms for this problem that perform better than the Hungarian algorithm and can scale efficiently to large datasets.

Optimization methods nowadays play a very important role in financial decisions such as portfolio managements, construction of index funds and pension funds.  This Master Thesis is devoted to the problem of an index fund construction. The problem is represented as a linear optimization problem of re-balancing the portfolio at minimum cost and solved using the Primal-Dual interior point method. The index fund is constructed using ten companies from the Dow Jones Industrial Average Index (DJIA). The Primal-Dual interior point method was first implemented in Matlab and later on in Java.

Background: Young adults ages 18-24 are disproportionally affected by unintended pregnancy and sexually transmitted diseases and infections (STD/I). The best protection against both pregnancy and STD/Is is dual contraceptive use: the concurrent use of a highly effective contraceptive method and a condom. Objectives: This dissertation aims to increase our understanding of the psychosocial constructs associated with contraceptive and condom use. This project: 1) examines differences in contraceptive and STD/I knowledge by sex and race, and its association with method use; 2) determines the association between relationship characteristics and dual use; and 3) uses the Theory of Triadic Influence to examine direct and indirect associations between sociocultural factors, interpersonal factors, biological factors, and dual use. Methods: Young adult college students ages 18-24 (N=4,196) were invited to complete a web-based, cross-sectional, sexual health survey in Fall 2018. Multivariable linear and logistic regression models were run to determine differences in contraceptive knowledge by sex and race and its association with effective method use (N=436), and differences in STD/I knowledge by sex and race and its association with condom use (N=414). Multiple logistic regression models were run to determine the association between relationship characteristics, pregnancy and condom attitudes, demographics, and dual use (N=463). Structural equation modeling (SEM) was used to assess the standardized direct and indirect associations of sociocultural, interpersonal, and biological factors and dual use (N=406). Results: Increased contraceptive knowledge was associated with 1.114 odds increase in effective method use (95% CI: 1.058, 1.172), but no association was found between STD/I knowledge and condom use (aOR=0.970, 95% CI: 0.940, 1.000). Adjusted for all relationship characteristics, one-unit increase in trust was associated with decreased odds of dual use (aOR=0.982; 95% CI 0.966, 0.998). In independent models, having sex with a casual date/acquaintance (aOR=3.149; 95% CI: 1.550-6.397) compared to a romantic partner was associated with increased odds of dual use. The hypothesized SEM measurement model had poor fit and was re-specified. The final model had moderate fit and explained 70% of the variance in overall dual use. Condom attitudes (β = 0.18) and partner commitment (β = -0.22) were significantly associated with dual use through intention. Intention was significantly associated with dual use (β = 0.84). Conclusions: Findings emphasize the influential nature of interpersonal and biological psychosocial constructs on method use behavior. Health programs that address partner influences on STD/I risk perceptions, method use intention, and method use behavior could be beneficial for young adults. / Epidemiology

Spread options are derivative securities, which are written on the difference between the values of two underlying market variables. They are very important tools to hedge the correlation risk. American style spread options allow the holder to exercise the option at any time up to and including maturity. Although they are widely used to hedge and speculate in financial market, the valuation of the American spread option is very challenging. Because even under the classic assumptions that the underlying assets follow the log-normal distribution, the resulting spread doesn't have a distribution with a simple closed formula. In this dissertation, we investigate the American spread option pricing problem. Several approaches for the geometric Brownian motion model and the stochastic volatility model are developed. We also implement the above models and the numerical results are compared among different approaches.

Neste trabalho, os métodos de pontos interiores primal-dual e preditor corretor são estudados e desenvolvidos para o problema de minimização de custos na geração e perdas na transmissão do pré-despacho DC (fluxo de carga em corrente contínua) de um sistema de potência hidroelétrico, com base no modelo de fluxo em redes e no princípio do mínimo esforço. A estrutura matricial, resultante da simplificação do problema proposto pela inclusão do princípio do mínimo esforço, é estudada visando implementações eficientes. / In this work, the primal-dual and predictor corrector interior points methods are studied and developed for the predispatch DC problem that minimizes generation and transmission losses on hydroelectric power systems, on the basis of the network flow model and the minimum effort principle. The matrix structure, resulting of the simplification of the problem considered by inclusion of the minimum effort principle, is studied aiming efficient implementations. A disturbed primal-dual method is considered on the basis of a heuristic definition that determine the choice of the disturbance parameter. This method showed to be efficient in practice and converged in fewer iterations when compare with an existing implementation of the network flow model.

Submitted by ANA KARLA PEREIRA RODRIGUES (anakarla_@hotmail.com) on 2017-08-14T11:52:04Z No. of bitstreams: 1 arquivototal.pdf: 1035035 bytes, checksum: 24db9b859fa0c32ac6b5b442ef6e12fa (MD5) / Made available in DSpace on 2017-08-14T11:52:04Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 1035035 bytes, checksum: 24db9b859fa0c32ac6b5b442ef6e12fa (MD5) Previous issue date: 2016-11-28 / In this work we study the existence of multi-bump solutions to a certain class of elliptic problems involving biharmonic problems. Moreover, we apply the method developed to biharmonic for study the existence of multi-bump solutions to Choquard Equation. / Neste trabalho estudamos a existência de soluções multi-bump para uma determinada classe de problemas elípticos que envolvem o operador Biharmônico. Além disso, aplicamos o método desenvolvido para o biharmônico no estudo da existência de solução multi-bump para equação de Choquard.

Neste trabalho, os métodos de pontos interiores primal-dual e preditor corretor são estudados e desenvolvidos para o problema de minimização de custos na geração e perdas na transmissão do pré-despacho DC (fluxo de carga em corrente contínua) de um sistema de potência hidroelétrico, com base no modelo de fluxo em redes e no princípio do mínimo esforço. A estrutura matricial, resultante da simplificação do problema proposto pela inclusão do princípio do mínimo esforço, é estudada visando implementações eficientes. / In this work, the primal-dual and predictor corrector interior points methods are studied and developed for the predispatch DC problem that minimizes generation and transmission losses on hydroelectric power systems, on the basis of the network flow model and the minimum effort principle. The matrix structure, resulting of the simplification of the problem considered by inclusion of the minimum effort principle, is studied aiming efficient implementations. A disturbed primal-dual method is considered on the basis of a heuristic definition that determine the choice of the disturbance parameter. This method showed to be efficient in practice and converged in fewer iterations when compare with an existing implementation of the network flow model.