Optimization Online


Nonsmooth Optimization Using Uncontrolled Inexact Information

Jérôme Malick(jerome.malick***at***inria.fr)
Welington de Oliveira(wlo***at***impa.br)
sofia Zaourar(sofia.zaourar***at***inria.fr)

Abstract: We consider convex nonsmooth optimization problems whose objective function is known through a (fine) oracle together with some additional (cheap but poor) information – formalized as a second coarse oracle with uncontrolled inexactness. It is the case when the objective function is itself the output of an optimization solver, using a branch-and-bound procedure, or decomposing the problem into parallel subproblems. Minimizing such objective function can be done by any bundle algorithm using only the (fine) oracle. In this paper, we propose a general scheme to incorporate the available coarse information into bundle-type methods in view of generating better iterates and then accelerating the algorithms. We study two practical versions of the scheme: a (simple) inexact Kelley method, and a (sophisticated) level bundle method. We prove that these methods are convergent, and we present numerical illustrations showing they speed up resolution.

Keywords: Nonsmooth optimization, bundle methods, inexact oracle, Lagrangian relaxation, Benders decomposition

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )


Download: [PDF]

Entry Submitted: 05/23/2013
Entry Accepted: 05/23/2013
Entry Last Modified: 05/23/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