A NEW EFFICIENT LARGE-UPDATE PRIMAL-DUAL INTERIOR-POINT METHOD BASED ON A FINITE BARRIER.

We introduce a new barrier-type function which is not, a barrier function in the usual sense: it has finite value at the boundary of the feasible region. Despite this, the iteration bound of a large-update interior-point method based on this function is shown to be O(square root of n (log n) log n/epsilon), which is as good as tile currently best known bound for large update methods. The recently introduced properly of exponential convexity for the kernel function underlying the barrier function, as well as the strong convexity of the kernel function, are crucial in the analysis. [ABSTRACT FROM AUTHOR]