Thread: Escaping from a saddle point

Hi,

I have an minimization problem in which by construction I sometimes need to start from a saddle point. To escape from this saddle point a possible solution would be to take as a descent direction the direction pointed by the eigenvector associated to the smallest negative eigenvalue of the Hessian matrix. This is unfortunately very computationally expensive.

To find a "good" direction I thought of drawing random unit vectors and look at the value , where H is the Hessian matrix. If I find a negative value, I use the vector as a descent direction and I know it's a good escape direction other wise i take the one with the smallest value and just test if i can minimize more.

My intuition that it might work is based on the fact that:

where and are the eigenvalues and corresponding eigenvector of H. So if lies mostly in the subspace corresponding to the negative eigenvalues, i will get a negative or at least a small value and x is a good direction.

Does any one knows about some useful references about this approach ?
Or any useful comment ?

Thanks

Alexis