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?

Anexos:

• r.ps