Evaluative Assignment - Efficient Frontier
For this assignment, write a program to find the efficient frontier, or optimal set of portfolios, given a universe of assets and their correlations.
Write a program "efficient_frontier", which takes two command line arguments:
- The name of a file with a universe of assets. This file is in CSV format with no header row. Each line contains the asset name, the average rate of return, and the standard deviation of the rate of return.
- The name of the file containing the correlation matrix for the universe of assets.
As sample data, universe.csv contains the following assets along with their average(annualized) returns and standard deviations of those returns: international equities, commodities, real estate, investmentgrade corporate bonds, inflation-linked, medium-term (7-10yr) US Treasury bonds, and short-term (13yr) US Treasury bonds. correlation.csv contains the asset correlations from March 2009 to June 2015. (This period comes right after the end of the credit crisis bear market.)
The efficient frontier is a hyperbola representing the boundary of all possible optimal portfolios that can be created from the assets provided.
From these assets, we need to find the optimal (least risky – i.e. lowest volatility) portfolio for each level of expected portfolio return.
A portfolio has a vector of weights, indicating how much of the portfolio is invested in each asset. These weights sum to 1. This program must estimate the optimal weights, i.e. minimum volatility, for each return level between 1% and 26% in 1% increments. The formula for portfolio volatility is
For this step, print a comma-separated list of the return and the minimum volatility for that rate of return. In this part, assume that short sales are allowed (the weights can be negative). For example, the values for 1-4% are: (expected output is on the right side)
ROR,volatility 1.0%,0.78% 2.0%,1.09% 3.0%,1.59% 4.0%,2.13%
Optimizing this problem is tricky, as it is a constrained quadratic optimization problem. You are free to use any method you like to implement the optimization, but additional details are provided in the document (“Optimization approach for efficient frontier”) on Sakai.
In this step, you will add additional functionality to the program. If the option "-r" is passed as the first command line argument (i.e., after the executable name), you should implement a restricted optimization, i.e., use an additional constraint that no short sales are allowed. That is, all weights must be non-negative. Many different ways exist to check for the “-r”, use one that works best for you.
Again, print a comma-separated list of the return and the minimum volatility for that rate of return. When no short sales are allowed, the values for 1-4% are: ( 0.98% is the correct value, not 0.96%) ROR,volatility 1.0%,0.98% 2.0%,1.20% 3.0%,1.71% 4.0%,2.28%
The Eigen package
A convenient linear algebra package is available at http://eigen.tuxfamily.org. This package is already installed on the MLP server, and linked under /usr/local/include, so you do not need to do anything special with your Makefile to use the package in your code.
- Execute “honor-statement 121_eff_frontier”
- As mentioned, the executable must be named “efficient_frontier”.
- You must provide a Makefile. Recommended C++ version: std=C++11
- If the –r flag is present, it will be in the 2nd position of the arguments - the first (index 0) is the program name. The asset file will then be specified, followed by the correlation matrix file.
- Review the relationship between standard deviations, covariance, and correlation.
- Spend some time getting comfortable with Eigen. Start with the “Getting Started” page: https://eigen.tuxfamily.org/dox/GettingStarted.html
- Think about what errors may exist in the data files. You do not need to perform any type of data correction. When you do find errors, print an appropriate message to standard error and exit with a status code of “EXIT_FAILURE”. When checking for data errors, you should perform these
- Look towards using more of an object-oriented design. Nouns typically specify classes/properties while verbs represent potential behaviors. o An Asset has a name, average rate of return, and standard deviation. o A Portfolio has a list of weights and a list of Assets, from which the portfolio volatility and rate of return can be calculated. You can add more attributes and functions. o Other classes and files as needed to support parsing and optimization.
From the Optimization Approach notes posted on Sakai, we can find the optimal solution where the gradients are 0, so we have the following equation.
? is the covariance matrix
? is a 2 by n matrix (where n = number of assets) that has the form: (from equations 6, 7, 10)
This produces the following matrix 0.0978 0.0208 -0.0003 -0.0064 -0.0035 0.0400 -0.0005 1.0000 0.2651
0.0208 -0.0003 -0.0064 -0.0035 0.0400 -0.0005 0.0436 -0.0002 -0.0040 -0.0002 0.0228 -0.0003 -0.0002 0.0035 0.0030 0.0023 0.0016 0.0003 -0.0040 0.0030 0.0048 0.0031 -0.0047 0.0005 -0.0002 0.0023 0.0031 0.0033 -0.0014 0.0003 0.0228 0.0016 -0.0047 -0.0014 0.0640 -0.0005 -0.0003 0.0003 0.0005 0.0003 -0.0005 0.0001 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 -0.0064 0.0791 0.0407 0.0391 0.2505 0.0093
1.0000 0.2651 1.0000 -0.0064 1.0000 0.0791 1.0000 0.0407 1.0000 0.0391 1.0000 0.2505 1.0000 0.0093 0.0000 0.0000 0.0000 0.0000
Now, solve a linear system of equations of the form ???? = ??.
x contains the vector of weights and the Lagrange multipliers. https://eigen.tuxfamily.org/dox/group__TutorialLinearAlgebra.html provides sample code.
While the optimization approach document presents using a projection step with the primal-dual gradient method, we can also continue to utilize the matrix equation approach. Once we have an initial vector of weights, we look to see where any of the weights are negative. If a negative weight exists (e.g., for the ith asset), we add a linear equation to the “Matrix”, setting that variable to 0. This means that a new row with a 1 in the ith position is added to the “Matrix”. We also need to add a “0” row to the column vector on the right-hand side of the equation. As the number of columns in the “Matrix” must equal the number of rows in both x and b, we need to add the transpose of that new row onto the matrix as well. This process repeats until no negative weights exist or the weight is within a small value of 0 such that it will not have any factor in the portfolio volatility equation. Each weight that is negative should only be added once.
Compute x for the unrestricted case While x has negative members (alternatively, ???? < −??, where ?? is a sufficiently small number): Add a linear equation for each member xi that is negative to constrain that number to 0 Recompute weights by solving the updated linear system of equations.
Suppose weights 1 and 3 were negative. The updated matrix and vector becomes: (rate = .1) 0.0208 -0.0003 -0.0064 -0.0035 0.0400 -0.0005 0.0436 -0.0002 -0.0040 -0.0002 0.0228 -0.0003 -0.0002 0.0035 0.0030 0.0023 0.0016 0.0003 -0.0040 0.0030 0.0048 0.0031 -0.0047 0.0005 -0.0002 0.0023 0.0031 0.0033 -0.0014 0.0003 0.0228 0.0016 -0.0047 -0.0014 0.0640 -0.0005 -0.0003 0.0003 0.0005 0.0003 -0.0005 0.0001 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 -0.0064 0.0791 0.0407 0.0391 0.2505 0.0093 1.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 1.0000 0.0000 0.0000 0.0000
1.0000 0.2651 1.0000 -0.0064 1.0000 0.0791 1.0000 0.0407 1.0000 0.0391 1.0000 0.2505 1.0000 0.0093 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
0.0000 1.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
0.0000 0.0000 0.0000 1.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
Unlike previous assignments, we will not provide direct results of the test cases. As this assignment forms part of your final evaluation for the course, you will be expected to create your own test cases. The assignment pre-grader will run your test cases against both your submission and the reference implementation. You will need to create a “testcases.txt” file that has two sections
error: lists any test cases that should generate an error message and exit code.
success: lists any test cases that should run normally. The outputs from the two
implementations will be compared. You will only be informed which lines did not match.
You may create additional files (e.g. a file with bad asset data) as part of your submission. Sample testcases.txt:
universe_err.csv correlation.csv universe.csv correlation_err1.csv universe.csv correlation_err2.csv universe.csv correlation_err3.csv