Optimisation
Year 3 · 4 sections · 43 concepts · 64 practice questions
What's covered
free1 · Linear programming12 concepts
- Overview 1 · The plan of this section
- Definition 1.1 · Linear programmes in standard form
- Proposition 1.2 · Basic feasible solutions are vertices
- Theorem 1.3 · The fundamental theorem of linear programming
- Definition 1.4 · The simplex method
- Proposition 1.5 · The simplex optimality test
- Example 1.6 · The simplex method in action
- Definition 1.7 · The dual linear programme
- Theorem 1.8 · Weak duality
- Theorem 1.9 · Strong duality
- Corollary 1.10 · Complementary slackness
- Check 1.11 · Check: solving and certifying an LP
2 · Convexity11 concepts
- Overview 2 · The plan of this section
- Definition 2.1 · Convex sets
- Definition 2.2 · Convex functions
- Proposition 2.3 · Derivative tests for convexity
- Theorem 2.4 · Local minima of convex functions are global
- Corollary 2.5 · The first-order optimality condition
- Theorem 2.6 · Projection onto a closed convex set
- Theorem 2.7 · The separating hyperplane theorem
- Corollary 2.8 · Farkas' lemma
- Example 2.9 · Building convex functions
- Check 2.10 · Check: proving a problem is convex
3 · Constrained optimisation10 concepts
- Overview 3 · The plan of this section
- Theorem 3.1 · Lagrange multipliers (equality constraints)
- Definition 3.2 · The Lagrangian and the dual problem
- Theorem 3.3 · The Karush–Kuhn–Tucker conditions
- Theorem 3.4 · KKT conditions are sufficient for convex problems
- Theorem 3.5 · Slater's condition and strong duality
- Example 3.6 · Solving problems with KKT
- Proposition 3.7 · Second-order sufficient conditions
- Remark 3.8 · Multipliers as shadow prices
- Check 3.9 · Check: solving a constrained problem
4 · Algorithms10 concepts
- Overview 4 · The plan of this section
- Definition 4.1 · Gradient descent and smoothness
- Lemma 4.2 · The descent lemma
- Theorem 4.3 · Gradient descent on convex functions
- Theorem 4.4 · Linear convergence for strongly convex functions
- Example 4.5 · Conditioning and zigzagging
- Proposition 4.6 · Backtracking line search
- Theorem 4.7 · Newton's method and quadratic convergence
- Example 4.8 · Newton's method in one dimension
- Check 4.9 · Check: choosing and analysing an algorithm
Try it: a free card from this module
This is exactly what studying looks like inside UniMaths.
Proposition 1.2 · Basic feasible solutions are vertices
Vertex ⇔ BFS: choose independent columns, solve, check non-negativity.
Proof
Learn all 43 concepts like this
Cards, step-by-step proofs, and 64 questions scheduled so you review right before you forget.