## Generalization of primal-dual interior-point methods to convex
optimization problems in conic form

###
Levent Tuncel

We generalize primal-dual interior-point methods for linear
programming problems to the convex optimization problems in conic
form. Previously, the most comprehensive theory of symmetric
primal-dual interior-point algorithms was given by Nesterov and Todd
\cite{NT97, NT98} for the feasible regions expressed as the
intersection of a symmetric cone with an affine subspace. In our
setting, we allow an arbitrary convex cone in place of the symmetric
cone. Even though some of the impressive properties attained by
Nesterov-Todd algorithms is impossible in this general setting of
convex optimization problems, we show that essentially all primal-dual
interior-point-algorithms for LP can be extended easily to the general
setting. We provide three frameworks for primal-dual algorithms, each
framework corresponding to a different level of sophistication in the
algorithms. As the level of sophistication increases, we demand
better formulations of the feasible solution sets, but our algorithms,
in return, attain provably better theoretical properties. We also
make a very strong connection to Quasi-Newton Methods by expressing
the square of the symmetric primal-dual linear transformation
(so-called scaling) as a BFGS update in the case of the least
sophisticated framework.

Research Report CORR 99-35, Department of Combinatorics
and Optimization, Faculty of Mathematics, University
of Waterloo, Waterloo, Ontario N2L 3G1, Canada,
August 25, 1999.

Contact: ltuncel@math.uwaterloo.ca