An inexact bundle variant suited to column generation

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...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2009-04, Vol.118 (1), p.177-206
Main Authors: Kiwiel, K. C., Lemaréchal, C.
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Calculus of Variations and Optimal Control
Optimization
Combinatorics
Computer programming
Convex analysis
Cutting stock problem
Euclidean space
Exact sciences and technology
Flows in networks. Combinatorial problems
Full Length Paper
Mathematical and Computational Physics
Mathematical functions
Mathematical Methods in Physics
Mathematical programming
Mathematics
Mathematics and Statistics
Mathematics of Computing
Numerical Analysis
Operational research and scientific management
Operational research. Management science
Optimization
Optimization and Control
Studies
Theoretical
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0025-5610
1436-4646
DOI:10.1007/s10107-007-0187-4