Advanced undergraduateApplied MathematicsPlanned
Optimisation
Linear programming and duality, convex sets and functions, Lagrange multipliers and the KKT conditions, gradient descent and Newton's method, and applications to data fitting.
math.applied.optimisation
The lesson for this topic has not been written yet. The outline below is part of the curriculum map and has not been reviewed.
Builds on
Required prerequisites, all the way down: 37
You will learn to
- Formulate and solve linear programs with the simplex method, and interpret the dual problem.
- Prove that local minima of convex functions are global, and apply the KKT conditions.
- Implement gradient descent and analyse its convergence for smooth convex functions.
Definition
- A set C is convex if it contains the line segment between any two of its points.
- A function f is convex if f(tx + (1 − t)y) ≤ t f(x) + (1 − t) f(y) for all x, y and 0 ≤ t ≤ 1.
- A linear program optimises a linear function subject to finitely many linear inequalities.
Theorem
- Strong duality for linear programming: if the primal problem has an optimal solution, so does the dual, with the same optimal value.
- Every local minimum of a convex function on a convex set is a global minimum.
- For a convex function with L-Lipschitz gradient, gradient descent with step size 1/L reduces the gap to the optimal value at rate O(1/k).
Common misconceptions
- Assuming every critical point is a minimum.
- Thinking every linear program has an optimal solution; it may be infeasible or unbounded.
Optional discoveries
- Statistical inference Least squares and maximum likelihood estimation are optimisation problems.
- ← Numerical methods
Learning pathways
Further reading
- Stephen Boyd and Lieven Vandenberghe, Convex Optimization (2004)
- Jorge Nocedal and Stephen J. Wright, Numerical Optimization (1999)