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

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.