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

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)$.

Note: I asked this on math.SE without receiving an answer

share|improve this question
    
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

1 Answer 1

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.)

share|improve this answer
    
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

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.