Bundle Methods for Convex Minimization with Partially Inexact Oracles

Krzysztof Kiwiel (kiwielibspan.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