Convex and Semicontinuous Functions on R^n

For the forward implication, take $(x,r),(y,s)\in \mathrm{epi}f$ and $t\in [0,1]$. By [F1], $f((1-t)x+ty)\le (1-t)f(x)+tf(y)\le (1-t)r+ts,$ so [F2] puts the convex combination in the epigraph.

For the reverse implication, assume the epigraph convex and apply its convexity to $(x,f(x))$ and $(y,f(y))$. By [F2], membership of their convex combination is exactly the inequality in [F1]. Thus $f$ is convex; if $C$ is empty, both conditions are vacuous.

For $N=1$, the only nonnegative weight summing to one is ${\lambda }_1=1$, so both sides equal $f(x_1)$.

Fix $N\ge 1$ and assume the inequality for every weighted family of $N$ points.

For $N+1$ points, if ${\lambda }_{N+1}=1$, then all earlier nonnegative weights vanish and the conclusion is immediate. Otherwise $s=1-{\lambda }_{N+1}>0$, and the normalized weights ${\mu }_j={\lambda }_j\mathrm{/}s$ for $j\le N$ are nonnegative and sum to one.

Apply the induction hypothesis to $z={\sum }_{j=1}^N{\mu }_j{x}_j\in C$, then apply [F1] to $z,x_{N+1}$ with weights $s,{\lambda }_{N+1}$. The resulting inequality is exactly the $(N+1)$-point formula, completing the induction.

If $f(x),f(y)\le \alpha$, then [F1] gives $f((1-t)x+ty)\le (1-t)f(x)+tf(y)\le \alpha$ for every $t\in [0,1]$.

Thus every segment between two sublevel points remains in the sublevel set, which is convex. If it has fewer than two points, the same condition is vacuous.

For a nonnegative finite combination, multiply the inequality [F1] for $f_j$ by $a_j\ge 0$ and add over $j$. This gives the convexity inequality for ${\sum }_j{a}_j{f}_j$.

An affine map satisfies $A((1-t)x+ty)=(1-t)A(x)+tA(y)$. Applying [F1] to the outer function gives convexity of $f\circ A$ on the convex preimage domain.

Let $g={\max }_j{f}_j$. For each $j$, [F1] gives $f_j((1-t)x+ty)\le (1-t)f_j(x)+t{f}_j(y)\le (1-t)g(x)+tg(y)\mathrm{.}$ Taking the nonempty finite maximum over $j$ proves the inequality for $g$.

Let $x,y\in D$ and $t\in [0,1]$. For every $i$, [F1] gives $f_i((1-t)x+ty)\le (1-t)f_i(x)+t{f}_i(y)\le (1-t)g(x)+tg(y)\mathrm{.}$ This common finite upper bound and [L1] show that the supremum exists at the combined point, so that point lies in $D$ and $D$ is convex.

The common upper bound from step 1.1 also bounds the least upper bound supplied by [L1]. Hence $g((1-t)x+ty)\le (1-t)g(x)+tg(y),$ which is [F1] for $g$.

Every point of $Q(a,r)$ is an explicit convex combination of its finite vertex set. By [L1], its value is at most the corresponding weighted average of the vertex values, hence at most their maximum $M$.

If $x\in Q(a,r\mathrm{/}2)$, then the reflection $2a-x$ lies in $Q(a,r)$ and $a=(x+(2a-x))\mathrm{/}2$. Convexity gives $f(a)\le (f(x)+f(2a-x))\mathrm{/}2$, so step 1.1 yields $2f(a)-M\le f(x)\le M\mathrm{.}$ Thus the half-sized cube has both bounds.

If $U=\mathrm{\varnothing }$, the conclusion is vacuous. If $n=0$ and $U$ is nonempty, then $U={\mathbb{R}}^0$ is a singleton and $f$ is Lipschitz with constant zero. Hence assume $n\ge 1$ and fix $a\in U$. Choose $r>0$ such that $Q(a,2r)\subseteq U$. Apply [L1] to obtain $M\ge 0$ with $\mathrm{\mid }f\mathrm{\mid }\le M$ on the half cube $Q(a,r)$, and use $Q(a,r\mathrm{/}2)$ as the inner cube of test points.

Take distinct $x,y\in Q(a,r\mathrm{/}2)$, put $d=\mathrm{\parallel }y-x{\mathrm{\parallel }}_{\mathrm{\infty }}$, and extend the ray from $x$ through $y$ until it first reaches $z\in \mathrm{\partial }Q(a,r)$. Writing $z=x+s(y-x)\mathrm{/}d$, one has $s\ge r\mathrm{/}2$ and $y=(1-d\mathrm{/}s)x+(d\mathrm{/}s)z$. Convexity and step 1.1 give $f(y)-f(x)\le 4Md\mathrm{/}r$; reversing $x,y$ gives $\mathrm{\mid }f(y)-f(x)\mathrm{\mid }\le 4M\mathrm{\parallel }x-y{\mathrm{\parallel }}_{\mathrm{\infty }}\mathrm{/}r$.

Since $\mathrm{\parallel }x-y{\mathrm{\parallel }}_{\mathrm{\infty }}\le \mathrm{\parallel }x-y{\mathrm{\parallel }}_2$, step 2.1 is the condition [F1] on $Q(a,r\mathrm{/}2)$ with constant $4M\mathrm{/}r$. Hence $f$ is locally Lipschitz at every $a\in U$.

At each $a\in U$, [L1] gives a neighbourhood on which the restriction of $f$ is Lipschitz, and [L2] makes that restriction continuous.

Thus $f$ is continuous at every domain point, hence continuous on $U$; if $U$ is empty, there is no point to check.

Choose $c_0\in C$ and put $R=\mathrm{\parallel }x-c_0{\mathrm{\parallel }}_2$. The set $K=C\cap \bar{B}(x,R)$ is nonempty, closed, and bounded, hence compact by [L1]. The continuous distance $z\mapsto \mathrm{\parallel }x-z{\mathrm{\parallel }}_2$ attains a minimum at some $p\in K$ by [L2]. Points of $C\setminus K$ have distance greater than $R$, so $p$ minimizes distance over all of $C$.

Suppose distinct $p,q\in C$ both minimize the squared distance at $d^2$. Convexity puts $(p+q)\mathrm{/}2$ in $C$, while [L3] gives ${\parallel x-\frac{p+q}{2}\parallel }_2^2=d^2-\frac{1}{4}\mathrm{\parallel }p-q{\mathrm{\parallel }}_2^2<d^2,$ contradicting minimality. Thus the nearest point is unique.

For the forward implication, let $p$ be the nearest point and take $z\in C$. For $0<t\le 1$, convexity puts $p+t(z-p)$ in $C$. Comparing its squared distance with the minimum in [L1] and expanding gives $2⟨x-p,z-p⟩\le t\mathrm{\parallel }z-p{\mathrm{\parallel }}_2^2\mathrm{.}$ If the left inner product were positive, a sufficiently small $t>0$ would violate this inequality, so it is nonpositive.

For the reverse implication, suppose the displayed variational inequality holds. Expanding gives $\mathrm{\parallel }x-z{\mathrm{\parallel }}_2^2=\mathrm{\parallel }x-p{\mathrm{\parallel }}_2^2+\mathrm{\parallel }z-p{\mathrm{\parallel }}_2^2-2⟨x-p,z-p⟩\ge \mathrm{\parallel }x-p{\mathrm{\parallel }}_2^2\mathrm{.}$ Thus $p$ satisfies the nearest-point condition of [L1].

Let $p$ be the nearest point supplied by [L2] and put $a=x-p$. By [L1], $⟨a,z⟩\le ⟨a,p⟩$ for every $z\in C$. Since $x\mathrm{\notin }C$, one has $a\mathrm{\ne }0$ and $⟨a,x⟩=⟨a,p⟩+\mathrm{\parallel }a{\mathrm{\parallel }}_2^2>⟨a,p⟩\mathrm{.}$

Taking $b=⟨a,p⟩$ in step 1.1 gives the stated strict separation with a nonzero normal.

Using [A2], paired sequences from $C$ and [F1] show by [L1] that $\bar{C}$ is convex. Fix $c_0\in C$ and put $W=\mathrm{span}(C-c_0)$ and $A=c_0+W$, the affine hull by [L2]. By [A1], [L3], and [L4], $W$ has a finite basis drawn from $C-c_0$. If $W=\{0\}$, then $W$ and the singleton $A$ are closed directly. Otherwise its positive-dimensional coordinate map pulls the Euclidean norm back to a norm on ${\mathbb{R}}^d$; [L5] and [L6] show that a convergent sequence in $W$ has its limit in $W$. Thus [L1] and [L8] make $W$, and hence $A$, closed in every case. Therefore $C$ and $\bar{C}$ have the same affine hull.

The basis vectors from step 1.1 give points of $C$ whose simplex has a positive barycentric core, so $C$ has nonempty relative interior. Fix a relative ball $B_A(p,r)\subseteq C$ and $y\in \bar{C}$. For $q=(1-t)p+ty$ with $0\le t<1$, [A2] and [L1] give a sequence $y_k\in C$ tending to $y$; choose a term so close that $t\mathrm{\parallel }y-y_k{\mathrm{\parallel }}_2<(1-t)r\mathrm{/}2$. If $h\in W$ and $\mathrm{\parallel }h{\mathrm{\parallel }}_2<(1-t)r\mathrm{/}2$, then $p_h=p+\frac{t(y-y_k)+h}{1-t}$ lies in $A$ and within distance $r$ of $p$, hence lies in $B_A(p,r)$, while $q+h=(1-t)p_h+t{y}_k\in C$ by [F1]. Thus a relative ball about every strict segment point lies in $C$, so every such point belongs to $\mathrm{ri}C$.

Let $x\in \mathrm{ri}(\bar{C})$. If $x\mathrm{\ne }p$, choose small $\epsilon >0$ such that $y=x+\epsilon (x-p)$ remains in a relative ball of $\bar{C}$ about $x$; then $x=\frac{\epsilon }{1+\epsilon }p+\frac{1}{1+\epsilon }y,$ so step 2.1 gives $x\in \mathrm{ri}C$. The case $x=p$ and the reverse inclusion are immediate. If $W={\mathbb{R}}^n$, relative and ordinary interiors agree. If $W$ is proper, choose $v\mathrm{\notin }W$; every ambient ball about $A$ contains a point displaced by a small nonzero multiple of $v$ and hence outside $A$, so both ordinary interiors are empty. Thus $\mathrm{int}C=\mathrm{int}\bar{C}$.

By [L8], $\overline{\stackrel{‾}{C}}=\bar{C}$. Combining this common closure with step 3.1 and the boundary formula [L7] gives $\mathrm{\partial }C=\mathrm{\partial }\bar{C}$.

By [A1], [A2], and [L0], $a$ remains a boundary point after replacing $C$ by the closed convex set $\bar{C}$. Since every ball about $a$ meets the complement, the sequence-producing direction of A point lies in the closure of $A$ iff some sequence in $A$ converges to it, and a set is closed iff it is sequentially closed uses [A2] to choose $x_j\mathrm{\notin }\bar{C}$ with $x_j\to a$. Apply [L1] to each $x_j$ and normalize its separating normal $u_j$ to length one; then $⟨u_j,z-x_j⟩<0(z\in \bar{C})\mathrm{.}$

The unit normals are bounded, so [L2] gives a subsequence converging to a vector $u$ of norm one. For fixed $z\in \bar{C}$, pass the inequalities of step 1.1 to the limit, using $x_j\to a$, to obtain $⟨u,z-a⟩\le 0$. The unit vector $u$ is nonzero, and the inequality holds in particular for $z\in C$.

Put $E=C-D=\{c-d:c\in C,d\in D\}$. It is nonempty and convex and omits zero because $C\cap D=\mathrm{\varnothing }$. By [L3], $\bar{E}$ is convex. Either $0\mathrm{\notin }\bar{E}$, or $0\in \bar{E}\setminus E$ and therefore $0\in \mathrm{\partial }E$, since an interior point of $E$ would belong to $E$.

In the first case, apply [L1] to $0$ and $\bar{E}$; in the second, [A1] licenses the hypotheses of [L2], which applies to $E$ at zero. Each branch gives a nonzero $a$ with $⟨a,e⟩\le 0$ for every $e\in E$. Substituting $e=c-d$ gives $⟨a,c⟩\le ⟨a,d⟩$ for all $c\in C,d\in D$.

Choose a closed ball $B$ centred at $a$ and contained in $\mathrm{int}C$. The restricted epigraph $E=\{(x,s):x\in B,f(x)\le s\}$ is closed by continuity and convex by [L1]. The point $(a,f(a))$ is on its boundary, so [A1] licenses the hypotheses of [L2], which gives a supporting normal $(u,\mu )\mathrm{\ne }0$. Since the epigraph contains every upward vertical ray, $\mu \le 0$; if $\mu =0$, the ball contains small displacements from $a$ in both directions and forces $u=0$, impossible. Thus $\mu <0$, and rescaling to $\mu =-1$ gives $f(x)\ge f(a)+⟨u,x-a⟩$ on $B$.

Let $y\in C$. Choose $0<t\le 1$ so that $z=a+t(y-a)\in B$. The local inequality from step 1.1 gives $f(z)\ge f(a)+t⟨u,y-a⟩$, while convexity gives $f(z)\le (1-t)f(a)+tf(y)$. Combining and dividing by $t>0$ yields $f(y)\ge f(a)+⟨u,y-a⟩$. Thus $u\in \mathrm{\partial }f(a)$.

For the forward implication, fix $x,y\in U$ and put $d=y-x$. For $0<t\le 1$, convexity gives $f(x+td)\le (1-t)f(x)+tf(y)$, hence $\frac{f(x+td)-f(x)}{t}\le f(y)-f(x)\mathrm{.}$ By [L1] the left side tends to $⟨\mathrm{\nabla }f(x),d⟩$ as $t\downarrow 0$, giving the displayed gradient inequality.

For the reverse implication, assume the gradient inequality and take $z=(1-t)x+ty$. Apply it at $z$ toward $x$ and toward $y$, multiply the results by $1-t$ and $t$, and add. The gradient terms cancel because $(1-t)(x-z)+t(y-z)=0$, leaving $f(z)\le (1-t)f(x)+tf(y)$. Thus $f$ is convex.

Fix $y\in U$ and put $d=y-a$. For $0<t\le 1$, [F1] gives $f(a+td)\le (1-t)f(a)+tf(y)$, hence $\frac{f(a+td)-f(a)}{t}\le f(y)-f(a)\mathrm{.}$ Differentiability at $a$ makes the left side tend to $⟨\mathrm{\nabla }f(a),d⟩$ as $t\downarrow 0$. Thus $f(y)\ge f(a)+⟨\mathrm{\nabla }f(a),y-a⟩$ for every $y\in U$, so $\mathrm{\nabla }f(a)\in \mathrm{\partial }f(a)$.

Let $v\in \mathrm{\partial }f(a)$. For each coordinate vector $e_i$ and sufficiently small positive and negative $t$, apply the subgradient inequality at $a+t{e}_i$. Dividing by $t$ with the appropriate reversal and taking the two one-sided limits gives $v_i\le {\mathrm{\partial }}_{i}f(a)$ and $v_i\ge {\mathrm{\partial }}_{i}f(a)$. Thus $v=\mathrm{\nabla }f(a)$, proving the singleton claim.