8
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Patrick Da Silva Apr 29 '13 at 4:27
  • $\begingroup$ 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). $\endgroup$ – Patrick Da Silva Apr 29 '13 at 4:36
  • $\begingroup$ 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. $\endgroup$ – Patrick Da Silva Apr 29 '13 at 5:29
3
$\begingroup$

Alright, here's a solution (I actually had fun solving this problem, thanks)!

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!

$\endgroup$
  • 1
    $\begingroup$ Very nice!!! +1 $\endgroup$ – user1551 Apr 29 '13 at 9:39
  • 1
    $\begingroup$ Thanks +Patrick Da Silva for the solution. Let it me look at it closely and get back to you! $\endgroup$ – Max Apr 29 '13 at 12:37
  • 1
    $\begingroup$ 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? $\endgroup$ – user7554 Apr 29 '13 at 16:43
  • $\begingroup$ @ PatrickDa Silva How is the change of variable fixed point preserving? it does not seem like $a$ solves the initial problem. $\endgroup$ – Max Apr 29 '13 at 17:06
  • 1
    $\begingroup$ I understood the substitution now ... very nice trick, thanks $\endgroup$ – Max Apr 29 '13 at 23:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.