Given a finite set $S$ of non-negative unit vectors in $\mathbb R_+^n$, find a non-negative unit vector $x$ such that the largest inner product of $x$ and a vector $v \in S$ is minimized. That is, $$ \min_{x\in \mathbb R_+^n,\|x\|_2=1}\max_{v\in S} x^Tv. $$
It seems like a quite fundamental problem in computational geometry. Has this problem been considered in the literature?
It can be formulated as an infinity norm minimization problem, which can in turn be expressed as a quadratically constrained LP. If the rows of matrix $A$ are the vectors in $S$, we seek $$ \begin{align} &&\min_x\|Ax\|_\infty \\ \rm{s.t.} && x^Tx=1 \\ && x\geq 0. \end{align} $$ But the quadratic constraint is non-convex, so this is not very encouraging.
I am interested in understanding properties of the solution, rather than obtaining it numerically, although a reasonably efficient exact numerical method might be insightful, of course.
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.