<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.

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.

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.