## Going in the direction of the gradient

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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

-

Do you mean instead that $x(t)$ is driven to the minimum of $g$ ? – Denis Serre Jul 9 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.   – robinson1 Jul 9 at 9:21

## 1 Answer

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! – robinson1 Jul 8 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 at 20:31
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 40, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9415762424468994, "perplexity_flag": "head"}