An entire space polynomial-time algorithm for linear programming

We propose an entire space polynomial-time algorithm for linear programming. First, we give a class of penalty functions on entire space for linear programming by which the dual of a linear program of standard form can be converted into an unconstrained optimization problem. The relevant properties on the unconstrained optimization problem such as the duality, the boundedness of the solution and the path-following lemma, etc, are proved. Second, a self-concordant function on entire space which can be used as penalty for linear programming is constructed. For this specific function, more results are obtained. In particular, we show that, by taking a parameter large enough, the optimal solution for the unconstrained optimization problem is located in the increasing interval of the self-concordant function, which ensures the feasibility of solutions. Then by means of the self-concordant penalty function on entire space, a path-following algorithm on entire space for linear programming is presented. The number of Newton steps of the algorithm is no more than <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$$O(nL\log (nL/ {\varepsilon }))$$</EquationSource> </InlineEquation>, and moreover, in short step, it is no more than <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$$O(\sqrt{n}\log (nL/{\varepsilon }))$$</EquationSource> </InlineEquation>. Copyright Springer Science+Business Media New York 2014