Journal article icon

Journal article

Consensus-based optimization for saddle point problems

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 two groups of interacting particles, one which performs a minimization over one variable while the other performs a maximization over the other variable. The two groups constantly exchange information through a suitably weighted average. This paradigm permits a passage to the mean-field limit, which makes the method amenable to theoretical analysis, and it allows to obtain rigorous convergence guarantees under reasonable assumptions about the initialization and the objective function, which most notably include nonconvex-nonconcave objectives. We further provide numerical evidence for the success of the algorithm.
Publication status:
Published
Peer review status:
Peer reviewed

Actions

Access Document

Publisher copy:
10.1137/22m1543367

Authors

More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Mathematical Institute
Role:
Author
ORCID:
0000-0002-2206-4334


Publisher:
Society for Industrial and Applied Mathematics
Journal:
SIAM Journal on Control and Optimization More from this journal
Volume:
62
Issue:
2
Pages:
1093-1121
Publication date:
2024-03-25
Acceptance date:
2023-09-22
DOI:
EISSN:
1095-7138
ISSN:
0363-0129


Terms of use


Views and Downloads

Views and downloads will return soon






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP