k-Means Clustering

Say we have $n$ points $x_1,x_2,\dots ,x_n$. We want to partition them into $k$ sets $S_1,S_2,\dots ,S_k$ such that the cost of the partition is minimised, $c(S_1,S_2,\dots ,S_k)$:

$$c(S_1,S_2,\dots ,S_k)=\sum _{i=1}^n\underset{j\in [k]}{\min }\left[\begin{array}{c}||x_i-{\mu }_j|{|}_2^2\end{array}\right]$$

Where ${\mu }_i$ is the mid-point of each cluster, i.e. ${\mu }_i=\frac{1}{|S_i|}{\sum }_{j\in S_i}{x}_j$.

Where $||\cdot |{|}_2^2$ is the squared L2 norm (squared Euclidian distance).