Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer 1

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|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
add comment

Your Answer

 
discard

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.