# 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)$$.

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