An asymptotical O(root nL)-iteration path-following linear programming algorithm that uses wide neighborhoods

Path-following linear programming (LP) algorithms generate a sequence:of points within certain neighborhoods of a central path C which prevent iterates From prematurely getting too close to the boundary of the feasible region; Depending on the norm used, these neighborhoods include N-2(beta), N-infinity(beta), and N-infinity(-)(beta), where beta is an element of (0,1) and C subset of N-2(beta) subset of N-infinity(-)(beta) for each beta is an element of (0,1). A paradox is that among all existing (infeasible or feasible) path-following algorithms, the theoretical iteration complexity O(root nL), of small-neighborhood (N-2) algorithms is significantly better than the complexity, O(nL), of wide-neighborhood (N-infinity(-)) algorithms. In practice, wide-neighborhood algorithms outperform small-neighborhood ones by a big margin. Here, n is the number of LP Variables and L is the LP data length. In this paper, we present an O(n n+1/2n L)-iteration (infeasible) primal-dual high-order algorithm that uses wide neighborhoods. Note that this iteration bound is asymptotically O(root nL), i.e., the best bound for small-neighborhood algorithms as n increases.