An accelerated minimax algorithm for convex-concave saddle point problems with nonsmooth coupling function

Radu Ioan Boţ (), Ernö Robert Csetnek () and Michael Sedlmayer ()
Additional contact information
Radu Ioan Boţ: University of Vienna
Ernö Robert Csetnek: University of Vienna
Michael Sedlmayer: University of Vienna

Computational Optimization and Applications, 2023, vol. 86, issue 3, No 6, 925-966

Abstract: Abstract In this work we aim to solve a convex-concave saddle point problem, where the convex-concave coupling function is smooth in one variable and nonsmooth in the other and not assumed to be linear in either. The problem is augmented by a nonsmooth regulariser in the smooth component. We propose and investigate a novel algorithm under the name of OGAProx, consisting of an optimistic gradient ascent step in the smooth variable coupled with a proximal step of the regulariser, and which is alternated with a proximal step in the nonsmooth component of the coupling function. We consider the situations convex-concave, convex-strongly concave and strongly convex-strongly concave related to the saddle point problem under investigation. Regarding iterates we obtain (weak) convergence, a convergence rate of order $$\mathcal {O}(\frac{1}{K})$$ O ( 1 K ) and linear convergence like $$\mathcal {O}(\theta ^{K})$$ O ( θ K ) with $$\theta

Keywords: Saddle point problem; Convex-concave; Minimax algorithm; Convergence rate; Acceleration; Linear convergence (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/s10589-022-00378-8 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:coopap:v:86:y:2023:i:3:d:10.1007_s10589-022-00378-8

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

DOI: 10.1007/s10589-022-00378-8

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().