Going in the direction of the gradient - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T00:34:43Z http://mathoverflow.net/feeds/question/101661 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/101661/going-in-the-direction-of-the-gradient Going in the direction of the gradient robinson1 2012-07-08T13:20:06Z 2012-07-08T14:39:55Z <p>First, a motivating example. Suppose $f(x)$ is convex, differentiable, with a single minimum $x^*$. </p> <p>Then the differential equation $$\dot{x}(t) = -\nabla f(x(t))$$ drives $x(t)$ to $x^*$. </p> <p>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?</p> <p>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)$. </p> <p>Note: I <a href="http://math.stackexchange.com/questions/165262/going-in-the-direction-of-the-gradient" rel="nofollow">asked this</a> on math.SE without receiving an answer </p> http://mathoverflow.net/questions/101661/going-in-the-direction-of-the-gradient/101673#101673 Answer by Anton Petrunin for Going in the direction of the gradient Anton Petrunin 2012-07-08T14:39:55Z 2012-07-08T14:39:55Z <p>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.</p> <p>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.)</p>