块坐标下降法

块坐标下降法（block coordinate descent）把决策向量分成若干组，每步只优化其中一组，并固定其余组。每组称为一个块，可以包含一个或多个变量。与坐标下降法相比，分组允许块内耦合在同一个子问题中解决，也使每步成本和可用并行性发生变化。

两个耦合变量放在同一块

考虑无约束的三变量教学模型 $$F(u,v,w)=\frac{1}{2}(u^2+v^2)+\frac{1}{2}(u+v-w{)}^2+\frac{1}{2}(w-2{)}^2.$$ 取第一块为 $(u,v)$，第二块为 $w$。固定 $w$ 时，第一块的一阶条件不是两个相互独立的式子，而是 $$2u+v=w,u+2v=w.$$ 相减给出 $u=v$，再代入得到 $u=v=w/3$。子问题 Hessian 为 $\left(\begin{array}{cc}2& 1\\ 1& 2\end{array}\right)$，特征值为一和三，故这确是唯一块最小点。然后固定新 $u,v$，对第二块求导得到 $$-(u+v-w)+(w-2)=0,w=\frac{u+v+2}{2}.$$

每轮先联立求解 u、v，再更新 w；虚线是相应极限。

从 $(0,0,0)$ 开始，第一轮的第一块不动，第二块令 $w=1$，目标由二降到一。第二轮先得 $(u,v,w)=(1/3,1/3,1)$，目标为 $2/3$；再令 $w=4/3$，目标为 $5/9$。第三轮末为 $(4/9,4/9,13/9)$。这些不同状态应逐一记录，不能只显示每轮最终目标而隐去耦合方程。

轮末纵变量满足 $w_{k+1}=w_k/3+1$，所以 $$w_k=\frac{3}{2}(1-3^{-k}),u_k=v_k=\frac{w_{k-1}}{3}(k\ge 1).$$ 极限是 $(1/2,1/2,3/2)$，目标值 $1/2$。原函数的二次型对任意非零增量 $(a,b,c)$ 给出 $a^2+b^2+(a+b-c{)}^2+c^2>0$，所以整体严格凸；极限处梯度为零，因此是唯一全局最小点。

乘积可行域与精确块更新

设向量分成 $B$ 个不相交块 $x=(x_1,\dots ,x_B)$，可行集为乘积 $X_1\times \cdots \times X_B$。循环更新在第 $j$ 块求解 $$x_j^{+}\in \mathrm{\ast }{argmin}_{z\in X_j}F(x_1^{+},\dots ,x_{j-1}^{+},z,x_{j+1},\dots ,x_B).$$ 前面的块使用新值，后面的块使用旧值。假定每个子问题有解，旧块值仍可行，因此每次更新不增大目标。乘积假设让单块可行性容易维护；若原问题有跨块约束，必须在子问题中保留该约束，或重新分组。

例如约束 $u+v=1$ 下最小化 $u^2+v^2$，若把 $u,v$ 拆成两个单变量块，从 $(1,0)$ 出发，每次固定另一个变量都会迫使所选变量保持原值，算法停住；而联合块可移到 $(1/2,1/2)$，把目标从一降到二分之一。这里失败的是分组后可行移动受限，不是导数计算错误。

单个变量不能在保持另一变量不变时移动；联合更新可以沿约束线到达中点。

正定二次模型的收敛论证

对 $F(x)=\frac{1}{2}{x}^{𝖳}Qx-b^{𝖳}x$，假定 $Q$ 实对称正定，块划分固定并循环遍历。一次块增量 $d_j$ 满足 $Q_{jj}{d}_j=-g_j$，其中 $g_j$ 是更新前的该块梯度。展开目标可得下降量恰为 $$F(x)-F(x^{+})=\frac{1}{2}{d}_j^{𝖳}{Q}_{jj}{d}_j\ge \frac{\mu }{2}\Vert d_j{\Vert }^2,$$ 这里 $\mu >0$ 是 $Q$ 的最小特征值，主块也满足同一下界。目标有下界，把所有更新下降量求和，得到 $\sum \Vert d_j{\Vert }^2<\mathrm{\infty }$，所以各步增量趋于零。

在每次块更新刚结束时，该块梯度为零；到轮末只经历有限个其他块的变化，而这些变化都趋于零，线性梯度的连续性便给出轮末全部梯度趋于零。又因 $\mathrm{\nabla }F(x)=Q(x-x^{\ast })$，有 $\Vert x-x^{\ast }\Vert \le \Vert \mathrm{\nabla }F(x)\Vert /\mu$，故轮末及轮内各点均趋于唯一最优解。这一证明使用正定二次结构，不能单凭“每步下降”推广到任意非凸块模型。

分组变式和实现

变式把本例的三个变量合成一个块。联立全梯度为零，先得 $u=v$、$w=3u$，再由 $2w-u-v-2=0$ 得 $u=v=1/2,w=3/2$，只需一次精确子问题求解。步数减少的代价，是单个子问题更大。

下例按两块执行，输入为三坐标及非负整数轮数，返回所有块更新的状态、目标值，不改写输入，只用标准库。该特殊模型每次块求解为常数成本，保存 $K$ 轮的返回历史需 $O(K)$ 输出空间；一般稠密大小为 $d$ 的二次块，直接分解约需 $O(d^3)$，固定矩阵可缓存分解，再用约 $O(d^2)$ 回代。块越大，耦合处理越充分，但每次计算通常也越重。

Python 3

def block_descent(start, rounds=3):
    if len(start) != 3 or rounds < 0 or int(rounds) != rounds:
        raise ValueError("three coordinates and integer rounds required")
    u, v, w = map(float, start)
    value = lambda u,v,w: (u*u+v*v+(u+v-w)**2+(w-2)**2)/2
    trace = [(0, "start", u, v, w, value(u,v,w))]
    for k in range(1, rounds+1):
        u = v = w/3
        trace.append((k, "uv", u, v, w, value(u,v,w)))
        w = (u+v+2)/2
        trace.append((k, "w", u, v, w, value(u,v,w)))
    return trace

for row in block_descent((0,0,0)):
    print(row[:2], tuple(round(v,6) for v in row[2:]))
assert abs(block_descent((0,0,0), 30)[-1][-1]-0.5) < 1e-12

输出轮末目标为 2.0、1.0、0.555556、0.506173，趋向 0.5。这个具体递推给出的收缩证据，比仅观察数值“看上去稳定”更强。