Convex Optimisation: Fall 2019
- Dates: Mondays, 13:15–15:00
- Time & place: Room 634.
- Please contact markus [dot] grasmair [at] ntnu [dot] no for any questions concerning the course.
- Exam: oral exam (time/date: TBA)
The objective of this module course is to get acquainted with the basic ideas of convex analysis in order to be able to apply convex techniques to the solution of convex (and sometimes non-convex) optimisation problem.
- N&W … Jorge Nocedal & Stephen J. Wright, Numerical Optimization, Second Edition, Springer, 2006.
- B&C … Heinz H. Bauschke & Patrick L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Second Edition, Springer 2017.
- B&L … Jonathan M. Borwein & Adrian S. Lewis, Convex Analysis and Nonlinear Optimization, Second Edition, Springer 2006.
- Cl … Christian Clason, Nonsmooth analysis and optimisation, lecture notes, arXiv, 2018.
- ADMM … Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein, Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers, Foundations and Trends in Machine Learning, 3(1), 2010, pp. 1-122.
|Week 37|| Introduction |
Backtracking gradient descent
Failure of gradient descent
|Week 38|| Review of smooth optimisation |
Line search and trust region approaches
Preconditioning of gradient descent
Newton and Quasi-Newton methods
|N&W, Chaps. 1-7|
|Week 39|| Convex sets |
Projections on convex sets
Polar and dual cones
|B&C, Chaps. 3.1, 3.2, 6.1, 6.3, 6.4|
|Week 40|| Tangent and normal cones |
|B&C, Chaps. 6.4, 8.1, 8.2, 8.3; Cl, Chap. 3|
|Week 41|| Convex conjugation |
Properties of convex conjugates
Convex subdifferentials and subgradients
Properties of subgradients
|B&C, Chaps. 13, 15.1, 16.1, 16.2, 16.3; Cl. Chaps. 5, 4|
|Week 42|| Characterisation of subdifferentials |
Subdifferentials of sums
Linear chain rule
|Cl, Chaps. 4, 5; B&C, Chap. 16.4|
|Week 44|| Fenchel–Rockafeller Theorem |
Primal and dual problems
Dual projected gradient descent
|Cl, Chap. 5; B&C, Chap. 19.1|
|Week 45|| Saddle point formulation of duality |
|Cl, Chaps. 6.2, 7.1, 7.2; B&C, Chap. 28.5|
|Week 46|| Douglas–Rachford splitting |
Arrow–Hurwicz and Chambolle–Pock methods
|Cl, Chaps. 7.3, 7.4; B&C, Chap. 28.3|
|Week 47|| Lagrangian method and dual gradient descent |
Augmented Lagrangian methods
|ADMM, Secs. 1, 2, 7|
Here you can find exercises to try your luck on. Currently, you can find there exercises related to the topics discussed in weeks 38–40, but I will add additional exercises later. Do not expect solutions.