316 CHAPTER 6 B) comes to our rescue. It gives a half-space containing G with the center on its boundary (to this end we apply the separation theorem to the convex set G and the point c). Intersecting this half-space with the last ellipsoid gives a half-ellipsoid containing all solutions of our problem. Therefore, we can continue the algorithm in the usual way, embedding this half-ellipsoid into the ellipsoid of smallest volume. Conclusion to section 6.8. The ellipsoid method is an adapta- tion of the center of gravity method. It makes use of the fact that the class of ellipsoids has so much flexibility that each half-ellipsoid is contained in an ellipsoid of smaller volume than the original ellip- soid. The ellipsoid algorithm is reliable and efficient, and it is easy to implement. 6.9 INTERIOR POINT METHODS Plan. In this final section we give an introduction to the other type of algorithms to solve convex optimization problems: interior point methods. We give an elementary presentation of the simplest case, that of primal-dual short-step algorithms for LP problems. A special feature of this presentation in compared to standard treat- ments is that it is coordinate-free. Two presentations: calculation of limit and barriers. In 1984, when Karmarkar published his epoch-making paper, interior point methods for solving linear programming problems seemed rather mysterious. By now, the basic idea can be explained in a relatively straightforward way: as a method to calculate a limit numerically, as we are going to see. In section 7.3 we will give a different presen- tation of interior point methods, using barriers for arbitrary convex problems. Here, we will not include an analysis of the complexity of this method. A discussion of the complexity will be considered in sec- tion 7.3. The approach to interior point methods given here--called the v-space approach--can be extended to semidefinite programming problems (cf. [73]). 6.9.1 Linear complementarity problems Plan and motivation. The best versions of the interior point method solve the primal and dual problems at the same time. This is