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.
Entry Submitted: 03/18/2009
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|