Hauptnavigation

Numerical Optimization

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

Lecture Information

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

Content:

In this lecture we will learn theories and algorithms of numerical optimization. We study the mathematical structure of typical optimization problems, in order to design efficient and advanced algorithms. Such structure is investigated by accessing the zero-th order (function values), the first order (derivatives), and the second order information (Hessians) about objective functions, as well as by looking into the geometry of constraints. We will discuss constrained and unconstrained optimization problems in continuous spaces, focusing on understanding motivations behind technical details, analyzing convergence rate / algorithm complexity, and applying algorithms. Fundamental concepts such as optimality and duality will be discussed in details, which become popular tools for analysis 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.


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, 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:

This is a tentative schedule, and may subject to change. If you have any question or find any bug, please don't hesitate to contact Dr. Lee.
  • (07.04) Lecture 1: Introduction (+Syllabus) [pdf]
  • (09.04) Lecture 2: Elements of Analysis and Topology [pdf] (figure updated 29.04)
    > A demo: image denoising/deblurring problem [paper] [code] (reading is not required)
  • (14.04) Lecture 3: Elements of Topology / Continuity and Differentiation [pdf] (updated 29.04)
  • (16.04) R Tutorial (see information below) [pdf]
  • (23.04) Lecture 4: Types of solutions and local models [pdf] (pdf updated 27.04)
  • (28.04) Lecture 5: Optimality conditions and spectral properties of the Hessian [pdf] (updated 08.05)
    > 3D contour plots of quadratic functions [R code]
  • (05.05) Lecture 6: Optimality conditions for convex functions / Existence of Solutions [pdf]
  • (07.05) Lecture 7: Line search with steepest descent and Newton directions (1) [pdf] (updated 19.05)
  • (19.05) Lecture 8: Line search with steepest descent and Newton directions (2) (continuing lecture-07.pdf)
  • (21.05) Lecture 9: Global convergence of line search / convergence rate of steepest descent/Newton's method [pdf] (updated 02.06)
  • (28.05) Quiz 1 discussion
  • (02.06) Lecture 10: Newton's Method with Hessian Modification / Quasi-Newton Methods [pdf] (updated 04.06)
  • (04.06) Lecture 11: Continuity of eigenvalues, Woodbury formula, conjugate gradient method [pdf] (updated 17.06)
  • (16.06) Lecture 12: Conjugate gradient method (Cont') [pdf]
  • (18.06) Lecture 13: Conjugate gradient method (Cont') [pdf]
  • (23.06) Lecture 14: Nonlinear CG / Constrained Optimization [pdf] (updated 07.07)
  • (25.06) Lecture 15: Constrained Optimization: Optimality Conditions [pdf] (updated 07.07)
  • (30.07) Lecture 16: Constrained Optimization: Optimality Conditions (cont') (continuing lecture-15.pdf)
  • (02.07) Lecture 17: Constrained Optimization: KKT Conditions [pdf]
  • (07.07) Lecture 18: Constrained Optimization: Second order / sufficient conditions [pdf] (updated 09.07)
  • (09.07) Lecture 19: Constrained Optimization: Duality [pdf] (updated 09.07)
  • (14.07) Lecture 20: Constrained Optimization Algorithms [pdf]
  • (16.07) Quiz 2

Homeworks:

A homework will be given approx. every two weeks. Some will require implementing algorithms in R.
  • Homework 1 (due 28.04) : you don't have to solve problem #6 for 28.14 submission.
  • Homework 2 (due 14.05) : In #5, x \neq 0 was missing and now added.
  • Homework 3 (due 11.06) : pdf updated 28.05, fixing typos.
    > R code for Rosenbrock function (and other helper functions) [code] (right-click the link and use save as...)
  • Homework 4 (due 02.07)
    > R code for a high dim function [code] (right-click the link and use save as...)
    > R code for helper functions [code] (right-click the link and use save as...)
  • Homework 5 (due 14.07)

R Tutorial (16.04):

Martin will give an introduction to the R language, focusing on how to write functions and linear algebraic operations (matrix x vector, etc.) We only require R coding for some homework questions intended for checking the understanding of algorithms and methods, so only basic features of R will be required. Please bring your laptop if possible on 16.04 .

Lecture Schedule:

The schedule may change, so please check often.
No lecture due to business trips: 12.05, 14.05