Limited memory bundle method for large bound constrained nonsmooth optimization: convergence analysis

Abstract

Practical optimization problems often involve nonsmooth functions of hundreds or thousands of variables. As a rule, the variables in such large problems are restricted to certain meaningful intervals. In the article [N. Karmitsa and M.M. Mäkelä, Adaptive limited memory bundle method for bound constrained large-scale nonsmooth optimization, Optimization (to appear)], we described an efficient limited-memory bundle method for large-scale nonsmooth, possibly nonconvex, bound constrained optimization. Although this method works very well in numerical experiments, it suffers from one theoretical drawback, namely, that it is not necessarily globally convergent. In this article, a new variant of the method is proposed, and its global convergence for locally Lipschitz continuous functions is proved.

Keywords:

• nondifferentiable programming
• large-scale optimization
• bundle methods
• limited memory methods
• box constraints
• global convergence

Acknowledgements

This work was financially supported by the University of Jyväskylä (Finland) and the University of Turku (Finland).

Notes

If none of the variables are on the boundary, this proof is in fact exactly the same as the proof of Lemma 3.4 in 34.

All of these problems can be downloaded from the website http://napsu.karmitsa.fi/lmbm.