I am looking for an algorithm to find all minimizers (in fact, one would be enough as from there it is easy to find all) of the following problem:
Let $y_1,\dots,y_n \in \mathbb{R}$ and $x_1,\dots,x_n \in \mathbb{R}^k$ and let $a \in \mathbb{R}$. (Here $n$ can be quite large, say, 200 or more, and $k$ will be about between, say 1 and 8). Find the minimizers $\beta \in \mathbb{R}^k$ of the function $$\sum_{i=1}^n \mathbf{1}\{a \le \langle \beta,x_i \rangle\} (a - y_i), $$ where $\mathbf{1}\{\cdot\}$ denotes the indicator function and $\langle \cdot,\cdot\rangle$ the standard scalar product. In the end, I need to solve this for all $a \in \mathbb{R}$ but any hint on a solution for $a=1$ would also be much appreciated.
I can solve the problem numerically (fast) for $k=1$, and it is possible to show that for all $k$ the set of minimizers is a convex (possibly unbounded) polytope. I am open for all suggestions, as I have thought about many possibilities without much success.
