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 AND MODELING

Sommersemester 2010

GENERAL INFORMATION

Convex optimization is a special class of mathematical optimization. Linear and quadratic programming problems are special cases. 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 have as topics convex analysis and 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 last but not least several applications where the modeling part, that is the transition from the problem to the formulation of an optimization problem is discussed.

The course requires a good background in linear algebra and calculus, but no prior knowledge in optimization is required. The course will follow to large extent the book of Boyd and Vandenberge on "Convex Optimization" and 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), 6 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

Slides 1 (Introduction/Reminder LA and Analysis) Exercise 1 Solution 1
Slides 2 (Convex Sets) Exercise 2 Solution 2
Slides 3 (Convex Functions) Exercise 3 Solution 3
Slides 4 (Convex Optimization) Exercise 4 Solution 4
Slides 5 (Convex Optimization II) Exercise 5 Solution 5
Slides 6 (Duality theory) Exercise 6 Solution 6
Slides 7 (Unconstrained Minimization) Exercise 7 Solution 7
Slides 8 (Unconstrained Minimization) Exercise 8 Matlab Files Solution 8
Slides 9 (Subgradient Methods) Exercise 9 Data Solution 9
Slides 10 (Barrier Method) Exercise 10 Newton Solution10
Slides 11 (Constrained First Order Methods) Exercise 11 Solution 11
Slides 12 (Proximal Gradient Methods) Exercise 12 TV-Data Solution 12
Slides 13 (Modeling)
Slides 14 (Numerical Linear Algebra)

LITERATURE AND OTHER RESOURCES

  • The lecture will be based on the following book:
    S. Boyd and L. Vandenberghe: Convex Optimization, Cambridge University Press, (2004).
    The book is freely available
  • Complementary book: 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

Dates for the oral exam: 30.7. and 6.8. Please write me an email with the dates where you would be available and I schedule the exams.

TIME AND LOCATION

Lecture: We, 10-12, E1 3, HS III

Exercises: Fr, 16-18, E2 4, Room 216

EXAMS AND GRADING

Exams:     End-term:    Re-exam:

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

Organization: Shyam Sundar Rangapuram