Local search worst case

Question

So we have a function f(u) over a lattice cube $\{0, 1, ..., n-1\}^3$ and you need to find a local minimum. A simple algorithm would be the following: start at position $u_0 = (0, 0, 0)$, and repeatedly, if $u_i$ is not a local minimum of f (x) then move to a neighbor $u_{i+1}$ with $f(u_{i+1}) < f (u)$. In the notes for my class, it's stated that in the worst case this can take $n^3$ steps, but I can't think of any examples where this would be the case.

I suppose that we could have a cube where the global and only minimum is at $(n-1, n-1. n-1)$ but even in that case, I'm confused as we're later told in our notes that there are deterministic algorithms that solve in $O(n^2)$ time, so it seems my example is flawed. What would be a situation where this would take at least $n^3$ time?

Answer 1

It's easy to construct examples on which the simple algorithm takes $n^3$ steps: just trace out an arbitrary path that visits every point in the lattice, and assign the points $f$-values of $n^3, n^3-1, \dots, 3, 2, 1$ according to the order in which they appear along the path.

Then it's possible for your algorithm to start at the first point of the path and then trace out the entire path, taking $n^3$ steps.

Of course, it's rather unlikely, since the algorithm has several choices at each step. But we can construct an example in which the algorithm takes $O(n^3)$ steps with no other options. Instead of tracing out a path that visits every point, trace out a path that visits a constant fraction of the points without ever coming close to touching itself. (For example, zigzag along the $z=1$ plane, hitting around half the points; then come up to $z=3$ and do the same thing there; then repeat for $z=5$ and so on. This visits around $\frac14 n^3$ points.) Then number points along the path just as we did earlier, and give points not on the path some extremely high value. Now the algorithm that moves to a neighbor has no choice but to follow the path to the end.

The existence of other deterministic algorithms that solve this problem in $O(n^2)$ time doesn't change the fact that this algorithm takes $O(n^3)$.

Answer 2

There are many ways to find a path on a grid that goes through every vertex, I have drawn some examples for $n=5$.

Anyway, the simplest one is the snake (fig.1) and it has the advantage to be easy to describe and to exists for any type of $n$-grid.

A cube lattice is no more than $n$ layers of bidimensionnal $n$-grids. So once you arrive at the last vertex of the grid of layer $k$ [ e.g. $\color{red}{24}$ for instance ], then jump to first vertex of layer $k+1$ [ e.g. $\color{red}{25}$ ] and go for another snake, and so on until the last layer.

This way, you have a path on the lattice cube that passes exactly once through every one of the $n^3$ vertices.

Note: I realize I have numbered in increasing order, change the problem to find a local maximum while going $f(u_{i+1})>f(u_i)$.

Now your algorithm starts in $0$, it has neighbours $1,9,49$ but you run out of luck and the algorithm selects $1$ which verifies $1>0$.

Next time $1$ has neighbours $0,2,8,48$ and your algorithm makes again the worst choice and selects $2$.

Through the sequence of worst choices, the algorithm goes through all the $n^3$ vertices and finally find a local maximum (which in this case is also a global one).

Of course, there are better algorithms, for instance a greedy one would select the biggest $f(x_i)$ among neighbours and would reach a local maximum faster, but the former one while respecting the increasing path, had a worst behaviour in $O(n^3)$.