LNMB course IPM
LNMB course IPM: “Interior point methods”
9 Mondays 15.15-17.15 (September 11 - November 13, 2023)
Online (Zoom link for weeks 2,3,4,6,7,8) or on site in Utrecht Science Park (weeks 1, 5 and 9, room HFG 611 in the Hans Freudenthal building, Budapestlaan 6, 3584 CD Utrecht )
Prof. Etienne de Klerk (Tilburg University).
Course description:
The field of optimization, particularly linear, convex and semi-definite optimization, has been given a new impulse by the development of interior point methods. Besides the existence of a new theory, there is a tremendous activity in new applications, especially in semi-definite programming.
The topics for this course include:
interior-point methods for conic programming;
classical duality theory for conic programming;
symmetric cones;
primal-dual interior-point algorithms;
semidefinite programming.
Address of the lecturer:
Dr. E. de Klerk
Department of Econometrics & Operations Research, Tilburg University
E-mail : e.deklerk@uvt.nl
URL : https://www.tilburguniversity.edu/staff/e-deklerk
Prerequisites:
Basic knowledge (bachelor level) of analysis (multivariate calculus) and linear algebra, as well as a first course in linear and nonlinear programming.
Literature:
Main course notes (students: please buy or borrow this book): James Renegar, “A Mathematical View of Interior-Point Methods for Convex Optimization”. MPS-SIAM Series on Optimization, Philadelphia (2001).
An earlier (incomplete) version of this book is available online at this link: https://web.mit.edu/~jadbabai/www/EE605/Renegar.pdf
Additional course notes:
Stephen Boyd and Lieven Vandenberghe. Convex Optimization, Cambridge University Press (2004)
Available online: http://www.stanford.edu/~boyd/cvxbook/
Assignments:
1) Deadline September 25th (pdf file)
2) Deadline October 9th (pdf file)
3) Deadline October 30th (pdf file)
4) Deadline November 13th (pdf file)
Slides and weekly curriculum:
Week 1 (room HFG 611) :
Topics: cone programming, semidefinite programming and second order cone examples, background material on matrices and linear operators.
In book by Renegar: Section 1.1.
Recording of lecture from 2021
Further reading :
M. Lobo, L. Vandenberghe, S. Boyd, H. Lebret, Applications of second-order cone programming. Linear Algebra and its Applications, 1998.
L. Vandenberghe, S. Boyd, Semidefinite programming. SIAM Review, 1996.
Week 2 (Zoom link):
Topics: Convex functions; Coordinate-free calculus; Taylor expansions for multivariate functions; Newton’s method for minimizing convex functions
In book by Renegar: §1.2, §1.3, parts of §1.4 and §1.6.
Recording of lecture from 2021
Week 3 (Zoom link):
Topics: More on Newton’s method and coordinate-free calculus; Analyzing the convergence of Newton’s method.
In Renegar’s book (parts of) §1.4 and §1.5.
Recording of lecture from 2021
Week 4 (Zoom link):
Topics: Error bounds for Newton's method; Self-concordant functions (a class of convex functions where Newton's method works provably well).
In Renegar’s book Chapter 2 to up to and including Section 2.2.2.
Recording of lecture from 2021
Week 5 (room HFG 611):
Today: self-concordant barriers and the barrier method.
In Renegar's book: (the remainder of) §2.2.2, §2.2.3, §2.3.1, §2.3.2.
Slides (pdf file)
Recording of lecture from 2021
Week 6 (Zoom link):
Today: self-concordant barriers and the barrier method.
In Renegar's book: §2.3.4, (parts of) §2.4.1, §2.4.2.
Recording of lecture from 2021
Week 7 (Zoom link):
Today: Finding a point near the central path, the long-step method, problems with equality constraints
In Renegar's book: (parts of) §2.3.4, §2.4.2, §2.4.3.
Recording of lecture from 2021
Week 8 (Zoom link):
Today: Duality in conic optimization; self-dual embeddings to find a starting point
In Renegar's book: (parts of) §3.1 and §3.2, but we will not follow the book closely here. The self-dual embedding part is not in the book - slides only.
Slides: conic duality, self-dual embeddings
Recording of lecture from 2021
Week 9 (room HFG 611):
Today: Primal-dual interior point methods; the Nesterov-Todd search direction; software and online resources
In Renegar's book: (parts of) §3.3 through §3.7, but we will not follow the book closely here.
Recording of lecture from 2021