Hauptnavigation

Numerical Optimization

Veranstaltung Wochentag Termin Ort
042527 (Übung: 042528) Montag (Übung: Mittwoch) 10.15 - 12.00 Otto-Hahn-Str. 12 - Raum 1.056,
Campus Nord

Lecture Information

  • Module description: pdf
  • Language: English
  • Lecturer: Dr. Sangkyun Lee
  • Attendance to Übung is REQUIRED.
  • Office Hour (lecturer): Thursday 13:00-14:00, LS8, OH 12, Raum 4.023 (or by appointments)

Exams:

The schedule is quite tight due to my relocation in Feb 2017. We'll consider a way to compensate the tight schedule (to be discussed in the class)

  • Midterm: 19.12.2016 (Mon) 21.12.2016 (Wed) in-class : MIN, AVG, MAX = 26, 38.25, 49
  • Final exam: 16.02.2017 (Thurs 10:15-13:00 OH12 R1.056) : MIN, AVG, MAX = 22, 40.9, 47.5
Registration form: link


Content:

In this lecture we will learn theories and algorithms of numerical optimization. We study the mathematical structure of various optimization problems to design efficient algorithms. The structure is investigated by accessing the zero-th order (function values), the first order (derivatives), and the second order information (Hessians) about the objective function, as well as by looking into the geometry of constraints. We discuss constrained and unconstrained optimization problems in continuous spaces, focusing on understanding motivations behind technical details and analyzing convergence rate / algorithm complexity algorithms. Fundamental concepts such as optimality and duality will be discussed in detail, which also become popular tools to better understand algorithms in many areas including machine learning, data mining, and statistics. The importance of smoothness and convexity will be elaborated, especially in connection to regularization problems in high dimensions. Some advanced topics from non-smooth, large-scale, or matrix optimization will be included if time permits. Homework assignments will be given to check theoretical and practical understanding of techniques. Some assignments would involve programming in the Julia language. Tutorials about the language will be given in Ubung for newbies.


Aims:

The aim of this lecture is to provide students with understanding of fundamental concepts and techniques in optimization in an advanced level, so that students can understand and see how to use and design efficient numerical optimization algorithms for their own research problems.


References:

  • Numerical Optimization, J. Nocedal and S. Wright, 2nd Ed, Springer, 2006
  • Introductory Lectures on Convex Optimization, Y. Nesterov, Springer, 2004
  • Nonlinear Programming, D. P. Bertsekas, 2nd Ed., Athena Scientific, 2003 (2nd printing)
  • Convex Optimization, S. Boyd and L. Vandenberghe, Cambridge, 2004 [pdf]

Lecture Notes:

The lecture notes will be updated: check before each lecture. Questions / correcting errors will be welcomed. See the calendar below for lecture topics and schedule.
  • Lecture notes (incrementally updated): [pdf]
  • (17.10) Lecture 0: Introduction
  • > (optional reading) Intro to compressed sensing pdf
  • For other lectures, see the schedule on the calendar below
  • (12.12) Stochastic gradient descent link
  • (09.01) Proximal gradient descent link
  • (01.02) ADMM link
  • (06.02) Duality link

Ubung:


Student Presenation

Each student can give a presentation (30-45min) about the following papers or some features of Julia.
  • [10] Julia topics:
    Advanced language features, debugging, parallelization, GPU computing, or even plotting data. Some interesting topics can be found from JuliaCon 2016 videos.
    Each Julia talk will be graded for up to 10 points



Homeworks:

  • A homework will be given approx. every two weeks. Some will require implementing algorithms in Julia.
  • Exercise questions are at the end of each chapter of the lecture notes.
  • Homeworks will NOT be graded: you don't need to submit your homeworks
  • You need to present at least 2 correction solutions at homework discussions, in total: this is REQUIRED for passing Ubung and being qualified for the final exam. I will ask volunteers at each discussion session, but you can tell me beforehand what you want to present
  • Dicussion of homework questions with other students is strongly encouraged. You can ask for help to other students if you have difficulties.
> Homework 1 (due 9.11, NOT 2.11): exercises 1.4, 2.1(a), 2.2, and 2.3. And solve the Sudoku problem using JuMP (my Sudoku solution)
> Homework 2 (due 23.11): exercises 3.1, 3.2, 4.1, 4.4, 4.5. In addition, 3.3 and 4.2 (since we've almost solved 3.1. I'll still ask for volunteers for 3.1. Updated 09.11) Some Julia solutions
> Homework 3 (due 14.12): exercises 5.2, 6,1, 6.2, 8.1, 8.2, 8.3 (MNIST data set: download)
> Homework 4 (due 18.1): ex 10.1, 10.2, 11.1, 11.2, 12.1
> Homework 5 (due 25.1): ex 12.2, 12.3, 12.4, 12.5 (lecture note is updated)
> Homework 6 (due 8.2): ex 12.4, 13.1, 14.1, 14.2, 14.3


Lecture Schedule:

The schedule may change, so please check often. Please ignore the lecture times on the calendar.