A Proximal Extension of the Column Generation Method to Nonconvex Conic Optimization Providing Bounds for the Duality Gap

Abstract

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.