##
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.

Contact: pengj@cas.mcmaster.ca