Thread: help in Integral Maximization

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 , where 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:



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:



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.

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

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























The output for this test case was





You're welcome. Have a good one!