Description

This course is about algorithms for solving large-scale, continuous, optimization problems. We will start from the basics and gradually build up to state-of-the-art algorithms for both convex and non-convex optimization problems. The focus will be on developing a deeper understanding of the challenges imposed by a given problem and how to identify mathematical structures that can be used to implement an efficient solver for the optimization problem. This requires knowledge of fundamental theoretical results as well as hands-on experience. The lectures will cover the relevant mathematical background while the homework assignments will provide ample opportunities to practice the hands-on skills.

The main course is worth 6 credits. There is also an optional course project worth an additional 3 credits, where you can apply what you've learned to an application from your own scientific area.

Examples of topics covered are:

essential numerical linear algebra (matrix factorizations, sparsity, and randomized methods);
first-order methods for unconstrained optimization (line-search methods, conjugate gradient, stochastic gradient descent);
first-order methods for constrained optimization (projected gradient, proximal methods including the alternating direction method of multipliers);
related theory and techniques (duality, automatic differentiation, and more).

Learning outcomes

After passing the course the student should be able to:

formulate problems in science and engineering as optimization problems;
analyze an optimization problem and identify relevant mathematical properties such as smoothness and convexity as well as structure that enables computational advantages, e.g., sparsity;
describe and explain the principles behind the algorithms covered in this course;
analyze, implement, and use variations of common optimization methods tailored to a given large-scale problem;
critically examine and provide constructive criticism on other student's homework assignments.

Course Structure

The course gives 6 hp (you can receive an additional 3 hp by carrying out a project).

Lectures: 10
Hand-in assignments: 3
Peer reviews: 3
Project: Optional

Examination

The examination consists of three hand-in assignments.

Course literature

We will primarily follow:

Wright, S. J., & Recht, B. (2022). Optimization for data analysis. Cambridge University Press.

Schedule

The main 6 hp course will be given during the first half of the fall term 2023. We'll meet once a week on Wednesdays 13:15-15:00, from August 30 to November 1, in room 101142 (Ångström, House 10, Floor 1). The optional project will then take place in the second half of the term, with the final presentation just before Christmas.

Course level

This is a PhD level course.

Prerequisites

Undergraduate courses in multivariate calculus and linear algebra. Experience in scientific programming using, e.g., Python, MATLAB, or Julia. Previous coursework in optimization is advantageous but not required.

Registration

Register by sending an e-mail to both jens.sjolund@it.uu.se and sebastian.mair@it.uu.se . Registrations are open until the first lecture, or until the max capacity of 30 students is reached. We use the first come, first served principle.