Optimization: Insights and Applications
This book provides an excellent overview of the theory, methods and applications of continuous optimization problems. The book deals with one-dimensional optimization (chapter 1), unconstrained optimization (chapter 2), optimization under equality constraints (chapter 3), optimization under inequality constraints (chapter 4), linear programming (chapter 6), convex optimization (chapter 7), mixed smooth-convex optimization (chapter 10), dynamic programming in discrete time (chapter 11), and dynamic optimization in continuous time (chapter 12). The following four-step procedure, conveniently adapted to each of the above families of continuous optimization problems, is proposed for computing an optimal solution of those problems that are analytically solvable (i.e. by a formula):
1. Establish the existence of global solutions.
2. Write down the first order necessary conditions.
3. Investigate these conditions.
4. Write down the conclusions.
The main tools in step 1 are the classical Weierstrass theorem (applied to some bounded non-empty sublevel set) and its extension to coercive functions. Step 2 is based upon the so-called Fermat-Lagrange principle (i.e. conditions of multiplier type) for finite-dimensional optimization problems and the Pontryagin principle for dynamic optimization problems. The particular versions of the Fermat-Lagrange principle for the different classes of mathematical programming problems considered in this book (all of them involving differentiable and/or convex functions, i.e. functions admitting linear approximations) are obtained via the tangent space theorem (closely related to the implicit function theorem) for smooth problems and by means of the supporting hyperplane theorem (related to the separation theorem) in the case of convex problems. Typically, step 3 provides a list of candidates and step 1 allows the identification of optimal solutions among them if the given problem is solvable. The second order conditions in chapter 5 give some insight although they do not play a crucial role in this approach because they can seldom be checked in practice. A similar point of view is adopted regarding the constraint qualifications.
Concerning those optimization problems that cannot be solved analytically but which admit a convex reformulation, the authors propose to solve them by means of interior point methods (such as the self-concordant barrier method) or cutting plane methods (such as the ellipsoid method). These and other complementary methods (e.g. line search methods and linear optimization methods) are described in chapters 6 and 7.
Each chapter contains a rich list of selected applications (many of them rare in the standard textbooks) that are presented as either motivating examples or as complementary exercises. Classical optimization problems (most of them relating to geometric objects), physical laws and economic models usually admit analytic solutions whereas real life (or pragmatic) applications may require the use of numerical methods. The solutions are given in appendix H. Chapters 8 and 9 are devoted to economic and mathematical applications, many of them surprising.
This description of the content of the book suggests that it is just one more of the many good textbooks that have been written on continuous optimization. Nevertheless, this book presents the following novel features:
1. The presentation of the material is as friendly, simple and suggestive as possible, including many illustrative examples and historical notes about results, methods and applications. These notes illustrate the important contributions of Russian mathematicians to optimization and related topics that have been ignored up to now in the occidental academic world.
2. The book is totally self-contained, although some familiarity with basic calculus and algebra could help the reader. The first explanation of each topic is intuitive, showing the geometric meaning of concepts (including those of basic calculus), results and numerical methods by means of suitable pictures. For instance, all the main ideas about one-dimensional optimization in the book are sketched in chapter 1 and this section could be read by college students. Subsection 1.5.1, entitled ‘All methods of continuous optimization in a nutshell’, is an excellent introduction to this topic. In order to understand the basic proofs and to be able to obtain analytic solutions, the reader must recall some elements of linear algebra, real analysis and continuity (Weierstrass theorem) that can be found in appendices A, B and C respectively.
3. The basic part of the book is written in a personal way, emphasizing the underlying ideas that are usually hidden behind technical details. For instance, in the authors’ opinion, the secret power of the Lagrange multiplier method consists in reversing the order of the two tasks of elimination and differentiation and not in the use of multipliers (as many experts think). In the same vein, personal anecdotes are also given, e.g. mention is made of some open problems (most of them extending classical optimization problems) that they posed in their lectures and were brilliantly solved by their students.
4. The book provides new simple proofs of important results on optimization theory (such as the Pontryagin principle in appendix G) and also results on other mathematical fields that can be derived from optimization theory (such as the fundamental theorem of algebra in chapter 2). Most formal proofs are confined to the last two appendices, which are written in a fully analytic style.
This book can be used for different courses on continuous optimization, from introductory to advanced level, for any field for which optimization is relevant: mathematics, engineering, economics, physics, etc. The introduction of each chapter describes a “royal road” containing the essential tools for problem solving. Examples of possible courses based on materials contained in this textbook are:
Basic optimization course: chapters 1, 2, 3, 4, and appendix D (Crash course on problem solving).
Intermediate optimization course: chapters 5, 6, 7, 10 and appendices E and F.
Advanced-course on the applications of optimization: chapters 8 and 9.
Advanced-course on dynamic optimization: chapters 11, 12 and Appendix G.
The website of the first author (people.few.eur.nl/brinkhuis) contains references to implementations of optimization algorithms and a list of corrections for the few shortcomings that are unavoidable in a first edition, despite its careful production. In my opinion, this stimulating textbook will be for the teaching of optimization what Spivak's "Calculus" was for the teaching of that subject (and even real analysis) in the 70’s.