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)
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 .
- 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
- Introduction to Optimization: Edwin K. P. Chong and Stanislaw H. Zak, WileyInterscience Series in Discrete Mathematics and Optimization (ISBN-13: 9780471089490, ISBN-10: 0471089494).
- Boyd, Stephen, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004. (ISBN-13: 978-0521833783, ISBN-10: 0521833787)
- Fletcher, Roger. Practical methods of optimization. John Wiley & Sons, 2013. (ISBN:978-0-471-49463-8)