Optimization Online


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

Wei Zhang (lindelfeel***at***gmail.com)
Kees Roos (c.roos***at***tudelft.nl)

Abstract: We introduce a new variant of Chubanov's method for solving linear homogeneous systems with positive variables. In the \BP\ we use a recently introduced cut in combination with Nemirovski's Mirror-Prox method. We show that the cut requires at most $O(n^3)$ time, just as Chabonov's cut. In an earlier paper it was shown that the new cuts are at least as sharp as those of Chubanov. Our \MMA\ is in essence the same as Chubanov's \MA, except that it uses the new \BP\ as a subroutine. The new method has $O(n^{4.5}L)$ time complexity. Some computational results are presented in comparison with Gurobi.

Keywords: linear homogeneous systems, algorithm, polynomial-time

Category 1: Applications -- OR and Management Sciences

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: Nat. Univ. Singapore/ TU Delft June 2020

Download: [PDF]

Entry Submitted: 04/03/2018
Entry Accepted: 04/03/2018
Entry Last Modified: 06/24/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society