1
$\begingroup$

In general setting of steepest descent algorithm we have,

\begin{equation} x_{n+1}=x_n-\alpha G_n, \end{equation}

where $\alpha$ is the step size and $G_n$ is the gradient evaluated at the point $x_n$.

I was trying to write a simple algorithm performs the gradient descent method but I get confused how to select the step size.

I know that if I am going to use normalized gradient descent I will get rid of the magnitude (always 1 by definition) and it will just give us the optimal direction to move. If I used this method with a fixed step the speed of convergence will be extremely large.

I read that it doesn't matter whether we use the normalized or unnormalized gradient but what really matters is how the step size $\alpha$ is selected.

My question is how do I select the step size? Or how do I select the step size depending on steepness? Any suggestion would be greatly appreciated.

$\endgroup$
1
$\begingroup$

If your gradient is Lipschitz continuous, with Lipschitz constant $L>0$, you can let the step size be $\alpha\leq\frac{1}{L}$ (you want equality, since you want an as large as possible step size). This is guaranteed to converge from any point with a non-zero gradient.

Update: At the first few iterations, you may benefit from a line search algorithm, because you may take longer steps than what the Lipschitz constant allows. However, you will eventually end up with a step $\alpha\leq\frac{1}{L}$.

$\endgroup$
  • $\begingroup$ I am not familiar with the concept of Lipschitz to be honest. Any simple suggestion how to let the magnitude of the gradient decide the step size? $\endgroup$ – user161260 Apr 9 '15 at 10:52
  • 2
    $\begingroup$ I'm not sure what you mean by selecting the step size base on steepness. The Lipschitz constant is an upper bound on how fast the gradient changes, and so takes the "steepness" into account. The Armijo (and the Wolfe) conditions in backtracking line search uses the gradient, and thus takes the "steepness" in account. Are you trying to work out some new condition of your own instead of using the proved and time tested approaches? $\endgroup$ – Tommy L Apr 9 '15 at 11:00
  • $\begingroup$ No, I am not trying to work out some new condition. I am new in the area of optimization that's why I am asking which conditions people used to use in their algorithms. I tried to read the theory behind these conditions but I am trying to find a source code maybe of steepest descent to see how people use these conditions in their algorithms. It happens to know how to find out the source code of steepest descent? $\endgroup$ – user161260 Apr 10 '15 at 7:55
  • $\begingroup$ The source code depends entierly on what language you are implementing this in. Gradient descent is really simple to implement and you wrote the pseudo code in your question. $x_{n+1}$, $x_n$ and $G_n$ are vectors, so you'll need a matrix library. In e.g., Matlab and R this is available out-of-the-box, for Python you have it in NumPy and SciPy. $G_n$ and $L$ depends on your problem, so you'll have to work them out yourself. $\endgroup$ – Tommy L Apr 13 '15 at 7:08
  • 1
    $\begingroup$ Sorry, I should've used your notation, in which $\nabla f(x_n)=G_n$. Note that $p_n=-G_n$ (its negative!), so $p_n^TG_n=-G_n^TG_n<0$. I have assumed that $x_n$ is a vector, so $\nabla f(x_n)=G_n$ is the gradient at $x_n$. $\endgroup$ – Tommy L Apr 14 '15 at 9:03
0
$\begingroup$

What you want to be looking at is Line Search algorithms. One of the simplest ones, Backtracking line search will start with a large step size and iteratively shrink it, according to the observed decrease in the objective function.

$\endgroup$
  • $\begingroup$ Well, that's something that I already tried. In case the $x_{n+1} > x_n$ then repeat the process by halving the step size until $x_{n+1} < x_n$. But I wanted to add a controlling power regarding the steepness. I am interested to know how to make the step size depending on steepness. $\endgroup$ – user161260 Apr 9 '15 at 9:49
0
$\begingroup$

for getting optimum step size multiply a factor a in step size and repeat multiply with same factor untill unless your new calculated value of function is equal or greater then old value of function (Woolfe's first criteria). If new value of function is less than old one then stop multiplying the factor and this will be your new step size with proper magnitude.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.