Matrix Factorizations, Triadic Matrices, and Modified Cholesky Factorizations for Optimization

Simple item page
dc.contributor.advisorO'Leary, Dianne Pen_US
dc.contributor.authorFang, Haw-renen_US
dc.contributor.departmentComputer Scienceen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.date.accessioned2006-09-12T06:00:27Z
dc.date.available2006-09-12T06:00:27Z
dc.date.issued2006-08-07en_US
dc.description.abstractThis thesis focuses on the Cholesky-related factorizations of symmetric matrices and their application to Newton-type optimization. A matrix is called triadic if it has at most two nonzero off-diagonal elements in each column. Tridiagonal matrices are a special case of these. We prove that the triadic structure is preserved in the Cholesky-related factorizations We analyze its numerical stability and also present our perturbation analysis. Newton-like methods solve nonlinear programming problems whose objective function and constraint functions are twice continuously differentiable. At each iteration, a search direction is computed by solving a linear symmetric system Ax=b. When A is not positive definite, the computed search direction may not be a descent direction. Modified Newton methods add a perturbation E to A, so that A+E is positive definite, where E is symmetric positive semidefinite. We study the modified Newton methods in the literature, and develop other stable and efficient algorithms. One of them exploits the merits of triadic structure. We apply our modified Newton methods to the Euclidean distance matrix completion problem (EDMCP). Given n points in Euclidean space, the Euclidean distance matrix (EDM) is the real symmetric matrix with (i,j) entry being the square of the Euclidean distance between i-th and j-th points. Given a partial Euclidean distance matrix (i.e., some entries are not specified), the EDMCP is to find a EDM that includes the specified entries. We tackle the EDMCP by transforming it into a global optimization problem and applying modified Newton methods. We also develop a dimensional relaxation method for global minimization and test it on sample problems including protein structure prediction.en_US
dc.format.extent1162457 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/3891
dc.language.isoen_US
dc.subject.pqcontrolledComputer Scienceen_US
dc.subject.pqcontrolledComputer Scienceen_US
dc.subject.pquncontrolledCholesky Factorizationen_US
dc.subject.pquncontrolledBackward Error Analysisen_US
dc.subject.pquncontrolledTridiagonal Matricesen_US
dc.subject.pquncontrolledModified Newton Methodsen_US
dc.subject.pquncontrolledInterior Point Methodsen_US
dc.subject.pquncontrolledDistance Matrix Completion Problemsen_US
dc.titleMatrix Factorizations, Triadic Matrices, and Modified Cholesky Factorizations for Optimizationen_US
dc.typeDissertationen_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
umi-umd-3739.pdf
Size:
1.11 MB
Format:
Adobe Portable Document Format
Download

Collections

UMD Theses and Dissertations
Computer Science Theses and Dissertations