A directed Cholesky factorization of a symmetric interval matrix \A consists of a permuted upper triangular matrix R such that for all symmetric A \in \A, the residual matrix A - R^T R is positive semidefinite with tiny entries. This must holds with full mathematical rigor, although the computations are done in floating-point arithmetic. Similarly, a directed modified Cholesky factorization of a symmetric interval matrix \A consists of a nonsingular permuted upper triangular matrix $R$ and a non-negative diagonal matrix D such that for all A \in \A the residual matrix A + D - R^T R is positive semidefinite with tiny entries. The paper shows how to construct a directed modified Cholesky factorization with the additional property that the entries of D are tiny, too, if \A is nearly positive definite, and they are zero for numerically positive definite matrices. The construction is based on an improved version of the directed Cholesky factorization of Domes & Neumaier, which performs better on nearly singular positive definite matrices. The improved method also allows one to select a set of columns which are eliminated before the other columns are processed. If the factorization fails, but the selected part was successfully processed an incomplete factorization is returned, needed for the new modified factorization. For the new factorizations and relaxation methods detailed algorithms are given. Directed rounding or interval computations are used to make sure that the methods are rigorous in spite of the use of floating point arithmetic. As application, new techniques are given for pruning boxes in the presence of an additional quadratic constraint, a problem relevant for branch and bound methods for global optimization and constraint satisfaction. Using either the improved directed Cholesky or the directed modified Cholesky factorization, a convex quadratic relaxation is created and an improved box enclosing the set of points in the original box satisfying the relaxed constraint. If the quadratic constraint is strictly convex and the box is sufficiently big, the relaxation and the enclosure are optimal up to rounding errors. Numerical test show the usefulness of the new factorization methods in the context of pruning.
Citation
University of Vienna, 2014
Article
View Directed modified Cholesky factorizations and convex quadratic relaxations