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.



Maximizing the minimum of piecewise linear functions in high dimensional space
As in your previous question, this is a nonconvex optimization problem, so it won't be LP, SOCP, or SDP representable. 


You've only got a 21 dimensional problem, and the constraint functions have easy Lipschitz constants. If you've got the time (hours or days of computation) and really need a fairly accurate solution (e.g. you need a solution within x% of optimal, where x% might be something like 1%), then a branch and bound approach to this global optimization problem might be appropriate. If you need a quick solution, then some kind of stochastic heuristic approach might yield a reasonable solution even if you can't prove that it's within some percent of optimal. 


