Column Generation Algorithms for Nonlinear Optimization, I: Convergence Analysis

Abstract

Column generation is an increasingly popular basic tool for the solution of large-scale mathematical programming problems. As problems being solved grow bigger, column generation may however become less efficient in its present form, where columns typically are not optimizing, and finding an optimal solution instead entails finding an optimal convex combination of a huge number of them. We present a class of column generation algorithms in which the columns defining the restricted master problem may be chosen to be optimizing in the limit, thereby reducing the total number of columns needed. This first article is devoted to the convergence properties of the algorithm class, and includes global (asymptotic) convergence results for differentiable minimization, finite convergence results with respect to the optimal face and the optimal solution, and extensions of these results to variational inequality problems. An illustration of its possibilities is made on a nonlinear network flow model, contrasting its convergence characteristics to that of the restricted simplicial decomposition (RSD) algorithm.

Keywords:

• Column Generation
• Simplicial Decomposition
• Inner Approximation
• Simplices
• Column Dropping
• Optimal Face
• Non-degeneracy
• Pseudo-convex Minimization
• Weak Sharpness
• Finite Convergence
• Pseudo-monotone