linear algebramatricesnonlinear optimizationoptimization
I'm reading about the Newton Algorithm for optimization, and when the hessian is not positive definite, it says that I can add a matrix $E_k$ such that $B_k = \nabla^2 f(x_k) + E_k$ is sufficiently positive definite. What does that mean? How does $E_k$ looks like?
If you take the matrix $A$ with entries $ A_{kj} = g_j(x_k) $ then $A$ should be invertible from linear independence of $g_i$s and you have entries of Hessian assuming your calculation as $$ H_{ij} = \frac{\partial^2 G}{\partial \beta_i\partial \beta_j} = 2 \sum_{k=1}^n A^T_{ik} A_{kj} $$ Hence $ H = 2A^T A $ which is always positive definite for invertible $A$.
I found a good example:
$f(x_1,x_2)=(1.5-x_1+x_1*x_2)^2 + (2.25-x_1+x_1*x_2^2)^2 + (2.625-x_1+x_1*x_2^3)^2$
Dampted Newton method with starting point $x_0 = (4,1)^T$ fails. This is why:
$\nabla^2 f(x_0)= \left( \begin{matrix} 0 & 27.75 \\ 27.75 & 610 \\ \end{matrix} \right) $ and search direction is $p_0=-\nabla^2 f(x_0)*\nabla f(x_0)=(-4,0)^T$
The search direction is pointing to a wrong direction! and this is because Hessian matrix is not positive definite and thus $p_0$ is not in the descent direction.
After using the Hessian modification technique such as "adding a multiple of the identity", the algorithm works fine and the search direction points to the corect direction, and eventually finds the local minimum $(3,0.5)^T$
Best Answer
There are lots of ways of constructing $E_{k}$. One simple approach would to be to add a small positive multiple of the identity matrix, $\alpha I$, to $B_{k}$. This shifts the eigenvalues of $B_{k}$ to the right by $\alpha$, which will ensure that the perturbed matrix is positive definite.
A variety of more sophisticated approaches that try to make $E_{k}$ as small as possible have been developed over the years. These are typically incorporated into an algorithm that computes a Cholesky factorization of the perturbed matrix, dynamically adjusting the perturbation in response to the values encountered during the Cholesky factorization.
A recent master thesis on this topic is: Thomas McSweeney. Modified Cholesky Decomposition and Applications. Manchester Institute of Mathematical Sciences, 2017.