Optimisation & Numerical Methods

This module introduces the algorithms used to solve the continuous and constrained optimisation problems that arise in modelling, machine learning and scientific computing, together with the numerical-analysis tools needed to run them reliably on finite-precision hardware. Learners cover gradient and Newton-type descent, line search and trust region, convexity, KKT conditions, linear and quadratic programming, and the main sources of numerical error. Mastery is demonstrated when a learner can pick an appropriate algorithm for a given problem, justify convergence and stability, and read the output critically.

Learning Outcomes

Characterise convex sets and functions and verify convexity through first- and second-order conditions.

Derive and apply first-order optimality conditions and the KKT conditions for constrained problems.

Select and tune gradient descent, Newton, quasi-Newton, conjugate-gradient and stochastic-gradient methods.

Apply bisection, Newton-Raphson and secant methods to root-finding and justify their convergence orders.

Formulate and solve linear and quadratic programmes using the simplex and interior-point methods.

Assess numerical error, condition number and stability for a chosen algorithm and representation.

Design line-search and trust-region strategies that satisfy Wolfe or Armijo conditions.

Translate an applied problem into a well-posed optimisation statement and interpret the solver output.

Topics Covered

Floating-point arithmetic, rounding error and the IEEE 754 standard

Condition number, forward and backward error, numerical stability

Root finding: bisection, Newton-Raphson, secant and fixed-point iteration

Convex sets, convex functions and operations that preserve convexity

First- and second-order optimality conditions

Gradient descent, step-size rules and convergence analysis

Newton's and quasi-Newton methods (BFGS, L-BFGS, DFP)

Conjugate-gradient and nonlinear conjugate-gradient methods

Stochastic gradient descent and mini-batch methods

Line search (Armijo, Wolfe) and trust-region strategies

Linear programming: standard form, duality and the simplex method

Quadratic programming and interior-point methods

Constrained optimisation: Lagrangian, KKT, and penalty/barrier methods

Non-smooth optimisation: subgradients and proximal methods

Numerical linear algebra for optimisation (LU, Cholesky, iterative solvers)

Skills Developed

Algorithm selection Convergence analysis Numerical stability assessment Convexity verification KKT reasoning Implementation of iterative solvers Benchmarking and tuning Reading solver diagnostics

Suggested Resources

Boyd, S. & Vandenberghe, L. (2004). Convex Optimization, Cambridge University Press

Nocedal, J. & Wright, S.J. (2006). Numerical Optimization, 2nd ed., Springer

Trefethen, L.N. & Bau, D. (1997). Numerical Linear Algebra, SIAM

Burden, R.L., Faires, J.D. & Burden, A.M. (2015). Numerical Analysis, 10th ed., Cengage

Bertsekas, D.P. (2016). Nonlinear Programming, 3rd ed., Athena Scientific

Higham, N.J. (2002). Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM

Stanford EE364a Convex Optimization lecture notes

Assessment

Learners are judged on choosing and implementing an appropriate algorithm, justifying its convergence and reasoning about numerical error. The weighting rewards implementation and critique over paper-and-pencil derivation alone.

Computational project implementing and tuning a solver40%

Written problem set portfolio on convexity, KKT and convergence30%

Timed closed-book examination15%

MCQ diagnostic bank (this module's 200+ item pool)15%

Practice bank: 197 MCQs · Timed mock & self-paced modes

Start Practice →