caa a22 4500 475750675 CHVBK 20180406123522.0 cr unu---uuuuu 170329e20000201xx s 000 0 eng 10.1023/A:1008787027641 doi (NATIONALLICENCE)springer-10.1023/A:1008787027641 A Polynomial Cutting Surfaces Algorithm for the Convex Feasibility Problem Defined by Self-Concordant Inequalities [Elektronische Daten] [Zhi-Quan Luo, Jie Sun] Consider a nonempty convex set in ℝm 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(Nlog 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. Kluwer Academic Publishers, 2000 analytic center nationallicence column generation nationallicence convex feasibility problem nationallicence potential reduction nationallicence Luo Zhi-Quan Communication Research Laboratory, Department of Electrical and Computer Engineering, McMaster University, L8S 4L7, Hamilton, Ontario, Canada aut Sun Jie Department of Decision Sciences, National University of Singapore, 119260, Singapore aut Computational Optimization and Applications Kluwer Academic Publishers 15/2(2000-02-01), 167-191 0926-6003 15:2<167 2000 15 10589 https://doi.org/10.1023/A:1008787027641 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1023/A:1008787027641 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Luo Zhi-Quan Communication Research Laboratory, Department of Electrical and Computer Engineering, McMaster University, L8S 4L7, Hamilton, Ontario, Canada aut NATIONALLICENCE 700 1- Sun Jie Department of Decision Sciences, National University of Singapore, 119260, Singapore aut NATIONALLICENCE 773 0- Computational Optimization and Applications Kluwer Academic Publishers 15/2(2000-02-01), 167-191 0926-6003 15:2<167 2000 15 10589 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer