Numerical Optimal Control (online)

Lectures: Prof. Dr. Moritz Diehl,          Exercises: Florian Messerer 

The course’s aim is to give an introduction into numerical methods for the solution of optimal control problems in science and engineering. The focus is on both discrete time and continuous time optimal control in continuous state spaces. It is intended for a mixed audience of students from mathematics, engineering and computer science.

The course is intended for self-study and is based on three pillars:

  • a course manuscript
  • lecture recordings, and
  • exercises, that are accompanied with solutions and solution recordings.

Each of the three pillars is explained below. The recommended course duration is 10 weeks, with an overall workload of 10-20 hours per week. An example week of self-study could comprise e.g. 3 hours for reading the manuscript, 3 hours for watching two lectures, 4 hours for solving one exercise.

Contact: moritz.diehl@imtek.uni-freiburg.de, florian.messerer@imtek.uni-freiburg.de

(Note for students taking the exam this winter semester: the date is 24.3.21, 10am-12pm, see below for more detail)

Manuscript

The lectures are closely following a recent book draft that serves as course manuscript. This manuscript is the first of three pillars for self-study. 

 Numerical Optimal Control (draft manuscript) by S. Gros and M. Diehl

 

Lectures

The video recordings correspond each to approximately 90 minutes, and comprise 20 lectures in total. These recordings are the second pillar for self-study, and it is recommended to watch about two lectures per week.

 Topic  Chapters
 Lecture 1 - Welcome and introduction (not recorded, suggested: first 10 minutes of this talk) -
 Lecture 2 - Introduction (cont.) and Newton-type methods 1.2 - 2.1
 Lecture 3 - Newton-type methods (cont.) 2.2 - 2.5
 Lecture 4 - Nonlinear optimization 3 - 3.2
 Lecture 5 - Nonlinear optimization (cont) and Newton-type optimization algorithms 3.3 - 4.1
 Lecture 6 - SOSC (recall) and Newton-type optimization algorithms 3.3 - 4.2
 Lecture 7 - Newton-type optimization algorithms (Inequalities and globalization) 4.3 - 4.4
 Lecture 8 - Calculating derivatives 5
 Lecture 9 - Discrete time optimal control 7 - 7.3
 Lecture 10 - Discrete time optimal control: sparsity structure (cont.) 7.3
 Lecture 11 - Dynamic Programming 8 - 8.3
 Lecture 12 - Dynamic Programming (cont.) 8.3 - 8.8
 Lecture 13 - Differential Dynamic Programming -
 Lecture 14 - Continous time optimal control and numerical simulation 9 - 10.2
 Lecture 15 - Numerical simulation (cont.) 10.2 - 10.5
 Lecture 16 - Talk by Michael Neunert and Hamilton Jacobi Bellman Equation 11
 Lecture 17 - Pontryagin and the indirect approach 12
 Lecture 18 - Direct Approaches 13
 Lecture 19 - Model predictive control 15
 Lecture 20 - Parametric Nonlinear Optimization 16

 

Exercises

The exercises are based partially on pen and paper and partially on Matlab + CasADi (see below). They are the third pillar of the course, and it is recommended to do work on one exercise sheet per week.

 Sheet (pdf)  Material (code) Solution (video)  Solution (material)
 Exercise 1 - Initial value problems - sol ex1 ex1_sol.zip
 Exercise 2 - Nonlinear optimization and Newton-type methods ex2.zip sol ex2 ex2_sol.zip
 Exercise 3 - Equality constrained optimization ex3.zip sol ex3 ex3_sol.zip
 Exercise 4 - Inequality constrained optimization ex4.zip sol ex4 ex4_sol.zip
 Exercise 5 - Algorithmic differentiation - sol ex5 ex5_sol.zip
 Exercise 6 - Optimal control formulations ex6.zip sol ex6 ex6_sol.zip
 Exercise 7 - Dynamic Programming ex7.zip sol ex7 ex7_sol.zip
 Exericse 8 - Continous time optimal control - sol ex8 ex8_sol.pdf
 Exercise 9 - Pontryagin's minimum principle  ex9.zip sol ex9 ex9_sol.zip
 Exercise 10 - Model predictive control  - - ex10_sol.zip

 

CasADi installation

CasADi is a symbolic framework for algorithmic differentiation and numerical optimization. In order to install CasADi, follow the instructions here. 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.

Further Material



Summer semester 2020

The content below is only relevant for students who followed the course in the summer semester 2020.

Structure of the course

The course is organized as an online lecture and we provide recordings of the lecture and of the exercise solutions. Nonetheless we will meet once a week. 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 Florian Messerer.

Virtual meetings: We will meet every Friday in a virtual lecture room. These meetings are alternatingly dedicated to either Q&A sessions with Prof. Diehl or exercise sessions with the teaching assistant (see below). We will use Zoom for the meetings. Please note that you can join the meeting via your browser and do not need to install to the Zoom client. Except for the kick-off session, none of the meetings will be recorded. For more information on how the university uses Zoom, a guide for students, and a note on data protection please see here (sorry, so far this page seems to exist in german only. Please let us know if you have any questions regarding the content).

Lecture recordings: The lecture recordings were already created in a past semester. There are 20 lectures of approximately 90 minutes each, which amounts to a lecture load of about 2 lectures or 3 hours per week. You can find a recommended schedule for watching them as well as the links in the calender below.

Course manuscript: The lectures are accompanied by a detailed course manuscript, which you may find in the materials section below. Please note that it is in general more detailed than the lectures and that we skip some of the chapters. Around 2 weeks after the start of the semester we will provide printed copies (for free).

Exercises: The exercises are mainly computer based. Computers with MATLAB and CasADi installed are required to solve them (see below for details). There will be a total of 10 exercises. They will be published throughout the semester, after some time delay followed by a solution manuscript as well as a video recording. The exercises are voluntary (though of course we strongly recommended 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.

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 not be used to show the solutions, but to discuss 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 participance.

Forum: On 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. You can join via this link.

Final evaluation: The final exam is a written closed book exam. Only pencil, paper, a calculator and two A4 sheets (i.e., 4 pages) of self-chosen content are allowed (handwritten). For students from the faculty of engineering and the 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.

Projects: The optional project (3 ECTS) consists in the formulation and implementation of a self-chosen problem of Numerical Optimal Control, resulting in documented computer code, a project report, and a public presentation. Project work starts in the last third of the semester. Checkout the project guidelines below for more detail. 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&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

We will meet on the following fridays. All meetings are held virtually via Zoom (see above), but except for the kick-off meeting, none of the meetings will be recorded. For lecture 1, there is no recording. The chapters refer to the course manuscript from the material section below.

 Date  Time  Format  To prepare (watch)  To prepare (read)  Hand in
 15.5.  2pm  kick-off  first 10 minutes of this talk (section "embedded optimization")    
 22.5.  2pm  Q&A  lecture 2, lecture 3, lecture 4*  chap. 1 to 3.2  ex1 (voluntary)
 29.5.  2pm  exercise  solution ex1  ex1_sol.zip  
 05.6.  10am  Q&A  lecture 5, lecture 6lecture 7, lecture 8  chap. 3.3 to 5.4  ex2.pdf ex2.zip ex3.pdf ex3.zip (voluntary)
 12.6.  10am  exercise  solution ex2, ex3  ex2_sol.zip ex3_sol.zip  
 19.6.  10am  Q&A - (open air, if weather is nice)  lecture 9, lecture 10, lecture 11, lecture 12

 chap. 7 to 8.8 (skip 6)

 ex4.pdf, ex4.zip, ex5.pdf (voluntary)
 26.6.  10am  exercise  solution ex4, ex5  ex4_sol.zip ex5_sol.zip  
 03.7.  10am  Q&A  lecture 13, lecture 14, lecture 15, lecture 16  chap. 8.9 to 11  ex6.pdfex6.zipex7.pdf ex7.zip (voluntary)
 10.7.  10am  exercise  solution ex6, ex7  ex6_sol.zip ex7_sol.zip  
 17.7.  10am  Q&A / projects  lecture 17, lecture 18, lecture 19, lecture 20

 chap. 12 to 16 (skip 14&17)

 ex8.pdfex9.pdf ex9.zip (voluntary)
 24.7.  10am  exercise  solution ex8, ex9  ex8_sol.pdf ex9_sol.zip  
 31.7.  10am  Q&A / projects      ex10.pdf (voluntary)
 14.8.  10am  project pres  Project presentations  ex10_sol.zip  
 28.8.  11.59pm   ***  Deadline project report    project report

* The last 10 minutes of lecture 4 are mute

Material

  • Manuscript of Numerical Optimal Control by S. Gros and M. Diehl (Draft)
  • Biegler, L. T., Nonlinear Programming, SIAM, 2010
  • Betts, J., Practical Methods for Optimal Control and Estimation Using Nonlinear Programming, SIAM, 2010
  • Rawlings, J. B., Mayne D. Q., Diehl, M., Model Predictive Control, 2nd Edition, Nobhill Publishing, 2017 (free PDF here)
  • Sample exams
  • Lecture recordings (with content overview)
    • Lecture 1 - Introduction (Not recorded)
    • Lecture 2 - Chapter 1.2 Continuous time Systems to Chapter 2.1 Local Convergence Rates
    • Lecture 3 - Chapter 2.2 Local Contraction to Chapter 2.5 Globalization
    • Lecture 4 - Chapter 3 Nonlinear Optimization to Chapter 3.2 First Order Optimality Conditions 
    • --note: in Lecture 4 the microphone's battery died at the end of the lecture, so the last 10 minutes are mute.
    • Lecture 5 - Chapter 3.3 Second Order Optimality Conditions to Chapter 4.1 Equality Constraint Optimization
    • Lecture 6 - Chapter 3.3 Second Order Optimality Conditions (recall) to Chapter 4.2 Local Convergence of Newton-Type Methods 
    • Lecture 7 - Chapter 4.3 Inequality Constrained Optimization to Chapter 4.4 Globalisation Strategies
    • Lecture 8 - Chapter 5 Derivatives to Chapter 5.4 Algorithmic Differentiation Software
    • Lecture 9 - Chapter 7 Discrete Optimal Control to Chapter 7.3 Sparsity Structure
    • Lecture 10 - Chapter 7.3 Sparsity Structure
    • Lecture 11 - Chapter 8 Dynamic Programming to Chapter 8.3 Infinite Horizon Problems
    • Lecture 12 - Chapter 8.3 Infinite Horizon Problems to Chapter 8.8 A Discrete Time Minimum Principle
    • Lecture 13 - Chapter 8.9 Differential Dynamic Programming
    • Lecture 14 - Chapter 9 Continuous Time Optimal Control to Chapter 10.2 Implicit Integration
    • Lecture 15 - Chapter 10.2 Implicit Integration  to end Chapter 10
    • Lecture 16 - Talk by Michael Neunert and Chapter 11 Hamilton Jacobi Bellman Equation
    • Lecture 17 - Chapter 12 Pontryagin and the Indirect Approach
    • Lecture 18 - Chapter 13 Direct Approaches
    • Lecture 19 - Chapter 15 Model Predictive Control
    • Lecture 20 - Chapter 16 Parametric Nonlinear Optimization

 

Project

The project guidelines can be found here. We will dedicate some parts of later Q&A sessions to project work (voluntary, though strongly recommended). The aim on July 17th will be to finalize your project ideas into concrete projects (though you are welcome to work ahead and contact us already earlier). On July 31st the focus are the challenges you encounter along the way of solving your project. Be prepared to give short, informal presentations of your project idea and current state of progress.

Matlab and CasADi installation

MATLAB is an environment for numerical computing based on a proprietary language that allows one to easily manipulate matrices and visualize data which will be very helpful in prototyping the algorithms presented during the lectures of this course. The University of Freiburg offers a free-of-cost license to students and staff which can be obtained following the instructions here. In order to be able to complete the exercises of this course, you will need a working installation of MATLAB. Follow the instructions at the provided link in order to install the software package.
 
CasADi is a symbolic framework for algorithmic differentiation and numerical optimization. In order to install CasADi, follow the instructions here. 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.