Introduction, canonical formulations, polyhedral geometry, simplex algorithm, duality et sensitivity analysis, introduction to discrete optimization (branch & bound).
Models : definitions and terminology, optimality conditions for unconstrained and constrained problems ; recognize and exploit convexity of a problem.
Methods : line-search methods for unconstrained problems (gradient, Newton and quasi-Newton methods) ; convergence properties (local and global) ; implementation details ; introduction to other methods (conjugate gradient, constrained problems, unavailable derivatives).
The course is comprised of lectures, exercise sessions and computer labs, as well as a project to be carried out in small groups. Consulting is available for help with the project.
Students will be evaluated with an individual written exam, based on the above-mentioned objectives. Students also carry out a project in small groups, whose evaluation is taken into account for the final grade.
- Introduction to Linear Optimization, Dimitri Bertsimas and John Tsitsiklis, Athena Scientific, 1997.
- Linear Programming. Foundation and Extensions, Robert Vanderbei, Kluwer Academic Publishers, 1996.
- Integer Programming, Laurence Wolsey, Wiley, 1998.
- Numerical Optimization, Jorge Nocedal et Stephen J. Wright, Springer, 2006.
- Convex Optimization, Stephen Boyd et Lieven Vandenberghe, Cambridge University Press, 2004.