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


Using the Primal Dual Infeasible Newton Method in the Analytic Center Method for Problems Defined by Deep Cutting Planes


The convergence and the complexity of a primal-dual column generation and cutting plane algorithm from approximate analytic centers for solving convex feasibility problems defined by a "deep cut" separation oracle is studied. The primal-dual infeasible Newton method is used to generate a primal-dual updating direction. In the case where the cut goes through the analytic center the number of recentering steps is at most three, while it is O(1) for cuts as deep as half way to the deep cut where the deepest cut is a cut that is tangent to the primal-dual variant of Dikin's ellipsoid.

, 31 pages

Ce cahier a été révisé en février 1997