Numerical Optimization Lecture Notes

[Clara Zellinger]

Ideallyit should take advantage of linear algebra and analysis whenever necessary and provide a lot of intuitions because I will primarily be reading on my own. The proofs are secondary, but I will be interested in reading constructive proof that facilitates understanding.

I highly recommend the lecture notes from EE236 by Vandenberghe at UCLA. There are three courses (A, B, and C) and there's a corresponding textbook (Convex Optimization by Boyd and Vandenberghe, which is free online).

I recommend the two recent books by Amir Beck: (1) Introduction to Nonlinear Optimization and (2) First-order methods in Optimization, SIAM. The other books are fine, but I personally enjoy the clarity and level of details in Beck's books more.

Each of the three pillars is explained below. The recommended course duration is 12 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 exercises.

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

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 half an exercise sheet per week.

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.

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 Florian Messerer.

Virtual meetings: We will meet every Friday, 2.15pm to 4.00pm, 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. You can join via this link (Meeting ID: 858 1034 4638). The password is nUQtQw09? . Except for the kick-off session, none of the meetings will be recorded (edit: we decided to also not record the kick-off session, but you can find all relevant information on this page). For more information on how the university uses Zoom, a guide for students, and a note on data protection please see here.

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). You can join the Ilias course via this link.

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.

Exercises: The exercises are mainly computer based. Computers with MATLAB 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 florian....@imtek.de.

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.

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 Dec 18, 11.59pm, 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 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: (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&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.

There is a time slot separate from the normal sessions for discussing the projects. Starting on Jan 21st, we will meet each Thursday, 10am-12pm. At that point, you need to have sent your project idea via email (see guidelines), and registered for the SL/PL as required by your examination office (deadline depending on your examination office). The first session will be used to finalize your project ideas, and the following sessions to discuss your progress and the problems you face. The final presentations will be on March 08, and the deadline for the written project is March 18, 23:59.

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.

This is a set of lecture notes for MATH 555, Penn State's graduate Numerical Optimization course. Numerical Optimization is the study of maximizing or minimizing functions through numerical techniques. Generally, it's rare to optimize anything other than through numerical techniques (unless of course you're talking about something really simple). Numerical optimization is used every day and is built on techniques from multi-variable calculus, optimization theory (obviously) numerical linear algebra (for algorithm efficiency) and other branches of mathematics.

The lecture notes are loosely based on Nocedal and Wright's book Numerical Optimization, Avriel's text on Nonlinear Optimization, Bazaraa, Sherali and Shetty's book on Non-linear Programming, Bazaraa, Jarvis and Sherali's book on Linear Programming and several other books. All of the books mentioned are good books (some great). The problem is, some books don't cover things in enough depth. The other problem is for students taking this course, this may be the first time they're seeing optimization, so we have to cover some preliminaries. This set of notes correct some of the problems I mention by presenting the material in a format for that can be used easily in Penn State in MATH 555. These notes are probably really inappropriate if you have a strong Operations Research program. You'd be better off reading Nocedal and Wright's book directly.

I am a Research Professor at the Applied Research Laboratory (ARL) at Penn State. In the broadest possible sense, my work is in applied math. Some of my work is on applied statistics on (real-world) dynamical systems.

3a8082e126