A polynomial cutting surfaces algorithm for the convex feasibility problemdefined by self-concordant inequalities

Consider a nonempty convex set in R-m which is defined by a finite number o f smooth convex inequalities and which admits a self-concordant logarithmic barrier. We study the analytic center based column generation algorithm fo r the problem of finding a feasible point in this set. At each iteration th e algorithm computes an approximate analytic center of the set defined by t he inequalities generated in the previous iterations. If this approximate a nalytic center is a solution, then the algorithm terminates; otherwise eith er an existing inequality is shifted or a new inequality is added into the system. As the number of iterations increases, the set defined by the gener ated inequalities shrinks and the algorithm eventually finds a solution of the problem. The algorithm can be thought of as an extension of the classic al cutting plane method. The difference is that we use analytic centers and "convex cuts" instead of arbitrary infeasible points and linear cuts. In c ontrast to the cutting plane method, the algorithm has a polynomial worst c ase complexity of O(N log 1/epsilon) on the total number of cuts to be used , where N is the number of convex inequalities in the original problem and epsilon is the maximum common slack of the original inequality system.