How to find a minimax solution to a set of linear inequalities?

Question

Let's consider the following linear inequalities:

$$a - 10 \leq b \leq a - 7 \\ b + 3 \leq c \leq b + 6 \\ c + 3 \leq d \leq c + 6 \\ d + 3 \leq e \leq d + 6$$

Is there a way to find a solution to this system where $\max \big( |a|, |b|, |c|, |d|, |e| \big)$ is minimized?

Answer 1

With the changed question, the minimised maximum absolute value is $4.5$

You have $e \ge d+3 \ge c+6 \ge b+9$ so $e-b\ge 9$ and $\max(|b|,|e|) \ge 4.5$

An optimal solution is $(2.5,-4.5,-1.5,1.5,4.5)$ and others are similar with $a \in [2.5,4.5]$

Answer 2

Here is a long winded version of Henry's answer:

Note that if $x_1 \le \cdots \le x_n$, then $\min_t \max_k |x_k-t| = \min_t \max(|x_1-t|,|x_n-t|) = {1 \over 2} |x_n-x_1|$, and a minimising value of $t$ is $t= {1 \over 2}(x_n+x_1)$.

We can rewrite the problem as $\min \{ \max (|a|,|a+\delta_1|,...,|a+\delta_1+\cdots+\delta_4|) | a \in \mathbb{R}, \delta \in F \}$, where $F= \{ \delta |\delta_1 \in [-10,-7], \delta_2,\delta_3,\delta_4 \in [3,6] \}$.

Note that we always have $a+\delta_1 \le a+ \delta_1+\delta_2 \le a+ \delta_1+\delta_2+\delta_3$, so the problem is equivalent to $\min \{ \max (|a|,|a+\delta_1|,|a+\delta_1+\cdots+\delta_4|) | a \in \mathbb{R}, \delta \in F\}$.

To reduce the problem to the first, we partition the feasible set into $F_1 = \{ \delta \in F | a+ \delta_1+\delta_2+\delta_3+ \delta_4 \le a\} $ and $F_2 = \{ \delta \in F | a+ \delta_1+\delta_2+\delta_3+ \delta_4 \ge a\} $ (these overlap, but that is not an issue).

If we restrict to the $F_1$ the problem becomes \begin{eqnarray} \min \{ \max (|a|,|a+\delta_1|) | a \in \mathbb{R}, \delta \in F_1\} &=& \min \{ \min_a \max (|a|,|a+\delta_1|) | \delta \in F_1\} \\ &=& \min \{ {1 \over 2} |\delta_1| | \delta \in F_1\} \\ &=& {1 \over 2} 9 \end{eqnarray} (since $\delta_1+\delta_2+\delta_3+ \delta_4 \le 0$, we have $\delta_1 \le -(\delta_2+\delta_3+ \delta_4) \le -9$)

If we restrict to $F_2$ the problem becomes \begin{eqnarray} \min \{ \max (|a+\delta_1|,|a+\delta_1+\cdots+\delta_4|) | a \in \mathbb{R}, \delta \in F_2\} &=& \min \{ \min_a \max (|a+\delta_1|,|a+\delta_1+\cdots+\delta_4|) | \delta \in F_2\} \\ &=& \min \{ \min_t \max (|t|,|t+\delta_2+\delta_3+\delta_4|) | \delta \in F_2\} \\ &=& \min \{ {1 \over 2} |\delta_2+\delta_3+\delta_4| | \delta \in F_2\} \\ &=& {1 \over 2} 9 \end{eqnarray}

Hence the minimum value is ${9 \over 2}$.

Note that since the problem is convex, and a solution exists in $F_1$ and $F_2$ there must be a solution in $F_1 \cap F_2$, so we can look for a solution with $\delta_1+\delta_2+\delta_3+\delta_4 = 0$. Since the solution is a solution in $F_1$ we have $\delta_1 = -9$ and $a={1 \over 2} (-\delta_1)={1 \over 2} 9$. Hence $\delta_2=\delta_3=\delta_4 = 3$. This corresponds to $(a,d,c,d,e) = ({9 \over 2}, -{9 \over 2}, -{3 \over 2}, {3 \over 2}, {9 \over 2})$.

Answer 3

Note that the objective function is the $\infty$-norm of the vector of variables. Hence, we have a convex optimization problem (that can be written as a linear program). Using CVXPY:

>>> from cvxpy import *
>>> a =  Variable()
>>> b =  Variable()
>>> c =  Variable()
>>> d =  Variable()
>>> e =  Variable()
>>> objective = Minimize( norm(bmat([[a],[b],[c],[d],[e]]),"inf") )
>>> constraints = [ a-10 <= b, b <= a-7, 
                     b+3 <= c, c <= b+6, 
                     c+3 <= d, d <= c+6, 
                     d+3 <= e, e <= d+6 ]
>>> prob = Problem(objective, constraints)
>>> prob.solve()
4.500000000794199

Hence, the minimum $\infty$-norm is $4.5$. This minimum is attained at:

>>> (a.value, b.value, c.value, d.value, e.value)
(3.4755024864272501, -4.5000000010660886, -1.5000000006636529, 1.500000000167093, 4.5000000008787637)