Evaluative Assignment - Efficient Frontier
For this assignment, write a program to find the efficient frontier - the optimal set of portfolios, given a universe of assets and their correlations. Please note the Academic Integrity section.
Part One
Write a program "efficient_frontier", which takes two command line arguments:
1. 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.
2. The name of the file containing the correlation matrix for the universe of assets.
Provided Data
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, investment- grade corporate bonds, inflation-linked, medium-term (7-10yr) US Treasury bonds, and short-term (1- 3yr) 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.)
Efficient Frontier
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 the portion of the portfolio invested in each asset. These weights sum to 1 (i.e., 100%). The 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
Where
��� = $%%��������������� = $%%��������������� ! " # "# " # " # "#
• ���" = weight of the ith asset in the portfolio
• ���������"# = covariance between the ith and jth assets
• ���" = standard deviation of the rates of return for the ith asset
• ���"# = correlation between the ith and jth assets
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)
Rate of Return 1%
2%
3%
4%
Volatility 0.78% 1.09% 1.59% 2.13%
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. Additionally, this document demonstrates how to utilize a linear system of equations to perform the optimization.
Part Two
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%
Solving Systems of Linear Equations
The code built in the Gaussian assignment is sufficient to solve the system of equations in this assignment. As an alternative, you can use the Eigen package, a well-documented, well-tested, and frequently used linear algebra package for C++:
Eigen Installation
Technically, Eigen is 100% implemented in header (include) files, and as such, you could simply copy the Eigen folder from a release into your project folder. However, it is much more convenient to install the package such that it can be used across multiple projects. The following commands download a release package and extract the header files into /usr/local/include. Most environments will have this location available to the compiler by default. As such, you would use #include <Eigen/Dense> to include the library in your code. (If you copied the header files into your project, then use #include "Eigen/Dense".) Difference between #include <filename> and #include "filename"
cd /tmp/
wget
cd eigen-3.4.0
sudo cp -R Eigen /usr/local/include
cd /tmp
rm -rf eigen-3.4.0*
Implementation Notes
• As mentioned, the executable must be named “efficient_frontier”.
• You must provide a Makefile. Recommended C++ version: std=C++17
• The Makefile must have a target of “efficient_frontier” and “clean”.
• 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.
• If you plan to use Eigen, spend some time getting comfortable with it. Start with the “Getting
Started” page:
• Think about what errors may exist in the data files. You do not need to perform any type of data
correction. When you 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 checks as close to the initial parsing as possible. Do not rely on checking invalid data after processing.
• Specific hints on error-checking:
o Isyour'-r'optionoptional?Itshouldbe.
o Doyoucheckfortwofilesascommandlinearguments?
o Doyouverifythateachfileexists?
o Doyouverifythateachfilehasalltherequiredvalues?Forexample,ifit'sanNbyN
matrix, does each of the N rows have N numeric values?
o Doyouacceptspacesinassetnames?
o Doyouverifythateachinputthatshouldbenumericisnumeric?
o Forthisassignment,valuesthatshouldbenumericbutaren't(nulls,spaces,words,
etc...) can be reported as errors.
• Look towards using more of an object-oriented design. Nouns typically specify
classes/properties, while verbs represent potential behaviors.
o AnAssethasaname,averagerateofreturn,andstandarddeviation.
o APortfoliohasalistofweightsandalistofAssets,fromwhichtheportfoliovolatility
and rate of return can be calculated. You can add more attributes and functions. o Otherclassesandfilesasneededtosupportparsingandoptimization.
Unrestricted Notes
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.
+��� ���$./���2=/02 ���0��� ���
��� 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
+1 1 ... 1.
������...��� %&'
(from the right-hand side of equations 6, 7, 10)
��� is a column vector of the form: + 1 . ���
/02 = ���
0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 1.0000 Rp
!
Now, solve a linear system of equations of the form ������ = ���. x contains the vector of weights and the Lagrange multipliers.
The solver you built for the Gaussian assignment is sufficient for this problem. If you use the Eigen package,
Restricted Notes
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 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 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.
Approach
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.
Example Data:
Suppose weights 1 and 3 were negative. The updated matrix and vector becomes: (rate = .1)
Grader
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 test cases. The assignment grader will run your test cases against your submission and the reference implementation. You 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 may create additional files (e.g. a file with bad asset data) as part of your submission. Sample testcases.txt:
#error
universe_err.csv correlation.csv
universe.csv correlation_err1.csv
universe.csv correlation_err2.csv
universe.csv correlation_err3.csv
#success
universe.csv correlation.csv
Your testcases.txt will not be graded. The grading breakdown will be 95% for test cases generated by the instructors and 5% for a code review.
Submission
Submit your Makefile, all associated code files, testcases.txt, and any associated data files to the Gradescope assignment. For the data files, you do need to include the provided data files if they are part of your test cases.
Academic Integrity
Note: This is an evaluative assignment! By submitting this assignment, you agree that you have adhered to the following rules:
• Your work must be your own!
• You may NOT consult with other students about:
o high-level approaches,
o how to implement your algorithm in code, or o how to debug your code.
(Basically, you may not discuss anything particular to this assignment).
• You may NOT look at another student's code, nor show your code to anyone else.
• You are responsible for keeping your code private.
• You may not look for solutions to this or similar problems online.
• You may not use code from any other source besides what is listed here.
• You may not use any AI assistive technology (e.g., ChatGPT)
• You MAY consult Programming: Principles and Practices Using C++.
• You MAY consult any docable page provided for this class.
• You MAY consult cppreference.com, cplusplus.com, eigen.tuxfamily.org
• You MAY consult any C++ book on the O'Reilly Learning Platform
• You MAY consult notes you wrote in your notebook.
• You MAY consult the man pages.
• You MAY ask the professor or TAs for clarification on the assignment.
If you use code from one of the approved sources, you should reference that source in a comment just prior to the function or code section. This includes any prior assignments.
