About This Course

This book teaches how to pose, analyse, and solve optimization problems whose variables range over a continuum. It is written for a reader working alone: an undergraduate or beginning graduate student in mathematics, engineering, economics, statistics, or computer science who wants the theory at the level of proof and the algorithms at the level where one can run them by hand on a small problem and explain every number.

You need three things before starting. From Multivariable Calculus: gradients, Hessians, the chain rule along a line, and second-order Taylor expansion. From Linear Algebra: solving linear systems, rank and null space, eigenvalues of symmetric matrices, positive definiteness, and orthogonal projection onto a subspace. From a first proof course: comfort with quantifiers, with proof by contradiction, and with the words closed, bounded, and continuous as they are used in Real Analysis. When a result from one of those courses is used, it is stated with the hypotheses that the argument needs and marked once with its library identifier; it is not proved again here.

By the end you should be able to do five things without notes. Turn a verbal decision problem into a mathematical program and say whether a solution exists. Prove that a set or a function is convex, or exhibit the segment on which convexity fails. Decide whether a candidate point is optimal by checking first-order, second-order, or Karush–Kuhn–Tucker conditions, and produce a dual certificate that bounds how far from optimal it can be. Run gradient, Newton, quasi-Newton, projected, proximal, simplex, and barrier iterations on small problems and predict their rates of convergence from the constants of the problem. Choose among those methods for a new problem and state what evidence at termination would justify calling the answer optimal.

Notation is conventional. Vectors are columns, \(x^{\top}y\) is the inner product, and \(\lVert x\rVert\) without a subscript is the Euclidean norm \(\sqrt{x^{\top}x}\) . For symmetric matrices, \(P\succeq 0\) means positive semidefinite and \(P\succ 0\) means positive definite; \(A\succeq B\) means \(A-B\succeq 0\) . Inequalities between vectors, such as \(x\ge 0\) , hold componentwise. A star marks an optimal object: \(x^\star\) is a minimizer, \(p^\star\) an optimal value.

Each chapter ends with exercises that range from recall to proof. Work them with pencil first. The companion solutions give full arguments for some, graduated hints for others, and bare answers for a few; an exercise with no support is meant to be settled by the methods of its chapter alone. Several exercises ask you to find the flaw in a plausible argument. Treat those seriously: recognising a wrong argument is a different skill from producing a right one, and optimization offers many attractive wrong arguments. The cumulative review at the end mixes chapters without saying which one each problem belongs to, because choosing the tool is part of the problem.