Numerical Optimization

Lectures: Prof. Dr. Moritz Diehl,   

Exercises: Armin Nurkanovic      


The course’s aim is to give an introduction into numerical methods for the solution of optimization problems in science and engineering. The focus is on continuous nonlinear optimization in finite dimensions, covering both convex and nonconvex problems. It is intended for a mixed audience of students from mathematics, engineering and computer science.

The course is organized as inverted classroom and based on four pillars:

  • a course manuscript
  • lecture recordings, and
  • exercises, that are accompanied with solutions and solution recordings, and
  • weekly alternating Q&A and exercise sessions to discuss the course contents

Contact: moritz.diehl@imtek.uni-freiburg.dearmin.nurkanovic@imtek.uni-freiburg.de

 

*** This page is intended for the course as taught in the winter semester 2023/24 at the University of Freiburg. For a timeless version with a focus on self study of the material see here. ***


Organization of the course

**************************************************************************************************************

Exam date: (not confirmed, might be subject to changes): 20.03.2024, 10.00-12.00, Room: TBA

**************************************************************************************************************

The course is organized as flipped classroom. We provide recordings of the lecture and will meet once a week to discuss the course contents. This course has 6 ECTS credits. It is possible to do a project to get an additional 3 ECTS, i.e., a total of 9 ECTS for course+project. For more information please contact Armin Nurkanović.  

Meetings: We will meet every Tuesday, 14:00 to 15:30 in Room HS Weismann-Haus, Albertstr. 21a

These meetings are alternatingly dedicated to either Q&A sessions with Prof. Diehl or exercise sessions with the teaching assistant (see calendar below), and will not be recorded.

Ilias: There is also an Ilias course, though most material will be published on the page you are currently viewing. In Ilias, we provide a forum for discussion of any questions you have related to the course, be it organization, content or exercises. Please feel free to open new topics and to answer questions of your fellow students. Further, the mid term quiz will be published on Ilias (see below).
Link to Ilias course.

Lecture recordings: The lecture recordings were already created in a past semester. There are 24 lectures of approximately 90 minutes each. You can find the recordings below in the materials section, and a recommended schedule in the calendar.

Course manuscript: The lectures are accompanied by a detailed course manuscript, which you may find in the materials section below. We will provide printed versions.

Exercises: The exercises are mainly computer based. Computers with (MATLAB or Python) and CasADi installed are required to solve them (see below for details). The exercises are voluntary (though of course we strongly recommend to solve them). Nonetheless we offer the possibility to hand them in to receive feedback, but for this please respect the deadlines you can find in the calendar below. If you would like feedback on a specific part of the exercise especially, you can state so on your solution sheet. To hand them in, send them in an email to Armin Nurkanović.  

Q&A sessions: Every second week there will be a virtual Q&A session with Prof. Diehl, where you can ask any questions about the course content. The format is meant to be highly interactive and depends strongly on your participation. We would recommend that while watching the video lectures or reading the course script, you write down any questions that come to your mind, such that you have them readily available for the Q&A sessions.

Exercise sessions: Every other week we will meet for the exercise sessions. They will be used to discuss the solutions and any questions related to the exercises. These can either be questions about the current exercise sheet or questions about the solution to the last sheet. As the Q&A sessions, this format depends heavily on your participation.

Mid term quiz: Some time before christmas, we will publish a quiz on Ilias, with questions covering the course contents so far. It is obligatory that you pass this quiz until 12.12.2023 (23:59), but you have infinitely many trials for doing so and will receive instant feedback by auto-grading. The quiz will be online at least one week before the deadline. Note that the questions will not necessarily be representative of an exam.

Final evaluation: The final exam is a written exam. Only pen, paper, a non-programmable calculator and two A4 sheets (i.e., 4 pages) of self-chosen content are allowed (handwritten). For students from M.Sc. MSE / ESE and B.Sc. Math, this exam is graded. Students from the M.Sc. Math need to pass the written exam in order to take the graded 11ECTS oral exam. Unmentioned special cases: Everyone who wants ECTS for this course needs to pass the exam.

Projects: (more detail in a section below) The optional project (3 ECTS) consists in the formulation and implementation of a self-chosen optimization problem or numerical solution method, resulting in documented computer code, a project report, and a public presentation. Project work starts in the last third of the semester. For students from the faculty of engineering the project is graded independently from the 6ECTS lecture. For students from the B.Sc. Math, the grade for the lecture and project 9ECTS module is solely determined by the written exam. For students from the M.Sc. Math the project is again a prerequisite to the graded 11ECTS oral exam.

Calendar

Date Format Content Watch this Week Prepare Deadlines
17.10 Intro     one question  
24.10 Q&A up to including Example 4.2 Lec. 1, 2, 3 one question  
31.10 Ex Solution to Ex 1 Lec. 4, 5, 6 one question  
7.11 Q&A up to including Chap. 8.1 Lec. 7, 8 one question Ex 1 (voluntary)
14.11 Ex Solution to Ex 2 Lec. 9, 10 one question  
21.11 Q&A up to including Chap. 10.3 Lec. 11, 12 one question Ex 2 (voluntary)
28.11 Ex Solution to Ex 3 Lec. 13, 14 one question  
5.12 Q&A up to including Chap. 13.5 Lec. 15, 16 one question Ex 3 (voluntary)
12.12 Q&A up to including Chap. 14.1 Lec. 17, 18 one question midterm quiz 
19.12 Ex Solution to Ex 4 Lec. 19, 20 one question  
26.12 ** *** Christmas Break *** *** *** ***
9.01 ** *** Christmas Break *** *** *** ***
16.01 Q&A proj, up to incl. Chap 18.1 Lec. 21, 22 one question project commitments 
23.01 Ex Solution to Ex 5, Project b. Lec. 23, 24 one question Ex 4 (voluntary)
30.01 Ex Project brainstorming   project quest. Ex 5 (voluntary)
6.02 Q&A/Project All course content; proj     project presentation
21.02 none no session - just a deadline     project report deadline

 

 

Manuscript

The lectures are closely following a course manuscript draft.

Numerical optimization (draft manuscript) by M. Diehl

Lectures

The video recordings correspond each to approximately 90 minutes, and comprise 24 lectures in total. A recommended schedule for watching can be found in the calendar above.

Recording of intro session

 Lecture  Content
 Lecture 1  Introduction to Section 1.3 (Mathematical formulation)
 Lecture 2  Section 1.4 (Definitions) to 2.7 (Mixed-Integer-Programming)
 Lecture 3  Section 3.1 (How to check convexity) to 3.5 (Standard form of convex opt. problems)
 Lecture 4  Section 3.6 (Semidefinite Programming) to Example 4.2 (Dual of LP)
 Lecture 5  Example 4.3 (Dual decomposition) to Chapter 6 introduction
 Lecture 6  Section 6.1 (Linear Least Squares) to 6.5 (L1-Estimation)
 Lecture 7  Section 6.6 (Gauss-Newton method) to 7.2 (Local convergence rates)
 Lecture 8  Section 7.3 (Newton-Type methods) to 8.1 (Local contraction)
 Lecture 9  Section 8.2 (Affine invariance) to 9.1 (Line search)
 Lecture 10  Section 9.2 (Wolfe conditions) to 9.3 (Global convergence of line search)
 Lecture 11  Section 9.4 (Trust-Region methods) to 9.5 (The Cauchi-Point)
 Lecture 12  Section 10.1 (Algorithmic Differentiation) to 10.3 (Backward AD)
 Lecture 13  Section 10.4 to Chapter 11 introduction
 Lecture 14  Section 11.1 (LICQ and linearized feasible cone) to 11.2 (SONC)
 Lecture 15  Section 12.1 (Optimality conditions) to 12.5 (Constrained Gauss-Newton)
 Lecture 16  Section 11.3 (Perturbation analysis) and 12.7 (Local convergence)
 Lecture 17  Section 12.6 (General constrained NT-Algorithm) to 12.9 (Careful BFGS updating)
 Lecture 18  Section 13.1 to 13.2 (Active constraints and LICQ)
 Lecture 19  Section 13.3 (Convex Problems)
 Lecture 20  Section 13.4 (Complementarity) to 14.1 (QPs via Active Set Method)
 Lecture 21  Section 14.2 (SQP) to 14.4 (Interior Point methods)
 Lecture 22  Section 14.4 (Barrier problem interpretation, SCP) to 15.5 (Simultaneous optimal control)
 Lecture 23  Problem reformulations and useful function approximations
 Lecture 24  Summary of the course

 

Exercises

The exercises are based partially on pen and paper and partially on (Matlab or Python) and CasADi (see below).

 

 Sheet (pdf)
 Material (code) Solution (video)  Solution (material)
Exercise 1 - Introduction to CasADi, Convex Optimization ex1 ex1_sol ex1_sol
Exercise 2 - Duality and Fitting Problems N/A ex2_sol ex2_sol
Exercise 3 - Unconstrained Newton-type Optimization, Globalization ex3 - -
Exercise 4 - Calculation of Derivatives, Equality Constrained Optimization - - -
 Exercise 5 - Inequality Constrained Optimization - - -

If you find typos or mistakes in the exercises, please report them to armin.nurkanovic@imtek.uni-freiburg.de.

Further Material

Project

You can find the project guidelines here.

 

Software

The exercises lean heavily on the open source tool CasADi, which offers an interface to Python, Matlab, and Octave. The computer exercise templates as well as the code solutions will be published in Matlab and Python and we offer support for both. The solution videos however are based on the Matlab version.

Python is one of the major programming languages and via libraries such as NumPy and SciPy a common choice for scientific computing. Apart from CasADi, we will use the libraries NumPy, SciPy and Matplotlib. If you are completly new to Python, you may want to check out the Anaconda distribution.

Matlab is an environment for numerical computing based on a proprietary language that allows one to easily manipulate matrices and visualize data. The University of Freiburg offers a free-of-cost license to students and staff which can be obtained following the instructions here.

CasADi is a symbolic framework for algorithmic differentiation and numerical optimization. In order to install CasADi, follow the instructions here.
Matlab: Download the binaries for your platform and, after having extracted them, add their location to MATLAB's path. To test your installation run the simple example described at the provided link. If successful, save the path by executing the command savepath. In this way, the location of the binaries will be known even after restarting MATLAB.
Python: If you are using pip, you can simply pip install casadi in your preferred environmentIf you are using Anaconda / conda for managing your environments, we suggest to first conda install pip inside a conda environment, followed by pip install casadi.