Using Nesterov's Excessive Gap Method as Basic Procedure in Chubanov's Method for Solving a Homogeneous Feasibility Problem

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 𝑛√𝑛. The price for this improvement is that the iterations are more costly, namely 𝑂(𝑛2) instead of 𝑂(𝑛). The overall gain in the complexity hence becomes a factor of √𝑛.