LNMB course IPM: “Interior point methods”
9 Mondays 15.15-17.15 (September 8 - November 3, 2025)
On site in Utrecht Science Park (weeks 1 through 6, room HFG 611 in the Hans Freudenthal building, Budapestlaan 6, 3584 CD Utrecht ), and online (Zoom in weeks 7,8,9) .
Prof. Etienne de Klerk (Tilburg University).
Course description:
The field of optimization, particularly linear, convex and semidefinite 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 semidefinite 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:
Available online: http://www.stanford.edu/~boyd/cvxbook/
Assignments:
1) Available here (pdf). Due September 22 at the start of class.
2) Available here (pdf). Due October 6th at the start of class.
3) Available here (pdf). Due October 27th at the start of class.
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.
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 (room HFG 611):
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.
Week 3 (room HFG 611):
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.
Week 4 (room HFG 611):
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.
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.
Week 6 (room HFG 611):
Today: self-concordant barriers and the barrier method.
In Renegar's book: §2.3.4, (parts of) §2.4.1, §2.4.2.
Week 7 (online):
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.
Slides
Week 8 (Online):
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
Week 9 (Online):
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.
Slides