Minimize the maximum inner product with vectors in a given set

Let vector $\mathrm v \in \mathbb R^n$ live in the following finite set

$$\mathcal V := \left\{ \mathrm v_1, \mathrm v_2, \dots, \mathrm v_m \right\} \subset (\mathbb R_0^+)^n$$

Introducing an optimization variable $t \in \mathbb R$, we solve the following optimization problem

$$\begin{array}{ll} \underset{\mathrm x \in \mathbb R^n, \, t \in \mathbb R}{\text{minimize}} & t\\ \text{subject to} & \mathrm v_1^\top \mathrm x \leq t\\ & \mathrm v_2^\top \mathrm x \leq t\\ & \quad\vdots\\ & \mathrm v_m^\top \mathrm x \leq t\\ & \| \mathrm x \|_2 = 1\\ & \mathrm x \geq 0_n \end{array}$$

or, more succinctly,

$$\boxed{\begin{array}{ll} \underset{\mathrm x \in \mathbb R^n, \, t \in \mathbb R}{\text{minimize}} & t\\ \text{subject to} & \mathrm V^\top \mathrm x \leq t \mathbb 1_m\\ & \| \mathrm x \|_2 = 1\\ & \mathrm x \geq 0_n \end{array}}$$

where

$$\mathrm V := \begin{bmatrix} | & | & & |\\ \mathrm v_1 & \mathrm v_2 & \dots & \mathrm v_m\\ | & | & & |\end{bmatrix}$$

My friend and I just published a paper on a very similar version of this problem - we consider it for arbitrary unit vectors in $S$ and $x$ is also an abritrary unit vector. We were basically able to derive matching upper and lower bounds. We call the problem "SphericalDiscrepancy." The problem is APX-Hard, but we mention some algorithms that work well in practice, including our own (our algorithm has an embarrassingly large running time, but its polynomial in the input anyway). The paper can be found here. A survey on the problem can be found here (friend's thesis).

For your case, the non-negativity constraints don't matter in terms of lower bounds when $|S| = O(n)$, any positive orthonormal basis will have $x^Tv \geq 1/\sqrt(n)$ for some $v\in S$.

My heart tells me that the same is true for upper bounds, but I would have to think about it longer. It seems close to the boolean discrepancy problem, where $S \subseteq \{ 0, 1 \}^n $, but $x \in \{ \pm 1 \} ^n $.

Note that there is no LP version of this problem, as the unit sphere is non-convex. Standard convex optimization techniques don't really apply here; at least not obviously.

EDIT: Some special Cases (somewhat hand-wavy proofs).

Upper Bound

I'm using soubscript R to denote sampling uniformly at random below... Let $x \sim_{R} \{0,1\}^n$ and suppose that $x$ has $\approx$ half of its entries set to 1. Let $S \subseteq_{R} \{0,1\}^n$, with $S = \{v_1 , \dots, v_m \}$ Let $Y_i$ indicate the event that $|x^Tv_i| \leq n/4 + \sqrt{(2m \log(2n)} $. Note that $\mathbb{E}[x^Tv_i] = n/4$.

By Hoeffding bound ($p=\frac{1}{4}$, $ \epsilon = \frac{\sqrt{(2m \log (2n))}}{n}$), we have $\Pr[X_i = 1] \leq 1/m. $. This implies (via the probabilistic method and union bound), that the random $x$ has max inner product at most $n/4 + \sqrt{(2m \log(2n)}$

Lower Bound

The lower bound is similar, we just need to construct a set of vectors where no $x$ and use the probabilistic method to show that there exist $S$ of size $m$ such that for any $x \in \{0,1\}^n$ there exists some $v_i$ with $|x^Tv_i|>\frac{n}{4}+O(\sqrt{n \log(m/n)})$. This is again done by choosing the entries of $S$ uniformly at random, and noting that there exists a constant $c>0$ s.t. $\Pr[|x^Tv_i|> \frac{n}{4}+c \sqrt{(n \log(m/n))}] <(\frac{1}{2})^{n/m}$. Since the entries of $S$ were chosen uniformly at random, the probability a random $x$ does not violate the inequality for some $i$ is at most $(1/2)^{n/m}$. By the probabilistic method, there exists some $S$ with $|S|=m$ such that no $x$ satisfies the inequality for all $v_i 's$.

Generalizing to the sphere is pretty easy here. Just divide by the norm of $x$. We did use the fact that approximately half of the entries of $x$ are 1, but you can probably handle the alternative as a special case.