# Maximizing the minimum of piecewise linear functions in high dimensional space

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.

-
Link to the previous question: mathoverflow.net/questions/72735 . –  Emil Jeřábek Aug 12 '11 at 17:23
This might be an instance of semilinear programming osti.gov/energycitations/product.biblio.jsp?osti_id=5423805 . –  Emil Jeřábek Aug 12 '11 at 17:32
Please clarify- by $[0,1]$, do you mean the closed interval between 0 and 1 in the real numbers, or do you mean the discrete set of values 0 and 1, excluding everything in between? –  Brian Borchers Aug 12 '11 at 18:05
In my notation, $[0,1]$ would mean the closed interval between 0 and 1 in $\mathbb R$. So by $[0,1]^{21}$, I mean the closed cube contained in $\mathbb R^{21}$ with all coordinates between 0 and 1. Sorry for the ambiguity. –  Jeff Aug 12 '11 at 18:40
@Emil: It does look similar to semilinear programming, but it's not clear to me exactly how to transform my problem into that framework; it would be more straightforward if the max and min in the standard formulation of semilinear programming were interchanged. –  Jeff Aug 12 '11 at 22:21

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.

-
Branch-and-bound sounds like the right approach, but it's new to me. Does the following sound right? For a particular (21-dimensional) rectangular subset $S$ of the domain, 1) Branch by splitting $S$ in half on a dimension selected at random. 2) Find a lower bound by evaluating the objective function on a few points in $S$ selected at random. 3) Find an upper bound by taking $\max_i \{\max_{x_i \in S} a_i + \|x_i - b_i\|_\infty \}$. Suitable $x_i$ will be found on the edge of $S$ farthest from $b_i$. Many thanks. –  Jeff Aug 14 '11 at 0:00
Yes, that's the basic idea. However, you can be more inteligent in picking your branching variables- look for an x(i) that is involved in the active constraint associated with your current x rather than splitting on a random dimension. –  Brian Borchers Aug 14 '11 at 15:55

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.

-
If I have it right, the 21st root of 0.001 is 0.7 roughly, so I think $a_{least} + 0.7$ is a good starting value for t, and after that it will be how many digits of precision you will need. Gerhard "High Dimensional Boxes Are Tiny" Paseman, 2011.08.13 –  Gerhard Paseman Aug 14 '11 at 2:34
Maybe I should say + 0.35 instead of + 0.7. Anyway, the high dimensionality of things may work in your favor. Gerhard "Just Bit Shift The Answer" Paseman, 2011.08.13 –  Gerhard Paseman Aug 14 '11 at 2:39
@Gerhard: Interesting idea! You make a good point about redundancies among constraints, with regard to finding a maximum. If branch-and-bound doesn't coverage quickly, I think I'll try adding in elements of this approach. Thanks much. –  Jeff Aug 15 '11 at 15:31

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.

-