坐标下降法

坐标下降法（coordinate descent）在优化时一次只改变一个变量，其他变量保持在当前值。每步可以精确求解一维子问题，也可以沿该坐标作受控的近似下降。它把一次更新的工作缩小了，但变量之间的耦合使得多个坐标通常需要反复轮换。

一个能看见耦合的二次函数

考虑教学用目标 $$f(x,y)=\frac{1}{2}(x^2+xy+y^2),(x,y)\in {ℝ}^2.$$ 固定 $y$ 后，关于 $x$ 的导数是 $x+y/2$，二阶导数为一，所以这一维的唯一最小点是 $x=-y/2$。随后固定刚更新的 $x$，得到 $y=-x/2$。第二步使用的是新 $x$，这与同时使用旧坐标更新两个变量不同。

从 $(0,2)$ 出发，状态依次为 $$(0,2)⟶(-1,2)⟶(-1,1/2)⟶(-1/4,1/2)⟶(-1/4,1/8).$$ 目标值分别为 $2,3/2,3/8,3/32,3/128$。图中的水平段对应优化 $x$，竖直段对应优化 $y$；每次拐弯都来自一个已经解完的一维问题。

点号依次对应正文的五个状态，曲线为相同二次函数的等高线。

若把一轮定义为先更新 $x$ 再更新 $y$，则轮末满足 $y_{k+1}=y_k/4$、$x_{k+1}=-y_k/2$。因此本例坐标趋于原点，且每轮目标值在第一轮之后乘以 $1/16$。原点是唯一全局最小点，因为 $x^2+xy+y^2=(x+y/2{)}^2+3y^2/4$，只有两坐标均为零才使目标为零。

一般更新与下降量

对 $f:{ℝ}^n\to ℝ$，当前向量为 $x$，第 $i$ 个标准基向量记作 $e_i$。精确更新选取 $$t\in \mathrm{\ast }{argmin}_{a\in ℝ}f(x+a{e}_i),x^{+}=x+t{e}_i.$$ 假定这个最小点存在，因为 $a=0$ 也是候选，便有 $f(x^{+})\le f(x)$。这是精确更新的下降不变量；它本身不保证收敛到全局最优。若函数只在乘积约束集上定义，就把一维搜索限制在相应坐标的可行区间。

对对称正定二次目标 $f(x)=\frac{1}{2}{x}^{𝖳}Qx-b^{𝖳}x$，令 $g=Qx-b$。沿第 $i$ 个坐标精确展开： $$f(x+t{e}_i)=f(x)+t{g}_i+\frac{1}{2}{Q}_{ii}{t}^2.$$ 正定性保证 $Q_{ii}>0$，故 $t=-g_i/Q_{ii}$，目标恰下降 $g_i^2/(2Q_{ii})$。这把一次便宜更新与可量化的进步联系起来。对一般光滑函数，若沿坐标的梯度 Lipschitz 常数为 $L_i>0$，同样的上界推导给出步长 $-g_i/L_i$，但它未必精确最小化一维问题。

两条轨迹均从 y₀=2 出发；ρ 越接近一，单轮收缩越弱。

选择坐标也属于算法：循环规则按固定顺序遍历；随机规则按指定概率抽取；贪心规则可偏好较大梯度分量，但需要计算或维护更多信息。随机版本的期望速率应连同抽样规则和凸性条件报告，不能直接赋给任意循环更新。

坐标最优的适用范围

若 $f$ 在整个 ${ℝ}^n$ 上可微且凸，一个点若对每一坐标都达到一维最小值，则各偏导数为零，故 $\mathrm{\nabla }f(x)=0$。凸函数的一阶不等式 $f(z)\ge f(x)+\mathrm{\nabla }f(x{)}^{𝖳}(z-x)$ 随即证明它全局最优。这是“已经对所有坐标最优”的结论，尚未证明某个特定更新顺序一定到达这样的点。

光滑性不能直接删除。例如 $h(x,y)=max\{x,y\}+0.1(x^2+y^2)$ 凸但在原点不可微。固定 $y=0$ 时，$h(x,0)\ge 0$，固定 $x=0$ 也如此，所以原点沿每个坐标都最优；然而 $h(-1,-1)=-0.8<0$。耦合的不可微项使单坐标无法通过对角方向离开原点。可分离不可微项有专门理论，不能与这个反例混淆。

变式与可运行计算

把例子的交叉项改成 $2\rho xy$，即 $f_{\rho }=\frac{1}{2}(x^2+2\rho xy+y^2)$，并令 $|\rho |<1$。两步分别为 $x=-\rho y$、$y=-\rho x$，故轮末 $y_{k+1}={\rho }^2{y}_k$。变式取 $\rho =0$：一轮到原点；取 $\rho =0.9$：每轮纵坐标乘 $0.81$，比原例慢。接近奇异的耦合因此可导致很慢的折线路径。

以下函数只用标准库，输入初始两坐标、$|\rho |<1$ 和非负整数轮数，返回每个坐标更新后的状态，不改写输入。每轮时间、工作空间均为 $O(1)$，保存 $K$ 轮历史需 $O(K)$。一般稠密 $n$ 维二次模型若维护残差，一次坐标更新为 $O(n)$，一轮为 $O(n^2)$。

Python 3

def coordinate_descent(start, rho=0.5, rounds=2):
    if len(start) != 2 or abs(rho) >= 1 or rounds < 0 or int(rounds) != rounds:
        raise ValueError("two coordinates, |rho| < 1, integer rounds required")
    x, y = map(float, start)
    value = lambda x, y: (x*x+2*rho*x*y+y*y)/2
    trace = [(x, y, value(x, y))]
    for _ in range(rounds):
        x = -rho*y
        trace.append((x, y, value(x, y)))
        y = -rho*x
        trace.append((x, y, value(x, y)))
    return trace

for row in coordinate_descent((0, 2)):
    print(tuple(round(v, 6) for v in row))
assert coordinate_descent((3, -2), 0, 1)[-1] == (0.0, 0.0, 0.0)

输出前五个点为正文路径，最后一项的目标值为 0.023438。残差或全梯度范数可以诊断停止精度；只检查本次被选坐标不再变化，会遗漏其他坐标。