3
$\begingroup$

I'd like to compute

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

where $a_i,\ldots, a_n$ and $b_1,\ldots,b_n$ are fixed and $x \in [0,1]$.

Can this be solved with a linear program? I'm familiar with a technique to minimize the maximum of absolute values, by doubling the number of constraints, but I don't think it applies to maximizing the minimum.

If a linear program won't work, is there another efficient way to get an exact solution?

Thanks much.

Improve this question
$\endgroup$
8
  • $\begingroup$ So you want the largest $t$ with any $x \in [0,1]$ using the Wikipedia form: Maximise $c^T X$ Subject to $AX \leq B$ and $X \geq 0$ Isn't this just: $X = [x,t]$ $c = [0,1]$ Then some nasty matrix A and vector B which I don't want to write out. But basically doing what you said. $\endgroup$
    – Lucas
    Commented Aug 12, 2011 at 3:51
  • $\begingroup$ Thanks for your comment. As I understand it, it's the absolute value operator that makes this something other than a textbook example of linear programming: the absolute value of a linear function is not linear, though it may be represented as the maximum of two linear functions. If it's represented in this way, then I'm trying to find the max (over t) of a min (over i) of a max (over $a_i + (x - b_i)$ and $a_i - (x - b_i)$). $\endgroup$
    – Jeff
    Commented Aug 12, 2011 at 5:42
  • 1
    $\begingroup$ Unless I'm making a mistake, you should be able to do this with at most $n+1$ linear programs: namely, assume without loss of generality that $b_1 \leq b_2 \leq \dots \leq b_n$ and break up the interval $[0,1]$ into at most $n+1$ subintervals, depending on the $i$ such that $x \in [b_i, b_{i+1}]$. On each such subinterval, you have $n$ linear functions (no absolute values). So it's pretty easy to find the max of the mins. Then take the max of the objective functions of these linear programs. $\endgroup$
    – Abhinav Kumar
    Commented Aug 12, 2011 at 14:01
  • $\begingroup$ @Abhinav: Why not post this as an answer? $\endgroup$
    – Emil Jeřábek
    Commented Aug 12, 2011 at 15:14
  • $\begingroup$ @Abhinav: This is a good solution, and I appreciate it. I was trying to simplify my problem when I posted it, but actually, $x$ and $b_i$ are in 21-dimensional space, and I'm using the sup-norm rather than absolute value. With 21-dimensions, I'm not sure whether it would be computationally possible to consider each linear piece separately. I've reposted the expanded question, since it seems like this one has been answered. Thanks for your help. $\endgroup$
    – Jeff
    Commented Aug 12, 2011 at 17:26

2 Answers 2

Reset to default
4
$\begingroup$

Unfortunately, this problem can't be represented by an LP, since your feasible region is in general nonconvex, and the feasible region of an LP (being the intersection of a bunch of half spaces) is always convex.

To be more specific, consider the problem

$\max \;t $

$ t \leq | x- 1/2 | $

$ t \leq | x- 3/4 | $

$ 0 \leq x \leq 1 $

A sketch of the feasible region shows that it's nonconvex. There's a local maximum at $x=5/8$, $t=1/8$, and a global maximum at at $x=0$, $t=1/2$.

Improve this answer
$\endgroup$
0
1
$\begingroup$

For the general answer check the reference found at http://link.springer.com/article/10.1007%2FBF00933924

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .