A convex combination based primal-dual algorithm with linesearch for general convex-concave saddle point problems
IMA Journal of Numerical Analysis · 12.04.2026
DOI: 10.1093/imanum/draf158 ↗Kurz gefasst
Fachartikel in der Zeitschrift IMA Journal of Numerical Analysis, online erschienen am 12.04.2026. Verfasst von Xiaokai Chang und 2 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 38 Literaturangaben. Gefördert von: National Natural Science Foundation of China, Key Laboratory of NSLSCS of the Ministry of Education of China, National Natural Science Foundation of U.S.A.
Abstract (Originalsprache)
Using convex combination and linesearch techniques, we introduce a novel primal-dual algorithm for solving structured convex–concave saddle point problems with a generic, smooth, nonbilinear coupling term. Our adaptive linesearch strategy works under specific local smoothness conditions, allowing for potentially larger step sizes. For an important class of structured convex optimization problems, the proposed algorithm reduces to a fully adaptive proximal gradient algorithm without linesearch, thereby representing an advancement over the golden ratio algorithm delineated in Malitsky,Y. (2020, Golden ratio algorithms for variational inequalities. Math. Program., 184, 383–410). We establish the global pointwise and ergodic sublinear convergence rate of the algorithm, measured by the restricted merit function in the general case. When the coupling term is linear in the dual variable, we measure the convergence rate by the function value residual and constraint violation of an equivalent constrained optimization problem. Furthermore, an accelerated algorithm achieving a faster $ O(1/N^{2})$ ergodic convergence rate is presented for the strongly convex case, where $N$ denotes the iteration number. The convergence rates established in this work are optimal (up to a constant factor) under the corresponding assumptions. Our numerical experiments on quadratically constrained quadratic programming and sparse logistic regression problems indicate that the new algorithm is significantly faster than the comparison algorithms.
Förderung
- National Natural Science Foundation of China
- Key Laboratory of NSLSCS of the Ministry of Education of China
- National Natural Science Foundation of U.S.A
- U.S.A. Office of Naval Research
Zitieren
APA
Chang, X., Yang, J., & Zhang, H. (2026). A convex combination based primal-dual algorithm with linesearch for general convex-concave saddle point problems. IMA Journal of Numerical Analysis. https://doi.org/10.1093/imanum/draf158
Vancouver
Chang X, Yang J, Zhang H. A convex combination based primal-dual algorithm with linesearch for general convex-concave saddle point problems. IMA Journal of Numerical Analysis. 2026. doi:10.1093/imanum/draf158
BibTeX
@article{Chang2026,
author = {Chang, Xiaokai and Yang, Junfeng and Zhang, Hongchao},
title = {A convex combination based primal-dual algorithm with linesearch for general convex-concave saddle point problems},
journal = {IMA Journal of Numerical Analysis},
year = {2026},
doi = {10.1093/imanum/draf158}
}
EUVIMED