Return to 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.
![Gradient Ascent][1]
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!

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.
![Gradient Ascent][1]
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!

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, 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.
![Gradient Ascent][1]
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!

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.
![Gradient Ascent][1]
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!