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: [email protected]

[DVI] [PS] [IP PAGE] [SEARCH AGAIN]