Applying Bundle Methods to the Optimization of Polyhedral Functions: An Applications-Oriented Development

Among practical methods for large-scale for Nondifferentiable Optimization (NDO), Bundle methods are widely recognized to play a relevant role; despite their potential, however, they are not often utilized for maximization of polyhedral functions, that appears in many different context such as Lagrangean Duals and decomposition algorithms, since simpler-to-program but less efficient approaches like subgradient methods are preferred. The aim of this work is to provide an applications-oriented survey of the theory of Bundle methods when applied to problems arising in continuous and combinatorial optimization, with an introduction to the several variants of Bundle approaches that can be built up by using a limited set of basic concepts and tools.