TU Berlin

FG Kombinatorische Optimierung und GraphenalgorithmenConvex Optimization and Applications (ADM III)

COGA 5-Wheel

Inhalt des Dokuments

zur Navigation

News

Registration to the exam

Some students had problems registering with the examination office, apparently due to some communication problems with that office. This problem should now be resolved: the course is well registered in the list of Advanced Mathematics Topics, as this document attests.

 

Deadline extension

The deadline for the programming exercise is extended to Feb. 13, 12:00 (noon)

 

The optional programming exercise is online, cf. next paragraph.

We had a programming session on December 19. Here is the link to the notebook we used for this session. To use this notebook, first go to File > "save a copy in drive". Then, you should be able to modify it and execute the cells.

The solutions to this notebook can be found here (a password was given in class, you can email me if you need it).

Programming exercises

The link for the programming exercise is here:

Instruction: Copy the notebook to your drive, so you can edit it. Then, fill the TODOs in the notebook. When you are done, download the notebook as a .ipynb file, and send it by email. The deadline to hand out your .ipynb files is February 13 12:00 (noon). 

Convex Optimization and Applications (ADM III)

Surprisingly many real-world optimization problems can be reformulated as convex optimization problems. This convexity plays a central role in the computational tractability of a solution. The goals of this course are:

  1. to provide the students with the necessary background to recognize optimization problems that can be reformulated as convex ones;
  2. to study the duality theory of convex optimization from the point of view of conic programming, which includes as particular cases the linear programming (LP), semidefinite programming (SDP), second order cone programming (SOCP), and geometric programming (GP);
  3. to review a variety of applications of convex optimization from various branches such as engineering, control theory, machine learning, robust optimization, and approximation algorithms for combinatorial problems;
  4. finally, to understand algorithms for convex programming, in particular interior point methods, and to be able to use modern interfaces to pass optimization problems to solvers that implement these algorithms.

Examination

The oral examinations will take place on February 28. Online oral exams will take place on May 14 and May 15.

Please register for one exam slot at Daniel Schmidt gen. W.'s office (MA 524) during office hours. You also need to register for the exam at the Pr├╝fungsamt, and you can bring us the yellow registration form at the end of any lecture.

All exams will take place in MA 518 or online (via Zoom). Don't forget to bring your student ID!

For the examinations, you are not expected to know everything by heart. However, you have to know the basic definitions, know which results exist, and be able to explain them with your own words (there is no need to know very technical formulas, but you must be able to restitute the main message of a theorem, for example. If you ever need a technical formula, there will be a printed copy of the handout available during the exam. You will not be asked to prove results from the course, but rather to demonstrate your general understanding on convex optimization techniques, solve some new exercises, and show your modelling skills.

 

Exam Schedule
Feb 28
May 14 (Online)
May 15 (Online)
July 1 (MA517)
Later
Helene
9:10
Jan-Erik
14:00
Malin
13:50
Linda
Felix
9:50
Lisa
14:50
Anh Huy
14:50
Anh Huy
14:40
Alfons
Fatima
10:30
Hannah
15:40
Diego
15:40
Willy
15:30
Till
11:10
Valentin
16:30
Franziska
16:30
Leonhard
16:20
Yujin
11:50
17:20
17:20
17:10
Anton
13:40
Sebastian
May22

 

 

Schedule

Schedule
Day
Time
Room
Lecture
Monday
10:15 - 11:45
MA 649
Lecture
Thursday
14:15 - 15:45
MA 550

 An exercise session will be held every second week on Thursday.

Contact Information

Evaluation

Exercises will be given on week in advance. At the beginning of exercise sessions, check the exercises you've prepared. One student will be asked to explain his solution. You need 50% of all exercises checked to take the exam.

There will be an oral examination. You should not learn everything by heart, but rather know which result exists. We expect a global understanding of how the chapters of this course articulate together. You will not be asked to prove results from the course, but you will have to solve some new exercises and show your modelling skills.

References

There will be a handout, posted online as the corresponding chapters are completed.

 

The course is mainly based on:

  • Boyd, S., & Vandenberghe, L. (2004). Convex optimization. Cambridge university press.

 

Selected chapters are also based on the following references:

  • "Lecture on Modern Convex Optimization", A. Ben-Tal & A. Nemirovski, 2001.
  • "Semidefinite Optimization", Lecture notes of M. Laurent & F. Vallentin at Utrecht.

Further references are indicated directly in the handout.

Handout

Chapter
1-Preliminaries
1_intro.pdf
2-Convex geometry
2_cvx_geom.pdf
3-Convex functions
3_cvx_fun.pdf
4-Convex optimization
4_cvx_optim.pdf
5-Ellipsoid method
5_ellipsoid.pdf
6-Conic Programming
6_conic_programming.pdf
7-Duality
7_duality.pdf
8 - Applications in Combinatorial Optimization
8_combi.pdf
9 - Lasserre Hierarchy & Polynomial Optimization
9_hierarchies.pdf
10 - Interior points methods
10_ipm.pdf
11 - Application to Data Science
11_data.pdf
12 - First Order Methods
12_first_order.pdf

 

 

Slides

Slides
1-Intro
slides-1.pdf
2-Convex geometry
slides-2.pdf
3-Convex functions
slides-3.pdf
4-Convex Optimization
slides-4.pdf
5-Ellipsoid Methods
slides-5.pdf
8-Combinatorial Optimization
slides-8.pdf
9-Lasserre Hierarchy
slides-9.pdf
10-Interior Point Methods
slides-10.pdf
11-Application to Data Science
slides-11.pdf
12-First Order Methods
slides-12.pdf

Exercise Sheets

Exercise Sheets
Exercise Sheet
Due Date
Sheet 1
Oct. 24
Sheet 2
Nov. 7
Sheet 3
Nov. 21
Sheet 4
Dec. 5
Sheet 5
Jan. 16
Sheet 6
Feb. 6

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe