Re: Maximum value of a function...

Thanks a lot for all your replies.
It was quite helpful.
In fact the constants Ci's are between 0 and 1.
So 0 < Ci <= 1

I have a cost function which has two parameters as inputs, constant N
and C1, C2, ..., Ck. As a matter of fact k (number of coefficients) is
also not constant in general. So for different instances of the
problem, I might have different k's.

The cost function is actually the time complexity of an algorithm and
I'm trying to do worst-case time analysis.

Complexity of the algorithm is: X1^C1 x X2^C2 x ... x Xk^Ck with the
constraint that X1 + X2 + ... + Xk = N.

I know that if C1 = C2 = ... = Ck = N / k, then the function would be
maximized as it would be (N / k)^k. Now to check the max of this based
on k, I actually found out that k = [N / e] would maximize it.
(everything is an integer. Ci's are 1/Ti where Ti is an integer!)

In that case the function would become e^N. So for these specific
values the algorithm is exponential for input size N.

However if Ci's are in general 0 < Ci <= 1 and not necessarily the
same, based on the replies the function would become:

N^k x (C1 x C2 x ... x Ck) / (C1 + C2 + ... + Ck)^k

So now I'm stuck. How can I get the maximum of this function having k
as the variable?
Is it going to be polynomial or again exponential?

How does the maximum look like?

I appreciate any kind of comment. If everything was continuous I could
use normal procedure of derivation to find the max (not so easily
though) however now I have no idea how I can find the maximum of this
function.

Thanks beforehand,

Amir

On Jul 24, 9:05 am, Ray Vickson <RGVick...@xxxxxxx> wrote:
On Jul 23, 7:22 pm, Amir <amirhossein.gholamip...@xxxxxxxxx> wrote:



Hi,
Hope everybody is doing just fine.
This might look silly in this group, but I have faced a problem which
I don't know how to solve and I have been away from calculus for a
long time now.
Here is the problem and I appreciate your help and comments in this
regards:

I have k variables X1, ..., Xk.
N, C1, C2, ..., Ck are constant numbers.

I know that:

X1 + X2 + ... + Xk = N

I want to maximize:

X1^C1 x X2^C2 x ... x Xk^Ck

I know that if C1 = C2 = ... = Ck then the above mentioned expression
is maximized when X1 = X2 = .. = Xk = N / k

However I'm not sure how it works considering that Ci's are not equal
necessarily. Besides the values for Xi's should be integer, but it
doesn't really matter. I'm not very concerned about that at this
moment.

Thanks a lot beforehand for your comments,

Amir

The solution Xi = N Ci/sum_j Cj only works if all Ci are > 0 (or, at
least, >= 0). It fails if some Ci are > 0 and others < 0. In such a
case there may be NO finite maximum. For example if [Ci] = [1/2, 1,
3/2, -5/2] we have sum_j Cj = 1/2 but C4 < 0. In this case f = product
(Xj^Cj ,j=1..4) can go to +infinity on the plane sum Xj = 1; for
example, if X1 = X2 = X3 = t/3 and X4=1-t, we have f = (1/27)*t^3 / (1-
t)^(5/2), and this --> +oo as t --> 1 from the left.

R.G. Vickson

.

Relevant Pages

  • Re: overlaping rectangles issue
    ... works because both the heuristic and the cost functions leads it ... The cost function should give a very high cost to boxes that won't fit. ... happening in each step of Simon's first algorithm. ... just re-calculate the total cost (sum of distances) as if you had made ...
    (rec.games.roguelike.development)
  • Re: overlaping rectangles issue
    ... (sum of the box distance) ... The cost function should give a very high cost to boxes that won't fit. ... situation you don't wanna force the algorithm to find a way to cram ...
    (rec.games.roguelike.development)
  • Formalism
    ... I'm looking for a formal definition of the following problem that I first ... 'E' that can be processed by each algorithm 'a', ... parameter) such that some given cost function is maximized. ... this is a simple maximization problem that I would like to express ...
    (sci.math)
  • Re: [9fans] `mk` (from Plan9 ports) efficiency related issue
    ... using simple algorithm with much worse time complexity than ... upfront as that would definitely be much faster than walking ... A dependency matrix is usually very sparse ...
    (comp.os.plan9)
  • Re: Quicker then QuickSort???
    ... Thank you for the information about the time complexity! ... Kristofer Gafvert - IIS MVP ... i cannot tell you the Ofor this algorithm (because i am ... > are sorting 30 things, an n^2 algorithm may go faster, but when sorting ...
    (microsoft.public.dotnet.languages.csharp)