Efficient algorithm for finding the minima of a piecewise linear function

Question

Consider real numbers $a_i$ and $b_i$ for $i=1\dots n$ and define a function by

$f(x) = \max_i ( a_i + b_i x )$

We desire to find $\min_x f(x)$. Obviously this occurs at an intersection of two lines:

$x = - \frac{a_i - a_j}{b_i - b_j}$

for $b_i\neq b_j$ and there are at most $n(n-1)/2$ such intersections. For large $n$ it may be impractical to manually check all possible points. Does there exist an efficient way of checking only a subset of the points, ideally one which completes in $O(n)$ rather than $O(n^2)$ time?

I'm thinking something along the lines of the simplex method, which moves from corner to corner of a convex set (the relevant set in this case being the area above the curve $f(x)$).

Answer 1

Looking at a figure one is lead to the following algorithm which traces out the graph of $f$:

One may assume $a_1< a_2 < \ldots < a_n$. If $0 < a_1$ or $a_n < 0$ then $m:=\min_x f(x)=-\infty$. Otherwise for $x$ large negative one has $f(x)=a_1 x + b_1$ and for $x$ large positive one has $f(x)=a_n x+b_n$. Therefore put $x_1:=-\infty$, $j_1:=1$ and for $k\geq1$ define recursively $$ r_i := {b_{j_k}-b_i\over a_i-a_{j_k}} \ (j_k < i \leq n),\quad x_{k+1}:=\min_{j_k < i \leq n}\ r_i\ ,\quad j_{k+1}:=\arg\min_{j_k < i \leq n} r_i\ .$$ When for the first time $a_{j_{k+1}}\geq0$ the minimum is found: One has $m=a_{j_k}x_{k+1}+b_{j_k}$.

As a bonus I propose the following algorithm which seems more sophisticated and is maybe faster:

Put $g_i(x):=a_i x+ b_i$ and denote by $g_i\wedge g_j$ the point of intersection of the two graphs. Assume for simplicity $ a_1 < \ldots a_s<0 < a_{s+1} < \ldots < a_n$. Then apply in succession

1. Put $l:=1$, $\ r:=n$.
2. Put $(\xi,\eta):= g_l\wedge g_r\ $.
3. If $l=s$ and $r=s+1$, goto 7.
4. Let $\tau:=\max_{l < i < r}\ g_i(\xi)\ ,\quad p:=\arg\max_{l < i < r}\ g_i(\xi).$
5. If $\tau\leq \eta$ goto 7.
6. If $p\leq s$ put $l:=p$, else put $r:=p$; then goto 2.
7. $m=\eta$.

Answer 2

This is a convex function of a single variable, so a derivative free search method such as Golden Section search will converge without problems. These methods all converge linearly, but they don't move along corners. The effort per function evaluation is $O(n)$.

Answer 3

The problem

$ \min_{x} \max_{i} a_{i}+b_{i}x $

(It doesn't really matter whether $x$ is a scalar or a vector) can be formulated and solved as a linear programming problem

$ \min_{x,t} t $

$ t \ge a_{i}+b_{i}x \;\;\; i=1, 2, \ldots m $

As a practical matter, the simplest approach is probably to give this LP to an LP solver routine and let it solve the problem. Unless the problem is extremely large, the LP will solve pretty quickly.

If your problem instances really are extremely large, then it might be worth investing time and effort in coming up with a specialized solver, but "extremely large" is probably bigger than you think.

Answer 4

If $n$ (and/or the number of linear pieces $m$) is extremely large and you are happy with approximate solutions you can try a subgradient method. The advantage is that their complexity does not depend on $n$, $m$ but only on the target accuracy $\varepsilon$, and the cost per iteration is linear in $n\times m$ (so it's at least as good as simplex).

The convergence rate in this case is $R/\sqrt{T}$ (where $R$ is an estimate on the distance from your starting point to the optimum, and $T$ is the number of iterations) and this algorithm is optimal when $n$ is large (see Nesterov's book Introductory Lectures on Convex Optimization, Theorem 3.2.2).