The Theory of Exterior and Interior Point Algorithms, and Semidefinite Programming

Two different definitions of extreme points, one of them taking the strict convex combination of two points and the other taking the hyperplane notion as a reference, are shown to be equivalent. The famous Representation (Resolution, Caratheodory) Theorem for Any Polyhedron, stating that any point in any (bounded or unbounded) polyhedron can be represented by its extreme points and extreme directions, is proved based on Sherali's work in 1987. Equivalence of basic feasible solutions and (algebraic and geometric) extreme points is shown in two different ways one of which makes use of a hint in Sherali's book. At the end, some ideas are given about transitions from feasible solutions to basic feasible solutions. Theory of Karmarkar's interior point algorithm studied via the affine scaling primal interior point algorithm for linear programming (LP). The path following primal-dual interior point algorithm for semidefinite programming (SDP) is studied via path following primal-dual interior point algorithm for linear pr-ogramming. Software packages of the book are introduced. At the end, Khachiyan's ellipsoid algorithm can be shown to be regarded as an interior point algorithm. Thereby, all the famous cornerstones of the previous century in LP and SDP are covered