Edinburgh Research Archive >
Mathematics, School of >
Mathematics thesis and dissertation collection >
Please use this identifier to cite or link to this item:
|Title: ||On inexact Newton directions in interior point methods for linear optimization|
|Authors: ||Al-Jeiroudi, Ghussoun|
|Supervisor(s): ||Gondzio, Jacek|
|Issue Date: ||2009|
|Publisher: ||The University of Edinburgh|
|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.|
|Sponsor(s): ||University of Damascus|
|Keywords: ||interior point method|
preconditioned conjugate gradients
|Appears in Collections:||Mathematics thesis and dissertation collection|
Items in ERA are protected by copyright, with all rights reserved, unless otherwise indicated.