Results 1 to 4 of 4

Math Help - Programming gradient descent for local minima

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    1

    Programming gradient descent for local minima

    I've been working on a Java program to do gradient descent on 4 different functions.

    This is what I'm doing:
    1. Calculating a step size ( I need to do an adaptive step size, but for now I'm just using a small constant like 0.1).
    2. Calculating the gradient of the function numerically
    3. Multiplying the gradient by the step size
    4. Adding that product to the current point. (i.e. p + \alpha \nabla g where \alpha is step size, p is current point, and \nabla g is numerical gradient of the function.
    5. Repeating until the distance between the points is less than a certain threshold (like 10e-6).


    Now my question is - how do I search for the local minimum and not the global minimum?

    In other words, some of my initial guesses just lead my algorithm to go to negative infinity. How can I tell if it's going to infinity or if going to a local minimum?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie eigenvex's Avatar
    Joined
    Feb 2010
    Posts
    19
    Hmm, gradient descent should find local minima by definition. That's one of it's pitfalls, kinda, that it gets caught in local minima instead of finding the global.

    Did you try using a smaller step size? What kind of functions are you using?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by scskowron View Post
    I've been working on a Java program to do gradient descent on 4 different functions.

    This is what I'm doing:
    1. Calculating a step size ( I need to do an adaptive step size, but for now I'm just using a small constant like 0.1).
    2. Calculating the gradient of the function numerically
    3. Multiplying the gradient by the step size
    4. Adding that product to the current point. (i.e. p + \alpha \nabla g where \alpha is step size, p is current point, and \nabla g is numerical gradient of the function.
    5. Repeating until the distance between the points is less than a certain threshold (like 10e-6).


    Now my question is - how do I search for the local minimum and not the global minimum?

    In other words, some of my initial guesses just lead my algorithm to go to negative infinity. How can I tell if it's going to infinity or if going to a local minimum?
    If your step size is positive, for minimisation you want:

    p_{new}=p_{old} -\alpha \nabla g

    CB
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by eigenvex View Post
    Hmm, gradient descent should find local minima by definition. That's one of it's pitfalls, kinda, that it gets caught in local minima instead of finding the global.

    Did you try using a smaller step size? What kind of functions are you using?
    It does not converge if you start outside the basin of attraction of one of the local minima.

    Consider:

    \mathrm{f}\left( x,y\right)<br />
 :=-\left( {x}^{2}+{y}^{2}\right) -\frac{100}{{x}^{2}+{y}^{2}+1}



    CB
    Attached Thumbnails Attached Thumbnails Programming gradient descent for local minima-gash.png  
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Local Maxima and Minima
    Posted in the Calculus Forum
    Replies: 0
    Last Post: November 12th 2009, 11:04 AM
  2. local maxima and minima
    Posted in the Calculus Forum
    Replies: 6
    Last Post: October 18th 2009, 06:50 PM
  3. Max rate of descent , gradient?
    Posted in the Calculus Forum
    Replies: 0
    Last Post: October 12th 2009, 08:02 PM
  4. Gradient - Steepest Descent
    Posted in the Calculus Forum
    Replies: 2
    Last Post: October 12th 2009, 06:52 PM
  5. Replies: 0
    Last Post: February 16th 2009, 06:36 AM

Search Tags


/mathhelpforum @mathhelpforum