1

I have to read up in convex optimization - and at the moment I stuck at inexact line search. The method of exact linesearch (like golde section, etc.) is pretty obvious and I have an "graphical idea". But with inexact line search, I have a problem with this "graphical idea": Armijo rule

Could anyone explain this graphic for a "nonmathematicians" :) The idea in exact line search is the following rihgt: I start at the current point (for example: direction is $-\nabla f(p)$: in this picture the green curve right?) then i would go in the green direction until the function value is decreasing.

edit: are the green and the blue lines directional derivative?

lars111
  • 321
Kenni
  • 171
  • 1
  • 9

1 Answers1

0

I think your idea of exact line-search is not correct. Let's have an example in $R^2 \rightarrow R$: Your function $f(x,y)$ looks like a "mountain / "flying carpet". Let's assume that we use steepest descent for finding the direction at point $(x0,y0)$. The gradient of a function points not "uphill" or "downhill", he points at the plain in the direction of greatest increase.

We now know, in which direction (downhill) we want to go; but not if "1cm or 100km".Therefore we use "line search-methods". Let's assume we want to go maximum 10(meter) and minimum 1(meter). A realy simple method (uniform search) would be to divide this intervall into steps (let's assume 10 steps).

Picture: Mountain (= function) and a plane with arrows (=gradients). We are at a special point $(x0,y0)$ on the mointain - and on this point is an "arrow", which points parallel to the x,y plane. In our case, that arrow is 10 (meter) long (because this is our assumend intervall).

Now we want to calculate $f(x,y)$ at all "10 steps". Example: $(x0,y0) = (1,1); direction =(3,2), stepsize = 1: (x1,y1)= (x0,y0) + stepsize*direction= (1,1) + 1*(3,2) = (4,3)$ Now you can evaluate the function $f(x1,x2)...f(x10,y10)$ and take the point, where the function has its minimum value as a new starting point.

lars111
  • 321