K-means clustering does not guarantee you global optimum (although I'd not call K-means a "heuristic" technique). However you can do this: run K-means a number of times, each time with different random initial centres seed, and obtain a set of final cluster centres each time. If these sets appear similar enough - in the sense that you can easily identify the "same" final centres across the runs - then you are surely close to the global optimum. Then just average those corresponding final centres across the runs and input the obtained averaged centers as initial ones for one final run. That run is almost sure to give you the global optimum solution.
Another, similar to this, trick to obtain "good" initial centres is to randomly split the total sample into subsamples and to perform K-means on each, then again averaging the final centres and running clustering of the total sample. Yet one more way to get "good" initial centres is to run Ward hierarchical clustering first and get K clusters with it, and use their centres as the input to K-means. Read about some variants of K-means initializing.
Under the following conditions (or "assumptions") you are more likely to get at the global optimal solution in K-means clustering:
- there is cluster structure in the data, i.e. the data is not single-cluster;
- your K, the-number-of-clusters specification, is correct;
- the number of variables is not very great: K-means is sensitive to the "curse of dimensionality", with many variables, a preliminary PCA would be a good idea;
- clusters in the data are more or less spherical, and compact in their middle (such as normally distributed); variances in clusters are about equal.
K-means assignes, at each iteration, each object to the closest cluster centre. After all objects were thus assigned, the K centres are updated. It thus appears that a centre moves further towards the set of objects that were already "its" objects. That's why each iteration is an improvement, and the optimum - local or global, dependent on the initial centres choice - is reached. The optimized function is the pooled within-cluster sum-of-squares (because mean is the locus of minimal SS deviations from it), which is equivalent to minimizing the pooled within-cluster sum of pairwise squared euclidean distances normalized by the respective number-of-objects in a cluster.