Abstract
An algorithm is described for finding the minimum of any convex, not necessarily differentiable, function f of several variables. The algorithm yields a sequence of points tending to the solution of the problem, if any, requiring only the calculation of f and one subgradient of f at designated points. Its rate of convergence is estimated for convex and for differentiable convex functions. For the latter, it is an extension of the method of conjugate gradients and terminates for quadratic functions.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
D.P. Bertsekas and S. Mitter, “A descent numerical method for optimization problems with nondifferentiable cost functions,” SIAM Journal on Control 11 (1973) 637–652.
J. Cullum, W.E. Donath and P. Wolfe, “The minimization of certain nondifferentiable sums of eigenvalues of symmetric matrices,” Mathematical Programming Study 3 (1975) 35–55 (this volume).
H.P. Crowder and P. Wolfe, “Linear convergence of the conjugate gradient method,” IBM Journal of Research and Development 16 (1972) 431–433.
V.F. Demjanov, “Algorithms for some minimax problems,” Journal of Computer and System Sciences 2 (1968) 342–380.
G.B. Dantzig and P. Wolfe, “The decomposition algorithm for linear programming,” Econometrica 29 (1961) 767–778.
J.P. Evans, F.J. Gould and J.W. Tolle, “Exact penalty functions in nonlinear programming,” Mathematical Programming 4 (1973) 72–97.
A. Feuer, “Minimizing well-behaved functions,” in: Proceedings of the twelfth annual Allerton conference on circuit and system theory, University of Illinois (October, 1974).
R. Fletcher, “A FORTRAN subroutine for minimization by the method of conjugate gradients,” AERE-R 7073, Theoretical Physics Division, A.E.R.E., Harwell, Berkshire (1972).
A.M. Geoffrion, “Elements of large-scale mathematical programming,” in: A.M. Geoffrion, ed., Perspectives on optimization (Addison-Wesley, Reading, Mass., 1972), ch. 2.
M. Held, R.M. Karp and P. Wolfe, “Large-scale optimization and the relaxation method”, in: Proceedings of the 25th national ACM meeting, Boston, Mass. (August, 1972).
W.W. Hogan, R.E. Marsten and J.W. Blankenship, “Boxstep: a new strategy for large scale mathematical programming,” Discussion Paper No. 46, Northwestern University, Evanston, Ill. (May, 1973).
M.R. Hestenes and E. Stiefel, “Methods of conjugate gradients for solving linear systems,” Journal of Research of the National Bureau of Standards 49 (1952) 409–436.
M. Held, P. Wolfe and H.P. Crowder, “Validation of subgradient optimization,” Mathematical Programming 6 (1974) 62–88.
C. Lemarechal, An algorithm for minimizing convex functions. Proceedings IFIP Congress 74 (August. 1974) 552–555.
C. Lemarechal, “An extension of Davidon methods to non differentiable functions,” Mathematical Programming Study 3 (1975) 95–109 (this volume).
M. Lenard, “Practical convergence conditions for restarted conjugate gradient methods,” MRC Tech. Summary Rept. No. 1373, Mathematical Research Center, University of Wisconsin, Madison (December 1973).
G.P. McCormick and K. Ritter, “On the convergence and rate of convergence of the conjugate gradient method”, George Washington University Serial T-266 (1972).
M.J.D. Powell, Conversation at Yorktown Heights, N.Y., March, 1975.
M.J.D. Powell, “A view of unconstrained optimization,” Rept. C.S.S. 14, Computer Science and Systems Division, A.E.R.E. Harwell, Oxfordshire (January, 1975).
R.T. Rockafellar, “Convex analysis” (Princeton University Press, Princeton, N.J., 1970).
N.Z. Shor, “Utilization of the operation of space dilatation in the minimization of convex functions,” Cybernetics (1970) 7–15. [Translation of Kybernetika 1 (1970) 6–12.]
N.Z. Shor, “Convergence rate of the gradient descent method with dilatation of the space”, Cybernetics (1970) 102–108. [Translation of Kybernetika 2 (1970) 80–85.]
P. Wolfe, “Convergence conditions for ascent methods,” SIAM Review 11, (1969) 226–235.
P. Wolfe, “Convergence theory in nonlinear programming,” in: J. Abadie, ed. Integer and nonlinear programming (North-Holland, Amsterdam, 1970) pp. 1–36.
P. Wolfe, “On the convergence of gradient methods under constraint,” IBM Journal of Research and Development 16 (1972) 407–411.
P. Wolfe, “An algorithm for the nearest point in a polytope”, IBM Research Center Report RC 4887 (June, 1974).
P. Wolfe, “An optimization problem arising in algorithm design”. Unpublishable manuscript (April, 1974).
G. Zoutendijk, Methods of feasible directions (Elsevier, Amsterdam, 1960).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1975 The Mathematical Programming Society
About this chapter
Cite this chapter
Wolfe, P. (1975). A method of conjugate subgradients for minimizing nondifferentiable functions. In: Balinski, M.L., Wolfe, P. (eds) Nondifferentiable Optimization. Mathematical Programming Studies, vol 3. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0120703
Download citation
DOI: https://doi.org/10.1007/BFb0120703
Received:
Revised:
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00763-7
Online ISBN: 978-3-642-00764-4
eBook Packages: Springer Book Archive