SemiDefinitePrograms Consider an undirected graph $G=(V,E)$ with an even number of

nodes and non$-$negative weights $w_{ij}$ for each edge in $E($and $w_{ij}=0$ if $(i,j)!$inE $).$ We would

like to partition the nodes in $V$ into two sets $S$ and $\frac{V}{\frac{?}{?}}S$ of equal cardinality so that the total

weight of the cut is maximized.

$($a$)$ Formulate this problem as a boolean optimization.

$($b$)$ Apply the lifting idea to construct an SDP relaxation for the boolean optimization. Make sure that your optimization involves only a matrix variable $x$ of size $|V||V|$ and noother variables.

use the following hint please to answer the question:

use a vector x belongs to Rn to represrent the partition$/$cut$.$ i$.$e$.$ xi $=1$ if the node i belongs to S and xi $=-1$ if the node i belongs to V$\backslash$S$.$ Apply the lifting idea and define a matrix

X $=$ x$*$xt $($ transpose $)$ with a rank $1$ constraint