<p>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:</p>

<p>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).</p>

<p>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. </p>

<p>[1] <a href="https://hal.archives-ouvertes.fr/file/index/docid/535950/filename/submodular_tutorial.pdf" rel="nofollow">https://hal.archives-ouvertes.fr/file/index/docid/535950/filename/submodular_tutorial.pdf</a>
[2] <a href="http://www.ml.uni-saarland.de/Publications/HeinSetzer-BeyondSC%282011%29-Supplement.pdf" rel="nofollow">http://www.ml.uni-saarland.de/Publications/HeinSetzer-BeyondSC%282011%29-Supplement.pdf</a></p>

CC BY-SA 3.0
2015-09-15T16:16:27.913Z
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?
Student
CC BY-SA 3.0
2015-09-15T16:19:19.923Z
(3) How do you think positive semi-definiteness would help in this context?
Student
CC BY-SA 3.0
2015-09-15T08:05:38.750Z
2015-09-15T11:27:35.683Z
2015-09-15T11:27:35.683Z
mnmltype
<p>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. </p>

<ul>
<li><p>Is either of these questions for any class of $f$ known to be solvable in $poly(n)$ time? </p></li>
<li><p>For any class of $f$ is $f'$ known to become submodular? </p></li>
</ul>

<hr>

<p>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.  </p>

<np-hardness><convex-optimization><convex-geometry><submodularity><convex-hull>
When can a convex function induce submodularity?
Student
# When can a convex function induce submodularity?

(Asked by: username_0 on 2015-09-14)

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.

**Tags:** np-hardness, convex-optimization, convex-geometry, submodularity, convex-hull

---

## 1 answers

### Answer by username_1 on 2015-09-15. Score: 4 | Accepted answer

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>

> **Comments:**
> **username_0**: 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?  
> **username_0**: (3) How do you think positive semi-definiteness would help in this context?  

---

