- Lecturers Michel Baes and Patrick Cheridito
- Topics
- Convex functions and sets, semidefinite cones
- Duality, conjugate functions, subgradients
- Karush–Kuhn–Tucker optimality conditions
- Conic programming, CQr sets and functions, SDr sets and functions, applications
- Black-box methods: bisection, gradient methods for unconstrained and constrained convex problems, stochastic gradient methods, mirror-descent methods, Newton method
- Interior point methods
- The Exam is a written test taking place on February 8th, 2019 from 9:00 - 11:00 in HG F 1. You are allowed to bring 10 single-sided A4 pages of your own notes. No books or lecture notes are allowed. Laptops, tablets, and mobile phones must be switched off during the whole exam. The exam questions will be of the same style as the exercises below.
- Office hours on January 10, 17 and 23 from 15:00 - 17:00 in HG F 42.1
- Exam preparation sessions on January 29 and February 4 from 14:15 - 16:00 in HG E 33.1
- Lectures
- 1. Convex sets and functions
- 2. Semidefinite cones and separation theorems
- 3. Duality
- 4. Optimality conditions, Lagrangian duality
- 5. Subgradients, conjugate functions
- 6. KKT Conditions and applications
- 7. Conic optimization and applications (robust linear programming, minimal surface problem, polynomial optimization, MaxCut, S-Lemma)
- 8. More applications: approximation, coalitions, maximum likelihood
- 9. Black-box methods 1 (grid method, bisection, gradient method, stochastic gradient method)
- 10. Black-box methods 2 (accelerated gradient method, Newton method, mirror-descent methods, multiplicative weights algorithm)
- 11. Interior-point methods
- Exercises
- Exercise set 1 (Lecture 1)
- Exercise set 2 (Lecture 2)
- Exercise set 3 (Lecture 3) Nesterov_Chebysev.m
- Exercise set 4 (Lecture 4)
- Exercise set 5 (Lecture 5)
- Exercise set 6 (Lecture 6)
- Exercise set 7 (Lecture 6)
- Exercise set 8 (Lecture 7) elliplot.m
- Exercise set 9 (Lecture 8)
- Exercise set 10 (Lecture 9)
- Exercise set 11 (Lecture 10)
- Exercise set 12 (Lecture 11)
- Exercise set 13 (Lecture 11)
- Solutions to selected exercises
- Useful links
- Literature
-
A. Barvinok, A Course in Convexity. American Mathematical Society, 2003.
- This well-written book covers convex analysis, with a particular emphasis on the interactions between convex analysis and combinatorial optimization problems. ETH-MATH E 0.130
-
A. Beck, First-Order Methods in Optimization. MOS-SIAM Series on Optimization, 2017.
- This book offers all the necessary fundamental results, as well as many applications, on this fast evolving topic. Available at the ETH central library or electronically on ETH's domain.
-
A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization - Analysis, Algorithms, and Engineering Applications, Princeton Series in Applied Mathematics.
- This authoritative work displays a great variety of applications of convex optimization. It constitutes an ideal complement to the book of Boyd and Vandenberghe. Available upon request.
-
A. Ben-Tal, L. El Ghaoui, and A. Nemirovski, Robust Optimization, MPS-SIAM Series on Optimization, MPS-SIAM.
- This book is the first systematic treatise on (finite dimensional) robust optimization. Along with a rigorous development of the theory, it contains a wealth of practical examples.
-
D. P. Bertsekas, A. Nedic and A. E. Ozdaglar, Convex Analysis and Optimization, Athena Scientific, 2003. ETH-MATH L 6.253
-
D. Bertsimas and J. N. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997. ETH-MATH L 6.248
-
S. Boyd, L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004.
- This thick book serves as one of the main references for the course. The
authors deal with a number of applications of convex optimization in an
impressive variety of fields.
Click on the link to download.
- This thick book serves as one of the main references for the course. The
authors deal with a number of applications of convex optimization in an
impressive variety of fields.
Click on the link to download.
-
S. Boyd, L. El Ghaoui, E. Feron and V. Balakrishnan, Linear Matrix Inequalities in System and Control Theory. SIAM, 1994. ETH-MATH H 8.162
-
P. Cheridito, Convex Analysis. Lecture notes, Princeton, 2013.
-
E. de Klerk, Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications, Book Series: APPLIED OPTIMIZATION, Vol. 65. Kluwer Academic Publishers. ETH-MATH L 6.246
-
R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, 1985.
- This well-known book is an excellent reference on linear algebra. Its sequel "Topics in Matrix Analysis" is also a classic. Available upon request.
-
Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Book Series: APPLIED OPTIMIZATION, Vol. 87. Kluwer Academic Publishers.
- This important book emerged from the lecture notes of Pr. Yurii Nesterov.
It focuses on the study of algorithms for convex optimization, and, among others,
first-order methods and interior-point methods.
Available upon request.
- This important book emerged from the lecture notes of Pr. Yurii Nesterov.
It focuses on the study of algorithms for convex optimization, and, among others,
first-order methods and interior-point methods.
Available upon request.
-
Y. Nesterov and A. Nemirovski, Interior Point Polynomial Algorithms in Convex Programming, Studies in Applied Mathematics Vol. 13, SIAM, 1993.
- This authoritative but hard book was the first to introduce the concept of self-concordance. ETH-MATH L 6.259
-
A. Nemirovski and D. Yudin, Problem Complexity and Method Efficiency in Optimization, John Wiley, 1983.
- This quite dense work focuses on the question "How efficient can optimization algorithms be ?".
Available upon request.
- This quite dense work focuses on the question "How efficient can optimization algorithms be ?".
Available upon request.
-
J. Renegar, A Mathematical View of Interior-Point Methods in Convex Optimization, MPS-SIAM Series on Optimization.
- This short book has been developed from a graduate course of Jim Renegar. It contains an original analysis of interior-point methods, which complements beautifully the book of Nesterov. Available upon request.
-
R.T. Rockafellar, Convex Analysis, Princeton University Press, 1997.
- This is a classical and rather complete reference on finite-dimensional convexity. Available upon request.
-
S. Shalev-Shwartz and S. Ben-David, Understanding Machine Learning - From Theory to Algorithms, Cambridge University Press, 2014.
-
H. Wolkowicz, R. Saigal and L. Vandenberghe, Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, Kluwer Academic Publishers.
- This book is a collection of well-written reviews on a variety of aspects of semidefinite programming, including a discussion on its numerical behavior and the development of a robustness analysis. ETH-MATH L 6.245
-