Topics

Introduction: Motivation and examples (3 hours)

Basics: Rd, vectors, matrices, norm, sequences & convergence, functions in one and several variables, Taylor series, derivatives, gradient, sub-gradient, Hessian, properties of symmetric operators, contours, affine functions, hyperplanes, convex functions, minima: local and global, subspaces, affine spaces, half-spaces, convex sets (9 hours)

Unconstrained Optimisation: gradient descent, line search, rates for various classes of convex functions, steepest descent, Newton’s method, conjugate gradient method, quasi-Newton method, linear least-squares regression: rates (9 hours)

Constrained Optimisation: linear and convex constraint sets, linear programming, simplex, interior-point method, duality theory: primal/dual programs, weak, strong duality, KKT conditions (12 hours)

Stochastic Optimisation: stochastic gradient descent, step-size conditions, Keifer-Wolwowitz method, simultaneous perturbation stochastic approximation (SPSA) method, smoothed functional method (9 hours)

Learning Outcomes

As a result of this course, the student should be able to

  • Pose a given optimisation problem by identifying the objective and constraints.
  • Draw level sets and graphs of functions, identify constraint regions described by set of function.
  • Choose stepsize and identify rates of convergence of optimisation algorithms.
  • Use stochastic optimisation techniques to derive data driven algorithms .

Learning Objectives

To

  • Look at the regions and functions in `d’ dimensions.
  • Build algorithms that find minima using first and second order information.
  • Look at constraint optimisation and duality theory with linear programming as a special case.
  • Introduce basics of stochastic optimisation

Text Books

  1. Introduction to Optimization: Edwin K. P. Chong and Stanislaw H. Zak, WileyInterscience Series in Discrete Mathematics and Optimization (ISBN-13: 9780471089490, ISBN-10: 0471089494).

References

  1. Boyd, Stephen, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004. (ISBN-13: 978-0521833783, ISBN-10: 0521833787)
  2. Fletcher, Roger. Practical methods of optimization. John Wiley & Sons, 2013. (ISBN:978-0-471-49463-8)