I am not able to give you a perfect answer, but I can share some knowledge that I hope can be useful toyou.

With k-means in general the approximation found can be arbitrarily bad with respect to the objective function compared to the optimal clustering. With the proper initialization, you can guarantee an approximation ratio O(log k) in expectation, but the algorithm is based on randomness, so you can't in general reach for sure the optimum, and in practise you will find a solution which is often very far from the optimum. If what you reach is a local optimum will also depend on the similarity function that you use to evaluate the distances of cluster points to the centroid of their assigned clusters. The standard k-means algorithm will continue to cluster the points suboptimally. The optimality of the solution will be based also on the threshold that you want to eventually introduce about largness of your closeness bond.

You can find useful discussions and proofs of the arguments in papers like this:

http://pdf.aminer.org/000/303/169/on_the_lower_bound_of_local_optimums_in_k_means.pdf

This is a good question.

The k-means optimality problem is considered in great detail in

M. Yan, Methods of determining the number of clusters in a data set and a new clustering criterion, Ph.D. thesis, Virginia Polytechnic Institute and State University, 2005:

http://scholar.lib.vt.edu/theses/available/etd-12062005-153906/unrestricted/Proposal-Face.pdf

Clustering optimization methods are covered in this thesis, starting on page 18.   See Section 2.2.2, starting on page 19, for related works on optimizing k-means clustering. See the Appendices for proofs, starting on page 49.

A beautifully detailed, discursive analysis of k-means clustering is given in

D. Dueck, Affinity Propagation: Clustering Data by Passing Messages, Ph.D. thesis, University of Toronto, 2009:

http://www.cs.columbia.edu/~delbert/docs/DDueck-thesis_small.pdf

Thank you very much for your answer Ms. Valentina Franzoni. It can add my knowledge about clustering problems.

Thank you very much Prof. James F Peters. It's an honor for me that you already gave the complete answers and voted up my question. I'm curious with clustering problems. I'm a Ph.D student in Bandung Institute of Technology, Indonesia. I tried many experiments especially in medical data using clustering method. I always found difficulties to find the centroid of the assigned cluster which can give global solution. Perhaps, we can find the solution by observing them mathematically. The thesis you suggested are really useful for me.