Consensus-Based Optimization for Saddle Point Problems

DOI10.1137/22M1543367MaRDI QIDQ6421517zbMATH OpenOpenAlexFDO

Authors Hui Huang, Jinniao Qiu, Konstantin Riedl

Publication date 23 December 2022

Full work available at URL https://doi.org/10.1137/22m1543367

Mathematics Subject Classification ID

Vlasov equations (35Q83) PDEs in connection with mathematical programming (35Q90) Stochastic particle methods (65C35) Numerical mathematical programming methods (65K05) Minimax problems in mathematical programming (90C47) Derivative-free methods and methods using generalized derivatives (90C56)

Abstract: In this paper, we propose consensus-based optimization for saddle point problems (CBO-SP), a novel multi-particle metaheuristic derivative-free optimization method capable of provably finding global Nash equilibria. Following the idea of swarm intelligence, the method employs a group of interacting particles, which perform a minimization over one variable and a maximization over the other. This paradigm permits a passage to the mean-field limit, which makes the method amenable to theoretical analysis and allows to obtain rigorous convergence guarantees under reasonable assumptions about the initialization and the objective function, which most notably include nonconvex-nonconcave objectives.

Recommendations

• Consensus-based optimization methods converge globally
• Consensus-based optimization via jump-diffusion stochastic differential equations
• Constrained Consensus-Based Optimization
• Trends in Consensus-Based Optimization
• One dimensional consensus based algorithm for non-convex optimization

Cited in

(14)

• Consensus-based optimization for multi-objective problems: a multi-swarm approach
• Consensus-based optimization methods converge globally
• Uniform-in-time mean-field limit estimate for the consensus-based optimization
• Tensor cross interpolation for global discrete optimization with application to Bayesian network inference
• A multiscale consensus-based algorithm for multilevel optimization
• A consensus-based algorithm for non-convex multiplayer games
• A PDE framework of consensus-based optimization for objectives with multiple global minimizers
• Consensus, error estimates and applications of first- and second-order consensus-based optimization algorithms
• Self-interacting CBO: existence, uniqueness, and long-time convergence
• A particle consensus approach to solving nonconvex-nonconcave min-max problems
• Kinetic variable-sample methods for stochastic optimization problems
• Well-posedness and mean-field limit estimate of a consensus-based algorithm for multiplayer games
• Uniform-in-time weak propagation of chaos for consensus-based optimization
• A consensus-based optimization method for nonsmooth nonconvex programs with approximated gradient descent scheme

This page was built for publication: Consensus-Based Optimization for Saddle Point Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6421517)