A Subgradient Algorithm for Certain Minimax and Minisum Problems.
Abstract
This paper presents a subgradient algorithm for the problem Min <F(x); x an element of R to the n power> where F(x) = Max <f sub i(x); i = 1, 2, ..., m> and where f sub i(x) = sum over j of f sub ij(x). Each f sub ij is assumed to be a proper convex function, and the number of different subgradient sets associated with nondifferentiable points of f sub ij is assumed to be finite on any bounded set. Problems belonging to this class include those where the f sub ij are l sub p - norms (1 < or = p < or = infinity); for example, the linear approximation problem and both the minimax and minisum problems of location theory. Convergence of the algorithm to an epsilon - optimal solution is proved and its effectiveness demonstrated by solving a number of problems from location theory and linear approximation theory. Our computational results are compared with other solution methods.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1977
- Accession Number
- ADA050166
Entities
People
- Donald Hearn
- Jacques Chatelon
- Timothy J. Lowe
Organizations
- University of Florida