Efficient algorithm for finding the minima of a piecewise linear function - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T03:37:18Z http://mathoverflow.net/feeds/question/61839 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/61839/efficient-algorithm-for-finding-the-minima-of-a-piecewise-linear-function Efficient algorithm for finding the minima of a piecewise linear function Chris Taylor 2011-04-15T17:12:59Z 2011-04-19T15:30:04Z <p>Consider real numbers $a_i$ and $b_i$ for $i=1\dots n$ and define a function by</p> <p>$f(x) = \max_i ( a_i + b_i x )$</p> <p>We desire to find $\min_x f(x)$. Obviously this occurs at an intersection of two lines:</p> <p>$x = - \frac{a_i - a_j}{b_i - b_j}$</p> <p>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?</p> <p>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)$).</p> http://mathoverflow.net/questions/61839/efficient-algorithm-for-finding-the-minima-of-a-piecewise-linear-function/61853#61853 Answer by Brian Borchers for Efficient algorithm for finding the minima of a piecewise linear function Brian Borchers 2011-04-15T18:44:12Z 2011-04-15T18:44:12Z <p>The problem </p> <p>$\min_{x} \max_{i} a_{i}+b_{i}x$</p> <p>(It doesn't really matter whether $x$ is a scalar or a vector) can be formulated and solved as a linear programming problem</p> <p>$\min_{x,t} t$</p> <p>$t \ge a_{i}+b_{i}x \;\;\; i=1, 2, \ldots m$</p> <p>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. </p> <p>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. </p> http://mathoverflow.net/questions/61839/efficient-algorithm-for-finding-the-minima-of-a-piecewise-linear-function/61854#61854 Answer by Hans Engler for Efficient algorithm for finding the minima of a piecewise linear function Hans Engler 2011-04-15T18:47:41Z 2011-04-15T18:57:07Z <p>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)$. </p> http://mathoverflow.net/questions/61839/efficient-algorithm-for-finding-the-minima-of-a-piecewise-linear-function/61855#61855 Answer by Christian Blatter for Efficient algorithm for finding the minima of a piecewise linear function Christian Blatter 2011-04-15T18:54:55Z 2011-04-19T15:30:04Z <p>Looking at a figure one is lead to the following algorithm which traces out the graph of $f$:</p> <p>One may assume $a_1&lt; a_2 &lt; \ldots &lt; a_n$. If $0 &lt; a_1$ or $a_n &lt; 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 &lt; i \leq n),\quad x_{k+1}:=\min_{j_k &lt; i \leq n}\ r_i\ ,\quad j_{k+1}:=\arg\min_{j_k &lt; 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}$.</p> <p>As a bonus I propose the following algorithm which seems more sophisticated and is maybe faster:</p> <p>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 &lt; \ldots a_s&lt;0 &lt; a_{s+1} &lt; \ldots &lt; a_n$. Then apply in succession</p> <ol> <li>Put $l:=1$, $\ r:=n$.</li> <li>Put $(\xi,\eta):= g_l\wedge g_r\$.</li> <li>If $l=s$ and $r=s+1$, goto 7.</li> <li>Let $\tau:=\max_{l &lt; i &lt; r}\ g_i(\xi)\ ,\quad p:=\arg\max_{l &lt; i &lt; r}\ g_i(\xi).$</li> <li>If $\tau\leq \eta$ goto 7.</li> <li>If $p\leq s$ put $l:=p$, else put $r:=p$; then goto 2.</li> <li>$m=\eta$.</li> </ol>