What is the motivation behind the , convex and concave closures of submodular functions?
Also, my understanding is that the submodularity condition is somewhat like concavity which makes it counter intuitive to me that maximizing them is hard. Does anyone have any intuition on this?
On
Having a continuous extension to any set function can be useful for reasons such as optimizing in continuous domain using gradient-based approaches and then rounding them to a set solution (See Pipage rounding).
Submodular functions exhibit convex and concave extensions. One possible convex extension is Lovasz Extension. On the other hand, it is NP-Hard to compute the Concave extension, therefore it might not be counter-intuitive now to see why submodular maximization is NP Hard.
Submodular functions act like concave function, as they share subadditivity property :
A concave function f such that f(0)=0 is subadditive.
A submodular function f such that f($\emptyset$) is subadditive.
We can't say a submodular function is concave as by nature a submodular function is a set function. Also having a definition of concave and convex closure of a function can be useful in several way, so it is for a set function.
In general we are used to minimize convex function and maximize them is more difficult. You can see a concave function $g$ as the opposite of a convex function $f=-g$, then it comes that maximizing a concave function is easier than minimizing one.