Preprint A166/2002
On approximations with finite precision in bundle methods for nonsmooth optimization

Mikhail Solodov

**Keywords: **
Nonsmooth optimization | convex optimization | bundle methods | stability analysis | perturbation

We consider the proximal form of a bundle algorithm for
minimizing a nonsmooth convex function, assuming that
the function and subgradient values are evaluated approximately.
We show how those approximations should be controlled in order
to satisfy the desired optimality tolerance.
This is relevant, for example, in the context of
Lagrangian relaxation, where obtaining exact information about
the function and subgradient values involves solving exactly
a certain optimization problem, which can be relatively costly
(and, as we show, is in any case unnecessary).
We exhibit that approximation with some finite precision
is sufficient in this setting, and give an explicit characterization
of this precision. Alternatively, our result can be viewed
as a stability analysis of standard proximal bundle methods,
as it answers the following question: for a given
approximation error, what kind of an
approximate solution can be obtained and how does it depend
on the magnitude of the perturbation?