On Convergence of the Arrow-Hurwicz Method for Saddle Point Problems

He, Bingsheng1; Xu, Shengjie2,3; Yuan, Xiaoming4

2022-04-01

10.1007/s10851-022-01089-9

JOURNAL OF MATHEMATICAL IMAGING AND VISION   影响因子和分区

0924-9907

1573-7683

The Arrow-Hurwicz method is an inexact version of the Uzawa method; it has been widely applied to solve various saddle point problems in different areas including many fundamental image processing problems. It is also the basis of a number of important algorithms such as the extragradient method and the primal-dual hybrid gradient method. Convergence of the classic Arrow-Hurwicz method, however, is known only when some more restrictive conditions are additionally assumed, such as strong convexity of the functions or some demanding requirements on the step sizes. In this short note, we show by very simple counterexamples that the classic Arrow-Hurwicz method with any constant step size is not necessarily convergent for solving generic convex saddle point problems, including some fundamental cases such as the canonical linear programming model and the bilinear saddle point problem. This result plainly fathoms the convergence understanding of the Arrow-Hurwicz method and retrospectively validates the rationale of studying its convergence under various additional conditions in image processing literature.

Arrow-Hurwicz method Uzawa method Saddle point problem Variational models Image reconstruction Convergence analysis

SCI ; EI

英语

其他

National Natural Science Foundation of China[11871029] ; Research Grants Council, University Grants Committee[12302318]

Computer Science ; Mathematics

Computer Science, Artificial Intelligence ; Computer Science, Software Engineering ; Mathematics, Applied

WOS:000788971200001

SPRINGER

20221812057981

Convergence of numerical methods ; Image reconstruction ; Linear programming

Numerical Methods:921.6

COMPUTER SCIENCE

Web of Science

1.Nanjing Univ, Dept Math, Nanjing, Peoples R China
2.Harbin Inst Technol, Dept Math, Harbin, Peoples R China
3.Southern Univ Sci & Technol, Dept Math, Shenzhen, Peoples R China
4.Univ Hong Kong, Dept Math, Pok Fu Lam, Hong Kong, Peoples R China

He, Bingsheng,Xu, Shengjie,Yuan, Xiaoming. On Convergence of the Arrow-Hurwicz Method for Saddle Point Problems[J]. JOURNAL OF MATHEMATICAL IMAGING AND VISION,2022,64:662-671.

He, Bingsheng,Xu, Shengjie,&Yuan, Xiaoming.(2022).On Convergence of the Arrow-Hurwicz Method for Saddle Point Problems.JOURNAL OF MATHEMATICAL IMAGING AND VISION,64,662-671.

He, Bingsheng,et al."On Convergence of the Arrow-Hurwicz Method for Saddle Point Problems".JOURNAL OF MATHEMATICAL IMAGING AND VISION 64(2022):662-671.