A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms
A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms
复制标题
DOI：
10.1007/s10107-007-0141-5
复制
发表时间：
2008-09-01
影响因子：
2.7
通讯作者：
Tsuchiya, Takashi
中科院分区：
文献类型：
--
作者：
Monteiro, Renato D. C.;Tsuchiya, Takashi
本文的主要目标是：i）与线性编程（LP）的Mizuno-Todd-ye预测器相关器（MTY P-C）算法相关联的两个迭代复杂性界限，以及； ii）研究LP中心路径的几何结构。本文考虑的MTY P-C算法结合的第一个迭代复杂性是根据中心路径的遍历部分的一定曲率函数的积分表示的。作者最近使用Vavasis和Ye引入的交叉事件概念得出的第二个迭代 - 复杂性结合，它是根据与LP的M X N约束矩阵相关的规模不变条件数来表达的。在本文中，我们通过证明第一个可以在第二个界限上进行大规模化，从而建立了这些界限之间的关系。我们还建立了有关中心路径的几何结果，该基础是根据vavasis和ye提出的主张的中心路径的曲率，鉴于其分层最小二乘路径在LP方法之后，中央路径由o（n（2））长但直连的零件组成，而其余的弯曲部分相对“短”。
The main goals of this paper are to: i) relate two iteration-complexity bounds derived for the Mizuno-Todd-Ye predictor-corrector (MTY P-C) algorithm for linear programming (LP), and; ii) study the geometrical structure of the LP central path. The first iteration-complexity bound for the MTY P-C algorithm considered in this paper is expressed in terms of the integral of a certain curvature function over the traversed portion of the central path. The second iteration-complexity bound, derived recently by the authors using the notion of crossover events introduced by Vavasis and Ye, is expressed in terms of a scale-invariant condition number associated with m x n constraint matrix of the LP. In this paper, we establish a relationship between these bounds by showing that the first one can be majorized by the second one. We also establish a geometric result about the central path which gives a rigorous justification based on the curvature of the central path of a claim made by Vavasis and Ye, in view of the behavior of their layered least squares path following LP method, that the central path consists of O(n(2)) long but straight continuous parts while the remaining curved part is relatively "short".