I am trying to maximum the term G = (k1+a)^p x (k2+b)^q x (k3+c)^r
where k1, k2, and k3 are known constants, p, q and r are values
between 0 and 1, such that p+q+r = 1 and a, b and c are non-negative
such that (a+b+c)<1. This can be done within Excel solver, but the
right answer is not always obtained (I can adjust one of the values
and increase G). Does anyone know of a method of doing this inside or
outside of Excel, please?

---

Clarification of Question by gampas-ga on 03 Oct 2006 09:00 PDT

k1, k2 and k3 are the current values of a portfolio depending on which
of three outcomes occur. They must be >0 and, in theory have no upper
limit. They are expressed in terms of the original asset, so that 1.1
means an increase of 10%, but this is not relevant. These outcomes
have probabilities p, q and r which total 1 and are obviously positive
values such that 0< p,q,r <1. It can be assumed that no solving is
needed if any of them is equal to 1! a, b and c are additions to the
portfolio, again positive values such that 0 < a+b+c <1.

I shall try the logarithmic approach, and also try the program
approach. Thanks again barneca and math-talk

---

Request for Question Clarification by mathtalk-ga on 08 Oct 2006 08:00 PDT

If you'd care to give some explicit values, I can use them to
illustrate the way to get the explicit solution outlined in my most
recent Comment.

regards, mathtalk-ga

i suspect you have so many variables that there are lots and lots of
local maxima, and that might be screwing up excel's solver.

first of all, if a researcher or another commenter wants to attack
this problem more formally, they might want to know if there are any
limits (non-negative, less than 1, etc) on k1, k2, and k3, and on each
(ki+x) term.  in a mathematical attack, i think it will matter whether
all of the (ki+x) are between zero and one or not.

as an engineer rather than a mathematician, it seems to me your best
bet is a brute force method: a short quickbasic (or similar) program
with lots of loops in it that will calculate G for every possible
combination of p,q,r,a,b,c.  you can control the step size to get as
accurate as you want; i doubt even a high degree of accuracy will take
very long to run.  if you know any programming language it should take
you 5-10 minutes to write a little program with 6 nested loops
(actually 5, i guess, since r=1-p-q) that spits out the largest G.

if you need to do it in excel, i hope someone else can help you out. 
too many variables to just make a big table.  you could probably
create a macro with loops in it, but we've just exceeded my knowledge
of excel.

-cab

Thanks for those comments, barneca. All of k1+x, k2+y, k3+z are
greater than 0, and, usually, less than 2. They represent the new
portfolio value for an outcome with probability p,q,r etc, where the
original value was 1. Yes, I think I could write a program with nested
loops which would give the answer quicker than Solver.

it was either this or start working this morning.  i chose this.

here's a skeleton of a quickbasic program, NOT guaranteed to be free of bugs.

Gmax = 0
input k1, k2, k3
input i
for p=0 to 1 step i
   for q=0 to (1-p) step i
      r=1-p-q
      for a = 0 to 1 step i
         for b= 0 to (1-a) step i
            for c = 0 to (1-a-b) step i
               G = (k1+a)^p * (k2+b)^q * (k3+c)^r
               if G>Gmax, Gmax=G
            next c
         next b
      next a
   next q
next p
print Gmax
end

-cab

I might try reformulating the problem for Excel's solver by taking logarithms:

max ln(G(a,b,c,p,q,r)) = p*ln(k1+a) + q*ln(k2+b) + r*ln(k3+c)

subject to:

 0 <= p,q,r, p+q+r = 1

 0 <= a,b,c, a+b+c < 1 (???)

As you can see, I have a question about the last constraint.  It seems
likely to me that in many cases the the actual maximum would be
attained only in the limit as a+b+c = 1, but the strict inequality
given in the original Question above will not allow this.

Is it intended?

regards, mathtalk-ga

One more Clarification, please.  You describe k1,k2,k3 as "known
constants", but not p,q,r or a,b,c in these terms.  Are p,q,r "given"
or parameters to be adjusted?  I was under the impression that all
p,q,r and a,b,c are "adjustable" values, but perhaps this is not your
meaning.

regards, mathtalk-ga

The reason I asked for Clarification as to whether probabillities
p,q,r are adjustable parameters in your problem, as I believe a,b,c
are (relative allocations to components of the portfolio), is that
without being required to choose optimal p,q,r (if these are "given"),
then your problem can be solved explicitly.

Briefly described, the strategy is to increase the component(s) a,b,c
which have the largest corresponding first-order partial derivative. 
If more than one component shares equally with another the largest
partial derivative, then these components must increase together to
keep that equality.  The optimal allocation in this circumstance is
given by "steepest ascent".

Consider p,q,r as constants, and maximize g(a,b,c) = ln(G) with respect to:

0 < a,b,c ; a + b + c <= 1

The first thing we will show is that the maximum occurs when a+b+c =
1.  I recognize that you did not explicitly state that the boundary
a+b+c = 1 is allowed, because you restate the problem with the strict
inequality:

0 < a + b + c < 1

However the maximum occurs on the boundary, so mathematically if you
wish to exclude the boundary, then you will be able to approach the
maximum of g (or G) as closely as desired but never attain it.

To see why the maximum is reached only with a + b + c = 1, let's first
examine the partial derivatives of g(a,b,c):

[1st Order Partial Derivatives]

gradient g = [ p/(k_1 + a) , q/(k_2 + b) , r/(k_3 + c) ]

[2nd Order Partial Derivatives]

Hessian g = diag( -p/(k_1 + a)^2, -q/(k_2 + b)^2 , -r/(k_3 + c)^2 )

Now suppose that a maximum value of g occurs at some point (a,b,c) for which:

a + b + c < 1

But at least one of the components of g (first-order partials) is
positive.  In fact any one of them for which the corresponding
probabilty p,q,r is positive is also positive, and p+q+r = 1. 
Increasing that component as allowed by the "slack" in constraint a +
b + c < 1 would locally increase the value of g (by virtue of the
positive partial derivative).

Thus the maximum of g cannot occur at an interior point a + b + c < 1,
and could only occur at a boundary point a + b + c = 1, since
continuing to increase the value of any component a,b,c corresponding
to a positive first partial derivative as above will continue to
increase g.

But we can say more.  We can explicitly compute the allocation of
assets that maximizes g.  Begin by ordering the values of the first
partials at:

  a = b = c = 0

which without loss of generality we may assume (by relabeling if necessary) to be:

  p/k_1 >= q/k_2 >= r/k_3 > 0

Now if we increase a > 0, then g increases because dg/da > 0, but at
the same time the first partial dg/da _decreases_ (as we can see from
the negativity of the second partial d^g/da^2, first diagonal entry of
Hessian of g).

What this means is that if we do nothing else besides increase a, the value of:

  dg/da = p/(k_1 + a) 

will decrease, possibly becoming equal to:

  dg/db = q/k_2   when b = 0

before a reaches 1.  In fact the two may have started out being equal.

If dg/da becomes equal to dg/db by increasing a (or if they start out
being equal), then from that point on we increase a and b
simultaneously in a manner that keeps these two partials equal.

Let's see how this works.  Suppose at a_1 we have reached equality:

  p/(k_1 + a_1) = q/k_2

How should we further increase a and b so that dg/da = dg/db?

Taking reciprocals:

  (k_1 + a)/p = (k_2 + b)/q

we can solve for a as a function of increasing b:

  a = (p/q)b + (p/q)k_2 - k_1

with the initial value that a = a_1 when b = 0 in this expression. 
Note that the increasing value of a depends linearly on increasing b,
and that:

  a + b = (1 + (p/q))b + (p/q)k_2 - k_1

Likewise if we were to reach a point where all three partials are equal:

  dg/da = dg/db = dg/c

before reaching the limiting condition a + b + c = 1, then we must
allocate the remaining increases in a,b,c so that the three partials
remain equal.  This is similar to the above, except that now a,b are
each linear functions of c, and we stop adjusting a,b,c when a + b + c
reaches the bounding value 1.

This analysis can be interpreted as giving the optimal allocation of
portfolio adjustments at any increment a+b+c between 0 and 1.

regards, mathtalk-ga