Page 4 of 4 FirstFirst 1234
Results 46 to 48 of 48

Math Help - help in Integral Maximization

  1. #46
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    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.
    Follow Math Help Forum on Facebook and Google+

  2. #47
    Member
    Joined
    Jun 2010
    From
    Zewail University - Cairo - Egypt
    Posts
    136
    very good idea thx very much u helped me alot
    i understand u
    Follow Math Help Forum on Facebook and Google+

  3. #48
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    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]}<br />
((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!
    Follow Math Help Forum on Facebook and Google+

Page 4 of 4 FirstFirst 1234

Similar Math Help Forum Discussions

  1. Maximization
    Posted in the Calculus Forum
    Replies: 2
    Last Post: May 31st 2010, 02:47 PM
  2. Maximization
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: February 25th 2010, 06:08 PM
  3. Maximization
    Posted in the Calculus Forum
    Replies: 1
    Last Post: December 11th 2009, 08:11 PM
  4. Maximization
    Posted in the Calculus Forum
    Replies: 5
    Last Post: April 13th 2008, 04:55 AM
  5. Maximization
    Posted in the Calculus Forum
    Replies: 6
    Last Post: January 19th 2007, 12:39 AM

Search Tags


/mathhelpforum @mathhelpforum