{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Introduction\n", "PyMCEF construct the efficient frontier from given jointly simulated asset returns. \n", "With risk meausre absolute semideviation and fixed target under-performance, the optimizatoin can be reformulated as an Linear Programming problem. \n", "With one single optimization, PyMCEF can find all optimal solutions with risk tolerance $\\lambda\\in [0,\\infty)$, and each optimal solution corresponds with an interval of $\\lambda$.\n", "The correctness of each optimal portfolio and its corresponding interval of $\\lambda$ can be checked against existing Linear Programming softwares.\n", "\n", "The accuracy of PyMCEF is benchmarked against [GLPK](https://www.gnu.org/software/glpk/) through python interface [cvxopt](http://cvxopt.org/).\n", "The speed of PyMCEF is compared with both GLPK and [CLP](https://projects.coin-or.org/Clp) (through its python interface [CyLP](https://github.com/coin-or/CyLP))." ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "### Linear Programming Setup \n", "\n", "Let's denote the random returns of all $N$ assets as a vector Y.\n", "A portfolio is defined by the $N$-vector of weights $\\{w_n\\}_{n=1}^N$.\n", "The reward of a portfolio is defined as its expected return.\n", "\n", "$$E[Y^{T}w]=E[\\sum_{n=1}^{N}w_{n}Y_{n}]$$\n", "\n", "Consider $K$ samples of $Y$: $\\{Y^{k}\\}_{k=1}^{K}$ and their sample\n", "means:\n", "\\begin{eqnarray*}\n", "\\overline{Y}_{n} & = & \\frac{1}{K}\\sum_{k=1}^{K}Y_{n}^{k},\\\\\n", "\\overline{Y} & = & \\left[\\overline{Y}_{1},\\dots,\\overline{Y}_{n}\\right]^{T}.\n", "\\end{eqnarray*}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Wtih absolute semideviation as risk measure, the optmization becomes the following:\n", "\n", "\\begin{eqnarray}\n", "\\underset{{u_{k},w_{n},v_{k}}}{\\mathrm{argmin}} & \\frac{1}{K}\\sum_{k=1}^{K}u_{k}-\\lambda\\sum_{n=1}^{N}w_{n}\\overline{Y}_{n}\\\\\n", "\\mathrm{subject\\ to} & \\sum_{n=1}^{N}w_{n} & =1\\\\\n", "& u_{k}+\\sum_{n=1}^{N}w_{n}(Y_{n}^{k}-\\overline{Y}_{n})-v_{k} & =0\\quad \\forall k=1,\\dots,K \\\\\n", " & w_{n},u_{k},v_{k} & \\ge0.\n", "\\end{eqnarray}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "With fixed target under-performance as risk measure, \n", "the optimization becomes the following:\n", "\n", "\\begin{eqnarray}\n", "\\underset{{u_{k},w_{n},v_{k}}}{\\mathrm{argmin}} & \\frac{1}{K}\\sum_{k=1}^{K}u_{k}-\\lambda\\sum_{n=1}^{N}w_{n}\\overline{Y}_{n}\\\\\n", "\\mathrm{subject\\ to} & \\sum_{n=1}^{N}w_{n} & =1\\\\\n", " & u_{k}+\\sum_{n=1}^{N}w_{n}Y_{n}^{k}-v_{k} & =t\\quad \\forall k=1,\\dots,K \\\\\n", " & w_{n},u_{k},v_{k} & \\ge0,\n", "\\end{eqnarray}\n", "where $t$ is the target, and $u_k$ are auxilary variables and $v_k$ are slack variables. " ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "# Benchmark Problems\n", "\n", "We start with a small starter problem where the details of LP problem and the optimal solutions can be displayed. \n", "After that, we test with larger problem to compare the results of PyMCEF and GLPK." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Starter problem\n", "\n", "Consider an investment universe with 3 assets, whose cross sectional returns have 3 equally possible outcomes:\n", "\n", "| | Asset 1 | Asset 2 | Asset 3 |\n", "|-----------|---------|---------|---------|\n", "| Outcome 1 | 10 | 1 | 5 |\n", "| Outcome 2 | -2 | 0 | 2 |\n", "| Outcome 3 | -3 | 1 | -3 |\n", "We use the fixed-target under-performance as risk measure and choose the fixed-target as $t=0$.\n", "In this case, the linear programming problem is:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\\begin{align*}\n", "\\underset{\\mathrm{u_{1},u_{2},u_{3},w_{1},w_{2},w_{3},v_{1},v_{2},v_{3}\\ge0}}{\\mathrm{argmin}} & \\frac{1}{3}u_{1}+\\frac{1}{3}u_{2}+\\frac{1}{3}u_{3}-\\lambda\\left(\\frac{5}{3}w_{1}+\\frac{2}{3}w_{2}+\\frac{1}{3}w_{3}\\right)\\\\\n", "\\left[\\begin{array}{ccccccccc}\n", "0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0\\\\\n", "1 & & & 10 & 1 & 5 & -1\\\\\n", " & 1 & & -2 & 0 & 2 & & -1\\\\\n", " & & 1 & -3 & 1 & -3 & & & -1\n", "\\end{array}\\right] & \\left[\\begin{array}{c}\n", "u_{1}\\\\\n", "u_{2}\\\\\n", "u_{3}\\\\\n", "w_{1}\\\\\n", "w_{2}\\\\\n", "w_{3}\\\\\n", "v_{1}\\\\\n", "v_{2}\\\\\n", "v_{3}\n", "\\end{array}\\right]=\\left[\\begin{array}{c}\n", "1\\\\\n", "0\\\\\n", "0\\\\\n", "0\n", "\\end{array}\\right]\n", "\\end{align*}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "With PyMCEF we can obtain all the optimal solutions, with $\\lambda$ varying from $+\\infty$ to $0$." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": true }, "outputs": [], "source": [ "%%capture\n", "from pymcef import SimpleEF, RiskMeasure\n", "import numpy as np\n", "# notice that each row corresponds of all realizations of one asset return\n", "\n", "returns = np.array([10,-2,-3,1,0,1,5,2,-3]).reshape((3, 3))\n", "labels = ['Asset 1', 'Asset 2', 'Asset 3']\n", "sol = SimpleEF(training_set = returns, \\\n", " risk_measure = RiskMeasure.FixTargetUnderPerformance, \n", " target_return = 0,\\\n", " asset_names = labels)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The solutions are:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "hide_input": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Efficient portfolio: 1\n", " Risk tolerance interval: (4.0, inf)\n", " Positions: \n", " Asset 1\n", " 1.0\n", "Efficient portfolio: 1\n", " Risk tolerance interval: (1.6, 4.0)\n", " Positions: \n", " Asset 1, Asset 3\n", " 0.5, 0.5\n", "Efficient portfolio: 3\n", " Risk tolerance interval: (0.0, 1.6)\n", " Positions: \n", " Asset 1, Asset 2, Asset 3\n", " 0.125, 0.75, 0.125\n" ] } ], "source": [ "i = 1\n", "for prt in sol.frontier_in_sample:\n", " print(\"Efficient portfolio: \" + str(i))\n", " lbd_l, lbd_u = prt['lambda_l'], prt['lambda_u']\n", " print(\" Risk tolerance interval: (\" + str(lbd_l) + \", \" + str(lbd_u) + \")\")\n", " ws = prt['weight']\n", " ks = [labels[i] for i in ws.keys()]\n", " vs = [str(v) for v in ws.values()]\n", " print(\" Positions: \")\n", " print(\" \" + \", \".join(ks))\n", " print(\" \" + \", \".join(vs))\n", " i += 1\n", "#sol.frontier_in_sample[0]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we choose various risk tolerances and use cvxopt(GLPK) to obtain the optimal solutions. \n", "Each solution obtained by cvxop should agree with one of the three solutions produced by PyMCEF, whose interval of $\\lambda$ covers that particular risk tolerance used by cvxop." ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": true }, "outputs": [], "source": [ "from cvxopt import solvers, matrix\n", "solvers.options['show_progress'] = False\n", "\n", "def Solve_With_GLPK(returns, lbds, t):\n", " numSims = returns.shape[0]\n", " numAssets = returns.shape[1]\n", " idn = np.eye(numSims)\n", " A_ub = - np.hstack((idn, returns)) # <= -t\n", " b_ub = np.array([-t]*numSims)\n", " c0 = returns.mean(axis=0)\n", " c1 = np.array([1.0/numSims] * numSims)\n", " A_eq = np.matrix([0.0]*numSims + [1.0] * numAssets)\n", " b_eq = np.array([1.0])\n", "\n", " G = matrix(np.vstack((A_ub, -np.eye(numSims + numAssets))))\n", " h = matrix([-t]*numSims + [0.0] * (numSims + numAssets))\n", " A = matrix([0.0]*numSims + [1.0] * numAssets, (1, numSims + numAssets))\n", " b = matrix([1.0])\n", " weights_cvxopt = np.zeros((len(lbds), numAssets))\n", " for i in range(len(lbds)):\n", " lbd = lbds[i]\n", " c = matrix(np.hstack((c1, -lbd * c0)))\n", " sol_cvxopt = solvers.lp(c, G, h, A=A, b=b, solver='glpk')\n", " tmp = np.array(sol_cvxopt['x'][-3:])\n", " weights_cvxopt[i, :] = tmp[:, 0]\n", " return weights_cvxopt" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "format": "row" }, "outputs": [ { "data": { "text/html": [ "
Risk tolerance | Asset 1 | Asset 2 | Asset 3 |
5.0 | 1.0 | 0.0 | 0.0 |
4.5 | 1.0 | 0.0 | 0.0 |
4.0 | 0.5 | 0.0 | 0.5 |
3.5 | 0.5 | 0.0 | 0.5 |
3.0 | 0.5 | 0.0 | 0.5 |
2.5 | 0.5 | 0.0 | 0.5 |
2.0 | 0.5 | 0.0 | 0.5 |
1.5 | 0.125 | 0.75 | 0.125 |
1.0 | 0.125 | 0.75 | 0.125 |
0.5 | 0.125 | 0.75 | 0.125 |
0.0 | 0.125 | 0.75 | 0.125 |