# When can a convex function induce submodularity?

Say I have a real valued convex function $f$ on the hypercube $[-1,1]^n$. Let $f'$ be the induced function on the discrete hypercube $\{-1,1\}^n$. Now I want to find a vertex on $\{-1,1\}^n$ on which either (1) $f' < c$ for some given constant $c$ or (2) $f'$ minimizes.

• Is either of these questions for any class of $f$ known to be solvable in $poly(n)$ time?

• For any class of $f$ is $f'$ known to become submodular?

Typically I am dealing with a $f(\vec{x}) = SpectralNorm ( A + \vec{x}.\vec{M} )$ where the matrices are $2n$ dimensional real symmetric matrices with entries in $\{0,1,-1 \}$ , $\vec{x} \in [-1,1]^n$ and the matrices in the coordinates of the vector (in matrix space) $\vec{M}$ being simultaneously diagonalizable. Any advice specific to this class would be most helpful.

The notion of sub-modularity you use is non-standard. Usually you consider set functions with domain $\lbrace 0, 1\rbrace^n$. But to answer your questions, the Lovász extension establishes the following relationship between sub-modularity and convexity:
A set-function $F$ is sub-modular if and only if its Lovász extension $f$ is convex. For a proof see Proposition 6 in [1]. To go a bit further, e.g. Proposition 2.3 in [2] establishes the fact the very set function can be written as a difference of two sub-modular function. Conversely, the Lovász extension of every set function is DC (difference of convex functions).
The converse is not true: Not every convex function restricted to $\lbrace 0, 1\rbrace^n$ is sub-modular. Form your description I assume that you matrix is positive semi-definite. But it is not clear to me how you define the convex $f(x)$? With that information, you can start checking sub-modularity.
• Thanks for the help! (1) I have clarified further the specific kind of $f(x)$ that I need to deal with. Does that help? (2) So you suggest that a way would be to show that my $f(\vec{x})$ is a Lovasz extension of my $f'(\vec{x})$? Any examples of such proof techniques? Like any previous example of trying to argue submodularity or Lovasz extension with spectral norms? Sep 15, 2015 at 16:16