首页 | 本学科首页   官方微博 | 高级检索  
     检索      


A Polynomial Cutting Surfaces Algorithm for the Convex Feasibility Problem Defined by Self-Concordant Inequalities
Authors:Zhi-Quan Luo  Jie Sun
Institution:(1) Communication Research Laboratory, Department of Electrical and Computer Engineering, McMaster University, Hamilton, Ontario, L8S 4L7, Canada;(2) Department of Decision Sciences, National University of Singapore, Singapore, 119260
Abstract:Consider a nonempty convex set in Ropfm 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 ldquoconvex cutsrdquo 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/epsi) on the total number of cuts to be used, where N is the number of convex inequalities in the original problem and epsi is the maximum common slack of the original inequality system.
Keywords:analytic center  column generation  convex feasibility problem  potential reduction
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号