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 2014

RESULT OF RE-EXAM and FINAL GRADES

download
Exam Inspection will be on Wednesday, 22th of October, 15.00-16.00 in Room 222.2

RESULT OF EXAM

download

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.

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

SLIDES AND EXCERCISES

17.04. Introduction/Quick review LA and Analysis

22.04. Convex Sets

Exercise 1 Solution 1
24.04. Convex sets (cont.) + Convex Functions

29.04. Convex Functions II

Exercise 2 Solution 2
01.05 - Public Holiday
06.05. Convex Functions III (Subdifferential)

Exercise 3 Solution 3
08.05. Convex Functions IV (Sublinear Functions)

13.05. Convex Functions V (Conjugate)

Exercise 4 Solution 4
20.05. Convex Optimization Problems

Exercise 5 Solution 5
22.05. Duality Theory

26.05. KKT conditions

Exercise 6 Solution 6
28.05. - Public Holiday
03.06. One-dimensional Convex Optimization

Exercise 7 Solution 7
05.06. Unconstrained Optimization

10.06. Unconstrained Optimization II

Exercise 8 Solution 8
12.06. Lecture canceled
17.06. Subgradient Methods/Constrained Newton

Exercise 9 Solution 9
19.06. Public Holiday
24.06. Interior Point Method

Exercise 10 Data Solution 10
26.06. Projected Gradient Descent

01.07. Lecture cancelled Exercise 11 Data from Exercise 10 Solution 11
03.07. Accelerated First Oder Methods
08.07. Primal Dual First Order Methods

Exercise 12 Solution 12
10.07. Coordinate Descent

15.07. Randomized Coordinate Descent

17.07. RCD/Efficient Implementation

22.07. Stochastic Gradient Descent

TIME AND LOCATION

Lecture: Tuesday, 10-12, E2 4, SR6 - Room 217, Thursday, 10-12, E2 4, SR6 - Room 217

Exercises: Thursday, 8-10, E1 3, SR 16 

EXAMS AND GRADING

End-term: 1.8., 14-17, HS 2 in E1 3, Re-exam: 10.10, 14-17, HS 2 in E1 3

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: Do, 16-18

Organization: to be announced

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  

NEWS

Check of first exam on October 7th, 11.00-12.00 in Room 222.2

Exam dates posted

Update of exercise sheet 10: added missing factor 1/2 in the definition of phi

Update of exercise sheet 10: The values for the error parameter C which are supposed to be used in the last part of the exercise have been added

03.05. - Registration is now possible in HISPOS until 19th of May.

Added the link to the additional free chapter on convex optimization algorithms by Bertsekas.