next up previous contents
Next: Annexes Up: Conclusions Previous: Some advice on how   Contents


The H-norm

The shape of an ideal trust region should reflect the geometry of the model and not give undeserved weight to certain directions.
Perhaps the ideal trust region would be in the H-norm, for which

$\displaystyle \Vert s \Vert _{\vert H\vert}^2 = \langle s, \vert H\vert s\rangle$ (12.3)

and where the absolute value $ \vert H\vert$ is defined by $ \vert H\vert= U \vert\Lambda \vert
U^T$, where $ \Lambda$ is a diagonal matrix constituted by the eigenvalues of $ H$ and where $ U$ is an orthonormal matrix of the associated eigenvectors and where the absolute value $ \vert\Lambda\vert$ of the diagonal matrix $ \Lambda$ is simply the matrix formed by taking absolute values of its entries.
This norm reflects the proper scaling of the underlying problem - directions for which the model is changing fastest, and thus directions for which the model may differ most from the true function are restricted more than those for which the curvature is small.
The eigenvalue decomposition is extremely expensive to compute. A solution, is to consider the less expensive symmetric, indefinite factorization $ H=PLBL^TP^T$ ($ P$ is a permutation matrix, $ L$ is unit lower triangular, $ B$ is block diagonal with blocks of size at most 2). We will use $ \vert H\vert \approx PL\vert B\vert L^TP^T$ with $ \vert B\vert$ computed by taking the absolute values of the 1 by 1 pivots and by forming an independent spectral decomposition of each of the 2 by 2 pivots and reversing the signs of any resulting negative eigenvalues.
For more information see [CGT00g].

next up previous contents
Next: Annexes Up: Conclusions Previous: Some advice on how   Contents
Frank Vanden Berghen 2004-04-19