Optimization Online


Bundle Methods for Convex Minimization with Partially Inexact Oracles

Krzysztof Kiwiel (kiwiel***at***ibspan.waw.pl)

Abstract: Recently the proximal bundle method for minimizing a convex function has been extended to an inexact oracle that delivers function and subgradient values of unknown accuracy. We adapt this method to a partially inexact oracle that becomes exact only when an objective target level for a descent step is met. In Lagrangian relaxation, such oracles may save work by evaluating the dual function approximately on most iterations, without compromising the strong convergence properties of exact bundle methods. We also show that the recent method of Gaudioso et al.\ for finite min--max problems fits our partially inexact framework, we correct and strengthen its convergence results and give useful modifications. Numerical illustrations on standard instances of the generalized assignment problem (GAP) are included.

Keywords: nondifferentiable optimization, convex programming, proximal bundle methods, approximate subgradients, finite min-max

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Citation: Technical report, Systems Research Institute, Polish Academy of Sciences, Newelska 6, 01-447 Warsaw, Poland, March 2009. Second revision, April 2010.

Download: [PDF]

Entry Submitted: 03/18/2009
Entry Accepted: 03/18/2009
Entry Last Modified: 12/15/2010

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 Programming Society