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?
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.