Given an arbitrary (sorted) set of numbers $\{c_1,\dots,c_n\}$, define for each number the piecewise continuous linear function $$ f_i(x) =\begin{cases} x & 0\leq x\leq c_i \\ 0 & otherwise \end{cases} $$

I'm interested in the value $x$ such that $\sum_{i}f_i(x) = \max_{c\in \mathbb{R}}\sum_{i}f_i(c)$.

Now I know I can design a simple algorithm for doing so, by simply searching through the sums of different values of $c_i$ since they are sorted.

I'm interested in using differentiable functions that approximate these piecewise linear functions, so that I can look at the derivative of the sum of these approximate functions and more analytically define the critical point.

  • $\begingroup$ If $c_1 <\ldots < c_n$ we have $\sum_i f_i(c_j)= (n+1-j) c_j$, so one could take the maximum of the $n$ different values. If $n$ is very large and the %c_j$ are distributed "nicely" one could evaluate the expression only for a subset of j's and interpolate. $\endgroup$ – user35593 Jan 7 at 7:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.