Cutting Surfaces And Analytic Center:
A Polynomial Algorithm For The Convex Feasibility
Problem Defined By Self-Concordant Inequalities
Z.-Q. Luo and J. Sun
Consider a nonempty convex set in $R^m$ which is defined by a finite
number of convex differentiable inequalities and which admits a
self-concordant logarithmic barrier. We study the analytic center based
column generation algorithm for the problem of finding a feasible point
in this set. At each iteration, the algorithm computes an approximate
analytic center of the set defined by the inequalities generated in the
previous iterations. If this approximate analytic center is a solution,
then the algorithm terminates; otherwise either 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 generated inequalities
shrinks and the algorithm eventually finds a solution of the problem. The
algorithm can be thought of as an extension of the classical cutting
plane method. The difference is that we use analytic centers and ``convex
cuts" instead of linear cuts. Our method has a polynomial worst case
complexity of $O(n\ln \frac{1}{\varepsilon})$ on the total number of cuts
to be used, where $n$ is the number of convex inequalities in the
original problem and $\varepsilon$ is the maximum common slack of the
original inequality system. In contrast, the early column generation
methods using linear cuts can only solve the convex feasibility problem
in pseudo-polynomial time.
Contact: [email protected]