Thread Subject:

Interesting optimization problem

Hi,

Have you ever seen this optimization problem ?
             n
max prod (p_i)^a_i
           i=1

                                  n
subject to sum p_i = 1
                                 i=1

where a_i is a positive constant for i=1,...,n

I would like to know if that optimization problem has any application
(or has been used to solve anything). Thank you for your comments.

Luis Felipe <luispipe16@gmail.com> wrote in message <8445cd34-c732-4010-aa1c-5a20d6b4b5cf@f14g2000vbn.googlegroups.com>...
> Hi,
>
> Have you ever seen this optimization problem ?
> n
> max prod (p_i)^a_i
> i=1
>
> n
> subject to sum p_i = 1
> i=1
>
> where a_i is a positive constant for i=1,...,n
>
> I would like to know if that optimization problem has any application
> (or has been used to solve anything). Thank you for your comments.

very nice, indeed... but: where's your problem with respect to CSSM (ML) (?)...

us

Luis Felipe wrote:

> Have you ever seen this optimization problem ?
> n
> max prod (p_i)^a_i
> i=1
>
> n
> subject to sum p_i = 1
> i=1
>
> where a_i is a positive constant for i=1,...,n

Your problem statement does not constrain p_i to be non-negative, leaving open
the possibility of using large negative and positive numbers.

Luis Felipe <luispipe16@gmail.com> wrote in message <8445cd34-c732-4010-aa1c-5a20d6b4b5cf@f14g2000vbn.googlegroups.com>...
> Hi,
>
> Have you ever seen this optimization problem ?
> n
> max prod (p_i)^a_i
> i=1
>
> n
> subject to sum p_i = 1
> i=1
>
> where a_i is a positive constant for i=1,...,n
>
> I would like to know if that optimization problem has any application
> (or has been used to solve anything). Thank you for your comments.

Not sure, but this is trivial to solve

Maximizing prod(p.*a) is equivalent to maximizing f(p) := sum(a*log(p))

The gradient of f is a./p.

The KTT condition tells us that

a./p = lambda*(1,1, ..).

Because sum(p) = 1, thus p = a/sum(a). We are done.

Bruno

Walter Roberson <roberson@hushmail.com> wrote in message <htpc0k$9o1$1@canopus.cc.umanitoba.ca>...
> Luis Felipe wrote:
>
> > Have you ever seen this optimization problem ?
> > n
> > max prod (p_i)^a_i
> > i=1
> >
> > n
> > subject to sum p_i = 1
> > i=1
> >
> > where a_i is a positive constant for i=1,...,n
>
> Your problem statement does not constrain p_i to be non-negative, leaving open
> the possibility of using large negative and positive numbers.

again,
very nice, indeed... but: where's your problem with respect to CSSM (ML) (?)...

us

Bruno Luong wrote:
> Luis Felipe <luispipe16@gmail.com> wrote in message
> <8445cd34-c732-4010-aa1c-5a20d6b4b5cf@f14g2000vbn.googlegroups.com>...

>> Have you ever seen this optimization problem ?
>> n
>> max prod (p_i)^a_i
>> i=1
>>
>> n
>> subject to sum p_i = 1
>> i=1
>>
>> where a_i is a positive constant for i=1,...,n

> Not sure, but this is trivial to solve
> Maximizing prod(p.*a) is equivalent to maximizing f(p) := sum(a*log(p))
> The gradient of f is a./p.

I'm not certain, Bruno, whether your solution is intended to work when the a_i
are potentially different from each other?

>
> I'm not certain, Bruno, whether your solution is intended to work when the a_i
> are potentially different from each other?

I believe as long as a a >= 0, it works, otherwise the solution does not exist. But I let those detail for OP to play with.

Bruno

Walter Roberson <roberson@hushmail.com> wrote in message <htpf09$ec7$1@canopus.cc.umanitoba.ca>...

> I'm not certain, Bruno, whether your solution is intended to work when the a_i
> are potentially different from each other?

Seems fine to me, provided that we also have the constraint p>=0, which the OP never verified. What doesn't look right to you?

Matt J wrote:
> Walter Roberson <roberson@hushmail.com> wrote in message
> <htpf09$ec7$1@canopus.cc.umanitoba.ca>...
>
>> I'm not certain, Bruno, whether your solution is intended to work when
>> the a_i are potentially different from each other?
>
> Seems fine to me, provided that we also have the constraint p>=0, which
> the OP never verified. What doesn't look right to you?

The statement that the gradient was a./p -- I'm not sure that is right when
the a(:) are different. Gradient is slope, which would be length(a)-1 values
in between the other values, and the slope between positions K and K+1 would
seem to more naturally depend upon a(K) and a(K+1)

Walter Roberson <roberson@hushmail.com> wrote in message <htpjbp$ko0$1@canopus.cc.umanitoba.ca>...
> The statement that the gradient was a./p -- I'm not sure that is right when
> the a(:) are different. Gradient is slope, which would be length(a)-1 values
> in between the other values, and the slope between positions K and K+1 would
> seem to more naturally depend upon a(K) and a(K+1)

  Bruno's solution is correct, Walter. It is a standard problem in Lagrange undetermined multiplier. At the maximum you have to satisfy two simultaneous differential conditions:

 a1/p1*dp1 + a2/p2*dp2 + .... + an/pn*dpn = 0
 dp1 + dp2 + dp3 + .... + dpn = 0

which forces a1/p1, a2/p2, etc to all be equal. The solution then falls out easily.

Roger Stafford

Walter Roberson <roberson@hushmail.com> wrote in message

> The statement that the gradient was a./p -- I'm not sure that is right when
> the a(:) are different. Gradient is slope, which would be length(a)-1 values
> in between the other values, and the slope between positions K and K+1 would
> seem to more naturally depend upon a(K) and a(K+1)

You seem to miss-interpret the word GRADIENT Walter. In calculus, gradient of function f(p) (from R^n to R) is the vector (df/dp1, df/dp2, ..., df/dpn). Each element is a partial derivative wrt a variable. There is nothing to do with *in between* two variables as you seem to express it.

Bruno