Chapter 2 studies a new potential-function and an infeasible-interior-point method based on this function for the solution of linear programming problems. This work is motivated by the apparent gap between the algorithms with the best worst-case complexity and their most successful implementations. The factors contributing to this gap include the regularity assumptions imposed on the problems in theoretical analyses that appear to be unnecessary for the convergence of the implementations, and the heuristic tricks incorporated into the state-of-the-art implementations that are not addressed in complexity analyses. The method described here and its analysis do not require any regularity assumptions and have the flexibility to integrate any heuristic technique for implementation while maintaining the important polynomial complexity feature. Possible extensions of this method for the solution of convex linear complementarity problems are also discussed.
Chapter 3 focuses on the horizontal linear complementarity problem (HLCP). An algorithm to reduce an HLCP to a standard linear complementarity problem is presented. In addition, the properties of matrix pairs that are analogous to the properties of a square matrix such as positive semi-definiteness and P- and P0-properties are studied. It is established that HLCPs defined by a a large class of matrix pairs, including P0-pairs, are reducible.
Chapter 4 studies certain interior-point methods for the semidefinite programming problem. Nesterov and Todd's interior-point method for such problems is examined and a framework for an efficient implementation of this method is developed. Specifically, Chapter 4 demonstrates how Nesterov-Todd search directions can be viewed as Newton directions, and how Mehrotra predictor-corrector steps can be computed in this framework.
The results of numerical experiments obtained from an implementation of the method developed in Chapter 2 are reported in Chapter 5.