Welcome to MathOverflow

Question

3

1

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.

flag	asked Aug 12 2011 at 2:51 Jeff 247●1●8

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. – Lucas Aug 12 2011 at 3:51

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)$). – Jeff Aug 12 2011 at 5:42

1

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. – Abhinav Kumar Aug 12 2011 at 14:01

@Abhinav: Why not post this as an answer? – Emil Jeřábek Aug 12 2011 at 15:14

@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. – Jeff Aug 12 2011 at 17:26

show 1 more comment

Brian Borchers · Accepted Answer · 2011-08-12 13:13:56Z UTC

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$.

naeme · Answer 2 · 2012-10-05 15:56:52Z UTC

-3

I have a problem like this (maximum of sum of minimum of absolute values)do you find any solution for this problem?

answered Oct 5 at 15:56

naeme
1

Hi naeme -- The details of your problem really matter, so my solution may be not be relevant to you. Ultimately I used a branch-and-bound algorithm to find upper and lower bounds. I also found that in high dimensional space, i.e. $x\in[0,1]^p$, a special case of my problem was equivalent to finding the largest empty cube -- an NP-hard problem. – Jeff Oct 10 at 18:20

Linear program to maximize the minimum absolute value of linear functions ?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.