Abstract
We present a subgradient algorithm for minimizing the maximum of a finite collection of functions. It is assumed that each function is the sum of a finite collection of basic convex functions and that the number of different subgradient sets associated with nondifferentiable points of each basic function is finite on any bounded set. Problems belonging to this class include the linear approximation problem and both the minimax and minisum problems of location theory. Convergence of the algorithm to an epsilon-optimal solution is proven and its effectiveness is demonstrated by solving a number of location problems and linear approximation problems.
Similar content being viewed by others
References
I. Barrodale and A. Young, “Computational experience in solving linear operator equations using the Chebyshev norm”, in: S.G. Hayes, ed.,Numerical approximation to functions and data (The Athlone Press, London, 1970) pp. 115–142.
D.P. Bertsekas and S. Mitter, “A descent numerical method for optimization problems with nondifferentiable cost functionals”,SIAM Journal on Control 11 (1973) 637–652.
F.H. Clarke, “Generalized gradients and applications”,Transactions of the American Mathematical Society 205 (1975) 247–262.
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.
P.M. Dearing and R.L. Francis, “A network flow solution to a multifacility minimax location problem involving rectilinear distances”,Transportation Science 8 (1974) 126–141.
V.F. Dem'yanov and V.N. Malozemov,Introduction to minimax (John Wiley, 1974).
J. Elzinga, D.W. Hearn and W.D. Randolph, “Minimax multifacility location with Euclidean distances”,Transportation Science 10 (1976) 321–336.
J.W. Eyster, J.A. White and W.W. Wierwille, “On solving multifacility location problems using a hyperboloid approximation procedure”,A.I.I.E. Transactions 5 (1973) 1–6.
A. Feuer, “An implementable mathematical programming algorithm for admissible fundamental functions”, Ph.D. Dissertation, Department of Mathematics, Columbia University, New York (1974).
E.G. Gilbert, “An iterative procedure for computing the minimum of a quadratic form on a convex set”,SIAM Journal on Control 4 (1966) 61–80.
A.A. Goldstein, “Optimization of Lipschitz continuous functions”,Mathematical Programming 13 (1977) 14–22.
J. Greenstadt, “Variations on variable metric methods”,Mathematics of Computation 24 (1970) 1–22.
D.W. Hearn and T.J. Lowe, “A subgradient procedure for the solution of minimax location problems”,Computers and Industrial Engineering 2 (1978) 17–25.
H.W. Kuhn and R.E. Kuenne, “An efficient algorithm for the numerical solution of the generalized Weber problem in spatial economics”,Journal of Regional Science 4 (1962) 21–33.
C. Lemarechal, “An extension of Davidon methods to nondifferentiable functions”,Mathematical Programming Study 3 (1975) 95–109.
D.G. Luenberger,Introduction to linear and nonlinear programming (Addison-Wesley, 1973).
R. Mifflin, “An algorithm for constrained optimization with semismooth functions”,Mathematics of Operations Research 2 (1977) 191–207.
Pshenichnyi,Necessary conditions for an extremum (Marcel Dekker, New York, 1971).
R.T. Rockafellar,Convex analysis (Princeton University Press, N.J., 1970).
P. Wolfe, “A method of conjugate subgradients for minimizing nondifferentiable functions”,Mathematical Programming Study 3 (1975) 145–173.
P. Wolfe, “Finding the nearest point in a polytope”,Mathematical Programming 11 (1976) 128–144.
Author information
Authors and Affiliations
Additional information
This research was partially supported by the Army Research Office, Triangle Park, NC, under contract number DAH-CO4-75-G-0150, and by NSF grants ENG 16-24294 and ENG 75-10225.
Rights and permissions
About this article
Cite this article
Chatelon, J.A., Hearn, D.W. & Lowe, T.J. A subgradient algorithm for certain minimax and minisum problems. Mathematical Programming 15, 130–145 (1978). https://doi.org/10.1007/BF01609012
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01609012