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
      0 references
      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
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references