Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Interesting optimization problem

Subject: Interesting optimization problem

From: Luis Felipe

Date: 28 May, 2010 21:04:12

Message: 1 of 11

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.

Subject: Interesting optimization problem

From: us

Date: 28 May, 2010 21:08:08

Message: 2 of 11

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

Subject: Interesting optimization problem

From: Walter Roberson

Date: 28 May, 2010 21:18:12

Message: 3 of 11

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.

Subject: Interesting optimization problem

From: Bruno Luong

Date: 28 May, 2010 21:21:05

Message: 4 of 11

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

Subject: Interesting optimization problem

From: us

Date: 28 May, 2010 21:22:21

Message: 5 of 11

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

Subject: Interesting optimization problem

From: Walter Roberson

Date: 28 May, 2010 22:09:13

Message: 6 of 11

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?

Subject: Interesting optimization problem

From: Bruno Luong

Date: 28 May, 2010 22:25:10

Message: 7 of 11

>
> 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

Subject: Interesting optimization problem

From: Matt J

Date: 28 May, 2010 22:29:22

Message: 8 of 11

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?

Subject: Interesting optimization problem

From: Walter Roberson

Date: 28 May, 2010 23:23:37

Message: 9 of 11

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)

Subject: Interesting optimization problem

From: Roger Stafford

Date: 28 May, 2010 23:55:24

Message: 10 of 11

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

Subject: Interesting optimization problem

From: Bruno Luong

Date: 29 May, 2010 06:59:11

Message: 11 of 11

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

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us