MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 typo corrections

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

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