Division of Research Graduate School of Business Administration The University of Michigan The Derivation of Efficient Sets Working Paper No. 97 by Gordon J. Alexander The University of Michigan December 1974 FOR DISCUSSION PURPOSES ONLY None of this material is to be quoted or reproduced without the express permission of the Division of Research.

ABSTRACT The Derivation of Efficient Sets By Gordon J. Alexander In 1952, Harry M. Markowitz described a theory on the selection of assets in forming a portfolio, which has had a major impact on research in the field of finance. His theory postulated that rational investors would select a portfolio from the set of all portfolios which offered maximum expected returns for varying amounts of risk (measured by variance), called the efficient set. Finding the optimal portfolio therefore involves (1) finding the efficient set, and (2) choosing that portfolio from the efficient set which maximizes the investor's utility. This paper will be concerned primarily with solving the former, which involves a quadratic objective function and linear constraints. The complementary pivot algorithm of C. M. Lemke will be shown to be not only adaptable to this problem, but also to be superior to the widely used critical line method in terms of computational efficiency. This working paper represents the culmination of a research project carried out by the author under the auspices of Professor Timothy J. Nantell.

INTRODUCTION In 1952, Harry M. Markowitz / 6/ described a theory on the selection of assets in forming a portfolio. Assuming asset returns are stochastic, his theory postulated that rational investors should select a portfolio from the set of all portfolios which offered minimum risk (measured by variance) for varying levels of expected return. This set was named the efficient set by Markowitz. There are two conditions (each sufficient but not necessary, as shown in / 16 /) that enable the investor to choose his portfolio only on, the basis:of its expected return and variance. First of all, if security returns are normally distributed, then they can be completely described by two parameters -- mean and variance. Secondly, if investors behave as if they had quadratic utility functions, then it can be 1/ shown- that they will choose between alternative portfolios on the basis of mean and variance of return. Assuming one of these conditions is valid, finding the optimal portfolio involves (a) determining the efficient set, which is the concern of this paper, and (b) choosing that portfolio from the efficient set which maximizes the investor's utility. Defining the Problem T The variance of a portfolio (Var (R ) ) is X CX where X is an N by 1 vector representing the proportions of the investor's funds that 1/ - See W. H. Jean, The Analytical Theory of Finance (New York: Holt, Rinehart and Winston, Inc., 1970), p. 76, for a demonstration of this property of quadratic utility functions.

-2 - are to be placed in each of the N securities, and C is an N by N matrix representing the covariance of returns between the N securities. The T expected return of the portfolio (E (R ) ) is X E(R) where E(R) is the A P vector representing the expected returns of the N securities. Deriving the efficient set involves solving the following problem * * for various E, where E represents a given level of expected return: Minimize Var (R ) = xTCX (1) T * Subject to E (R ) = X E(R) = E P X K = 1 X ~ 0. Here K is an N by 1 vector with all its elements equal to one. The problem therefore involves solving a quadratic objective function with linear constraints. METHODS OF SOLVING THE PROBLEM Past research has developed several methods for deriving the efficient set. These methods can be separated into two classes -- those that solve problem (1) exactly and those that seek a solution to problem (1) -by. approximation. One method of exact solution, shown by Martin / 8 /, involves the use of calculus to minimize a Lagrangian objective function formulated from problem (1): Z = X CX + (XTE(R) E) +2 (XN - 1). 1 t2 By taking advantage of the fact that the efficient set is convex, this problem need only be solved for a finite number of values of E is problem need only be solved for a finite number of values of E. This

-3 - method involves the inversion of an N + 2 by N + 2 matrix, and may require extra steps if X is not nonnegative. In 1956 Markowitz / 7_/ derived a widely used algorithm, called the critical line method, which provides another method for determining exactly the efficient set. It begins by finding the portfolio with maximum expected return (point A in Figure 1) and then proceeds to delineate corner portfolios (a corner portfolio being one in which a security either enters or leaves the efficient set):by generating the X vector for each one as it moves down the efficient set through succeedingly smaller values of E. The algorithm stops when it reaches the minimum variance portfolio, denoted by B in Figure 1. This method also involves the continual inversion of an N + 1 by N + 1 matrix, which must be done at each corner portfolio. E(R) Efficient p * Set A Feasible Set B r "- ^^/ Var (R) Fig. 1. Efficient set. The methods for solving problem (1) by approximation involve the use of an expression for the problem which is amenable to either linear programming or available quadratic programming methods. Several of the methods require security returns to be expressed in terms of a single

-4 - index model. This model assumes be represented as: that the return on any security i can where A. variance variance R. = A. + B.I + C. (2) 1 i 1 1 and B.are constants, I is an appropriate market index with 1 2 QM and C. is a random variable with a mean of zero and. here are two vital assumptions to this mode 2 Q.. There are two vital assumptions to this model: 1 Cov (I, C.) = 0 1 Cov (Ci, Cj)= 0 i # j. is used to denote covariance. With these assumptions, portfolio can be expressed as: Here Cov variance. N Var (R) = ( i=l N X.B. )2 Q2 +.2 2 1i MXi 1 1 (3) Sharpe / 11 / has developed an algorithm for finding the efficient set exactly, but requires the problem to be stated in terms of the single index model. It involves the creation of an artificial variable, XN+, which has a value of ( iBiX ). Furthermore, the covariance i=l matrix C has all off-diagonal elements set equal to zero and is then expanded to include an additional row and column of zeros with entry 2 (N + 1, N + 1) equal to Q. This enables portfolio variance to be M T expressed as X S X, where S is the new form of the covariance matrix. With S being a diagonal matrix, Sharpe uses the critical line method to solve the problem:

-5 - Minimize Var (R ) = X S +X (4) p N+l P Subject to E(R ) = X E(R) = E T X K = 1 x~o. The cost savings of this method when compared to the critical line method applied to problem (1) come from the ease of inverting the diagonal matrix SN+. However, the single index model is an appromimation to problem (1) and hence the solution obtained, while exact for problem (4), is an approximate solution to problem (1). Sharpe / 12 / also suggested using the single index model and then solving problem (4) by approximation. He requires the existence of ceilings on the proportion invested in any particular security, justifying it by noting that many investment managers face this constraint by law. This enables him to approximate the portfolio variance in equation (3) by only the first term, ( X.B.i Q2 since the i=l second term will be close to zero. Then Sharpe uses a linear programming technique to solve: Minimize X. B. (5) 1 1 i=l T * Subject to E(R)= XE = E T X K = 1 X 0. x.>o. Hence this method involves two approximations -- the single index model to approximate problem (1) and then an approximation for portfolio variance in the single index model.

-6 - Sharpe / 14 / developed a third method to solve problem (1) which does not require the use of the single index model. Instead, he transforms the objective function of problem (1) so as to diagonalize the covariance matrix C and then uses piecewise linear approximations of the transformation to solve the problem. The results yield an approximate solution to problem (1). Stone / 15 / also devised a way to use a linear programming method to solve the quadratic programming problem (1). However, his method requires the use of the single index model and upper bounds on the X.. Hence two approximations to problem (1) are involved, similar to Sharpe / 14_/. In summary, past methods of solving problem (1) by approximation have this inherent disadvantage: they don't give the exact solution. Those methods which do solve problem (1) exactly have generally been expensive to use. LEMKE'S ALGORITHM C. M. Lemke / 5_/ derived the complementary pivot algorithm in 1965 to solve exactly the complementary problem of the form: W = MZ + Q (6) T W Z = 0 Z 0 Quadratic programming problems may be solved exactly by the use of this algorithm, as demonstrated by Ravindran / 10 /. Since determination

-7 - of the efficient set is a quadratic programming problem, this paper will explore the feasibility of using Iemke's algorithm to solve this problem. Its Applicability Consider the following quadratic programming problem: Minimize D X + X GX Subject to AX $ B X ' 0. x o. Ravindran / 10 / has demonstrated that an optimal solution to this problem may be obtained by solving a complementary problem of the form: Li] = " T 2T] LU] + T T V G C: ~+ G -A U, V, X, Y O V, X + U Y 0. Here W=, Z X= M= G T -A and Q = D Ui Y A -0 -B from the original complementary problem, denoted (6). The efficient set problem fits into this form, setting D = 0 and making the following substitutions: C = G A= E(R) B = E -E(R) -E N 1 -N _-1

-8 - Note that both problems (1) and (6) require the X vector to be nonnegative. Two alterations were made to the above formulation prior to its implementation. First, the second row in the A matrix and the second element in the B vector may be deleted. Figure 1 demonstrates that as the expected return of the efficient set declines, the variance similarly declines. This feature results in the optimal solution, i.e., portfolio with minimum variance and expected return greater than * or equal to E occurring at the smallest feasible expected return, * 2/ T * which is E -. Thus the constraints forcing X E(R) = E are not T * necessary, the constraint X E(R) A E is sufficient. Secondly, to remove the possibility of roundoff errors causing the algorithm to fail in finding a solution, the last element in the B vector was set equal to -1.0001.3/ If upper or lower bound constraints exist on some of the X., because of legal, personal, or institutional dictates, then lemke's algorithm can incorporate them in the problem. Letting E. denote the unit vector th with a one in the i- position, upper and lower bounds on X. and X. 1 3 respectively may be represented by X E. - S and X E. - T. Hence 1 j 2/ ~e* - The only time this does not hold is when E is chosen so that it lies below the minimum variance portfolio of the efficient set, denoted B in Figure 1. This case will be handled subsequently. 3/Requiring X K _ 1 and -X K - -1 caused the algorithm to fail to find a solution when a solution was known to exist. Using -1.0001 was not thought to introduce any significant bias in the optimal solution to the problem.

-9 - matrix A would have the additional rows -E. and E. added onto it and vector B would have -S and T appended to it. Ravindran points out that Lemke's algorithm is guaranteed to find an optimal solution if M is positive semidefinite, which is the case if G is also positive semidefinite. Remembering G equals C, the covariance matrix, and that the variance of any portfolio is nonnegative (i.e., X TCX 0), we find it follows that M is positive semidefinite. Hence lemke's algorithm is guaranteed to find the optimal solution. In deriving the efficient set by use of Iemke's algorithm, a * means of determining which values E should assume is essential. Since Markowitz's critical line method starts by seeking that security with maximum expected return, this procedure was followed in implementing Lemke's algorithm. This return will be denoted E. Next, the maxmax imum of either zero. pr the minimum expected return' of the.Nsecdurities was found, denoted EB.. The interval -.EE.. was divided by 10, mmn max mn and a uniform grid search for the minimum variance portfolio was * carried out by continually decreasing E = E by (1/10)(E max max E. ) and solving problem (1). This search was terminated when the min T expected return (X E(R) ) for the current optimal solution was higher than E, This termination will occur only when the search finds the minimum variance portfolio. To remove the possibility of roundoff errors causing premature termination, the current optimal solution was

-10 - * 4/ 5/ compared with 1.001 E.- Since the efficient set is convex,finding its value at a finite number of points is sufficient in determining its location. A sample problem for 5 securities is provided in Appendix.A. Its Advantages After Ravindran's computer program of Iemke's algorithm was modified as previously described, it was tested on The University of Michigan's IBM System 360 model 67 computer. Since Markowitz's 6/ algorithm was available, — comparisons of the two methods were made. Initial results for 5 and 20 securities are presented in Table 1. Table 1 A Comparison of lemke's and Markowitz's Algorithm N= 5 N= 20 Central Processing Unit Time Markowitz 60 seconds 104 seconds lemke 11 seconds 16 seconds Cost Markowitz $3.64 $9.16 Lemke $1.38 $1.78 4/ -/Roundoff errors could cause the optimal solution to be slightly higher thanE. Hence a precaution was taken to guard against this event. This precaution has no effect on the optimal solution. -/See W. F. Sharpe, Portfolio Theory and Capital Markets, (New York: McGraw-Hill, Inc., 1970), ch. 4, for a description of the shape of the efficient set. 6/ - The program used was written at the Amos Tuck School, Dartmouth College',. Hanover, N.H.!

-11 -7/ Note that in both CPU time and cost,- Lemke's algorithm was superior to the critical line algorithm of Markowitz (see Appendix B for further discussion). On occasion research has involved the comparison of two or more efficient sets which were derived from the same E(R) vector but 8/ different C matrices.- If solutions — i.e., X vectors -- for the different efficient sets at common values of E can be found, direct comparisons of the portfolio variances can be made in order to determine the degree of dissimilarity of the C matrices. This comparison is accomplished by the use of Lemke's algorithm if the previously described uniform grid search method is appended to it, as it will find the X vectors at the same values of E for all the efficient sets. However, the critical line method produces solutions only at corner portfolios. Whether two efficient sets have corner portfolios at the same values of E is an uncertainty. What must be done in the case where there is no explicit solution given at common values of E involves, first, determining at which values of E such comparisons are to be made and then, second, interpolating, if necessary, to find the X vector for each efficient set for each E. Since neither of 7/ - Included in the time and cost figures was the compilation of the respective programs. 8/or exa - See / 1/ and / 17 /, for example,

these steps Ji-s~ necessary with Lemke's algorithm, this is another advantage it possesses over the critical line method. CONCLUS I ON This paper has demonstrated the following: 1. Lemke's algorithm can be used to derive efficient sets. 2. Lemke's algorithm is superior to Markowitz's algorithm in terms of CPU time and cost. 3. The comparison of efficient sets is facilitated when Lemke's algorithm (rather than Markowitz's algorithm) is used to solve for efficient sets derived from the same E(R) vector but different C matrices.

APPENDIX A A Sample Problem There are 5 securities from which the efficient set is to be derived. It has been determined that they have the following expected return vector and variance-covariance matrix: E(R) =.0215 C =.0096.0089.0046.0019.0137.0267.0089.0440.0064.0071.0232.0158.0046.0064.0088.0036.0048.0452.0019.0071.0036.0062.0052 0318.0137.0232.0048.0052.0878 The algorithm proceeds to find the largest and smallest elements in the E(R) vector. These are the 4th and 3rd elements, respectively, and are labelled E and E. Next, the interval between Emax and max min 'max E min is divided by 10 and a uniform grid search is systematically min carried out by continually reducing E =.0452 by.0029 = (1/10) max (E - E. ). The search produces the following points on the max min efficient set: Security Weights E (R) Var(R ) X X1 X X X4.0452.0062 -- -- 1.0000 --.0423.0053.1241.-.8759.0393.0048.2481 - -.7519.0364.0046.2933 --.0635.6431.0343.0046.3016 -:1234.5700 Note that the last value of E is.0343. Here the algorithm originally set E at.0335, but the minimum variance portfolio was found, since set E at.0335, but the minimum variance portfolio was found, since

the optimal solution was greater than.0335. Hence the termination criterion was met (.0343 7.0335) and the search was stopped. The efficient set and the individual securities are shown in Figure 1A. Point A (security 4) denotes the maximum return security and point B denotes the minimum variance portfolio. E(R') p.0450 -.0300 - Efficie t Set B Feasible Set \ 3.0150 4 5 2 --.-. -- -- Var (R ) 200.09250 000 P.0050.0100.0150.0 fVV. v iv. vvv Fig. 1A. The efficient set for the sample problem.

-15 -APPENDIX B The Use of Lemke's Algorithm for 75 and 90 Securities After compiling lemke's algorithm along with the previously * described search procedure for E on the computer, test runs were made using larger number of securities than those mentioned in Table 1. The results are displayed in Table 1A. Table 1A Test Runs of Iemke's Algorithm CPU Total Time Test Run Number Iterations (Seconds) Cost 75 securities: Run 1 400 57.2 $5.74 Run 2 409 61.7 6.41 Run 3 423 62.2 6.20 Run 4 426 61.6 6.41 Run 5 703 98.9 10.07 Run 6 805 112.2 11.38 Average 528 75.6 7.70 90 securities: Run 1 825 167.1 $16.86 Run 2 944 186.9 18.82 Run 3 1150 217.0 21.77 Average 973 190.3 19.15

-16 -The maximum number of points on an efficient set which can be found using the previously described procedure is 11..Eleven points were found for the last two runs with 75 securities and for all three runs with 90 securities. All the other runs involved 10 points. From Table 1A it appears that the total number of iterations performed explains the differing CPU times and costs for a given number of securities.

-17 - REFERENCES 1. Cohen, Kalman J., and Pogue, Jerry E. "An Empirical Evaluation of Alternative Portfolio Selection Models." Journal of Business, April 1967, pp. 166 —93.. 2. Francis, Jack C., and Archer, Stephen H. Portfolio Analysis. Englewood Cliffs, NJ: Prentice-Hall, Inc., 1971. 3. Hogg, Robert V., and Craig, Allen T. Introduction to Mathematical Statistics. 3rd ed. New York: McGraw-Hill, Inc., 1970. 4. Jean, William H.; The Analytical Theory of Finance. New York: Holt, Rinehart and Winston, Inc., 1970. 5. Lemke, C. E. "Bimatrix Equilibrium Points and Mathematical Programming." Management Science, May 1965, pp. 681-89. 6. Markowitz, Harry M. "Portfolio Selection." Journal of Finance, March 1952, pp. 77-91. 7.. "The Optimization of a Quadratic Function Subject to Linear Constraints." Naval Research Logistics Quarterly, MarchJune, 1956, pp. 111-+33.. 8. Martin, A. D. Jr. "Mathematical Programming of Portfolio Selections." Management Science, January 1955, pp. 152 —66.. 9. Mood, Alexander M., and Graybill, Franklin A. Introduction to the Theory of Statistics. 2nd ed. New York: McGraw-Hill, Inc., 1963. 10. Ravindran, Arunachalam "A Computer Routine for Quadratic and Linear Programming Problems." Communications of the ACM, September 1972, pp. 818-20. 11. Sharpe, William F. "A Simplified Model for Portfolio Analysis." Management Science, January 1963, pp. 277- 93.. 12.. "A Linear Programming Algorithm for Mutual Fund Portfolio Selection." Ibid. March 1967, pp. 499-510. 13.. Portfolio Theory and Capital Markets. New York: McGraw-Hill, Inc., 1970. 14.. "A Linear Programming Approximation for the General Portfolio Analysis Problem." Journal of Financial and Quantitative Analysis, December 1971, pp. 1263-75.-.

-18 -15. Stone, Bernell K. "A Linear Programming Formulation of the General Portfolio Selection Problem." Ibid. September 1963, pp. 621-36.. 16. Tsiang, S. C. "The Rationale of the Mean-Standard Deviation Analysis Skewness Preference, and the Demand for Money." American Economic Review, June 1972, pp. 354-71.. 17. Wallingford, Buckner A. "A Survey and Comparison of Portfolio Selection Models." Journal of Financial and Quantitative Analysis, June 1967, pp. 85-106. 18. Wolfe, Philip. "The Simplex Method for Quadratic Programming." Econometrica,July 1959, pp. 382-98..