这些年做目标跟踪，最常碰到的问题不是模型选得不好，也不是特征提得不对，而是优化目标明明写出来了，却被一个不可导的正则项卡住。稀疏表示那一类跟踪框架尤其典型，目标函数里带 L1 项，梯度下降根本没法直接套。后来我把 ADMM 这个求解器嵌进跟踪流程，整个局面一下子清爽了很多，几乎每个子问题都有解析解，写起来就是几十行代码的事。这篇文章把我在目标跟踪中使用 ADMM 求解的完整经验捋一遍，包括原理推导、变量分裂、代码实现和调参踩坑，适合正在做跟踪算法、或者刚接触优化方法、想把论文里的公式落到代码上的同学参考。
1. 跟踪问题为什么需要ADMM来求解
1.1 跟踪任务里的优化目标是怎么来的
先回到跟踪任务本身。给一段视频和第一帧的目标位置，我们要在后续每一帧预测目标跑到哪儿了。主流框架是采样加评分：在上一帧目标位置周围撒一批候选窗口，提取特征，和模板做比较，得分最高的位置作为当前帧的估计结果。
这个过程会产生两类典型的优化模型。一类是判别式相关滤波，典型代表是 SRDCF、BACF 这条技术线。它们的思路是训练一个滤波器 h，让滤波器与图像特征的卷积响应接近预设的高斯标签，写成优化问题就是：
min_h ||y - Xh||_2^2 + λ||h||_2^2
其中 X 是由图像特征构成的样本矩阵，y 是高斯响应标签，λ 是正则系数。这类问题的难点在于 X 的规模可能很大，而且实际使用中往往还要加约束，比如只关注背景区域以外的一部分像素，原本可以直接闭式求解的问题就变得复杂了。
另一类是生成式稀疏表示，最早可以追溯到 L1 跟踪器那一脉。它的思路是：目标外观可以用模板字典里的若干基原子线性组合近似，每个候选样本在这个字典上做稀疏编码，重构误差最小的候选就是目标位置。对应的优化问题为：
min_c ||y - Dc||_2^2 + λ||c||_1
D 是模板字典，c 是稀疏系数，λ 控制稀疏度。这个问题的难点是 L1 范数在零点不可导，传统梯度类方法不好直接处理。
两类问题有一个共同特征：目标函数里同时存在光滑项和不可导项（或者困难约束），直接端到端求解很别扭。所以真正需要的是一个能把这些东西拆开、每个子问题又能解析求解的算法——这正是 ADMM 擅长的领域。
1.2 为什么偏偏是ADMM而不是其他算法
能处理 L1 项的算法其实不少，但我在实际对比中，ADMM 在跟踪场景里的优势非常明显。
排名第一的候选对手是 ISTA，也就是迭代软阈值算法。它每一步做一次梯度下降加一次软阈值映射，逻辑简单，但收敛速度是次线性的，经常要迭代几百次才能达到比较好的精度。跟踪器每帧的时间预算通常只有几十毫秒，这根本无法接受。FISTA 加动量加速后收敛快了很多，但每一步依然需要一次完整矩阵乘法，几百个候选样本就是几百次矩阵运算，累计时间依旧可观。投影梯度法也可以，但遇到非光滑目标时，每一轮都要计算投影算子，而这个投影往往没有闭式解，实用性打了折扣。
ADMM 的做法完全不同。它把原始问题分裂成两个子问题：一个只包含光滑二次项，对变量求一阶条件后得到线性方程组；另一个只包含 L1 项，解就是闭式软阈值算子。两个子问题都不需要嵌套迭代，交替执行再更新一个拉格朗日乘子，通常十几二十次迭代就能收敛到跟踪任务够用的精度。
更妙的是，在相关滤波类方法里，子问题还能搬到傅里叶域变成逐元素运算，彻底绕开矩阵求逆。这就是 BACF 那一类方法能跑实时的重要原因。可以说，ADMM 在跟踪里的流行不是因为理论多漂亮，而是因为它同时满足了“算得动”和“算得快”这两个矛盾的需求。
2. ADMM的原理，用大白话怎么讲
2.1 从拉格朗日乘子法到增广拉格朗日
理解 ADMM 之前得先看它的前身。对一个带约束的凸优化问题：
min f(x) 约束条件：Ax = b
拉格朗日乘子法把约束拉进目标函数，构造 L(x, v) = f(x) + v^T(Ax - b)，原问题变成对 x 求极小、对 v 求极大的鞍点问题。理论上这是严格的，但数值上有个大麻烦：v 的更新完全依赖次梯度信息，迭代过程容易在两个方向之间来回震荡，收敛又慢又不稳。
增广拉格朗日法在拉格朗日函数后面补了一个二次惩罚项 (ρ/2)||Ax - b||_2^2。这一项的作用是给目标函数“加深加陡”，把迭代点压向约束流形附近，有效抑制震荡。直观理解就是：原来的约束只是在目标函数里轻度提醒一下，现在变成了强推一把，两个方向的收敛速度都显著提升，代价是引入一个需要试出来的惩罚系数 ρ。
2.2 ADMM的三步标准迭代
ADMM 针对的是更一般的双变量可分问题：
min f(x) + g(z) 约束条件：x = z
它把单变量问题拆成 x 和 z 两个变量，约束 x - z = 0 把它们拉回一致。算法迭代只有三步，全是机械操作。第一步，固定 z 和 u，更新 x：x_{k+1} = argmin_x f(x) + (ρ/2)||x - z_k + u_k||2^2，本质是在当前约束偏差下极小化 f。第二步，固定 x 和 u，更新 z：z{k+1} = argmin_z g(z) + (ρ/2)||x_{k+1} - z + u_k||2^2，这一步只动 z，完全不碰 f。第三步，更新对偶变量 u：u{k+1} = u_k + x_{k+1} - z_{k+1}，把两个变量之间的分歧累计进位。
可以看到，f 和 g 在每一步里都是分别极小化的，互不干扰。这给了我们极大的设计自由度：只要把不容易处理的部分（比如 L1、约束条件）放进 g，把光滑部分放进 f，两个子问题就能各显神通地解析求解。
我经常用一个比喻帮助理解：f 和 g 像是两个风格迥异的合伙人，一个擅长谈判，一个擅长执行，它们需要就同一个决策达成一致（x = z），中间的 u 就是传话的协调人，每次会谈后负责把双方的分歧反馈回来。迭代的过程就是三方不断会商，分歧越来越小，最终达成共识。
2.3 ADMM的收敛性到底怎么理解
对收敛性，我需要澄清一个常见误解。当 f 和 g 都是闭凸函数且问题存在鞍点时，ADMM 保证目标函数收敛到全局最优值。但它不像梯度下降那样每一步目标值都单调下降，中途出现小幅反弹是正常的。判断收敛的正确指标是残差范数 ||x - z||（也叫原始残差）和 ||z - z_prev||（对偶残差），而不是目标函数值。
理论上凸问题的 ADMM 有 O(1/k) 的收敛率。在跟踪应用里，k 不需要太大。我实测的规律是：前 5 到 8 次迭代残差下降最快，之后转入缓慢的线性收敛段，再往后就是边际效应递减。跟踪任务对精度的要求不是极致苛刻，所以 10 到 30 次迭代完全够用。
提示：如果你发现目标函数值在前几次迭代不降反升，先别慌，去看原始残差是否在下降。只要残差在降，算法就是健康的。盲目加大迭代次数只会浪费时间。
2.4 两个参数决定ADMM的脾气
ADMM 最重要的参数就两个：ρ 和 λ。后者是原问题里本来就有的正则参数，不是 ADMM 引入的。
ρ 控制惩罚强度。ρ 太大会让原始残差收敛得很快，但对偶残差收敛变慢，最终解的精度差一点；ρ 太小则原始残差收敛很慢，迭代迟迟收不了尾。一个实用经验是：数据做过归一化的话，从 ρ = 1 开始试，打印残差曲线，根据曲线形状调整。更省心的是用自适应调度，后面第 5 节会给出可落地的策略。
λ 控制解向量的稀疏度。在稀疏表示跟踪里，λ 太小导致解稠密，重构误差的区分度变差；λ 太大导致解太稀疏，可能丢失对目标外观的刻画。一般从 0.05 起步，范围在 0.01 到 0.1 之间比较常见，但最终取值必须结合字典的归一化方式和特征量级，不能直接照搬别人的数。
3. 实战：用ADMM求解稀疏表示跟踪
3.1 变量分裂：把麻烦从光滑项里剥离
以稀疏表示跟踪最核心的优化问题为例：
min_c ||y - Dc||_2^2 + λ||c||_1
直接求解的障碍是 L1 项不可导。ADMM 的思路是引入辅助变量 z，把问题等价变形为：
min_{c,z} ||y - Dc||_2^2 + λ||z||_1 约束条件：c = z
拆分之后，c 子问题变成纯粹的二次优化，z 子问题变成纯粹的 L1 优化，两边都干净利落。增广拉格朗日函数写成：
L(c,z,u) = ||y - Dc||_2^2 + λ||z||_1 + (ρ/2)||c - z + u||_2^2
注意这里的 u 就是上一步对偶变量积累下来的误差补偿。每一轮迭代，它都会把 c 和 z 之间的偏差反馈进两个子问题，引导它们走向一致。这种“引入辅助变量、把耦合项拆开”的思路，是整个 ADMM 应用的精髓。
3.2 c子问题：其实就是在解一个线性方程组
固定 z 和 u，对 c 求最优解。对 L 关于 c 求导并令梯度为零，得到：
(D^T D + ρI_n) c = D^T y + ρ(z - u)
这是一个标准线性方程组，系数矩阵 D^T D + ρI_n 在整个迭代过程中是固定的，只要字典 D 没变，就可以预先算好逆矩阵，每轮迭代只做一次矩阵向量乘。这是 ADMM 在这个问题上效率高的最大来源。
有个细节值得强调：如果不用直接求逆，而是用 Cholesky 分解预分解系数矩阵，数值稳定性会更好，而且分解只需做一次，后续每轮就是两次三角回代。在字典规模上千的时候，这个差异是实实在在的。
3.3 z子问题：软阈值闭式解
固定 c 和 u，对 z 求最优解。这个子问题只涉及二次项和 L1 项的逐元素求和，解是软阈值算子：
z = shrink(c + u, λ/ρ) = sign(c + u) · max(|c + u| - λ/ρ, 0)
为什么是这么个形式？可以把每个维度单独拿出来看：目标函数是 0.5ρ(z_i - a_i)^2 + λ|z_i|，其中 a_i = c_i + u_i。这是一个一维凸问题，开口向上的抛物线加一个 V 形绝对值函数。求极值点会发现：当 a_i 的模长小于阈值 λ/ρ 时，极值点出现在原点；否则出现在 a_i 减去符号方向上一个固定偏移的位置。合起来就是上面的软阈值公式。
这个算子实现起来就几行向量化代码，是整个 ADMM 循环里几乎免费的一步。它也是 L1 正则能产生稀疏解的根本原因——小于阈值的分量被精确置零。
3.4 对偶变量更新与收敛判据
第三步是最简单的：u = u + c - z。这相当于把当前两个变量的分歧累计进乘子。然后计算原始残差 r = ||c - z||。我的停止条件是用 r < tol 做主判据，外加最大迭代次数兜底，防止异常情况下死循环。
调试时把每次迭代的 r 打印出来，画成曲线，你能非常直观地看到收敛过程。我第一次跑通时那条曲线前面几轮垂直下落、后面缓缓贴地，心里顿时就踏实了。之后再处理遮挡、光照变化这些实际难题，替换的只是字典更新策略，ADMM 内核几乎没再动过。
4. 代码实现：一个能直接跑的最小求解器
4.1 三十多行的核心实现
下面是完整可运行的精简版求解器：
import numpy as np def admm_sparse_coding(D, y, lam=0.05, rho=1.0, max_iter=30, tol=1e-4): m, n = D.shape # 预计算系数矩阵的逆，迭代过程中固定不变 H = D.T @ D + rho * np.eye(n) H_inv = np.linalg.inv(H) Dt_y = D.T @ y c = np.zeros(n) z = np.zeros(n) u = np.zeros(n) z_prev = z.copy() prim_res = [] dual_res = [] for k in range(max_iter): # 第1步：c子问题，线性方程组求解 c = H_inv @ (Dt_y + rho * (z - u)) # 第2步：z子问题，软阈值 z = np.sign(c + u) * np.maximum(np.abs(c + u) - lam / rho, 0.0) # 第3步：对偶变量更新 u = u + (c - z) # 残差记录 prim_res.append(np.linalg.norm(c - z)) dual_res.append(rho * np.linalg.norm(z - z_prev)) if prim_res[-1] < tol and dual_res[-1] < tol: break z_prev = z.copy() return z, np.array(prim_res), np.array(dual_res)接入跟踪器时，对每个候选样本 y 调用一次这个函数，得到稀疏系数 z，然后计算重构误差 ||y - D @ z||，误差最小的候选就是当前帧的目标位置。整个调用流程非常机械，核心思想就是给候选样本打分。
4.2 跑实验前必须处理的三个细节
代码本身只是第一步，实操中还有三个容易掉进去的坑。
第一，特征和字典的归一化。没归一化之前，特征向量里某些维度数值特别大，会主导重构误差，λ 和 ρ 的量级也会变得极不可控。我的标准流程是：对特征做 L2 归一化，对字典每一列也做 L2 归一化，再送进 ADMM。归一化之后，λ = 0.05、ρ = 1 这些默认值在大部分序列上都有一致的表现。
第二，ρ 与特征尺度的匹配。换了特征提取方式，D 的数值范围可能整体变大或变小，如果 ρ 沿用旧值，收敛速度会剧烈恶化。排查方法很简单：打印前 5 轮原始残差，如果下降非常缓慢而且数值整体偏大，优先怀疑 ρ。
第三，warm start 的利用。跟踪相邻帧之间的目标外观变化是连续的，上一帧的最优解可以作为这一帧的迭代初始值，能显著减少迭代次数。我把 z 初始化为上一帧的结果，平均迭代数从 20 次降到 12 次左右，效果非常明显。
4.3 效率和实时性大概是什么水平
我测过一组典型配置：字典规模 50 维特征、200 个字典原子，20 次迭代，普通笔记本上单次 ADMM 求解约 0.2 毫秒。如果每帧评估 300 个候选样本，总耗时约 60 毫秒。这个水平用于离线分析或者 15fps 左右的实验完全没问题，但实时跟踪就需要配合一些工程手段了。
实际中常用的提速手段有几个：一是降低候选样本数量，用运动模型先粗筛一遍；二是把字典规模减半，精度损失通常不大，速度能翻倍；三是在非关键帧减少迭代次数，只迭代 8 到 10 次。这些技巧组合起来，单帧总耗时能压到 20 毫秒以内。
5. 调参经验与常见问题
5.1 正则化参数λ的选择经验
λ 的选择不能只看数值大小，要看它给解带来的稀疏度变化。我在调试时的做法是：固定其他参数，在验证序列上跑一遍，记录解向量中非零分量占比。占比在 10% 到 30% 之间是比较理想的工作区间。占比过高说明 λ 偏小，解太稠密、区分力下降；占比过低说明 λ 偏大，解里有效信息太少，跟踪容易漂移。
另外，模板字典的质量直接影响 λ 的合理范围。字典越干净，λ 可以取小一些；字典越杂，混入了背景样本或者噪声模板，λ 需要调大以抑制不相关原子的激活。我遇到过不少案例，问题根本不是 λ 的锅，而是字典太久没更新，外观变化累积导致所有候选的重构误差都差不多，这时候调 λ 没用，先更新字典。
5.2 ρ的自适应更新策略
固定 ρ 只是起步方案。我在正式实验里用自适应策略，每 5 轮迭代评估一次原始残差和对偶残差的比值：
- 如果原始残差超过 10 倍对偶残差，说明原始残差收敛过慢，把 ρ 乘以 2；
- 如果对偶残差超过 10 倍原始残差，说明对偶残差收敛过慢，把 ρ 除以 2；
- 其余情况保持不变。
这个策略的思路是让两条残差保持均衡，实际跑下来收敛稳定性明显提升。代价是 ρ 变化后系数矩阵的逆需要重算，所以我只在第 5 到第 15 轮之间允许调整，前后各留一段缓冲，既享受自适应收益，又不至于频繁重算拖慢速度。
5.3 ADMM解出来但跟踪还是丢：先查模型
这是最容易走弯路的地方。很多同学看到跟踪丢失，第一反应就是调 ADMM 参数。我踩过几次坑之后总结出一个排查顺序：先查模型，再查优化。所谓查模型，就是把每一帧所有候选样本的重构误差画成曲线。如果误差曲线在遮挡帧出现明显突变尖峰，说明模型本身对遮挡敏感，这不是求解器能解决的问题；如果误差曲线整体平缓、区分度低，说明模型表达力不足，同样与 ADMM 无关。这两类问题往 ADMM 参数上使劲，纯属缘木求鱼。
只有当模型没问题但求解结果确实异常，比如 c 和 z 迟迟不收敛、残差曲线抖得离谱，才回到 ρ 和迭代次数上排查。顺序别搞反，否则浪费大量时间。
5.4 相关滤波跟踪器中的ADMM变体
如果你用的是相关滤波这条技术线（BACF 及其后续工作），ADMM 的用法是相通的，但有两点差异值得说明。
第一，相关滤波器的循环矩阵在傅里叶域可以对角化，因此 c 子问题会从矩阵求逆变成逐元素的频域除法，速度更快。第二，频域运算涉及复数，原本的软阈值算子需要改为复数软阈值：对复数的模长做收缩、保持相位不变。这个细节非常容易写错，我最初实现复数版本时就在相位处理上栽过跟头，如果不管相位直接套实数公式，重构误差会乱得一塌糊涂，而且还不容易一眼看出是这里的问题。
最后讲点实际体会。我最初把 ADMM 用进目标跟踪，最打动我的点不是理论上的收敛保证，而是它的工程亲和力——每一步子问题都落在矩阵运算或者向量运算上，向量化顺手，调试直观，相比之前折腾的各种带学习率的梯度类方法，踩中的雷要少得多。如果你正在做带正则项的跟踪模型，或者换了一个场景想快速把手里的优化问题解出来，强烈建议先把第 3、4 节的例子跑通，把残差曲线打印出来亲眼看一遍，那两条曲线带给你的理解，比看十篇论文都直接。后续想扩展到多任务联合优化、分布式多传感器跟踪，或者频域加速版本，这套思维框架都可以直接复用。
