Optimization: principles and algorithms, by Michel Bierlaire
modifiedCholesky.m
Go to the documentation of this file.
1 %> \file
2 %> Algorithm 11:7: Modified Cholesky factorization. Implementation of algorithm 11.7 of \cite Bier17-book. This implementation is far from efficient, and is designed for illustrative purposes only. Implementations suggested by \cite fang2008modified and \cite SchnEsko99, for instance, should be preferred.
3 %>
4 %> @author <a href="http://people.epfl.ch/michel.bierlaire">Michel Bierlaire</a>
5 %> @date Sat Mar 21 12:28:56 2015
6 %> @ingroup Algorithms
7 %> @ingroup chap11
8 
9 %> \note Tested with \ref runModifiedCholesky.m
10 %> \note Called by \ref newtonLineSearch
11 
12 
13 %> Given a symmetric matrix \f$ A\in \mathbb{R}\times \mathbb{R}\f$, provide a lower triangular matrix \f$L\f$ and a real \f$\tau\f$ such that \f[ A + \tau I = L L^T.\f]
14 %> @param A symmetric matrix \f$n \times n \f$.
15 %> @return [L, tau]
16 %> @return L: lower triangular matrix \f$L\f$
17 %> @return tau: real \f$\tau\f$ such that \f$ A + \tau I = L L^T.\f$
18 function [L, tau] = modifiedCholesky(A)
19  tau = 0.0 ;
20  [m,n] = size(A) ;
21  if (m != n)
22  error("Matrix must be square. Size %dx%d",m,n) ;
23  endif
24  nf = norm(A,"fro") ;
25  if (nf <= 1.0e-6)
26  nf = 1.0e-6 ;
27  endif
28 
29  mindiag = min(diag(A)) ;
30 
31  if (mindiag > 0)
32  tau = 0 ;
33  R = A ;
34  else
35  tau = nf ;
36  R = A + tau * eye(n,n) ;
37  endif
38 
39  mineig = min(eig(R)) ;
40 
41  while (mineig <= 0)
42  tau = max([2 * tau, 0.5 * nf]) ;
43  R = A + tau * eye(n,n) ;
44  mineig = min(eig(R)) ;
45  endwhile
46  L = chol(R,"lower") ;
47  return
48 
49 endfunction
function newtonLineSearch(in obj, in x0, in eps, in printlevel)
Applies Newton&#39;s algorithm with line search to solve where .
function modifiedCholesky(in A)
Given a symmetric matrix , provide a lower triangular matrix and a real such that ...
Copyright 2015-2016 Michel Bierlaire