Using Nemirovski's Mirror-Prox method as basic procedure in Chubanov's method for solving homogeneous feasibility problems

Zhang Wei, Kees Roos*

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

49 Downloads (Pure)

Abstract

We introduce a new variant of Chubanov's method for solving linear homogeneous systems with positive variables. In the Basic Procedure we use a recently introduced cut in combination with Nemirovski's Mirror-Prox method. We show that the cut requires at most (Formula presented.) time, just as Chubanov's cut. In an earlier paper it was shown that the new cuts are at least as sharp as those of Chubanov. Our Modified Main Algorithm is in essence the same as Chubanov's Main Algorithm, except that it uses the new Basic Procedure as a subroutine. The new method has (Formula presented.) time complexity, where (Formula presented.) is a suitably defined condition number. As we show, a simplified version of the new Basic Procedure competes well with the Smooth Perceptron Scheme of Peña and Soheili and, when combined with Rescaling, also with two commercial codes for linear optimization.

Original languageEnglish
Pages (from-to)1447-1470
Number of pages24
JournalOptimization Methods and Software
Volume37
Issue number4
DOIs
Publication statusPublished - 2022

Keywords

  • Chubanov's method
  • homogeneous
  • Linear optimization
  • Mirror-Prox method

Fingerprint

Dive into the research topics of 'Using Nemirovski's Mirror-Prox method as basic procedure in Chubanov's method for solving homogeneous feasibility problems'. Together they form a unique fingerprint.

Cite this