Lindahl L.A. Convexity and Optimization

Uppsala (Sweden): Uppsala University, 2016. — 437 p.As promised by the title, this book has two themes, convexity and optimization, and convex optimization is the common denominator. Convexity plays a very important role in many areas of mathematics, and the book’s first part, which deals with finite dimensional convexity theory, therefore contains significantly more of convexity than is then used in the subsequent three parts on optimization, where Part II provides the basic classical theory for linear and convex optimization, Part III is devoted to the simplex algorithm, and Part IV describes Newton’s algorithm and an interior point method with self-concordant barriers. We present a number of algorithms, but the emphasis is always on the mathematical theory, so we do not describe how the algorithms should be implemented numerically. Anyone who is interested in this important aspect should consult specialized literature in the field. Maximization and minimization problems have of course been studied and solved since the beginning of the mathematical analysis, but optimization theory in the modern sense started around 1948 with George Dantzig, who introduced and popularized the concept of linear programming (LP) and proposed an efficient solution algorithm, the simplex algorithm, for such problems. Karmarkar’s discovery became the starting point for an intensive development of various interior-point methods, and a new breakthrough occurred in the late 1980’s, when Yurii Nesterov and Arkadi Nemirovski introduced a special type of convex barrier functions, the so-called self-concordant functions. Such barriers will cause a classical interior-point method to convergence polynomially, not only for LP problems but also for a large class of
convex optimization problems. This makes it possible today to solve optimization problems that were previously out of reach. The "embryo" of this book is a compendium written by Christer Borell and myself 1978–79, but various additions, deletions and revisions over the years, have led to a completely different text. The most significant addition is Part IV which contains a description of self-concordant functions based on the works of Nesterov and Nemirovski. The presentation in this book is complete in the sense that all theorems are proved. Some of the proofs are quite technical, but none of them requires more previous knowledge than a good knowledge of linear algebra and calculus of several variables.Preface.
List of symbols.
Convexity
Preliminaries.
Convex sets.
Separation.
More on convex sets.
Polyhedra.
Convex functions.
Smooth convex functions.
The subdifferential.
Optimization − basic theory
Optimization.
The Lagrange function.
Convex optimization.
Linear programming.
The simplex algorithm
The simplex algorithm.
Interior-point methods
Descent methods.
Newton’s method.
Self-concordant functions.
The path-following method.
The path-following method with self-concordant barrier.
Bibliografical and historical notices.

Answers and solutions to the exercises.
Index.