Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm trying to prove the submodularity of the product of two non-negative, monotone increasing submodular functions

Formally, we have $f$ and $g$ are submodular functions, that is, $f:2^{\Omega}\rightarrow \mathbb{R}$ and for every $S, T \subseteq \Omega$ we have that $f(S)+f(T)\geq f(S\cup T)+f(S\cap T)$.

We also have that $f$ and $g$ are non-negative: $f(.) \geq 0$

And are monotone increasing: $f(S) \leq f(T)$, for all sets $S \subseteq T$

I just wonder is there a way we can prove that $fg$ is submodular (or not)?

share|cite|improve this question
up vote 2 down vote accepted

Counter example:

$\Omega = \{a,b\}$. $f(\phi)=0$, $f(\{a\})=1$, $f)\{b\})=2$, $f(\{a,b\}) = 3$.

Multiply $f$ with itself. The result is not submodular.

share|cite|improve this answer
Thanks polkjh for the comment, it's been a while. I found from the Exercise 3.32 (b), page 119, S.Boyd's Convex Optimization book that the 2 functions must be 1 increasing and 1 decreasing to make the product function submodular. In this case, since they're both increasing, we can definitely build up a counter example like you did to show that the product is not submodular – HuyNA Mar 4 '13 at 23:52
@HuyNA One increasing and one decreasing look sufficient, but I think the condition is too strong. It might be possible to get a weaker condition for product being submodular, though I have no idea yet how. Anyway, thanks for pointing that out! – polkjh Mar 5 '13 at 4:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.