Non-linear root finding with positive definite Jacobian

Question

I am dealing with a system of non-linear equations:

$$ f(\boldsymbol{x}) = \boldsymbol{y}, \;\;\; \boldsymbol{x}, \boldsymbol{y} \in \mathbb{R}^d. $$

And I know that the Jacobian $J(\boldsymbol{x})$ is positive definite: $$ \boldsymbol{z}^T J(\boldsymbol{x}) \boldsymbol{z} \geq \epsilon > 0, \;\;\;\;\;\;\forall \; \boldsymbol{x}, \, \boldsymbol{z} \; :\; ||\boldsymbol{z} || = 1 $$ for any $\boldsymbol{x}$. My intuition is that this implies that the system can by solved for any $\boldsymbol{y}$. In the univariate case it seems obvious, but is this still correct in the multivariate case? And is there a way to prove it? Many thanks!

Answer 1

The question changed, so this a new answer. If $(z,J(x)z)\geq\epsilon>0$, then take (w.l.o.g.) $f(0)=0$, and consider a path $g:[0,1]\to\mathbb{R}^n$ such that $$ g(0) = 0, \qquad f(g(0)) = 0, \qquad f(g(t)) = y t, \quad 0\leq t\leq 1, $$ so that $g(1)$ is the solution to $f(x)=y$. Then we differentiate with respect to $t$ to get an ODE for $g(t)$: $$ g'(t) = J(g(t))^{-1}y, \qquad g(0) = 0. $$ By the Picard-Lindelof theorem, it is enough to have the function $g\mapsto J(g)^{-1}y$ be Lipschitz everywhere on $\mathbb{R}^n$ for a unique solution to the ODE to exist. Since we already have $\|J^{-1}\|\leq\frac1\epsilon$, it is enough for $J$ to have uniformly bounded derivatives: $$ \frac{\partial}{\partial g_i}J(g)^{-1}y = -J(g)^{-1}\frac{\partial J}{\partial g_i}J(g)^{-1}y, $$ so $\|(J^{-1}y)'\| \leq \frac{1}{\epsilon^2}\|y\|\|\partial_i J\|$.

Of course, even with $n=1$, $J\geq\epsilon$ does not imply $(J^{-1})'$ is bounded. For example one could take $J=2+\sin x^2$ (whose antiderivative $f$ is given in terms of the Fresnel integral $S$), which is bounded above and below, but has unbounded derivative, so Picard-Lindelof is not applicable.

By the Peano existence theorem, on the other hand, if the function $\|J(g)^{-1}y\|$ is bounded by $\frac1\epsilon\|y\|$ over the range $\|g\|\leq c$, then there exists at least one solution on the interval $|t|\leq c \epsilon/\|y\|$. (Also note that this is an autonomous system of ODEs, meaning no $t$ dependence.) In this case, $\|J^{-1}\|$ is bounded by $\frac1\epsilon$ everywhere independent of $g$, so the theorem guarantees existence on an arbitrary interval, including $[0,1]$, which is sufficient to establish $f(g(1))=y$.

I couldn't think of a simpler answer to your question that wouldn't go through ODE theory. Maybe someone else can do better.

Answer 2

You could consider $d=1$ and $$ f(x) = e^x, \qquad y=0. $$ I don't think a function's derivative being positive everywhere implies that the function's range is all of $\mathbb{R}$.

It does imply, though, that solutions are unique. If $(x_1,y)$, $(x_2,y)$, $x_1\neq x_2$ are two solutions, then $$ 0 = (x_2-x_1)\cdot(f(x_1) - f(x_2)) = \int_0^1 (x_2-x_1)\cdot J(x_1+t(x_2-x_1))(x_2-x_1)\,dt $$ so it can't be that $J$ is positive definite everywhere.