2
$\begingroup$

I'm trying to find the general way of optimizing a summation function and I'm a bit lost. I would like to find the maxium (and the minimum, ideally) of:

$$ \sum_{n=1}^{x} f(n)$$

For example, let's say:

$$ f(n) = -(n-4)^2 + 16 $$

In this scenario, the answer is easy to find without doing any work: f(n) is positive for $n \in [0, 8]$, and then becomes negative for infinity, we can maximize the sum by adding all positive numbers ($x = 8$).

Is there a way to find this mathematically, in a general way for all functions? Usually when looking to optimize a function I would take the derivative, but the derivative of a summation doesn't make much sense, does it?

Thanks.

$\endgroup$
  • $\begingroup$ Of course you can derive the summation, as long as it is finite. $\endgroup$ – Filippo De Bortoli Feb 7 '17 at 17:55
  • $\begingroup$ Can you please remove the "accepted" tick from my answer? It isn't right, works by chance. :-) $\endgroup$ – Filippo De Bortoli Feb 7 '17 at 20:12
2
$\begingroup$

For a local max at positive integer $x$, you want $f(x) \ge 0$ while $f(x+1) \le 0$. Similarly for a local min with $\le$ and $\ge$. So you look for the places where $f$ changes sign.

$\endgroup$
  • $\begingroup$ Say for any $\epsilon > 0$ we can easily determine a sufficiently large $K(\epsilon) \in \mathbb{N}$ s.t. $\left| \sum_{n = K(\epsilon)}^\infty f(n)\right| < \epsilon,$ do you have any ideas on methods for efficiently finding a solution which is within $\epsilon$ of global optimality? $\endgroup$ – David Feb 7 '17 at 18:25
  • $\begingroup$ In general (i.e. if all you can do is evaluate $f$ at given values), then no: the best you can do is a brute-force search of $n = 0$ to $K(\epsilon)$. $\endgroup$ – Robert Israel Feb 8 '17 at 0:02
0
$\begingroup$

Attention, please: this solution works by chance. It isn't by any means right. Sorry.


When your summation is finite, you can take its derivative, and $$ \left(\sum_{n=0}^x f(n)\right)^\prime = \sum_{n=0}^x f^\prime(n). $$

Assuming $f(n) = -(n-4)^2 + 16$, we obtain $f^\prime(n) = -2n + 8$ and $$ \left(\sum_{n=0}^x f(n)\right)^\prime = \sum_{n=0}^x f^\prime(n) = 8x - 2\sum_{n=0}^x n, $$ which equals to $8x - x^2 - x = -x^2 + 7x$.

Solving for $x$, we find that $$ \begin{aligned} x(7-x) = 0 &\implies x = 0 \lor x = 7 \\ x(7-x) \ge 0 &\implies x \in [0,8). \end{aligned} $$

Why did $7$ come out, instead of $8$? My guess: for $n = 8$, $f(n)$ equals zero, meaning that the $8$-th term of the summation does not provide any contribute, so the local maximum is at $n = 7$.

$\endgroup$
  • 2
    $\begingroup$ I'm confused. He is trying to maximize over $x$ yet you seem to be differentiating w.r.t. $n$? Am I missing something obvious? I believe the OP was referring to $$\frac{d}{dx}\sum_{n=0}^x f(n)$$ in the question (which would, of course, be $f(x)$ under suitable conditions if we extended the summation to an integral). $\endgroup$ – David Feb 7 '17 at 18:20
  • $\begingroup$ To me, it seemed quite natural to derive first, and sum then. Doing the opposite brings almost the same result ($-x^2 + 7x -23/6$). To be honest, the more I ruminate on this, the more I get confused, too. $\endgroup$ – Filippo De Bortoli Feb 7 '17 at 18:54
  • 1
    $\begingroup$ The problem is your differentiation is with respect to the wrong variable -- not that you are differentiating in the wrong order (differentiation is a linear operator). Your method worked by coincidence, it does not work in general. Consider $f(n) = (n-6)(n+4)$, then the summation is minimized at $x \in \{5,6\}$. However, note $$\frac{d}{dn}f(n) = 2n-2,$$ and $$\sum_{n=0}^x 2n-2$$ is monotone non-decreasing over the positive integers. $\endgroup$ – David Feb 7 '17 at 19:47
  • 1
    $\begingroup$ Ok. Thank you for the provided example, it made me understand what you meant in the previous comment. I'll leave the answer because I think it's useful to help others avoid this kind of mistake, and I'll request the OP to remove the green tick from this. $\endgroup$ – Filippo De Bortoli Feb 7 '17 at 20:12

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.