Finite termination of the proximal point algorithm (Q1176570)

This paper is concerned with aspects of the relationship of a sharp minimum on a set to the proximal point algorithm, in the context of the convex programming problem (1): minimize \(\{\phi(x)\mid x\in X\}\), where \(\phi\) is a closed convex function on \(\mathbb{R}^ n\) and \(S\) is a closed convex set in \(\mathbb{R}^ n\). By introducing the closed convex function \(\phi_ S(x)=\phi(x)+\psi(x\mid S)\), (1) is equivalent to minimize \(\{\phi_ S(x)\mid x\in\mathbb{R}^ n\}\). The author defines a sharp minimum as a generalization of that of \textit{B. T. Polyak} [``Introduction to optimization'', Optimization Software (New York 1987); for the 1983 Russian original see Zbl 0652.49002], who defines \(\bar x\in S\) as a sharp minimim of \(\phi\) if there exists \(\alpha>0\) with \(\phi(x)- \phi(\bar x)\geq\alpha\| x-\bar x\|\) for all \(x\in S\). If \(\partial\phi_ S\) is the subdifferential, (1) can be solved by finding a solution of a generalized equation \(0\in\partial\phi_ S(x)\). Defining the resolvent \(J_ \lambda\) as \(J_ \lambda=(I+\lambda\partial\phi_ S)^{-1}\) then \(0\in\partial\phi_ S(x)\Leftrightarrow x=J_ \lambda x\) for some \(\lambda>0\). The proximal point method generates the sequence \(\{x_ i\}\), defined by \(x^{i+1}=J_{\lambda_ i}x^ i\) where \(\lambda_ i\geq\lambda>0\) for all \(i\). The main result lies in showing that, if (1) has a sharp minimum, the proximal point algorithm terminates in a finite number of iterations. A final theorem shows that, for any given starting vector, the proximal point algorithm terminates in one iteration for sufficiently large \(\lambda\).