Maximizing the minimum of piecewise linear functions in high dimensional space

Question

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.

Answer 1

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.

Answer 2

Here is a left field approach. Consider the volume taken by each constraint at a level s, so you want measure of D, where D is the set of x for which the constraint has a value less than s. If s is small enough, the volume will be less than 1/1000th the volume of the whole cube, so you know that in this case the maximum will be greater than s. You can also see if there is redundancy in some of the constraints, in particular is b_i - b_j "less than" a_i - a_j for constraints i and j? Remove such redundancies and try the volume estimate again. In practice, you might get away with the sum of the volumes being twice the volume of the cube, because of overlap, and still have a feasible value for t.

Gerhard "Ask Me About System Design" Paseman, 2011.08.13

Answer 3

You might look at the literature on the upper envelope (or equivalently, the lower envelope) of a collection of surfaces in $\mathbb{R}^d$. Such upper envelopes arise in a variety of computational geometry contexts, and so have been heavily studied. A good source is:

Daniel Halperin, "Arrangments," Handbook of Discrete and Computational Geometry, (ed. O’Rourke & Goodman) CRC Press, pp. 529-562, 2004.

For example, the upper envelope of $n$ surfaces in $\mathbb{R}^d$, under certain assumptions on the surfaces (e.g., that they are algebraic of constant maximum degree) has complexity about $O(n^{d-1})$. Perhaps closer to your problem, the upper envelope of $n$ $(d{-}1)$-simplices in $\mathbb{R}^d$ also has complexity near $O(n^{d-1})$. For the latter, there are efficient algorithms to construct the envelope. See:

Herbert Edelsbrunner, Leonidas J. Guibas and Micha Sharir, "The upper envelope of piecewise linear functions: Algorithms and applications," Volume 4, Number 1, 311-336, 1989. Discrete & Computational Geometry.

It may be that you could adapt these techniques to your computation, avoiding construction of the full envelope, and focusing on the maxima.