Nonsmooth Equilibrium

Suppose $f$ is convex and take $(x,r),(y,s)\in \mathrm{epi}f$. For $t\in [0,1]$, the chord inequality gives $f((1-t)x+ty)\le (1-t)f(x)+tf(y)\le (1-t)r+ts$, so $(1-t)(x,r)+t(y,s)\in \mathrm{epi}f$. Thus the epigraph is convex.

Conversely, if the epigraph is convex and $f(x),f(y)$ are finite, then $(x,f(x))$ and $(y,f(y))$ lie in it; their convex combination lies in it and gives the chord inequality. If either value is $+\mathrm{\infty }$ and its coefficient is positive, the right side is $+\mathrm{\infty }$ and the inequality is automatic; at $t=0$ or $t=1$ it is equality.

Suppose $\mathrm{epi}f$ is closed and fix $a\in \mathbb{R}$. For $n=d,d+1$ write $d_n(u,v)=({\sum }_{j=1}^n(u_j-v_j{)}^2{)}^{1\mathrm{/}2}$ for the Euclidean metric. The slice map $i_a(x)=(x,a)$ satisfies $d_{d+1}(i_a(x),i_a(y))=d_d(x,y)$. If $f(x)>a$, then $(x,a)\mathrm{\notin }\mathrm{epi}f$; closedness gives $\epsilon >0$ such that the $d_{d+1}$-ball of radius $\epsilon$ around $(x,a)$ misses $\mathrm{epi}f$. Whenever $d_d(x,y)<\epsilon$, the distance identity puts $(y,a)$ in that ball, so $f(y)>a$. Thus the complement of $\{y:f(y)\le a\}$ is open, and this weak sublevel set is closed.

Conversely suppose every weak sublevel set is closed and let $(x,r)\mathrm{\notin }\mathrm{epi}f$, so $r<f(x)$. Choose a finite real $a$ with $r<a<f(x)$ when $f(x)$ is finite, and choose $a=r+1$ when $f(x)=+\mathrm{\infty }$. The set $N=\{y:f(y)>a\}$ is an open neighborhood of $x$, as it is the complement of a closed weak sublevel set. Choose $\delta >0$ with $B_d(x,\delta )\subseteq N$ and $\eta >0$ with $r+\eta <a$. If $d_{d+1}((x,r),(y,s))<\min (\delta ,\eta )$, then $y\in N$ and $s<r+\eta <a<f(y)$, so $(y,s)\mathrm{\notin }\mathrm{epi}f$. The epigraph's complement therefore contains a ball around each of its points and is open, so the epigraph is closed.

Choose $e_0\in E$ and set $R=\mathrm{\parallel }z-e_0{\mathrm{\parallel }}_2+1$. The set $K=E\cap \{e:\mathrm{\parallel }z-e{\mathrm{\parallel }}_2\le R\}$ is nonempty and bounded; it is closed because $E$ is closed and the distance map is continuous by [L1]. Hence [L2] makes it compact, and the continuous function $e\mapsto \mathrm{\parallel }z-e{\mathrm{\parallel }}_2^2$ attains a minimum at some $e_{\ast }\in K$ by [L3].

This $e_{\ast }$ is nearest to $z$ in all of $E$: every $e\in E\setminus K$ satisfies $\mathrm{\parallel }z-e{\mathrm{\parallel }}_2>R>\mathrm{\parallel }z-e_0{\mathrm{\parallel }}_2\ge \mathrm{\parallel }z-e_{\ast }{\mathrm{\parallel }}_2$. Put $u=z-e_{\ast }$; since $z\mathrm{\notin }E$, $u\mathrm{\ne }0$.

Fix $e\in E$ and put $v=e-e_{\ast }$. For $0<t\le 1$, [F2] gives $e_{\ast }+tv\in E$, so minimality of $e_{\ast }$ and [F1] imply $2t⟨u,v⟩\le t^2\mathrm{\parallel }v{\mathrm{\parallel }}_2^2$. If $⟨u,v⟩>0$, then $v\mathrm{\ne }0$; setting $t=\min \{1,⟨u,v⟩\mathrm{/}\mathrm{\parallel }v{\mathrm{\parallel }}_2^2\}$ contradicts this inequality whether the minimum is $1$ or the quotient. Hence $⟨u,v⟩\le 0$.

Therefore $⟨u,e⟩\le ⟨u,e_{\ast }⟩$ for every $e\in E$, while $⟨u,z⟩=⟨u,e_{\ast }⟩+\mathrm{\parallel }u{\mathrm{\parallel }}_2^2>⟨u,e_{\ast }⟩$. Taking $c=⟨u,e_{\ast }⟩$ proves strict separation.

Since $x\in \mathrm{dom}f$, the value $⟨p,x⟩-f(x)$ is one of the values over which $f^{\ast }(p)$ is the supremum; the stated inequality follows.

Equality means every $y\in \mathrm{dom}f$ satisfies $⟨p,y⟩-f(y)\le ⟨p,x⟩-f(x)$, which rearranges to the subgradient inequality; for $y\mathrm{\notin }\mathrm{dom}f$ that inequality is automatic because $f(y)=+\mathrm{\infty }$. Conversely the subgradient inequalities make the value at $x$ a finite upper bound attained there, so $f^{\ast }(p)=⟨p,x⟩-f(x)$.

For any $x$ with $f(x)<+\mathrm{\infty }$ and any $p$ with $f^{\ast }(p)<+\mathrm{\infty }$, the defining supremum gives $f^{\ast }(p)\ge ⟨p,x⟩-f(x)$, hence $⟨p,x⟩-f^{\ast }(p)\le f(x)$; taking the supremum over $p$ yields $f^{\ast \ast }(x)\le f(x)$. If $f(x)=+\mathrm{\infty }$, the same upper bound is automatic.

Fix $x\in \mathrm{dom}f$ and a real $t<f(x)$. Apply [F3] to $(x,t)$ and the nonempty closed convex set $\mathrm{epi}f$, and negate the resulting separator to write $⟨a,y⟩+bs\ge c>⟨a,x⟩+bt$ for all $(y,s)\in \mathrm{epi}f$. Upward closure forces $b\ge 0$. If $b=0$, the inequality at $(x,f(x))\in \mathrm{epi}f$ would give $⟨a,x⟩\ge c>⟨a,x⟩$, impossible. Thus $b>0$.

Now fix $x\mathrm{\notin }\mathrm{dom}f$ and $t\in \mathbb{R}$. Apply [F3] to $(x,t)$ and negate the separator to obtain $⟨a,y⟩+bs\ge c>⟨a,x⟩+bt$ for all $(y,s)\in \mathrm{epi}f$. If $b>0$, then $f(y)\ge -⟨a\mathrm{/}b,y⟩+c\mathrm{/}b$ for every $y\in \mathrm{dom}f$, so with $p=-a\mathrm{/}b$ one has $f^{\ast }(p)\le -c\mathrm{/}b<+\mathrm{\infty }$ and $f^{\ast \ast }(x)\ge ⟨p,x⟩-f^{\ast }(p)\ge (c-⟨a,x⟩)\mathrm{/}b>t$.

Substituting $(y,f(y))$ for every $y\in \mathrm{dom}f$ gives the affine minorant $\mathrm{\ell }(y)=-⟨a\mathrm{/}b,y⟩+c\mathrm{/}b\le f(y)$. With $p=-a\mathrm{/}b$, [F4] gives $f^{\ast }(p)\le -c\mathrm{/}b$, hence $f^{\ast \ast }(x)\ge ⟨p,x⟩-f^{\ast }(p)\ge \mathrm{\ell }(x)>t$. Since this holds for every $t<f(x)$, $f^{\ast \ast }(x)\ge f(x)$ on $\mathrm{dom}f$.

In the $b=0$ case of step 1.3, the separator gives $⟨a,y⟩\ge c>⟨a,x⟩$ for every $y\in \mathrm{dom}f$. Choose $y_0\in \mathrm{dom}f$ and a finite $t_0<f(y_0)$. Apply [F3] to $(y_0,t_0)$ and $\mathrm{epi}f$, reversing the separator orientation to obtain $⟨a_0,y⟩+b_{0}s\ge c_0>⟨a_0,y_0⟩+b_0{t}_0$ for every $(y,s)\in \mathrm{epi}f$. Upward closure gives $b_0\ge 0$, and $b_0=0$ contradicts the inequality at $(y_0,f(y_0))$, so $b_0>0$. Set $p_0=-a_0\mathrm{/}{b}_0$ and $r_0=c_0\mathrm{/}{b}_0$; substituting $(y,f(y))$ gives the affine minorant ${\mathrm{\ell }}_0(y)=⟨p_0,y⟩+r_0\le f(y)$ on $\mathrm{dom}f$, so [F4] gives $f^{\ast }(p_0)\le -r_0$. For each positive integer $k$, define ${\mathrm{\ell }}_k(y)={\mathrm{\ell }}_0(y)+k(c-⟨a,y⟩)=⟨p_0-ka,y⟩+(r_0+kc)$. Since $c-⟨a,y⟩\le 0$ on $\mathrm{dom}f$, this is still a minorant; [F4] gives $f^{\ast }(p_0-ka)\le -(r_0+kc)<+\mathrm{\infty }$ and hence $f^{\ast \ast }(x)\ge {\mathrm{\ell }}_k(x)={\mathrm{\ell }}_0(x)+k\delta$, where $\delta :=c-⟨a,x⟩>0$ by step 1.3. For any prescribed $B\in \mathbb{R}$, apply [L1] to $q=(B-{\mathrm{\ell }}_0(x))\mathrm{/}\delta$ to choose a positive integer $k$ with $q<k$; multiplying by $\delta >0$ gives ${\mathrm{\ell }}_0(x)+k\delta >B$. Hence $f^{\ast \ast }(x)$ exceeds every real bound, so $f^{\ast \ast }(x)=+\mathrm{\infty }=f(x)$.

The upper bound from step 1.1 and the lower bounds from steps 2.1 and 2.2 cover respectively finite and infinite values of $f(x)$, proving equality everywhere.

Since $f$ is proper, choose $x_0\in \mathrm{dom}f$ and put $c=g(x_0)\in \mathbb{R}$. By coercivity, first choose a radius $R_0>0$ such that $g(x)>c+1$ whenever $\mathrm{\parallel }x{\mathrm{\parallel }}_2\ge R_0$, then enlarge it to $R>\max \{R_0,\mathrm{\parallel }{x}_0{\mathrm{\parallel }}_2\}$; the same implication holds for this $R$. Let $K=\{x:\mathrm{\parallel }x{\mathrm{\parallel }}_2\le R\}$; it is nonempty, closed, bounded, and therefore compact by [L3].

The epigraph of $g$ is $T^{-1}(\mathrm{epi}f)$, because $g(x)\le r$ exactly when $f(x)\le r+⟨p,x⟩$. By [L1], $\mathrm{epi}f$ is closed. Fix $z\mathrm{\notin }{T}^{-1}(\mathrm{epi}f)$; openness of the complement of $\mathrm{epi}f$ gives $\epsilon >0$ such that the Euclidean ball of radius $\epsilon$ around $Tz$ misses $\mathrm{epi}f$. Set $\rho =\epsilon \mathrm{/}(K+1)>0$. If $\mathrm{\parallel }{z}^{\mathrm{\prime }}-z{\mathrm{\parallel }}_2<\rho$, [L2] gives $\mathrm{\parallel }T{z}^{\mathrm{\prime }}-Tz{\mathrm{\parallel }}_2\le K\mathrm{\parallel }{z}^{\mathrm{\prime }}-z{\mathrm{\parallel }}_2<\epsilon$, so $T{z}^{\mathrm{\prime }}$ also lies outside $\mathrm{epi}f$. Thus the complement of $T^{-1}(\mathrm{epi}f)$ is open and $\mathrm{epi}g$ is closed. By [L1], $g$ is lower semicontinuous.

For each real $r>0$, $U_r=\{x\in K:g(x)>-r\}$ is relatively open in $K$, since its complement is the weak sublevel $K\cap \{g\le -r\}$. These sets cover $K$ because $g(x)\in \mathbb{R}\cup \{+\mathrm{\infty }\}$ for every $x$ (properness excludes $-\mathrm{\infty }$ and the tilt is finite). Compactness gives a finite subcover, and [L6] supplies a largest real index $r_{\ast }$ among its finitely many indices. Since the $U_r$ are nested, $U_{r_{\ast }}=K$, so every finite value of $g$ on $K$ is greater than $-r_{\ast }$.

Let $S:=\{g(x):x\in K,g(x)<+\mathrm{\infty }\}$. It is nonempty because $x_0\in K$ and $g(x_0)=c$, and it is a real set bounded below by $-r_{\ast }$ by step 2.1. It therefore has a real infimum $m$. For every $\epsilon >0$, [L5] gives $s\in S$ with $s<m+\epsilon$; choosing $x\in K$ with $g(x)=s$ shows $F_{\epsilon }:=K\cap \{x:g(x)\le m+\epsilon \}$ is nonempty. It is closed in $K$ by [L1]. Any nonempty finite subfamily has nonempty intersection, because the member with least positive $\epsilon$ is contained in all the others; the empty subfamily has intersection $K\mathrm{\ne }\mathrm{\varnothing }$.

Applying [L4] to the family $(F_{\epsilon }{)}_{\epsilon >0}$ gives $x_{\ast }\in {\bigcap }_{\epsilon >0}{F}_{\epsilon }$. The bound $g(x_{\ast })\le m+1$ makes $g(x_{\ast })$ finite, so $g(x_{\ast })\in S$ and $m\le g(x_{\ast })$. If $g(x_{\ast })>m$, choose $\epsilon =(g(x_{\ast })-m)\mathrm{/}2>0$; then $x_{\ast }\in F_{\epsilon }$ would give $g(x_{\ast })\le m+\epsilon <g(x_{\ast })$, a contradiction. Thus $g(x_{\ast })=m$.

For $x\mathrm{\notin }K$, step 1.1 gives $g(x)>c+1\ge m+1$, because $x_0\in K$ implies $m\le c$. Thus $x_{\ast }$ is a global minimizer over ${\mathbb{R}}^d$, and its value $m$ is finite.

On $\mathrm{dom}f$, $-g(x)=⟨p,x⟩-f(x)$, and outside this domain $g(x)=+\mathrm{\infty }$. The global minimum $m$ is attained at $x_{\ast }\in \mathrm{dom}f$, so the supremum in the definition of $f^{\ast }(p)$ is finite, equals $-m$, and is attained at $x_{\ast }$. Therefore $f^{\ast }(p)=⟨p,x_{\ast }⟩-f(x_{\ast })$; [L7] yields $p\in \mathrm{\partial }f(x_{\ast })$.

The set ${\mathrm{\Delta }}_m$ contains each coordinate vector. The coordinate maps, the sum map $\theta \mapsto {\sum }_i{\theta }_i$, and $Q$ are continuous by [L1]. For any continuous map $T$ into a Euclidean space and any closed set $K$, the complement of $T^{-1}(K)$ is open: if $T(z)\mathrm{\notin }K$, a ball about $T(z)$ misses $K$, and continuity gives a ball about $z$ mapped inside that ball. Thus $T^{-1}(K)$ is closed. Coordinate half-lines $[0,\mathrm{\infty })$ and singletons are closed, since a point outside either has a positive-distance ball missing it; a finite intersection of closed sets is closed because its complement is a finite union of open sets. These facts show that ${\mathrm{\Delta }}_m$ is closed and that ${\mathrm{\Theta }}_x={\mathrm{\Delta }}_m\cap Q^{-1}(\{x\})$ is closed. Since $0\le {\theta }_i\le 1$ on ${\mathrm{\Delta }}_m$, both sets are bounded and hence compact by [F1]. For $x\in P$, the definition of $P$ makes ${\mathrm{\Theta }}_x$ nonempty. The linear objective is continuous by [L1] and attains its minimum on ${\mathrm{\Theta }}_x$ by [F3].

Let $C=\{{\sum }_i{\theta }_i(q_i,a_i):\theta \in {\mathrm{\Delta }}_m\}\subset {\mathbb{R}}^{d+1}$ and $V=\{(0,s):s\ge 0\}$. The affine map defining $C$ is continuous by [L1], so $C$ is compact by [F2]. The set $C$ is convex because convex combinations of points in ${\mathrm{\Delta }}_m$ remain in ${\mathrm{\Delta }}_m$ (nonnegativity and the unit-sum equation are preserved) and the defining map is affine; $V$ is closed and convex. If $(x,r)\in \mathrm{epi}{f}_{\mathrm{m}\mathrm{i}\mathrm{x}}$, a minimizing $\theta \in {\mathrm{\Theta }}_x$ gives $(x,f_{\mathrm{m}\mathrm{i}\mathrm{x}}(x))\in C$ and $r-f_{\mathrm{m}\mathrm{i}\mathrm{x}}(x)\ge 0$, so $(x,r)\in C+V$. Conversely if $(x,r)={\sum }_i{\theta }_i(q_i,a_i)+(0,s)$ with $s\ge 0$, then $f_{\mathrm{m}\mathrm{i}\mathrm{x}}(x)\le {\sum }_i{\theta }_i{a}_i\le r$. Thus $\mathrm{epi}{f}_{\mathrm{m}\mathrm{i}\mathrm{x}}=C+V$.

The coordinate vector with ${\theta }_i=1$ and all other weights zero shows $f_{\mathrm{m}\mathrm{i}\mathrm{x}}(q_i)\le a_i$. Let $h:{\mathbb{R}}^d\to \bar{\mathbb{R}}$ be convex with $h(q_i)\le a_i$. For any weights $\theta \in {\mathrm{\Delta }}_m$, prove $h({\sum }_i{\theta }_i{q}_i)\le {\sum }_i{\theta }_{i}h(q_i)$ by induction on the number $N$ of positive weights: for $N=1$ it is equality; for $N>1$, choose an index $j$ with $0<{\theta }_j<1$, put $y=(1-{\theta }_j{)}^{-1}{\sum }_{i\mathrm{\ne }j}{\theta }_i{q}_i$, and apply the induction hypothesis to the normalized remaining weights. Convexity then gives $h({\sum }_i{\theta }_i{q}_i)\le {\theta }_{j}h(q_j)+(1-{\theta }_j)h(y)\le {\sum }_i{\theta }_{i}h(q_i)$. All terms on the right are finite because $h(q_i)\le a_i$ and the codomain excludes $-\mathrm{\infty }$. For $x\in P$ and any $\theta \in {\mathrm{\Theta }}_x$, this gives $h(x)\le {\sum }_i{\theta }_i{a}_i$; taking the minimum yields $h(x)\le f_{\mathrm{m}\mathrm{i}\mathrm{x}}(x)$. For $x\mathrm{\notin }P$, $h(x)\le +\mathrm{\infty }=f_{\mathrm{m}\mathrm{i}\mathrm{x}}(x)$. Thus $f_{\mathrm{m}\mathrm{i}\mathrm{x}}$ is the greatest convex minorant of the data.

The set $C+V$ is convex: for $c_1,c_2\in C$, $v_1,v_2\in V$, and $t\in [0,1]$, $(1-t)(c_1+v_1)+t(c_2+v_2)=((1-t)c_1+t{c}_2)+((1-t)v_1+t{v}_2)\in C+V$ by [F5]. To see it is closed, fix $z=(x,r)\mathrm{\notin }C+V$ and write $c=(u,a)\in C$. The distance from $z$ to the ray $c+V$ is ${\rho }_z(c)=\sqrt{\mathrm{\parallel }x-u{\mathrm{\parallel }}_2^2+\max \{a-r,0{\}}^2}$: if $r\ge a$ the closest ray point has height $r$, and if $r<a$ it has height $a$. This formula is continuous in $c$ because $\max \{w,0\}=(w+\mathrm{\mid }w\mathrm{\mid })\mathrm{/}2$, and it is positive for every $c\in C$ since $z\mathrm{\notin }c+V$. Compactness of $C$ and [F3] give a minimum $\delta >0$; every point of $C+V$ is at distance at least $\delta$ from $z$, so the ball of radius $\delta \mathrm{/}2$ about $z$ misses $C+V$.

By [F4] and step 3.1, $f_{\mathrm{m}\mathrm{i}\mathrm{x}}$ is convex and lower semicontinuous. It is proper because $P$ is nonempty, each value on $P$ is finite by step 1.1, and it is $+\mathrm{\infty }$ outside $P$. Therefore [F6] gives $f_{\mathrm{m}\mathrm{i}\mathrm{x}}=f_{\mathrm{m}\mathrm{i}\mathrm{x}}^{\ast \ast }$.

Let $p\in \mathrm{\partial }{f}_{\mathrm{m}\mathrm{i}\mathrm{x}}(x)$ and let $\theta$ attain the minimum defining $f_{\mathrm{m}\mathrm{i}\mathrm{x}}(x)$. By [F7], $f_{\mathrm{m}\mathrm{i}\mathrm{x}}^{\ast }(p)=⟨p,x⟩-f_{\mathrm{m}\mathrm{i}\mathrm{x}}(x)$. Also $f_{\mathrm{m}\mathrm{i}\mathrm{x}}(q_i)\le a_i$ implies $⟨p,q_i⟩-a_i\le ⟨p,q_i⟩-f_{\mathrm{m}\mathrm{i}\mathrm{x}}(q_i)\le f_{\mathrm{m}\mathrm{i}\mathrm{x}}^{\ast }(p)$. Since $⟨p,x⟩-f_{\mathrm{m}\mathrm{i}\mathrm{x}}(x)={\sum }_i{\theta }_i(⟨p,q_i⟩-a_i)$ is a weighted average of terms bounded above by $f_{\mathrm{m}\mathrm{i}\mathrm{x}}^{\ast }(p)$, each term with ${\theta }_i>0$ equals that bound, proving the supporting-hyperplane formula.

By [A1] and [L1], each $a_i=S(s_i)$ is finite. For any $\theta \in {\mathrm{\Delta }}_m$, [L2] gives $m(M_{\theta })={\sum }_i{\theta }_{i}m(e_{s_i})={\sum }_i{\theta }_i=1$. If ${\theta }_i=0$, its term is the empty compound and contributes zero; equivalently omit such terms, leaving only positive coefficients and never applying a positive-scaling comparison axiom at zero. The representation assigns $M_{\theta }$ the value $V(\theta )={\sum }_i{\theta }_i{a}_i$. By [A3], its coordinate is ${\sum }_i{\theta }_i{q}_i$. Since the states are distinct, the coefficient of $s_i$ in $M_{\theta }$ is exactly ${\theta }_i$, so this parametrization is injective. Hence mixtures in this fixed family with coordinate $x$ correspond exactly to $\theta \in {\mathrm{\Theta }}_x$ from [L3].