A full-Newton step infeasible interior-point algorithm for linear programming based on a kernel function

Zhongyi Liu (zhyihhu.edu.cn)

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). We introduce a kernel function in the algorithm. For $p\in[0,1)$, the polynomial complexity can be proved and the result coincides with the best result for infeasible interior-point methods, that is, $O(n\log n/\varepsilon)$.

Keywords: linear programming, infeasible interior-point method, full-Newton step, polynomial complexity, kernel function

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation:

Download:

Entry Submitted: 11/10/2008
Entry Accepted: 11/10/2008
Entry Last Modified: 08/11/2009

Modify/Update this entry