Aims:

Interior-point methods are theoretically the fastest algorithms for solving linear programming problems. Over the past twenty years a thorough theoretical understanding of these methods has emerged, and the theory has been extended to other classes of optimization problems: semidefinite programming, conic programming, and general nonlinear programming. The aim of this course is to give an introduction to this theory to provide an understanding of the main principles that render these methods so powerful, and to address practical issues that arise in implementations. We will first treat the case of linear programming and later discuss extensions to nonlinear problems, in particular semidefinite programming, for which we will stress the use as a modelling tool in applications.

Synopsis:

Lecture 1:	Overview, linear programming duality.
Lecture 2:	Optimality conditions for convex programming.
Lecture 3:	The central path, Newton's method.
Lectures 4-5:	A primal-dual interior-point algorithm for LP.
Lecture 6:	Affine and centering directions, wider neighbourhoods of the central path.
Lecture 7:	Convergence of the algorithms considered so far.
Lecture 8:	Practical interior-point methods, Mehrotra's predictor corrector method, numerical issues.
Lecture 9:	Extensions to other formulations of LP, linear complementarity problems, and nonlinear programming.
Lecture 10:	Semidefinite programming problem formulation and applications, modelling aspects.
Lecture 11:	Strong SDP duality, interior-point methods for SDP.
Lecture 12:	A primal-dual interior-point method for semidefinite programming.

Reading List

• J.Renegar, A Mathematical View of Interior-Point Methods in Convex Optimization SIAM, 2001

• S.Wright, Primal-Dual Interior-Point Methods SIAM, 1997