Finite-mixture convex envelope and its supporting-face condition

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.