View Question
 Question
 Subject: Optimisation Problem Category: Computers > Algorithms Asked by: gampas-ga List Price: \$10.00 Posted: 28 Sep 2006 07:48 PDT Expires: 28 Oct 2006 07:48 PDT Question ID: 769201
 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
 There is no answer at this time.

 Subject: Re: Optimisation Problem From: barneca-ga on 28 Sep 2006 09:58 PDT
 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
 Subject: Re: Optimisation Problem From: gampas-ga on 28 Sep 2006 19:48 PDT
 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.
 Subject: Re: Optimisation Problem From: barneca-ga on 29 Sep 2006 05:25 PDT
 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
 Subject: Re: Optimisation Problem From: mathtalk-ga on 02 Oct 2006 08:37 PDT
 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
 Subject: Re: Optimisation Problem From: mathtalk-ga on 02 Oct 2006 08:41 PDT
 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
 Subject: Re: Optimisation Problem From: mathtalk-ga on 03 Oct 2006 18:27 PDT
 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