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

• 成果类型: Article
• 署名作者: Monteiro, Renato D. C.; Tsuchiya, Takashi
• 署名单位: University System of Georgia; Georgia Institute of Technology; Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-007-0141-5
• 发表日期: 2008
• 页码: 105-149
• 关键词: interior-point algorithm; GLOBAL CONVERGENCE; linear-programs; variant

摘要

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.