Complexity analysis of an interior cutting plane method for convex feasibility problems. (English) Zbl 0856.90088

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

SIAM J. Optim. 6, No. 3, 638-652 (1996).

Summary: We further analyze the convergence and the complexity of a dual column generation algorithm for solving general convex 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 a nonempty interior.

MSC:

90C25	Convex programming
90C60	Abstract computational complexity for mathematical programming problems
90C26	Nonconvex programming, global optimization

Keywords:

potential reduction; cutting planes; convergence; complexity; dual column generation algorithm; convex feasibility problems; separation oracle; fully polynomial approximation algorithm