{
 "metadata": {
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Non-Convex Extensions"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Many non-convex optimization problems can be solved exactly or approximately via a sequence of convex optimization problems. CVXPY can easily be extended to handle such non-convex problems. The ``cvxpy/examples/mixed_integer`` package uses the Alternating Direction Method of Multipliers (ADMM) as a heuristic for mixed integer problems.\n",
      "\n",
      "The following code performs feature selection on a linear kernel SVM classifier using a cardinality constraint:\n"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from cvxpy import *\n",
      "import mixed_integer as mi\n",
      "import cvxopt\n",
      "\n",
      "# Construct problem.\n",
      "gamma = Parameter(nonneg=True)\n",
      "gamma.value = 0.1\n",
      "# 'a' is a variable constrained to have at most 6 non-zero entries.\n",
      "a = SparseVar(n,nonzeros=6)\n",
      "b = Variable()\n",
      "\n",
      "slack = [pos(1 - label*(sample.T*a - b)) for (label,sample) in data]\n",
      "objective = Minimize(norm2(a) + gamma*sum(slack))\n",
      "p = Problem(objective)\n",
      "# Extensions can attach new solve methods to the CVXPY Problem class.\n",
      "p.solve(method=\"admm\")\n",
      "\n",
      "# Count misclassifications.\n",
      "error = 0\n",
      "for label,sample in data:\n",
      "    if not label*(a.value.T*sample - b.value)[0] >= 0:\n",
      "        error += 1\n",
      "\n",
      "print \"%s misclassifications\" % error\n",
      "print a.value\n",
      "print b.value\n",
      "\n",
      "N = 50\n",
      "M = 40\n",
      "n = 10\n",
      "data = []\n",
      "for i in range(N):\n",
      "    data += [(1, cvxopt.normal(n, mean=1.0, std=2.0))]\n",
      "for i in range(M):\n",
      "    data += [(-1, cvxopt.normal(n, mean=-1.0, std=2.0))]\n",
      "\n",
      "# Construct problem.\n",
      "gamma = Parameter(nonneg=True)\n",
      "gamma.value = 0.1\n",
      "# 'a' is a variable constrained to have at most 6 non-zero entries.\n",
      "a = mi.SparseVar(n, nonzeros=6)\n",
      "b = Variable()\n",
      "\n",
      "slack = [pos(1 - label*(sample.T*a - b)) for (label, sample) in data]\n",
      "objective = Minimize(norm(a, 2) + gamma*sum(slack))\n",
      "p = Problem(objective)\n",
      "# Extensions can attach new solve methods to the CVXPY Problem class.\n",
      "p.solve(method=\"admm\")\n",
      "\n",
      "# Count misclassifications.\n",
      "errors = 0\n",
      "for label, sample in data:\n",
      "    if label*(sample.T*a - b).value < 0:\n",
      "        errors += 1\n",
      "\n",
      "print \"%s misclassifications\" % errors\n",
      "print a.value\n",
      "print b.value"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}