{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Max-cut problem\n",
    "\n",
    "An undirected graph $\\mathscr{G} = (\\mathcal{V},\\mathcal{E})$ is defined as a collection of two sets: a set of vertices $\\mathcal{V}$, and a set of edges $\\mathcal{E}$. If there is an edge $e_{ij}\\in\\mathcal{E}$ connecting the vertices $v_{i},v_{j}\\in\\mathcal{V}$, then we can assign an weight $w_{ij} \\geq 0$ to that edge to model the relative importance of that particular edge. Assuming the cardinality of the vertex set $|\\mathcal{V}|=n$ , we normalize the weights as $\\sum_{i\\leq j}w_{ij} = 1$. This gives rise to a weighted directed graph $\\mathscr{G}_{W} = (\\mathcal{V},\\mathcal{E},W)$ where the edge weight matrix $W\\in\\mathbb{R}^{n\\times n}$ is symmetric with elements in $[0,1]$.\n",
    "\n",
    "A \"cut\" in $\\mathscr{G}_{W}$ is simply a partition of the vertex set $\\mathcal{V}$ into two (disjoint) sets: $\\mathcal{S}$ and its complement $\\overline{\\mathcal{S}}:=\\mathcal{V}\\setminus\\mathcal{S}$, that is, $\\mathcal{V}=\\mathcal{S}\\cup\\overline{\\mathcal{S}}$. The \"weight of a cut\" is the sum of weights for those (and only those) edges which connect vertices in $\\mathcal{S}$ to vertices in $\\overline{\\mathcal{S}}$. The \"max-cut problem\" concerns with finding a cut in $\\mathscr{G}_{W}$ that maximizes the weight of cut. \n",
    "\n",
    "In the following example graph with $n=4$ vertices, the \"red solid\" cut is the max-cut (cut weight = 0.7), while the \"blue dashed\" cut is sub-optimal (cut-weight = 0.5). In this example, the red max-cut corresponds to the partition $\\mathcal{V} = \\{v_{1},v_{3}\\} \\cup \\{v_{2},v_{4}\\}$. The sub-optimal blue cut corresponds to the partition $\\mathcal{V} = \\{v_{1},v_{2}\\} \\cup \\{v_{3},v_{4}\\}$.\n",
    "\n",
    "<img width=\"450\" src=\"maxcut.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(a) (5+5=10 points) To formulate the max-cut problem as an optimization problem, let us consider any cut $\\mathcal{V}=\\mathcal{S}\\cup\\overline{\\mathcal{S}}$, and for $i=1,...,n$, assign a variable $x_{i}$ to each vertex of $\\mathscr{G}_{W} = (\\mathcal{V},\\mathcal{E},W)$, as\n",
    "\n",
    "$$x_{i} = \\begin{cases} \n",
    "1 & \\text{if}\\quad v_{i}\\in\\mathcal{S},\\\\\n",
    "-1 & \\text{if}\\quad v_{i}\\in\\overline{\\mathcal{S}}.\n",
    "\\end{cases}$$\n",
    "\n",
    "Next, notice that $(1-x_{i}x_{j}) = 0$ if the vertices $v_{i}$ and $v_{j}$ are in the same set, and $=2$ otherwise. Therefore, the quantity $\\sum_{i<j}w_{ij}(1-x_{i}x_{j})$ is twice the cut weight, and hence the max-cut problem is\n",
    "\n",
    "$$\\begin{aligned}\n",
    "p^{*} := \\underset{x\\in\\{-1,+1\\}^{n}}{\\text{maximize}}\\quad\\displaystyle\\frac{1}{2}\\displaystyle\\sum_{i<j}w_{ij}\\left(1-x_{i}x_{j}\\right).\n",
    "\\end{aligned}$$\n",
    "\n",
    "Explain why the above max-cut problem is equivalent to solving\n",
    "\n",
    "$$\\underset{x\\in\\{-1,+1\\}^{n}}{\\text{minimize}}\\quad x^{\\top}W x.$$\n",
    "\n",
    "Is this optimization problem convex? Why/why not? \n",
    "\n",
    "(Hint: $\\frac{1}{2}\\sum_{i<j}w_{ij}(1-x_{i}x_{j}) = \\frac{1}{4}\\sum_{i,j}w_{ij}(1-x_{i}x_{j})$.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(b) (15 points) Although the constraint set of the optimization problem derived in part (a) is finite, it has cardinality $2^{n}$, and therefore, it is computationally impractical to take enumerative approach to solve it for large $n$. In fact, this optimization problem is known to be NP hard.\n",
    "\n",
    "Derive the Lagrangian, the Lagrange dual function, and the dual optimization problem for the primal problem obtained in part (a)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(c) (10 points) Use the Lagrange dual function derived in part (b) to provide a **simple sub-optimal** (meaning, not the tightest) bound for $p^{*}$ in part (a)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(d) (10 points) Is the dual problem derived in part (b) a convex optimization problem? If \"yes\", then what kind of convex optimization problem is it? If \"no\", then explain why not. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(e) (15+5=20 points) For the example graph with 4 vertices given above, write a code using cvxpy, to solve the dual problem. You need to write the code in your solution notebook. Use the answer of your cvxpy code to write an inequality for $p^{*}$ in part (a).\n",
    "\n",
    "(Hint: Weak duality.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "(f) (5+5+10=20 points) Let us now go back to the problem derived in part (a):\n",
    "\n",
    "$$\\underset{x\\in\\{-1,+1\\}^{n}}{\\text{minimize}}\\quad x^{\\top}W x.$$\n",
    "\n",
    "Prove that the above optimization problem can be re-written as\n",
    "\n",
    "$$\\begin{aligned}\n",
    "&\\underset{X\\in\\mathbb{S}^{n}_{+}}{\\text{minimize}}\\quad \\text{trace}\\left(WX\\right)\\\\\n",
    "&\\text{subject to}\\quad X_{ii} = 1,\\quad i=1,...,n,\\\\\n",
    "& \\qquad\\qquad\\; \\text{rank}(X) = 1.\n",
    "\\end{aligned}$$\n",
    "\n",
    "Is the above re-written optimization problem convex? Why/why not?\n",
    "\n",
    "Consider yet another modification of the above problem, obtained by ignoring/deleting the rank constraint:\n",
    "\n",
    "$$\\begin{aligned}\n",
    "q^{*} =\\, &\\underset{X\\in\\mathbb{S}^{n}_{+}}{\\text{minimize}}\\quad \\text{trace}\\left(WX\\right)\\\\\n",
    "&\\text{subject to}\\quad X_{ii} = 1,\\quad i=1,...,n.\n",
    "\\end{aligned}$$\n",
    "\n",
    "Is the above optimization problem convex? Why/why not? Write an inequality between $p^{*}$ in part (a) and $q^{*}$ given above."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(g) (5+5=10 points) Let us examine the geometric meaning of the constraint set for $q^{*}$ in part (f). This set is called **elliptope**. For $n=3$, the elliptope\n",
    "\n",
    "$$\\{X \\in \\mathbb{S}^{3}_{+} \\:\\mid\\: X_{11} = X_{22} = X_{33} = 1\\} = \\Bigg\\{(x,y,z)\\in\\mathbb{R}^{3} \\:\\mid\\: \\begin{bmatrix} 1 & x & y\\\\\n",
    "x & 1 & z\\\\\n",
    "y & z & 1\\end{bmatrix} \\succeq 0\n",
    "\\Bigg\\}$$\n",
    "can be visualized as a subset of $\\mathbb{R}^{3}$. Write a code to make a 3D plot the above set superimposed with the cube $[-1,1]^{3}$.\n",
    "\n",
    "Is the above 3D set convex? Is it contained in $[-1,1]^{3}$? Mathematically justify your answers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "(h) (5 points) Write and explain the relation between $p^{*}$ (optimal value of the primal problem), $d^{*}$ (optimal value of the dual problem), and $q^{*}$ (optimal value of the problem derived in part (f)).\n",
    "\n",
    "(Hint: Consider the dual problem of the dual problem derived in part (b).)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}