Given a matrix $A\in\mathbb{R}^{n \times k}$, with rows $a_1,\dots,a_n \in \mathbb{R}^k$, I want to find vectors $\ell,u\in\mathbb{R}^k$ such that:
- The (elementwise) inequality $\ell \le a_i \le u$ holds for at least $\alpha n$ of the rows in $A$, where $\alpha \in [0,1]$. In other words, if $\alpha=0.95$, then 95% of the rows in $A$ are "contained" in the band $(\ell,u)$.
- The vectors $\ell,u$ are optimal in the sense that if some other $\ell',u'$ satisfy 1), then $\| \ell - u \| \le \| \ell' - u'\| $.
It is easy to express this as a mixed ILP problem, and I have implemented a solver using Gurobi. However it is extremely slow even for moderately large $n$ and $k$. I'm wondering if this problem has been studied elsewhere, or reduces to another known combinatorial optimization problem for which specialized or approximation algorithms have been developed.