How do I guess an intital step length in a line search (minimization)? I am currently trying to write a "simple" minimizer for a function $y = f(x)$ where $x$ is a multidimensional vector and $y$ is a real number where I have access to the derivate vector.
If I have a search direction ${\bigtriangleup}x$ (i.e. the initial direction will be ${\bigtriangledown_x}f$) I have to perform a line search to obtain a proper step length ($\alpha$) for the next ($n+1$) step.
$$x_{n+1} = x_n + \alpha{\bigtriangleup}x$$
I want to use backtracking line search as a starting point and I think I can handle most of it but my problem is: How do I obtain a reasonable guess for $\alpha$?
All the line search resources I had a look at explain how to do "the actual line search" but only mention that one needs "a first guess" for the step size.
 A: If $f$ is continuously differentiable, then you can apply the Armijo step size rule. An algorithm using this rule looks as follows:


*

*Choose $\alpha, \beta \in (0,1)$ and set $i = 0$. Select an $x_0 \in \mathbb{R}^n$ to start with.

*Compute $h_i = \nabla f(x_i)$. 

*Compute the minimum $k_i \in \mathbb{N}$ such that
\begin{equation}
f(x_i + \beta^{k_i}h_i) - f(x_i) \leq -\alpha\beta^{k_i}\|\nabla f(x_i)\|^2
\end{equation}
Set $\lambda_i = \beta^{k_i}$.

*Set $x_{i+1} = x_i + \lambda_ih_i$, set $i = i + 1$ and go back to step $2$. 


In using this, it is typical to select a stopping rule based on the norm of the gradient, i.e., in Step $2$ if $\|\nabla f(x_i)\| < \epsilon$ (for some $\epsilon > 0$ chosen a priori), then the algorithm should exit. It is also typical to select $\alpha = \beta = 0.5$ and these values often work for many "nice" functions. 
A: This is what I've done, once upon a time, as ( I hope somewhat ) related to your question.
Let there be given a black & white picture $p(x,y)$ where the black pixels
$(x,y)$ are assumed to have function value $p(x,y)=1$ and the white pixels
are assumed to have function value $p(x,y)=0$ . The picture is "fuzzyfied"
by taking the convolution with a two-dimensional Gauss distribution:
$$
   P(x,y) = \frac{1}{2\pi\sigma^2} \iint p(\xi,\eta)\;
   e^{-\frac{1}{2}\left[(x-\xi)^2+(y-\eta)^2\right]/\sigma^2} d\xi\, d\eta
$$
A consequence of this is that the meaning of black & white becomes fuzzyfied, ipse est: gray.
Also take note of the fact that $P(x,y)$ has become a differentiable function now. One
could ask for the maximum value(s) of that function. Which in turn is the same (?) as asking
for the skeleton of a picture. The gist of our method is in the fact that
there exists a relationship between the gradient of $P(x,y)$ and the running mean $(μ_x,μ_y)$ [ the latter is still a function of $x$ and $y$ ] :
$$ P(x,y)\left[ \mu_x - x \right] = \sigma^2 \frac{\partial P}{\partial x} \qquad ; \qquad    P(x,y)\left[ \mu_y - y \right] = \sigma^2 \frac{\partial P}{\partial y} $$
Here is a visualization of the iteration process:   →      →      →   
The iterations will eventually "come to rest" when $x = μ_x$ and $y = μ_y$ .
All references I can come up with (alas): "Programming in Delphi" ( index ) and (
2004 ) .
