Continuous Optimization

Recommended Prerequisites

Mathematical Analysis II, Linear Algebra, Numerical Linear Algebra

Teaching Methods

The aim of theoretical and practical classes is to consolidate concepts and do some problem solving with the active participation of the students. Small computational problem solving can be done.

Learning Outcomes

This course offers an introduction to the foundations of contiuous optimization, starting from linear programming and going through the basic theory and the most common methods in nonlinear programming with and without restrictions. Over the duration of the course, special emphasis will be given to applications to data science, that will illustrate the methods that will be covered.
This course intends to develop a solid mathematical basis over which a more applicational component can later be securely developped, namely in the field of machine learning.
By the end of the course the student should know and understand the more important algorithms in continuous optimization, be able to model and solve optimization problems and be capable of autonomously implementing elementary versions of them.

Work Placement(s)

No

Syllabus

1. Linear programming
1.1- Formulations
1.2- Convex geometry
1.3- Simplex algorithm
1.4- Duality
2. Unconstrained nonlinear optimization
2.1- Existence and uniqueness of solutions
2.2- Line search methods
2.2-1. First order methods
2.2-2. Second order methods [Newton, BFGS…]
2.3- Trust-region methods
3. Constrained nonlinear optimization
3.1- Constraint qualification and suficiente and necessary conditions for optimality
3.2- Quadratic penalty method
3.3- Projected gradient
3.4- Augmented Lagrangean
3.5- Sequential quadratic programming
4. Data science applications (to distribute throughout the course). For example compressed sensing, nonlinear least squares, LASSO, etc.

Head Lecturer(s)

José Luís Esteves dos Santos

Assessment Methods

Assessment
Resolution Problems: 15.0%
Exam: 85.0%

Bibliography

 D. Bertsimas, J.N. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997.

M.S. Bazaraa, J.J. Jarvis, H.D. Sherali, Linear Programming and Network Flows, segunda edição, Wiley & Sons, 1990.

 J. Nocedal e S. J. Wright, Numerical Optimization, segunda edição, Springer, Berlim, 2006.

 M.S. Bazaraa, H.D. Sherali, C.M. Shetty. Nonlinear programming: theory and algorithms. John Wiley & Sons, 2013.

S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.

 I. Griva, S. G. Nash e A. Sofer, Linear and Nonlinear Optimization, segunda edição, SIAM, Filadélfia, 2009.

 S. Sra, S. Nowozin, S.J. Wright. Optimization for machine learning. Cambridge, Mass. MIT Press, 2012.

- G. Strang. Computational Science and Engineering. Wellesley-Cambridge Press, 2007.