Relationship between the Lipschitz modulus and conjugate function The Lipschitz modulus of a real value function $L(x)$, $x\in\mathbb{R}$, is defined as $$\mathrm{lip}(L)=\sup_{x,x'\in\mathbb{R}}\left\{\frac{|L(x)-L(x')|}{  |x - x'|}: x\neq x' \right\}.$$
I also see an alternative definition that $\mathrm{lip}(L)=\sup_{\theta}\{ |\theta|:L^*(\theta)<\infty \}$, where $L^*(\theta)$ is the conjugate function of $L(x)$.
Could anyone tell me why these two definitions are equivalent?
 A: They are equivalent only if $L$ is convex. If it is not, then the second expression evaluates to $-\infty$.
Let us distinguish between the two constants by ${\rm lip}_1(L)$ and ${\rm lip}_2(L)$, respectively, and recall the definition of the convex conjugate to $L$:
$$L^*(y)=\sup_{x\in\mathbb{R}}(xy-L(x))=-\inf_{x\in\mathbb{R}}(L(x)-xy),$$
which may also attain $\infty$ value.
1) The inequality ${\rm lip}_2(L)\leq{\rm lip}_1(L)$ holds for any $L$.
Let $z$ be such that $L^*(z)<\infty$. By the definition of $L^*$, for every $n$, there is $x_n$ such that
$$L^*(z)\leq zx_n-L(x_n)+\frac1n.$$
To the both sides of this, you can add $L(y)-yz$ for any $y\in\mathbb{R}$ and use Fenchel's inequality on the left-hand-side (or just again the definition of $L^*$) to get
$$0\leq z(x_n-y)-(L(x_n)-L(y))+\frac1n.$$
If you choose $y=x_n-7$, then
$$-z\leq-\frac{L(x_n)-L(x_n-7)}{7}+\frac1{7n}\leq{\rm lip}_1(L)+\frac1{7n}\to{\rm lip}_1(L),\quad n\to\infty.$$
If you take $y=x_n+5$, then
$$z\leq\frac{L(x_n+5)-L(x_n)}{5}+\frac1{5n}\leq {\rm lip}_1(L)+\frac1{5n}\to{\rm lip}_1(L),\quad n\to\infty.$$
Therefore $|z|\leq {\rm lip}_1(L)$ for every $z$ with the property $L^*(z)<\infty$, which proves
$${\rm lip}_2(L)\leq{\rm lip}_1(L).$$
2) The inequality ${\rm lip}_1(L)\leq {\rm lip}_2(L)$ holds if and only if $L$ is convex.
Assume first that $L$ is convex and let again $z$ be such that $L^*(z)<\infty$. From the definition of $L^*$, we get
$$xz-L(x)\leq L^*(z),$$
hence, by a simple rearranging, we have
$$L(y)-L(x)\leq z(y-x)+L(y)+L^*(z)-yz$$
for any $x,y\in\mathbb{R}$. Note that the role of $x$ and $y$ can be interchanged and so, we also get
$$-(L(y)-L(x))\leq z(x-y)+L(x)+L^*(z)-xz.$$
Now we obviously want to take the infimum of $z$ on the right-hand-sides. Doing this (and using $\inf (f+g)\leq \sup f+\inf g$) leads to
$$L(y)-L(x)\leq(y-x)\sup_{L^*(z)<\infty}z+L(y)-L^{**}(y)$$
and
$$-(L(y)-L(x))\leq(x-y)\sup_{L^*(z)<\infty}z+L(x)-L^{**}(x),$$
respectively. Thanks to the convexity of $L$ and the Fenchel-Moreau theorem, we have $L^{**}=L$ (otherwise $L^{**}\leq L$, which is useless in our estimate). Thus, assuming that $x<y$, for instance, we easily obtain from the above inequalities that
$$|L(y)-L(x)|\leq(y-x)\Big|\sup_{L^*(z)<\infty}z\Big|\leq{\rm lip}_2(L)(y-x),$$
hence ${\rm lip}_1(L)\leq {\rm lip}_2(L)$ by taking the supremum over $x,y$.
The inequality fails if $L$ is not convex, because then actually $L^*(z)=\infty$ for every $z$, which means that ${\rm lip}_2(L)=-\infty$ (supremum over an empty set). To see this, it is enough to examine again the definition of $L^*$ closely enough, and compute, e.g., $(-|x|)^*$. Actually, it is useful to look first at $(ax+b)^*$, which are the "critical" functions that you can compare with (as the set $\{z:L^*(z)<\infty\}$ reduces to a singular point $a$). Also, it may be useful to first realize that if $L^*(x)<\infty$ and $L^*(y)<\infty$, then also
$$L^*((1-\alpha)x+\alpha y)\leq(1-\alpha)L^*(x)+\alpha L^*(y)<\infty$$
for all $0\leq\alpha\leq1$. This means that $\{z:L^*(z)<\infty\}$ is a convex set (interval) and $L^*$ is convex there.
