11
$\begingroup$

In the "User's guide to viscosity solutions" by Crandall, Ishii and Lions (link), they make the following claim (inequality (A.4) p. 58) :

Given $x$, $\xi$ $\in \mathbb{R}^n$, $A \in \cal{S}(n)$ (space of symmetric $n \times n$ matrices) , for all $\varepsilon >0$, the Cauchy-Schwarz inequality yields

$\langle Ax,x \rangle \leq \langle (A+\varepsilon A^2) \xi,\xi \rangle+\left(\frac{1}{\varepsilon} + \|A\|\right)|x-\xi|^2,$

where I guess $\|A\|$ is the spectral radius of $A$.

I have tried without success to prove this inequality and would appreciate some help.

2 Answers 2

13

So first of all I will use $y$ instead of $\xi$ because I love my eyes and I will use $e$ for $\varepsilon$ because it is simpler to type. I hope you don't get offended by that.

I think they use some sort of a triangle inequality of the form, $\|x-y\| + \|y\| \geq \|x\|$ and $x^TAx\leq\lambda_{max}x^Tx$. But I couldn't see it and I doubt that C-S is needed anyway. Let's do the dirty work, take the LHS to the right and denote that expression with $(\star)$, then: $\begin{align} (\star) &\geq -x^TAx +y^T(A+e A^2)y+(x-y)^T\left(\frac{1}{e}I + A \right)(x-y) \\ &=y^T(A+e A^2)y+(x-y)^T\frac{1}{e}I(x-y) + y^TAy - 2x^TAy\\ &=y^TA(I+e A)y+y^TAy + \frac{1}{e}y^Ty-2\frac{1}{e}x^Ty+\frac{1}{e}x^Tx-2x^TAy\\ &=y^TA(I+e A)y + y^T(\frac{1}{e}I+A)y -2x^T(\frac{1}{e}I+A)y + \frac{1}{e}x^Tx\\ &= \frac{1}{e}y^T(I+e A)^2y -2\frac{1}{e}x^T(I+eA)y + \frac{1}{e}x^Tx\\ &=\frac{1}{e}\|x-(I+eA)y\|^2\\ &\geq 0 \end{align} $

To be honest, this type of math snobbery makes me sick. Maybe there is a direct argument using C-S inequality. Then it would be shorter than this so why not including it in the document. But anyway, hope it helps.

EDIT: by the way the norm definition is given on page 17.

  • 1
    @Nate : It is not the omission of the derivation but the style of skipping it drives me nuts. They don't even say from where C-S yields this expression. It just goes "...If \epsilon > 0, the Cauchy-Schwarz inequality yields..."! Ingenuity and novelty can not be an excuse for horrible style choices.2011-09-15
10

I only post this answer since you asked how to prove this using the Cauchy–Schwarz inequality. Here's the best argument I could come up with (and there's not much difference to percusse's argument, of course).

Write $B = \varepsilon A$ and multiply the inequality by $\varepsilon \gt 0$ to get $\DeclareMathOperator{\eps}{\varepsilon}$ $\langle Bx,x \rangle \leq \langle (B+B^2)\xi,\xi \rangle + (1 + \|B\|)\, \|x - \xi\|^2.$

Now estimate using the symmetry condition $\langle Sy,z\rangle = \langle y, Sz\rangle = \langle Sz,y\rangle$ several times $\begin{align*} \langle Bx, x\rangle &\leq \langle Bx, x\rangle + \|(1+B)\xi - x\|^2 \\ %&= %\langle Bx, x\rangle+ %\|(1+B)\xi\|^2-2\langle(1+B)\xi,x\rangle +\|x\|^2\\ &= \color{green}{\langle Bx, x\rangle}+ \color{red}{\langle (1+B)\xi,\xi\rangle}+ \color{blue}{\langle(1+B)\xi,B\xi\rangle}- \color{red}{2\langle(1+B)\xi,x\rangle}+\color{green}{\langle x,x\rangle} \\ &=\color{blue}{\langle(B+B^2)\xi,\xi\rangle}+ \color{red}{\langle(1+B)\xi,\xi-x\rangle}- \color{red}{\langle(1+B)\xi,x\rangle}+ \color{green}{\langle(1+B)x,x\rangle} \\ &=\langle(B+B^2)\xi,\xi\rangle+ \langle(1+B)(\xi-x),\xi\rangle -\langle(1+B)(\xi-x),x\rangle \\ &=\langle(B+B^2)\xi,\xi\rangle + \langle (1+B)(\xi-x),\xi-x\rangle. \end{align*}$ Now we are in position to apply the Cauchy–Schwarz inequality: $\langle(1+B)(\xi-x),\xi-x\rangle \leq \|(1+B)(\xi-x)\|\,\|\xi-x\|.$ Using $\|(1+B)(\xi-x)\| \leq \|1+B\|\,\|\xi-x\| \leq (1+\|B\|)\|\xi-x\|$ by definition of the operator norm, we get $\langle Bx,x\rangle \leq \langle(B+B^2)\xi,\xi\rangle + (1+\|B\|)\,\|\xi-x\|^2,$ as desired.

  • 1
    @pgassiat: I agree that it could have been phrased in a clearer way (simply say what one has to add on the left hand side), but I disagree that it is snobbery. Be a bit charitable with the authors: when you have spent long enough doing the same computations over and over again you simply don't see anymore that things that are obvious routine to you are not obvious and routine to others. It is extremely hard to write up things homogeneously in difficulty. Maybe they just thought that hinting at CS makes it clear enough what one has to do.2011-09-18