Complexity analysis of an interior cutting plane method for convex-feasibility problems
Complexity analysis of an interior cutting plane method for convex-feasibility problems
复制标题
DOI：
10.1137/s1052623493258635
复制
发表时间：
1996-08-01
影响因子：
3.1
通讯作者：
Ye, YY
中科院分区：
文献类型：
--
作者：
Goffin, JL;Luo, ZQ;Ye, YY
进一步分析了求解分离预言机定义的一般凸可行性问题的对偶列生成算法的收敛性和复杂性。预言被称为在一个近似的分析中心的集合给出的线性不等式的交集，这是以前的答案的预言。我们证明了该算法在有限时间内收敛，实际上是一个完全多项式近似算法，只要可行域具有非空的内部。
The further analyze the convergence and the complexity of a dual column generation algorithm for solving general convex feasibility problems defined by a separation oracle. The oracle is called at an approximate analytic center of the set given by the intersection of the linear inequalities which are the previous answers of the oracle. We shown that the algorithm converges in finite time and is in fact a fully polynomial approximation algorithm, provided that the feasible region has a nonempty interior.