MS-E2148 - Dynamic Optimization D, 13.01.2021-25.02.2021
This course space end date is set to 25.02.2021 Search Courses: MS-E2148
Topic outline
-
If you are attending the online exam on Thu 15.4 @ 15:00 to Fri 16.4 @ 15:00, see Section Online exam for further instructions.
Please note that this course is a self-study course in spring 2021. Our main communication channel is Slack, e.g., in the discussion between teachers and participants concerning homework assignments.
Why this course?
This course examines dynamic optimization models; i.e. models that are defined over continuous time, multiple stages, etc. They capture many relevant real-life problems: scheduling, route planning, solving optimal strategies for games, inventory control, investment problems, machine repair, text processing, dna sequence matching, stopping problems, airplane/rocket flight path optimization, minimum time/effort problems, optimal fishery management, saving/consumption optimization, optimal feedback controllers for plants and regulator problems and so on.
The models that are examined are:
- Optimal control problem. The task is to find a control function that is admissible, i.e. satisfies some control constraints, that minimizes a given cost function, subject to (usually first-order) differential equation constraints.
- Calculus of variations problem. Find twice continuously differentiable function with given boundary conditions that minimizes an integral functional over a fixed time horizon. The famous example is the Brachistochrone problem, where we seek shortest time curve, or curve of fastest descent, for a ball to slide down under uniform gravitational field. The problem was posed by Johann Bernoulli in 1696, and solved soon after that by Newton.
- Dynamic Programming (DP) problem. Here the problem is formulated in a form that can be solved numerically using the recursive backward (or forward) dynamic programming algorithm. We will study dynamic, both deterministic and stochastic optimization problems in detail, and derive various DP algorithms for solving them.
Course details
The course consists of 9 lectures, and 10 exercises with 2 homework assignments per each exercise. For a more detailed guide on how to complete the course see Guide to self-study.
Lecturer: Harri Ehtamo
Assistant: Anton von Schantz
Teaching: Self-study
Assessment methods: Exam, homework assignments, and participation in the Slack discussion forum
Grading scale: 0-5
Study material: Lecture slides and exercises are based on the material in the following books.
- D. E. Kirk: Optimal Control Theory. Prentice Hall, 1970 (2004).
- D. P. Bertsekas: Dynamic Programming and Optimal Control, vol 1 (and vol 2). Athena Scientific, 1995.
- M. L. Kamien and N. L. Schwartz: Dynamic Optimization - The calculus of variations and optimal control in economics and management, 2nd edition. North Holland, 1991.
The course books can be found as pdf versions with a Google search. It is not necessary to read the books, but they can provide additional material for those who are interested. For example, they contain more problems and solutions.
Language of instruction: English
Prerequisites: 1st and 2nd years math, recommended MS-C2105 Introduction to Optimization (or equivalent)
- Optimal control problem. The task is to find a control function that is admissible, i.e. satisfies some control constraints, that minimizes a given cost function, subject to (usually first-order) differential equation constraints.
-
Completing the course
In spring 2021, the course is 100% self-study. So there is no contact teaching/Zoom teaching. However, the course has a Slack discussion forum, where students can discuss topics and homework assignments of the course. See the Slack discussion forum page for more details.There are 2 homework assignments per exercise, 4 per week, altogether 20 homework assignments. These are based on the lecture material in question and the corresponding solved exercise problems. See Assignments for practical information about submitting, deadlines, and grading of homework assignments.Weekly Schedule
The students can familiarize with the course topics in their own phase, but the teachers, lectures and exercises follow the following schedule:1. Introduction, calculus of variations, Euler equation (Week 2).2. Calculus of variations, transversality conditions (Week 2).3. Optimal control (Week 3).4. Pontryagin minimum principle, infinite time horizon in calculus of variations (Week 3).5. Minimum time and control-effort problems (Week 4).6. Dynamic Programming (DP), discrete time/state problems (Week 4).7. DP applications (Week 5).8. Continuous time problem, HJB equation (Week 6).9. Discounted problems, numerical methods (Week 6).Learning goals
After the course, the student should have learned the following things:- Solving continuous time problems using calculus of variations, including different end point conditions. Lectures 1-2 (Kirk Section 4).
- Solving optimal control problems, including different end point conditions, and minimum principle. Lectures 3-5 (Kirk Section 5).
- Solving infinite horizon problems. Lecture 4 (Bertsekas Vol 2, Section 1).
- Solving discrete time/state problems using DP algorithm, including stochastic problems. Lectures 6-7 (Bertsekas Vol 1, Sections 1-5).
- Solve continuous time problems using Hamilton-Jacobi-Bellman equation. Lecture 8 (Kirk Section 3.11).
- Discounted problems and numerical methods, e.g. value- and policy iterations. Lecture 9 (Bertsekas Vol 1 Section 7).
- Learning definitions for relevant concepts and terminology used in the course. These definitions are often asked in course exams.
Exam
See Online exam for practical details about the exam.Grading
30 points from exam + a maximum of 12 extra points. A maximum of 12 extra points can be obtained from homework (12 points) and activity on Slack discussion forum (6 points). For example, 6 points from homework and 6 from activity, or 12 points from homework, and 0 from activity, and so on.
Grade/lower grade limit in points:
5/27; 4/24; 3/21; 2/18; 1/12
The extra points do not help in passing the course. To pass the course one must get at least 12 points in the exam.
- Solving continuous time problems using calculus of variations, including different end point conditions. Lectures 1-2 (Kirk Section 4).
-
At the start of the course, all course participants will be sent an invitation to the Slack discussion forum.
The primary communication channel in this course is Slack. Slack can be used to discuss the exercises, but keep the discussion sensible and avoid posting full solutions. For active participation in Slack, for example trying to answer other students questions or posting your own, you can be awarded up to 6 exam points (the earned points are based on the teachers' subjective evaluation of students' activity). For the teaching assistant to be able to estimate your activity, when you join the channel, change the display name to your full name (please refer to this guide).All communication should be done using the channels available in Slack. If you have any questions regarding the exercises, the course or need help with anything else, please post your question to one of the channels and the teaching assistant will try and help you. Please don’t send personal messages to the teaching assistant on Slack, rather make them public, this way someone else can also benefit from the answer to a question that you have posted. -
The lecture slides may be updated as the course goes on.
-
The exercises may be updated as the course goes on.
The deadline for returning homework assignments (two exercises per week, and two homework assignments per exercise) are:
Exercises 1&2: Wednesday 20.1.2021 @ 14:00
Exercises 3&4: Wednesday 27.1.2021 @ 14:00
Exercises 5&6: Wednesday 3.2.2021 @ 14:00
Exercises 7&8: Wednesday 10.2.2021 @ 14:00
Exercises 9&10: Wednesday 17.2.2021 @ 14:00
Return your homework assignment to its associated submission box on the bottom of this page. Whenever possible, return your solutions as a single pdf-file (you can merge files, for example, with https://www.sodapdf.com/pdf-merge/). Remember to also provide your student number and name.
Each homework assignment is graded 0-2. In the end of the course, the homework points will be scaled up to 12 exam points.
In addition to the homework assignments, there are self-study problems for which the solutions are handed for the student to familiarize with the topics.
-
- The exam is organized as an online exam starting on Thursday 15.4.2021 at 15:00 and ending on Friday 16.4.2021 at 15:00. So, you have 24 hours to complete the exam. This is the second, and the last exam organized in 2021.
- The exam papers and submission boxes will become available on this page once the exam starts. The submission box will close when the exam ends.
- The exam contains 5 problems (each worth 6 points). The problems are similar to those in exercise sessions and there will be also short essay questions related to lecture material.
- You can use tools like Google search, course material, Mathematica, etc. to solve the problems. Please provide just your code in your solution. It goes without saying, that cooperation between students is forbidden (e.g., in the Slack discussion group or offline).
- Only clearly handwritten or LaTeX-compiled solutions are accepted. Return your solutions are a single pdf, jpg, or png file.
- For any concerns, contact the assistant either in Slack or by email (anton.von.schantz[at]aalto.fi).
- The exam is organized as an online exam starting on Thursday 15.4.2021 at 15:00 and ending on Friday 16.4.2021 at 15:00. So, you have 24 hours to complete the exam. This is the second, and the last exam organized in 2021.
-