Fast finite methods for a system of linear inequalities (Q1819897)

The paper deals with the solution of a system of m linear inequalities in n unknowns: \[ Ax\geq b. \] After a brief survey on the best known algorithms (simplex, Karmarkar) the author reformulates the problem to minimize the square of infeasibilities. To solve this problem a family of Newton-type algorithms is defined and two special cases of the family are discussed in detail. Some heuristics are also presented that can successfully be implemented in the algorithms. Proof of convergence for the simplest case is also given. The probabilistic estimate for the speed of convergence is \(O((m/n)\log^ 3n)\). The analysis is carefully described and some limited numerical experiences are also presented.