Please use this identifier to cite or link to this item:
Title: An analytic center based column generation algorithm for convex quadratic feasibility problems
Authors: Luo, Z.-Q.
Sun, J. 
Keywords: Analytic center
Column generation
Convex quadratic feasibility problem
Potential reduction
Issue Date: 1998
Citation: Luo, Z.-Q.,Sun, J. (1998). An analytic center based column generation algorithm for convex quadratic feasibility problems. SIAM Journal on Optimization 9 (1) : 217-235. ScholarBank@NUS Repository.
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.
Source Title: SIAM Journal on Optimization
ISSN: 10526234
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

checked on Dec 1, 2020

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.