# Thread: help in Integral Maximization

1. Here's my gut instincts.

For the uniform interval case: take the two smallest y values and assign them to the endpoints. Assign the rest of the y values any way you want.

For the non-uniform interval case: You have two options: brute force search, or some sort of heuristic.

Option 1: brute force search will be $O(N!)$, where $N$ is the number of points. This is not good performance! The algorithm would like like this:

Code:
Largest_Area = - infinity;
Best_Permutation = Y;
For each permutation of the Y set:
compute new_area = trapezoidal rule for non-uniform intervals;
If new_area > Largest_Area Then
Best_Permutation = Current_Permutation;
Largest_Area = new_area;
End If
End For
Output Largest_Area, Best_Permutation
Option 2: heuristics. Here's one strategy: rank the intervals according to width. Rank the y values according to value. Perform a match-up of intervals to y-values in this order subject to the following constraints:

1. I think you want to have all the trapezoids as close to being squares as possible. You might try minimizing the least squares formula that follows:

$\displaystyle{E=\sum_{j=2}^{N}\left((x_{j}-x_{j-1})-\frac{y_{j}+y_{j-1}}{2}\right)^{2}.}$

I don't know how you would do this, however. What you're changing is the permutation of the Y set.

This formula represents a measure of how far off from being square all the trapezoids are.

2. There must be continuity from one interval to the next. That is, only one y value may be chosen at the intersection of two intervals.

Example: X = {0,1,4,6,7}, Y={1,1,2,4,5}.

Ranking of x-intervals:
[1,4]
[4,6]
[0,1]
[6,7]

Ranking of y-values:
5
4
2
1
1

Matchup:

y = 5 and y = 4 correspond to [1,4]. Choose y = 4 and y = 2 to correspond with [4,6]. Choose y = 2 and y = 1 to correspond with [6,7]. Finally, choose y = 1 and y = 5 to correspond with [0,1]. That is, the Y set permutation is {1,5,4,2,1}.

Now this algorithm, as is, will not necessarily provide you with the absolute maximum sum. It will get close. As a matter of fact, the assignment Y = {1,4,5,2,1} gives a slightly higher area.

I think you generally want to assign larger y values to larger intervals. However, as I have already pointed out, there are further optimizations to be done. You might want to think about choosing the higher y values to be closer to the "x center of mass", which you could define as follows:

$\displaystyle{\overline{x}=\frac{\sum_{j=2}^{N}(x_ {j}-x_{j-1})\frac{x_{j}+x_{j-1}}{2}}{\sum_{j=2}^{N}(x_{j}-x_{j-1})}=\frac{1}{2}\frac{\sum_{j=2}^{N}(x_{j}^{2}-x_{j-1}^{2})}{\sum_{j=2}^{N}(x_{j}-x_{j-1})}.}$

Conclusion: the non-uniform case is a difficult problem. I'm not sure if I know of a sure-fire way to find the global max other than brute-force search. The algorithms I've outlined here will get you a good value, I think. But it's difficult. With lots of intervals, the problem can get very challenging indeed. You might consider evolutionary algorithms in order to avoid local maximums. Or an annealing algorithm. Here's a fantastic book that has loads of information on heuristics: How to Solve It: Modern Heuristics, by Michalewicz and Fogel. This book is simply a fun read. I'd highly recommend it.

2. very good idea thx very much u helped me alot
i understand u

3. You're welcome. Incidentally, I was able to code up a solution in Mathematica:

$X=\{3,5,6,8,11\};$

$Y=\{1,5,2,4,1\};$

$PY=\text{Permutations}[Y];$

$\text{LargeArea}=-\infty;$

$\text{BestPermutation}=Y;$

$\text{For}[k=1,k<\text{Length}[PY], k++;$

$\text{NewArea}=\frac{1}{2}\sum_{j=2}^{\text{Length }[X]}
((X[[j]]-X[[j-1]])(PY[[k]][[j]]+PY[[k]][[j-1]]));$

$\text{If}[\text{NewArea}>\text{LargeArea},\text{BestPermutat ion}=PY[[k]]; \text{LargeArea}=\text{NewArea}]$

$];$

$\text{BestPermutation}$

$\text{LargeArea//N}.$

The output for this test case was

$\{1,2,4,5,1\}$

$24.$

You're welcome. Have a good one!

Page 4 of 4 First 1234