$l^\infty$-minimization with one parameter - explicit solution formula available?

Question

Given two vectors $a,b\in \mathbb R^n$, I want to solve the (one-dimensional) minimization problem $$ \min_{s\in \mathbb R} \|a - bs\|_\infty. $$ We can assume that $b\ge0$. In the case that all entries of $b$ are equal to one, then a solution of the above problem is given by $$ s = \frac12( \min_ia_i + \max_ia_i). $$ Is there a similar (easy) solution formula available if $b$ has at least two different entries? Or is there a method to compute the solution in $O(n)$ operations? I know that the above problem can be formulated as standard linear programming problem and solved as such.

Answer 1

Here is a solution in $O(n \log n)$.

By doubling (and modifying) the entries in $a,b$, we can reformulate the problem as $$\min_{s \in \mathbb R} \max( a + s b ),$$ where $\max$ denotes the maximal entry of a vector.

This problem can be cast as the following linear problem \begin{align*} \text{Minimize} \quad & t \\ \text{s.t.} \quad & a + s b \le t e. \end{align*} Here, $e$ is the all-one-vector. Its dual problem is (equivalent to) \begin{align*} \text{Maximize} \quad&a^\top \lambda \\ \text{such that} \quad & b^\top \lambda = 0 \\ & e^\top \lambda = 1\\ & \lambda \ge 0. \end{align*} This problem has a nice geometrical interpretation: We look for a point in the convex hull of $\{(a_i,b_i) | i = 1,\ldots,n\}$ whose $y$-coordinate is zero and whose $x$-coordinate is as big as possible. It is possible to compute the convex hull (and thus, to solve the dual problem) in $O(n \log n)$. From the dual solution, one can reconstruct the primal solution.

Since we do not need the full convex hull, it is maybe possible to solve the dual problem faster than $O(n \log n)$, but I do not have any idea how to accomplish that.