Metraipolis › archive › dc_5cd0052d56d5

A New Primal-Dual Algorithm with Two Convex Combinations and Linesearch for General Convex-Concave Saddle-Point Problems — arXiv:2608.28993

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.28993
License (as archived)
CC0-1.0
Archived
2026-10-17T09:02:45.805Z
SHA-256 of the archived text
7d01fe04f62708da8b4d6cd4c607a84959ef63f82db31d22e427af4f4701b2ae
Stable URL of this page
https://metraipolis.com/documento/dc_5cd0052d56d5

How to cite

A New Primal-Dual Algorithm with Two Convex Combinations and Linesearch for General Convex-Concave Saddle-Point Problems — arXiv:2608.28993 — arXiv (en), https://arxiv.org/abs/2608.28993 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5cd0052d56d5 (Metraipolis archive dc_5cd0052d56d5, sha256 7d01fe04f62708da8b4d6cd4c607a84959ef63f82db31d22e427af4f4701b2ae)
BibTeX
@misc{dc5cd0052d56d5,
  title = {A New Primal-Dual Algorithm with Two Convex Combinations and Linesearch for General Convex-Concave Saddle-Point Problems — arXiv:2608.28993},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.28993},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5cd0052d56d5; sha256 7d01fe04f62708da8b4d6cd4c607a84959ef63f82db31d22e427af4f4701b2ae},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.28993. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Convex-concave saddle-point problems are ubiquitous across diverse domains, including machine learning, image processing, economics, and equilibrium problems. Primal-dual algorithms provide a highly effective and powerful framework for convex-concave saddle-point problems. Convex combination has become a crucial acceleration technique for primal-dual algorithms, and the integration of this technique has recently made these algorithms a highly active research topic. The choice of the convex combination parameter often has a significant impact on both the theoretical analysis and the numerical performance of the corresponding algorithms. However, the requirements on this parameter imposed by theory are sometimes inconsistent with those suggested by numerical experiments. For instance, theoretical analysis often requires the parameter to be small, while numerical experiments tend sometimes to favor larger values. To address this inconsistency and further advance primal-dual algorithms with convex combination, we develop a novel strategy based on two convex combinations, integrate it into a primal-dual framework, and propose a new primal-dual algorithm with linesearch, termed NPDAL-n, for general convex-concave saddle-point problems. The proposed two convex combinations in NPDAL-n ensure that the permissible range of the convex combination parameters is mainly determined by theoretical considerations, with little regard for numerical performance. Through rigorous Lyapunov energy descent analysis, we establish the global convergence and a sublinear ergodic convergence rate of $\mathcal{O}(1/N)$ for NPDAL-n under standard assumptions. When the primal function is strongly convex, we develop an accelerated version of NPDAL-n that achieves an optimal $\mathcal{O}(1/N^2)$ rate.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-01 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2608.28993 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T08:40:19.722Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).