<p><div><div><div><div data-show-faces="false" data-height="21" data-width="100" data-layout="button_count" data-send="true" data-href="https://www.r-bloggers.com/online-portfolio-allocation-with-a-very-simple-algorithm/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="https://insightr.wordpress.com/2017/06/22/online-portfolio-allocation-with-a-very-simple-algorithm/"> R – insightR</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<div>
<p><strong>By Yuri Resende</strong></p>
<p> </p>
</div>
<p>Today we will use an online convex optimization technique to build a very simple algorithm for portfolio allocation. Of course this is just an illustrative post and we are going to make some simplifying assumptions. The objective is to point out an interesting direction to approach the problem of portfolio allocation.</p>
<p><span></span></p>
<p>The algorithm used here is the Online Gradient Descendent (OGD) and we are going to compare the performance of the portfolio with the Uniform Constant Rebalanced Portfolio and the Dow Jones Industrial Average index. You can skip directly to Implementation and Example if you already know what an online algorithm is.</p>
<h2>For those who don’t know what Online Convex Optimization is…</h2>
<p>From now on, we will say that <img alt="p" title="p" src="https://s0.wp.com/latex.php?latex=p&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex"> represents a point in dimension <img alt="N" title="N" src="https://s0.wp.com/latex.php?latex=N&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex">, where <img alt="N" title="N" src="https://s0.wp.com/latex.php?latex=N&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex"> is the number of possible stocks to invest. Each of it’s coordinates represent the amount invested in the respective stock. For example, suppose that <img alt="N = 3" title="N = 3" src="https://s0.wp.com/latex.php?latex=N+%3D+3&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex"> and <img alt="p_t = [0.25, 0.25, 0.5]^prime" title="p_t = [0.25, 0.25, 0.5]^prime" src="https://s0.wp.com/latex.php?latex=p_t+%3D+%5B0.25%2C+0.25%2C+0.5%5D%5E%5Cprime&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex">. Then, our portfolio at time $latex  t$ are composed of <img alt="25%" title="25%" src="https://s0.wp.com/latex.php?latex=25%5C%25&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex"> from stock one, <img alt="25%" title="25%" src="https://s0.wp.com/latex.php?latex=25%5C%25&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex"> from stock two, and <img alt="50%" title="50%" src="https://s0.wp.com/latex.php?latex=50%5C%25&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex"> from stock three.</p>
<p>Online Convex Optimization is based on the idea of minimizing the so-called Regret function, which is basically an idea of how far from a good player you are (some kind of optimal player that you want to be). In the set-up of portfolio management, the Regret function is defined as:</p>
<p>
<img alt="displaystyle Regret=sum_{i=1}^tlog(p^*r_i)-sum_{i=1}^tlog(p_ir_i)" title="displaystyle Regret=sum_{i=1}^tlog(p^*r_i)-sum_{i=1}^tlog(p_ir_i)" src="https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+Regret%3D%5Csum_%7Bi%3D1%7D%5Etlog%28p%5E%2Ar_i%29-%5Csum_%7Bi%3D1%7D%5Etlog%28p_ir_i%29&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex"></p>
<p>The first part on the right hand side is the cumulative log return of the portfolio <img alt="p^*" title="p^*" src="https://s0.wp.com/latex.php?latex=p%5E%2A&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex">, and the second part, is the cumulative log return of our portfolio until time <img alt="t" title="t" src="https://s0.wp.com/latex.php?latex=t&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex">, which we have played strategy <img alt="p_i,~~~i=1,2,dots,t" title="p_i,~~~i=1,2,dots,t" src="https://s0.wp.com/latex.php?latex=p_i%2C~~~i%3D1%2C2%2C%5Cdots%2Ct&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex">. What is interesting is that <img alt="p^*" title="p^*" src="https://s0.wp.com/latex.php?latex=p%5E%2A&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex"> is a very special case of portfolio. It represents the Best Constant Rebalanced Portfolio (CRP)…it means that if someone could see the future and knew upfront all the returns of all the stocks and had to play a fixed portfolio proportion at time zero, <img alt="p^*" title="p^*" src="https://s0.wp.com/latex.php?latex=p%5E%2A&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex"> would be his choice. In the worst case scenario, the best CRP is equal to the best stock in the period, and the best CRP is the portfolio that we want to track.</p>
<p>The OGD algorithm is quite simple, we are going to update our position every week based on the gradient of the <img alt="Regret" title="Regret" src="https://s0.wp.com/latex.php?latex=Regret&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex"> function in the currently strategy. Here it follows:</p>
<ol>
<li>First play <img alt="p_1 = frac{1}{n} textbf{1}" title="p_1 = frac{1}{n} textbf{1}" src="https://s0.wp.com/latex.php?latex=p_1+%3D+%5Cfrac%7B1%7D%7Bn%7D+%5Ctextbf%7B1%7D&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex"></li>
<li>For <img alt="t &gt; 1" title="t &gt; 1" src="https://s0.wp.com/latex.php?latex=t+%3E+1&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex">,</li>
<li><img alt="b_{t-1} = sum_{tau = 1}^{t-1}nabla(textit{Regret})" title="b_{t-1} = sum_{tau = 1}^{t-1}nabla(textit{Regret})" src="https://s0.wp.com/latex.php?latex=b_%7Bt-1%7D+%3D+%5Csum_%7B%5Ctau+%3D+1%7D%5E%7Bt-1%7D%5Cnabla%28%5Ctextit%7BRegret%7D%29&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex"></li>
<li><img alt="tilde{p}_t = p_{t-1} - eta b_{t-1}" title="tilde{p}_t = p_{t-1} - eta b_{t-1}" src="https://s0.wp.com/latex.php?latex=%5Ctilde%7Bp%7D_t+%3D+p_%7Bt-1%7D+-+%5Ceta+b_%7Bt-1%7D&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex"></li>
<li><img alt="p_t = prod_{S_n}(tilde{p}_t)" title="p_t = prod_{S_n}(tilde{p}_t)" src="https://s0.wp.com/latex.php?latex=p_t+%3D+%5Cprod_%7BS_n%7D%28%5Ctilde%7Bp%7D_t%29&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex"></li>
<li><img alt="prod_{S_n}(q) = argmin_{x in S_n} (x - q)^prime(x-q)" title="prod_{S_n}(q) = argmin_{x in S_n} (x - q)^prime(x-q)" src="https://s0.wp.com/latex.php?latex=%5Cprod_%7BS_n%7D%28q%29+%3D+arg%5Cmin_%7Bx+%5Cin+S_n%7D+%28x+-+q%29%5E%5Cprime%28x-q%29&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex"></li>
</ol>
<p>This algorithm is proved to have <img alt="Regret" title="Regret" src="https://s0.wp.com/latex.php?latex=Regret&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex"> of order <img alt="O(GDsqrt{T})" title="O(GDsqrt{T})" src="https://s0.wp.com/latex.php?latex=O%28GD%5Csqrt%7BT%7D%29&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex"> if <img alt="eta = frac{G}{Dsqrt{T}}" title="eta = frac{G}{Dsqrt{T}}" src="https://s0.wp.com/latex.php?latex=%5Ceta+%3D+%5Cfrac%7BG%7D%7BD%5Csqrt%7BT%7D%7D&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex">. There is another similar algorithm which takes second order information and is quite similar to an online version of the Newton’s method. The name, not surprisingly is Online Newton Step. See Agrawal et al (2006) for further details.</p>
<h2>Implementation and Example</h2>
<p>In our set-up the set of possible portfolios will not allow us to borrow money or short selling stocks, so every position should be bigger then zero and the sum of all positions should be one. This set is called simplex and define polytope. Basically it’s a triangle in higher dimension.</p>
<pre>library(quantmod)

symbols &amp;amp;amp;amp;amp;amp;amp;lt;- c('MMM', 'AXP', 'AAPL', 'BA', 'CAT', 'CVX', 'CSCO', 'KO', 'DIS', 'DD', 'XOM', 'GE',
  'GS', 'HD', 'IBM', 'INTC', 'JNJ', 'JPM', 'MCD', 'MRK', 'MSFT', 'NKE', 'PFE', 'PG',
  'TRV', 'UTX', 'UNH', 'VZ', 'V', 'WMT')

for (i in 1:length(symbols)) getSymbols(symbols[i], from = '2007-01-03', to = '2017-06-21')

# Building weekly returns for each of the stocks
data &amp;amp;amp;amp;amp;amp;amp;lt;-sapply(symbols, function(x) Ad(to.weekly(get(x))))
data &amp;amp;amp;amp;amp;amp;amp;lt;- Reduce(cbind, data)
data_returns &amp;amp;amp;amp;amp;amp;amp;lt;- apply(data, 2, function(x) diff(log(x))) #log returns
colnames(data_returns) &amp;amp;amp;amp;amp;amp;amp;lt;- symbols
data_returns[is.na(data_returns)] &amp;amp;amp;amp;amp;amp;amp;lt;- 0 # VISA hasnt negotiations between 2007 and 2008
</pre>
<p>The OGD algorithm is implemented next. It uses the <code>quadprogXT</code> package to solve the projection onto the viable set. We are going to test two different values for <img alt="eta" title="eta" src="https://s0.wp.com/latex.php?latex=%5Ceta&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex"> to check the algorithm sensibility.</p>
<pre>library(quadprogXT)

OGD &amp;amp;amp;amp;amp;amp;amp;lt;- function(base, eta) {

  # Gradient of Regret Function
  gradient = function(b, p, r) b + r/(p%*%r)

  # Projection onto viable Set
  proj = function(p) {

    Dmat = diag(length(p))
    Amat = cbind(diag(rep(1, length(p))), -1)
    bvec = c(rep(0, length(p)), -1)

    fit = solveQPXT(Dmat = Dmat, dvec = p, Amat = Amat, bvec = bvec)

    return(fit$solution)
  }

  T = nrow(base)
  N = ncol(base)

  r = as.matrix(base) + 1 # this is because the algo doesnt work directly with log returns
  p = matrix(0, nrow = N, ncol = T); p[,1] = 1/N # initial portfolio
  b = matrix(0, nrow = N, ncol = T); b[,1] = 0

  for (i in 2:T) {
    b[,i] = gradient(b[,i-1], p[,i-1], r[i-1,]) # calculating gradient
    p.aux = p[,i-1] + eta*b[,i] # what we would like to play
    p[,i] = proj(p.aux) # projection in the viable set
  }

  return(list('portfolio' = p,'gradient' = b))
}

# testing two etas
portfolio1 &amp;amp;amp;amp;amp;amp;amp;lt;- OGD(base = data_returns, eta = 1/100)
portfolio2 &amp;amp;amp;amp;amp;amp;amp;lt;- OGD(base = data_returns, eta = 1/1000)
</pre>
<p>Lets build a small function to calculate the compound return of portfolios taking their log return as input.</p>
<pre>compound_return &amp;amp;amp;amp;amp;amp;amp;lt;- function(portfolio, r) {

  return_OGD &amp;amp;amp;amp;amp;amp;amp;lt;- c(); return_OGD[1] = portfolio$portfolio[,1]%*%r[1,]
  portfolio_value &amp;amp;amp;amp;amp;amp;amp;lt;- c(); portfolio_value[1] = 1 + portfolio$portfolio[,1]%*%r[1,]

  for (i in 2:nrow(r)) {
    return_OGD[i] = portfolio$portfolio[,i]%*%r[i,]
    portfolio_value[i] = portfolio_value[i-1]*(1 + return_OGD[i])
  }  

 return(list('value' = portfolio_value, 'return' = return_OGD))
}
</pre>
<p>Now let’s check the performance of the OGD algorithm with both <img alt="0.01" title="0.01" src="https://s0.wp.com/latex.php?latex=0.01&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex"> and <img alt="0.001" title="0.001" src="https://s0.wp.com/latex.php?latex=0.001&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex"> values for <img alt="eta" title="eta" src="https://s0.wp.com/latex.php?latex=%5Ceta&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex">. We are going to compare the cumulative return first with the Uniform Constant Rebalanced Portfolio and the DJIA index. Them we will check the compound returns of DJIA stocks individually to see if the algorithm tracked the best stocks like we want them to do.</p>
<pre># Dow Jones
getSymbols('^DJI', src = 'yahoo', from = '2007-01-03', to = '2017-06-21')
</pre>
<pre>## [1] &quot;DJI&quot;
</pre>
<pre>DJIA_returns = as.numeric(cumprod(weeklyReturn(DJI) + 1))

# Individual stocks
stocks_returns = apply(data_returns + 1, 2, cumprod)

# Our portfolios
portfolio_value1 &amp;amp;amp;amp;amp;amp;amp;lt;- compound_return(portfolio1, data_returns)
portfolio_value2 &amp;amp;amp;amp;amp;amp;amp;lt;- compound_return(portfolio2, data_returns)
</pre>
<p>In the figures below we can see the performance of the strategies that were implemented. Both portfolios had a surprisingly perform, much better than DJIA and UCRP portfolio.</p>
<p><img alt="plot of chunk graphics" src="https://i1.wp.com/i.imgur.com/dOAC4n7.png"><img alt="plot of chunk graphics" src="https://i1.wp.com/i.imgur.com/RcCIVdh.png"></p>
<p>Indeed, if <img alt="eta" title="eta" src="https://s0.wp.com/latex.php?latex=%5Ceta&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex"> is relatively big, the algorithm quickly found Apple as the best stock, and start pursuing it. If <img alt="eta" title="eta" src="https://s0.wp.com/latex.php?latex=%5Ceta&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex"> is relative small, them the algorithm takes more time to adapt, but this makes the portfolio more stable.</p>
<p><img alt="Portfolio variation eta = 0.01" src="https://i1.wp.com/i.imgur.com/IISWzAv.png"></p>
<pre>## &amp;amp;amp;amp;amp;amp;amp;lt;ScaleContinuousPosition&amp;amp;amp;amp;amp;amp;amp;gt;
##  Range:
##  Limits:    0 --    1
</pre>
<p><img alt="Portfolio variation eta = 0.001" src="https://i2.wp.com/i.imgur.com/9m7UwB4.png"></p>
<p>To finish the comparison between our portfolios and DJIA, lets do a very simple risk analysis with just empirical quantiles using historical results. For a proper risk analysis we should model the conditional volatility of the portfolio, but this will be discussed in another post.</p>
<pre>risk_analysis &amp;amp;amp;amp;amp;amp;amp;lt;- function(return) {

  report = matrix(0, ncol = 2, nrow = 2)

  report[1,] = quantile(return, probs = c(0.01, 0.05))
  report[2,] = c(mean(return[which(return &amp;amp;amp;amp;amp;amp;amp;lt;= report[1,1])]), mean(return[which(return &amp;amp;amp;amp;amp;amp;amp;lt;= report[1,2])]))

  rownames(report) = c('VaR', 'CVaR')
  colnames(report) = c('1%', '5%')

  return(round(report, 3))
}

report1 &amp;amp;amp;amp;amp;amp;amp;lt;- risk_analysis(portfolio_value1$return)
report2 &amp;amp;amp;amp;amp;amp;amp;lt;- risk_analysis(portfolio_value2$return)
report_DJIA &amp;amp;amp;amp;amp;amp;amp;lt;- risk_analysis(weeklyReturn(DJI))
</pre>
<table border="1">
<caption align="bottom">Portfolio1 eta = 0.01</caption>
<tbody>
<tr>
<th></th>
<th>1%</th>
<th>5%</th>
</tr>
<tr>
<td align="right">VaR</td>
<td align="right">-0.091</td>
<td align="right">-0.047</td>
</tr>
<tr>
<td align="right">CVaR</td>
<td align="right">-0.119</td>
<td align="right">-0.074</td>
</tr>
</tbody>
</table>
<table border="1">
<caption align="bottom">Portfolio2 eta = 0.001</caption>
<tbody>
<tr>
<th></th>
<th>1%</th>
<th>5%</th>
</tr>
<tr>
<td align="right">VaR</td>
<td align="right">-0.057</td>
<td align="right">-0.039</td>
</tr>
<tr>
<td align="right">CVaR</td>
<td align="right">-0.085</td>
<td align="right">-0.055</td>
</tr>
</tbody>
</table>
<table border="1">
<caption align="bottom">DJIA index</caption>
<tbody>
<tr>
<th></th>
<th>1%</th>
<th>5%</th>
</tr>
<tr>
<td align="right">VaR</td>
<td align="right">-0.060</td>
<td align="right">-0.040</td>
</tr>
<tr>
<td align="right">CVaR</td>
<td align="right">-0.084</td>
<td align="right">-0.055</td>
</tr>
</tbody>
</table>
<p>It’s quite evident that setting a big <img alt="eta" title="eta" src="https://s0.wp.com/latex.php?latex=%5Ceta&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex">, like we did in portfolio1, may have caused problems with VaR and Conditional VaR since Apple is a volatile stock. For portfolio2, where <img alt="eta" title="eta" src="https://s0.wp.com/latex.php?latex=%5Ceta&bg=ffffff&%23038;fg=333333&%23038;s=0" class="latex"> is small the portfolio takes time to change, the historical VaR and CVaR are very similar to what we already observed in DJIA, but the returns were much better.</p>
<h2>References</h2>
<p>Agarwal, Amit, et al. “Algorithms for portfolio management based on the newton method.” Proceedings of the 23rd international conference on Machine learning. ACM, 2006.</p>
<p> <a rel="nofollow" href="http://feeds.wordpress.com/1.0/gocomments/insightr.wordpress.com/375/" target="_blank"><img border="0" alt="" src="http://feeds.wordpress.com/1.0/comments/insightr.wordpress.com/375/"></a> <img border="0" alt="" src="https://i1.wp.com/pixel.wp.com/b.gif?resize=1%2C1&ssl=1" data-recalc-dims="1"></p>
	<p>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="https://insightr.wordpress.com/2017/06/22/online-portfolio-allocation-with-a-very-simple-algorithm/"> R – insightR</a></strong>.</div>
<hr>
<a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers.com</a> offers <strong><a rel="nofollow" href="https://feedburner.google.com/fb/a/mailverify?uri=RBloggers">daily e-mail updates</a></strong> about <a rel="nofollow" href="https://www.r-project.org/" title="The R Project for Statistical Computing">R</a> news and <a rel="nofollow" href="https://www.r-bloggers.com/search/tutorial" title="R tutorials">tutorials</a> on topics such as: <a rel="nofollow" href="https://www.r-bloggers.com/search/data%20science" title="Data science">Data science</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Big%20Data" title="Big Data">Big Data, <a rel="nofollow" href="https://www.r-users.com/" title="R jobs">R jobs</a>, visualization (<a rel="nofollow" href="https://www.r-bloggers.com/search/ggplot2" title="ggplot and ggplot2 tutorials">ggplot2</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/boxplot" title="Boxplots using lattice and ggplot2 tutorials">Boxplots</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/map" title="Maps and gis">maps</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/animation" title="Animation in R">animation</a>), programming (<a rel="nofollow" href="https://www.r-bloggers.com/search/RStudio" title="RStudio IDE for R">RStudio</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/sweave" title="Sweave and literate programming">Sweave</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/LaTeX" title="LaTeX in R">LaTeX</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/SQL" title="SQL and databases">SQL</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/eclipse" title="Eclipse IDE for R">Eclipse</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/git" title="git and github, Version Control System">git</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/hadoop" title="Large data in R using Hadoop">hadoop</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Web+Scraping" title="Web Scraping of google, facebook, yahoo, twitter and more using R">Web Scraping</a>) statistics (<a rel="nofollow" href="https://www.r-bloggers.com/search/regression" title="Regressions and ANOVA analysis tutorials">regression</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/PCA" title="principal component analysis tutorial">PCA</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/time+series" title="Time series">time series</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/trading" title="finance trading">trading</a>) and more...
<img width="1" alt="" src="http://feeds.feedburner.com/~r/RBloggers/~4/bRnGVClJ5OU" height="1"></a></div>