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

Zhi Quan Luo, Jie Sun

Research output: Contribution to journalArticlepeer-review

20 Scopus citations

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 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/ε) on the total number of cuts to be used, where n is the number of convex quadratic polynomial inequalities in the problem and ε 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.

Original languageEnglish (US)
Pages (from-to)217-235
Number of pages19
JournalSIAM Journal on Optimization
Volume9
Issue number1
DOIs
StatePublished - Jan 1 1998

Keywords

  • Analytic center
  • Column generation
  • Convex quadratic feasibility problem
  • Potential reduction

Fingerprint

Dive into the research topics of 'An analytic center based column generation algorithm for convex quadratic feasibility problems'. Together they form a unique fingerprint.

Cite this