This set of codes compute Cholesky factorizations of real symmetric matrices, modified if necessary to make them positive definite. We have included implementations of modified Cholesky algorithms gmw81, gmw1, gmw2, se90, se99, and se1. They differ in how they compute the modification.

To be precise, given a symmetric matrix A, each algorithm produces output matrices L, P, and E, so that

P(A+E)P^T = LL^T,

where P is a permutation matrix for pivoting, L is lower triangular, and E is the modification.

In practice, for non-convex optimization, the se90 algorithm is not generally stable, whereas the other 5 algorithms work fine and recommended.

• Why modified Cholesky factorizations?
• How to install?
• How to use?
• The 1+33 test matrices
• Matlab/Octave mex interface
• Modified Newton methods for unconstrained optimization

To minimize a function f : ℝⁿ → ℝ by Newton's method, we solve a linear system Ax = b for the search direction at every iteration, where A ∈ ℝ^n × n is the Hessian matrix and b ∈ ℝⁿ is the negated gradient.

The Hessian matrix A is symmetric under the assumption that second partial derivatives of the objective function f are continuous. Moreover, A is symmetric positive definite (SPD) and the search direction from solving Ax = b is descent, if the objective function f is strictly convex. Coupled with line search for globalization, Newton's method is guaranteed to converge to the minimum, which is unique and hence global due to convexity.

When the objective function f is not convex, the Hessian A may be indefinite, and Netwon's direction may not be descent. As a result, convergence to a minimum is no longer guaranteed. A modified Cholesky algorithm perturbs A to be a positive definite A + E to ensure a descent search direction and therefore the convergence to a local minimum.

Note that modified Cholesky factorizations are useful not only for unconstrained non-convex optimization, but also for constrained optimization with a non-convex objective by interior point methods.

$ cd ./drivers
$ make

It should build an archive file ./source/libmchol.a and then executable ./drivers/gmw and ./drivers/se.

Run gmw without arguments, and a help message should print. It takes input/output matrices in matrix-market format (mtx file).

Here is an example.

$ cd data/mtx
$ ../../drivers/gmw -gmw81 FIRST.mtx L.mtx -P=P.mtx -E=E.mtx

Here FIRST.mtx is the input matrix. We should get the Cholesky factor L stored in L.mtx, the permutation matrix P stored in P.mtx, and the modification matrix E stored in E.mtx.

For Matlab/Octave users, a Matlab/Octave script to read mtx files is here:

http://math.nist.gov/MatrixMarket/mmio/matlab/mmread.m

There are 1+33 matrices are used for testing the modified Cholesky algorithms in the se99 paper and our 2008 paper (see reference). The se99 paper refers to:

Robert B. Schnabel and Elizabeth Eskow, "A Revised Modified Cholesky Factorization Algorithm," SIAM J. Optim., Vol. 9 No. 4, 1135-1148, 1999.

The 1+33 matrices are provided in 2 format, mtx and csv, in directories ./data/mtx/ and ./data/csv/.

The test results of the 1+33 test matrices can be found in the following folders ./tests_mtx/ and ./tests_csv/, parallel to each other. In ./tests_mtx/, the factorizations are performed by the executable files under ./drivers/ and the matrix files are in mtx (matrix-market) format. In ./tests_csv/, the factorizations are performed by the mex files under ./mex/ and the matrix files are in csv format. See ./tests_mtx/README.txt and ./tests_csv/README.txt for more information.

We provide an Matlab/Octave mex interface such that the 6 modified Cholesky algorithms can be invoked directly in Matlab/Octave. Go to ./mex/ and under Matlab/Octave, execute make for the 6 mex files of the 6 algorithms. See ./mex/README.txt for more information.

In ./opt/, we provide Matlab/Octave m-files for the modified Newton methods for unconstrained optimization with examples. It requires the mex files under ./mex/. See ./opt/README.txt for more information.

Questions, comments, and complaints, send us email:

• Hawren Fang, hrfang (at) yahoo (dot) com
• Dianne P. O'Leary, oleary (at) cs (dot) umd (dot) edu

Haw-ren Fang and Dianne O'Leary, "Modified Cholesky Algorithms: A Catalog with New Approaches," Mathematical Programming, Series A, Vol. 115, No. 2, pp. 319--349, 2008. preprint