An inexact conic bundle variant suited to column generation

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 0 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 :
Rapport
[Research Report] RR-6011, INRIA. 2006
Liste complète des métadonnées

Littérature citée [44 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00109402
Contributeur : Rapport de Recherche Inria <>
Soumis le : vendredi 10 novembre 2006 - 09:59:28
Dernière modification le : mercredi 11 avril 2018 - 01:51:44
Document(s) archivé(s) le : lundi 20 septembre 2010 - 16:45:36

Fichiers

Identifiants

  • HAL Id : inria-00109402, version 2

Collections

Citation

Krzysztof Kiwiel, Claude Lemarechal. An inexact conic bundle variant suited to column generation. [Research Report] RR-6011, INRIA. 2006. 〈inria-00109402v2〉

Partager

Métriques

Consultations de la notice

226

Téléchargements de fichiers

259