Level bundle methods for oracles with on-demand accuracy

Abstract

For non-smooth convex optimization, we consider level bundle methods built using an oracle that computes values for the objective function and a subgradient at any given feasible point. For the problems of interest, the exact oracle information is computable, but difficult to obtain. In order to save computational effort the oracle can provide estimations with an accuracy that depends on two additional parameters, informed to the oracle together with the evaluation point. The first of such parameters is a descent target, while the second one is a bound for inexactness. If the oracle can reach the target with its function estimation, then the corresponding error is bounded by the second parameter. Otherwise, if the oracle detects that the target cannot be met, the function and subgradient estimations can be rough and have an unknown accuracy. For some selected iterates the considered methods drive the inexactness parameter to zero, thus ensuring that an exact solution to the optimization problem is asymptotically found. The approach is comprehensive and covers known exact and inexact level methods as well as some novel variants that can handle inaccuracy in an adaptive manner. In particular, when the feasible set is also compact, some of the new on-demand accuracy methods have the same rate of convergence of exact level variants known in the literature. A numerical benchmark on a battery of two-stage stochastic linear programs assesses the interest of the approach, substantially faster than the L-shaped method, without any accuracy loss.

Keywords:

• bundle methods
• inexact oracles
• non-smooth optimization
• level methods

Acknowledgements

The authors are grateful to the reviewers for their insightful comments and remarks.

Funding

Research of the second author was partially supported by Grants CNPq 303840/2011-0, AFOSR FA9550-08-1-0370, NSF DMS 0707205, as well as by PRONEX-Optimization and FAPERJ.