2
$\begingroup$

Why does Steepest Descent converge? I know that will be take the objective $f$ and walk it through direction $-\nabla f$ with step size $\alpha_k$ but step size seems able to be negative and it does the function walk to maximum direction intead minimum.

Look at:

$x_{k+1}=x_{k}+\alpha_{k}d_k$

Where:

$\alpha_k=argmin_{\alpha}f(x_{k}+\alpha.d_k)$

$d_k=-\nabla f(x_k)$

There is no any reason in the math to $\alpha_k$ always be greater than 0.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

$\alpha_k$ being greater than zero is a precondition; for example, see the Wikipedia article that uses $\gamma$ as your $\alpha_k$.

for a $\gamma \in \mathbb{R}_+$ small enough, then $F(\mathbf{a_n}) \geq F(\mathbf{a_{n+1}})$...

If $\alpha_k$ were negative, you'd recover steepest ascent. (Traditionally, you'd treat this as a positive $\alpha_k$ and use $+\nabla f(x_k)$ for $d_k$.)

Improve this answer
$\endgroup$
3
  • $\begingroup$ Set $d_k=\nabla f(x_k)$ if $\alpha_k>0$ it would solve the problem but that approach doesn't belong to algorithm. I would like to proof the convergence of Steepest Descent as i've mentioned where $\alpha_k=argmin_{\alpha}f(x_k+\alpha.d_k)$ and $d_k$ is always negative gradient of $f$. $\endgroup$
    – Davi Américo
    Commented May 8, 2021 at 4:34
  • $\begingroup$ No, it wouldn’t solve the problem. I think you’ve copied down the algorithm wrong; where is $\alpha$‘s domain defined? $\endgroup$
    – Arya McCarthy
    Commented May 8, 2021 at 14:34
  • $\begingroup$ $\alpha_k$ is real valuated, I've copied this one from (Robert M. Freund 2004) and (Juan C. Meza 2010) $\endgroup$
    – Davi Américo
    Commented May 8, 2021 at 20:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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