Groupe d’études et de recherche en analyse des décisions


Decomposition and Non-differentiable Optimization with the Projective Algorithm

, et

This paper deals with an application of the projective algorithm to the solution of a generic nondifferentiable minimization problem. This problem is closely related to the Dantzig-Wolfe decomposition technique used in large scale convex programming. The method is based on a column generation technique defining a sequence of primal linear programming maximization problems. Associated with each such problem one defines a weighted Karmarkar function which is minimized using a variant of the projective algorithm. When a point close to the potential minimum is reached, it corresponds to it, in the dual space, a point close to the analytic center of a polytope containing the solution set of the nondifferentiable optimization problem. An admissible cut of the polytope, corresponding to a new supporting hyperplane of the epigraph of the function to minimize, is then generated at this analytic center. In the primal space it generates a new column for the associated linear programming problem. The algorithm is applied to the solution of a set of convex programming problems. It shows good performance.

, 26 pages