Edinburgh Research Archive logo

Edinburgh Research Archive

University of Edinburgh homecrest
View Item 
  •   ERA Home
  • Mathematics, School of
  • Mathematics thesis and dissertation collection
  • View Item
  •   ERA Home
  • Mathematics, School of
  • Mathematics thesis and dissertation collection
  • View Item
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.

On inexact Newton directions in interior point methods for linear optimization

View/Open
AlJeiroudi2009.pdf (440.0Kb)
Date
2009
Author
Al-Jeiroudi, Ghussoun
Metadata
Show full item record
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.
URI
http://hdl.handle.net/1842/3863
Collections
  • Mathematics thesis and dissertation collection

Library & University Collections HomeUniversity of Edinburgh Information Services Home
Privacy & Cookies | Takedown Policy | Accessibility | Contact
Privacy & Cookies
Takedown Policy
Accessibility
Contact
feed RSS Feeds

RSS Feed not available for this page

 

 

All of ERACommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsPublication TypeSponsorSupervisorsThis CollectionBy Issue DateAuthorsTitlesSubjectsPublication TypeSponsorSupervisors
LoginRegister

Library & University Collections HomeUniversity of Edinburgh Information Services Home
Privacy & Cookies | Takedown Policy | Accessibility | Contact
Privacy & Cookies
Takedown Policy
Accessibility
Contact
feed RSS Feeds

RSS Feed not available for this page