More Like this

1. Nash Equilibrium Problems of Polynomials

   https://doi.org/10.1287/moor.2022.0334  

   Nie, Jiawang; Tang, Xindong (May 2024, Mathematics of Operations Research)

   This paper studies Nash equilibrium problems that are given by polynomial functions. We formulate efficient polynomial optimization problems for computing Nash equilibria. The Moment-sum-of-squares relaxations are used to solve them. Under generic assumptions, the method can find a Nash equilibrium, if there is one. Moreover, it can find all Nash equilibria if there are finitely many ones of them. The method can also detect nonexistence if there is no Nash equilibrium. Funding: J. Nie was supported by the National Science Foundation [Grant DMS-2110780]. 

   more » « less
2. Pareto Front-Diverse Batch Multi-Objective Bayesian Optimization

   https://doi.org/10.1609/aaai.v38i10.28951  

   Ahmadianshalchi, Alaleh; Belakaria, Syrine; Doppa, Janardhan Rao (March 2024, Proceedings of the AAAI Conference on Artificial Intelligence)

   We consider the problem of multi-objective optimization (MOO) of expensive black-box functions with the goal of discovering high-quality and diverse Pareto fronts where we are allowed to evaluate a batch of inputs. This problem arises in many real-world applications including penicillin production where diversity of solutions is critical. We solve this problem in the framework of Bayesian optimization (BO) and propose a novel approach referred to as Pareto front-Diverse Batch Multi-Objective BO (PDBO). PDBO tackles two important challenges: 1) How to automatically select the best acquisition function in each BO iteration, and 2) How to select a diverse batch of inputs by considering multiple objectives. We propose principled solutions to address these two challenges. First, PDBO employs a multi-armed bandit approach to select one acquisition function from a given library. We solve a cheap MOO problem by assigning the selected acquisition function for each expensive objective function to obtain a candidate set of inputs for evaluation. Second, it utilizes Determinantal Point Processes (DPPs) to choose a Pareto-front-diverse batch of inputs for evaluation from the candidate set obtained from the first step. The key parameters for the methods behind these two steps are updated after each round of function evaluations. Experiments on multiple MOO benchmarks demonstrate that PDBO outperforms prior methods in terms of both the quality and diversity of Pareto solutions. 

   more » « less
3. Polynomial optimization relaxations for generalized semi-infinite programs

   https://doi.org/10.1007/s12532-025-00280-4  

   Hu, Xiaomeng; Nie, Jiawang (September 2025, Mathematical Programming Computation)

   Abstract This paper studies generalized semi-infinite programs (GSIPs) given by polynomials. We propose a hierarchy of polynomial optimization relaxations to solve them. They are based on Lagrange multiplier expressions and polynomial extensions. Moment-SOS relaxations are applied to solve the polynomial optimization. The convergence of this hierarchy is shown under certain conditions. In particular, the classical semi-infinite programs can be solved as a special case of GSIPs. We also study GSIPs that have convex infinity constraints and show that they can be solved exactly by a single polynomial optimization relaxation. The computational efficiency is demonstrated by extensive numerical results. 

   more » « less
4. Profiling Pareto Front With Multi-Objective Stein Variational Gradient Descent

   Xingchao Liu; Xin Tong; Qiang Liu (January 2021, Advances in neural information processing systems)

   Finding diverse and representative Pareto solutions from the Pareto front is a key challenge in multi-objective optimization (MOO). In this work, we propose a novel gradient-based algorithm for profiling Pareto front by using Stein variational gradient descent (SVGD). We also provide a counterpart of our method based on Langevin dynamics. Our methods iteratively update a set of points in a parallel fashion to push them towards the Pareto front using multiple gradient descent, while encouraging the diversity between the particles by using the repulsive force mechanism in SVGD, or diffusion noise in Langevin dynamics. Compared with existing gradient-based methods that require predefined preference functions, our method can work efficiently in high dimensional problems, and can obtain more diverse solutions evenly distributed in the Pareto front. Moreover, our methods are theoretically guaranteed to converge to the Pareto front. We demonstrate the effectiveness of our method, especially the SVGD algorithm, through extensive experiments, showing its superiority over existing gradient-based algorithms. 

   more » « less
5. Identifying Redundant Constraints for AC OPF: The Challenges of Local Solutions, Relaxation Tightness, and Approximation Inaccuracy

   https://doi.org/10.1109/NAPS52732.2021.9654442  

   Owen Aquino, Alejandro D.; Roald, Line A.; Molzahn, Daniel K. (November 2021, 2021 North American Power Symposium (NAPS))

   To compute reliable and low-cost operating points, electric power system operators solve optimization problems that enforce inequality constraints such as limits on line flows, voltage magnitudes, and generator outputs. A common empirical observation regarding these constraints is that only a small fraction of them are binding (satisfied with equality) during operation. Furthermore, the same constraints tend to be binding across time periods. Recent research efforts have developed constraint screening algorithms that formalize this observation and allow for screening across operational conditions that are representative of longer time periods. These algorithms identify redundant constraints, i.e., constraints that can never be violated if other constraints are satisfied, by solving optimization problems for each constraint separately. This paper investigates how the choice of power flow formulation, represented either by the non-convex AC power flow, convex relaxations, or a linear DC approximation, impacts the results and the computational time of the screening method. This allows us to characterize the conservativeness of convex relaxations in constraint screening and assess the efficacy of the DC approximation in this context. 

   more » « less