Standard Bundle Methods: Untrusted Models and Duality

We review the basic ideas underlying the vast family of algorithms for nonsmooth convex optimization known as “bundle methods”. In a nutshell, these approaches are based on constructing models of the function, but lack of continuity of first-order information implies that these models cannot be trusted, not even close to an optimum. Therefore, many different forms of stabilization have been proposed to try to avoid being led to areas where the model is so inaccurate as to result in almost useless steps. In the development of these methods, duality arguments are useful, if not outright necessary, to better analyze the behaviour of the algorithms. In addition, in many relevant applications the function at hand is itself a dual one, so that duality allows to map back algorithmic concepts and results into a “primal space” where they can be exploited; in turn, structure in that space can be exploited to improve the algorithms’ behaviour, e.g. by developing better models. We present an updated picture of the many developments around the basic idea along at least three different axes: form of the stabilization, form of the model, and approximate evaluation of the function.