A strongly polynomial-time algorithm for the strict homogeneous linear-inequality feasibility problem

<Para ID="Par1">A strongly polynomial-time algorithm is proposed for the strict homogeneous linear-inequality feasibility problem in the positive orthant, that is, to obtain <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$$x\in \mathbb {R}^n$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>x</mi> <mo>∈</mo> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mi>n</mi> </msup> </mrow> </math> </EquationSource> </InlineEquation>, such that <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$$Ax > 0$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>A</mi> <mi>x</mi> <mo>></mo> <mn>0</mn> </mrow> </math> </EquationSource> </InlineEquation>, <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$$x> 0$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>x</mi> <mo>></mo> <mn>0</mn> </mrow> </math> </EquationSource> </InlineEquation>, for an <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$$m\times n$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>m</mi> <mo>×</mo> <mi>n</mi> </mrow> </math> </EquationSource> </InlineEquation> matrix <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$$A$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mi>A</mi> </math> </EquationSource> </InlineEquation>, <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$$m\ge n$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>m</mi> <mo>≥</mo> <mi>n</mi> </mrow> </math> </EquationSource> </InlineEquation>. This algorithm requires <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$$O(p)$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>p</mi> <mo stretchy="false">)</mo> </mrow> </math> </EquationSource> </InlineEquation> iterations and <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$$O(m^2(n+p))$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>m</mi> <mn>2</mn> </msup> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <mi>p</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">)</mo> </mrow> </math> </EquationSource> </InlineEquation> arithmetical operations to ensure that the distance between the solution and the iteration is <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$$10^{-p}$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <msup> <mn>10</mn> <mrow> <mo>-</mo> <mi>p</mi> </mrow> </msup> </math> </EquationSource> </InlineEquation>. No matrix inversion is needed. An extension to the non-homogeneous linear feasibility problem is presented. Copyright Springer-Verlag Berlin Heidelberg 2014