{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Quadratic program"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A quadratic program is an optimization problem with a quadratic objective and affine equality and inequality constraints. A common standard form is the following:\n",
    "$$  \n",
    "    \\begin{array}{ll}\n",
    "    \\mbox{minimize}   & (1/2)x^TPx + q^Tx\\\\\n",
    "    \\mbox{subject to} & Gx \\leq h \\\\\n",
    "                      & Ax = b.\n",
    "    \\end{array}\n",
    "$$\n",
    "Here $P \\in \\mathcal{S}^{n}_+$, $q \\in \\mathcal{R}^n$, $G \\in \\mathcal{R}^{m \\times n}$, $h \\in \\mathcal{R}^m$, $A \\in \\mathcal{R}^{p \\times n}$, and $b \\in \\mathcal{R}^p$ are problem data and $x \\in \\mathcal{R}^{n}$ is the optimization variable. The inequality constraint $Gx \\leq h$ is elementwise.\n",
    "\n",
    "A simple example of a quadratic program arises in finance. Suppose we have $n$ different stocks, an estimate $r \\in \\mathcal{R}^n$ of the expected return on each stock, and an estimate $\\Sigma \\in \\mathcal{S}^{n}_+$ of the covariance of the returns. Then we solve the optimization problem\n",
    "$$  \n",
    "    \\begin{array}{ll}\n",
    "    \\mbox{minimize}   & (1/2)x^T\\Sigma x - r^Tx\\\\\n",
    "    \\mbox{subject to} & x \\geq 0 \\\\\n",
    "                      & \\mathbf{1}^Tx = 1,\n",
    "    \\end{array}\n",
    "$$\n",
    "to find a nonnegative portfolio allocation $x \\in \\mathcal{R}^n_+$ that optimally balances expected return and variance of return.\n",
    "\n",
    "When we solve a quadratic program, in addition to a solution $x^\\star$, we obtain a dual solution $\\lambda^\\star$ corresponding to the inequality constraints. A positive entry $\\lambda^\\star_i$ indicates that the constraint $g_i^Tx \\leq h_i$ holds with equality for $x^\\star$ and suggests that changing $h_i$ would change the optimal value."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the following code, we solve a quadratic program with CVXPY."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "The optimal value is 86.89141585569918\n",
      "A solution x is\n",
      "[-1.68244521  0.29769913 -2.38772183 -2.79986015  1.18270433 -0.20911897\n",
      " -4.50993526  3.76683701 -0.45770675 -3.78589638]\n",
      "A dual solution corresponding to the inequality constraints is\n",
      "[ 0.          0.          0.          0.          0.         10.45538054\n",
      "  0.          0.          0.         39.67365045  0.          0.\n",
      "  0.         20.79927156  6.54115873]\n"
     ]
    }
   ],
   "source": [
    "# Import packages.\n",
    "import cvxpy as cp\n",
    "import numpy as np\n",
    "\n",
    "# Generate a random non-trivial quadratic program.\n",
    "m = 15\n",
    "n = 10\n",
    "p = 5\n",
    "np.random.seed(1)\n",
    "P = np.random.randn(n, n)\n",
    "P = P.T@P\n",
    "q = np.random.randn(n)\n",
    "G = np.random.randn(m, n)\n",
    "h = G@np.random.randn(n)\n",
    "A = np.random.randn(p, n)\n",
    "b = np.random.randn(p)\n",
    "\n",
    "# Define and solve the CVXPY problem.\n",
    "x = cp.Variable(n)\n",
    "prob = cp.Problem(cp.Minimize((1/2)*cp.quad_form(x, P) + q.T@x),\n",
    "                 [G@x <= h,\n",
    "                  A@x == b])\n",
    "prob.solve()\n",
    "\n",
    "# Print result.\n",
    "print(\"\\nThe optimal value is\", prob.value)\n",
    "print(\"A solution x is\")\n",
    "print(x.value)\n",
    "print(\"A dual solution corresponding to the inequality constraints is\")\n",
    "print(prob.constraints[0].dual_value)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}