34
$\begingroup$

Let $f(x,y)$ define a surface $S$ in $\mathbb{R}^3$ with a unique local minimum at $b \in S$. Suppose gradient descent from any start point $a \in S$ follows a geodesic on $S$ from $a$ to $b$. (Q1.) What is the class of functions/surfaces whose gradient-descent paths are geodesics?

Certainly if $S$ is a surface of revolution about a $z$-vertical line through $b$, its "meridians" are geodesics, and these would be the paths followed by gradient descent down to $b$. So the class of surfaces includes surfaces of revolution. But surely it is wider than that?

(Q2.) One could ask the same question about paths followed by Newton's method, which in general are different from gradient-descent paths, as indicated in this Wikipedia image:
       Newton's vs. Gradient Gradient descent: green. Newton's method: red.

(Q3.) These questions make sense in arbitrary dimensions, although my primary interest is for surfaces in $\mathbb{R}^3$.

Any ideas on how to formulate my question as constraints on $f(\;)$, or pointers to relevant literature, would be appreciated. Thanks!

Improve this question
$\endgroup$
4
  • 6
    $\begingroup$ Let me add a fourth side to the question. (Q4.) Let $h:{\mathbb R}\rightarrow{\mathbb R}$ be smooth and increasing. Let $f$ be a function as in (Q1). Is $h\circ f$ such a function too ? $\endgroup$
    – Denis Serre
    Commented Oct 18, 2010 at 13:55
  • $\begingroup$ @Denis: I see your motivation. Excellent question! $\endgroup$
    – Joseph O'Rourke
    Commented Oct 18, 2010 at 14:21
  • 1
    $\begingroup$ Solutions $s$ to the eikonal equation $|ds|=1$ always have geodesics as gradient flow lines, and their level sets are perpendicular to those geodesics. This gives you quite a few examples. The geodesics perpendicular to a hypersurface are always locally given by solving the eikonal equation ($s$ is the oriented distance to the hypersurface). $\endgroup$
    – Ben McKay
    Commented Mar 4, 2017 at 14:29
  • $\begingroup$ The eikonal equation story, for example, gives you Joseph O'Rourke's example below. $\endgroup$
    – Ben McKay
    Commented Mar 4, 2017 at 14:30

2 Answers 2

Reset to default
20
$\begingroup$

For (Q1). The tangent space of $S$ is generated by the gradient flow vector field $v = (|\nabla f|^2, \nabla f)$ and the tangents to the level sets $w= (0, \nabla^\perp f)$. The geodesic constraint can be imposed as the condition "no sideways acceleration", which means that $[(\nabla f \cdot \nabla )v] \cdot w = 0$. This implies that $\nabla^2_{ij} f \nabla^if \nabla^{(\perp)j}f = 0$. In other words, the eigendirections of the Hessian of $f$ must be $\nabla f$ and its orthogonal, or that $\nabla f$ is parallel to $\nabla |\nabla f|^2$. So this means that $f$ and $|\nabla f|^2$ share the same level sets. (This same characterization is valid for any dimension; so also answers (Q3). )

In particular, this answers Denis Serre's (Q4) in the positive.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ @Willie: That is a beautiful characterization, that $f$ and the square gradient share the same level sets! I do not yet see what this implies in terms of the global geometric shape of $f$, but it certainly is a succinct encapsulation. Thanks! $\endgroup$
    – Joseph O'Rourke
    Commented Oct 18, 2010 at 18:23
  • 2
    $\begingroup$ Two functions share the same level sets iff the values of each of them only depend on the values of the other. So Willie's condition writes as an eikonal equation $|\nabla f(x)|^2=h(f(x)),$ and I guess that solutions are all of the form $f(x)=g(\mathbb{dist}(x,C)),$ at least locally ($g$ and $h$ being related by $1/h= (g^{-1})^')$. Here $\mathbb{dist}(x,C)$ is the point-set Euclidean distance from $C$. $\endgroup$
    – Pietro Majer
    Commented Oct 18, 2010 at 19:18
  • $\begingroup$ @Pietro: And $C$ is ... ? $\endgroup$
    – Joseph O'Rourke
    Commented Oct 18, 2010 at 19:21
  • 1
    $\begingroup$ (I guess) $C$ could be any subset, even not smooth, for the distance function from $C$ is 1-Lipschitz, thus differentiable a.e., and $|\nabla d_C|=1$, so in any case one gets a solution. A smooth, convex $C$ should give solutions defined everywhere. Note that $C$ a point gives the surfaces of revolutions you mentioned in the questions. $\endgroup$
    – Pietro Majer
    Commented Oct 18, 2010 at 19:31
  • $\begingroup$ (sorry, I changed notation: $d_C(x)=\mathbb{dist}(x,C)$). Another way to characterize the functions $f$ should be, that sublevel sets {f<c} are uniform neighborhoods of $C$ (or of any sublevel set {f<b}, with b<c). $\endgroup$
    – Pietro Majer
    Commented Oct 18, 2010 at 19:46
4
$\begingroup$

Here is a function $f(x,y)$ which is 0 inside the square $C=[\pm1,\pm1]$, and outside that square has value equal to the Euclidean distance $d( p, C )$ from $p=(x,y)$ to the boundary of $C$. [I am trying to follow Pietro Majer's suggestion, as far as I understand it.] It is not a surface of revolution (but it is centrally symmetric). Are its gradient descent paths geodesics? I think so...
Function, Contours
Left above: $f(x,y)$. Right above: Level sets of $f$. Below: $\nabla f$.
Gradient
And here (below) is a closeup of the function defined using squared distance $[d( p, C )]^2$, as per Willie Wong's suggestion:
WW

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ Hmmm, like Jeopardy, :) your answer is in the form of a question... I think they just might be, but now in this case, there is no point that is a unique minimum. Everything within the square $C$ is the minimum. So what is your gradient descending to? The closest point in $C$ to your starting point? So you've got 4 voronoi cells defined by (0.5,0) (0,0.5) (-0.5,0) and (0,-0.5) for E/N/W/S directions, which delineate the four regions closest to the 4 edges of $C$,except for any point within $C$ in which case its gradient descent is the point itself. $\endgroup$
    – sleepless in beantown
    Commented Oct 19, 2010 at 0:53
  • $\begingroup$ @sleepless: Yes, no unique local min, but still one can define descent paths for all points exterior to the central square. Your description is accurate, including answer$=$question! $\endgroup$
    – Joseph O'Rourke
    Commented Oct 19, 2010 at 1:02
  • $\begingroup$ Or, you've got 8 regions, with the 4 quadrants translated (+/-0.5, +/-0.5) in the xy plane with gradient descents for any point in those planes mapping to the corners of the square $C$, e.g. (x≥0.5,y≥0.5)→(+0.5,+0.5), and the other three quadrants where you swap in less-than signs for -0.5 values all having gradient descents as lines going to the corners of the square $C$; and the regions for x > 0.5 and $-0.5 \le y \le 0.5$ having a gradient descent to $(y,0.5)$, and three other similar regions mapping to the edges of the region $C$ $\endgroup$
    – sleepless in beantown
    Commented Oct 19, 2010 at 1:02
  • $\begingroup$ So the answer in this case, is a definite YES, the gradient descents for this figure for any point starting outside of $C$ are definitely geodesics. I'd call this figure a circle fractured into quadrants intercalated by strips of the plane defined by a square at the center of the fractured circle quadrants. (instead of drawing the contours of the distance, draw the gradient of the function and you'll see it clearly.) $\endgroup$
    – sleepless in beantown
    Commented Oct 19, 2010 at 1:09
  • $\begingroup$ By the way, this function certainly is rotationally symmetric about the $z$-axis with 4-fold symmetry. $\endgroup$
    – sleepless in beantown
    Commented Oct 19, 2010 at 1:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .