Saarland University, Machine Learning Group, Fak. MI - Mathematik und Informatik, Campus E1 1, 66123 Saarbrücken, Germany

Machine Learning Group
Department of Mathematics and Computer Science - Saarland University

# TEACHING

## CONVEX OPTIMIZATION

Sommersemester 2017

### 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.

The course counts as lecture in mathematics and computer science.

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

<
 20.04. - Introduction Exercise 0 Solution 0 24.04. - Convex sets 27.04. - Convex Functions I Exercise 1 Solution 1 01.05 - No lecture due to public holiday 04.05. - Convex functions + subdifferential Exercise 2 Solution 2 08.05. - Normal cone/Optimality conditions 11.05. - Conjugate Function/Quasiconvex Exercise 3 Solution 3 15.05. - Convex Optimization 18.05. - Duality Theory Exercise 4 Solution 4 25.05. - No lecture due to public holiday 29.05. - Lecture canceled 01.06. - Sensitivity/KKT Conditions Exercise 5 Solution 5 05.06. - No lecture due to public holiday 08.06. - Non-smooth KKT/One-dimensional convex Opt Exercise 6 Solution 6 12.06. - Gradient Descent 15.06. - No lecture due to public holiday 19.06. - Newton and Quasi-Newton Method Exercise 7 Solution 7 22.06. - Subgradient Descent 26.06. - Interior Point Method 29.06. - Interior Point Method (cont.) Exercise 8 Solution 8 Material for Ex8 03.07. - Projected Grad/Subgrad Descent 06.07. - Accelerated Gradient Descent Exercise 9 Solution 9 10.07. - Primal-Dual Proximal Method 13.07. - Lecture canceled Exercise 10 Solution 10 17.07. - Primal-Dual Proximal Method II 20.07. - Coordinate Descent

### TIME AND LOCATION

Lecture: Monday, 10-12, E1 3, HS 003, Thursday, 10-12, E1 3, HS 003

Tutorials:  Friday, 14-16, E1 3, SR 015

End-term: 11.08., E1 3, HS 001/002, 14-17, Re-exam: 09.10., E1 3, HS 001/002, 10-13

• 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

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

### NEWS

Results of second exam: here
Exam inspection will be on Thursday, October 19 at 16:00 in E1 1 room 222.2.