##
An Easy Way to Teach Interior Point Methods

###
T. Terlaky

In this paper the duality theory of Linear Optimization (LO) is built
up based on ideas emerged from interior point methods. All we need is
elementary calculus. We will embed the LO problem and its dual in a
self--dual skew--symmetric problem. Most duality results, except the
existence of a strictly complementary solution, are trivial for this
embedding problem. The existence of the central path and its
convergence to the analytic center of the optimal face will be
proved. The proof is based on an elementary, careful analysis of a
Newton step.
We show also that if an almost optimal solution on the central path is
known, then a simple strongly polynomial rounding procedure provides a
strictly complementary optimal solution.
The all-one vector is feasible for the embedding problem and it is an
interior point on the central path. This way an elegant solution to
the initialization of IPMs is obtained as well. This approach allows
to apply any interior point method to the embedding problem while
complexity results obtained for feasible interior point methods are
preserved.
Report 98-24,

Faculty of Information Technology and Systems

Subfaculty of Technical Mathematics and Informatics,

Department of Statistics, Stochastic and Operations Research

Delft University of Technology,

P.O. Box 5031, 2600 GA Delft, The Netherlands.

Contact: terlaky@ssor.twi.tudelft.nl