On inexact Newton directions in interior point methods for linear optimization
View/ Open
Date
2009Author
Al-Jeiroudi, Ghussoun
Metadata
Abstract
In each iteration of the interior point method (IPM) at least one linear system
has to be solved. The main computational effort of IPMs consists in the computation
of these linear systems. Solving the corresponding linear systems
with a direct method becomes very expensive for large scale problems.
In this thesis, we have been concerned with using an iterative method for
solving the reduced KKT systems arising in IPMs for linear programming.
The augmented system form of this linear system has a number of advantages,
notably a higher degree of sparsity than the normal equations form.
We design a block triangular preconditioner for this system which is constructed
by using a nonsingular basis matrix identified from an estimate of
the optimal partition in the linear program. We use the preconditioned conjugate
gradients (PCG) method to solve the augmented system. Although
the augmented system is indefinite, short recurrence iterative methods such
as PCG can be applied to indefinite system in certain situations. This approach
has been implemented within the HOPDM interior point solver.
The KKT system is solved approximately. Therefore, it becomes necessary
to study the convergence of IPM for this inexact case. We present the
convergence analysis of the inexact infeasible path-following algorithm, prove
the global convergence of this method and provide complexity analysis.