A new variant of the primal affine scaling algorithm for linear programs (Q3979522)

The primal affine scaling algorithm was introduced by \textit{I. I. Dikin} [Sov. Math., Dokl. 8, 674--675 (1967); translation from Dokl. Akad. Nauk SSSR 174, 747--748 (1967; Zbl 0189.19504)]. After \textit{N. Karmarkar} had proposed his algorithm [Combinatorica 4, 373--395 (1984; Zbl 0557.90065)], it was rediscovered as a variant of Karmarkar's algorithm. Here the authors introduce in turn a variant of the affine scaling algorithm. The novelty consists in computing, at each step of the algorithm, the required direction vector minimizing a linear functional over a larger nonlinear domain, as compared to the original algorithm. Numerous restrictive hypotheses are required. The feasible region must be bounded and have non-void interior, both the primal and the dual problem must be non-degenerate, and, finally, the number of variables must be greater than the number of equality constraints plus one. A good deal of mathematical effort leads to the conclusion that the algorithm converges as the number of steps goes to infinity and that, to the expense of a greater numerical effort at each step, there is a slight improvement of the rate of asymptotic convergence, with some possible net gain in efficiency. Numerical experiments confirm this, showing a reduction in effort of 11\% in the average over the original algorithm. A bottom line may be that the approach is close to the asymptote of its potential, since the deployment of a noteworthy mathematical skill and the exploitation of a remarkably restrictive set of hypotheses produces a rather marginal improvement of efficiency.