哈喽，大家好~
今儿和大家聊一个话题：为什么 k-means 目标函数是非凸的？
咱们先从 k-means 的基础说起~
先打个比方。当你在食堂，看着满屋子的人，手里有数据：他们的身高、体重。你想把这些人分成几堆（比如 3 堆），看是不是能形成「一堆偏高大威猛的」「一堆中等身材的」「一堆小巧灵动的」。
这就是 K-means 聚类要干的事：
输入：一堆点（每个点是一条数据记录，可以是二维的、三维的甚至更高维的向量）。 输出：把这些点分成 K 个簇。 原则：同一簇里的点彼此“接近”，不同簇之间“尽量远”。
K-means 的核心思想：
先随机挑 K 个点当“簇中心”（cluster centers，也叫 centroids）。 把每个数据点分配给离它最近的簇中心。 更新簇中心：每个簇的中心就变成“这个簇里所有点的均值”。 重复第 2、3 步，直到簇中心不再变化或者变化很小。
一句话总结：分配 + 更新，不断循环，直到收敛。
目标函数
K-means 不只是随便聚一聚，它有个明确的目标函数要最小化：
：第 个簇 ：第 个簇的中心（就是所有点的均值） ：点 到中心的平方距离
直白点说，我们要让“点到中心的距离平方和”尽可能小，你可以理解成“簇内紧密度”最大化。
流程细拆
初始化：随机选 K 个点当簇中心。这里很玄学，不同的初始化可能导致不同结果。
分配步骤：每个点 找最近的中心 ，归属到对应簇。
公式：
更新步骤：对每个簇，重新计算中心：
迭代：重复 2、3 步，直到目标函数 不再显著下降。
那么， 问题来了，为什么目标函数是非凸的？
这是很多人容易糊涂的点。我们来逐层拆解。
为什么目标函数是非凸的
一个函数是凸的，直觉上意味着：它的图像像“碗”一样，只有一个全局最小值，不会有多个坑。
凸优化问题：好解，保证找到全局最优解。
非凸优化问题：麻烦，容易卡在局部最优。
再看下，K-means 目标函数：
这里的麻烦出在：簇分配 不是连续变量，而是离散的分类变量，数据点属于哪个簇，这是个组合问题（类似把点分组的 NP-hard 问题）。
换句话说：如果簇分配固定了，那么优化中心 是个凸问题（直接取均值就是最优）。
如果中心固定了，那么优化分配也是简单的（直接选最近的），但两个合起来就不是凸的。
4 个点：，你要分成 2 个簇。
分法 A：左两点一簇，右两点一簇 → 目标函数值 X。 分法 B：上两点一簇，下两点一簇 → 目标函数值 Y。
这两种分法都可能是局部最优，你得不到唯一的全局解。
这说明目标函数有多个“谷底”，而不是单一的“碗”。
更严格点看：目标函数本质是对“簇分配变量 + 簇中心变量”的联合优化。
簇分配变量是离散的（one-hot）。 当我们把离散和连续混在一起，优化空间就像一个「坑坑洼洼的地形图」。 所以整体函数 不是凸的。
换句话说，非凸性来自于簇分配的离散性。
案例实现
下面写一段代码，展示 K-means 在不同初始化下会收敛到不同局部最优，印证“非凸性”。
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
# 构造数据：两个方形簇
X = np.array([[0,0], [0,10], [10,0], [10,10]])
# 用不同随机初始化多次跑 KMeans
fig, axes = plt.subplots(1, 3, figsize=(12, 4))
for i, seed in enumerate([0, 5, 10]):
kmeans = KMeans(n_clusters=2, random_state=seed, n_init=1, init="random")
kmeans.fit(X)
centers = kmeans.cluster_centers_
labels = kmeans.labels_
axes[i].scatter(X[:,0], X[:,1], c=labels, s=100, cmap="coolwarm")
axes[i].scatter(centers[:,0], centers[:,1], c="black", marker="x", s=200)
axes[i].set_title(f"Init Seed = {seed}")
plt.show()
运行后大家会看到：
不同初始化种子 => 聚类结果不一样。 有的按“上下”分簇，有的按“左右”分簇。
这就体现了目标函数的非凸性：不同初始点可能卡在不同局部最优。
总结一句话：K-means 目标函数非凸，是因为它同时要解“点的离散分配”和“中心的连续更新”，组合起来就像在多山的地形里找最低谷，注定不是一口碗那么简单。
最后
