Abstract
We propose a modification of the classical extragradient and proximal point algorithms for finding a zero of a maximal monotone operator in a Hilbert space. At each iteration of the method, an approximate extragradient-type step is performed using information obtained from an approximate solution of a proximal point subproblem. The algorithm is of a hybrid type, as it combines steps of the extragradient and proximal methods. Furthermore, the algorithm uses elements in the enlargement (proposed by Burachik, Iusem and Svaiter) of the operator defining the problem. One of the important features of our approach is that it allows significant relaxation of tolerance requirements imposed on the solution of proximal point subproblems. This yields a more practical proximal-algorithm-based framework. Weak global convergence and local linear rate of convergence are established under suitable assumptions. It is further demonstrated that the modified forward-backward splitting algorithm of Tseng falls within the presented general framework.
Similar content being viewed by others
References
Auslender, A.: Numerical methods for nondifferentiable convex optimization, Math.Programming Study 30(1987), 102–126.
Burachik, R. S., Iusem, A. N. and Svaiter, B. F.: Enlargement of monotone operators with applications to variational inequalities, Set-Valued Anal. 5(1997), 159–180.
Burachik, R. S., Sagastizábal, C. A. and Svaiter, B. F.: "-Enlargements of maximal monotone operators: Theory and applications, in: M. Fukushima and L. Qi (eds), Reformulation - Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, Kluwer Acad. Publ., 1999, pp. 25–44.
Burke, J. V. and Qian, M.: A variable metric proximal point algorithm for monotone operators, SIAM J.Control Optim. 37(1998), 353–375.
Chen, H.-G.: Forward-backward splitting techniques: Theory and applications, PhD Thesis, University of Washington, Seattle, Washington, December 1994.
Chen, X. and Fukushima, M.: Proximal quasi-Newton methods for nondifferentiable convex optimization, Math.Programming (1999), to appear.
Cominetti, R.: Coupling the proximal point algorithm with approximation methods, J.Optim. Theory Appl. 95(1997), 581–600.
Eckstein, J.: Approximate iterations in Bregman-function-based proximal algorithms, Math. Programming 83(1998), 113–123.
Eckstein, J. and Bertsekas, D. P.: On the Douglas- Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math.Programming 55(1992), 293–318.
Ferris, M. C.: Finite termination of the proximal point algorithm, Math.Programming 50 (1991), 359–366.
Gabay, D.: Applications of the method of multipliers to variational inequalities, in: M. Fortin and R. Glowinski (eds), Augmented Lagrangian Methods: Applications to the Solution of Boundary-Value Problems, North-Holland, 1983, pp. 299–331.
Georgiev, P. Gr.: Submonotone mappings in Banach spaces and applications, Set-Valued Anal. 5(1997), 1–35.
Güler, O.: New proximal point algorithms for convex minimization, SIAM J.Optim. 2(1992), 649–664.
Korpelevich, G. M.: The extragradient method for finding saddle points and other problems, Matecon 12(1976), 747–756.
Lemaire, B.: The proximal algorithm, in: dJ. P. Penot (ed.), New Methods of Optimization and Their Industrial Use, Internat. Ser. Numer. Math. 87, Birkhäuser, Basel, 1989, pp. 73–87.
Lions, P. L. and Mercier, B.: Splitting algorithms for the sum of two nonlinear operators, SIAM J.Numer.Anal. 16(1979), 964–979.
Luque, F. J.: Asymptotic convergence analysis of the proximal point algorithm, SIAMJ.Control Optim. 2 2 (1984), 277–293.
Martinet, B.: Regularisation d'inequations variationelles par approximations successives, Revue Française d'Informatique et de Recherche Opérationelle 4(1970), 154–159.
Minty, G. J.: Monotone (nonlinear) operators in Hilbert space, Duke Math.J. 29(1962), 341–346.
Opial, Z.: Weak convergence of the sequence of successive approximations for nonexpansive mappings, Bull.Amer.Math.Soc. 73(1967), 591–597.
Passty, G. B.: Weak convergence theorems for nonexpansive mappings in Banach spaces, J.Math.Anal.Appl. 67(1979), 274–276.
Qi, L. and Chen, X.: A preconditioning proximal Newton method for nondifferentiable convex optimization, Technical Report AMR 95/20, Department of Applied Mathematics, University of New South Wales, Sydney, SW, Australia, 1995.
Rockafellar, R. T.: On the maximality of sums of nonlinear monotone operators, Trans.Amer. Math.Soc. 149(1970), 75–88.
Rockafellar, R. T.: Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math.Oper.Res. 1(1976), 97–116.
Rockafellar, R. T.: Monotone operators and the proximal point algorithm, SIAM J.Control Optim. 14(1976), 877–898.
Solodov, M. V. and Svaiter, B. F.: A new projection method for variational inequality problems, SIAM J.Control Optim. 37(1999), 765–776.
Solodov, M. V. and Svaiter, B. F.: Forcing strong convergence of proximal point iterations in a Hilbert space, Math.Programming (1997), to appear.
Solodov, M. V. and Svaiter, B. F.: A globally convergent inexact Newton method for systems of monotone equations, in: M. Fukushima and L. Qi (eds), Reformulation - Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, Kluwer Acad. Publ., Dordrecht, 1999, pp. 355–369.
Solodov, M. V. and Svaiter, B. F.: An inexact hybrid generalized proximal point algorithm and some new results on the theory of Bregman functions, Math.Oper.Res. (1998), to appear.
Solodov, M. V. and Svaiter, B. F.: A hybrid projection - proximal point algorithm, J.Convex Anal. 6( 1)(1999).
Spingarn, J. E.: Submonotone subdifferentials of Lipschitz functions, Trans.Amer.Math.Soc. 264(1981), 77–89.
Tossings, P.: The perturbed proximal point algorithm and some of its applications, Appl.Math. Optim. 29(1994), 125–159.
Tseng, P.: Further applications of a splitting algorithm to decomposition in variational inequalities and convex programming, Math.Programming 48(1990), 249–263.
Tseng, P.: Applications of a splitting algorithm to decomposition in convex programming and variational inequalities, SIAM J.Control Optim. 29(1991), 119–138.
Tseng, P.: A modified forward-backward splitting method for maximal monotone mappings, Department of Mathematics, University of Washington, Seattle, WA, 1998.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Solodov, M.V., Svaiter, B.F. A Hybrid Approximate Extragradient – Proximal Point Algorithm Using the Enlargement of a Maximal Monotone Operator. Set-Valued Analysis 7, 323–345 (1999). https://doi.org/10.1023/A:1008777829180
Issue Date:
DOI: https://doi.org/10.1023/A:1008777829180