using fixed point theorem

Hi I want to use the fixed point theorem to show that for $G: \mathbb{R}^n \rightarrow \mathbb{R}^n$ $G(x)= \epsilon M x + \max(x,y)$, here $y$ is given and $\max(x,y)$ is the vector with component $\max(x_i,y_i)$, $M$ is negative definite $n \times n$ matrix, $G(x)=x$ has a solution. (Note this is for any $\epsilon >0$).

First, I showed that $G$ is a non expansive map for $\epsilon < \dfrac{1}{\|M\|}$. So the fixed point for contraction map wouldn't work so I changed direction.

I know that $G$ is a continuous map, so if I can find a closed set $B$ (ball) in $\mathbb R^n$ such that $G$ maps from $B$ to $B$ then the Brower's fixed point theorem says that $G$ has a fixed point. I can not figure out $B$. I had difficulty to deal with $|\max(x,y)|$.

Any thought on this would be very much appreciated!

• How did you get your bound? Because I tried to derive it and I believe it's wrong ; I can't think of a way to deal with the difference of maximums. – Patrick Da Silva Apr 29 '13 at 4:27
• The epsilon in this question is irrelevant, so you might as well say $\varepsilon = 1$ and essentially you're saying that you solved the case where $\| M \| < 1$. Which I'm not confident about if $y$ is 'special' (can't pinpoint which $y$ would be wrong). – Patrick Da Silva Apr 29 '13 at 4:36
• I tried to simplify the problem and here's what I got : write $$G(y+x) = M(y+x) + \max \{ y+x, y \} = M(y+x) + y + \max \{x,0\},$$ hence if $y+x$ is a fixed point, it follows that $$x = M(y+x) + \max \{ x,0\}.$$ So you would want to consider this new function $$H(x) = M(y+x) + \max \{ x, 0\}$$ because now there are no weird stuff happening around $y$, it's just a constant vector which translates the function in a very linear way. It makes it easier to compute fixed-point theorem inequalities though. Although I insist ; even with this technique, I can't get your $\| M \| < 1$ bound. – Patrick Da Silva Apr 29 '13 at 5:29

Without loss of generality, $\varepsilon = 1$. So you start with the original problem $$G(x) = Mx + \max \{ x,y\}$$ which under the substitution $x \mapsto x+y$ becomes $$x+y = M(x+y) + \max \{ x+y,y \} = M(x+y) + y + \max \{x,0\}.$$ or in other words, $$x = Mx + My + \max \{x,0\}.$$ Since $M$ is negative definite, $M$ cannot have $1$ as an eigenvalue, so $I-M$ is invertible ($I$ denotes the identity matrix). A solution to this equation therefore solves $$x = (I-M)^{-1} (My + \max \{x,0\}).$$ Now define $H(x) = (I-M)^{-1} (My + \max \{x,0\})$. Note that all my changes of variables were fixed-point preserving in both directions, so all we need to do now is find a fixed point of $H$. If we want to apply Banach's fixed point theorem on $H$, for $x_1, x_2 \in \mathbb R^n$, we compute \begin{aligned} \| H(x_1) - H(x_2) \| & = \| (I-M)^{-1} (\max \{ x_1, 0\} - \max \{ x_2, 0\} ) \| \\ & \le \| (I-M)^{-1} \| \| \max \{ x_1, 0 \} - \max \{ x_2, 0 \} \| \\ & \le \| (I-M)^{-1} \| \| x_1 - x_2 \| \end{aligned} The last inequality follows because for real numbers $t_1, t_2$, we have $$\max \{ t_1, 0 \} \le \max\{ t_1 - t_2, 0 \} + \max \{ t_2, 0 \}$$ hence by interchanging roles, you get \begin{aligned} |\max \{ t_1, 0 \} - \max \{ t_2, 0 \}| & \le \max \{ \max \{ t_1 - t_2 , 0 \} , \max \{ t_2 - t_1, 0 \} \} \\ & \le \max \{ | t_1 - t_2 | , 0 \} \\ & = |t_1 - t_2| \end{aligned} so that if $x_j = (x_j^1 , \dots, x_j^n)$, $j=1,2$, we have $$\| \max \{ x_1, 0 \} - \max \{ x_2, 0 \} \| \le \sqrt{ \sum_{i=1}^n |x_1^i - x_2^i|^2 } = \| x_1 - x_2 \|.$$ All we need to show now is that $\|(I-M)^{-1}\| < 1$ and we can apply Banach's fixed point theorem. So we want to show that \begin{aligned} 1 > \|(I-M)^{-1}\| & = \sup_{x \neq 0} \frac{ \|(I - M)^{-1}x \|}{\|x\|} \\ & = \sup_{x \neq 0} \frac{\|x\|}{\|(I-M)x\|} \\ & = \sup_{\|x\| = 1} \frac 1{\|(I-M)x\|} \\ & = \frac 1{\inf_{\|x\| =1} \|(I-M)x\|}, \\ & \\ & \\ & \\ \Longleftrightarrow & \quad \inf_{\|x\| = 1} \|(I-M)x\| > 1. \end{aligned} The unit sphere is compact and linear applications/norms are continuous functions, hence this infimum is a minimum say at $\hat x$ with $\|\hat x\| = 1$. Fix an orthogonal basis $\{ \hat x, e_2, \dots, e_n \}$ of $\mathbb R^n$, so that since $\hat x^{\top} M \hat x < 0$, by Pythagoreas's theorem, we have $$\|(I-M)\hat x\|^2 = (\hat x^{\top}(I-M)\hat x)^2 + \sum_{i=2}^n (e_i^{\top} M \hat x)^2 > \| \hat x\|^2 = 1.$$ Hope you liked it!
• This is a reply to Patrick. I was interested in this post too. I am a little concern about the substitution as it supposes that $a+g$ solves $G(x)=x$ already? I am sorry if it's too obvious but I can not see how $a$ solves the two equations? – user7554 Apr 29 '13 at 16:43
• @ PatrickDa Silva How is the change of variable fixed point preserving? it does not seem like $a$ solves the initial problem. – Max Apr 29 '13 at 17:06