A Kernel Function Approach for Interior Point Methods

The last 20 years gave rise to revolutionary developments, both in computer technology and in software and algorithm improvements . As a consequence, Linear Optimization (LO) problems that 20 years ago required a computational time of one month, can now be solved within 10 seconds. The book address algorithmic improvements in Interior Point Methods (IPMs) for LO, and introduce a new class of kernel functions. The author derive many new and tight estimates that greatly simplify the analysis of IPMs. Ten specific kernel functions are considered, and using the new estimates present a complete complexity analysis for each of these functions. Iterations bounds both for large- and small-update methods for LO are derived. These results are extended to semidefinite optimization and linear complementarity problems. The book present an easy implementations of IPMs algorithm, and investigate the influence of the choice of the kernel function on the computational behavior of the algorithm for LO. An indispensable reference for students and researchers in applied mathematics, computer science, operations research, management science and engineering.