A Gentle Introduction to Optimization

Citation

Guenin, B., Könemann, J., & Tunçel, L. (2014). A Gentle Introduction to Optimization. Cambridge University Press.

Chapter Summary

The book is short, about 280 pages: seven chapters and an appendix on computational complexity, with more than 140 exercises. Sections and chapters marked with an asterisk are designed to be skipped without loss, and most chapters close with a "Further reading and notes" section. The preface names relaxation, primal–dual reasoning, convexity and geometric interpretation as the threads that run through the whole book.

Chapter 1: Introduction

The chapter is about modelling, not solving. It opens with a small production-planning problem for a fictional company, WaterTech, and uses it to separate the word description of a problem from its mathematical formulation and to explain what it means for a formulation to be correct. It then introduces linear programs (including multiperiod models), integer programs (assignment and knapsack problems), optimization problems on graphs (shortest paths and minimum-cost perfect matchings, first described and then written as integer programs) and nonlinear programs, among them pricing a gadget and finding a "central" feasible solution of a linear program.

Chapter 2: Solving linear programs

Starting from the three possible outcomes of a linear program (infeasible, unbounded, optimal), the chapter brings problems into standard equality form, defines bases and canonical forms, and builds the simplex algorithm from a single iteration upwards, with a two-phase method for finding a first feasible solution. The tableau version of simplex is a starred section. The chapter ends with the geometry of polyhedra, convexity and extreme points, and interprets the simplex algorithm geometrically. The preface says the presentation deliberately favours the main ideas over implementation detail.

Chapter 3: Duality through examples

Duality is introduced through two combinatorial problems: shortest paths and minimum-cost perfect matching in bipartite graphs. For each, the chapter finds an intuitive lower bound, turns it into a general weak-duality argument, and derives and proves an algorithm from it. The preface states that one of the two problems is enough.

Chapter 4: Duality theory

The general theory follows the examples: weak and strong duality for linear programs, complementary slackness and a geometric characterization of optimality. Farkas' lemma is a starred section.

Chapter 5: Applications of duality*

An optional chapter with three applications: a primal–dual approximation algorithm for set cover, compared with a greedy method; the economic interpretation of dual variables; and the max-flow–min-cut theorem, proved with totally unimodular matrices.

Chapter 6: Solving integer programs

The chapter compares integer programs with their linear-programming relaxations and presents the two classical solution methods, cutting planes (linked back to the simplex algorithm) and branch and bound. A starred section treats the traveling salesman problem with a separation algorithm.

Chapter 7: Nonlinear optimization

After examples and a section showing that some nonlinear programs are very hard, the chapter develops convex functions, epigraphs and level sets, relaxes convex problems through subgradients and supporting halfspaces, and proves a Karush–Kuhn–Tucker theorem, first for differentiable convex problems, then through Lagrangians, then for nonconvex problems. Starred sections cover convex relaxation of nonconvex problems and a polynomial-time interior-point method for linear programs. The preface stresses that the KKT theorem is reached with linear algebra and geometry alone, without real analysis.

Appendix A: Computational complexity

A brief introduction to what makes an algorithm fast or slow: big-O notation, input size, polynomial versus exponential running times, the classes P, NP and co-NP, reductions and NP-completeness, with the book's own algorithms as examples.

Key Concepts

Chapters 1–2: Formulation and the simplex method

• Formulation: a mathematical model with variables, an objective function and constraints, judged correct when its feasible solutions match those of the word description.
• Linear, integer and nonlinear programs: the three kinds of formulation; the book tries for a linear program whenever possible, since these are the easiest to solve.
• Bases and canonical forms: the algebraic description of a vertex that the simplex algorithm moves between.
• Extreme points: the corners of a polyhedron, which give the geometric meaning of a simplex iteration.

Chapters 3–5: Duality

• Weak duality: any feasible dual solution bounds the optimal value of the primal problem.
• Strong duality and complementary slackness: when optimal solutions exist, the two optimal values agree, and the optimal pair satisfies matching zero conditions.
• Primal–dual algorithm: a method that keeps a primal and a dual solution together, used for shortest paths, matchings and set cover.
• Totally unimodular matrices: constraint matrices for which the linear program already has integral optimal solutions, giving the max-flow–min-cut theorem.

Chapter 6: Integer programs

• Relaxation: dropping integrality to obtain a linear program whose value bounds the integer optimum.
• Cutting planes and branch and bound: the two classical ways of closing the gap between an integer program and its relaxation.

Chapter 7 and Appendix A: Nonlinear optimization and complexity

• Convex functions and subgradients: the structure that makes nonlinear problems tractable and lets them be relaxed by halfspaces.
• Karush–Kuhn–Tucker conditions: optimality conditions for constrained nonlinear problems, derived here through geometry and Lagrangians.
• P, NP and NP-completeness: the vocabulary for separating easy problems from hard ones.

Critical Analysis

Strengths

• Low entry point, real destination. The preface asks only for first-year linear algebra, yet the book reaches duality, integer programming and a Karush–Kuhn–Tucker theorem. It is meant to prepare students for further courses in optimization, and its "Further reading and notes" sections point the way.
• Duality taught through problems first. Chapter 3 derives weak duality and a correct algorithm from intuitive lower bounds for shortest paths and matchings before Chapter 4 states the general theory, so the abstract results have something concrete behind them.
• Built for different courses. Starred material can be skipped, and the preface sets out about ten chapter sequences: modelling and applications, linear programming only, linear and discrete optimization for a computer science department, linear and nonlinear optimization, and others. The drafts were used by twelve instructors over four years with students from accounting and business to pure mathematics and computer science.
• Combinatorics and complexity alongside continuous methods. Graph problems, approximation algorithms, total unimodularity and an appendix on P and NP sit in the same short book as convexity and KKT conditions, so the book serves students of operations research and computer science as well as of continuous mathematics.

Limitations

• Light on algorithms for nonlinear problems. Chapter 7 is about convexity and optimality conditions; apart from the starred interior-point method for linear programs, the table of contents shows no algorithms for nonlinear problems.
• Brief by design. The preface sets out to keep the text concise and to leave advanced or side topics to starred sections and exercises, so students who want more depth on any one topic will need a second book.
• Solutions for instructors only. The publisher says solutions are available to instructors; independent readers have no answers to check against.
• No software. The table of contents has no material on modelling languages or solvers; formulations are written out by hand, and computation is a matter for the course to add.

Where It Fits in the Course

This is the natural first textbook of the optimization strand of the course. Alain Goriely's Applied Mathematics: A Very Short Introduction is a much shorter, almost equation-free account of how applied mathematicians build and analyse models, and makes good background reading before or alongside it. Ian Jacques's Mathematics for Economics and Business and Adam Ostaszewski's Advanced Mathematical Methods treat optimization as one part of a broader toolkit of mathematical methods for economics, business and related applications, and do not centre on linear programming and duality.

Chong, Lu and Żak's An Introduction to Optimization is the next step for those who want algorithms. It covers unconstrained and constrained nonlinear optimization and linear programming in more depth, with applications to machine learning, and fills the main gap in Chapter 7 here. Boyd and Vandenberghe's Convex Optimization is a fuller and more demanding treatment of convex sets, functions, duality and algorithms; readers who have finished Chapters 4 and 7 of this book will find its ideas familiar.

How to Use This Book

The book suits first- and second-year students in mathematics, computer science, engineering, business or economics who have taken a first course in linear algebra; matrix manipulation and solving linear systems are all it needs. Comfort with reading short proofs helps, because duality and correctness arguments are proved, not only stated.

A reading plan for a one-term course:

• Core: Chapter 1 for modelling, Chapter 2 for the simplex method (the tableau section can be skipped), one of the two problems in Chapter 3, and Chapter 4.
• Then choose: Chapter 6 for discrete optimization, Chapter 7 for nonlinear optimization, or both. Chapter 5 is optional; its section on economic interpretation suits business and economics students, while set cover and max-flow–min-cut suit computer scientists.
• For a modelling course, follow the preface's suggestion of Chapters 1, 2, 3, 6 and 7. If the simplex method is already known, start at Chapter 3 instead.
• The appendix on complexity can be read once the simplex method is familiar; it explains why linear programs are treated as easy and integer programs as hard.

Spend most time on Chapter 1's formulation exercises: writing correct models is the skill the rest of the book relies on. Check your models by asking whether every feasible solution of the word problem matches one of the formulation and vice versa, as the first chapter does. Since solutions go to instructors only, it is worth solving small models with any linear-programming solver to confirm answers by computer, and leaving the starred exercises for a second pass.