# Efficient algorithm for finding the minima of a piecewise linear function

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

-
The simplex method will indeed only use $O(n)$ steps, because your set has at most $n+1$ corners (there can’t be more than two on a particular line). Whether a generic LP solver (as indicated in Brian Borchers’ answer) will or will not be faster than a special-purpose simplex implementation is not clear to me. – Emil Jeřábek Apr 15 '11 at 18:59
Emil- I'm willing to bet that if you add the time to program any specialized algorithm to the time to solve the problem it will end up being longer than the time to setup and solve the LP. Unless you have a lot of instances of the problem to solve, it's probably not worth investing the human time in programming something for this particular problem. – Brian Borchers Apr 16 '11 at 1:21
Brian, typically this problem will need to be solved multiple times per second on a rolling basis - so speed is important, but it only needs to be "good enough". If a general purpose LP solver can solve in, say, less than 100ms, that will be well within the bounds of "good enough". – Chris Taylor Apr 17 '11 at 16:29

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

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.

-
The LP can be solved in polynomial time, although you won't get this done in linear or quadratic time. – Brian Borchers Apr 15 '11 at 18:46
Thanks. I will experiment with this and see how it turns out. Typically I will be considering n ~ 10^6 which may or may not be "extremely large" under your definition! – Chris Taylor Apr 17 '11 at 16:27

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

-

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

-