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.

• How can you get a reasonable answer with this meager amount of information ? Would you please elaborate a bit more for those who are willing to help eventually ? To be specific: what sort of thing is $f$ ? Dec 18 '13 at 21:15
• @HandeBruijn $f$ is a continuous function with N (dimensionality of $x$) parameters. I'm sorry if my question is not perfect. Just tell me what kind of information is missing. Dec 19 '13 at 0:27

If $f$ is continuously differentiable, then you can apply the Armijo step size rule. An algorithm using this rule looks as follows:

1. Choose $\alpha, \beta \in (0,1)$ and set $i = 0$. Select an $x_0 \in \mathbb{R}^n$ to start with.
2. Compute $h_i = \nabla f(x_i)$.
3. Compute the minimum $k_i \in \mathbb{N}$ such that $$f(x_i + \beta^{k_i}h_i) - f(x_i) \leq -\alpha\beta^{k_i}\|\nabla f(x_i)\|^2$$ Set $\lambda_i = \beta^{k_i}$.
4. 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.

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 ) .

• That one sounds very nice. Did you publish any papers or is there any source for a detailed description of this method? Dec 21 '13 at 0:35
• I've added a few lines to my answer according to your request. I know it's not satisfactory, but the theory is in the program and the source code of that program is free. It's 9 years ago and my memory is somewhat rusty. Dec 21 '13 at 20:21