TEACHING

GENERAL INFORMATION

Convex optimization problems arise quite naturally in many application areas like signal processing, machine learning, image processing, communication and networks and finance etc.

The course will give an introduction into convex analysis, the theory of convex optimization such as duality theory, algorithms for solving convex optimization problems such as interior point methods but also the basic methods in general nonlinear unconstrained minimization, and recent first-order methods in non-smooth convex optimization. We will also cover related non-convex problems such as d.c. (difference of convex) programming, biconvex optimization problems and hard combinatorial problems and their relaxations into convex problems. While the emphasis is given on mathematical and algorithmic foundations, several example applications together with their modeling as optimization problems will be discussed.

The course requires a good background in linear algebra and multivariate calculus, but no prior knowledge in optimization is required. The course can be seen as complementary to the core lecture "Optimization" which will also takes place during the summer semester.

Students who intend to do their master thesis in machine learning are encouraged to take this course.

Type: Advanced course (Vertiefungsvorlesung), 9 credit points

LECTURE MATERIAL

The course follows in the first part the book of Boyd and Vandenberghe.

Lecture notes (will be updated - coverage until convex sets): Lecture notes

The practical exercises will be in Matlab and will make use of CVX.

SLIDES AND EXCERCISES

21.04. - Introduction
26.04. - Convex sets	Exercise 1	Solution 1
28.04. - Convex sets + Convex Functions
03.05. - Convex Functions II	Exercise 2	Solution 2
05.05. - No lecture due to public holiday
10.05. - Convex Functions II	Exercise 3	Solution 3
12.05. - Subdifferential
17.05. - Convex Optimization	Exercise 4	Solution 4
19.05. - Convex Optimization
24.05. - Duality Theory	Exercise 5	Solution 5
26.05. - No lecture due to public holiday
31.05. - KKT Conditions	Exercise 6	Solution 6
02.06. - Sensitivity/non-smooth KKT conditions
07.06. - One-dimensional Opt/Grad Descent	Exercise 7	Solution 7	Material for Ex7
09.06. - Newton Descent
14.06. - Subgradient Methods/Constrained Newton	Exercise 8	Solution 8	Material for Ex8
16.06. - Barrier Method
21.06. - Barrier Method/Projected Grad Descent	Exercise 9	Solution 9	Material for Ex9
23.06. - Projected Grad/Subgrad Descent
28.06. - Accelerated Gradient/Proximal Methods	Exercise 10	Solution 10
01.07. - Primal-Dual Proximal Method
05.07. - Quasi Newton	Exercise 11	Solution 11
07.07. - Coordinate Descent
12.07. - SDCA/Coordinate Gradient Descent	Exercise 12	Solution 12
14.07. - Coordinate Gradient Descent
19.07. - Implementation/Parallelization
21.07. - Parallel Methods
26.07. - Stochastic Gradient Descent
28.07. - Nonconvex Optimization

TIME AND LOCATION

Lecture: Tuesday, 14-16, E2 4, SR6 - Room 217, Thursday, 10-12, E1 3, HS 003

Tutorials:  Friday, 16-18, E2 4, SR6 - Room 217

EXAMS AND GRADING

End-term: 10.8.2016, 13-15 HS 001, Re-exam: 11.10.2016, 14-16 HS 003

Grading:

• 50% of the points in the exercises are needed to take part in the exams.
• An exam is passed if you get at least 50% of the points.
• The grading is based on the better result of the end-term and re-exam.
• Exams can be oral or written (depends on the number of participants).

LECTURER

Prof. Dr. Matthias Hein

Office Hours: Thursday, 16-18

Organization: Quynh Nguyen Ngoc

LITERATURE AND OTHER RESOURCES

• D. P. Bertsekas: Convex Optimization Theory, (2009).
  Link to the free chapter on optimization algorithms.
• J.-B. Hiriart-Urruty, C. Lemaréchal: Fundamentals of Convex Analysis (2013).
• S. Boyd and L. Vandenberghe: Convex Optimization, Cambridge University Press, (2004).
  The book is freely available
• D. P. Bertsekas: Nonlinear Programming, Athena Scientific, (1999).
• Other resources:
  • Matlab is available on cip[101-114] and cip[220-238].studcs.uni-sb.de, gpool[01-27].studcs.uni-sb.de
    The path is /usr/local/matlab/bin.
    For the sun workstations you have to select in the menu Applications/studcsApplications/Matlab
    Access from outside should be possible via ssh: ssh -X username@computername.studcs.uni-sb.de
  • Matlab tutorial by David F. Griffiths