An Introduction to Optimization: With Applications to Machine Learning

Citation

Chong, E. K. P., Lu, W.-S., & Żak, S. H. (2023). An Introduction to Optimization: With Applications to Machine Learning (5th ed.). Wiley.

Chapter Summary

The book has 31 chapters in five parts, about 670 pages, with references and an index. The publisher says every chapter is followed by MATLAB exercises and practice problems. The fifth edition adds a chapter on Lagrangian duality and expands the coverage of matrix games, projected gradient algorithms and machine learning, according to the publisher.

Part I (Chapters 1–5): Mathematical Review

Chapter 1, "Methods of Proof and Some Notation", introduces truth tables, De Morgan's laws, conditional and biconditional statements, proof by direct argument, contraposition, contradiction and induction, and set notation, in a few pages. Chapter 2, "Vector Spaces and Matrices", covers vectors and matrices, rank, linear equations, and inner products and norms. Chapter 3, "Transformations", treats linear transformations, eigenvalues and eigenvectors, orthogonal projections, quadratic forms and matrix norms. Chapter 4, "Concepts from Geometry", covers line segments, hyperplanes and linear varieties, convex sets, neighbourhoods, and polytopes and polyhedra. Chapter 5, "Elements of Calculus", covers sequences and limits, differentiability, the derivative matrix, differentiation rules, level sets and gradients, and Taylor series.

Part II (Chapters 6–14): Unconstrained Optimization

Chapter 6, "Basics of Set-Constrained and Unconstrained Optimization", introduces set-constrained and unconstrained problems and the conditions for local minimizers. Chapter 7, "One-Dimensional Search Methods", covers golden section, Fibonacci, bisection, Newton and secant methods, bracketing and line search in several dimensions. Chapter 8, "Gradient Methods", and Chapter 9, "Newton's Method", present steepest descent and Newton's method with analysis, the Levenberg–Marquardt modification and nonlinear least squares. Chapter 10, "Conjugate Direction Methods", and Chapter 11, "Quasi-Newton Methods", cover the conjugate gradient algorithm, rank-one correction, DFP and BFGS. Chapter 12, "Solving Linear Equations", covers least squares, recursive least squares, minimum-norm solutions and Kaczmarz's algorithm. Chapter 13, "Unconstrained Optimization and Neural Networks", treats single-neuron training and backpropagation. Chapter 14, "Global Search Algorithms", covers the Nelder–Mead algorithm, simulated annealing, particle swarm optimization and genetic algorithms.

Part III (Chapters 15–19): Linear Programming

Chapter 15, "Introduction to Linear Programming", gives a brief history, simple examples, two-dimensional programs, convex polyhedra, standard form and basic solutions. Chapter 16, "Simplex Method", develops row operations, the canonical augmented matrix, the simplex algorithm, matrix form, the two-phase and revised methods. Chapter 17, "Duality", covers dual programs, their properties and matrix games. Chapter 18, "Nonsimplex Methods", covers Khachiyan's, the affine scaling and Karmarkar's methods. Chapter 19, "Integer Linear Programming", covers unimodular matrices and the Gomory cutting-plane method.

Part IV (Chapters 20–25): Nonlinear Constrained Optimization

Chapter 20, "Problems with Equality Constraints", covers tangent and normal spaces, the Lagrange condition, second-order conditions and minimizing quadratics subject to linear constraints. Chapter 21, "Problems With Inequality Constraints", covers the Karush–Kuhn–Tucker conditions and second-order conditions. Chapter 22, "Convex Optimization Problems", covers convex functions, convex problems and semidefinite programming. Chapter 23, "Lagrangian Duality" (new in this edition), covers the primal–dual pair, general duality properties, strong duality and the convex case. Chapter 24, "Algorithms for Constrained Optimization", covers projections, projected gradient methods and their convergence, Lagrangian algorithms and penalty methods. Chapter 25, "Multiobjective Optimization", covers Pareto solutions, computing the Pareto front, reduction to single-objective problems and uncertain linear programs.

Part V (Chapters 26–31): Optimization in Machine Learning

Chapter 26, "Machine Learning Problems and Feature Engineering", covers data normalization, histograms of oriented gradients and principal component analysis with linear autoencoders. Chapter 27, "Stochastic Gradient Descent Algorithms", covers stochastic gradient descent and variance-reduced variants. Chapter 28, "Linear Regression and Its Variants", covers least-squares regression, cross-validation and regularization. Chapter 29, "Logistic Regression for Classification", covers binary and multicategory classification. Chapter 30, "Support Vector Machines", covers hinge loss, binary and multicategory classification and the kernel trick. Chapter 31, "K-Means Clustering", covers the algorithm, K-means++ initialisation, variants and image compression by vector quantization.

Key Concepts

Part I: Mathematical Review

• Methods of proof: direct proof, contraposition, contradiction and induction.
• Quadratic forms: the matrix tool used later to state second-order conditions.
• Convex sets and polyhedra: the geometry on which linear programming and convex optimization rest.
• Gradient and Taylor series: the calculus behind local minimizer conditions.

Part II: Unconstrained Optimization

• Conditions for local minimizers: first- and second-order conditions in Chapter 6.
• Steepest descent, Newton and quasi-Newton methods: the main families of iterative algorithms, compared by analysis in Chapters 8 to 11.
• Conjugate gradient algorithm: a method designed for quadratic problems and extended to nonquadratic ones.
• Backpropagation: gradient computation for neural-network training.

Parts III–IV: Linear and Nonlinear Constrained Optimization

• Simplex method and basic solutions: moving between vertices of a polyhedron.
• Duality: the dual of a linear program and, in the new Chapter 23, the Lagrangian dual of a nonlinear one.
• Karush–Kuhn–Tucker conditions: first-order conditions for inequality constraints.
• Pareto front: the set of trade-off solutions in multiobjective problems.

Part V: Machine Learning

• Stochastic gradient descent: updating from samples instead of the full objective.
• Logistic regression and support vector machines: classifiers trained by optimization.
• K-means clustering: clustering by repeated assignment and centre updates.

Critical Analysis

Strengths

• Self-contained preparation. Part I reviews the linear algebra, geometry and calculus needed before the optimization chapters begin, so a reader with some gaps can fill them in the book.
• Wide, orderly coverage. One text moves from unconstrained methods to linear programming, constrained nonlinear problems and machine learning. The publisher presents the book for a one- or two-semester senior undergraduate or beginning graduate course.
• Computational support. The publisher advertises MATLAB exercises after each chapter and worked examples. The authors' page links M-files for the algorithms, data sets and code for Part V, and Python code for some of the algorithms contributed by Paul Atzberger and his students at UCSB.
• Praise from a review of an earlier edition. The back cover quotes MAA Reviews on the third edition, saying that the book guides the reader along the learning path and that the examples are clearly stated with attention to detail.

Limitations

• Instructor-only solutions. The solutions manual is available only to instructors who adopt the book, so self-studiers must work without worked answers.
• Breadth over depth in places. The contents suggest brief treatments of some topics: semidefinite programming is a single section of Chapter 22, and integer programming is a three-section chapter. Readers who need a full treatment of convex optimization will want a dedicated text.
• Neural networks stay at the basics. They appear in Chapter 13 (single-neuron training and backpropagation), and the machine learning part lists regression, logistic regression, support vector machines and K-means, with no deep-network architectures.
• A long book for one course. With 31 chapters and about 670 pages, a course must choose what to omit.

Where It Fits in the Course

Within the optimization and applied mathematics list, Chong, Lu and Żak is the general textbook covering the standard syllabus. Guenin, Könemann and Tunçel's A Gentle Introduction to Optimization is the gentler first course, built on formulating problems and the simplex method with only a first course in linear algebra assumed. Boyd and Vandenberghe's Convex Optimization is the rigorous follow-up when convex problems and duality become the main topic, with Chapters 22 and 23 here as a bridge.

The other books on the list are broader: Ostaszewski's Advanced Mathematical Methods gives linear algebra and calculus with applications, Jacques's Mathematics for Economics and Business places optimization in an economic setting, and Goriely's Applied Mathematics: A Very Short Introduction is a nontechnical overview of how applied mathematicians work.

How to Use This Book

The publisher presents the book for one- or two-semester senior undergraduate or beginning graduate courses in optimization theory and methods, and as a reference for researchers and practitioners in mathematics, operations research, electrical engineering, economics, statistics and business. The site lists multivariable calculus and linear algebra as prerequisites.

A practical plan:

• Core for a one-semester course: Chapters 6 to 11 on unconstrained optimization, Chapters 15 to 17 on linear programming, and Chapters 20 and 21 on constrained optimization.
• Extensions: Chapter 22 on convex optimization and Chapter 23 on Lagrangian duality for readers moving toward modern theory, and Chapters 12 to 14 and 18 to 19 as options.
• Machine learning track: a sensible preparation for Part V is Chapters 6 to 9, 12 and 13, which supply gradient methods, least squares and backpropagation.
• Practice: do the exercises with MATLAB or Python code from the authors' page, and use Part I as a refresher rather than reading it straight through.