582486 Convex Optimization (8 cr)
Convex optimization problems arising in, e.g., data analysis and
machine learning, and efficient algorithms for solving them are
studied. Convex duality theory, interior point algorithms and gradient
based approaches are among techniques covered in the course.
News
- Please give feedback on the course!
- Course exam: Wednesday 3.5. at 9-12 in CK112. Note that the exam starts at 9.00, not 15 past.
- Project guidance sessions have been cancelled. If you need guidance in project work, please see Sandor (room A324) Tuesdays 12-14.
- Exercise session 6 has been moved to 21.3. A project specification session will be held on 14.3.
- Project work instructions are now available.
- Please see the section on programming tools for replacements for Matlab Statistical Toolbox.
- Dr Sandor Szedmak will give a guest lecture titled How to teach Support Vector Machine to learn vector outputs on 17 February at 14.15 in C222
- First lecture on 16 January at 14.15 in D122
Exercises
- Exercise 1 (24.1.)
- Exercise 2 (31.1.)
- Exercise 3 (7.2.)
- Exercise 4 (14.2.)
- Exercise 5 (21.2.)
- Exercise 6 (21.3., rescheduled from 14.3.)
Computers in room Dk110 have access to Matlab in Linux. You can start Matlab with
/opt/matlab/bin/matlab
Slides
- 16.1. (introduction, mathematical background up to second derivate)
- 17.1. (mathematical background continued)
- 23.1. (hyperplanes, cones, convex functions)
- 24.1. (quasiconvex functions, convex optimization problems)
- 30.1. (convex and quadratic optimization problems)
- 31.1. (second order cone programming, semidefinite programming)
- 6.2. (duality, lagrangian duals)
- 7.2. (duality, KKT, sensitivity)
- 13.2. (unconstrained optimization, gradient descent)
- 14.2. (gradient descent, Newton's method)
- 20.2. (equality constrained optimization, conditional gradient)
- 21.2. (gradient projection methods, barrier method)
- 13-14.3. (network flows)
- 20-21.3. (approximation)
- 27-28.3. (optimization in machine learning)
- 3-4.4. (algorithms & solution frameworks) (updated 7.4.)
- 10-11.4. (large scale optimization)
Please don't print the slides on department printers!
Project work
- Project work topics are discussed in a session on 14 March at 12-14 in C221. If you have an outline of your own topic, you may present it informally. Otherwise, you may discuss with Sandor to find a good project topic.
- Deadline for the project specification is 21.3 at 23.59. Return your one-page specification in the exercise session or by mail to Esa.
- Project guidance: see Sandor in his office A324 Tuesdays 12-14.
- You should present your project in the final seminar 24-25.4. at 14-16 in D122 (20-30 minute oral presentation).
-
Deadline for the project report (5-6 pages) is 25.4. at 23.59.
The report should contain
- the description of the problem domain
- optimization problem solved
- algorithms used
- data the problem was tried on
- what kind of experiments we tried
- results of the experiments
- discussion
Course organizers
- Lectures: prof. Juho Rousu, Dr Sandor Szedmak
- Course Assistant: Esa Pitkänen
Course schedule
Period 3
- Lectures: (16.1-21.02) Mondays and Tuesdays 14-16 room D122
- Exercise groups: (23.1-24.2) Tuesdays 12-14 room CK107
Period 4
- Lectures: (13.03-11.04) Mondays and Tuesdays 14-16 room D122
- Project specification session: 14.3. at 12-14 room C221
- Exercise session: 21.3 at 12-14 room C221 (rescheduled from 14.3.)
- Project guidance sessions: (28.3-11.4) Tuesdays 12-14 room C221
- Final seminar: 24-25.4 at 14-16 room D122
Passing the course
The course grade will consist of three components:- Points in course exam (max 30 points), to successfully pass the course a score of at least 15 points is required from the exam
- Points from exercises (max 10 points)
- Points from the project (max 20 points). Grading of the project will be based both on the project report and the oral presentation.
Course contents
- Mathematical foundation: convex sets
- Mathematical foundation: convex functions
- Optimization and feasibility
- Duality and Lagrangian multipliers
- Algorithms: unconstrained optimization
- Algorithms: constrained minimization
- Applications: Network problems
- Applications: Approximation
- Applications: SVMs
- Interior point method
- Nondifferentiable problems and towards large-scale problems
Exam
- Course exam: Wednesday 3.5. at 9.00-12.00 in CK112
- List of course exam dates and places
Course book
- Stephen Boyd, Lieven Vandenberghe: Convex Optimization, Cambridge University Press, 2004.
Additional material
- Jon Dattoro: Convex Optimization and Euclidean Geometry; a PDF book available on the net and on CD
- Dimitri P. Bertsekas: Nonlinear Programming; lecture slides on the web
Programming tools
- BPMPD_MEX is a free Matlab package for linear and linearly constrained quadratic programming problems.
Previous update: 26.04.2006 09:02 - Esa Pitkänen