×

Convergence analysis and applications of the Glowinski-Le Tallec splitting method for finding a zero of the sum of two maximal monotone operators. (English) Zbl 0908.90209

Summary: Many problems of convex programming can be reduced to finding a zero of the sum of two maximal monotone operators. For solving this problem, there exists a variety of methods such as the forward-backward method, the Peaceman-Rachford method, the Douglas-Rachford method, and more recently the \(\theta\)-scheme. This last method has been presented without general convergence analysis by Glowinski and Le Tallec and seems to give good numerical results. The purpose of this paper is first to present convergence results and an estimation of the rate of convergence for this recent method, and then to apply it to variational inequalities and structured convex programming problems to get new parallel decomposition algorithms.

MSC:

90C25 Convex programming
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Mahey, P., and Pham, D. T., Partial Regularization of the Sum of Two Maximal Monotone Operators, Modélisation Mathématique et Analyse Numérique, Vol. 92, pp. 375–392, 1995.
[2] Mahey, P., Oualibouch, S., and Pham, D. T., Proximal Decomposition on the Graph of Maximal Monotone Operators, SIAM Journal on Optimization, Vol. 5, pp. 454–466, 1995. · Zbl 0834.90105
[3] Passty, G. B., Ergodic Convergence to a Zero of the Sum of Monotone Operators in Hilbert Space, Journal of Mathematical Analysis and Applications, Vol. 72, pp. 383–390, 1979. · Zbl 0428.47039
[4] Gabay, D., Application of the Method of Multipliers to Variational Inequalities, Augmented Lagrangian Methods: Applications to the Solution of Boundary-Valued Problems, Edited by M. Fortin and R. Glowinski, North-Holland, Amsterdam, Holland, pp. 299–331, 1983.
[5] Tseng, P., Further Applications of a Splitting Algorithm to Decomposition in Variational Inequalities and Convex Programming, Mathematical Programming, Vol. 48, pp. 249–263, 1990. · Zbl 0725.90079
[6] Tseng, P., Applications of a Splitting Algorithm to Decomposition in Convex Programming and Variational Inequalities, SIAM Journal on Control and Optimization, Vol. 29, pp. 119–138, 1991. · Zbl 0737.90048
[7] Chen, G., and Rockafellar, R. T., Application of a Splitting Algorithm to Optimal Control and Extended Linear-Quadratic Programming, Technical Report, Department of Applied Mathematics, University of Washington, 1990.
[8] Chen, G., and Rockafellar, R. T., Convergence and Structure of Forward-Backward Splitting Methods, Technical Report, Department of Applied Mathematics, University of Washington, 1990.
[9] Chen, G., and Rockafellar, R. T., Extended Forward-Backward Splitting Methods and Convergence, Technical Report, Department of Applied Mathematics, University of Washington, 1990.
[10] Chen, G., and Rockafellar, R. T., Forward-Backward Splitting Methods in Lagrangian Optimization, Technical Report, Department of Applied Mathematics, University of Washington, 1992.
[11] Zhu, C., Asymptotic Convergence Analysis of the Forward-Backward Splitting Algorithm, Mathematics of Operations Research, Vol. 20, pp. 449–464, 1995. · Zbl 0837.90114
[12] Peaceman, D. H., and Rachford, H. H., The Numerical Solution of Parabolic Elliptic Differential Equations, SIAM Journal on Applied Mathematics, Vol. 3, pp. 28–41, 1955. · Zbl 0067.35801
[13] Lions, P. L., and Mercier, B., Splitting Algorithms for the Sum of Two Nonlinear Operators, SIAM Journal on Numerical Analysis, Vol. 16, pp. 964–979, 1979. · Zbl 0426.65050
[14] Douglas, J., and Rachford, H. H., On the Numerical Solution of the Heat Conduction Problem in 2 and 3 Space Variables, Transactions of the American Mathematical Society, Vol. 82, pp. 421–439, 1956. · Zbl 0070.35401
[15] Eckstein, J., and Bertsekas, D. P., On the Douglas-Rachford Splitting Method and the Proximal Point Algorithm for Maximal Monotone Operators, Mathematical Programming, Vol. 55, pp. 293–318, 1992. · Zbl 0765.90073
[16] Glowinski, R., Splitting Methods for the Numerical Solution to the Incompressible Navier-Stokes Equations, Vistas in Applied Mathematics: Atmospheric Sciences, Immunology, Edited by A. V. Balakrishnan, A. A. Dorodnitsyn, and J. L. Lions, Optimization Software, New York, New York, pp. 57–95, 1986.
[17] Glowinski, R., and Le Tallec, P., Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics, SIAM, Philadelphia, Pennsylvania, 1989. · Zbl 0698.73001
[18] Le Tallec, P., Numerical Analysis of Viscoelastic Problems, Masson, Paris, France, 1990. · Zbl 0718.73091
[19] Mouallif, K., Nguyen, V. H., and Strodiot, J. J., A Perturbed Parallel Decomposition Method for a Class of Nonsmooth Convex Minimization Problems, SIAM Journal on Control and Optimization, Vol. 29, pp. 829–847, 1991. · Zbl 0733.65038
[20] Fukushima, M., Haddou, M., Nguyen, V. H., Strodiot, J. J., Sugimoto, T., and Yamakawa, E., A Parallel Descent Algorithm for Convex Programming, Computational Optimization and Applications, Vol. 5, pp. 5–37, 1996. · Zbl 0844.90065
[21] BrÉzis, H., Opérateurs Maximaux Monotones et Semi-Groupes de Contraction dans les Espaces de Hilbert, North-Holland, Amsterdam, Holland, 1973. · Zbl 0252.47055
[22] Rockafellar, R. T., Monotone Operators and the Proximal Point Algorithm, SIAM Journal on Control and Optimization, Vol. 14, pp. 877–898, 1976. · Zbl 0358.90053
[23] Rockafellar, R. T., On the Maximality of Sums of Nonlinear Monotone Operators, Transactions of the American Mathematical Society, Vol. 149, pp. 75–88, 1970. · Zbl 0222.47017
[24] Rockafellar, R. T., Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970. · Zbl 0193.18401
[25] Eckstein, J., and Fukushima, M., Some Reformulations and Applications of the Alternating Direction Method of Multipliers, Large-Scale Optimization: State of the Art, Edited by W. W. Hager, D. W. Hearn, and P. M. Pardalos, Kluwer Academic Publishers, Dordrecht, Netherlands, pp. 115–134, 1994. · Zbl 0816.90109
[26] Chen, G., and Teboulle, M., A Proximal-Based Decomposition Method for Convex Minimization Problems, Mathematical Programming, Vol. 64, pp. 81–101, 1994. · Zbl 0823.90097
[27] Auslender, A., Cominetti, R., and Crouzeix, J.P., Convex Functions with Unbounded Level Sets and Applications to Duality Theory, SIAM Journal on Optimization, Vol. 3, pp. 669–687, 1993. · Zbl 0808.90102
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.