First we review the basic concepts of self-regular proximity based Interior Point Method that allowed a complexity improvement of large-update, large-scale interior point methods. Some intriguing properties of a specific self-regular proximity function are discussed and we will show that the neighborhood used in our predictor-corrector algorithm contains the infinity norm neighborhood that is used in all practical implementations of IPMs.
Then a new adaptive self-regular predictor-corrector algorithm is presented where the corrector step is defined by our self-regular proximity and the predictor step is either a self-regular or an affine-scaling step. Polynomial worst case complexity [O(sqrt(n) log(n) L) in the best case] and asymptotic quadratic convergence rate is established.
