0
$\begingroup$

I am studying line search methods and I stumbled upon the "backtracking algorithm" for calculating a step length $a_k$ that gives a sufficient decrease in our function. To actually compute this sufficient decrease, we use the first Wolfe condition, which is as follows :

$$f(x_k + ap_k) \leq f(x_k) + ca \nabla f_k^Tp_k, c \in (0,1)$$

The backtracking algorithm says: Start with an arbitrary positive $a$. While the above equation isn't true, substitue $a$ with a smaller value, i.e. $$a \leftarrow ρ a$$ where $ρ \in (0,1)$. When we reach a value for $a$ for which the above inequality is satisfied, the algorithm stops.

I have a question that is of a more intuitive nature I think. Why do we make $a$ smaller at every iteration ? Why not make it bigger? If we are talking about a simple convex function like $f(x)=x^2$, I think I can justify the decrease of $a$. But consider the following graph enter image description here

You see that small values of $a$ are acceptable, then there is an interval for which we can't accept $a$ and the finally another interval of acceptable values. If our first estimation of $a$ falls in the interval of non acceptable values, can't we just increase it's value so it goes to the next interval of acceptable values? Because according to the backtracking algorithm, if we land in an non acceptable value of $a$, we will make smaller and smaller until if enters the first acceptable area.

Is there a reason that we want $a$ to be small and we avoid to make it bigger? Or is it because this particular graph isn't convex ? Not sure.

Sorry if my thoughts are a bit jumbled. Thanks in advance.

Note : Picture is taken from "Numerical Optimization, Nocedal & Wright".

$\endgroup$

1 Answer 1

1
$\begingroup$

If we increase $a$, we do not know if this will ever result in a valid choice. There is no guaranty for finding another valley farther away from where we are.

But we can be sure that we will find a point below the line $l$ if only we make $a$ small enough. This is because $c\in(0,1),$ which means that $\phi$ is steeper than $l$ at $a=0.$

EDIT: Why can we be sure that we will find a suitable $a$ with $\phi(a)<l(a)$?

Let $g(a)=l(a)-\phi(a).$ Then $g(0)=f(x_k)-f(x_k)=0$ and $g'(0)=(c-1)(\nabla f_k^T p_k)>0,$ because $c-1<0$ and $\nabla f_k^T p_k<0.$

We have $$ g'(0)=\lim_{a\to 0}\frac{g(a)-g(0)}{a-0} = \lim_{a\to 0}\frac{g(a)}{a} $$ From the definition of $\lim$: For each $\varepsilon>0$ there is a $\delta>0$ such that $$ |a-0|<\delta \;\Rightarrow \; \left|\frac{g(a)}{a}-g'(0)\right|<\varepsilon $$ Now set $\varepsilon=\frac12 g'(0)$ and set $\delta$ accordingly, such that the aforementioned implication holds. Then $$ 0<a<\delta \;\Rightarrow\; g'(0)-\frac 12 g'(0) < \frac{g(a)}{a} < g'(0)+\frac 12 g'(0) \\ \;\Rightarrow \; \frac 12 g'(0) < \frac{g(a)}{a} \;\Rightarrow \; g(a) > \frac a2 g'(0) >0 $$

$\endgroup$
10
  • $\begingroup$ Thank you ! I have 2 questions. 1) So the graph I posted having a 2nd acceptable interval is coincidental, and noone can guarantee us that it will actually exist? 2) Regarding you 2nd statement. Is this true because we have chosen a descent direction, meaning that at least for small values of $a$, $φ$ will decrease for sure, like in the graph? Of course for large steps we dont know what will happen for sure, but for small values of the step, the function $φ$ is guaranteed to decrease right? $\endgroup$
    – Thomas
    Commented Nov 15, 2019 at 14:54
  • $\begingroup$ Correct. It is exactly like that. But in order to stay below $l,$ it is not enough to have a descent direction, we also need that $l$ is not as steep as $\phi.$ Therefore we allow $c$ to be in $(0,1)$, only. $\endgroup$ Commented Nov 15, 2019 at 14:58
  • 1
    $\begingroup$ The steepness is not the same at $a=0.$ It differs by a factor of $c.$ And we set the value $c.$ It is a parameter of the algorithm. $l-\phi$ is differentiable and we have $(l-\phi)(0)=0$ and $(l'-\phi')(0)=(c-1)(\nabla f_kp_k)>0.$ Therefore, we can be sure that there is a $\delta>0$ with $(l-\phi)(\delta) > 0.$ $\endgroup$ Commented Nov 15, 2019 at 16:04
  • 1
    $\begingroup$ @Thomas I have added the required explanations to the answer. $\endgroup$ Commented Nov 16, 2019 at 11:03
  • 1
    $\begingroup$ They are correct and probably helpful for the intuition, but not sufficient for a proof. $\endgroup$ Commented Nov 16, 2019 at 11:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .