A proximal point algorithm for minimax problems (Q1371666)

This paper presents a proximal point algorithm for solving discrete \(\ell_\infty\) approximation problems of the form minimize \(\| Ax-b \|_\infty\) where \(A\in \mathbb{R}^{m \times n}\), \(b\in\mathbb{R}^m\) and \(x\in \mathbb{R}^n\). If \((\varepsilon_\ell)\) is a sequence of arbitrary positive real numbers then, starting from an arbitrary initial point \(z_0\in \mathbb{R}^n\), the algorithm will generate a sequence of points \(z_\ell\in \mathbb{R}^n\), \(\ell=0\), \(1,\dots\), where \(z_{\ell+1}\) is obtained from \(z_\ell\) via the rule \[ z_{\ell+1}= {\underset {z} {\text{argmin}}} \bigl\{\textstyle {1\over 2} \varepsilon_\ell \| z-z_\ell \|^2_2+ \textstyle {1\over 2} \| Az-b\|^2 \bigr\}. \] One establishes convergence of the proposed algorithm. Numerical experiments illustrate the feasibility of the ideas.