An analytic center based column generation algorithm for convex quadratic feasibility problems

摘要

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 to 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 1/epsilon) on the total number of cuts to be used, where n is the number of convex quadratic polynomial inequalities in the problem and epsilon 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 pseudopolynomial time. [References: 17]