Ergodic Results and Bounds on the Optimal Value in Subgradient Optimization

Torbjörn Larsson, Ann-Brith Strömberg and Michael Patriksson
Department of Mathematics
Linköping Institute of Technology
S-581 83 Linköping
Sweden

ABSTRACT:

Subgradient methods for nonsmooth optimization have rendered considerable
popularity, mainly in the context of Lagrangean relaxation; this is due to
their simplicity and proven practical usefulness.
We consider the minimization of a nonsmooth convex function over a convex and
compact set, using a (conditional) subgradient optimization scheme with
divergent series step lengths.
We show that such a scheme may be augmented by a convergent lower bounding
procedure based on the computation of an ergodic (averaged) sequence of
subgradients and of affine functions underestimating the objective.
The sequence of lower bounds enables a judgement of the quality of the
solutions obtained, and can thus be used in a termination criterion.
Numerical experience from an application of the bounding procedure within a
subgradient scheme for a nonsmooth formulation of the linear multicommodity
network flow problem is presented.