Thanks! The Calculus of Variations is exactly what I'm looking for. Do you recommend a particular document to learn about it? I found maths.ed.ac.uk/~jmf/Teaching/Lectures/CoV.pdf. Can you post your answer as an answer so that I can accept it?

Can you give a little more information about the physical background of the problem? How can you mix even one $\int p(x)f(x)$? You seem to be mixing uncountably many things there?

Perhaps Frechet derivatives on Banach spaces can help here. What you'd want to say is d{the L1 norm}/dp = 0, except that p is a function not a number. Frechet derivatives generalize taking derivatives to taking derivatives by functions. That is, if you have an operator H : (R -> R) -> R, you can find H'. The solution in this case would be the solution to H'(p) = 0. I believe that H'(p) = 0 will reduce to a differential equation for p.

Willie Wong, I rewrote the question using LaTeX.

Hmm yes you are right...how about the problem with the additional constraint f(0) = f(1) = 0?

If you don't have a bound on t_i then the problem is trivial. You can get arbitrarily close by just making t_i huge and s small.

Perhaps you can search for s around maxCi/M, it seems that the total error can be reduced by roughly a factor of 3 versus just picking s=maxCi/M.

Correction: choose s round $max C_i/M$.

For a given s the problem is easy. We want to minimize $|t_i*s - C_i|$, so suppose we could solve it exactly: $t_i = C_i/s$. Now we have to try only 2 candidates per $t_i$: $min(M,floor(C_i/s))$ and $min(M,ceil(C_i/s))$. So for a given s we can solve the problem quickly. I did this for a sample input and plotted s versus the resulting error $\sum |t_i*s-C_i|$. The result i.imgur.com/zcKOW.png The error is very high if you choose s much to small or much too large. Choosing s around $max {t_i}/M$ seems to get good results, perhaps good enough for your purposes.

That settles this question. Thanks!