# Optimization problem: Maximize the sum of minimum.

Given positive integers $L$ and a set of non-negative integers $N$.

Find maximum of: $$\large \sum_{i = 1}^{4L}\ N_i\cdot(\min(\vert i - c\vert, 4L - \vert i - c\vert))$$

with $c \in \{1, 2,\dots ,4L\}$ and $\frac {\text {number of } N_i > 0} {L}$ is small (about $\frac 1 {100}$)

How can I solve this and similar problems efficiently? Thanks.

• Let me understand your problem better. What are the variables of your problem? The sum goes from 1 to $4L−1$ ? Jun 11, 2014 at 8:14
• I edited my question. Jun 11, 2014 at 11:05
• Yes, sorry about that. Jun 12, 2014 at 18:28
• You want to find $c$ that maximizes the sum? And must $c$ be an integer? Jun 12, 2014 at 18:33
• I can solve your problem, however only if minimization is performed instead of maximization. Does this help you? Jun 13, 2014 at 6:40

Problem: I assume the problem is \begin{align} S &= \max_{c \in \{1, \ldots, 4L\}} \sum_{i=1}^{4L} N_i \min \left(|i-c|, 4L-|i-c|\right) \\ &= \max_{c \in \{1, \ldots, 4L\}} T(c) \end{align} \quad (*)

Complexity Simple Search: A simple search of $(*)$ over all $c$-values would require about $(4L)^2$ term evaluations, needing 1 $+$, 1 $\cdot$, 2 $-$, 1 $\min(.,.)$ and 1 $|.|$ calculation each.

Lemma 1: The change $\Delta T$ for increasing $c$ is:

$$\Delta T(c) := T(c+1) - T(c)$$

It can be calculated recursively:

\begin{align} \Delta T(1) &:= N_1 - \sum_{i=2}^{2L+1} N_i + \sum_{i=2L+2}^{4L} N_i \\ \Delta T(c) &:= \Delta T(c-1) + 2(N_{c} - N_{2L + c}) \quad c \in \{ 2, \ldots, 2L \} \end{align} \quad (**)

Lemma 2: The change has a symmetry: $$\Delta T(c) = -\Delta T(c - 2L), \quad c \in \{ 2L+1, \ldots, 4L \}$$

Thus we can calculate the $2L$ values of $\Delta T$ in the second half of the $c$-interval faster, because we can make use of the values from the first half.

Quick Summation: Calculate the relative sum vector $Q$: \begin{align} Q(1) &:= 0 \\ Q(c) &:= Q(c-1) + \Delta T(c-1) \\ \end{align} \quad c \in \{ 2, \cdots, 4L \}

Lemma 3: The $c^*$ which maximizes $Q(c)$ will maximize $T(c)$ as well.

Solution: Determine $c^*$ according to lemma 3 and the quick summation procedure. Then calculate

$$S = T(c^*)$$

using the original defintion $(*)$ or even better using the optimized term evaluation:

\begin{align} T_{L->R}(c) &:= \sum_{i = 1}^{c-1} N_i \, (c-i) + \sum_{i = c+1}^{2L+c-1} N_i \, (i-c) + \sum_{i = 2L+c}^{4L} N_i \, (4L - (i-c)) \\ & \quad c \in \{ 1, \ldots, 2L \} \\ T_{R->L}(c) &:= \sum_{i = 1}^{c - 2L} N_i \, (4L - (c-i)) + \sum_{i = c - 2L + 1}^{c-1} N_i \, (c-i) + \sum_{i = c + 1}^{4L} N_i \, (i-c) \\ & \quad c \in \{ 2L+1, \ldots, 4L \} \end{align} \quad (\#)

The optimized term $(\#)$ avoids minimum and absolute value operations. Its greater benefit is that it allows to determine the differences for lemma 1.

Complexity of the Solution: The complexity relative to the simple search has been reduced to less than $16 L$ $+$, $12 L$ $-$ and $6L$ $\cdot$ operations. Or roughly from quadratic to linear. In both cases not considering the similar $4L$ comparisons for the extremum search.

Bonus Lemma 1: The same procedure works for searching the minimum sum efficiently, just replace $\max$ with $\min$.

Bonus Lemma 2: The $N_i$ can be arbitrary real numbers.

Derivation of the Optimized Terms: We can avoid the minimum calculations in $(*)$ by using $T_{L\to R}$ for the $c$-values from $1$ up to $c_s = 2L$ and then using $T_{R\to L}$. We further split those sums after $i_{s, L\to R} = 2L+c-1$ and $i_{s, R\to L} = c - 2L$:

\begin{align} T_{L->R}(c) &= \sum_{i = 1}^{2L+c-1} N_i \, |i-c| + \sum_{i = 2L+c}^{4L} N_i \, (4L - (i-c)) \\ T_{R->L}(c) &= \sum_{i = 1}^{c - 2L} N_i \, (4L - (c-i)) + \sum_{i = c - 2L + 1}^{4L} N_i \, |i-c| \end{align}

And we can split up two sums further to avoid the decisions during absolute value calculations, getting $(i-c)$ and $(c-i)$ factors. This yields $(\#)$.

Proof Lemma 1: The change $\Delta T$ for increasing $c$ is: $$\Delta T(c) := T(c+1) - T(c) = \sum_{i=1}^c N_i - \sum_{i=c+1}^{2L+c} N_i + \sum_{i=2L+c+1}^{4L} N_i, \quad c \in \{ 1, \ldots, 2L \} \quad (\#\#)$$ This has been derived from $(\#)$ by analyzing how that expression changes from $c$ to $c+1$. It is a discrete analogon to differentiation. The expression is simpler than $(*)$ but still contains the information to determine the optimum.

Applying this idea again: If one knows $\Delta T(c)$, one can calculate $\Delta T(c+1)$ using:

$$\Delta^2 T(c) := \Delta T(c+1) - \Delta T(c) = 2(N_{c+1} - N_{2L+c+1})$$

This has been derived from $(\#\#)$. The result is the recursive scheme $(**)$.

Proof Lemma 2: Start with the second branch from $(\#)$. Determine the difference like in the proof of lemma 1. Compare the result with $(\#\#)$.

Proof Lemma 3: The relative sum $Q$ differs only by a constant from $T$ $$Q(c) = T(c) - T(1).$$

Appendix:

• Here is a program written in Ruby, for those who want to experiment a bit more with this problem.
Sample output here or here or here. It generates random $N$-vectors and also checks if the optimized equations $(\#)$ give the same results like the original $(*)$.
• Observation: The changes of the sums $$\frac{\Delta}{\Delta c} \sum\limits_{i = a(c)}^{b(c)}t(i, c)$$ seem to behave similar to the derivatives of the parameter integrals $$\frac{\partial}{\partial c} \int\limits_{a(c)}^{b(c)} t(x, c) \, dx = t(b(c),c) \, b'(c) - t(a(c), c) \, a'(c) + \int\limits_{a(c)}^{b(c)} \!\! \frac{\partial}{\partial c} t(x, c) \, dx$$

If $c$ is an integer, it is worth noting that full search is maybe the fastest way to solve your problem. Trying out all possible values $c=1,\dots,4L$ is not critical in your case as the problem is one-dimensional.