I am trying to show that the objective function for the K-means clustering is non convex. I was hoping if the experts here can tell me if I am doing it correctly.
$ \min_{z,\mu} L(z,\mu) = \sum_n\sum_k z_{nk}||x_n - \mu_k||^2 $
My first step is to remove the sums and assume the dimensions of $x$ and $\mu$ are both 1.
$ L = z(x^2 + 2x\mu + \mu^2) $
Now I compute the Hessian.
$\dfrac{\partial L}{\partial x} = 2zx - 2\mu z$
$\dfrac{\partial L}{\partial z} = x^2 - 2x\mu + \mu $
$\dfrac{\partial^2 L}{\partial x^2} = 2z$
$\dfrac{\partial^2 L}{\partial z^2} = 0 $
$\dfrac{\partial^2 F}{\partial z \partial x} = 2x - 2\mu$
For a 2x2 hessian to be positive-semi definite, its diagonal entries must be non negative and its determinant positive. For the function above, the determinant is $-(2x-2\mu)$ and thus is always negative. And so it is not jointly convex. Is this correct ? Hello ?