Abstract
In this paper, 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 ofm sets, the variational inequality decomposes intom 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 Mangasarian and De Leone, a diagonalization algorithm of Feijoo and Meyer, the coordinate descent method, and the dual gradient method. This algorithm is also closely related to a splitting algorithm of Gabay and a gradient projection algorithm of Goldstein and of Levitin-Poljak, and has interesting applications to separable convex programming and to solving traffic assignment problems.
Similar content being viewed by others
References
Rockafellar, R. T.,Network Flows and Monotropic Optimization, Wiley-Interscience, New York, New York, 1984.
Feijoo, B., andMeyer, R. R.,Piecewise-Linear Approximation Methods for Nonseparable Convex Programming, Management Science, Vol. 34, pp. 411–419, 1988.
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.
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.
D'Esopo, D. A.,A Convex Programming Procedure, Naval Research Logistics Quarterly, Vol. 6, pp. 33–42, 1959.
Luenberger, D. G.,Linear and Nonlinear Programming, Addison-Wesley, Reading, Massachusetts, 1984.
Powell, M. J. D.,On Search Directions for Minimization Algorithms, Mathematical Programming, Vol. 4, pp. 193–201, 1973.
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.
Zangwill, W. I.,Nonlinear Programming, Prentice-Hall, Englewood Cliffs, New Jersey, 1969.
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.
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.
Goldstein, A. A.,Convex Programming in Hilbert Space, Bulletin of the American Mathematical Society, Vol. 70, pp. 709–710, 1964.
Levitin, E. S., andPoljak, B. T.,Constrained Minimization Methods, Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki, Vol. 6, pp. 787–823, 1966 (in Russian).
Luque, J.,The Nonlinear Proximal Point Algorithm, Massachusetts Institute of Technology, Laboratory for Information and Decision Systems, Report No. P-1598, 1986.
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.
Rockafellar, R. T.,Monotone Operators and the Proximal Point Algorithm, SIAM Journal on Control and Optimization, Vol. 14, pp. 877–898, 1976.
Dafermos, S. C.,An Iterative Scheme for Variational Inequalities, Mathematical Programming, Vol. 26, pp. 40–47, 1983.
Bertsekas, D. P., andTsitsiklis, J. N.,Parallel and Distributed Computation: Numerical Methods, Prentice-Hall, Englewood Cliffs, New Jersey, 1989.
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).
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.
Pang, J. S.,Asymmetric Variational Inequality Problems over Product Sets: Applications and Iterative Methods, Mathematical Programming, Vol. 31, pp. 206–219, 1985.
Bertsekas, D. P.,Constrained Optimization and Lagrange Multiplier Methods, Academic Press, New York, New York, 1982.
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.
Rockafellar, R. T.,Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970.
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.
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.
Tseng, P.,Coordinate Ascent for Maximizing Nondifferentiable Concave Functions, Massachusetts Institute of Technology, Laboratory for Information and Decision Systems, Report No. P-1840, 1988.
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.
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.
Chen, R. J., andMeyer, R. R.,Parallel Optimization for Traffic Assignment, Mathematical Programming, Vol. 42, pp. 327–345, 1988.
Dafermos, S. C.,Traffic Equilibrium and Variational Inequalities, Transportation Science, Vol. 14, pp. 42–54, 1980.
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.
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.
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.
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.
Author information
Authors and Affiliations
Additional information
Communicated by O. L. Mangasarian
This work was partially supported by the US Army Research Office Contract No. DAAL03-86-K-0171 and by the National Science Foundation Grant No. ECS-85-19058. The author thanks the referees for their many helpful comments, particularly for suggesting the use of a general functionH instead of that given by (4).
Rights and permissions
About this article
Cite this article
Tseng, P. Decomposition algorithm for convex differentiable minimization. J Optim Theory Appl 70, 109–135 (1991). https://doi.org/10.1007/BF00940507
Issue Date:
DOI: https://doi.org/10.1007/BF00940507