Christoph Helmberg, Alois Pichler: Dynamic Scaling and Submodel Selection in Bundle Methods for Convex Optimization

Author(s):

Christoph Helmberg
Alois Pichler

Title:

Christoph Helmberg, Alois Pichler: Dynamic Scaling and Submodel Selection in Bundle Methods for Convex Optimization

Electronic source:

application/pdf

Preprint series:

Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 04, 2017

Mathematics Subject Classification:

    90C25 []
    90C06 []
    65K05 []

Abstract:

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.

Keywords:

nonsmooth optimization, numerical methods

Language:

English

Publication time:

8/2017