Show simple item record

dc.contributor.advisorGondzio, Jacek
dc.contributor.advisorHall, Julian
dc.contributor.authorSchork, Lukas Marius
dc.date.accessioned2019-07-02T12:28:19Z
dc.date.available2019-07-02T12:28:19Z
dc.date.issued2019-07-01
dc.identifier.urihttp://hdl.handle.net/1842/35682
dc.description.abstractSolving normal equations AAᵀx = b, where A is an m x n matrix, is a common task in numerical optimization. For the efficient use of iterative methods, this thesis studies the class of preconditioners of the form BBᵀ , where B is a nonsingular "basis" matrix composed of m columns of A. It is known that for any matrix A of full row rank B can be chosen so that the entries in [B⁻¹A] are bounded by 1. Such a basis is said to have "maximum volume" and its preconditioner bounds the spectrum of the transformed normal matrix in the interval [1, 1+mn]. The theory is extended to (numerically) rank deficient matrices, yielding a rank revealing variant of Gaussian elimination and a method for computing the minimum norm solution for x from a reduced normal system and a low-rank update. Algorithms for finding a maximum volume basis are discussed. In the linear programming interior point method a sequence of normal equations needs to be solved, in which A changes by a column scaling from one system to the next. A heuristical algorithm is proposed for maintaining a basis of approximate maximum volume by update operations as those in the revised simplex method. Empirical results demonstrate that the approximation means no loss in the effectiveness of the preconditioner, but makes basis selection much more efficient. The implementation of an interior point solver based on the new linear algebra is described. Features of the code include the elimination of free variables during preconditioning and the removal of degenerate variables from the optimization process once sufficiently close to a bound. A crossover method recovers a vertex solution to the linear program, starting from the basis at the end of the interior point solve. A computational study shows that the implementation is robust and of general applicability, and that its average performance is comparable to that of state-of-the-art solvers.en
dc.language.isoenen
dc.publisherThe University of Edinburghen
dc.relation.hasversionL. Schork and J. Gondzio. An inexact potential reduction method for linear programming. Technical Report ERGO-16-005, University of Edinburgh, 2016.en
dc.relation.hasversionL. Schork and J. Gondzio. Maintaining a basis matrix in the linear programming interior point method. Technical Report ERGO-17-009, University of Edinburgh, 2017.en
dc.relation.hasversionL. Schork and J. Gondzio. Permuting spiked matrices to triangular form and its application to the Forrest-Tomlin update. Technical Report ERGO-17-002, University of Edinburgh, 2017.en
dc.relation.hasversionL. Schork and J. Gondzio. Implementation of an interior point method with basis preconditioning. Technical Report ERGO-18-014, University of Edinburgh, 2018.en
dc.relation.hasversionL. Schork and J. Gondzio. Rank revealing Gaussian elimination by the maximum volume concept. Technical Report ERGO-18-002, School of Mathematics, University of Edinburgh, 2018.en
dc.subjectpreconditionersen
dc.subjectnonsingular basis matrixen
dc.subjectrank deficient matricesen
dc.subjectlinear programming interior pointen
dc.subjectinterior point solveren
dc.titleBasis preconditioning in interior point methodsen
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