Consider a convex function $f : \mathbb{R}^d \to \mathbb{R}$. Define now the set-input function $g\_f : 2^{[d]} \to \mathbb{R}$ as follows,
\begin{align}
g\_f(S) = \min \left\{ f(x) : x \in \mathbb{R}^d \text{ and } \forall i \not\in S, x\_i = 0 \right\}.
\end{align}
In other words, $g\_f(S)$ is the minimum of $f$ when restricted to the coordinates in $S$.


Is it generally true that $g\_f$ is either submodular or supermodular?



Submodularity of a particular function derived from a convex function?
The answer is no. E.g., if $d=2$ and
$$f(x,y)=f\_c(x,y):=(x - 1)^2 + (y - 1)^2 - 2 c (x - 1) (y - 1) \tag{1}\label{1}$$
for some real $c\in(-1,1)$ and all real $x,y$,
then the function $f$ is convex. However, for $S=\{1\}$ and $T=\{2\}$ we have
$$\Delta\_f(S,T):=g\_f(S)+g\_f(T)-g\_f(S\cup T)-g\_f(S\cap T)=2(1-c)c,$$
which can actually be $>0$ or $<0$ depending on the sign of $c\in(-1,1)$.


So, $g\_f$ is neither generally submodular nor generally supermodular.




---


Letting now $d=4$ and
$$f(x,y,u,v):=f\_{1/2}(x,y)+f\_{-1/2}(u,v) \tag{2}\label{2}$$
for all real $x,y,u,v$ (with $f\_c$ given by \eqref{1}), we get one function $g\_f$ which is neither submodular nor supermodular. Indeed, for $f$ given by \eqref{2}, we have $\Delta\_f(\{1\},\{2\})=1/2>0$ and $\Delta\_f(\{3\},\{4\})=-3/2<0$.


