Home
Uni-Logo
 

Convex Analysis and Optimization

Dr. Peter Ochs

Many problems in image processing, computer vision, and machine learning can be formulated as convex optimization problems and can be solved efficiently. The development of fast optimization algorithms relies on the knowledge of convex analysis. In this lecture, the basics of convex analysis are introduced, where we will attach importance to the geometric interpretation. Moreover, the connection between theory and applications will be explored in programming exercises from image processing and machine learning.

This mathematical lecture introduces the basic terminology and tools from convex analysis, such as convex functions/sets, relation between sets and functions, the Projection Theorem, Moreau envelope and proximal mapping, the subdifferential and optimality conditions of (nonsmooth) convex functions, and some basic duality theory. This first part of the lecture is complemented with some simple algorithms. The focus of the second part is efficient convex optimization algorithms and their complexity estimates.


Lecture:
(2 SWS)
Monday, 14-16,
Room: SR 02-017, Building 052

Exercises:
(2 SWS)

Wednesday, 12-14,
Room: SR 02-017, Building 052
Contact persons: Peter Ochs, Mohammadreza Zolfaghari
Beginning: Monday, October 17, 2016

ECTS Credits: 6
Recommended semester:   1 - 3 (Master)
Requirements: Fundamental mathematical knowledge.
Language and exam: The lectures are given in English. The exam will be an oral exam.

Convex Optimization

News:

26.10.2016:First version of the lecture notes is online. (See below.)
31.10.2016:Tutorials on Wednesdays are cancelled. For feedback on the exercises, please come to the office of Peter Ochs or Mohammadreza Zolfaghari. Extra tutorial sessions will be announced here. Please check this web page from time to time.
31.10.2016:Peter Ochs is away from 14.11. to 18.11. The lecture on 14.11.2016 is postponed to the tutorial on 23.11.2016.
09.01.2017:There is no lecture on 06.02.2017.
30.01.2017:The date for the oral exam is: 23.03.2017.
07.03.2017:Schedule for the oral exam on 23.03.2017 in room 01-020, building 052:

10:30-11:00: Baumgärtner Katrin
11:00-11:30: Striet Ludwig
11:30-12:00: Bhatt Aditya

Note: By default, the exam will be in English. In case you prefer German, please contact Peter Ochs.


Slides:

Class 0 (17.10.): Introduction and basic concepts of complexity
Class 1 (24.10.): Lipschitz continuity and the Gradient Descent Method
Class 2 (31.10.): Terminology of Variational Analysis
Class 3 (7.11.): Convex sets and the Projection Theorem
Class 4 (21.11.): Convex functions
Class 5 (23.11.): Moreau envelope and Proximal Mapping
Class 6 (28.11.): Moreau envelope and Proximal Mapping II
Class 7 (5.12.): The subdifferential and Fermat's rule
Class 8 (12.12.): Lower complexity bounds
Class 9 (19.12.): The Gradient Method for smooth convex optimization
Class 10 (9.1.): Nonsmooth convex optimization
Class 11 (16.1.): Geometric introduction to duality
Class 12 (23.1.): Applications of convex duality
Class 13 (30.1.): Summary
Class 14 (6.2.): cancelled

Download Lecture Notes (Version 23.01.2017).

Exercise material:

Theoretical and practical exercises (in Matlab).
Exercise material will appear here.

Exercise 0 (19.10.)
Exercise 1 (26.10.)
Exercise 2 (02.11.)
Exercise 3 (09.11.)
Exercise 4 (21.11.)
Exercise 5 (23.11.)
Exercise 6 (30.11.)
Exercise 7 (07.12.)
Exercise 8 (14.12.): same as Exercise 7
Exercise 9 (21.12.): catch up with all previous exercises
Exercise 10 (11.01.)
Exercise 11 (18.01.)
Exercise 12 (25.01.): catch up with all previous exercises
Exercise 13 (01.02.): catch up with all previous exercises
Exercise 14 (08.02.) cancelled


References:

There is no specific book that covers the complete content of this class.

  • T. Rockafellar: Convex Analysis. Princeton University Press, 1970.
  • Y. Nesterov: Introductory Lectures on Convex Optimization - A Basic Course. Kluwer Academic Publishers, 2004.
  • D. P. Bertsekas: Convex Analysis and Optimization. Athena Scientific, 2003.
  • S. Boyd: Convex Optimization. Cambridge Univeristy Press, 2004.
  • H. H. Bauschke and P. L. Combettes: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, 2011.
  • Further references will be given during the lecture.