I'd like to compute

$\max_{x,t} t$ such that $\forall i$, $t < a_i + \|x - b_i\|_\infty$.

where $a_i,\ldots, a_n \in \mathbb R$ and $b_1,\ldots,b_n \in [0,1]^{21}$ are fixed, $x \in [0,1]^{21}$, $\|\cdot\|_\infty$ is $\sup$-norm, and $n$ is roughly $1000$.

I understand this problem cannot be solved with a linear program since the feasible set is not convex. Also, because the dimensionality of $x$ is high, it seems impractical to partition the domain into regions where the constraints are linear, and to address each region separately, before taking a max over all regions.

Is there any efficient way to get an exact solution? If not, is there any way to get a good lower bound?

Thanks much.

I'd like to compute

$\max_{x,t} t$ such that $\forall i$, $t < a_i + \|x - b_i\|_\infty$.

where $a_i,\ldots, a_n \in \mathbb R$ and $b_1,\ldots,b_n \in [0,1]^{21}$ are fixed, $x \in [0,1]^{21}$, $\|\cdot\|_\infty$ is $\sup$-norm, and $n$ is roughly $1000$.

I understand this problem cannot be solved with a linear program since the feasible set is not convex. Also, because the dimensionality of $x$ is high, it seems impractical to partition the domain into regions where the constraints are linear, and to address each region separately, before taking a max over all regions.

Is there any efficient way to get an exact solution? If not, is there any way to get a good upper bound?

Thanks much.