Discrete gradient ascent cycles

Question

I am wondering what can be inferred when a discrete gradient ascent algorithm gets stuck in a cycle. Here is the situation. A function $f(x,y)$ is defined over a range $[0,n]^2$, and the algorithm walks on integer lattice points. The algorithm is simple: from $p$ it looks at the $f$-value at the three adjacent lattice points, excluding the lattice point from which it arrived at $p$. If one is uniquely highest in $f$-value, it steps to that point. If there is a tie for highest, it chooses, say, the clockwise-most option.

Here are the assumptions on $f$: (a) $f$ has a unique maximum in the interior of the search range; (b) $\nabla f$ is positive everywhere (pointing up), except it is zero at the maximum; (c) The level curves $f(x,y) = c$ are strictly convex, strictly meaning there are no flat (zero-curvature) sections of a level curve.

Under these circumstances, I think the following holds:

1. If the ascent walk falls into a cycle, it is a $1 \times 1$ cycle, around the boundary of a square cell of the lattice.
2. The maximum of $f$ must lie either in the same row as this cell or the same column of this cell.

Perhaps the figure below helps explain these conclusions.

The ascent path is $(p,a,b,c,d)$. When first at $a$, $f(b)=f(d)$ and the algorithm chooses the cw point $b$. The maximum lies in the same "row" as the red cell.

Question 1. Are the two conclusions above correct?

If not, please ignore the 2nd question!

Question 2. Generalizing to $f$ defined on a $d$-dimensional region, with the algorithm step comparing $f$ at $2d -1$ adjacent lattice points ($\pm$ in every coordinate, excluding the arrival direction), are there analogous claims about the shape of the possible cycles and implications on where the maximum could lie?

Thanks for insights!

Answer 1

Can we assume that the algorithm terminates when all directions other than back go downhill?

Can we also change the properties of the function to this: For every $z$, the set where $f(x, y) \ge z$ is a strictly convex closed set and the set where $f(x, y) = z$ is its boundary? I think this is a weaker condition, mainly because it doesn't require differentiability, but I have not really checked.

Then I think your conclusions can be justified. First, from the termination condition it follows that f must be constant on that cycle, which by the properties of the function means that they must be on the boundary of some strictly convex set, and the maximum must be in the interior of that set.

Furthermore, since movement is horizontally or vertically, the only shapes meeting the convexity requirement are rectangles, and because of the strict convexity, no three points can be colinear, which means the rectangle cannot be larger than a single cell. However, since going back is expressly disallowed, it cannot be smaller either, hence your conclusion 1.

The second conclusion can be reached in at least two ways. One is that since the points in the cycle are boundary points of a strictly convex set they cannot be in the convex hull of other points in the set, in particular the convex hull of the other points in the cycle and the maximum. Another way is that no lattice point adjacent to a point in the cycle can be in the convex hull of all the points in the cycle and the maximum, for such a point would have a higher value of $f$ and this would break the cycle.

Judging by your sketch, this is pretty much what you had in mind.

Most of this generalizes easily to higher dimensions, but probably not in a useful way. We can still conclude that the cycle must be contained in a single cell. We can also conclude that it must be at least a square. However, suppose it is just a square. Then the maximum can be placed anywhere in the space, provided that the pyramid it forms with the square manages to avoid a few points adjacent to the square. An educated guess says that that is at least half the space.