A new iteration-complexity bound for the MTY predictor-corrector algorithm
A new iteration-complexity bound for the MTY predictor-corrector algorithm
复制标题
DOI：
10.1137/s1052623402416803
复制
发表时间：
2005-01-01
影响因子：
3.1
通讯作者：
Tsuchiya, T
中科院分区：
文献类型：
--
作者：
Monteiro, RDC;Tsuchiya, T
本文给出了线性规划Mizuno-Todd-Ye预估-校正（MTY P-C）原对偶邻近点算法的一个新的迭代复杂性界。本文的分析是基于Vavasis和Ye提出的交叉事件的重要概念。对于标准形式线性规划min{c（T）x：Ax = B，x >= 0}，其中决策变量x是R（n）中的一个元素，我们证明了MTY P-C算法，从一个具有对偶间隙n μ（0）的良好中心的相邻可行解出发，在O（T（mu（0）/eta）+ n）的时间内找到对偶间隔小于n eta的邻域可行解（3.5）log（（chi）over bar（A）*））迭代，其中对于所有t > 0，T（t）= min{n（2）log（log t），log t}，并且（chi）over bar（A）* 是与矩阵A相关联的缩放不变条件数。更具体地说，（chi）over bar（A）* 是所有条件数（chi）over bar（AD）的下确界，其中D在正对角矩阵的集合上变化。在图灵机模型下，分析得出MTY P-C算法寻找原始-对偶最优解的迭代复杂度为O（n（3.5）L（A）+ min{n（2）log L，L}），其中LA和L分别为矩阵A和数据（A，B，c）的输入大小.这与MTY P-C算法的经典迭代复杂度界限形成了很好的对比，MTY P-C算法的经典迭代复杂度界限线性地依赖于L而不是log L。
In this paper we present a new iteration-complexity bound for the Mizuno-Todd-Ye predictor-corrector (MTY P-C) primal-dual interior-point algorithm for linear programming. The analysis of the paper is based on the important notion of crossover events introduced by Vavasis and Ye. For a standard form linear program min{c(T)x : Ax = b, x >= 0} with decision variable x is an element of R(n), we show that the MTY P-C algorithm, started from a well-centered interior-feasible solution with duality gap n mu(0), finds an interior-feasible solution with duality gap less than n eta in O(T(mu(0)/eta) + n(3.5) log((chi) over bar (A)*)) iterations, where T(t) = min{n(2) log(log t), log t} for all t > 0 and (chi) over bar (A)* is a scaling invariant condition number associated with the matrix A. More specifically, (chi) over bar (A)* is the infimum of all the conditions numbers (chi) over bar (AD), where D varies over the set of positive diagonal matrices. Under the setting of the Turing machine model, our analysis yields an O(n(3.5) L(A) + min{n(2) log L, L}) iteration-complexity bound for the MTY P-C algorithm to find a primal-dual optimal solution, where LA and L are the input sizes of the matrix A and the data (A, b, c), respectively. This contrasts well with the classical iteration- complexity bound for the MTY P-C algorithm, which depends linearly on L instead of log L.