Continuous variation from solution of easy problem to solution of hard problem

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

I asked this question a week ago over on math.stackexchange and got no reply, so I am asking here with slightly different wording. I am trying to prove that there exists a solution to a problem. I can't solve this problem in general, but I can always continuously vary the parameters of the general problem to turn it into a specific case which is easy to solve. I believe that the solution of the easy problem can then be varied continuously to be a solution to the hard problem.

It seems to me that this would be a widely used technique, but I haven't seen it before, and I don't know how to prove that it works. To be specific, suppose that $g:\mathbb{R}^n \times \mathbb{R} \to \mathbb{R}^n$. I have a solution $x_0$ to $g(x_0, t=0)=0$. I desire to show the existence of a solution to $g(x_1, t=1)=0$. My strategy is to take the known solution $x_0$ and vary it from $t=0$ to $t=1$. What I need is a theorem of the following form:

Suppose $g(x_0, t=0)=0$, and suppose that $\exists f$ such that \begin{equation} \frac{dx}{dt}=f(x,t) \implies \frac{dg(x,t)}{dt}=0, \end{equation} with $x$ a function of $t$. If $f$ and $g$ are "well behaved enough" in the vicinity $|g(x,t)| < \epsilon$ for some $\epsilon$, then $\exists x$ such that $g(x,1)=0$.

$f$ and $g$ in my case are "well behaved enough" that I can probably prove just about any sort of continuity condition that is needed. What properties of $f$ and $g$ are needed, and what theorem will help me here? It looks like Picard-Lindelof may help, but it seems to only give the existence of a unique solution to the differential equation, and I need to show that that solution satisfies $g(x_1, t=1)=0$. Furthermore, $f$ is not well behaved when $g$ is far from zero, and so it seems I cannot use Picard-Lindelof without prior assumption that $g(x,t)$ stays small (which is kind of assumes the fact that I am trying to prove).

-
I don't see how to interpret the left-hand-side of the left part of your implication. $\hspace{1.7 in}$ $x$ does not appear to depend on $t$ (or anything, for that matter). $\;\;$ – Ricky Demer Mar 1 2012 at 23:10

4
I may be all wrong here, but it sounds very much like you're talking about homotopy continuation methods. ams.org/journals/tran/1978-242-00/… – Gilead Mar 1 2012 at 23:27
Not directly an answer to your question, but the idea of starting with a solution of an easy problem and continuously following its evolution as parameters are changed is also the idea behind the quantum adiabatic algorithm: arxiv.org/abs/quant-ph/0104129 – Yoav Kallus Mar 2 2012 at 7:45
@Ricky: I've edited to make clear that x is a function of t. @Gilead: Thanks. – Dan Stahlke Mar 2 2012 at 14:35

1
In the special case that your functions are continuously differentiable and the nice conditions: (1) Whenever $g(x,t) = 0$, then $D_x g(x,t)$ is an isomorphism; (2) Given $g(x_n,t_n) \equiv 0$ with $t_n \to t$, then the sequence $x_n$ has a convergent subsequence, then you can proceed directly with the implicit function theorem without appealing to degree theory (although its still there behind the scenes). – Aaron Hoffman Mar 2 2012 at 21:39
show 1 more comment

1 Answer

The right tag for this question is topology and the answer is degree theory. You could start by reading, say, http://en.wikipedia.org/wiki/Degree_of_a_map

or/and

http://unapologetic.wordpress.com/2011/12/10/calculating-the-degree-of-a-proper-map/

for a quick introduction.

Read also the book Differential forms in algebraic topology by Bott and Tu for in depth discussion. (Actually, read this book in any case!)

Warning: Wikipedia article confuses local diffeomorphisms and covering maps, but you do not need to worry about this. It also unnecessarily restricts the discussion to the case of bounded domains, while all you need to assume is that the homotopy is proper, see below.

Here is the upshot: For general continuous (or even smooth) functions $g$, the existence of solution for $t=0$ does not imply existence of solution for $t=1$. However, if you assume that $g(x, 0)$ has nonzero degree over its value $0$ and the family $g(\cdot , t)$ is a proper homotopy, then $g(x,1)$ also has nonzero degree over $0$, in particular, the equation $g(x,1)=0$ also has (at least one) solution. The key principles are:

i. proper homotopy preserves the degree

and

ii. map $h$ has nonzero degree $\Rightarrow$ existence of solution of the equation $h(x)=0$ (the function $h$ is surjective).

Here, every continuous map $g(x,t)$ defines a homotopy of the function $h_0=g(x,0)$ to the function $h_1=g(x,1)$. This homotopy is proper if the map $g: {\mathbb R}^n \times [0,1]\to {\mathbb R}^n$ is a proper map (inverse image of compact is compact). In calculus terms: $$\lim_{|x|\to\infty, t\to t_0} g(x,t)=\infty$$

Below are two examples to think about ($n=1$):

1. $g(x,t)=x^2 + t - \frac{1}{2}$. Then the equation $g(x,t)=0$ has solution for $t=0$ and all $t\le 1/2$ but no solutions for $t>1/2$. In this case, $g(x,t)$ (as a function of $x$) has zero degree at $0$ for every $t$.

2. $g(x,t)= (t-1)x +1$. In this case $g(x,t)=0$ again has a solution for all $t\ne 1$, but the equation $g(x,1)=0$ has no solutions. In this case, the map $g(x,t)$ (as a function of $x$) has nonzero degree for all $t\ne 1$, but the homotopy is not proper (the map $g(x,1)$ is not a proper map).

In most places, you will read about degree of maps between compact manifolds, while you are interested in maps of ${\mathbb R}^n$. However, the 1-point compactification of ${\mathbb R}^n$ is the sphere $S^n$. Properness allows you to extend your homotopy $g(\cdot, t)$ to $S^n$, so now you can appeal to the usual degree theory.

Interestingly, the degree theory generalizes (with some difficulty) to the case of maps of Banach spaces which, in turn, is very useful for proving existence of solutions of differential equations. (Google "Degree Theory" + "Banach Spaces".)

-

Thank you very much for such a good answer.  I am not a mathematician so I have quite some reading ahead of me! – Dan Stahlke Mar 2 2012 at 14:25
{"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": 74, "mathjax_display_tex": 1, "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": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9478201270103455, "perplexity_flag": "head"}