Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem (Q705124)

A new combinatorial algorithm is described in order to solve the homogenized linear feasibility problem of finding a point \(x\) on the unit sphere, satisfying \(n\) linear inequalities \(a^T_i x\geq0\). The use of the centers of the inspheres of spherical simplices, whose facets are determined by a subset of the constraints, leads to a combination of the algorithm of Agmon-Motzkin-Schoenberg with the algorithm of Khachiyan. A rescaling is periodically used to speed up the convergence, leading to the polynomiality of this algorithm. The geometry of the algorithm is thoroughly studied, resulting in an extension of the possibilities of application to more general convex feasibility problem. The investigation of practical ways to perform necessary calculations shows no particular difficulties and that the complexity of a single step is on average comparable with the simplex algorithm. Numerical examples are presented to emphasize the practical interest of this algorithm.