# Going in the direction of the gradient

First, a motivating example. Suppose $f(x)$ is convex, differentiable, with a single minimum $x^*$.

Then the differential equation $$\dot{x}(t) = -\nabla f(x(t))$$ drives $x(t)$ to $x^*$.

Now my question is about a generalization of this. Let $f(x), g(x)$ be two smooth convex functions and let ${\cal G}$ be the set of minima of $g(x)$, which we assume to be nonempty. Consider the differential equation $$\dot{x}(t) = - \frac{1}{t} \nabla f(x(t)) - \nabla g(x(t))$$ Is it true that this equation drives $x(t)$ to the minimum of $f(x)$ on ${\cal G}$? If not, would it be true if we replaced $1/t$ by a different function, say one which perhaps decays slower? Or perhaps by adding some additional conditions on $f$, e.g., strong convexity?

This statement seems to be true in a few simple examples I tried. For example, taking $g(x)=(x_1+x_2-2)^2$ and $f(x)=x_1^2+x_2^2$ and solving the resulting equation numerically, I get that solutions seem to approach $(1,1)$.

-
Do you mean instead that $x(t)$ is driven to the minimum of $g$ ? – Denis Serre Jul 9 '12 at 9:02
No, $x(t)$ should be driven to the minimum of $f(x)$ on ${\cal G}$, which is the set of minimizers of $g$ (at least, that is what I think should be true!) For example, in the example I gave in the final paragraph, the set of minimizers of $g$ is the set $x_1+x_2=2$ and the minimum of $f$ on it is $(1,1)$ - which is where indeed the solution appears to go numerically. – user21162 Jul 9 '12 at 9:21

Assume $f$ is strongly convex (i.e., $f''>\varepsilon$ for some fixed $\varepsilon>0$). Then for any two solutions $x$ and $y$ we have $|x(t)-y(t)|\le \tfrac C t$. In particular if one solution converges then all of them converge to the same point.
If this point $x^*$ is not the minimum of $f$ on $\mathcal G$ then you get an immediate contradiction. (There is a draught in one direction near $x^*$ for all $t$'s.)
Thank you for answering. Could I ask for more details? I tried to understand your answer but failed. 1. Why do solutions satisfy $|x(t)−y(t)| < C/t$? 2. How do you know at least one solution converges? 3. Can you spell out the contradiction that converging to a non-minimum results in? Thanks! – user21162 Jul 8 '12 at 14:56
The estimate follows along the same lines as Picard's existence theorem. For the second part of argument, look at a neighborhood of $x^*$ and try to estimate the behavior of solutions for big $t$, it will slide in a direction of a fixed vector tangent to $\mathcal{G}$; that means this can not be a limit point. – Anton Petrunin Jul 8 '12 at 20:31