WS 2016/2017: Convex Optimization
News:
Grades of the exam have been sent per email. Please contact me if you did not receive it; A date for the resit exam will be scheduled shortly.
- Exam and solution available in the section 'Download' (at the bottom of this page)
- Training-exam and its solution are available in the section 'Download' (at the bottom of this page)
Final written exam: 24.02.2017, 10:00, Room 025/026 Arnimallee 6 (You may use your own lecture notes during the exam, in particular it is recommended to bring a copy of the duality theorem for conic programming).
- Conic Duality Thorem is available in the section 'Download' (at the bottom of this page)
- A few typos corrected in Exercise 2 and 7 of Worksheet#5-6.
- From now on, the lecture on Tuesday will start at 10AM !
- Exercise Worksheets will be available in the section 'Download' (at the bottom of this page)
- Slides of introductory lecture available in the section 'Download' (at the bottom of this page)
- Link to interactive notebooks:
- Notebooks:
- Complete solution of first tutorial session
- Notebook activity_levels.ipynb for Ex.3 of Worksheet #5-6 (solution)
- Notebook chebyshev_center.ipynb for Ex.8 of Worksheet #5-6 (solution)
- Notebook denoising.ipynb for tutorial session #8 (solution)
- Notebook truss_design.ipynb for tutorial session #9 (solution)
- Notebook christmas_star.ipynb for extra christmas exercise [Enter your solution in the last cell of the notebook, and send your solution per email as a .ipynb file. You can test your solution by using the interactive binder].
Content:
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
- to provide the students with the necessary background to recognize optimization problems that can be reformulated as convex ones;
- 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);
- to review a variety of applications of convex optimization from various branches such as engineering, control theory, data fitting, statistics and machine learning;
- 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.
References:
The course is mainly based on:
- Boyd, S., & Vandenberghe, L. (2004). Convex optimization. Cambridge university press.
This book is freely available online, cf. the website of the "Convex optimimization book", which also contains very interesting additional material: http://stanford.edu/~boyd/cvxbook/
Other useful references may be found in:
- Ben-Tal, A., & Nemirovski, A. (2001). Lectures on modern convex optimization: analysis, algorithms, and engineering applications (Vol. 2). Siam.
- Laurent, M., & Vallentin, F.. Lecture notes on Semidefinite Optimization, 2012: http://page.mi.fu-berlin.de/fmario/sdp/laurentv.pdf
- El-Ghaoui (2013). Convex Optimization Lecture Notes for EE227BT: http://people.eecs.berkeley.edu/~elghaoui/Teaching/EE227BT/LectureNotes_EE227BT.pdf
- Gärtner, B., & Matoušek, J., Approximation Algorithms and Semidefinite Programming (Lecture notes of course 251-1426-00L): http://www.ti.inf.ethz.ch/ew/lehre/ApproxSDP09/notes/interior.pdf
- Freund, R.M. (2004). Truss Design and Convex Optimization (Lecture notes of the course "Systems-Optimization--Models-and-Computation" at MIT) https://ocw.mit.edu/courses/sloan-school-of-management/15-094j-systems-optimization-models-and-computation-sma-5223-spring-2004/lecture-notes/truss_design_art.pdf
Requirements & Formalities:
Prerequisites:
Good background in Linear Algebra. Basic knowledge of Linear Programming is a plus, but is not required.
Target Group:
BMS students, and Master students.
Examination:
Written exam. 50% of homework points are required. Final grade will be computed with following formula:
max[exam, 1/2*(exam+homeworks) ]
Contact:
Guillaume Sagnol <sagnol (at) zib (dot) de>.