A generalized homogeneous and self-dual algorithm for linear programming

A generalized homogeneous and self-dual infeasible-interior-point algorithm for linear programming (LP) is proposed in this paper. The algorithm does not need to start from a big M initial point, while achieving -iteration complexity by following a certain central path on a central surface in a neighborhood , where can be any number between 0 and 1, is the number of variables and L is the data length of the LP problem. In particular, an algorithm is developed, where the searching direction is obtained by solving a Newton equation system without infeasible residual terms on its right-hand side.