IKT719 - Advanced Optimization

Overview

This course targets competences in formulating, analyzing, and solving non-linear optimization problems. As opposed to the introductory course IKT720, here problems are not necessarily convex. The first part deals with the formulation and theoretical analysis of optimization problems. The second part is concerned with algorithms.

Prerequisites

Linear algebra, analysis, convex optimization, MATLAB programming.

Course Material

Since I could not find any reference collecting all the material that I deemed most relevant, I wrote these lecture notes, which have gradually grown over the years. These notes are intended to serve as i) material for self-study, ii) lecturing material, and iii) reference. To achieve this end, the contents are clearly structured and explicitly organized to the paragraph level.

Teaching Approach

Since this topic may be difficult to digest, the student is expected to carefully study the lecture notes before each session. A collection of quiz questions throughout the notes prompt the student to reflect on the concepts presented there, review additional material when necessary, and stimulate persistence in the student's long-term memory. The answers to the quiz questions can be submitted before the corresponding lecture to obtain extra grade points.

The lectures then build the big picture and query students to both help them understand the core concepts and to detect those parts that were not understood. They follow a guided flipped-classroom approach.

Syllabus

• Optimization problems
  • Introduction
    • Optimization problems
    • Solution of an optimization problem
    • Existence of optimal solutions
  • Properties of optimization problems
    • Convexity
    • Strong convexity
    • Lipschitz smoothness
  • Equivalent problems
  • Solving optimization problems
• Optimality conditions and duality
  • Introduction
  • Unconstrained optimization problems
  • Constrained optimization problems
• Introduction to iterative methods
  • Introduction
  • Descent methods
  • Optimal first-order methods
• Optimization of non-differentiable objectives
  • Subgradients and subdifferentials
  • The subgradient method
  • Proximal methods
    • The proximal point algorithm
    • The proximal gradient method
• Distributed optimization
  • Primal decomposition
  • Dual decomposition
  • The method of multipliers
  • ADMM
• Stochastic optimization methods
  • Stochastic gradient descent
  • Momentum
  • Convergence analysis
  • Adaptive learning rate algorithms
    • AdaGrad
    • RMSprop
    • Adam
    • AdamW
• Dynamic programming

Main Bibliography

1. Daniel Romero, Advanced Optimization Lecture Notes.
2. Dimitri P. Bertsekas. Nonlinear Programming. Third edition, Athena Scientific, 2016.
3. Yurii Nesterov. Lectures on convex optimization. Springer, 2018.
4. Stephen P. Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.