Full course description
Optimization (or “Optimisation”) is the subject of finding the best or optimal solution to a problem from a set of potential or feasible solutions.
Optimization problems are fundamental in all forms of decision-making, since one wishes to make the best decision in any context, and in the analysis of data, where one wishes to find the best model describing experimental data. This course treats two different areas of optimization: nonlinear optimization and combinatorial optimization. Nonlinear optimization deals with the situation that there is a
continuum of available solutions. A best solution is then usually approximated with one of several available general-purpose algorithms, such as Brent’s method for one-dimensional problems, Newton, quasi-Newton and conjugate gradient methods for unconstrained problems, and Lagrangian methods, including active-set methods, sequential quadratic programming and interior-point methods for general constrained problems. Combinatorial optimization deals with situations that a best solution from a finite number of available solutions must be chosen. A variety of techniques, such as linear programming, branch and cut, Lagrange relaxation dynamic programming and approximation algorithms are employed to tackle this type of problems. Throughout the course, we aim to provide a coherent framework for the subject, with a focus on consideration of optimality conditions (notably the Karush-Kuhn-Tucker conditions), Lagrange multipliers and duality, relaxation and approximate problems, and on convergence rates and computational complexity.
The methods will be illustrated by in-class computer demonstrations, exercises illustrating the main concepts and algorithms, and modelling and computational work on case studies of practical interest, such as optimal control and network flow.
Desired Prior Knowledge: Simplex algorithm. Calculus, Linear Algebra.
1. Nonlinear Programming, Theory and Algorithms, by Bazaraa, Sherali, and Shetty (Wiley). 2. Combinatorial Optimization, Algorithm and Complexity, by Papadimitriou and Steiglitz (Dover Publications).