zbMATH — the first resource for mathematics

Interior point methods. (English) Zbl 0906.90124
Beasley, J. E. (ed.), Advances in linear and integer programming. Oxford: Clarendon Press. Oxf. Lect. Ser. Math. Appl. 4, 47-102 (1996).
This is a chapter providing an introduction to the theory of interior point methods (IPM) for linear programming (LP) problems. A good deal of discussion in this chapter is devoted to the complexity analysis of algorithms, i.e., to establishing bounds on the number of iterations.
The authors consider the pair of dual LP problems \[ (\text{P})\quad \min\{c^Tx: Ax= b,\;x\geq 0\}\quad\text{and} \quad (\text{D})\quad \max\{b^Ty: A^Ty+ s= c,\;s\geq 0\}, \] where \(A\in\mathbb{R}^{m\times n}\) has full row rank. \(y\) and \(s\) in (D) are related through \(y= (AA^T)^{-1} A(c- s)\). They also assume that (P) has a feasible \(x>0\) (called interior primal feasible solution), and that (D) has a feasible \((y,s)\) with \(s>0\) (called interor dual feasible solution). A fundamental result is that for each \(w= (w_j)\in \mathbb{R}^n_+\) the following system has a unique solution \[ Ax= b\;(x>0),\quad A^Ty+ s= c\;(s>0),\quad x_js_j= w_j\;(j=1,\dots, n). \] When \(w= \mu e\), where \(e= (1,\dots, 1)^T\), and \(\mu>0\), the unique solution of the above system is denoted by \(x(\mu)\), \((y(\mu),s(\mu))\); and it traces a path called the central path, a privileged continuous curve in the interior of the feasible sets that converges to an optimum pair as \(\mu\to 0^+\). Almost all IPMs use the central path as a guideline to obtain the optimal sets of (P) and (D).
The authors describe a variety of IPMs using the notion of target following methods which are based on an iterative approach to reduce the duality gap \(x^Ts\) to \(0\) through Newton steps. Recasting the primal-dual predictor-corrector method into the target following format, they derive its asymptotic convergence rate to be quadratic. The issue of infeasible starts is also discussed using the framework of the projective algorithm of Karmarkar.
For the entire collection see [Zbl 0869.00020].

90C05 Linear programming
90C60 Abstract computational complexity for mathematical programming problems