Optimization Online


Proximal bundle methods in depth: a unified analysis for inexact oracles

Welington Oliveira (wlo***at***impa.br)
Claudia Sagastizábal (sagastiz***at***impa.br)
Claude Lemaréchal (claude.lemarechal***at***inria.fr)

Abstract: The last few years have seen the advent ofa new generation of bundle methods, capable to handle inexact oracles, polluted by ``noise''. Proving convergence of a bundle method is never simple and coping with inexact oracles substantially increases the technicalities. Besides, several variants exist to deal with noise, each one needing an ad hoc proof to show convergence, keeping in mind that in the presence of inexactness convergence is to be understood in an approximate manner. The purpose of this paper is twofold. First, we state a synthetic convergence theory, in which we highlight the main arguments and specify which assumption is used to establish each intermediate result. Our framework is comprehensive and generalizes in various ways a number of algorithms proposed in the literature, for which we show convergence without much effort. Second, based on the ingredients of our synthetic theory, we consider new bundle variants adapted to oracles for which high accuracy is possible, yet it is preferable not to make exact calculations often, because they are too time consuming.

Keywords: Convex optimization, nonsmooth optimization, bundle methods

Category 1: Convex and Nonsmooth Optimization


Download: [PDF]

Entry Submitted: 02/06/2013
Entry Accepted: 02/26/2013
Entry Last Modified: 12/02/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society