4
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ Do you mean instead that $x(t)$ is driven to the minimum of $g$ ? $\endgroup$
    – Denis Serre
    Commented Jul 9, 2012 at 9:02
  • $\begingroup$ 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. $\endgroup$
    – user21162
    Commented Jul 9, 2012 at 9:21

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$
    – user21162
    Commented Jul 8, 2012 at 14:56
  • $\begingroup$ 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. $\endgroup$
    – Anton Petrunin
    Commented Jul 8, 2012 at 20:31

You must log in to answer this question.

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