ScalingStacks

Appendix A Lipschitz constants of convex functions [01HM]

Original official author HTML, exact retained edition. Historical TeX conversion verdicts remain unchanged. Cited-edition alignment and mathematical self-containment are not assessed.

Complete original source context · Original author HTML

Appendix A Lipschitz constants of convex functions

Let VV be a finite dimensional real vector space and τ⊂V\tau\subset V a compact convex set with nonempty interior. Denote by ℰ⁡(τ)\mathcal{E}(\tau) the set of extremal points of τ\tau. Given a norm ∥⋅∥\|\cdot\| on VV the Lipschitz constant of a continuous function φ:τ→𝐑\varphi:\tau\to\mathbf{R} is defined as usual as

Lipτ⁡(φ):=supv≠v′|φ⁡(v)−φ⁡(v′)|‖v−v′‖∈[0,+∞]\lip_{\tau}(\varphi):=\sup_{v\neq v^{\prime}}\frac{|\varphi(v)-\varphi(v^{\prime})|}{\|v-v^{\prime}\|}\in[0,+\infty]

and its C0,1C^{0,1}-norm is then

‖φ‖C0,1​(τ):=‖φ‖C0​(τ)+Lipτ⁡(φ).\|\varphi\|_{C^{0,1}(\tau)}:=\|\varphi\|_{C^{0}(\tau)}+\lip_{\tau}(\varphi).

This quantity of course depends on the choice of ∥⋅∥\|\cdot\|, but since all norms on VV are equivalent, choosing another norm only affects the estimates to follow by an overall multiplicative constant.

Let φ:τ→𝐑\varphi:\tau\to\mathbf{R} be a continuous convex function. Our goal is to estimate the C0,1C^{0,1}-norm of φ\varphi on τ\tau in terms of ‖φ‖C0​(∂τ)\|\varphi\|_{C^{0}(\partial\tau)} and certain directional derivatives of φ\varphi at boundary points. Let us first introduce some notation. First, for v,w∈τv,w\in\tau we define the directional derivative of φ\varphi at vv towards ww as

(A.1) Dv​φ​(w):=dd​t|t=0+​φ​((1−t)​v+t​w);D_{v}\varphi(w):=\left.\frac{d}{dt}\right|_{t=0_{+}}\varphi((1-t)v+tw);

this limit exists by convexity of φ\varphi. Second, given a point e∈ℰ⁡(τ)e\in\mathcal{E}(\tau) we define a projection πe:τ∖{e}→∂τ\pi_{e}:\tau\setminus\{e\}\to\partial\tau by setting

te(v):=sup{t∈𝐑,e+t(v−e)∈τ}t_{e}(v):=\sup\left\{t\in\mathbf{R},\,e+t(v-e)\in\tau\right\}

and

πe​(v):=e+te​(v)​(v−e),\pi_{e}(v):=e+t_{e}(v)(v-e),

so that πe​(v)∈∂τ\pi_{e}(v)\in\partial\tau is the unique point such that v∈[e,πe​(v)]v\in[e,\pi_{e}(v)].

Proposition A.1.

There exists C>0C>0 such that every Lipschitz continuous convex function φ:τ→𝐑\varphi:\tau\to\mathbf{R} satisfies

C−1​‖φ‖C0,1​(τ)≤‖φ‖C0​(∂τ)+supe∈ℰ⁡(τ),v∈int⁡(τ)|Dπe​(v)​φ​(e)|≤C​‖φ‖C0,1​(τ).C^{-1}\|\varphi\|_{C^{0,1}(\tau)}\leq\|\varphi\|_{C^{0}(\partial\tau)}+\sup_{e\in\mathcal{E}(\tau),v\in\mathrm{int}(\tau)}\left|D_{\pi_{e}(v)}\varphi(e)\right|\leq C\,\|\varphi\|_{C^{0,1}(\tau)}.
Proof.

The right-hand inequality is clear, so we focus on the left-hand one. Given v∈int⁡(τ)v\in\mathrm{int}(\tau) and e∈ℰ⁡(τ)e\in\mathcal{E}(\tau) we may write v=πe​(v)+t0​(e−πe​(v))v=\pi_{e}(v)+t_{0}\left(e-\pi_{e}(v)\right) for some 0<t0<10<t_{0}<1. Consider the restriction of φ\varphi to the segment [πe​(v),e][\pi_{e}(v),e], i.e. set θ⁡(t):=φ⁡(πe​(v)+t⁡(e−πe​(v))CLOSE\theta(t):=\varphi\left(\pi_{e}(v)+t(e-\pi_{e}(v)\right), t∈[0,1]t\in[0,1]. If we denote by θ′​(t)\theta^{\prime}(t) the right-derivative of θ\theta at tt then the convexity of θ\theta yields

(A.2) θ′​(0)≤(θ⁡(t0)−θ⁡(0))/t0\theta^{\prime}(0)\leq\left(\theta(t_{0})-\theta(0)\right)/t_{0}

and

(A.3) θ′​(0)≤θ′​(t0)≤(θ⁡(1)−θ⁡(t0))/(1−t0).\theta^{\prime}(0)\leq\theta^{\prime}(t_{0})\leq\left(\theta(1)-\theta(t_{0})\right)/(1-t_{0}).

Now, by definition, θ′​(0)=Dπe​(v)​φ​(e)\theta^{\prime}(0)=D_{\pi_{e}(v)}\varphi(e), t0​θ′​(0)=Dπe​(v)​φ​(v)t_{0}\theta^{\prime}(0)=D_{\pi_{e}(v)}\varphi(v) and (1−t0)​θ′​(t0)=Dv​φ​(e)(1-t_{0})\theta^{\prime}(t_{0})=D_{v}\varphi(e), so that (A.2) reads

t0​Dπe​(v)​φ​(e)≤φ⁡(v)−φ⁡(πe​(v)).t_{0}D_{\pi_{e}(v)}\varphi(e)\leq\varphi(v)-\varphi(\pi_{e}(v)).

Since we also have supτφ=sup∂τφ\sup_{\tau}\varphi=\sup_{\partial\tau}\varphi by convexity, this shows that

‖φ‖C0​(τ)≤‖φ‖C0​(∂τ)+supe∈ℰ⁡(τ),v∈int⁡(τ)|Dπe​(v)​φ​(e)|.\|\varphi\|_{C^{0}(\tau)}\leq\|\varphi\|_{C^{0}(\partial\tau)}+\sup_{e\in\mathcal{E}(\tau),v\in\mathrm{int}(\tau)}\left|D_{\pi_{e}(v)}\varphi(e)\right|.

On the other hand, (A.2) combined with (A.3) yields

(1−t0)​Dπe​(v)​φ​(e)≤Dv​φ​(e)≤φ⁡(e)−φ⁡(πe​(v))−t0​Dπe​(v)​φ​(e)(1-t_{0})D_{\pi_{e}(v)}\varphi(e)\leq D_{v}\varphi(e)\leq\varphi(e)-\varphi\left(\pi_{e}(v)\right)-t_{0}D_{\pi_{e}(v)}\varphi(e)

and we conclude by Lemma A.2 below. ∎

Lemma A.2.

There exists a constant C>0C>0 such that every Lipschitz continuous function φ:τ→𝐑\varphi:\tau\to\mathbf{R} satisfies

C−1​Lipτ⁡(φ)≤supe∈ℰ⁡(τ),v∈A|Dv​φ​(e)|≤C​Lipτ⁡(φ)C^{-1}\lip_{\tau}(\varphi)\leq\sup_{e\in\mathcal{E}(\tau),v\in A}|D_{v}\varphi(e)|\leq C\lip_{\tau}(\varphi)

where A⊂int⁡(τ)A\subset\mathrm{int}(\tau) denotes the set of points at which φ\varphi is differentiable.

Proof.

It is clear that |Dv​φ​(e)|≤diam⁡(τ)​Lipτ⁡(φ)|D_{v}\varphi(e)|\leq\diam(\tau)\lip_{\tau}(\varphi) for all e,ve,v. Conversely it is a standard consequence of Rademacher’s theorem that Lipτ⁡(φ)=supv∈A‖∇φ​(v)‖\lip_{\tau}(\varphi)=\sup_{v\in A}\|\nabla\varphi(v)\|. For each v∈Av\in A we also have Dv​φ​(e)=⟨∇φ​(v),e−v⟩D_{v}\varphi(e)=\langle\nabla\varphi(v),e-v\rangle. We now claim that there exists C>0C>0 such that

‖λ‖≤C​supe∈ℰ⁡(τ)|⟨λ,v−e⟩|\|\lambda\|\leq C\sup_{e\in\mathcal{E}(\tau)}|\langle\lambda,v-e\rangle|

for all λ∈V∗\lambda\in V^{*} and all v∈τv\in\tau, which will conclude the proof. Indeed the supremum in the right-hand side is a lower semicontinuous function of (λ,v)∈V∗×τ(\lambda,v)\in V^{*}\times\tau. As a consequence it achieves its infimum on the compact set {λ∈V∗,‖λ‖=1}×τ\{\lambda\in V^{*},\,\|\lambda\|=1\}\times\tau, and this infimum cannot be zero since {v−e,e∈ℰ⁡(τ)}\{v-e,\,e\in\mathcal{E}(\tau)\} spans VV for each v∈τv\in\tau. The claim follows by homogeneity. ∎

Original mathematics by the credited authors. Source-backed reader collection; mathematical self-containment is not assessed.