A New Iteration-Complexity Bound for the MTY Predictor-Corrector Algorithm (Q5317499)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2206178
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A New Iteration-Complexity Bound for the MTY Predictor-Corrector Algorithm |
scientific article; zbMATH DE number 2206178 |
Statements
A New Iteration-Complexity Bound for the MTY Predictor-Corrector Algorithm (English)
0 references
16 September 2005
0 references
interior-point algorithms
0 references
primal-dual algorithms
0 references
path-following
0 references
central path
0 references
layered least squares steps
0 references
condition number
0 references
polynomial complexity
0 references
crossover events
0 references
linear programming
0 references
scale-invariance
0 references
predictor-corrector
0 references
affine scaling
0 references
convergence
0 references
0.7686958
0 references
0.76146245
0 references
0.75524765
0 references
0.75444937
0 references
0.75241464
0 references
0.7417631
0 references
0.73952967
0 references
0.73529214
0 references
0.7342824
0 references
This work is strongly motivated by the work of \textit{S. Vavasis} and \textit{Y. Ye} [Math. Program. 74, No. 1(A), 79--120 (1996; Zbl 0868.90081)]. The authors developed a new iteration-complexity bound for the Mizuno-Todd-Ye predictor-corrector (MTY P-C) primal-dual interior-point algorithm for linear programming using the notation of crossover events due to Vavasis and Ye [loc. cit.]. In contrast to the classical iteration-complexity bound, which is proportional to \(\log(\mu_0 / \eta)\), the new bound depends linearly on \(\log \left (\log(\mu_0 / \eta)\right)\). In contrast to the iteration-complexity bound developed in the work of Vavasis and Ye [loc. cit.], the presented bound is scaling-invariant and has an extra but relatively small term \(\;itT ( \mu_0/ \eta) \), where \[ it T(t)\equiv\min\{n^2 \log (\log t),\log t\}\quad\text{for all }t>0. \] Using this bound it is proved that the sequence generated by the MTY P-C algorithm is quadratically convergent. The above iteration-complexity results for the MTY P-C algorithm were presented under the real number computational model. A few implications of these results under the Turing machine model were discussed, too.
0 references