A Generalized Primal-Dual Algorithm with Improved Convergence Condition for Saddle Point Problems

He, Bingsheng1; Ma, Feng2; Xu, Shengjie3,4; Yuan, Xiaoming5

2022

10.1137/21M1453463

SIAM Journal on Imaging Sciences   Impact Factor & Quartile

1936-4954

We generalize the well-known primal-dual algorithm proposed by Chambolle and Pock for saddle point problems and relax the condition for ensuring its convergence. The relaxed convergence -guaranteeing condition is effective for the generic convex setting of saddle point problems, and we show by the canonical convex programming problem with linear equality constraints that the relaxed condition is optimal. It also allows us to discern larger step sizes for the resulting sub-problems, 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.

saddle point problem convex programming image processing primal-dual algorithm convergence condition assignment problem

SCI

English

Others

National Natural Science Foundation of China (NSFC)[11871029] ; NSFC["12171481","11871264"] ; Guangdong Basic and Applied Basic Research Foundation of China[2018A0303130123] ; General Research Fund from Hong Kong Research Grants Council[12302318]

Computer Science ; Mathematics ; Imaging Science & Photographic Technology

Computer Science, Artificial Intelligence ; Computer Science, Software Engineering ; Mathematics, Applied ; Imaging Science & Photographic Technology

WOS:000894217500002

SIAM PUBLICATIONS

Web of Science

1.Nanjing Univ, Dept Math, Nanjing, Peoples R China
2.High Tech Inst Xian, Xian 710025, Shaanxi, Peoples R China
3.Harbin Inst Technol, Dept Math, Harbin, Peoples R China
4.Southern Univ Sci & Technol, Dept Math, Shenzhen, Peoples R China
5.Univ Hong Kong, Dept Math, Hong Kong, Peoples R China

He, Bingsheng,Ma, Feng,Xu, Shengjie,et al. A Generalized Primal-Dual Algorithm with Improved Convergence Condition for Saddle Point Problems[J]. SIAM Journal on Imaging Sciences,2022,15(3).

He, Bingsheng,Ma, Feng,Xu, Shengjie,&Yuan, Xiaoming.(2022).A Generalized Primal-Dual Algorithm with Improved Convergence Condition for Saddle Point Problems.SIAM Journal on Imaging Sciences,15(3).

He, Bingsheng,et al."A Generalized Primal-Dual Algorithm with Improved Convergence Condition for Saddle Point Problems".SIAM Journal on Imaging Sciences 15.3(2022).