{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "title: Finance\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Originally Contributed by**: Arpit Bhatia"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Optimization models play an increasingly important role in financial decisions.\n",
    "Many computational finance problems can be solved efficiently using modern optimization techniques.\n",
    "In this tutorial we will discuss 3 such examples.\n",
    "The first two are taken from the book Optimization Methods in Finance[[1]](#c1),\n",
    "while the third is the famous Markowitz Portfolio Optimization problem with data from\n",
    "lecture notes from a course taught at Georgia Tech[[2]](#c2)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "using JuMP\n",
    "using GLPK"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Short Term Financing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Corporations routinely face the problem of financing short term cash commitments such as the following:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Month**        |Jan    |Feb    |Mar    |Apr    |May    |Jun\n",
    ":-----:          |:-----:|:-----:|:-----:|:-----:|:-----:|:-----:\n",
    "**Net Cash Flow**|-150   |-100   |200    |-200   |50     |300"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Net cash flow requirements are given in thousands of dollars. The company has the following sources of funds:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- A line of credit of up to $100K at an interest rate of 1% per month,\n",
    "- In any one of the first three months, it can issue 90-day commercial paper bearing a total interest of 2% for the 3-month period,\n",
    "- Excess funds can be invested at an interest rate of 0.3% per month."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our task is to find out the most economical way to use these 3 sources such that\n",
    "we end up with the most amount of money at the end of June.\n",
    "We model this problem in the following manner:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will use the following decision variables:\n",
    "- the amount $u_{i}$ drawn from the line of credit in month $i$\n",
    "- the amount $v_{i}$ of commercial paper issued in month $i$\n",
    "- the excess funds $w_{i}$ in month $i$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we have three types of constraints:\n",
    "1. for every month, cash inflow = cash outflow for each month\n",
    "2. upper bounds on $u_{i}$\n",
    "3. nonnegativity of the decision variables $u_{i}$, $v_{i}$ and $w_{i}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our objective will be to simply maximimse the company's wealth in June, which say we represent with the variable $m$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "objective_value(financing) = 92.49694915254233\n"
     ]
    }
   ],
   "source": [
    "financing = Model(GLPK.Optimizer)\n",
    "\n",
    "@variables(financing, begin\n",
    "    0 <= u[1:5] <= 100\n",
    "    0 <= v[1:3]\n",
    "    0 <= w[1:5]\n",
    "    m\n",
    "end)\n",
    "\n",
    "@objective(financing, Max, m) # Money at the end of June\n",
    "\n",
    "@constraints(financing, begin\n",
    "    u[1] + v[1] - w[1] == 150 # January\n",
    "    u[2] + v[2] - w[2] - 1.01u[1] + 1.003w[1] == 100 # February\n",
    "    u[3] + v[3] - w[3] - 1.01u[2] + 1.003w[2] == -200 # March\n",
    "    u[4] - w[4] - 1.02v[1] - 1.01u[3] + 1.003w[3] == 200 # April\n",
    "    u[5] - w[5] - 1.02v[2] - 1.01u[4] + 1.003w[4] == -50 # May\n",
    "    -m - 1.02v[3] - 1.01u[5] + 1.003w[5] == -300 # June\n",
    "end)\n",
    "\n",
    "optimize!(financing)\n",
    "@show objective_value(financing);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Combinatorial Auctions\n",
    "In many auctions, the value that a bidder has for a set of items may not be\n",
    "the sum of the values that he has for individual items.\n",
    "It may be more or it may be less.\n",
    "Examples are equity trading, electricity markets, pollution right auctions and auctions for airport landing slots.\n",
    "To take this into account, combinatorial auctions allow the bidders to submit bids on combinations of items."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let $M=\\{1,2, \\ldots, m\\}$ be the set of items that the auctioneer has to sell.\n",
    "A bid is a pair $B_{j}=\\left(S_{j}, p_{j}\\right)$ where $S_{j} \\subseteq M$ is a nonempty set of items and\n",
    "$p_{j}$ is the price offer for this set.\n",
    "Suppose that the auctioneer has received $n$ bids $B_{1}, B_{2}, \\ldots, B_{n} .$\n",
    "The goal of this problem is to help an auctioneer determine the winners in order to maximize his revenue."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We model this problem by taking a decision variable $y_{j}$ for every bid.\n",
    "We add a constraint that each item $i$ is sold at most once. This gives us the following model:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{align*}\n",
    "\\max && \\sum_{i=1}^{n} p_{j} y_{j} \\\\\n",
    "\\text { s.t. }  && \\sum_{j : i \\in S_{j}} y_{j} \\leq 1 && \\forall i=\\{1,2 \\ldots m\\} \\\\\n",
    "&& y_{j} \\in\\{0,1\\} && \\forall j \\in\\{1,2 \\ldots n\\}\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "objective_value(auction) = 21.0\n",
      "value.(y) = [1.0, 1.0, 1.0, 0.0, 0.0, 0.0]\n"
     ]
    }
   ],
   "source": [
    "bid_values = [6 3 12 12 8 16]\n",
    "bid_items = [[1], [2], [3 4], [1 3], [2 4], [1 3 4]]\n",
    "\n",
    "auction = Model(GLPK.Optimizer)\n",
    "@variable(auction, y[1:6], Bin)\n",
    "@objective(auction, Max, sum(y' .* bid_values))\n",
    "for i in 1:6\n",
    "    @constraint(auction, sum(y[j] for j in 1:6 if i in bid_items[j]) <= 1)\n",
    "end\n",
    "\n",
    "optimize!(auction)\n",
    "\n",
    "@show objective_value(auction);\n",
    "@show value.(y);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Portfolio Optimization\n",
    "Suppose we are considering investing 1000 dollars in three non-dividend paying stocks,\n",
    "IBM (IBM), Walmart (WMT), and Southern Electric (SEHI), for a onemonth period.\n",
    "This means we will use the money to buy shares of the three stocks at the current market prices,\n",
    "hold these for one month, and sell the shares off at the prevailing market prices at the end of the month.\n",
    "As a rational investor, we hope to make some profit out of this endeavor, i.e.,\n",
    "the return on our investment should be positive.\n",
    "Suppose we bought a stock at $p$ dollars per share in the beginning of the month,\n",
    "and sold it off at $s$ dollars per share at the end of the month.\n",
    "Then the one-month return on a share of the stock is $ \\frac{s-p}{p} $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since the stock prices are quite uncertain, so is the end-of-month return on our investment.\n",
    "Our goal is to invest in such a way that the expected end-of-month return is at least $50.00 or 5%.\n",
    "Furthermore, we want to make sure that the “risk” of not achieving our desired return is minimum."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that we are solving the problem under the following assumptions:\n",
    "1. We can trade any continuum of shares.\n",
    "2. No short-selling is allowed.\n",
    "3. There are no transaction costs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We model this problem by taking decision variables $x_{i}, i=1,2,3,$ denoting the dollars invested in each of the 3 stocks.\n",
    "Let us denote by $\\tilde{r}_{i}$ the random variable corresponding to the monthly return\n",
    "(increase in the stock price) per dollar for stock $i .$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then, the return (or profit) on $x_{i}$ dollars invested in stock $i$ is $\\tilde{r}_{i} x_{i},$ and\n",
    "the total (random) return on our investment is $\\sum_{i=1}^{3} \\tilde{r}_{i} x_{i} .$\n",
    "The expected return on our investment is then\n",
    "$\\mathbb{E}\\left[\\sum_{i=1}^{3} \\tilde{r}_{i} x_{i}\\right]=\\sum_{i=1}^{3} \\overline{r}_{i} x_{i},$\n",
    "where $\\overline{r}_{i}$ is the expected value of the $\\tilde{r}_{i} .$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we need to quantify the notion of “risk” in our investment.\n",
    "Markowitz, in his Nobel prize winning work, showed that a rational investor’s notion of minimizing risk\n",
    "can be closely approximated by minimizing the variance of the return of the investment portfolio.\n",
    "This variance is given by:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\operatorname{Var}\\left[\\sum_{i=1}^{3} \\tilde{r}_{i} x_{i}\\right] = \\sum_{i=1}^{3} \\sum_{j=1}^{3} x_{i} x_{j} \\sigma_{i j}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "where $\\sigma_{i j}$ is the covariance of the return of stock $i$ with stock $j$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the right hand side of the equation is the most reduced form of the expression and\n",
    "we have not shown the intermediate steps involved in getting to this form.\n",
    "We can also write this equation as:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\operatorname{Var}\\left[\\sum_{i=1}^{3} \\tilde{r}_{i} x_{i}\\right] =x^{T} Q x\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Where $Q$ is the covariance matrix for the random vector $\\tilde{r}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, we can write the model as:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{align*}\n",
    "\\min x^{T} Q x \\\\\n",
    "\\text { s.t. } \\sum_{i=1}^{3} x_{i} \\leq 1000.00 \\\\\n",
    "\\overline{r}^{T} x \\geq 50.00 \\\\\n",
    "x \\geq 0\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "After that long discussion, lets now use JuMP to solve the portfolio optimization problem for the data given below."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| Month        |  IBM     |  WMT    |  SEHI  |\n",
    "|--------------|----------|---------|--------|\n",
    "| November-00  |  93.043  |  51.826 |  1.063 |\n",
    "| December-00  |  84.585  |  52.823 |  0.938 |\n",
    "| January-01   |  111.453 |  56.477 |  1.000 |\n",
    "| February-01  |  99.525  |  49.805 |  0.938 |\n",
    "| March-01     |  95.819  |  50.287 |  1.438 |\n",
    "| April-01     |  114.708 |  51.521 |  1.700 |\n",
    "| May-01       |  111.515 |  51.531 |  2.540 |\n",
    "| June-01      |  113.211 |  48.664 |  2.390 |\n",
    "| July-01      |  104.942 |  55.744 |  3.120 |\n",
    "| August-01    |  99.827  |  47.916 |  2.980 |\n",
    "| September-01 |  91.607  |  49.438 |  1.900 |\n",
    "| October-01   |  107.937 |  51.336 |  1.750 |\n",
    "| November-01  |  115.590 |  55.081 |  1.800 |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Float64,2}:\n",
       " 0.018641    0.00359853  0.00130976\n",
       " 0.00359853  0.00643694  0.00488727\n",
       " 0.00130976  0.00488727  0.0686828"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "using Statistics # Useful for calculations\n",
    "using Ipopt      # Ipopt since our objective is quadratic\n",
    "\n",
    "stock_data = [\n",
    "93.043 51.826 1.063;\n",
    "84.585 52.823 0.938;\n",
    "111.453 56.477 1.000;\n",
    "99.525 49.805 0.938;\n",
    "95.819 50.287 1.438;\n",
    "114.708 51.521 1.700;\n",
    "111.515 51.531 2.540;\n",
    "113.211 48.664 2.390;\n",
    "104.942 55.744 3.120;\n",
    "99.827 47.916 2.980;\n",
    "91.607 49.438 1.900;\n",
    "107.937 51.336 1.750;\n",
    "115.590 55.081 1.800;\n",
    "]\n",
    "\n",
    "# Calculating stock returns\n",
    "\n",
    "stock_returns = Array{Float64}(undef, 12, 3)\n",
    "\n",
    "for i in 1:12\n",
    "    stock_returns[i, :] = (stock_data[i + 1, :] .- stock_data[i, :]) ./ stock_data[i, :]\n",
    "end\n",
    "\n",
    "# Calculating the expected value of monthly return\n",
    "\n",
    "r = [Statistics.mean(stock_returns[:,1]) Statistics.mean(stock_returns[:,2]) Statistics.mean(stock_returns[:,3])]'\n",
    "\n",
    "# Calculating the covariance matrix Q\n",
    "\n",
    "Q = Statistics.cov(stock_returns)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "******************************************************************************\n",
      "This program contains Ipopt, a library for large-scale nonlinear optimization.\n",
      " Ipopt is released as open source code under the Eclipse Public License (EPL).\n",
      "         For more information visit http://projects.coin-or.org/Ipopt\n",
      "******************************************************************************\n",
      "\n",
      "objective_value(portfolio) = 22634.41784988414\n",
      "value.(x) = [497.04552984986407, 0.0, 502.9544801594808]\n"
     ]
    }
   ],
   "source": [
    "# JuMP Model\n",
    "\n",
    "portfolio = Model(optimizer_with_attributes(Ipopt.Optimizer, \"print_level\" => 0))\n",
    "@variable(portfolio, x[1:3] >= 0)\n",
    "@objective(portfolio, Min, x' * Q * x)\n",
    "@constraint(portfolio, sum(x) <= 1000)\n",
    "@constraint(portfolio, sum(r .* x) >= 50)\n",
    "\n",
    "optimize!(portfolio)\n",
    "\n",
    "@show objective_value(portfolio);\n",
    "@show value.(x);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### References\n",
    "<a id='c1'></a>\n",
    "1. Cornuéjols, G., Peña, J., & Tütüncü, R. (2018). <i>Optimization Methods in Finance</i>. Cambridge: Cambridge University Press. doi:10.1017/9781107297340\n",
    "<a id='c2'></a>\n",
    "2. Ahmed, S. ISyE6669: Deterministic Optimization. Available at: https://www2.isye.gatech.edu/~sahmed/isye6669/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.5.1",
   "language": "julia",
   "name": "julia-1.5"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}