2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Is $f$ assumed to be bounded from below? $\endgroup$ Commented May 23, 2023 at 21:44
  • $\begingroup$ @IosifPinelis It is ok to assume that $f$ is bounded from below. I would be happy to see a proof of this claim even if it means imposing stronger assumptions (or a counter-example if it is not generally true) $\endgroup$
    – Television
    Commented May 23, 2023 at 22:02

1 Answer 1

4
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .