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

Abstract

This 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.