1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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$ ? $\endgroup$ Dec 18 '13 at 21:15
  • $\begingroup$ @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. $\endgroup$ Dec 19 '13 at 0:27
3
$\begingroup$

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 \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}$.
  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.

$\endgroup$
2
$\begingroup$

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:
enter image description here  →   enter image description here   →   enter image description here   →   enter image description here

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

$\endgroup$
2
  • $\begingroup$ That one sounds very nice. Did you publish any papers or is there any source for a detailed description of this method? $\endgroup$ Dec 21 '13 at 0:35
  • $\begingroup$ 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. $\endgroup$ Dec 21 '13 at 20:21

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.