Journal of Convex Analysis 17 (2010), No. 3&4, 721--736
Copyright Heldermann Verlag 2010
A Proximal Extension of the Column Generation Method to Nonconvex Conic Optimization Providing Bounds for the Duality Gap
Institut Camille Jordan, Université Claude Bernard, 43 Boulevard du 11 Novembre 1918, 69622 Villeurbanne - Lyon, France
We consider nonconvex conic optimization that covers Standard Nonlinear Programming, Semidefinite Programming, Second Order Cone Programming. To the dual Lagrangian problem, we associate a relaxed primal convex problem, and give bounds for the duality gap. Then we propose a proximal extension of the column generation method of Dantzig-Wolfe algorithm (PECGM) which provides these bounds if we suppose in addition Slater's condition. Finally new applications are given in order to make implementable the step of PECGM for which a nonconvex program is supposed to be solved numerically.
Keywords: Standard nonlinear programming, semidefinite programming, second order cone programming, duality gap, generation column algorithm, proximal method.
[ Fulltext-pdf (160 KB)] for subscribers only.