zbMATH — the first resource for mathematics

Decomposition algorithm for convex differentiable minimization. (English) Zbl 0739.90052
Summary: We propose a decomposition algorithm for convex differentiable minimization. This algorithm at each iteration solves a variational inequality problem obtained by adding to the gradient of the cost function a strongly proximal related function. A line search is then performed in the direction of the solution to this variational inequality (with respect to the original cost). If the constraint set is a Cartesian product of \(m\) sets, the variational inequality decomposes into \(m\) coupled variational inequalities, which can be solved in either a Jacobi manner or a Gauss-Seidel manner. This algorithm also applies to the minimization of a strongly convex (possibly nondifferentiable) cost subject to linear constraints. As special cases, we obtain the GP-SOR algorithm of O. Mangasarian and R. De Leone [Ann. Oper. Res. 14, 41–59 (1988; Zbl 0739.90068)], a diagonalization algorithm of B. Feijoo and R. R. Meyer [Manage. Sci. 34, No. 3, 411–419 (1988; Zbl 0648.90059)], the coordinate descent method, and the dual gradient method. This algorithm is also closely related to a splitting algorithm of D. Gabay [in: M. Fortin and R. Glowinski (eds.), “Augmented Lagrangian methods: application to the numerical solution of boundary-value problems”, Stud. Math. Appl. 15, 299–331 (1983; Zbl 0525.65045)] and a gradient projection algorithm of A. A. Goldstein [Bull. Am. Math. Soc. 70, 709–710 (1964; Zbl 0142.17101)) and of E. S. Levitin and B. T. Polyak [Zh. Vychisl. Mat. Mat. Fiz. 6, 787–823 (1966); translation in USSR Comput. Math. Math. Phys. 6 (1966), No. 5, 1–50 (1968; Zbl 0184.38902)] and has interesting applications to separable convex programming and to solving traffic assignment problems.

90C25 Convex programming
49J40 Variational inequalities
65K05 Numerical mathematical programming methods
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
49M27 Decomposition methods
Full Text: DOI
[1] Rockafellar, R. T.,Network Flows and Monotropic Optimization, Wiley-Interscience, New York, New York, 1984. · Zbl 0596.90055
[2] Feijoo, B., andMeyer, R. R.,Piecewise-Linear Approximation Methods for Nonseparable Convex Programming, Management Science, Vol. 34, pp. 411-419, 1988. · Zbl 0648.90059 · doi:10.1287/mnsc.34.3.411
[3] Lin, Y. Y., andPang, J. S.,Iterative Methods for Large Convex Quadratic Programs: A Survey, SIAM Journal on Control and Optimization, Vol. 25, pp. 383-411, 1987. · Zbl 0624.90083 · doi:10.1137/0325023
[4] Mangasarian, O. L., andDe Leone, R.,Parallel Gradient Projection Successive Overrelaxation for Symmetric Linear Complementarity Problems, Annals of Operations Research, Vol. 14, pp. 41-59, 1988. · Zbl 0739.90068 · doi:10.1007/BF02186473
[5] D’Esopo, D. A.,A Convex Programming Procedure, Naval Research Logistics Quarterly, Vol. 6, pp. 33-42, 1959. · doi:10.1002/nav.3800060105
[6] Luenberger, D. G.,Linear and Nonlinear Programming, Addison-Wesley, Reading, Massachusetts, 1984. · Zbl 0571.90051
[7] Powell, M. J. D.,On Search Directions for Minimization Algorithms, Mathematical Programming, Vol. 4, pp. 193-201, 1973. · Zbl 0258.90043 · doi:10.1007/BF01584660
[8] Sargent, R. W. H., andSebastian, D. J.,On the Convergence of Sequential Minimization Algorithms, Journal of Optimization Theory and Applications, Vol. 12, pp. 567-575, 1973. · Zbl 0253.65037 · doi:10.1007/BF00934779
[9] Zangwill, W. I.,Nonlinear Programming, Prentice-Hall, Englewood Cliffs, New Jersey, 1969.
[10] Pang, J.-S.,More Results on the Convergence of Iterative Methods for the Symmetric Linear Complementarity Problem, Journal of Optimization Theory and Applications, Vol. 49, pp. 107-134, 1986. · Zbl 0568.90096 · doi:10.1007/BF00939250
[11] Gabay, D.,Applications of the Method of Multipliers to Variational Inequalities, Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems, Edited by M. Fortin and R. Glowinski, North-Holland, Amsterdam, Holland, pp. 299-331, 1983.
[12] Goldstein, A. A.,Convex Programming in Hilbert Space, Bulletin of the American Mathematical Society, Vol. 70, pp. 709-710, 1964. · Zbl 0142.17101 · doi:10.1090/S0002-9904-1964-11178-2
[13] Levitin, E. S., andPoljak, B. T.,Constrained Minimization Methods, Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, Vol. 6, pp. 787-823, 1966 (in Russian). · Zbl 0184.38902
[14] Luque, J.,The Nonlinear Proximal Point Algorithm, Massachusetts Institute of Technology, Laboratory for Information and Decision Systems, Report No. P-1598, 1986.
[15] Martinet, B.,Détermination approchée d’un point fixe d’une application pseudocontractante. Cas de l’application prox, Comptes Rendus des Séances de l’Académie des Sciences, Série A, Vol. 274, pp. 163-165, 1972.
[16] 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 · doi:10.1137/0314056
[17] Dafermos, S. C.,An Iterative Scheme for Variational Inequalities, Mathematical Programming, Vol. 26, pp. 40-47, 1983. · Zbl 0506.65026 · doi:10.1007/BF02591891
[18] Bertsekas, D. P., andTsitsiklis, J. N.,Parallel and Distributed Computation: Numerical Methods, Prentice-Hall, Englewood Cliffs, New Jersey, 1989. · Zbl 0743.65107
[19] Korpelevich, G. M.,The Extragradient Method for Finding Saddle Points and Other Problems, Ekonomika i Matematicheskie Metody, Vol. 12, pp. 747-756, 1976 (in Russian). · Zbl 0342.90044
[20] Lions, P. L., andMercier, B.,Splitting Algorithms for the Sum of Two Nonlinear Operators, SIAM Journal on Numerical Analysis, Vol. 16, pp. 964-979, 1979. · Zbl 0426.65050 · doi:10.1137/0716071
[21] Pang, J. S.,Asymmetric Variational Inequality Problems over Product Sets: Applications and Iterative Methods, Mathematical Programming, Vol. 31, pp. 206-219, 1985. · Zbl 0578.49006 · doi:10.1007/BF02591749
[22] Bertsekas, D. P.,Constrained Optimization and Lagrange Multiplier Methods, Academic Press, New York, New York, 1982. · Zbl 0572.90067
[23] Tseng, P.,Dual Ascent Methods for Problems with Strictly Convex Costs and Linear Constraints: A Unified Approach, SIAM Journal on Control and Optimization, Vol. 28, pp. 214-242, 1990. · Zbl 0692.49025 · doi:10.1137/0328011
[24] Rockafellar, R. T.,Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970. · Zbl 0193.18401
[25] Tseng, P., andBertsekas, D. P.,Relaxation Methods for Problems with Strictly Convex Costs and Linear Inequality Constraints, Massachusetts Institute of Technology, Laboratory for Information and Decision Systems, Report No. P-1717, 1987. · Zbl 0636.90072
[26] Rockafellar, R. T.,Augmented Lagrangians and Applications for the Proximal Point Algorithms in Convex Programming, Mathematics of Operations Research, Vol. 1, pp. 97-116, 1976. · Zbl 0402.90076 · doi:10.1287/moor.1.2.97
[27] Tseng, P.,Coordinate Ascent for Maximizing Nondifferentiable Concave Functions, Massachusetts Institute of Technology, Laboratory for Information and Decision Systems, Report No. P-1840, 1988.
[28] Aashtiani, H. Z., andMagnanti, T. L.,Equilibria on a Congested Transportation Network, SIAM Journal on Algebraic and Discrete Methods, Vol. 2, pp. 213-226, 1981. · Zbl 0501.90033 · doi:10.1137/0602024
[29] Bertsekas, D. P., andGafni, E. M.,Projection Methods for Variational Inequalities with Application to the Traffic Assignment Problem, Mathematical Programming Study, Vol. 17, pp. 139-159, 1982. · Zbl 0478.90071
[30] Chen, R. J., andMeyer, R. R.,Parallel Optimization for Traffic Assignment, Mathematical Programming, Vol. 42, pp. 327-345, 1988. · Zbl 0665.90030 · doi:10.1007/BF01589409
[31] Dafermos, S. C.,Traffic Equilibrium and Variational Inequalities, Transportation Science, Vol. 14, pp. 42-54, 1980. · doi:10.1287/trsc.14.1.42
[32] Bertsekas, D. P., Hosein, P. A., andTseng, P.,Relaxation Methods for Network Flow Problems with Convex Arc Costs, SIAM Journal on Control and Optimization, Vol. 25, pp. 1219-1243, 1987. · Zbl 0641.90036 · doi:10.1137/0325067
[33] Dembo, R. S., andKlincewicz, J. G.,A Scaled Reduced-Gradient Algorithm for Network Flow Problems with Convex Separable Costs, Mathematical Programming Study, Vol. 15, pp. 125-147, 1981. · Zbl 0477.90025
[34] Miller, C. E.,The Simplex Method for Local Separable Programming, Recent Avances in Mathematical Programming, Edited by R. L. Graves and P. Wolfe, McGraw-Hill, New York, New York, pp. 89-100, 1963. · Zbl 0232.90060
[35] 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 · doi:10.1137/0329006
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.