DOE OSTI · 21241844
A Full-Newton Step Infeasible Interior-Point Algorithm for Linear Programming Based on a Kernel Function
Abstract
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 p element of [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})
Explore related subjects
Keep this discovery
Explore connections, maps & timelines
Sun, Wenyu. 2009-10-15. A Full-Newton Step Infeasible Interior-Point Algorithm for Linear Programming Based on a Kernel Function. https://doi.org/10.1007/s00245-009-9069-x
Cite the original work for its findings. Save a collection to share your selection of sources.