2
$\begingroup$

Given a real valued convex function $g$ on $[-1,1]^n$, let $f$ be the restriction of it on the hypercube $\{-1,1\}^n$. I want to find a vertex on the hypercube $\{-1,1\}^n$ on which either (1) $f$ minimizes or (2) $f < c$ for some some constant $c$.

  • Is this kind of a question known to be doable in deterministic $poly(n)$ time?

I would be happy to be pointed out to any relevant literature in this direction which might help.

The typical kind of $g$ that I need are roughly of the form, $g (x) = SpectralNorm (A + x_1M_! + x_2M_2 +..+x_nM_n)$ where $x \in [-1,1]^n$. Where $A$ and $M$s are symmetric matrices of dimension $2n$ with entries in $\{0,1,-1\}$ and the $M$ matrices are simultaneously diagonalizable.

Any advice specific to such functions would be greatly appreciated.

Improve this question
$\endgroup$
1
  • $\begingroup$ Minimizing a general convex function $g(x)$ of $x=(x_1, ..., x_n)$ over discrete points $x_i \in \{-1,1\}$ is NP hard for general convex functions $g$. I don't know about your fixed structure of $g$. $\endgroup$
    – Michael
    Commented Sep 14, 2015 at 23:43

0

Reset to default

You must log in to answer this question.