Self-Regular Proximities and New Search Directions for Linear and Semidefinite Optimization

J. Peng, C. Roos and T. Terlaky

In this paper, we first introduce the notion of {\em self-regular} function which is different from the well-known {\em self-concordance} of a function. Then we use such functions to define proximity measures for path-following methods for solving linear optimization (LO) problems. New search direction, based on the proximity measure for solving LO, is suggested. Using the properties of the proximity, we prove that the large-update path-following method for LO has a polynomial complexity $O\br{n^{\frac{q+1}{2q}}\log\frac{n}{\e}}$ iteration bound where $q\ge 1$ is the so-called barrier degree of the proximity. When $q$ increases, our result approaches the best known complexity $O\br{\sqrt{n}\log\frac{n}{\e}}$ iteration bound for interior point methods. Our unified analysis provides also the $O\br{\sqrt{n}\log\frac{n}{\e}}$ best known complexity of small-update IPMs. At each iteration, we need only to solve one linear system. As a byproduct of our results, we remove some limitations of the algorithms presented in one of our recent work and improve their complexity as well. Extension of these results to SDO is also discussed.

Preprint, Department of Computing and Software, McMaster University, Hamilton, Ontario, Canada, March 2000.