E-raamat: Arc-Search Techniques for Interior-Point Methods [Taylor & Francis e-raamat]

"This book discusses one of the most recent developments in interior-point methods, the arc-search techniques. Introducing these techniques result in an efficient interior-point algorithm with the lowest polynomial bound, which solves a long-standing issue of the interior-point methods in linear programming, i.e., the algorithm with the best polynomial bound is the least efficient and the most efficient interior-point algorithm cannot be proved to converge. The book also covers important results since 1990s and the extensions of the arc-search techniques to the general optimization problems, such as convex quadratic programming, linear complementarity problem, and semi-definite programming"--

This book discusses an important area of numerical optimization, interior-point method, which has been very active since 1980s when people realized that all popular simplex algorithms were not convergent in polynomial time and many interior-point algorithms could be proved to converge in polynomial time. However, for a long time, there was a noticeable gap between theoretical polynomial bounds of the interior-point algorithms and efficiency of these algorithms. Namely, strategies, which were known to be important to the computational efficiency, became barriers in the proof of good polynomial bounds. The more strategies were used in an algorithm, the worse the polynomial bounds were obtained. To further exacerbate the problem, Mehrotra’s predictor-corrector (MPC) algorithm (the most popular and efficient interior-point algorithm until recently) uses all good strategies and fails to prove the convergence. Therefore, MPC does not have polynomiality, a critical issue with the simplex method. This book discusses recent development that resolves the dilemma. It has three major parts. The first part, including Chapters 1, 2, 3, and 4, presents some most important algorithms during the development of the interior-point method around 1990s, most of them are widely known. The main purpose of this part is to explain the dilemma described above by analyzing these algorithms’ polynomial bounds and summarizing the computational experience associated with these algorithms. The second part, including Chapters 5, 6, 7, and 8, describes how to solve the dilemma step by step using arc-search techniques. At the end of this part, a very efficient algorithm with the lowest polynomial bound is presented. The last part, including Chapters 9, 10, 11, and 12, extends arc-search techniques to some more general problems, such as convex quadratic programming, linear complementarity problem, and semi-definite programming.