Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
5  
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 ? –  Denis Serre Oct 18 '10 at 13:55
    
@Denis: I see your motivation. Excellent question! –  Joseph O'Rourke Oct 18 '10 at 14:21
add comment

2 Answers

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.

share|improve this answer
1  
@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! –  Joseph O'Rourke Oct 18 '10 at 18:23
2  
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$. –  Pietro Majer Oct 18 '10 at 19:18
    
@Pietro: And $C$ is ... ? –  Joseph O'Rourke Oct 18 '10 at 19:21
1  
(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. –  Pietro Majer Oct 18 '10 at 19:31
    
(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). –  Pietro Majer Oct 18 '10 at 19:46
show 3 more comments

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'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 Will's suggestion:
alt text

share|improve this answer
1  
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. –  sleepless in beantown Oct 19 '10 at 0:53
    
@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! –  Joseph O'Rourke Oct 19 '10 at 1:02
    
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$ –  sleepless in beantown Oct 19 '10 at 1:02
    
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.) –  sleepless in beantown Oct 19 '10 at 1:09
    
By the way, this function certainly is rotationally symmetric about the $z$-axis with 4-fold symmetry. –  sleepless in beantown Oct 19 '10 at 1:24
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.