Dynamic Scaling and Submodel Selection in Bundle Methods for Convex Optimization

Bundle methods determine the next candidate point as the minimizer of a cutting model augmented with a proximal term. We propose a dynamic approach for choosing a quadratic proximal term based on subgradient information from past evaluations. For the special case of convex quadratic functions, conditions are studied under which this actually reproduces the Hessian. The approach forms the basis of an efficiently implementable variant that uses only the diagonal as dynamic scaling information. The second topic addresses the choice of the cutting model when minimizing the sum of several convex functions. We propose a simple rule for dynamically choosing a few functions that are each modeled by a separate cutting model while the others are subsumed in a common sum model and combine this with the scaling approach. Numerical experiments with a development version of the callable library ConicBundle illustrate the benefits of these techniques on a class of large scale instances of practical relevance.

Citation

Preprint 2017-4, Technische Universit├Ąt Chemnitz, Faculty of Mathematics, 09107 Chemnitz, Germany

Article

Download

View Dynamic Scaling and Submodel Selection in Bundle Methods for Convex Optimization