A reduced-complexity bundle method for maximizing concave nonsmooth functions

Bundle methods have emerged as a promising concept for maximizing nonsmooth concave functions of many variables. A computationally-expensive step in conventional bundle methods is to find a trial direction, and current methods have exponential complexity, making them impractical for large problems. In this paper, a new version of the bundle method is developed, and this method has polynomial complexity in computing a trial direction