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' &lt; 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. 

[1] https://hal.archives-ouvertes.fr/file/index/docid/535950/filename/submodular_tutorial.pdf
[2] http://www.ml.uni-saarland.de/Publications/HeinSetzer-BeyondSC%282011%29-Supplement.pdf