2
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Student
    Sep 15, 2015 at 16:16
  • $\begingroup$ (3) How do you think positive semi-definiteness would help in this context? $\endgroup$
    – Student
    Sep 15, 2015 at 16:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.