Take the 2-minute tour ×
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.

Do you know mathematical results which can be nicely proved using subgradient?

For example, Jensen's inequilaty can be proved like that: Let $\varphi : \mathbb{R}^n \to \mathbb{R}$ be a convex function and $g \in L^1([0,1],\mathbb{R}^n)$. So $\displaystyle \varphi \left( \int_0^1 g(t)dt \right) \leq \int_0^1 \varphi(g(t))dt$.

Indeed, $\partial \varphi(\overline{g}) \neq \emptyset$ with $\displaystyle \overline{g}= \int_0^1g(t)dt$. Let $\zeta \in \partial \varphi(\overline{g})$. So $\varphi(g(t))- \varphi(\overline{g}) \geq \langle \zeta, g(t)- \overline{g} \rangle$ for all $t \in [0,1]$. By integrating the inequality, you get Jensen's inequality.

Do you know other such result?

share|improve this question

1 Answer 1

up vote 0 down vote accepted

In case anyone is curious, here is a description of the object $\partial f$.

I recommend R.T. Rockafellar's "Convex Analysis" - it has several chapters devoted to the differential theory of convex functions. Here are a couple nice results from it:

  • Theorem 24.3 The graphs of the subdifferential mappings of closed, proper convex functions $f$ on $\Bbb{R}$ are precisely the complete non-decreasing curves $\Gamma$ in $\Bbb{R}^2$. Moreover $f$ is uniquely determined by $\Gamma$ up to an additive constant.

A "non-decreasing curve" is essentially the graph of a continuous non-decreasing function, with possibly some vertical segments. Essentially, we can always find a "convex potential" for such curves - i.e. a function $f$ such that $\Gamma=\partial f$. There is a higher dimensional version of this where "non-decreasing" is replaced by a condition called "cyclical monotonicity".

  • Theorem 27.1 Let $f$ be a closed proper convex function $f$. Then, the minimum set of $f$ is $\partial f^*(0)$ where $f^*$ is the convex conjugate of $f$. Thus the infimum of $f$ is attained if and only if $f^*$ is subdifferentiable at 0.

This theorem has many more parts, but the idea is that we can characterize the minimizers of convex functions by looking at the subdifferential of the convex conjugate. A nice summary of the relationship between the subdifferential and the convex conjugate is the following equivalencies:

$$ x\cdot y=f(x)+f^*(y)\Longleftrightarrow y\in\partial f(x)\Longleftrightarrow x\in\partial f^*(y) $$

where $x\cdot y$ is the standard dot product on $\Bbb{R}^n$.

Another place I've seen subdifferentials used prominently is in the theory of optimal transportation/transport: see e.g. either of Villani's books on the subject. For instance, Brenier's theorem states that if $\mu$ and $\nu$ are probability measures on $\Bbb{R}^n$ and $\mu$ does not give mass to "small" sets, there is an a.e. unique convex function $\varphi:\Bbb{R}^n\rightarrow\Bbb{R}$ such that

$$ (\nabla\varphi)\#\mu=\nu $$

where $\#$ indicates the pushforward measure. This is essentially a change-of-variables theorem for measures, and it's proved by solving the Monge-Kantorovich transport problem:

$$ \inf_{\gamma\in S}\int_{\Bbb{R}^n\times\Bbb{R}^n}\vert x-y\vert^2 d\gamma\\ $$

where $S$ is the set of joint probability measures such that the margianals are $\mu$ and $\nu$:

$$ S=\{\gamma\in P(\Bbb{R}^n\times\Bbb{R}^n):\gamma[E\times\Bbb{R}^n]=\mu[E],\gamma[\Bbb{R}^n\times E]=\nu[E]\} $$

As it turns out, one can show that the support of minimizers $\gamma$ must be "cyclically monotone", and another theorem in Rockafellar states that such sets must be contained in the subdifferential of a convex function $\varphi:\Bbb{R}^n\rightarrow\Bbb{R}$. With a bit of work, one can also show that this convex function is in fact differentiable almost everywhere, so that $\partial \varphi=\{\nabla\varphi\}$ almost everywhere, and this is exactly the "convex potential" in Brenier's theorem.

share|improve this answer

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.