Convex Optimization – A.A. 2023/24
About
The aim of the course is to provide students with fundamental concepts in convexity and convex optimization, as well as their application to nonlinear optimization problems. The course will focus on how to recognize convexity, how to formulate convex relaxations of nonlinear optimization problems, and how to solve convex optimization problems. The course is addressed at an audience from all areas of mathematics. Planned topics include:
-
Convex sets, convex hulls, Caratheodory’s theorem, polyhedra and polytopes, extreme points, Minkowski’s theorem
-
Convexity of functions, subgradients, inequalities related to convexity, convex conjugate
-
Convex optimization problems, Lagrange duality, Karush-Kuhn-Tucker optimality conditions
-
Convex optimization algorithms, gradient and subgradient methods, mirror descent
-
Convex optimization modeling software (such as CVXPY), disciplined convex programming
Enrollment
Prospective students should express their interest by sending an email message to the lecturer (vincenzo.bonifaci@uniroma3.it) in order to be enrolled in the course, or if they seek additional information.
Schedule
When: November 15 — December 20, 2023
Every Wednesday 14.00-16.00 and Friday 14.00-16.00 (except December 8)
Where: Rooms M1 (Wednesday) and M3 (Friday), Dipartimento di Matematica e Fisica, Università Roma Tre
via Lungotevere Dante, 376 — also accessible by walking from Largo San Leonardo Murialdo, 1
Lectures will also be streamed on the Microsoft Teams platform.
| Date | Room | Hours | Topics |
|---|---|---|---|
November 15 |
M1 |
14.00-16.00 |
Convex sets I — Optimization problems, convex combinations, Carathéodory’s theorem |
November 17 |
M3 |
14.00-16.00 |
Convex sets II — Convexity-preserving set transformations, separating and support hyperplanes, polytopes, Minkowski’s theorem |
November 22 |
M1 |
14.00-16.00 |
Convex functions I — Characterizations, three-slope inequality, local to global optimality, epigraph, subgradients |
November 24 |
M3 |
14.00-16.00 |
Convex functions II — Inequalities related to convexity, convexity-preserving function transformations, convex conjugate |
November 29 |
M1 |
14.00-16.00 |
Convex optimization problems — Optimality condition for a constrained convex problem, examples |
December 1 |
M3 |
14.00-16.00 |
Convex optimization problems — Lagrangian Duality, weak and strong duality, complementary slackness conditions |
December 6 |
M1 |
14.00-16.00 |
Convex optimization algorithms — Karush-Kuhn-Tucker conditions, Gradient Descent |
December 13 |
F (in via Vasca Navale, 84) |
14.00-16.00 |
Convex optimization algorithms — Projected Gradient Descent, effects of smoothness and strong convexity |
December 15 |
M3 |
14.00-16.00 |
Convex optimization algorithms — Mirror Descent, Bregman projections, Hedge algorithm |
December 20 |
M1 |
14.00-16.00 |
Convex optimization software — Disciplined Convex Programming, CVXPY examples |
References
-
A. Barvinok. A Course in Convexity. American Mathematical Society, 2002.
-
A. Beck. First-Order Methods in Optimization. SIAM, 2017.
-
D. Bertsekas. Convex Optimization Theory. Athena Scientific, 2003.
-
J.M. Borwein, A.S. Lewis. Convex Analysis and Nonlinear Optimization. Canadian Mathematical Society, 2006.
-
J.M. Borwein, J.D. Vanderwerff. Convex Functions. Cambridge University Press, 2010.
-
S. Boyd, L. Vanderberghe. Convex Optimization. Cambridge University Press, 2004.
-
S. Bubeck. Convex Optimization: Algorithms and Complexity. Foundations and Trends in Machine Learning, Vol. 8, No. 3-4 (2015) 231–357
-
N. Vishnoi. Algorithms for Convex Optimization. Cambridge University Press, 2021.
-
Disciplined Convex Programming webpage.