An inexact bundle variant suited to column generation

• 成果类型: Article
• 署名作者: Kiwiel, K. C.; Lemarechal, C.
• 署名单位: Inria
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-007-0187-4
• 发表日期: 2009
• 页码: 177-206
• 关键词: algorithm; optimization; approximations; DECOMPOSITION; point

摘要

We give a bundle method for constrained convex optimization. Instead of using penalty functions, it shifts iterates towards feasibility, by way of a Slater point, assumed to be known. Besides, the method accepts an oracle delivering function and subgradient values with unknown accuracy. Our approach is motivated by a number of applications in column generation, in which constraints are positively homogeneous-so that zero is a natural Slater point-and an exact oracle may be time consuming. Finally, our convergence analysis employs arguments which have been little used so far in the bundle community. The method is illustrated on a number of cutting-stock problems.