{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Second-order cone program"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A second-order cone program (SOCP) is an optimization problem of the form\n",
    "$$  \n",
    "    \\begin{array}{ll}\n",
    "    \\mbox{minimize}   & f^Tx\\\\\n",
    "    \\mbox{subject to} & \\|A_ix + b_i\\|_2 \\leq c_i^Tx + d_i, \\quad i=1,\\ldots,m \\\\\n",
    "                      & Fx = g,\n",
    "    \\end{array}\n",
    "$$\n",
    "where $x \\in \\mathcal{R}^{n}$ is the optimization variable and $f \\in \\mathcal{R}^n$, $A_i \\in \\mathcal{R}^{n_i \\times n}$, $b_i \\in \\mathcal{R}^{n_i}$, $c_i \\in \\mathcal{R}^n$, $d_i \\in \\mathcal{R}$, $F \\in \\mathcal{R}^{p \\times n}$, and $g \\in \\mathcal{R}^p$ are problem data.\n",
    "\n",
    "An example of an SOCP is the robust linear program\n",
    "$$  \n",
    "    \\begin{array}{ll}\n",
    "    \\mbox{minimize}   & c^Tx\\\\\n",
    "    \\mbox{subject to} & (a_i + u_i)^Tx \\leq b_i \\textrm{ for all } \\|u_i\\|_2 \\leq 1, \\quad i=1,\\ldots,m,\n",
    "    \\end{array}\n",
    "$$\n",
    "where the problem data $a_i$ are known within an $\\ell_2$-norm ball of radius one. The robust linear program can be rewritten as the SOCP\n",
    "$$  \n",
    "    \\begin{array}{ll}\n",
    "    \\mbox{minimize}   & c^Tx\\\\\n",
    "    \\mbox{subject to} & a_i^Tx + \\|x\\|_2 \\leq b_i, \\quad i=1,\\ldots,m,\n",
    "    \\end{array}\n",
    "$$\n",
    "\n",
    "When we solve a SOCP, in addition to a solution $x^\\star$, we obtain a dual solution $\\lambda_i^\\star$ corresponding to each second-order cone constraint. A non-zero $\\lambda_i^\\star$ indicates that the constraint $ \\|A_ix + b_i\\|_2 \\leq c_i^Tx + d_i$ holds with equality for $x^\\star$ and suggests that changing $d_i$ would change the optimal value."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the following code, we solve an SOCP with CVXPY."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The optimal value is -9.582695716265503\n",
      "A solution x is\n",
      "[ 1.40303325  2.4194569   1.69146656 -0.26922215  1.30825472 -0.70834842\n",
      "  0.19313706  1.64153496  0.47698583  0.66581033]\n",
      "SOC constraint 0 dual variable solution\n",
      "[ 0.61662526  0.35370661 -0.02327185  0.04253095  0.06243588  0.49886837]\n",
      "SOC constraint 1 dual variable solution\n",
      "[ 0.35283078 -0.14301082  0.16539699 -0.22027817  0.15440264  0.06571645]\n",
      "SOC constraint 2 dual variable solution\n",
      "[ 0.86510445 -0.114638   -0.449291    0.37810251 -0.6144058  -0.11377797]\n"
     ]
    }
   ],
   "source": [
    "# Import packages.\n",
    "import cvxpy as cp\n",
    "import numpy as np\n",
    "\n",
    "# Generate a random feasible SOCP.\n",
    "m = 3\n",
    "n = 10\n",
    "p = 5\n",
    "n_i = 5\n",
    "np.random.seed(2)\n",
    "f = np.random.randn(n)\n",
    "A = []\n",
    "b = []\n",
    "c = []\n",
    "d = []\n",
    "x0 = np.random.randn(n)\n",
    "for i in range(m):\n",
    "    A.append(np.random.randn(n_i, n))\n",
    "    b.append(np.random.randn(n_i))\n",
    "    c.append(np.random.randn(n))\n",
    "    d.append(np.linalg.norm(A[i]@x0 + b, 2) - c[i].T@x0)\n",
    "F = np.random.randn(p, n)\n",
    "g = F@x0\n",
    "\n",
    "# Define and solve the CVXPY problem.\n",
    "x = cp.Variable(n)\n",
    "# We use cp.SOC(t, x) to create the SOC constraint ||x||_2 <= t.\n",
    "soc_constraints = [\n",
    "    cp.SOC(c[i].T@x + d[i], A[i]@x + b[i]) for i in range(m)\n",
    "]\n",
    "prob = cp.Problem(cp.Minimize(f.T@x),\n",
    "                  soc_constraints + [F@x == g])\n",
    "prob.solve()\n",
    "\n",
    "# Print result.\n",
    "print(\"The optimal value is\", prob.value)\n",
    "print(\"A solution x is\")\n",
    "print(x.value)\n",
    "for i in range(m):\n",
    "    print(\"SOC constraint %i dual variable solution\" % i)\n",
    "    print(soc_constraints[i].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
}