A Gentle Introduction to Optimization

This introductory text is the opposite of a cookbook. It ensures that you understand what kinds of problems we are interested in, what would constitute solutions, and what kind of mathematics can be used to attack the problems. Only then does it go into the techniques of solution. It avoids getting too abstract by always giving concrete examples; indeed most of the first 45 pages of the book is devoted to example problems. However, it is primarily a theory book rather than an applied book. The prerequisites are very low, claimed (p. ix) to be only first-year linear algebra.

Although it is an introduction and does not go very deep, it does cover an impressive amount of optimization theory. One limitation is that it deals only with constrained optimization, so there are for example no least-squares problems or techniques to find the maximum of a function of several real variables. It is primarily a linear-programming book, but one that concentrates on the characteristics of linear programs and teaches only a moderate amount of technique (the simplex method and tableaus get only a few pages). Duality is a key concept; about one-third of the book is devoted to that and its consequences.

There is a moderate amount on integer programming and a little bit on non-linear problems; for both areas the primary technique is to replace the given problem with a less-constrained linear program in continuous variables (relaxation). For integer programs the book teaches the two techniques of cuttings planes and branch and bound. For non-linear problems the difficulty is often that the feasible region is not convex, and the book shows some ad-hoc methods for expanding the feasible region to a convex region. There’s some discussion of Lagrange multipliers. Several forms of the Karush–Kuhn–Tucker theorem are presented.

There are examples of discrete problems scattered though the book, such as shortest-path problems. The book shows how to code these with boolean variables to signal whether an item is included or not. The problem then becomes an integer programming problem, where the integers are constrained to take only the values 0 or 1.

Bottom line: a surprisingly comprehensive though accessible introduction, well-written and having lots of interesting topics.

Allen Stenger is a math hobbyist and retired software developer. He is an editor of the Missouri Journal of Mathematical Sciences. His mathematical interests are number theory and classical analysis.