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

Further Complexity Analysis of a Primal-Dual Column Generation Algorithm for Convex or Quasiconvex Feasibility Problems

Jean-Louis Goffin, Zhi-Quan Luo et Yinyu Ye

We further analyze the convergence and the complexity of a primal-dual column generation algorithm for solving general convex or quasiconvex feasibility problems defined by a separation oracle. The oracle is called at an approximate analytic center of the set given by the intersection of the linear inequalities which are the previous answers of the oracle. We show that the algorithm converges in finite time and is in fact a fully polynomial approximation algorithm, provided that the feasible region has an nonempty interior.

, 20 pages