A generalized primal-dual algorithm with improved convergence condition for saddle point problems

2021/12/01 by Bingsheng He, He, Bingsheng, Feng Ma +5 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Matrix Theory and Algorithms #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.2112.00254

openalex publication_date 2021/12/01 · openalex created_date 2021/12/06 · openalex updated_date 2026/07/28

Abstract

We generalize the well-known primal-dual algorithm proposed by Chambolle and Pock for saddle point problems, and improve the condition for ensuring its convergence. The improved convergence-guaranteeing condition is effective for the generic setting, and it is shown to be optimal. It also allows us to discern larger step sizes for the resulting subproblems, and thus provides a simple and universal way to improve numerical performance of the original primal-dual algorithm. In addition, we present a structure-exploring heuristic to further relax the convergence-guaranteeing condition for some specific saddle point problems, which could yield much larger step sizes and hence significantly better performance. Effectiveness of this heuristic is numerically illustrated by the classic assignment problem.

Citations

• From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
• Monotone Operators and the Proximal Point Algorithm
• On the Convergence of Primal-Dual Hybrid Gradient Algorithm
• Atomic Decomposition by Basis Pursuit

Cited by

• A Triple-Bregman Balanced Primal-Dual Algorithm for Saddle Point Problems

Related

• Optimal Primal-Dual Methods for a Class of Saddle Point Problems
• First-order primal-dual algorithm with correction
• Accelerated Primal Dual Method for a Class of Saddle Point Problem with Strongly Convex Component
• Inexact First-Order Primal-Dual Algorithms
• Primal-Dual Sequential Subspace Optimization for Saddle-point Problems