An Analytic Center Based Column Generation Algorithm
For Convex Quadratic Feasibility Problems
Z.-Q. Luo and J. Sun
ABSTRACT: We consider the analytic center based column generation
algorithm for the problem of finding a feasible point in a set defined by
a finite number of convex quadratic inequalities. At each iteration, the
algorithm computes an approximate analytic center of the set defined by
the intersection of quadratic inequalities generated in the previous
iterations. If this approximate analytic center is a solution, then the
algorithm terminates; otherwise a quadratic inequality violated at the
current center is selected and a new quadratic cut (defined by a convex
quadratic inequality) is placed near the approximate center. As the
number of cuts increases, the set defined by their intersection shrinks
and the algorithm eventually finds a solution of the problem. Previously,
similar analytic center based column generation algorithms were studied
first for the linear feasibility problem and later for the general convex
feasibility problem. Our method differs from these early methods in that
we use ``quadratic cuts" in the computation instead of linear cuts.
Moreover, 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 quadratic inequalities in the problem
and $\varepsilon$ is the radius of the largest ball contained in the
feasible set. In contrast, the early column generation methods using
linear cuts can only solve the convex quadratic feasibility problem
in pseudo-polynomial time.