The gradient method works well for solving the type of problem that we have termed the standard asset allocation problem:
- Select:
- x
- to maximize:
- u = ep - vp/rt
- where:
- ep = x'*e
vp = x'*C*x- subject to:
- sum(x) = k
lb <= x <= ub
If there are no bounds on holdings, cases with additional linear constraints can be solved directly, as we have shown in the previous sections. But thus far we have no procedure for solving cases in which there are both bounds on holdings and linear constraints in addition to the standard full-investment constraint.
Fortunately, Markowitz developed a general procedure in Markowitz 1956 that can handle additional linear constraints and upper and lower bounds on holdings. Moreover, the approach provides a method for determining the entire set of efficient portfolios. And, (as if this were not enough) it also leads to conclusions about the properties of the efficient set and a new separation theorem.
Markowitz called his procedure the critical line method, as shall we.
Recall that the standard problem involves two sets of constraints. The first requires that the sum of the proportions invested equal a constant:
sum(x) = k
The second constraints require that the proportions remain within specified bounds:
lb <= x <= ub
As in the analysis of problems without bounds, we can generalize the first constraint to allow for any desired number of constraints as long as they are linear in the variables (x values). Given m such constraints. We require that:
A*x = b
where A is an {m*n} matrix with the left-hand side coefficients of the constraints, and b is an {m*1} vector of the right-hand sides of the constraints. As indicated earlier, a problem with only the full investment constraint is a special case in which m=1 and all the coefficients in A and b are equal to 1.0.
Linear equality constraints may be of some interest in their own right, but in most practical cases they are only a means to an end. By combining a linear equality with bounds on a variable one can constrain a linear function of the asset holdings to be within desired bounds.
To illustrate, consider a three-asset case in which it is desired to limit the amount invested in cash plus bonds to 40% of the overall portfolio. To do so, we introduce a new variable (number 4) to represent the sum of the amounts invested in assets 1 plus 2. To make this variable (X4) equal to the sum of X1 and X2, we add a second equation to the constraint set, giving:
A = [ 1 1 1 0 1 1 0 -1 ]b = [ 1 0 ]
Note that in the first (full-investment) constraint, variable 4 has a coefficient of zero, since it is not an investment, per se.
To restrict the amount invested in the sum of the first two asset classes to be less than 40% of the portfolio, we need only to assign the appropriate values for the bounds on variable 4. In this case:
lb = [ 0 0 0 0 ]ub = [ 1 1 1 0.4 ]
We are now ready to formally define two versions of the general asset allocation problem. The non-parametric general asset allocation problem has the form:
- Select:
- x
- to maximize:
- u = ep - vp/rt
- where:
- ep = x'*e
vp = x'*C*x- subject to:
- A*x = b
lb <= x <= ub
The parametric general asset allocation problem has the form:
For all positive values of rt:
- Select:
- x
- to maximize:
- u = ep - vp/rt
- where:
- ep = x'*e
vp = x'*C*x- subject to:
- A*x = b
lb <= x <= ub
The solution to the parametric version will be a matrix of portfolios rather than a single portfolio. One might imagine that this would be huge -- containing, for example, a different portfolio for every possible level of risk tolerance. Not so. We will show that in fact, a remarkably parsimonious matrix of portfolios can be used to determine the solution to the non-parametric version of the problem for any desired magnitude of rt. This rather opaque statement will (hopefully) be clear as the analysis unfolds.
To illustrate some of the key concepts that form the basis for the critical line method, we use a variation on the by-now familiar three-asset problem. The assets are cash, bonds and stocks, with expected returns, risks and correlations:
e = 2.8000 6.3000 10.8000 sd = 1.0000 7.4000 15.4000cc = 1.0000 0.4000 0.1500 0.4000 1.0000 0.3500 0.1500 0.3500 1.0000
To make the problem interesting, we assume that for some reason, it is required that at least 20% of the portfolio be invested in each of the assets and that no more than 50% of the portfolio be invested in any asset. Thus:
lb =
0.2000
0.2000
0.2000
ub =
0.5000
0.5000
0.5000
Our goal is to find all the portfolios which are efficient. In effect, we wish to maximize ep-vp/rt for every non-negative value of rt.
To start, we take a somewhat easier problem:
- Maximize
- e - vp/rt
- when
- rt = infinity
Of course, this is equivalent to:
- Maximize
- ep
- where:
- ep = x'*e
vp = x'*C*x- subject to:
- A*x = b
lb <= x <= ub
This is a linear programming problem, since all the constraints are linear, some are inequalities, and the objective function is linear. Many algorithms exist for solving such problems. The MATLAB optimization toolbox contains a function called lp that can handle any such problem. Since it is designed to minimize a linear function f'*x, the signs of the expected returns must be reversed to achieve maximization of ep. Since the function can also handle somewhat more general problems, two additional arguments need to be included. For our purposes these can be written as functions of e and A. The maximum-expected return portfolio can then be found using the statement:
xinf = lp(-e,A,b,lb,ub,ones(size(e)),size(A,1));
where the notation xinf serves to indicate that this is the composition of a portfolio that is optimal for an Investor with infinite risk tolerance.
While problems with two or more linear equalities are best solved using general linear programming algorithms, cases such as the present one, in which the only equation is the full investment constraint can be solved more simply using the following algorithm:
1. set all variables at their lower bounds
2. rank the variables in order of decreasing e(i)
3. increase the amount invested in the highest-e(i) variable to the smaller of
a. the lower bound plus the remaining funds
b. the upper bound
4. repeat step 3 with the next highest e(i) variable until no funds remain
In MATLAB:
% given e, lb, ub, finds maxe-portfolio xinf where sum(xinf)=1
xinf = lb;
[zz,ii] = sort(-e);
amtleft = 1 - sum(xinf);
ix = 1;
while amtleft>0
i = ii(ix);
chg = min((ub(i)-lb(i)),amtleft);
xinf(i) = xinf(i) + chg;
amtleft = amtleft-chg;
ix = ix+1;
end;
In this case:
xinf =
0.2000
0.3000
0.5000
Now, recall the classification of a variable's status in a solution:
down: l(i) = x(i) in: l(i) < x(i) < u(i) up: x(i) = u(i)
In this case, cash is down (at its lower bound), bonds are in (the solution), and stocks are up (at the upper bound).
It is convenient to represent the states of the variables in a vector (s) using the following conventions:
i down : s(i) = -1
i in : s(i) = 0
i up : s(i) = 1
Here:
s =
-1
0
1
We have found the optimal portfolio for an Investor with infinite risk tolerance. What about one with a risk tolerance of, say, 45?
To find an answer we might guess that the status of each variable in such a case would be the same as in the solution for rt=infinity. There is no reason to believe that this is so (except a suspicion that the author may know it to be the case). But for now, assume that it is true.
Given this information, could you easily determine the magnitudes of the variables? Yes indeed.
Recall the solution equation for the case in which no bounds are binding:
D*y = k + rt*f
In this case:
2*C(1,1) 2*C(1,2) 2*C(1,3) 1 x(1) 0 e(1) 2*C(2,1) 2*C(2,2) 2*C(2,3) 1 * x(2) = 0 + rt* e(2) 2*C(3,1) 2*C(3,2) 2*C(3,3) 1 x(3) 0 e(3) 1 1 1 0 tmup 1 0
The first equation is derived by setting the derivative of the Lagrangean function with respect to the first variable equal to zero. The second equation is derived by doing so with respect to the second variable. And so on, for the first n equations. These first-order condition equations remain appropriate for the variables that are in the solution, for their bounds are not binding and hence could have been omitted entirely (at least for the risk tolerance being examined). Note, however, that the corresponding equations will not generally hold for variables that are down or up. On the other hand, it is easy to write an equation for any such variable, since it must be at the corresponding bound. In the case at hand we need to replace the first equation with one that states:
x(1) = lb(1)
and the third equation with one that states:
x(3) = ub(3)
This is easily done by modifying D, k and f to give:
DD*y = kk + rt*ff
where the new matrices and vectors are:
1 0 0 0 x(1) 0.20 0 2*C(2,1) 2*C(2,2) 2*C(2,3) 1 * x(2) = 0 + rt* e(2) 0 0 1 0 x(3) 0.50 0 1 1 1 0 tmup 1 0
We can now proceed to solve the system of equations. The solution is given by:
y = inv(DD)*kk + rt*inv(DD)*ff
Here:
y =
0.2000
0.3000
0.5000
209.5740
If everything else is correct, the optimal portfolio is the same for someone with a risk tolerance of 45 as for someone who doesn't care at all about risk!
In all the asset allocation problems we have analyzed the goal is to maximize a Lagrangean function. In this case, it is:
L = rt*ep - vp + g1*[b(1)-A(1,:)*x]
The objective is to reach the highest point in a terrain in which altitude is measured by L. However, in this setting we may not be on a smooth terrain. The presence of inequality constraints may lead to places in which there is an abrupt change in slope or a move in one or more directions is infeasible (in a sense, there is a fence). Nonetheless, there are some characteristics of the optimal position that can be exploited when designing a solution algorithm.
Consider dL/dx(i) in the x(i) direction when at the optimal point. If x(i) is an in-variable, this derivative (slope) must be zero or else we would not in fact be at the top of the feasible hill. Thus we have:
dL/dx(i) = 0 : for all in variables
Now consider dL/dx(i) at the optimal point for a down-variable. If this were positive, we could not be at the top of the feasible hill since an increase in x(i) would improve the solution. However, it could (and in most cases would) be negative, indicating that a further decrease would lead to a higher value of L, but such a decrease is not allowed. Thus:
dL/dx(i) <=0 : for all down variables
Finally, it must be the case that dL/dx(i) is zero or positive for all up variables. If such a slope were negative, it would pay to decrease the value of the variable, since by so doing one could reach a higher position. Thus:
dL/dx(i) >= 0: for all up variables
These three characteristics of an optimal solution are collectively known as the Kuhn-Tucker conditions. If they are not met, a portfolio is not optimal.
To make certain that all is well with a purported solution, it is a simple matter to compute the derivative of the Lagrangean with respect to each variable. In this case the Lagrangean is:
L = rt*ep - vp + g1*[b(1)-A(1,:)*x]
The derivative of L with respect to Xi is:
dL/dx(i) = rt*e(i) - 2*C(i,:)*x -g1
and the full set of the derivatives with respect to the assets can be written in matrix form as:
dL = rt*e - 2*C*x -g
where g is the vector of Lagrange multipliers.
Since vector y contains the asset holdings (x) plus the Lagrange multipliers (g), we may take advantage of the structures of vector f and matrix D to write:
dL = rt*f - D*y
where the first n elements of dL are the derivatives of L with respect to the asset holdings.
For the case at hand:
dL =
-88.0600
0
14.4104
-1.0000
Note that all the Kuhn-Tucker conditions for an optimal solution have been met. The derivative is negative for the down variable (cash), zero for the in variable (bonds),and positive for the up variable (stocks).
By good fortune and hard work we have found the solution to the portfolio problem when rt = 45. We have also verified that it is indeed the solution by checking the derivatives of the Lagrangean function to see that they satisfy the Kuhn-Tucker conditions for optimality. But what about a case in which rt = 44? If in fact all the variables have the same status as in the previous solution we can use the same formulas. The portfolio is given by:
y = inv(DD)*kk + rt*inv(DD)*ff
and the derivatives by:
dL = rt*f - D*y
For rt = 44 we obtain:
y = 0.2000 0.3000 0.5000 203.2740dL = -84.5600 0 9.9104 -1.0000
It worked! Each asset in vector y is within its allowable bounds and the derivatives satisfy the Kuhn-Tucker conditions.
We could, if desired, go on like this, trying values for rt of 43, 42, 41, etc. until the procedure "did not work". There are two ways that a purported solution could fail. First, one or more of the variables in y could be outside the permissible bounds. Second, the required Kuhn-Tucker conditions for the derivatives could be violated. In the first instance the ostensible solution would be infeasible. In the second instance, it would be suboptimal.
But we need not proceed by trial and error. Instead we can determine the value of rt at which one or both of these conditions will first be violated as the value of rt is decreased.
To keep the notation reasonably simple, it is useful to rewrite:
y = inv(DD)*kk + rt*inv(DD)*ff
as:
y = ya + yb*rt
where:
ya = inv(DD)*kk yb = inv(DD)*ff
In this case:
ya = 0.2000 0.3000 0.5000 -73.9260yb = 0 0 0 6.3000
Now, recall that:
dL = rt*f - D*y
Substituting the equation for y gives:
dL = rt*f - D*(ya + yb*rt)
Simplifying:
dL = dla + dlb*rt
where:
dla = -D*ya dlb = f - D*yb
In this case:
dla =
69.4400
0.0000
-188.0896
-1.0000
dlb =
-3.5000
0
4.5000
0
Now, note that a variable may change status in one of four ways as rt falls.
1) An in variable may go up. This can only happen if yb(i) is negative. The critical value of rt (crt) is reached when y(i)=ub(i), that is, when:
ub(i) = ya(i)+yb(i)*crt or: crt(i) = (ub(i) - ya(i))/yb(i)
2) An in variable may go down. This can only happen if yb(i) is positive. The critical value of rt is reached when y(i)=lb(i), that is, when:
lb(i) = ya(i)+yb(i)*crt or: crt(i) = (lb(i) - ya(i))/yb(i)
3) A down variable may come in. This can only happen if dlb(i) is negative. The critical value of rt is reached when dL(i)=0, that is, when:
0 = dla(i)+dlb(i)*crt or: crt(i) = -dla(i)/dlb(i)
4) An up variable may come in. This can only happen if dlb(i) is positive. The critical value of rt is reached when dL(i)= 0, that is:
0 = dla(i)+dlb(i)*crt or: crt(i) = -dla(i)/dlb(i)
Applying these rules to the case at hand gives the following critical values of rt for our three variables:
crt =
19.8400
0
41.7977
The greatest value of crt is the next value at which a variable must change status. Letting nrt represent the next critical value of rt:
nrt = max(crt);
In MATLAB we can find both the next critical value of rt and the variable to change status in one expression:
[ncp,ichg] = max(crt);
where ichg is the variable for which crt is largest. In this case:
ncp =
41.7977
ichg =
3
So stocks (variable 3) are to change status. Since s(3)=1, they want to go from up (s=1) to in (s=0).
Before proceeding further, it is important to draw some implications from our experience to date. Imagine that we know that for a range of risk tolerances from rta to rtb the same bounds are binding. In other words, within this range, as risk tolerance is changed each member (if any) of one set of variables will remain at its upper bound, each member (if any) of another set of variables will remain at its lower bound, and each of the other variables will move within its designated bounds. For this range of risk tolerances one could find the optimal set of portfolios by solving the standard set of linear equations using the same DD matrix and kk and ff vectors. Therefore, within this range every asset holding is a linear function of risk tolerance. This in turn implies that for any risk tolerance between rta and rtb, the optimal portfolio can be constructed by simply taking a weighted average of the portfolios that are optimal for rta and rtb, with the weights proportional to the difference between the desired risk tolerance and the endpoints of the range rta to rtb.
This observation provides the motivation for assigning a name to each portfolio that is optimal for a risk tolerance at which a variable changes status. We call such a portfolio a corner portfolio because in a graph that plots holdings against risk tolerance, two or more variables "turn a corner". As we will see, corner portfolios play a central role in the critical line algorithm. They also are attractive candidates for mutual funds.
We now have the ingredients to complete the algorithm for the parametric general asset allocation problem. Here it is in outline form:
1. Find the portfolio that gives the maximum expected return. 2. Determine the status of each variable in the max-e portfolio. 3. Record the composition of the portfolio4. Compute DD, kk and ff given the current status of each variable. 5. Find the equations for the optimal holdings and the derivatives of the Langrangean function. 6. Determine the next critical value of rt and the variable to change status. 7. Determine the optimal portfolio for the next critical value of rt and record it and the associated value of rt8. Repeat steps 4 through 8 until the last critical value of rt is zero or negative
The end result will be a matrix of portfolios and a vector of the associated risk tolerances. With the exception of the first, each of the portfolios in the matrix will be a corner portfolio. Moreover, this information is all that is needed to determine the optimal portfolio for any degree of risk tolerance! Given an Investor's risk tolerance, the Analyst needs only to do a table lookup to find the two corner portfolios for risk tolerances on either side of the desired value, then perform a simple computation involving a weighted average of the compositions of the portfolios in question.
The figure below shows the composition of all optimal portfolios, given our inputs, for risk tolerances from 0 to 50 (the blue line represents Cash, the red line Stocks, and the green line Bonds).
The corner portfolios are evident in the figure. Their compositions are shown in the table below:
rt % Cash % Bonds % Stocks <= 13.73 50.00 30.00 20.00 15.10 45.19 34.81 20.00 21.02 22.18 50.00 27.82 22.30 20.00 50.00 30.00 22.94 20.00 50.00 30.00 >=41.80 20.00 30.00 50.00
Note that over the range of risk tolerances from 22.30 to 22.94 the optimal composition remains the same. This is not a rounding error. Since the efficient frontier is piecewise quadratic, there is always the possibility that there is a kink at the point corresponding to a specific level of risk and return. In such a case indifference curves with different slopes (risk tolerances) can be tangent to the efficient frontier at the same point, giving the same optimal portfolio.
A world with inequality constraints is more complex than one without them. In such a setting, it is rarely possible to obtain an optimal investment strategy by determining a single optimal combination of risky securities, then mixing it with borrowing or lending to suit the risk tolerance of a given Investor. However, all is not lost. It is still possible to construct a limited number of mutual funds, each holding a portfolio of risky securities that is optimal for a particular risk tolerance, then allocate the assets of each Investor between two of the resulting mutual funds. This of course cannot be done haphazardly. To minimize the number of mutual funds, each should hold a different corner portfolio from the optimization analysis. If there are C different such corner portfolios, the minimum number of mutual funds required to service all possible Investors will equal C. Each fund will be ideal (if the optimization inputs were correct) for an Investor with a specific risk tolerance. Given this set of funds, each Investor should allocate his or her money between the two funds with objectives (risk tolerances) closest to his or her own.
In a world of inequality constraints, there may need to be as many funds as there are different corner portfolios in the efficient set of portfolios. Given C such funds, the investment decision can be separated into (1) the formation of C funds and (2) the choice of one or two among them for each Investor. We memorialize this process by calling it C-fund Separation.
If additional linear attributes are important, more efficient funds will be required, and the Investor will typically have to choose a combination of A funds (where A is the total number of relevant attributes). But separation of the process into two phases (construction of a set of mutual funds and Investor choice among those funds) is still possible.
The results associated with the critical line algorithm have important implications for practical people. We finish with a case in point.
Assume that there are four efficient funds, advertised as conservative (C), moderate (M), aggressive (A) and very aggressive (V), differing only in levels of risk (that is, no additional attributes are relevant). An Investor with preferences lying between "moderate" and "aggressive" should allocate assets between funds M and A. While he or she might achieve the same amount of risk by choosing a combination of C and V, this would be inefficient, giving lower expected return.. A slightly better choice, although still an inefficient one, might involve investing in all four mutual funds. But the best choice of all involves only the two funds with objectives nearest those of the Investor in question. This suggests that the desire to diversify across many mutual funds, each of which is itself relatively diversified, may be counterproductive. It is entirely possible to have too many mutual funds!
