An implicit gradient-descent procedure for minimax problems

Montacer Essid (), Esteban G. Tabak () and Giulio Trigila ()
Additional contact information
Montacer Essid: Courant Institute of Mathematical Sciences
Esteban G. Tabak: Courant Institute of Mathematical Sciences
Giulio Trigila: Baruch College

Mathematical Methods of Operations Research, 2023, vol. 97, issue 1, No 3, 57-89

Abstract: Abstract A game theory inspired methodology is proposed for finding a function’s saddle points. While explicit descent methods are known to have severe convergence issues, implicit methods are natural in an adversarial setting, as they take the other player’s optimal strategy into account. The implicit scheme proposed has an adaptive learning rate that makes it transition to Newton’s method in the neighborhood of saddle points. Convergence is shown through local analysis and through numerical examples in optimal transport and linear programming. An ad-hoc quasi-Newton method is developed for high dimensional problems, for which the inversion of the Hessian of the objective function may entail a high computational cost.

Keywords: Saddle point optimization; Adversarial optimization; Game theory; Optimal transport. (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00186-022-00805-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:97:y:2023:i:1:d:10.1007_s00186-022-00805-w

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s00186-022-00805-w

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().