Hemisphere containing the maximum number of points scattered on a sphere

Question

Consider a set of points $x_1, \ldots,x_n$ on $\mathbb{S}^{k-1}$ (the unit sphere in $\mathbb{R}^k$). The goal is finding the hemisphere which contains the maximum number of $x_i$'s. Basically, we would like to find the hyperplane passing through the origin, which contains the maximum number of $x_i$'s on one side. Any pointers to equivalent problems, or (in)exact algorithms?

Answer 1

You can solve the problem via mixed integer linear programming as follows. Let continuous decision variables $\beta_j$ be the coefficients of the desired hyperplane, and let binary decision variable $y_i$ indicate whether $x_i$ is in the hemisphere defined by $\sum_{j=1}^k \beta_j z_j \le 0$. The problem is to maximize $\sum_{i=1}^n y_i$ subject to \begin{align} \sum_{j=1}^k \beta_j x_{ij} &\le M_i(1-y_i) &&\text{for $i\in\{1,\dots,n\}$} \tag1\label1\\ -1 \le \beta_j &\le 1 &&\text{for $j\in\{1,\dots,k\}$} \tag2\label2 \end{align} Constraint \eqref{1} enforces the logical implication $y_i = 1 \implies \sum_{j=1}^k \beta_j x_{ij} \le 0$. Constraint \eqref{2} is an optional normalization, which is valid without loss of optimality; you can always divide both sides of the hyperplane inequality by the absolute value of the largest coefficient.

In the big-M constraint \eqref{1}, the constant $M_i$ is a (small) upper bound on the LHS when $y_i=0$. Because of \eqref{2}, you can take $M_i = \sum_j |x_{ij}|$.