Portfolios and linear programming 1

Toy Model

Various stocks with rewards and risks on a scale of 0-3 (0 low risk, 3 high risk) are shown below.

Stock Name	Reward	Risk
AAA	15%	3
BBB	12%	2
CCC	4%	0.5

Decision Variables

$x_{1}={\text{fraction of portfolio invested in AAA}}$

$x_{2}={\text{fraction of portfolio invested in BBB}}$

$x_{3}={\text{fraction of portfolio invested in CCC}}$

Optimization Function

$z=15x_{1}+12x_{2}+4x_{3}$

Constraints

$3x_{1}+2x_{2}+{\dfrac {1}{2}}x_{3}\leq \sigma$

$\sigma ={\text{maximum risk}}$

$x_{2}-x_{3}\leq 0\;{\text{ (invest at least one dollar in CCC for every dollar invested in BBB)}}$

$x_{1}+x_{2}+x_{3}\leq 1$

$-x_{1}-x_{2}-x_{3}\leq -1$

$x_{1},x_{2},x_{3}\geq 0$

Slack Variables

$x_{4}=\sigma -3x_{1}-2x_{2}-{\dfrac {1}{2}}x_{3}$

$x_{5}=-x_{2}+x_{3}$

$x_{6}=1-x_{1}-x_{2}-x_{3}$

$x_{7}=-1+x_{1}+x_{2}+x_{3}$

$x_{4},x_{5},x_{6},x_{7}\geq 0$

Worked Solution

${\text{Let}}\;\sigma ={\dfrac {3}{2}}$

${\begin{aligned}x_{4}&={\dfrac {3}{2}}-3x_{1}-2x_{2}-{\dfrac {1}{2}}x_{3}\\x_{5}&=-x_{2}+x_{3}\\x_{6}&=1-x_{1}-x_{2}-x_{3}\\x_{7}&=-1+x_{1}+x_{2}+x_{3}\\z&=15x_{1}+12x_{2}+4x_{3}\\\end{aligned}}$

${\begin{aligned}x_{3}&\leftrightarrow x_{6}\\x_{3}&=1-x_{1}-x_{2}-x_{6}\\x_{4}&=1-{\dfrac {5}{2}}x_{1}-{\dfrac {3}{2}}x_{2}+{\dfrac {1}{2}}x_{6}\\x_{5}&=1-x_{1}-2x_{2}-x_{6}\\x_{7}&=-x_{6}\\z&=4+11x_{1}+8x_{2}-4x_{6}\\\end{aligned}}$

${\begin{aligned}x_{2}&\leftrightarrow x_{5}\\x_{2}&={\dfrac {1}{2}}-{\dfrac {1}{2}}x_{1}-{\dfrac {1}{2}}x_{5}-{\dfrac {1}{2}}x_{6}\\x_{3}&={\dfrac {1}{2}}-{\dfrac {1}{2}}x_{1}+{\dfrac {1}{2}}x_{5}-{\dfrac {1}{2}}x_{6}\\x_{4}&={\dfrac {1}{4}}-{\dfrac {7}{4}}x_{1}+{\dfrac {3}{4}}x_{5}+{\dfrac {5}{4}}x_{6}\\x_{7}&=-x_{6}\\z&=8+7x_{1}-4x_{5}-8x_{6}\\\end{aligned}}$

${\begin{aligned}x_{1}&\leftrightarrow x_{4}\\x_{1}&={\dfrac {1}{7}}-{\dfrac {4}{7}}x_{4}+{\dfrac {3}{7}}x_{5}+{\dfrac {5}{7}}x_{6}\\x_{2}&={\dfrac {3}{7}}+{\dfrac {2}{7}}x_{4}-{\dfrac {5}{7}}x_{5}-{\dfrac {6}{7}}x_{6}\\x_{3}&={\dfrac {3}{7}}+{\dfrac {2}{7}}x_{4}+{\dfrac {2}{7}}x_{5}-{\dfrac {6}{7}}x_{6}\\x_{7}&=-x_{6}\\z&=9-4x_{4}-x_{5}-3x_{6}\\\end{aligned}}$

${\text{The optimal solution is}}\;x_{1}={\dfrac {1}{7}},x_{2}={\dfrac {3}{7}},x_{3}={\dfrac {3}{7}},{\text{with optimal value}}\;z=9\;{\text{and a total risk of}}\;{\dfrac {3}{2}}.$

Dual Problem

Objective Function

${\text{minimize}}\;w=\sigma y_{1}+y_{3}-y_{4}$

Constraints

${\begin{aligned}{\text{s.t.}}\;&3y_{1}+y_{3}-y_{4}\geq 15\\&2y_{1}+y_{2}+y_{3}-y_{4}\geq 12\\&{\dfrac {1}{2}}y_{1}-y_{2}+y_{3}-y_{4}\geq 4\\&y_{1},y_{2},y_{3},y_{4}\geq 0\\\end{aligned}}$

Slack Variables

$y_{5}=15+3y_{1}+y_{3}-y_{4}$

$y_{6}=12+2y_{1}+y_{2}+y_{3}-y_{4}$

$y_{7}=4+{\dfrac {1}{2}}y_{1}-y_{2}+y_{3}-y_{4}$

$y_{5},y_{6},y_{7}\geq 0$

Worked Solution

${\text{Let}}\;\sigma ={\dfrac {3}{2}}$

${\begin{aligned}y_{5}&=-15+3y_{1}+y_{3}-y_{4}\\y_{6}&=-12+2y_{1}+y_{2}+y_{3}-y_{4}\\y_{7}&=-4+{\dfrac {1}{2}}y_{1}-y_{2}+y_{3}-y_{4}\\-w&=-{\dfrac {3}{2}}y_{1}-y_{3}+y_{4}\\\end{aligned}}$

${\begin{aligned}y_{3}&\leftrightarrow y_{5}\\y_{3}&=15-3y_{1}+y_{4}+y_{5}\\y_{6}&=3-y_{1}+y_{2}+y_{5}\\y_{7}&=11-{\dfrac {5}{2}}y_{1}-y_{2}+y_{5}\\-w&=-15+{\dfrac {3}{2}}y_{1}-y_{5}\\\end{aligned}}$

${\begin{aligned}y_{1}&\leftrightarrow y_{6}\\y_{1}&=3+y_{2}+y_{5}-y_{6}\\y_{3}&=6-3y_{2}+y_{4}-2y_{5}+3y_{6}\\y_{7}&={\dfrac {7}{2}}-{\dfrac {7}{2}}y_{2}-{\dfrac {3}{2}}y_{5}+{\dfrac {5}{2}}y_{6}\\-w&=-{\dfrac {21}{2}}+{\dfrac {3}{2}}y_{2}+{\dfrac {1}{2}}y_{5}-{\dfrac {3}{2}}y_{6}\\\end{aligned}}$

${\begin{aligned}y_{2}&\leftrightarrow y_{7}\\y_{2}&=1-{\dfrac {3}{7}}y_{5}+{\dfrac {5}{7}}y_{6}-{\dfrac {2}{7}}y_{7}\\y_{1}&=4+{\dfrac {4}{7}}y_{5}-{\dfrac {2}{7}}y_{6}-{\dfrac {2}{7}}y_{7}\\y_{3}&=3+y_{4}-{\dfrac {5}{7}}y_{5}+{\dfrac {6}{7}}y_{6}+{\dfrac {6}{7}}y_{7}\\-w&=-9-{\dfrac {1}{7}}y_{5}-{\dfrac {3}{7}}y_{6}-{\dfrac {3}{7}}y_{7}\\\end{aligned}}$

${\text{i.e.}}\;w=9+{\dfrac {1}{7}}y_{5}+{\dfrac {3}{7}}y_{6}+{\dfrac {3}{7}}y_{7}$

${\text{The optimal solution is}}\;y_{1}=4,y_{2}=1,y_{3}=3,y_{4}=0\;{\text{with optimal value}}\;w=9.$

Interpretation of Results

In both the primal and the dual the optimal solutions, z and w respectively, are 9. This tells us that using the investment distribution given by the primal we should see a return of 9% on our initial investment.

Now, consider the variables from the optimal solution to the dual problem.

$y_{1}$: this variable refers to the first constraint. The first constraint puts an upper bound on the amount of total risk we are willing to take on. This means $y_{1}$ gives the increase in output for an additional unit of risk we're willing to take on. So in this case, increasing the risk we'd take by 1 increases out total return by 4%.

$y_{2}$: this variable refers to the second constraint. Here, $x_{2}\leq x_{3}$. Lets consider what happens if you loosen the constraint by 0.1. In this case the increase in return would go up by 0.1%.

$y_{3}$ and $y_{4}$: these variables correspond with the constraints derived from $x_{1}+x_{2}+x_{3}=1$. These would be the changes in return percentage based on borrowing additional money; however, borrowing is outside the scope of this toy problem so we will not discuss this any further.

Actual Portfolio

We will use these options from TD bank.

Various BMO ETFs with rewards (3 year annualized return), risks on a scale of 1-5 (1 low risk, 5 high risk) and volatility (3 year volatility) are shown below.

Variable	Symbol	Stock Name	Reward	Risk	Volatility
$x_{1}$	ZXB	BMO 2015 Corporate Bond Target Mat ETF	-0.23%	3	6.55
$x_{2}$	ZXC	BMO 2020 Corporate Bond Target Mat ETF	2.63%	3	7.81
$x_{3}$	ZXD	BMO 2025 Corporate Bond Target Mat ETF	0.91%	4	7.55
$x_{4}$	ZAG	BMO Aggregate Bond ETF	2.50%	3	9.31
$x_{5}$	ZDV	BMO Canadian Dividend ETF	6.43%	3	9.46
$x_{6}$	ZCH	BMO China Equity ETF	26.73%	3	13.60
$x_{7}$	ZWB	BMO Covered Call Canadian Banks ETF	11.47%	4	12.23
$x_{8}$	ZWA	BMO Covered Call DJIA Hedged to CAD ETF	11.76%	3	11.18
$x_{9}$	ZDJ	BMO Dow Jones Ind Avg Hdgd CAD ETF	13.63%	3	11.96
$x_{10}$	ZEF	BMO Emerging Market Bnd Hdgd to CAD ETF	3.88%	5	10.85
$x_{11}$	ZRE	BMO Equal Weight REITs ETF	1.99%	2	12.10
$x_{12}$	ZUB	BMO Eq Weight US Banks Hdgd to CAD ETF	22.05%	4	15.73
$x_{13}$	ZGI	BMO Global Infrastructure ETF	17.37%	3	10.66
$x_{14}$	ZHY	BMO High Yld US Corp Bd Hdgd to CAD ETF	5.00%	5	8.14
$x_{15}$	ZJN	BMO Junior Gas ETF	9.75%	4	21.80
$x_{16}$	ZJG	BMO Junior Gold ETF	-27.79%	5	42.71
$x_{17}$	ZJO	BMO Junior Oil ETF	1.46%	4	22.12
$x_{18}$	ZLC	BMO Long Corporate Bond ETF	2.92%	2	9.72
$x_{19}$	ZFL	BMO Long Federal Bond ETF	-0.20%	3	10.59
$x_{20}$	ZLB	BMO Low Volatility Canadian Equity ETF	19.23%	1	8.52
$x_{21}$	ZCM	BMO Mid Corporate Bond ETF	2.67%	5	7.53
$x_{22}$	ZFM	BMO Mid Federal Bond ETF	0.20%	5	7.92
$x_{23}$	ZMI	BMO Monthly Income ETF	4.60%	4	7.96
$x_{24}$	ZDM	BMO MSCI EAFE Hdg to CAD ETF	18.95%	4	10.56
$x_{25}$	ZEM	BMO MSCI Emerging Markets ETF	8.86%	3	10.97
$x_{26}$	ZQQ	BMO NASDAQ 100 Equity Hedged to CAD ETF	20.36%	5	12.61
$x_{27}$	ZRR	BMO Real Return Bond ETF	-2.31%	4	11.77
$x_{28}$	ZUE	BMO S&P 500 Hedged to CAD ETF	17.36%	4	11.07
$x_{29}$	ZCN	BMO S&P/TSX Capped Composite ETF	9.92%	3	9.16
$x_{30}$	ZEB	BMO S&P/TSX Equal Weight Banks ETF	13.06%	3	13.34
$x_{31}$	ZMT	BMO S&P/TSX EqWt Glb BM Hdgd to CAD ETF	-4.23%	4	20.63
$x_{32}$	ZEO	BMO S&P/TSX Equal Weight Oil&Gas ETF	0.27%	1	16.66
$x_{33}$	ZCS	BMO Short Corporate Bond ETF	0.74%	4	6.44
$x_{34}$	ZFS	BMO Short Federal Bond ETF	-0.61%	4	6.41
$x_{35}$	ZPS	BMO Short Provincial Bond ETF	0.08%	5	6.27
$x_{36}$	ZST	BMO Ultra Short-Term Bond ETF	-0.97%	3	6.78

LP Problem

${\text{maximize}}\;z=\sum \limits _{n=1}^{36}Yield_{n}x_{n}$

${\begin{aligned}{\text{s.t.}}\;&\sum \limits _{n=1}^{36}Reward_{n}x_{n}\leq 10\\&\sum \limits _{n=1}^{36}x_{n}=1\\&0\leq x_{n}\leq 0.15\;{\text{for}}\;n=1,2,3,\dots ,36\\\end{aligned}}$

Results

Z = 15.9009

Symbol	Percentage Invested
ZXB	0
ZXC	0
ZXD	0
ZAG	0
ZDV	0
ZCH	0.15
ZWB	0
ZWA	0
ZDJ	0
ZEF	0
ZRE	0
ZUB	0
ZGI	0.15
ZHY	0
ZJN	0
ZJG	0
ZJO	0
ZLC	0
ZFL	0
ZLB	0.15
ZCM	0
ZFM	0
ZMI	0
ZDM	0.15
ZEM	0
ZQQ	0
ZRR	0
ZUE	0.15
ZCN	0.0849481
ZEB	0
ZMT	0
ZEO	0
ZCS	0.15
ZFS	0
ZPS	0.0150519
ZST	0

Solver Code

Here is the code to solve the LP program using python.

Operating System: Ubuntu 14.04 LTS This uses a modified version PyGLPK found at https://github.com/bradfordboyle/pyglpk Ran on python version 2.7

Both the code, called solve.py, and the datafile it uses, data.txt are shown below. Note, data.txt must be in the same directory as solve.py.

solve.py

   import glpk

   max_percent_per_stock = 0.15
   max_volatility = 10
   data_filename = 'data.txt'
   the_file = open(data_filename, 'r')

   lines = []
   for line in the_file:
       l = line.strip()
       l = line.split()
       lines.append(l)

   # Drop first line. It's column labels.
   stocks       = lines[1:]
   n            = len(stocks)
   names        = [stock[0] for stock in stocks]
   rewards      = [float(stock[1].replace("%", "")) for stock in stocks]
   risks        = [stock[2] for stock in stocks]
   volatilities = [float(stock[3]) for stock in stocks]

   # Referencing solver code from http://tfinley.net/software/pyglpk/ex_ref.html
   lp              = glpk.LPX()
   lp.name         = '340project'
   lp.obj.maximize = True

   # add rows
   #   1 row for first constraint
   #   1 row for second constraint
   #   n rows for last constraint
   lp.rows.add(n+2)
   for row in lp.rows:
       row.name = 's{0}'.format(row.index)

   # put bounds on constraints
   # constraint 1: 0 \leq x_n \leq 0.15 \text{ for }n=1, 2, ..., n
   for row in lp.rows[:n]:
       # TODO ISSUE: 0 \leq x_n \leq 0.15? Can I use None or should I use 0?
       row.bounds = None, max_percent_per_stock

   # constraint 2: \sum\limits{n=1}_{36} Volatility_n*x_n \leq 10
   lp.rows[n].bounds = None, max_volatility

   # constraint 3: \sum\limits{n=1}_{36} x_n = 1
   lp.rows[n+1].bounds = 1.0, 1.0

   # initial dictionary has n non-basic variables so we need n columns
   lp.cols.add(n)
   for col in lp.cols:
       col.name = '{0}'.format(names[col.index])
       col.bounds = 0, None

   # set the objective function
   lp.obj[:] = rewards

   # build matrix of coeffs. We refer to this as matrix A in class.
   matrix = []

   # constraint 1: 0 \leq x_n \leq 0.15 \text{ for }n=1, 2, ..., n
   for stock_num in xrange(len(stocks)):
       row_of_zeros = [0 for x in xrange(n)]
       row_of_zeros[stock_num] = 1
       matrix += row_of_zeros

   # constraint 2: \sum\limits{n=1}_{36} Volatility_n*x_n \leq 10
   matrix += volatilities

   # constraint 3: \sum\limits{n=1}_{36} x_n = 1
   matrix += [1 for x in xrange(n)]

   lp.matrix = matrix

   lp.simplex()
   print 'Z = %g\n' % lp.obj.value,
   print '{| class="wikitable" style="text-align: center;"'
   print '|-'
   print '! Symbol !! Percentage Invested'
   print '|-'
   print '\n|-\n'.join('| %s || %g' % (c.name, c.primal) for c in lp.cols)
   print '|-'
   print '|}'

data.txt

   Symbol Reward Risk Volatility
   ZXB 	-0.23% 	3 	6.55
   ZXC 	2.63% 	3 	7.81
   ZXD 	0.91% 	4 	7.55
   ZAG 	2.50% 	3 	9.31
   ZDV 	6.43% 	3 	9.46
   ZCH 	26.73% 	3 	13.60
   ZWB 	11.47% 	4 	12.23
   ZWA 	11.76% 	3 	11.18
   ZDJ 	13.63% 	3 	11.96
   ZEF 	3.88% 	5 	10.85
   ZRE 	1.99% 	2 	12.10
   ZUB 	22.05% 	4 	15.73
   ZGI 	17.37% 	3 	10.66
   ZHY 	5.00% 	5 	8.14
   ZJN 	9.75% 	4 	21.80
   ZJG 	-27.79% 5 	42.71
   ZJO 	1.46% 	4 	22.12
   ZLC 	2.92% 	2 	9.72
   ZFL 	-0.20% 	3 	10.59
   ZLB 	19.23% 	1 	8.52
   ZCM 	2.67% 	5 	7.53
   ZFM 	0.20% 	5 	7.92
   ZMI 	4.60% 	4 	7.96
   ZDM 	18.95% 	4 	10.56
   ZEM 	8.86% 	3 	10.97
   ZQQ 	20.36% 	5 	12.61
   ZRR 	-2.31% 	4 	11.77
   ZUE 	17.36% 	4 	11.07
   ZCN 	9.92% 	3 	9.16
   ZEB 	13.06% 	3 	13.34
   ZMT 	-4.23% 	4 	20.63
   ZEO 	0.27% 	1 	16.66
   ZCS 	0.74% 	4 	6.44
   ZFS 	-0.61% 	4 	6.41
   ZPS 	0.08% 	5 	6.27
   ZST 	-0.97% 	3 	6.78