Abstract
A class of implementable algorithms is described for minimizing any convex, not necessarily differentiable, functionf of several variables. The methods require only the calculation off and one subgradient off at designated points. They generalize Lemarechal's bundle method. More specifically, instead of using all previously computed subgradients in search direction finding subproblems that are quadratic programming problems, the methods use an aggregate subgradient which is recursively updated as the algorithms proceed. Each algorithm yields a minimizing sequence of points, and iff has any minimizers, then this sequence converges to a solution of the problem. Particular members of this algorithm class terminate whenf is piecewise linear. The methods are easy to implement and have flexible storage requirements and computational effort per iteration that can be controlled by a user.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J.E. Dennis, Jr. and J.J. Moré, “Quasi-Newton methods, motivation and theory”,SIAM Review 19 (1977) 46–89.
J.E. Kelley, “The cutting-plane method for solving convex programs”,Journal of the Society for Industrial and Applied Mathematics 8 (1960) 703–712.
K.C. Kiwiel, “A variable metric method of centres for nonsmooth minimization”, CP-81-23, International Institute for Applied Systems Analysis (Laxenburg, Austria, June, 1981).
K.C. Kiwiel, “Efficient algorithms for nonsmooth optimization and their applications”, Ph.D. thesis, Dept. of Electronics, Technical University of Warsaw (Warsaw, Poland, 1982).
L.S. Lasdon, “Optimization theory for large systems” (Macmillan, New York, 1970).
C. Lemarechal, “An extension of Davidon methods to nondifferentiable problems,” in: M.L. Balinski and P. Wolfe, eds., “Nondifferentiable optimization”,Mathematical Programming Study 3 (1975) 95–109.
C. Lemarechal, “Nonsmooth optimization and descent methods”, RR-78-4, International Institute for Applied Systems Analysis (Laxenburg, Austria, March, 1978).
C. Lemarechal and R. Mifflin, eds., “Nonsmooth optimization” (Pergamon Press, Oxford, 1978).
R.E. Marsten, W.W. Hogan and J.W. Blankenship, “The boxstep method for large scale optimization”,Operations Research 23 (1975) 389–405.
R. Mifflin, “An algorithm for constrained optimization with semismooth functions”Mathematics of Operations Research 2 (1977) 191–207.
R. Mifflin, “A modification and an extension of Lemarechal's algorithm for nonsmooth minimization,” in: D.C. Sorensen and R.J.-B. Wets, eds., “Nondifferential and variational techniques in optimization”,Mathematical Programming Study 17 (1982) 77–90.
B.N. Pshenichnyi, “Convex analysis and extremal problems” (in Russian) (Nauka, Moscow, 1980).
B.N. Pshenichnyi, “Nonsmooth optimization and nonlinear programming” in: C. Lemarechal and R. Mifflin, eds., “Nonsmooth optimization” (Pergamon Press, Oxford, 1978).
A.P. Wierzbicki, “Lagrangian functions and nondifferentiable optimization”, WP-78-63, International Institute for Applied Systems Analysis (Laxenburg, Austria, December, 1978).
P. Wolfe, “A method of conjugate subgradients for minimizing nondifferentiable functions”, in: M. Balinski and P. Wolfe, eds., “Nondifferentiable optimization”,Mathematical Programming Study 3 (1975) 145–173.
P. Wolfe, “Finding a nearest point in a polytope”,Mathematical Programming 11 (1976) 128–149.
P. Wolfe, “Sufficient minimization of piecewise-linear univariate functions”, in: C. Lemarechal and R. Mifflin, eds., “Nonsmooth optimization” (Pergamon Press, Oxford, 1978).
Author information
Authors and Affiliations
Additional information
Research sponsored by the Institute of Automatic Control, Technical University of Warsaw, Poland, under Project R.I.21.
Rights and permissions
About this article
Cite this article
Kiwiel, K.C. An aggregate subgradient method for nonsmooth convex minimization. Mathematical Programming 27, 320–341 (1983). https://doi.org/10.1007/BF02591907
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02591907