|
Using Nesterov's Excessive Gap Method as Basic Procedure in Chubanov's Method for Solving a Homogeneous Feasibility Problem
|
Zhang Wei   , Cornelis Roos |
| Delf University of Technology , c.roos@tudelf.nl |
|
|
Abstract: (6681 Views) |
| We deal with a recently proposed method of Chubanov [1], for solving linear homogeneous systems with positive variables. We use Nesterov's excessive gap method in the basic procedure. As a result, the iteration bound for the basic procedure is reduced by the factor $nsqrt{n}$. The price for this improvement is that the iterations are more costly, namely $O(n^2 )$ instead of $O(n)$. The overall gain in the complexity hence becomes a factor of $sqrt{n}$. |
|
| Keywords: Linear homogeneous systems, Algorithm, Polynomial-time. |
|
|
Full-Text [PDF 289 kb]
(12307 Downloads)
|
Type of Study: Original |
Subject:
Continuous Optimization
Received: 2019/12/5 | Accepted: 2019/12/5 | Published: 2019/12/5
|
|
|
|
|
|
