In the previous post we saw that the "smallest" update to a matrix so that it satisfies a given linear constraint is a rank-1 update. However, the updated matrix may lose it symmetric and positive definite characteristics. In this post we will find a matrix update that maintains the symmetric nature of the matrix and we will stick to a rank-1 update.
A symmetric rank-1 update can be expressed as \(\alpha xx^T\) where \(x\) is some vector and \(\alpha\) is \(\pm 1\). So, compared to our previous post, instead of the matrix \(X\) we have this symmetric rank-1 update and we still have the same constraint, namely,
\[ \alpha xx^T a = b\]
which can be rewritten as
\[ \alpha \left( x^Ta \right) x = b\]
and straightaway tells us that \(x\) is linearly dependent on \(b\). Plugging, \(x=\beta b\) into the original constraint we get:
\[ \alpha \beta^2 (b^Ta) b = b\]
which implies that
\[ \alpha \beta^2 = \frac{1}{b^Ta} \]
giving us our symmetric rank-1 update as \(\frac{bb^T}{b^Ta}\). Mapping, the symbols back to the original problem we get:
\[J'_n = J'_{n-1} + \frac{ (\Delta f - J_{n-1}x_{n-1})(\Delta f - J_{n-1}x_{n-1})^T}{(\Delta f - J_{n-1}x_{n-1})^T(\Delta x)}\]
This update is known by the TLA SR1 (Symmetric Rank-1 update) and is the update for a symmetric rank-1 update that satisfies the secant condition. Depending on the sign of the denominator this update may or may not be positive definite. Since SR1 was a result of just requiring the update to be symmetric and rank-1 and no other constraint we cannot hope to obtain a symmetric positive definite rank-1 update that satisfies the secant condition. We will again use the approach of Part I and look for a "smallest" update that gives us both symmetry and positive definiteness and we will end up with a rank-2 update and the famous DFP and BFGS formulas.
A symmetric rank-1 update can be expressed as \(\alpha xx^T\) where \(x\) is some vector and \(\alpha\) is \(\pm 1\). So, compared to our previous post, instead of the matrix \(X\) we have this symmetric rank-1 update and we still have the same constraint, namely,
\[ \alpha xx^T a = b\]
which can be rewritten as
\[ \alpha \left( x^Ta \right) x = b\]
and straightaway tells us that \(x\) is linearly dependent on \(b\). Plugging, \(x=\beta b\) into the original constraint we get:
\[ \alpha \beta^2 (b^Ta) b = b\]
which implies that
\[ \alpha \beta^2 = \frac{1}{b^Ta} \]
giving us our symmetric rank-1 update as \(\frac{bb^T}{b^Ta}\). Mapping, the symbols back to the original problem we get:
\[J'_n = J'_{n-1} + \frac{ (\Delta f - J_{n-1}x_{n-1})(\Delta f - J_{n-1}x_{n-1})^T}{(\Delta f - J_{n-1}x_{n-1})^T(\Delta x)}\]
This update is known by the TLA SR1 (Symmetric Rank-1 update) and is the update for a symmetric rank-1 update that satisfies the secant condition. Depending on the sign of the denominator this update may or may not be positive definite. Since SR1 was a result of just requiring the update to be symmetric and rank-1 and no other constraint we cannot hope to obtain a symmetric positive definite rank-1 update that satisfies the secant condition. We will again use the approach of Part I and look for a "smallest" update that gives us both symmetry and positive definiteness and we will end up with a rank-2 update and the famous DFP and BFGS formulas.
No comments:
Post a Comment