Research Paper No. 475: // Stanford University
Research Paper No. 475: // Stanford University
Research Paper No. 475: // Stanford University
475
W. F. Sharpe
October 1978
_7~~:2
AN ALGORITHM FOR PORTFOLIO IMPROVENENT
*
W. F. Sharpe
August, 1978
The portfolio selection problem (as described in, e.g. N2, S2) can
be written:
subject to:
N
EX. =1 (lb)
i=l
where:
N
E = E X.E.
11
i=l
N N
V= E EX,X.C..
1=1 j=l 1 3 1.]
*
Timken Professor of Finance, Stanford University. This research was moti-
vated by discussions with members of the Investment Systems Group of Wells
Fargo Investment Advisors. Valuable comments and suggestions were made by
Bob Fuhrman, Kelly Haughton, Cary Martin, Leland Robinson, Polly Shouse,
and Larry Tint. This research was sponsored by the Stanford Program in
Finance. Major contributors to the Stanford Program in Finance are Bank
America Foundation, The First Boston Corporation, The Chase Manhattan Bank,
Continental Bank Foundation, The Dean Witter Foundation, General Electric
Company, Goldman, Sachs & Co., Morgan Guaranty Trust Company, Morgan Stanley
& Co., Inc., Salomon Brothers, Security Pacific National Bank, and Wells
Fargo Bank.
-2-
N,
Z = z - E )Ix.1 - H.
1
t.l
if (2)
1=1
where:
In their natural form, such problems involve a very dense matrix of qua-
dratic coefficients (i.e. most or all of the C.. ‘s are non-zero). More-
13
over, the constraints are extremely simple (e.g. (lb) and (ic)). Finally,
folio.
Previous Approaches
codes (e.g. Ml, RI, R2, Vl) for portfolio problems of modest size (e.g. up
the quadratic portion of the problem to allow the use of algorithms designed
Most security returns are correlated, thus C.. ~10 for the vast majority
data may yield unbiased estimates but such values may still be subject to
algorithm. This suggests the need to employ simplified models of the relation-
ships among security returns to provide useful estimates of the C..’s, even
can meet this need, have been reported (see, e.g. El, Fl, Kl, R3).
-4-
and then to design an algorithm that can efficiently solve the resulting
have been developed (see, e.g. E2, E3, E4, R4, 51, S3, S4).
relationships. Since some of the underlying models (most notably, Sl) are
size the revision problem (as in 2) although our algorithm solves the
(lb) and (ic) are accommodated but, as will be shown, additional aspects
cients in the objective function. We will show that the approach, like
some recent algorithms developed by Elton and Gruber (E2, E3, E4) has
so much so that there can be no doubt that it has occurred to others and
turn covariances suggests that the efficiency with which the approach can
constraints (lb) and (lc). In the rare instance in which the initial
costs.
in one or more of the others. All securities for which X. < U. are candi-
1 1
dates for increased holdings while all securities for which X.1 > L.1 are
amount:
~ ~i ..
-6-
will be obtained by (1) increasing X. for the security among those eli-
gible for an increase that gives the largest value of bZ/ôx. and (2) de-
creasing X. for the security among those eligible for a decrease that gives
the former security is less than or equal to that for the latter, no further
improvement is possible and the optimal portfolio has been found. Otherwise
the portfolio can be improved by changing the holdings of the two securities
while this procedure selects the locally optimal change for each iter-
ation, there remains the issue of the appropriate magnitude for the actual
where:
A Z = the increment in Z
A z = the increment in z
A = the increment in X.
1
-7-
Assume that in the selection phase, security Z has been chosen for in-
creased holdings and security ~ has been chosen for decreased holdings.
Formulas (3) can be utilized tofind the value of A that would maximize
ing bounds and continuity. Then the actual increment is determined by:
X1-.*~~X~ + A
X-~ X -A
The Algorithm
Figure 1
select security t to
be increased and
security ~1to be
decreased
no
Revise Holdings
+ A
-9-
N
S. = E X.C. . (6)
~ ~=l 3 13
These are computed once at the beginning of the procedure, using the entire
covariance matrix, a row at a time. They are revised after each iteration,
but as will be seen, only two rows of the covariance matrix are needed to
Note thai~:
= 2S
ox.1 i
Thus:
=E. - 2AS.
OX. 1 1
1
*
Note that S. = C. the covariance of the return on security i with the
,
- select to maximize.:
E1 - 2AS~ — for X1 H1
oz
Ox1 E; — 2A S~ + t for X; <
- select ~ to minimize:
E~ - 2AS~ - for H
X..4—X; + A
- A
Substituting (6):
if X~< H~
t if X~> H~
T~ =
- if
From (3)
AZ = Az - T1 A + T9 A
*
To maximize A Z, we set 0 (A Z)/O~ to zero, giving:
*
Note also, from (7a) and (7b), that:
Oz
OXL bX~
= 2 A(C22 - 2C~ + C~)
The denominator of (9) will be non-negative in all cases and will equal
zero only if securities Z end ~ are perfectly correlated and have equal
variances. In such a case, the security with the higher expected return
net of transactions costs would dominate the other. This situation can
be determined by checking the denominator of (9) and setting A* at an
appropriately large value if the denominator does in fact equal zero.
The magnitude of the revision is then determined using (5), with values of
Revising Sl,...,SN
sums Sl,...,SN to account for the changed holdings. The values are altered
as follows:
As indicated earlier, only two rows (i and ~) from the original covariance
matrix are required for this step. Moreover, after the initial computation
of Sl,...,SN only this procedure requires any use of the original covariance
matrix.
Extensions
Many problems that arise in practice can be solved directly using this
*
Experience suggests that rounding errors are not very serious with this
algorithm; thus complex procedures to avoid numeric errors are not needed.
However, after many iterations, some errors may cumulate in the values of
the S.’s. To control for this, a count can be kept of the number of itera-
tions1since the initial computation of the sums. When the count exceeds a
specified amount, the sums are recomputed using the original covariance
matrix (i.e. the next iteration simply starts one step earlier than usual).
-13-
described here is used. However, some constraints may well reflect the
Vk = E a.kX. (10)
The restriction:
Vk Uk
= —
(cx if <
where: ~K =j 0 if 1k ~ vk Uk
I.cx’ if vk> uk
While the algorithm described here cannot handle this type of restric-
tion, it can accommodate a penalty function of the form shown in Figure 2b.
-14-
Figure 2a
Uk Vk
Figure 2b
tk Vk
-15—
= Pk(vk - tk)
In many cases this type of quadratic penalty function will better reflect
the reality of the practical problem than will a function of the form shown
in Figure 2a.
K 2
z’ = z - E Pk(vk - rk) . (11)
k=l
2pktkvk + Pktk]
= E - AV - k=l [pkvk -
Substituting (10):
N N N
z’ = E X.E. - A I~ E (X.X.C..)
i=l j=l 1313
N N N
- E ~ E (a. a. p ) X.X.
i=l j=l1=1 ikjkk 13
+ ~ [2 E(a.kpktk)]X.
K 2
- Ep1t
k=l
—16—
Re-arranging:
N ~N N 1 K
2
i=l X.E’
E 1 E E (X.X.C!.) k=1 (p tk)
= - - E (12)
~ i=1 j=l ~ 3 13
where: E! = E. + 2 [k~likPk~]
K
C!.
13 = AC..
13 + E (a.ikjkk
k=l a. p )
Note that the third term in (12) is not a function of the decision variables
(the X.’s). Thus its ommission will not affect the solution. This gives:
~N N
= E X.E! - i~E Z (x.X.C!.)
i=l 1 1 Li=l j=l 1 3 13
need be done only once for all portfolios for which the same set of targets
*
and penalties is applicable.
side of the initial holding, the function is linear. This may well re-
flect the relevant turnover costs for highly liquid stocks. However, for
less liquid securities the total cost (explicit transactions .cost and pos-
3b.
I Xj_HjItj+(Xj_Hi)2t~
the selection procedure (formula (7)) and in the computation of the amount
As before, formulas (7) and (9) are altered to deal with this case. Asym-
metric turnover penalty functions can be used to handle, for example, the
Interactive Use
ceeds until an optimal solution is found, then prints the recommended changes.
A portfolio manager using such a program could either accept the recommenda-
-18-
Figure 3a
Turnover
Penalty
H. X.
1 1
Figure 3b
Turnover
Penalty
H. X~
1 1
-19-
(e.g. the need to hold only integral numbers of shares, preferences for
more) the manager could decide whether or not to accept the buy/sell recom-
manager would be able to alter one or more of the inputs (upper and lower
bounds, turnover penalties, etc.) before any further revisions were analyzed
by the algorithm. -
Since each iteration selects the “best” security for purchase and the
“worst” for sale, and since feasibility is maintained throughout, the pro-
in the process, with actual transactions costs reflected directly from iter-
ation to iteration.
Cost
the initial solution is suboptinml, the size of the problem, and the partic-
*
These factors can only be handled exactly by an (expensive) integer qua-
dratic programming algorithm. However, interactive use and/or the incor-
poration of simple heuristic procedures in the algorithm described here
should prove acceptable.
-20-
Test cases of two sizes were run, using representative estimates for expec-
* **
ted returns and covariances. In each case, the initial portfolio hold-
ings were decidedly suboptimal, so the resulting times and costs were
*
Expected returns were created using representative values based on
securities’ covariances with the overall market plus deviations for
assumed mispricing. The latter deviations were arranged to have a
cross-sectional variance equal to that of estimates produced by Wells
Fargo Investment Advisors for the securities covered by its analysts.
**
The covariance matrix was filled using representative values for the
parameters of a single-index model of the form described in (S2).
While this is an overly simplistic model of covariances, an entire
covariance matrix was created using it, and the optimization proced-
ure used the full matrix. It is unclear whether or not this created
a bias in estimating the relevant cost of solving problems based on
more realistic covariance structures. Since the initial portfolio
involved equal holdings of all securities, the use of the single-
index assumption may have led to longer-than-normal running times,
since many iterations might have been required to obtain a portfolio
with fewer-than-normal holdings.
*.~-*
As indicated, the initial portfolios consisted of equal holdings of
every stock. Since expected returns and covariances were not gener-
ated in a manner that would make such a portfolio particularly desir-
able, considerable revision was required to obtain an optimal solution.
-21-
turnover penalties
increased holdings 17. 17.
decreased holdings 17. 17.
While the costs shown here are far from exhorbitant, in practice the
revise estimates of covariances only quarterly, and the revisions are small.
ted returns) change more frequently, but the changes from month to month
of the relative market values of holdings, will change during the course
*
Based on estimates provided by a time-sharing company. The company in
question bases its charges on both CPU time and disk input and output
operations (both of which were taken into account in the estimates).
Given this pricing structure, the code could undoubtedly be altered
to reduce cost, but no attempt has been made to estimate the amount
that could be saved in this manner. Moreover, no attempt was made
to determine whether other companies’ pricing structures would result
in lower costs for the algorithm as presently programmed.
—22-
over penalties are included in the problem formulation, relatively few iter-
earlier. -
Thus one might reasonably expect costs dramatically lower than those
shown here. However, only extended use by an ongoing organization can pro-
the algorithm.
-23-
References
El. Elton, E.J. and Gruber, N.J., “Estimating the Dependence Structure
E2. Elton, E.J., Gruber, M.J. and Padberg, M.W., “Portfolio Selection
-- The Exploitation of Special Structures,” Bulletin of the Opera-ET1 w386 527 m51
E3. Elton, E.J., Gruber, M.J. and Padberg, M.W., “Simple Criteria for
E4. Elton, E.G., Gruber, N.J. and Padberg, M.W., “Simple Rules for
Kl. King, B.F., “Market and Industry Factors in Stock Price Behavior,”
June 1956.
P1. Pogue, J.A., “An Extension of the Markowitz Portfolio Selection Model
R2. Ravindran, A., “A Computer Routine for Quadratic and Linear Programming
S2. Sharpe, W.F., Portfolio Theory and Capital Markets, McGraw-Hill 1970.