Infeasibility of either the primal or the dual problem is detected by divergence of the iterates. After presenting a prototype infeasible IPM preprocessing techniques, elements and algorithms of sparse linear algebra, adaptive higher order methods, initialization, starting point and stopping strategies are discussed. The effect of centering, croos-over and basis identification techniques are studied. Finally some open problems are presented. Each has his own strong points.
Several example illustrate and ease the understanding.
After presenting a prototype polynomial algorithm and an implementable variant of the prototype algorithm, several classes of structured convex programs are considered that satisfy the imposed smoothness condition. It is quite a straightforward idea that IPMs are generalizable for linear complementarity problems at least if the coefficient matrix satisfy some additional condition. Here feasible and infeasible IPMs for linear complementarity problems with appropriate matrices are discussed. The generalization for non-linear complementarity problems is far from being trivial. Smoothness conditions similar to that discussed in Chapter 7 are needed.