1
$\begingroup$

First i have searched this forum but could not find a question that matched mine, though some are somewhat similar.

my issue is whether or not the signage matters when i try to calculate the optimum step size for the gradient descent method.

for gradient descent, the equation is given as, eqn 1, $$x_{k+1} = x_{k} - \alpha\nabla f(x_{k}) $$ for gradient ascent, the equation is given as, eqn 2, $$x_{k+1} = x_{k} + \alpha\nabla f(x_{k})$$

where $\alpha$ is the step size.

Using exact line search for a quadratic function, I get 2 different signages for the optimum step size depending on whether I use eqn 1 or eqn 2.

for a quadratic given by, $$f(X)=\frac{1}{2} X^TQX+B^TX + C$$ and Q is positive definite.

Then I will end up with, $$\alpha^*=-\frac{(\nabla f(x_{k}))^T\nabla f(x_{k})}{(\nabla f(x_{k}))^TQ\nabla f(x_{k})}$$ when using eqn1 and $$\alpha^*=\frac{(\nabla f(x_{k}))^T\nabla f(x_{k})}{(\nabla f(x_{k}))^TQ\nabla f(x_{k})}$$ when deriving using eqn 2.

MY QUESTION: Does the sign matter? Why do I end up with 2 different signs. Should I just take the absolute value for the step size. Then, if for example I am using gradient descent, I can susbsitute the absolute value for the optimum step size in to eqn 1, $x_{k+1} = x_{k} - \alpha\nabla f(x_{k}) $

pls help!!

$\endgroup$
  • $\begingroup$ In general I would use $$x_{k+1} = x_{k} + \alpha\nabla f(x_{k})$$ If it is an descent then $\nabla f(x_{k})$ will be negative. The formula is just a version of the linear approximation, see here. $\endgroup$ – callculus Mar 16 at 16:30
  • $\begingroup$ Thanks, i agree regarding taylor thoerem. However, lets say i evaluate $\nabla f(x_{k})$ as you suggest, this will point in the direction of the greatest increase of $f$ (i.e., ascent). For any choice of $\alpha$, I would assign a negative value to it. But if I want to find the optimum step length for a given step, for a quadratic, I would end up with an expression which is negative for $\alpha$. How can we explain that? Do we just ignore that negative sign and only care abouts its magnitude? $\endgroup$ – the1andonly Mar 16 at 18:36
  • $\begingroup$ You´re welcome. $\endgroup$ – callculus Mar 16 at 18:36
  • $\begingroup$ sorry, i didnt realise pushing enter would add the comment. i was hoping to add a new line. eek! im still confused. thanks for reading my post and commenting though, i appreciate it $\endgroup$ – the1andonly Mar 16 at 18:43
  • $\begingroup$ For me is not clear how you´ve obtained $\alpha^*$. What is the underlying equation? $\endgroup$ – callculus Mar 16 at 18:51
0
$\begingroup$

Say you are at iteration $k$ with $x_{k}$. Now, you define your descent step $x_{k+1} = x_{k} - \alpha\nabla f(x_{k}),$ with $\alpha > 0$ (otherwise, it would be an ascent step). Sub this in $f(X)=\frac{1}{2} X^TQX+B^TX + C$, you get a second order polynomial in $\alpha$, say $g(\alpha)$. As $Q$ is positive definite, the minimum for $g$ is reached at $g'(\alpha) = 0, $ which is, from your calculation, $$\alpha^*=\frac{(\nabla f(x_{k}))^T\nabla f(x_{k})}{(\nabla f(x_{k}))^TQ\nabla f(x_{k})}.$$ As expected $\alpha^*>0.$

$\endgroup$
  • $\begingroup$ Thanks, I understand the logic. Can you show your steps please? $\endgroup$ – the1andonly Mar 18 at 11:07

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.