Applied Mathematics and Optimization, Vol.60, No.2, 237-251, 2009
A Full-Newton Step Infeasible Interior-Point Algorithm for Linear Programming Based on a Kernel Function
This paper proposes an infeasible interior-point algorithm with full-Newton step for linear programming, which is an extension of the work of Roos (SIAM J. Optim. 16(4):1110-1136, 2006). The main iteration of the algorithm consists of a feasibility step and several centrality steps. We introduce a kernel function in the algorithm to induce the feasibility step. For parameter pa[0,1], the polynomial complexity can be proved and the result coincides with the best result for infeasible interior-point methods, that is, O(nlog n/epsilon).
Keywords:Linear programming;Infeasible interior-point method;Full-Newton step;Polynomial complexity;Kernel function