zbMATH — the first resource for mathematics

New proximal point algorithms for convex minimization. (English) Zbl 0778.90052
Two modifications of the classical proximal point algorithm for the optimization problem \(\min_{x\in R^ n} f(x)\) are studied, under the only assumption that \(f: R^ n\to R\cup\{+\infty\}\) is a proper lower- semicontinuous convex function. In both of them, starting with an initial point \(x_ 0\in R^ n\), an auxiliary sequence \(\{y_ k\}^ \infty_{k=0}\) of approximately optimal solutions is computed according to \(x_{k+1}=J_{\lambda_ k} x_ k:=\arg\min_{x\in R^ n}\bigl\{f(x)+(1/2\lambda_ k)\| x-y_ k\|^ 2\bigr\}\), \(\{\lambda_ k\}^ \infty_{k=0}\) being a sequence of positive numbers. In the first variant, a sequence \(\{\varphi_ k\}^ \infty_{k=0}\) of strictly convex quadratic functions is generated in such a way that, for all \(k\geq 0\) and \(x\in R^ n\), \(\varphi_{k+1}(x)- f(x)\leq (1-\alpha_ k)(\varphi_ k(x)-f(x))\) for some \(\alpha_ k\in[0,1)\) and one sets \(y_ k=(1-\alpha_ k)x_ k+\alpha_ k\nu_ k\), with \(\nu_ k\) being the minimizer of \(\varphi_ k\). For this algorithm, it is proved that \(f(x_ k)-\inf_{x\in R^ n} f(x)=O\Bigl(1\Bigl/\Bigl(\sum^{k-1}_{j=0}\sqrt{\lambda_ j}\Bigr)^ 2\Bigr)\) while, for the second variant, \(f(x_ k)-\inf_{x\in R^ n} f(x)=O(1/(k+1)^ 2)\).

90C25 Convex programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text: DOI