Please use this identifier to cite or link to this item: https://doi.org/10.1023/A:1008787027641
Title: Polynomial cutting surfaces algorithm for the convex feasibility problem defined by self-concordant inequalities
Authors: Luo, Z.-Q.
Sun, J. 
Issue Date: 2000
Citation: Luo, Z.-Q., Sun, J. (2000). Polynomial cutting surfaces algorithm for the convex feasibility problem defined by self-concordant inequalities. Computational Optimization and Applications 15 (2) : 167-191. ScholarBank@NUS Repository. https://doi.org/10.1023/A:1008787027641
Abstract: Consider a nonempty convex set in Rm which is defined by a finite number of smooth convex 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 arbitrary infeasible points and linear cuts. In contrast to the cutting plane method, the algorithm has a polynomial worst case complexity of O (N log 1/ε) on the total number of cuts to be used, where N is the number of convex inequalities in the original problem and ε is the maximum common slack of the original inequality system.
Source Title: Computational Optimization and Applications
URI: http://scholarbank.nus.edu.sg/handle/10635/44891
ISSN: 09266003
DOI: 10.1023/A:1008787027641
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

10
checked on Jul 22, 2018

WEB OF SCIENCETM
Citations

11
checked on Jun 19, 2018

Page view(s)

59
checked on Jul 13, 2018

Google ScholarTM

Check

Altmetric


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