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.
Citation
Technical report, Systems Research Institute, Polish Academy of Sciences, Newelska 6, 01-447 Warsaw, Poland, March 2009. Second revision, April 2010.