An inexact bundle variant suited to column generation

Krzysztof Kiwiel Claude Lemaréchal 1
1 BIPOP - Modelling, Simulation, Control and Optimization of Non-Smooth Dynamical Systems
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, INPG - Institut National Polytechnique de Grenoble
Abstract : 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.
Type de document :
Article dans une revue
Mathematical Programming, Springer Verlag, 2009, 118 (1), pp.177-206. 〈10.1007/s10107-007-0187-4〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00821373
Contributeur : Brigitte Bidégaray-Fesquet <>
Soumis le : jeudi 9 mai 2013 - 14:06:28
Dernière modification le : mercredi 11 avril 2018 - 01:58:01

Lien texte intégral

Identifiants

Collections

Citation

Krzysztof Kiwiel, Claude Lemaréchal. An inexact bundle variant suited to column generation. Mathematical Programming, Springer Verlag, 2009, 118 (1), pp.177-206. 〈10.1007/s10107-007-0187-4〉. 〈hal-00821373〉

Partager

Métriques

Consultations de la notice

189