EUVIMEDEUVIMED entdecken
Crossref

A convex combination based primal-dual algorithm with linesearch for general convex-concave saddle point problems

Xiaokai Chang, Junfeng Yang, Hongchao Zhang

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →