#!/usr/bin/env python
# coding: utf-8

# # Max-cut problem
# 
# 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]$.
# 
# 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. 
# 
# 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}\}$.
# 
# <img width="450" src="maxcut.png">

# (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
# 
# $$x_{i} = \begin{cases} 
# 1 & \text{if}\quad v_{i}\in\mathcal{S},\\
# -1 & \text{if}\quad v_{i}\in\overline{\mathcal{S}}.
# \end{cases}$$
# 
# 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
# 
# $$\begin{aligned}
# 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).
# \end{aligned}$$
# 
# Explain why the above max-cut problem is equivalent to solving
# 
# $$\underset{x\in\{-1,+1\}^{n}}{\text{minimize}}\quad x^{\top}W x.$$
# 
# Is this optimization problem convex? Why/why not? 
# 
# (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})$.)

# (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.
# 
# Derive the Lagrangian, the Lagrange dual function, and the dual optimization problem for the primal problem obtained in part (a).

# (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).

# (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. 

# (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).
# 
# (Hint: Weak duality.)

# (f) (5+5+10=20 points) Let us now go back to the problem derived in part (a):
# 
# $$\underset{x\in\{-1,+1\}^{n}}{\text{minimize}}\quad x^{\top}W x.$$
# 
# Prove that the above optimization problem can be re-written as
# 
# $$\begin{aligned}
# &\underset{X\in\mathbb{S}^{n}_{+}}{\text{minimize}}\quad \text{trace}\left(WX\right)\\
# &\text{subject to}\quad X_{ii} = 1,\quad i=1,...,n,\\
# & \qquad\qquad\; \text{rank}(X) = 1.
# \end{aligned}$$
# 
# Is the above re-written optimization problem convex? Why/why not?
# 
# Consider yet another modification of the above problem, obtained by ignoring/deleting the rank constraint:
# 
# $$\begin{aligned}
# q^{*} =\, &\underset{X\in\mathbb{S}^{n}_{+}}{\text{minimize}}\quad \text{trace}\left(WX\right)\\
# &\text{subject to}\quad X_{ii} = 1,\quad i=1,...,n.
# \end{aligned}$$
# 
# Is the above optimization problem convex? Why/why not? Write an inequality between $p^{*}$ in part (a) and $q^{*}$ given above.

# (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
# 
# $$\{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\\
# x & 1 & z\\
# y & z & 1\end{bmatrix} \succeq 0
# \Bigg\}$$
# 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}$.
# 
# Is the above 3D set convex? Is it contained in $[-1,1]^{3}$? Mathematically justify your answers.

# (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)).
# 
# (Hint: Consider the dual problem of the dual problem derived in part (b).)

# In[ ]: