Show simple item record

dc.contributor.advisorGondzio, Jacek
dc.contributor.authorAl-Jeiroudi, Ghussoun
dc.date.accessioned2010-10-06T10:17:55Z
dc.date.available2010-10-06T10:17:55Z
dc.date.issued2009
dc.identifier.urihttp://hdl.handle.net/1842/3863
dc.description.abstractIn 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.en
dc.language.isoenen
dc.publisherThe University of Edinburghen
dc.subjectinterior point methoden
dc.subjectlinear programmingen
dc.subjectpreconditioned conjugate gradientsen
dc.titleOn inexact Newton directions in interior point methods for linear optimizationen
dc.typeThesis or Dissertationen
dc.type.qualificationlevelDoctoralen
dc.type.qualificationnamePhD Doctor of Philosophyen


Files in this item

This item appears in the following Collection(s)

Show simple item record