An easy way to teach interior-point methods

In this paper the duality theory of Linear Optimization (LO) is built up based on ideas emerged from interior-point methods (IPMs). 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 centre 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 an exact 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 IPM to the embedding problem while complexity results obtained for feasible IPMs are preserved.