Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 3 down vote favorite

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

share|improve this question
Where have you used the function $f$? Or am I missing something? – Aneesh Karthik C Jul 10 '12 at 10:48
Sorry, that was a mistake. $f$ should be $u$. I edited my question – hulik 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. – hulik 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
show 1 more comment

1 Answer

up vote 1 down vote

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.

share|improve this answer
@ Leonid Kovalev: thank you for your answer. I have some additional question relating to the second apron of your answer."those of the form (Hessian of u plus a positive semidefinite matrix", why plus a positive semidefinite matrix?. Then, why is it true that "One general thing to note that when p is in the interior of the subdifferential (..) any X will work." What would be your solution to my example. It seems to me not that easy to find these pairs. Again, thanks for your help – hulik Jul 11 '12 at 8:23
@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? – hulik 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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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