Re: Find Max of "Concave" List

• To: mathgroup at smc.vnet.net
• Subject: [mg13200] Re: Find Max of "Concave" List
• From: "Allan Hayes" <hay at haystack.demon.cc.uk>
• Date: Mon, 13 Jul 1998 07:42:48 -0400
• References: <6n4rki\$o17@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```Jrgen Tischer wrote in message <6n4rki\$o17 at smc.vnet.net>...
>Hi Chris,
>not elegant, but quite fast: bisection:
>
>concaveMax[li_]:= Module[{a=1,b=Length[li]},
>          While[b-a>1,
>            With[{n=Quotient[b+a,2]},
>                If[li[[n]]==li[[n+1]],Return[li[[n]]]];
>                If[li[[n]]<li[[n+1]],a=n+1,b=n]]];
>          Max[li[[a]],li[[b]]]]
>
>J=FCrgen

Jrgen,
Reducing the amount of testing at each step might be a good overall
strategy:

concaveMax[li_]:=
Module[{a=1,b=Length[li]},
While[b-a>1,
With[{n=Quotient[b+a,2]},
If[li[[n]]==li[[n+1]],Return[li[[n]]]];
If[li[[n]]<li[[n+1]],a=n+1,b=n]
]
];
Max[li[[a]],li[[b]]]
]

concaveMax2[li_]:=
Module[{a=1,b=Length[li],n},
While[a!=b,
n=Quotient[b+a,2];
If[li[[n]]<li[[n+1]],a=n+1,b=n]

];
li[[a]]
]

TEST:
li = Join[ Range[10000],Reverse[Range[9000]]];

concaveMax[li]
10000

concaveMax2[li]
10000

Do[concaveMax[li],{100}]//Timing
{1.05 Second,Null}

Do[concaveMax2[li],{100}]//Timing
{0.66 Second,Null}

Allan

------------------------------------------------------------- Allan
Hayes
Training and Consulting
Leicester UK
http://www.haystack.demon.co.uk
hay at haystack.demon.co.uk
voice: +44 (0)116 271 4198
fax: +44(0)116 271 8642

>
>-----Original Message-----
>From: Chris Farr <farr at brown.edu>
To: mathgroup at smc.vnet.net
>Subject: [mg13200] [mg12918] Find Max of "Concave" List
>
>
>>
>>I have a one-dimensional list which is concave.  That is, if you did a
>>ListPlot on the list you would have a concave curve.
>>
>>Given the concavity, when finding the max, it is inefficient to use
>>Max[] which does a comparison on all elements of the list.
>>
>>Is there an elegant way to exploit the concavity when performing a
>>Max[]?  That is, the algorithm should stop when the next element in the
>> list is lower then the previous element.  This would limit the number
>>of  comparisons.
>>
>>Thanks,
>>
>>Chris Farr
>>
>>
>
>

```

• Prev by Date: symbolized symbol in LHS of function
• Next by Date: Anyone use MultiplierMethod.m Package for Nonlinear Optimization?
• Previous by thread: symbolized symbol in LHS of function
• Next by thread: Anyone use MultiplierMethod.m Package for Nonlinear Optimization?