程序代写代做代考 Excel algorithm 1

CHAPTER 4

Portfolio Mean-Variance Optimization

4.1. Portfolio Selection

The fundamental goal of portfolio selection is to optimally allocate investments between different

assets by considering the trade-off between risk and return. In this chapter, we discuss the

implementation of a quantitative tool known as Mean-Variance Optimization (MVO) using the matrix

operation in EXCEL and VBA. Consider a portfolio consisting of n assets with prices { S1 , … , Sn }

and quantities { q1 , … , qn }. If it is to be kept for a period of time, the portfolio value at end of period

will be subjected to uncertain asset price changes { S1 , … , Sn }. The potential gain or loss of the

portfolio in this period can be summed up as

SP  
n

i  1 qi Si (4.1)

The objective of MVO is to determine the optimal portfolio content within a budget so as to minimize

the risk exposure in this period under an expected growth in value. The idea relies on the correlation

among asset price changes under a stochastic regime for which the statistics can be inferred from

historical data.

It is convenient to rewrite equation (4.1) in terms of asset price returns ri  Si /Si over the

investment horizon for which portfolio return rP in this period can be written as a weighted sum of

asset returns in the basket. This gives

rP  
n

i  1 wi ri , 
n

i  1 wi  1 (4.2)

where the weight factor wi represents the fraction of the total portfolio budget that will be invested on

the i-th asset. In the stochastic model, uncertain asset returns in (4.2) can all be considered as random

variables parameterized by historical means and variances. Written as their linear combination,

portfolio return can also be considered as a random variable with mean and variance defined through

(4.2) as

P  
n

i  1 wi i (4.3)

P
2
 

i  1 
n

j  1 wi wj ij (4.4)

where i and i
2
 ii denote respectively the mean and variance of individual asset return ri , and ij

for i  j denotes the covariance between two different returns ri and rj. Under this framework, the task

of MVO is to determine the optimal portfolio content that minimizes the random variation of the

portfolio return in (4.4) given an expected return in (4.3) and should also be feasible under the

portfolio budget. The variance terms wi
2 i

2
in (4.4) are strictly positive and they are adding up. The

idea of MVO relies on the fact that the covariance terms wi wj ij could possibly be negative and thus

diversify the total portfolio variance.

It is efficient to express equations (4.3) and (4.4) in matrix multiplication and formulate MVO as

the determination of the column vector w that

minimize P
2
 w

T
 w (4.5)

subject to w
T
  P and u

T
w  1

where

1
2
12 … 1n

w1 1  21 2
2
… 2n

w   ,    , u   ,    
wn n   

n1 n2 … n
2

The entries in the mean vector  and the variance-covariance matrix  can presumably be estimated

using historical asset returns over the same horizon as the portfolio. The optimization in (4.5) allows

both long and short positions for which wi can be positive or negative. It can be solved very easily

using the method of Lagrange multipliers and the optimal solution was first worked out by Merton1 as

(4.6)

(4.7)

where A  u
T
1  , B  

T
1  , and C  u

T
1 u. Since the variance-covariance matrix  is

symmetric, it can be shown that the two quadratic forms, B and C, and the denominator BC  A2 are

all positive. The optimal portfolio mean-variance relation in (4.7) is then strictly convex as shown in

Figure 4.1(a). It is usual to invert (4.7) and present the risk-adverse domain ( P  A/C ) of the mean-

variance relation in term of the so-called portfolio efficient frontier as shown in Figure 4.1(b) with the

following optimal relation.

(4.8)

Figure 4.1: (a) Optimal portfolio mean-variance relation with risky assets only, and (b) Portfolio

efficient frontier.

1 See Robert C. Merton, “An analytic deviation of the efficient portfolio frontier”, Journal of Financial and

Quantitative Analysis, Vol. 7, No. 3 (1972) p1851-1872. We first define the Lagrange function L that

incorporates the objective function and the constraints in (4.5) with two multipliers 1 and 2 as

L  ½ wT  w  1 ( w
T   P )  2 ( u

T w  1 )

The optimal w can be determined through the first order stationary conditions : { L/w1  0, … , L/wn  0 }

in conjunction with the original constraints.

CP
2
 2AP  B

BC  A2
P

2


P   (BC  A
2)(CP

2
 1)

C
1

(a) P
2

P

Risk-adverse

A/C

1/C

1/√C

A/C

(b)

P

P
Efficient frontier

( CP  A )(
1 )  ( B  AP )(

1 u)

BC  A2
w 

The above discussion analyzes the case in which all the available assets are risky. We can extend

the analysis to include risk-free cash that provides a guaranteed return 0 over the investment period.

Consider w0 to be the fraction of the total portfolio budget that will be held as cash. Reformulate the

MVO in (4.5) as the determination of the column vector w and w0 that

minimize P
2
 w

T
 w (4.9)

subject to w
T
  w0 0  P and u

T
w  w0  1

Again, it can be solved very easily using the method of Lagrange multipliers2 and the optimal

portfolio content is given by

(4.10)

that generates the efficient frontier as shown in Figure (4.2) with the following linear optimal

relation3.

(4.11)

Figure 4.2: Efficient frontier of a portfolio with cash and risky assets.

We have considered so far MVO that allows both long and short positions on the risky assets for

which wi can be positive or negative. Suppose there are short-selling restrictions on the risky assets

due to market constraint or internal policy. In such long-only portfolio, the asset positions wi are all

limited to be non-negative in the optimization. Accordingly, the MVO in (4.9) should be appended

with additional constraints as

minimize P
2
 w

T
 w (4.12)

subject to w
T
  w0 0  P , u

T
w  w0  1 , and w1 , … , wn  0

2 Similarly, we can define the Lagrange function L with two multipliers 1 and 2 as

L  ½ wT  w  1 ( w
T   w0 0  P )  2 ( u

T w  w0  1 )

The optimal w and w0 can be determined through the stationary conditions : { L/w0  0, L/w1  0, … ,

L/wn  0 }.
3 We can rewrite the optimal risky content in (4.10) as w  (1  w0) ŵ where ŵ  ( 

1  0 
1u )/(A  0C).

Along the efficient frontier, we are actually buying or short-selling various units of the so-called market

portfolio { ŵ1, … , ŵn } together with cash holding. For 0  A/C , the cash position w0 can be positive, zero, or

negative through borrowing. For 0  A/C, the cash position is however strictly positive.

P  0  P  C0
2
 2A0  B

0

P

P

Efficient frontier

w0  1 
( P  0 )( A  0 C )

C0
2
 2A0  B

w 
( P  0 )( 

1  0 
1u )

C0
2
 2A0  B

It should be noted that the cash position w0 remains unconstrained in (4.12) where it can be positive,

zero, or negative. In principle, (4.12) can be solved using again the method of Lagrange multipliers4.

However, the evaluation of the optimal portfolio content would be non-trivial because of the

inequality constraints in the Kuhn-Tucker conditions.

Markowitz has developed an efficient algorithm5 that allows us to solve the MVO in (4.12) using

simply the optimal result in (4.10). Consider another MVO related to (4.12) for which we delete the

non-negative constraints w1, 2, … , n  0 and instead constrain certain subset of { w1, … , wn }, called the

OUT subset, to be zero. The basic idea in the Markowitz algorithm is that the optimal solution of this

related problem could possibly be a particular solution of the original problem for specific segment of

the efficient frontier. The optimal solution can simply be obtained from (4.10) by modifying the array

entries in {  ,  , u } associated with the OUT subset. If wi is in the OUT subset, we set the i-th row of

both the vectors  and u to zero, and also the i-th row and i-th column of the matrix  to zero except

the diagonal entry which set to be one.

i  0 , ui  0 (4.13)

i1 , … , in  0 , 1i , … , ni  0 , except ii  1

Suppose { m , m , um } are the modified arrays according to the OUT subset. The optimal solution of

the related problem is then given by

(4.14)

with multipliers

where Am  um
T
m

1 m , Bm  m
T
m

1 m , and Cm  um
T
m

1 um . It is clear in (4.14) that wi  0 inside the

OUT subset. If all wi outside the OUT subset are non-negative for particular value of P, (4.14) could

possibly be a solution of the MVO in (4.12) that also satisfies the Kuhn-Tucker conditions as

L/w0   1 0  2  0 (4.15)

L/wi  ( w  1   2 u)i  0 when wi  0 (4.16)

 0 when wi  0 , for i  1, … , n

4 Define the Lagrange function H with multipliers { 1 , 2 , 1 , … , n } as

H  L  1 w1  …  n wn , where L  ½ w
T  w  1 ( w

T   w0 0  P )  2 ( u
T w  w0  1 )

With inequality constraints, the optimal w and w0 can be determined through the Kuhn-Tucker conditions :

L/w0  0 , L/wi  i , i  0 , wi  0 , and i wi  0 for i  1, … , n

that can be rewritten as L/w0  0 , L/wi  0 when wi  0 , and L/wi  0 when wi  0 for i  1, … , n.

5 See H.M. Markowitz, G.P. Todd, and W.F. Sharpe, Mean-Variance Analysis in Portfolio Choice and Capital

Markets, Frank J. Fabozzi Associates, 1987.

, w0  1 
( P  0 )( Am  0 Cm )

Cm 0
2
 2Am 0  Bm

w 
( P  0 )( m

1m  0 m
1um )

Cm 0
2
 2Am 0  Bm

, 1 
( P  0 )

Cm 0
2
 2Am 0  Bm

2 
 0 ( P  0 )

Cm 0
2
 2Am 0  Bm

It should be noted that L/w0  0 in (4.15) would automatically be satisfied with the multipliers

defined in (4.14). Given portfolio return P  0 , we can determine the optimal portfolio content by

solving the MVO in (4.12) through the Markowitz algorithm as

(1) Define an OUT subset and construct the modified arrays { m , m , um } according to (4.13).

(2) Check that all the entries of w in (4.14) are non-negative. If so, proceed to step (3). If this is not

the case, return to step (1) and try another OUT subset.

(3) Check that condition (4.16) has been satisfied. If so, w0 and w defined in (4.14) will be an optimal

solution given portfolio return P. Otherwise, return to step (1) and try another OUT subset.

In step (1), the size of the OUT subset can be chosen from Nout  0 to Nout  n  1. When Nout  n,

there is only one OUT subset namely the entire risky content { w1, … , wn }. The algorithm will not

work as well in this case as the denominator in (4.14) vanishes with m and um being zero vectors.

However, this corresponds to the trivial portfolio content with w  0 and w0  1. The algorithm will

guarantee to find a solution before we exhaust the list of all OUT subsets. Also, the optimal portfolio

content is unique given return. We should quit the routine once we obtain a solution.

4.2. EXCEL Implementation

It is always convenient to separate the raw data from the actual calculations using different

worksheets defined as6

dayclose  Historical daily closing prices of all risky assets to be considered.

return  Historical price returns generated through “dayclose” for specific time horizon.

MVO  Actual calculations of the mean-variance optimization based on “return”.

Figure 4.3 depicts the layout of the worksheet “dayclose” with historical daily closing prices of 35

commonly traded commodities from year 1998 to 2005. Sequences of closing prices are recorded one

column per asset starting from column B onward with the corresponding timestamp given by column

A. In each column, the top cell records the asset name with its ticker symbol in the following cell. For

example, column B records the daily closing prices of Crude Oil with ticker symbol being CL.

Figure 4.3: The layout of the worksheet “dayclose” with daily closing prices.

Figure 4.4 displays the worksheet “return” that contains the historical price returns of the assets.

They are generated dynamically using the raw data in “dayclose” and according to the investment

horizon defined in cell K16 (named as horizon) of worksheet “MVO”. Again, return sequences are

6 Refer to mean_variance_opt.xls.

arranged one column per asset starting from column A onward with the corresponding ticker symbol

defined in the top cell. Such labeling row can be constructed through a direct mapping from

“dayclose” using the common expression A1  dayclose!B2 along the row. The investment horizon

should be defined in number of days. Suppose, for example, it is taken to be five days (horizon  5).

The cell A2 should correspond to the price return of CL with opening price dayclose!B3 and closing

price dayclose!B8 five days later. In the same way, the following cell A3 should correspond to the

price return from dayclose!B8 to dayclose!B13 in the subsequent five days. In general, this can be

done very easily using the OFFSET function with the leftmost corner cell dayclose!$A$3 being the

reference location in worksheet “dayclose”. In each column of worksheet “return”, price returns in

each cell can be calculated by identifying the opening and closing prices through row offset from the

reference location according to its row number ROW() as

opening price  OFFSET( dayclose!$A$3, ( ROW()  2 )  horizon , COLUMN() )

closing price  OFFSET( dayclose!$A$3, ( ROW()  1 )  horizon , COLUMN() )

price return  ( closing price  opening price ) / opening price

The column number COLUMN() will provide a column offset from the reference location to match

up the ticker symbol in the two worksheets. Running down the row of “return”, price returns should

be calculated until the location of the closing price has exceeded the data range of “dayclose”. It

happens when closing price is pointing to a blank cell thereafter, and where we simply insert a blank

cell in “return”. The following expression can be applied to every columns of “return” with ticker

symbol:

IF( OFFSET( dayclose!$A$3, ( ROW()  1 )  horizon , COLUMN() )  “” , “” ,

( OFFSET( dayclose!$A$3, ( ROW()  1 )  horizon , COLUMN() )

 OFFSET( dayclose!$A$3, ( ROW()  2 )  horizon , COLUMN() ) )

/ OFFSET( dayclose!$A$3, ( ROW()  2 )  horizon , COLUMN() ) )

Figure 4.4: The layout of the worksheet “return” with price returns over specific investment horizon.

In worksheet “MVO”, we first construct the variance-covariance matrix  using the asset price

returns in “return”. Figure 4.5 depicts the layout of the matrix with user-defined portfolio contents. As

shown in the figure, the number of assets to be included in the portfolio is arbitrary with the maximum

size limited to ten. The choice of asset can be specified through the cells J3:S3 by entering their ticker

symbols. The total number of assets in the portfolio is given by K15  COUNTA( J3:S3 ) that counts

the number of non-empty cells in this array. The adjacent cells J4:S4 will identify the corresponding

column location of data in worksheet “return” to facilitate calculation of the matrix. For an unused

blank cell in J3:S3, the adjacent cell will also be blank in J4:S4. The following expression can be used

to define J4 and apply to all other cells in J4:S4 :

J4  IF( J3  “” , “” , MATCH( J3 , return!1:1 , 0 ) )

In Figure 4.5, the ticker symbol of J3 is defined as HG, the above function will search for this item in

array return!1:1 ( row 1 of “return”) and report in J4 its relative position (the sixth column) in this

array. We can use the column locations acquired in cells J4:S4 to construct the variance-covariance

matrix defined in cells J5:S14 (named as vcmatrix). We first repeat the same sequence vertically in

cells I5:I14 based on the common expression I5  IF( J4  “” , “” , J4 ). Thus, each matrix entry ij

will associate with the target column locations of two assets reading off from I5:I14 ( for i  1, 2, … )

and J4:S4 ( for j  1, 2, … ). For example, the entry in J5 has target locations given by I5 and J4. The

corresponding return data to be included in the covariance calculation can be identified using the

OFFSET function with the cell return!$A$2 in leftmost column of “return” being the reference

location.

COVAR( OFFSET( return!$A$2 , 0 , $I5  1 , nsample ) ,

OFFSET( return!$A$2 , 0 , J$4  1 , nsample ) ) (4.17)

For both target locations, the row and column offsets from the reference location aim at the leading

entry of the data set, the height parameter (named as nsample) then defines the downward range to be

included in the calculation. The height parameter is simply the size of the return data given an

investment horizon. It is defined in N16  COUNT( return!A:A ) by counting the number of numeric

cells in column A of “return”. If there are blank cells in J4:S4 (and so I5:I14), the variance-covariance

matrix will have redundant columns (and rows) relative to the unused cells. With respect to such

redundancy, the matrix should be augmented with zero columns (and zero rows) except an one at

diagonal entries. We can use the following formula to define J5 and all other matrix entries:

J5  IF( OR( $I5  “” , J$4  “” ) ,

IF( ROW()  ROW( $J$5 )  COLUMN()  COLUMN( $J$5 ) , 1 , 0 ) ,

COVAR( OFFSET( return!$A$2 , 0 , $I5  1 , nsample ) ,

OFFSET( return!$A$2 , 0 , J$4  1 , nsample ) ) )

Figure 4.5: The layout of the variance-covariance matrix in worksheet “MVO”.

As shown in Figure 4.6, the mean vector  is defined in C5:C14 (named as mvec) of worksheet

“MVO”. Similar to (4.17), it can be constructed with reference to the target locations given by I5:I14.

For example, the mean return in C5 can be calculated according to the target location in I5 as

AVERAGE( OFFSET( return!$A$2 , 0 , $I5  1 , nsample ) )

Again, the mean vector will have zero redundant entries if there are blank cells in I5:I14. This is also

true for the u vector defined in B5:B14 (named as uvec). The following expressions can be used to

define the mean vector and the u vector, respectively, as

C5  IF( $I5  “” , 0 , AVERAGE( OFFSET( return!$A$2 , 0 , $I5  1 , nsample ) ) )

B5  IF( $I5  “” , 0 , 1 )

Figure 4.6: The layout of the optimal output in worksheet “MVO”.

Consider first the MVO problem in (4.5) that allows both long and short positions in risky assets.

As shown in Figure 4.5, we have evaluated the factors A, B, and C in cells K17 (named as Avalue),

K18 (named as Bvalue), and K19 (named as Cvalue), respectively, through EXCEL matrix operations

K17 = MMULT( TRANSPOSE( uvec ) , MMULT( MINVERSE( vcmatrix ) , mvec ) )

K18 = MMULT( TRANSPOSE( mvec ) , MMULT( MINVERSE( vcmatrix ) , mvec ) )

K19 = MMULT( TRANSPOSE( uvec ) , MMULT( MINVERSE( vcmatrix ) , uvec ) )

In Figure 4.6, the expected portfolio return P is defined in D18 (named as mport) by scaling the

choice of daily rate in C18 with the investment horizon as D18  C18horizon. The optimal portfolio

content w in (4.6) can be determined in cells D5:D14 using the formula

{ D5:D14  ( ( Cvalue  mport  Avalue )  MMULT( MINVERSE( vcmatrix ) , mvec )

 ( Bvalue  Avalue  mport )  MMULT( MINVERSE( vcmatrix ) , uvec ) )

/ ( Bvalue  Cvalue  Avalue^2 ) }

The minimized portfolio variance P
2
can be calculated in D19 based on the optimal content as

D19  MMULT( TRANSPOSE( D5:D14 ) , MMULT( vcmatrix , D5:D14 ) )

Consider the MVO problem in (4.9) with the inclusion of cash. In Figure 4.6, the risk-free return

0 is defined in D17  C17horizon (named as riskfree) by scaling the daily rate in C17. The optimal

portfolio content w and cash w0 in (4.10) can be determined in cells E5:E14 and E15, respectively,

using the formula

{ E5:E14  ( mport  riskfree )  ( MMULT( MINVERSE( vcmatrix ) , mvec )

 riskfree  MMULT( MINVERSE( vcmatrix ) , uvec ) )

/ ( Cvalue  riskfree^2  2  Avalue  riskfree  Bvalue ) }

E15  1  ( mport  riskfree )  ( Avalue  riskfree  Cvalue )

/ ( Cvalue  riskfree^2  2  Avalue  riskfree  Bvalue )

As before, the minimized portfolio variance can also be calculated in E19 based on the optimal

content.

Consider now the MVO problem in (4.12) with short-selling restrictions on risky assets. We defer

our discussion on the implementation of the Markowitz algorithm to section 4.3 with the use of VBA.

Here, we consider solving this problem using EXCEL SOLVER despite there are critical issues on

initializing the algorithm. In Figure 4.6, the portfolio content w to be optimized is defined in cells

G5:G14. The corresponding cash position w0 in G15 can be related to this content through the budget

constraint w0  1  u
T
w in (4.12) as

G15  1  MMULT( TRANSPOSE( uvec ) , G5:G14 )

In G18 and G19, we explicitly evaluate the expected return w
T
  w0 0 and variance w

T
 w of the

portfolio, respectively, relative to this content as

G18  MMULT( TRANSPOSE( G5:G14 ) , mvec )  G15  riskfree

G19  MMULT( TRANSPOSE( G5:G14 ) , MMULT( vcmatrix , G5:G14 ) )

In the Solver Parameters screen as shown in Figure 4.7, we set the Target Cells to be the portfolio

variance in G19 and check Equal To as Min for minimizing. We take in the By Changing Cells the

portfolio content in cells G5:G14 and include in the Subject to the Constraints field the condition

that the so-evaluated portfolio return in G18 must equal the prescribed value mport in D18. In the

Solver Options screen as shown in Figure 4.8, we check Assume Non-Negative that imposes the

non-negative constraints in (4.12) on the portfolio content specified in the By Changing Cells. It is

sufficient to consider in Precision the required precision of 108 for the algorithm and limits the

number of iterations within 20. To start off the search algorithm, we need to provide initial values for

G5:G14 as close to the solution as possible. A proper choice would be a cash portfolio with no risky

assets { w1  0, … , wn  0 }. However, there is no guarantee of finding the correct optimal solution.

Figure 4.7: Solver Parameters screen.

Figure 4.8: Solver Options screen.

4.3. EXCEL Plus VBA Implementation

An effective and reliable way to solve the MVO problem in (4.12) is to implement the Markowitz

algorithm as discussed in section 4.1 using VBA. It will guarantee to find the correct optimal solution

that is unique given portfolio return. The idea is to examine all possible OUT subsets and identify the

particular case that generates the optimal solution of the original problem. The size of the OUT subset

can run from Nout  0 to Nout  n  1. For each Nout , there are Nc ( equals n choose Nout ) OUT subsets

with different combinations:

Nout OUT subsets Nc

0 {  } 1

1 { w1 }, { w2 }, … , { wn } n

2 { w1 , w2 }, { w1 , w3 }, … , { w1 , wn }, { w2 , w3 }, … , { w2 , wn }, … , { wn  1 , wn } ½n(n  1)



n  1 { w2 , w3 , … , wn }, { w1 , w3 , … , wn }, … , { w1 , w2 , … , wn  1 } n

Among all possible OUT subsets above, there is a unique combination for which the corresponding

optimal content w given by (4.14) will be non-negative and satisfies the Kuhn-Tucker conditions in

(4.16).

We first develop a routine called GetOutSubset( ) capable of generating all OUT subsets given its

size Nout  k. Consider the array Ik( L, 1: k ) that provides in ascending order the pointers to all

elements in different OUT subsets labeling through L  1, …, Nc(k). When k  2, for example, we

have I2( 1, 1 )  1 and I2( 1, 2 )  2 that define the first OUT subset { w1 , w2 }. Pointer arrays of size k

can be generated by appending every pointer array of size k  1 with an additional entry of higher

value. Given pointer array Ik  1( l, 1: k  1 ) of size k 1, we can generate several pointer arrays of

size k (labeled consecutively as L  l, l  1, …); each with additional entry of separate value greater

than the last entry in the given array:

h …

Ik  1( l, 1: k  1 ) h  1



Ik( l, 1: k )

h  2



Ik( l + 1, 1: k )

In this way, the entire set of pointer arrays Ik( L, 1: k ) for L  1, …, Nc(k) can be generated iteratively

by considering every Ik  1( L, 1: k  1 ) for L  1, …, Nc(k  1). The pseudo code of GetOutSubset( )

is given by Code 4.1 which performs such tasks. As input, the routine reads in all pointer arrays for

size k 1 and the number of combinations. As output, it generates the arrays for size k and updates the

number of combinations. The iteration should start off from k  1 with Nc(1)  n pointer arrays,

namely, I1( 1, 1 )  1, I1( 2, 1 )  2, … , and I1( n, 1 )  n. The VBA code of GetOutSubset( ) is given

by Code 4.2. Note that “nmax” and “Ncmax” are parameters that configure the maximum possible

size of n and Nc, respectively, in the module. In worksheet “MVO”, the number of assets to be

included in the portfolio is limited below ten. We should set nmax  10, and the maximum number of

OUT subsets should correspondingly be Ncmax  252 (10 choose 5).

__________________________________________________________________________________

GetOutSubset( n , k , Nc , I( 1 : Nc , 1 : k ) )

l  0

# input Nc and I for size k  1, and consider every input array

For( L  1 to Nc ) {

# for particular array I, generate several Inew for size k with consecutive labeling

For( j  I( L, k  1 )  1 to n ) { l = l  1
For( i = 1 to k  1 ){ Inew( l, i )  I( L, i ) }

Inew( l, k )  j }

}

# return Inew as I and update Nc

For( L  1 to l ) { For( i  1 to k ){ I( L , i )  Inew( L , i ) } }
Nc  l

__________________________________________________________________________________

Code 4.1: Pseudo code of the GetOutSubset( ) routine.

__________________________________________________________________________________

Sub GetOutSubset(n As Integer, k As Integer, ByRef Nc As Integer, ByRef Iout() As Integer)
Dim lcount As Integer, L As Integer, Lprime As Integer

Dim i As Integer, j As Integer

Dim Inew(1 To Ncmax, 1 To nmax) As Integer

lcount = 0

For Lprime = 1 To Nc
For j = Iout(Lprime, k – 1) + 1 To n

lcount = lcount + 1

For i = 1 To k – 1
Inew(lcount, i) = Iout(Lprime, i)

Next i

Inew(lcount, k) = j

Next j

Next Lprime

For L = 1 To lcount

For i = 1 To k
Iout(L, i) = Inew(L, i)

Next i

Next L

Nc = lcount

End Sub

__________________________________________________________________________________

Code 4.2: VBA code of the GetOutSubset( ) routine.

We now want to develop a routine called Markowitz( ) that considers every OUT subset generated

from GetOutSubset( ) and performs the checking in steps 1-3 as stated at end of section 4.1. The

pseudo code of Markowitz( ) is given by Code 4.3. As input, it reads in the total number of risky

assets n, the data arrays {  ,  , u }, the expected portfolio return P, and the risk-free return 0. As

output, it returns the optimal portfolio content w and cash position w0. To examine all possible OUT

subsets, we have considered in the outer loop the values of Nout from 0 to n  1. For each Nout, we

generate the entire OUT subsets and perform the checking on every combination in the inner loop of

L. The checking will proceed to higher values of Nout until an optimal solution has been identified

where the procedure will be stopped immediately.

For Nout  0, there is Nc(0)  1 OUT subset {  } with no modification on the entries in {  ,  , u }.

For Nout  1, the OUT subsets are generated iteratively through GetOutSubset( ) starting off from Nout

 1 with Nc(1)  n subsets as defined above. For each OUT subset, the modified arrays { m , m , um }

will be constructed according to the generated pointer array, and the portfolio content defined in

(4.14) will also be calculated. The checking of non-negative and Kuhn-Tucker conditions for such

portfolio content will subsequently be conducted.

It should be noted that the denominator Dm  Cm 0
2
 2Am 0  Bm in (4.14) is strictly positive.

However, it could possibly be negative due to floating point precision that renders the sign of (4.14) to

be misidentified. Under double precision, a real number will only be quoted up to 15 decimal places,

it is therefore essential to adjust the denominator by a floating precision of   1014. The same factor

should also be used in checking whether a real number x is negative (x  ), positive (x  ), or zero

(|x|  ). Using the first “Next L”, we skip those OUT subsets with negative portfolio content in (4.14)

if wi   for either one component of w. Then, for the Kuhn-Tucker conditions in (4.16), we skip

again using the second “Next L” if neither ( i   )  ( |wi|   ) or ( |i|   )  ( wi   ) is true ( i.e.

testflag  .False.) for either one component of w and   ( w  1   2 u). It runs through all L and

proceeds to higher values of Nout. If an OUT subset has not been filtered out by these two exit

conditions, the corresponding portfolio content in (4.14) will be the optimal solution of the MVO in

(4.12). The entire procedure will be stopped immediately by “Exit Nout” that exits two nested loops.

__________________________________________________________________________________

Markowitz( n , (1 : n ) , u(1 : n) , (1 : n , 1 : n ) , P , 0 , w(1 : n) , w0 )

  1  1014

For ( Nout  0 to n  1 ) {

# generate the OUT subsets

If( Nout  0 ) then

Nc  1

elseif( Nout  1) then

Nc  n

For ( L  1 to Nc ) { I( L , 1 )  L }
else

Call GetOutSubset( n , Nout , Nc , I( 1 : Nc , 1 : Nout ) )

endif

For ( L  1 to Nc ) {

# construct the modified arrays according to (4.13)

For ( i  1 to n ) { m( i )  ( i ) , um( i )  u( i )

For ( j  1 to n ) do{ m( i , j )  ( i , j ) } }

For ( k  1 to Nout ) { i  I( L , k )
m( i )  0 , um( i )  0

For ( j  1 to n ) { m( i , j )  0 , m( j , i )  0 }

m( i , i )  1 }

# calculate Am, Bm, and Cm

Am  u
T
m( 1 : n ) m

1( 1 : n , 1 : n ) m( 1 : n )
Bm  

T
m( 1 : n ) m

1( 1 : n , 1 : n ) m( 1 : n )
Cm  u

T
m( 1 : n ) m

1( 1 : n , 1 : n ) um( 1 : n )

# calculate the portfolio content defined in (4.14)

Dm  Cm 0
2
 2Am 0  Bm  

1  ( P  0 ) / Dm , 2   0 ( P  0 ) / Dm

w( 1 : n )  1 m
1( 1 : n , 1 : n ) m( 1 : n )  2 m

1( 1 : n , 1 : n )  um( 1 : n )
w0  1  1 ( Am  0 Cm )

# check that all the entries of w in (4.14) are non-negative

For ( i  1 to n ) { If( w( i )   ) { Next L } }

# check that the KKT condition (4.16) has been satisfied

( 1 : n )  ( 1 : n , 1 : n ) w( 1 : n )  1 ( 1 : n )  2 u( 1 : n )

For ( i  1 to n ) { testFlag  OR( AND( ABS( ( i ) )   , w( i )   ) ,
AND( ( i )   , ABS( w( i ) )   ) )

If ( .NOT. testFlag ) { Next L } }
Exit Nout

} }
__________________________________________________________________________________

Code 4.3: Pseudo code of the Markowitz( ) routine.

The VBA code of Markowitz( ) is given by Code 4.4. For the calculations of Am, Bm and Cm , we

have used the routine SolveAxb( ) (see Code 3.4) to first calculate the vectors m
1m and m

1um. The

matrix multiplications with the transposed vectors u
T
m and 

T
m can then be performed very easily

through the rule x
T
y  

n
i  1 xi yi for two (n  1) vectors. In addition, the portfolio content w in (4.14)

can also be calculated immediately using the same results. Notice that the vector   L/w in (4.16)

has been determined by directly applying the rule for matrix multiplication and addition as

i  
n

k  1 ik wk  1 i  2 ui , for i  1, 2, …, n

To exit a nested loop during the checking of non-negative w and the KKT condition, we use “GoTo

nextL” and label the “Next L” statement in the coding as “nextL”. To terminate the entire procedure

once the optimal solution has been found, we exit two nested loops using “GoTo exitNout” for which

we label the line immediately after “Next Nout” as “exitNout”.

We will use the same spreadsheet design in Figures 4.5 and 4.6 for this VBA implementation. The

main VBA routine MVO( ) can be invoked through the “Markowitz” button in the spreadsheet as

shown in Figure 4.6. In Code 4.5, we have divided the MVO( ) routine into three parts handling the

data input, the core Markowitz algorithm, and the output. As input, it reads in the total number of

risky assets n in cell K15, the expected portfolio return P in cell D18, and the risk-free return 0 in

cell D17. It also reads in the data arrays {  ,  , u } according to the size of n with the use of the

OFFSET function relative to the cells J5, C5, and B5, respectively. As output, it returns the optimal

portfolio content and cash position that display in cells F5:F14 and F15, respectively. It should be

noted that if n is less than nmax  10, the additional portfolio contents in F5:F14 will always be zero

in the output.

__________________________________________________________________________________

Sub Markowitz(n As Integer, mvec() As Double, uvec() As Double, vcmatrix() As Double, mport As Double, _

riskfree As Double, ByRef wvec() As Double, ByRef w0 As Double)

Dim Nout As Integer, Nc As Integer

Dim Iout(1 To Ncmax, 1 To nmax) As Integer
Dim L As Integer, i As Integer, j As Integer, k As Integer

Dim mvecm(1 To nmax) As Double

Dim uvecm(1 To nmax) As Double

Dim vcmatrixm(1 To nmax, 1 To nmax) As Double
Dim etavec(1 To nmax) As Double

Dim tempvec1(1 To nmax) As Double

Dim tempvec2(1 To nmax) As Double

Dim Am As Double, Bm As Double, Cm As Double, Dm As Double

Dim lambda1 As Double, lambda2 As Double
Dim testFlag As Boolean

For Nout = 0 To n – 1

‘generate the OUT subsets

If (Nout = 0) Then
Nc = 1

ElseIf (Nout = 1) Then

Nc = n
For L = 1 To Nc: Iout(L, 1) = L: Next L

Else

Call GetOutSubset(n, Nout, Nc, Iout)
End If

For L = 1 To Nc
‘construct the modified arrays

For i = 1 To n

mvecm(i) = mvec(i)
uvecm(i) = uvec(i)

For j = 1 To n: vcmatrixm(i, j) = vcmatrix(i, j): Next j

Next i

For k = 1 To Nout

i = Iout(L, k)
mvecm(i) = 0

uvecm(i) = 0

For j = 1 To n
vcmatrixm(i, j) = 0

vcmatrixm(j, i) = 0

Next j
vcmatrixm(i, i) = 1

Next k

‘calculate Am, Bm, and Cm

Call SolveAxb(vcmatrixm, mvecm, tempvec1, n, 1, 1, 1)

Call SolveAxb(vcmatrixm, uvecm, tempvec2, n, 1, 1, 1)

Am = 0

Bm = 0

Cm = 0
For i = 1 To n

Am = Am + uvecm(i) * tempvec1(i)

Bm = Bm + mvecm(i) * tempvec1(i)
Cm = Cm + uvecm(i) * tempvec2(i)

Next i

‘calculate the portfolio content

Dm = Cm * riskfree ^ 2 – 2 * Am * riskfree + Bm + eps
lambda1 = (mport – riskfree) / Dm

lambda2 = -riskfree * (mport – riskfree) / Dm

For i = 1 To n: wvec(i) = lambda1 * tempvec1(i) + lambda2 * tempvec2(i): Next i

w0 = 1 – lambda1 * (Am – riskfree * Cm)

‘check that the portfolio content are non-negative

For i = 1 To n

If (wvec(i) < -eps) Then GoTo nextL Next i 'checking the KKT condition For i = 1 To n tempvec1(i) = 0 For j = 1 To n: tempvec1(i) = tempvec1(i) + vcmatrix(i, j) * wvec(j): Next j etavec(i) = tempvec1(i) - lambda1 * mvec(i) - lambda2 * uvec(i) Next i For i = 1 To n testFlag = (Abs(etavec(i)) <= eps And wvec(i) >= – eps) Or (etavec(i) > eps And Abs(wvec(i) <= eps)) If (Not testFlag) Then GoTo nextL Next i GoTo exitNout nextL: Next L Next Nout exitNout: End Sub __________________________________________________________________________________ Code 4.4: VBA code of the Markowitz( ) routine. __________________________________________________________________________________ Option Explicit Private Const nmax = 10, Ncmax = 252 Private Const eps = 1 * 10 ^ -14 _____________________________________________________________________________________________________________ Sub MVO() Dim n As Integer Dim mvec(1 To nmax) As Double Dim uvec(1 To nmax) As Double Dim vcmatrix(1 To nmax, 1 To nmax) As Double Dim mport As Double Dim riskfree As Double Dim wvec(1 To nmax) As Double Dim w0 As Double Dim i As Integer, j As Integer n = Range("K15").Value mport = Range("D18").Value riskfree = Range("D17").Value For i = 1 To n mvec(i) = Range("C5").Offset(i - 1) uvec(i) = Range("B5").Offset(i - 1) For j = 1 To n: vcmatrix(i, j) = Range("J5").Offset(j - 1, i - 1): Next j Next i Call Markowitz(n, mvec, uvec, vcmatrix, mport, riskfree, wvec, w0) For i = 1 To nmax: Range("F5").Offset(i - 1) = wvec(i): Next i Range("F15").Value = w0 End Sub __________________________________________________________________________________ Code 4.5: VBA code of the MVO( ) routine.

Related Posts