Über die Autorin bzw. den Autor

Jiming Peng, Cornelis Roos, & Tamás Terlaky

Von der hinteren Coverseite

"The new idea of self-regular functions is very elegant and I am sure that this book will have a major impact on the field of optimization."--Robert Vanderbei, Princeton University

"The progress outlined in Self-Regularity represents one of the really major events in our field during the last five years or so. This book requires just standard mathematical background on the part of the reader and is thus accessible to beginners as well as experts."--Arkadi Nemirovski, Technion-Israel Institute of Technology

Auszug. © Genehmigter Nachdruck. Alle Rechte vorbehalten.

Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms

PRINCETON UNIVERSITY PRESS

Contents

Preface..........................................................................................................................................................................viiAcknowledgements.................................................................................................................................................................ixNotation.........................................................................................................................................................................xiList of Abbreviations............................................................................................................................................................xvChapter 1. Introduction and Preliminaries........................................................................................................................................1Chapter 2. Self-Regular Functions and Their Properties...........................................................................................................................27Chapter 3. Primal-Dual Algorithms for Linear Optimization Based on Self-Regular Proximities......................................................................................47Chapter 4. Interior-Point Methods for Complementarity Problems Based on Self-Regular Proximities.................................................................................67Chapter 5. Primal-Dual Interior-Point Methods for Semidefinite Optimization Based on Self-Regular Proximities....................................................................99Chapter 6. Primal-Dual Interior-Point Methods for Second-Order Conic Optimization Based on Self-Regular Proximities..............................................................125Chapter 7. Initialization: Embedding Models for Linear Optimization, Complementarity Problems, Semidefinite Optimization and Second-Order Conic Optimization.....................159Chapter 8. Conclusions...........................................................................................................................................................169References.......................................................................................................................................................................175Index............................................................................................................................................................................183

Chapter One

Linear Programming is a revolutionary development that permits us, for the first time in our long evolutionary history, to make decisions about the complex world in which we live that can approximate, in some sense, the optimal or best decision. George B. Dantzig

A short survey about the fields of linear optimization and interior-point methods is presented in this chapter. Based on the simple model of standard linear optimization problems, some basic concepts of interior-point methods and various strategies used in the algorithm are introduced. The purpose of this work, as well as some intuitive observations that sparked the authors' research, are described. Several preliminary technical results are presented as a preparation for later analysis, and the contents of the book are also outlined.

1.1 HISTORICAL BACKGROUND OF INTERIOR-POINT METHODS

1.1.1 Prelude

There is no doubt that the major breakthroughs in the field of mathematical programming are always inaugurated in linear optimization. Linear optimization, hereafter LO, deals with a simple mathematical model that exhibits a wonderful combination of two contrasting aspects: it can be considered as both a continuous and a combinatorial problem. The continuity of the problem is finding a global minimizer of a continuous linear function over a continuous convex polyhedral constrained set, and its combinatorial character is looking for optimality over a set of vertices of a polyhedron. The Simplex algorithm, invented by Dantzig in the mid-1940s, explicitly explores its combinatorial structure to identify the solution by moving from one vertex to an adjacent one of the feasible set with improving values of the objective function. Dantzig's Simplex method has achieved tremendous success in both theory and application, and it remains to this day one of the efficient workhorses for solving LO.

The invention of the digital computer has brought dramatic changes to the world, and thus to the area of optimization. By combining computers with efficient methods, we can now solve many large and complex optimization problems that were unsolvable before the advent of computers, or even two decades ago. Inspired by the fast development of computers, scientists began to study the complexity theory of methods in the 1960s and 1970s. An algorithm was termed polynomial if the number of arithmetic operations taken by the algorithm to solve the problem, could be bounded above by a polynomial in the input "size" of the problem. Correspondingly such a polynomial algorithm was recognized as an efficient algorithm. Although the Simplex method with certain pivot rules works very well in practice and its probabilistic computational complexity is strongly polynomial (see Borgwardt]), it might take 2ⁿ - 1 iterations to solve the LO problem constructed by Klee and Minty in 1972, where n is the number of variables in the problem with 2n constraints. Similar "exponential examples" for different variants of the Simplex method have also been reported. Agitated by these difficult exponential examples for the Simplex method, researchers in the field became interested in the issue of whether LO problems are solvable in polynomial time.

In 1979, an affirmative answer to the above question was given by Khachiyan, who utilized the so-called ellipsoid method to solve the LO problem and proved that the algorithm has a polynomial O(n²L) iteration complexity with a total of O(n⁴L) bit operations. Khachiyan's results were immediately hailed in the international press, and the ellipsoid algorithm was subsequently studied intensively by various scholars in both theory and implementation. Unfortunately, in contrast to people's high expectation, even the best known implementation of the ellipsoid method is far from competitive with existing Simplex solvers. In this first challenge of polynomial algorithms to the Simplex method, the latter was the obvious winner. Nevertheless, the sharp contrast between the practical efficiency and the theoretical worst-case complexity of an algorithm set the stage for further exciting developments.

1.1.2 A Brief Review of Modern Interior-Point Methods

The new era of interior-point methods (IPMs) started in 1984 when Karmarkar proposed his LO algorithm, which enjoyed a polynomial complexity of O(nL) iterations with O(n^3,5L) bit operations, and made the announcement that his algorithm could solve large-scale LO problems much faster than the Simplex method. At that time, the name of Karmarkar and his algorithm reached the front page of the New York Times despite the fact that his claim was received with much skepticism by some...