# How do you find such a pair $(p,X)$?

Let $u$ be a real valued function with domain $\mathbb{R}^n$ and I want to find all pair $(p,X)\in \mathbb{R}^n\times\mathcal{S}^n$, where $\mathcal{S}^n$ is the set of symmetric $n\times n$ matrices, such that $$\lim\sup_{y\to x}\frac{u(y)-u(x)-\langle p,(y-x)\rangle-\frac{1}{2}\langle X(y-x),(y-x)\rangle}{|y-x|^2}\le 0$$ Where $\langle\cdot,\cdot\rangle$ is the canonical scalar product. Furthermore, with $|\cdot|$ we denote the euclidean norm on $\mathbb{R}^n$. Consider a concrete example. Let $u(x):=-|x|$, here $n=1$, so both $p,X$ are real numbers. Of course I have to use a case-by-case analysis. Suppose $x>0$. I have to find all pairs $(p,X)$ such that $\lim\sup_{y\to x}\frac{u(y)-u(x)-p(y-x)-\frac{1}{2}X(y-x)(y-x)}{|y-x|^2}=\lim\sup_{y\to x}\frac{-|y|+|x|-p(y-x)-\frac{1}{2}X(y-x)(y-x)}{|y-x|^2}=\lim\sup_{y\to x}\frac{-|y|+x-p(y-x)-\frac{1}{2}X(y-x)(y-x)}{|y-x|^2}\le 0$

Now how can I find all this pairs $(p,X)$? I have no idea how to solve this. Thank you for your help

-
Where have you used the function $f$? Or am I missing something? –  Host-website-on-iPage Jul 10 '12 at 10:48
Sorry, that was a mistake. $f$ should be $u$. I edited my question –  user20869 Jul 10 '12 at 11:30
Say $n=2$. What are $x$ and $y$? scalars, or vectors? ditto for $u(x)$. In the numerator, it looks like you are subtracting a matrix from a vector, or else multiplying two vectors. –  Gerry Myerson Jul 10 '12 at 13:22
Sorry if my notation was not clear. I added some details. –  user20869 Jul 10 '12 at 13:35
That's better, but you still have the incomprehensible $p(y-x)$, a product of some form of two vectors. What is it? –  Gerry Myerson Jul 10 '12 at 13:43

It's better to begin with a simpler problem: find all $p$ such that $u(y)\le u(x)+\langle p, y-x\rangle+o(\|y-x\|)$. (If you are not familiar with the Landau notation O() and o(), look it up -- it is very convenient here.) At the points where $u$ is once differentiable, we get $p=\nabla u(x)$ from the definition of derivative. You should consider the example of $u(x) =|x|$ at $0$ and convince yourself that the set of $p$ is described by $|p|\le 1$. You may want to read about the "subdifferential" at this time.
Now you are ready to tackle the question of finding p and X such that $u(y)\le u(x)+\langle p, y-x\rangle+\langle X(y-x),y-x\rangle/2 + o(|y-x|^2)$. First, notice that $p$ must satisfy the first order condition considered above. Also, at the points where $u$ is twice differentiable (more precisely, admits a second degree Taylor expansion), we can state precisely which X are allowed - those of the form (Hessian of $u$ plus a positive semidefinite matrix). At the points of nonsmoothness we work case by case. One general thing to note that when $p$ is in the interior of the subdifferential (ie strictly between -1 and 1 in out example) any X will work. It's only on the boundary of the subdifferential that we have to seriously think about X. Again, the answer will likely involve positive semidefiniteness.
@hulik Positive semidefiniteness of X means that $\langle Xv , v \rangle \ge 0$ for every vector v. Do you see that this is relevant for the kind of inequalities you have? If not, consider the case when $u$ is identically zero. In your example with $|x|$, at the origin you can take $(p,X)$ with $|p|<1$ and any $X$; also, $p=\pm 1$ and $X\ge 0$. –  user31373 Jul 11 '12 at 11:22
@ Leonid Kovalev: The thing which I do not understand is why $X$ has to be of the form Hessian PLUS a positive semidefinite matrix. I positive semidefiniteness is important, however it is not necessary, right? If we look at the case $x>0$ in my example. How do I get all the right pairs? The solution tells me that $\{(-1,X): X\ge 0\}$. How do I see this? –  user20869 Jul 11 '12 at 13:08
@hulik Let $H$ be the Hessian at $x$. If $X-H$ is not positive semidefinite, there exists $v$ such that $\langle (X-H)v,v\rangle<0$. Take $y=x+\epsilon v$ and in the limit $\epsilon\to 0$ you will not have the inequality you want... For the specific example with $x>0$, we have $p=\nabla u=1$ according to what I said, and since the Hessian $u''$ is zero, the allowable $X$ are just nonnegative numbers (this is what positive semidefinite matrices are in one dimension). –  user31373 Jul 11 '12 at 14:13