Numerical Optimization

Prof. Dr. Moritz Diehl - moritz.diehl@imtek.uni-freiburg.de

The course’s aim is to give an introduction into numerical methods for the solution of optimization problems in science and engineering. It is intended for students from two faculties, mathematics and physics on the one hand, and engineering and computer science on the other hand. The focus is on continuous nonlinear optimization in finite dimensions, covering both convex and nonconvex problems. The lecture is divided into four major parts:

  1. Fundamental Concepts of Optimization: Definitions, Types of Optimization Problems, Convexity, Duality.
     
  2. Unconstrained Optimization and Newton Type Algorithms: Stability of Solutions, Gradient and Conjugate Gradient, Exact Newton, Quasi-Newton, BFGS and Limited Memory BFGS, and Gauss-Newton, Line Search and Trust Region Methods, Algorithmic Differentiation.
     
  3. Equality Constrained Optimization Algorithms: Newton Lagrange and Generalized Gauss-Newton, Range and Null Space Methods, Quasi-Newton and Adjoint Based Inexact Newton Methods.
     
  4. Inequality Constrained Optimization Algorithms: Karush-Kuhn-Tucker Conditions, Linear and Quadratic Programming, Active Set Methods, Interior Point Methods, Sequential Quadratic and Convex Programming, Quadratic and Nonlinear Parametric Optimization.

The lecture (6 ECTS) is accompanied by intensive weekly computer exercises (based on MATLAB) and a project in the last third of the semester. The project (3 ECTS), which is obligatory for students of mathematics but optional for students of engineering, consists in the formulation and implementation of a self-chosen optimization problem and numerical solution method, resulting in documented computer code, a project report, and a public presentation.

Time and place

To equally benefit students from both faculties, the lectures are in the “Institutsviertel” while the exercises take place on “Campus Flugplatz”.

  • Lecture: Tuesdays 14:15 - 16:00 and Fridays 14:00 - 15:45 at Albertstrasse 23b, HS 2.
  • Exercises: Wednesdays 16:00 - 18:00 at Georges-Koehler-Allee 101, SR 01-016.

The first lecture is on Oct. 23 and the first exercise on Oct. 28, 2015. 

Announcements

  • There is no exercise session on Dec. 23, 2016.
  • First lecture after Christmas is on Jan. 8, 2016.
  • All subsequent Fridays (namely, 15.01, 22.01, 29.01, 5.02) are dedicated to project work.
  • For the dates above, a room is reserved for you at Georges-Koehler-Allee 101, SR 01-009/13.
  • On Jan. 13 and Jan 15, 2016, there will be no supervision for the project work (due to a team workshop).
  • Timetable for project presentations (12.02.2016) 
  • EXAM: 15.03.2016, 11:00, GKA 101, 010/14
  • A past exam can be found here.
  • Reminder from sheet 0:
    "The final exam is a closed book exam. Only pencil, paper, a calculator and four single A4 pages of self-chosen formulas are allowed."

Teaching assistants

  • Dimitris Kouzoupis - dimitris.kouzoupis@imtek.uni-freiburg.de 
  • Andrea Zanelli - andrea.zanelli@imtek.uni-freiburg.de

Office hours: Wednesdays 14:00 - 16:00 at Georges-Koehler-Allee 102, 01-211.

Homework policy

Each Friday a new exercise sheet is distributed and some hints may be given. Students can then prepare themselves for the exercise session, where they can complete the tasks in teams of 1 to 4 people and show the results to the teaching assistant. Groups that require more time or cannot make it to the exercise session may send their solutions by email to the teaching assistant until the upcoming Friday at 12:00. Groups that complete the tasks during the exercise session do not need to send a report by email. 

Assignments

Please fill in your data (if missing) and form groups for the exercises using this sheet. Groups for the exercises are allowed to change during the semester.

Exercise 0: General Information

Exercise 1: Introduction to YALMIP

Exercise 2: Convex Optimization

Exercise 3: Duality Theory and Semidefinite Programming

Exercise 4: Estimation and Fitting Problems

Exercise 5: Unconstrained Newton-type Optimization

Exercise 6: Newton Type Optimization and Globalization Strategies

Exercise 7: Calculation of Derivatives

Exercise 8: Equality Constrained Optimization

Exercise 9: Christmas Sheet 

Exercise 10: Inequality Constrained Optimization

Recordings

We try our best to upload the recordings from the lecture the soonest possible after they take place. However, the workflow is still under development so there can be some delays the first weeks. Please visit the whole series here, or use the direct-links below.
Note: Please use the links in the Download column.

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

 

Literature

  1. Jorge Nocedal and Stephen J. Wright, Numerical Optimization, Springer, 2006.
  2. Amir Beck, Introduction to Nonlinear Optimization, MOS-SIAM Optimization, 2014.
  3. Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge Univ. Press, 2004.
  4. Moritz Diehl, Lecture Notes on Numerical Optimization, Leuven-Freiburg 2007-2015 (last update: 02.02.2016).