Advanced Optimization

Recommended Prerequisites

Continuous Optimization

Teaching Methods

The lectures will be of expository nature, while promoting student participation and where the student is expected to develop on her/his own applications of the methods learned.

There will also be problem solving and small applicational computational projects for illustrating the topics covered.

Weekly, tutorial time is offered to help students.

Learning Outcomes

This course aims to give the students advanced notions of optimization, with particular emphasis on those that are of importance in the field of machine learning. The intention is to provide the students with a solid mathematical foundation for the methods they use, allowing them to evaluate the capabilities and limitations of the studied methods and their applications.

The course aims at developing the following skills: analysis and synthesis, organization and planning, oral and written communication, problem-solving skills and computational ability. On the personal level it also allows to develop self-learning skills and independent thinking.

Work Placement(s)

No

Syllabus

1 - Ellipsoid method
2- Advanced first order methods:
- General convex functions, strong and strict convexities, subgradients
- Revision of gradient descent
- Nesterov's accelerated gradient descent
- Frank-Wolfe conditional gradient descent
- Projected subgradient descent
3 - Sums of smooth and simple nonsmooth functions
- LASSO
- ISTA and FISTA
4- Interior point methods
- Self-concordand functions
- ISTA and FISTA
5- Semidefinite Programming
- Properties
- Combinatorial Programming relaxations
- Various applications: Nuclear norm, phase retrieval, polynomial optimization...
6- Derivative free optimization

Head Lecturer(s)

João Eduardo da Silveira Gouveia

Assessment Methods

Assessment
Project: 15.0%
Frequency: 85.0%

Bibliography

Convex Optimization: Algorithms and Complexity (2015) de Sébastien Bubeck

Lectures on Convex Optimization, 2^nd ed., (2018) de Yurii Nesterov

Convex Optimization (2004) de Stephen Boyd e Lieven Vandenberghe

Optimization for Machine Learning (2011), editado por Suvrit Sra, Sebastian Nowozin, Stephen J. Wright

Introduction to Derivative-Free Optimization (2009) de Andrew R. Conn , Katya Scheinberg e Luis N. Vicente