Back to Search
Start Over
A NEW ITERATION-COMPLEXITY BOUND FOR THE MTY PREDICTOR-CORRECTOR ALGORITHM.
- Source :
-
SIAM Journal on Optimization . 2004, Vol. 15 Issue 2, p319-347. 29p. - Publication Year :
- 2004
-
Abstract
- 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 {cTχ: Aχ = b, &chi ≥ 0 } with decision variable ..., we show that the MTY P-C algorithm, started from a well-centered interior-feasible solution with duality gap nμ0 finds an interior-feasible solution with duality gap less than nn in O (T(μ0/η)+n3.5 log (Χ*A)) iterations, where T(t ) =min {n² log (log t), log t} for all t>0 and Χ*A is a scaling invariant condition number associated with the matrix A. More specifically,Χ*A is the infimum of all the conditions numbers XAD, where D varies over the set of positive diagonal matrices. Under the setting of the Turing machine model, our analysis yields an O (n3.5 LA + min {n² 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 10526234
- Volume :
- 15
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Optimization
- Publication Type :
- Academic Journal
- Accession number :
- 16197508
- Full Text :
- https://doi.org/10.1137/S1052623402416803