Results 1 to 1 of 1

Thread: Escaping from a saddle point

  1. #1
    Apr 2009

    Escaping from a saddle point


    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 $\displaystyle x_i$ and look at the value $\displaystyle \mathbf x_i^T H \mathbf x_i$, where H is the Hessian matrix. If I find a negative value, I use the vector $\displaystyle \mathbf x_i$ 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:
    $\displaystyle \mathbf x^T H \mathbf x = \sum_k \lambda_k (\mathbf u_k^T \mathbf x)^2$
    where $\displaystyle \lambda_k$ and $\displaystyle \mathbf u_k$ are the eigenvalues and corresponding eigenvector of H. So if $\displaystyle \mathbf x$ 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 ?


    Last edited by AlexisM; Dec 9th 2011 at 03:09 AM. Reason: cleaning notations
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Using eigenvectors to determine nature of saddle point
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Nov 13th 2011, 05:04 AM
  2. Local Minimum and Maximum; Saddle Point
    Posted in the Calculus Forum
    Replies: 5
    Last Post: Oct 25th 2010, 08:37 PM
  3. Critical point and Saddle Point Question
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: Nov 21st 2009, 08:32 AM
  4. maxima, minima, saddle point problem
    Posted in the Calculus Forum
    Replies: 3
    Last Post: Sep 5th 2008, 02:27 PM
  5. saddle point
    Posted in the Calculus Forum
    Replies: 1
    Last Post: May 7th 2008, 08:48 AM

Search Tags

/mathhelpforum @mathhelpforum