做目标跟踪这些年一个特别深的体会是网络结构往往不是最大门槛真正卡住进度的常常是“优化求解”这一步。尤其是相关滤波、稀疏表示这类判别式跟踪器目标函数写起来容易但每一帧的高维优化问题要解出来往往得花掉好几个晚上。一开始我习惯直接调通用优化器可跟踪是流式任务一帧只有几十毫秒预算通用求解器根本扛不住。后来把交替方向乘子法ADMM搬进求解流程很多难题一下子有了高效的结构——子问题各自有闭式解整个迭代能压到几次快速傅里叶变换的量级。这篇文章就围绕目标跟踪中的ADMM求解展开把原理、公式、实现细节和踩坑经验一次讲清楚适合正在接触相关滤波或稀疏表示跟踪、被优化步骤卡住的同学。1. 跟踪器里的优化问题为什么总卡在求解这步1.1 相关滤波目标函数每加一项约束解就难一截先看一个典型的相关滤波跟踪训练目标。假设我们有 $K$ 个特征通道每个通道的样本构成循环矩阵 $X_k$滤波器是 $w_k$期望响应是高斯形状的 $y$经典岭回归形式长这样$$ E(w) \frac{1}{2} \left| y - \sum_{k1}^{K} X_k w_k \right|^2 \frac{\lambda}{2} \sum_{k1}^{K} |w_k|^2 $$如果只有这一项事情其实很简单循环矩阵在频域可以被离散傅里叶变换对角化每个频率独立求解一步就拿到闭式解。这也是最早期相关滤波跟踪器能跑得飞快的原因。但真实场景里没人只用一个纯净岭回归。为了抑制循环移位带来的边界效应需要加空间正则或者干脆约束滤波器只在某个区域内非零为了让模型适应目标外观变化需要加时间正则项让当前滤波器不要离上一帧的滤波器太远。这些附加项都有明确物理意义不能随便丢掉。也正是它们的出现把“频域对角化”这条最舒服的路径堵死了——空间掩码破坏了循环平移不变性时间正则又把相邻帧的参数耦合在一起。目标函数每多一项闭式解的推导难度就上一个台阶。1.2 梯度类方法在跟踪任务里为什么不够用那直接用梯度下降行不行行是行但代价很大。跟踪器的参数空间会随着特征通道数、搜索区域尺寸迅速膨胀比如一个多通道相关滤波器特征维度轻松到几十万甚至上百万。再加上循环矩阵本身的条件数受样本能量分布影响目标函数常常是病态的。梯度下降在这种问题上表现如何可以想象成一个蒙着眼睛下山的人每一步只朝当前最陡的方向迈碰到一个狭长山谷就会来回震荡明明离最低点不远却怎么都走不到。更要命的是实时性预算。跟踪器每一帧只有几十毫秒的计算时间通用梯度法往往需要几百上千轮迭代才能收敛到可用精度。我试过在深度学习跟踪器里用梯度求解子问题效果还行但速度实在没办法满足在线更新的要求。这也正是ADMM这类分裂方法在目标跟踪里被大量使用的原因宁可牺牲“每步都最优”也要保证“每一步都便宜”。1.3 ADMM到底在什么时机出手总结来说当优化问题同时包含两股互相牵扯的力量——比如频域里漂亮的对角化结构和空间域里必须强制满足的掩码约束——单靠某一类工具都会顾此失彼。ADMM的思路不是硬刚整个问题而是把变量拆开让频域友好的项留在频域解让空间约束的项在空间域处理再用一个乘子把两边重新绑在一起。它解决的是“鱼和熊掌都想兼得”的问题。2. 拆开再看ADMM三个更新公式背后的直觉2.1 变量分裂给每个目标各配一个副本很多第一次接触ADMM的人都会困惑明明问题里只有一个变量 $x$为什么要强行引入一个辅助变量 $z$把 $f(x)g(x)$ 写成 $f(x)g(z)$ 然后要求 $xz$这不是多此一举吗关键在于$f$ 和 $g$ 虽然作用在同一个变量上但它们各自“喜欢”的数学空间不一样。举个不太严谨但贴切的类比一个团队既要快速出图又要严格校对让同一个人同时干两件事结果两头都干不好。ADMM的做法是安排两个人各自负责一项然后定期对一下结果有分歧就互相调整。用数学语言说就是把原来耦合在一起的目标拆成两个独立的子问题每个子问题都能在各自擅长的地方高效求解。所谓“分裂”分裂的不是目标而是求解职责。2.2 增广拉格朗日与三步交替考虑一般形式$$ \min_{x,z} f(x) g(z), \quad \text{s.t.} \quad x z $$写出增广拉格朗日这里把乘子项写成对偶变量 $u$ 的缩放形式更方便实现$$ L(x,z,u) f(x) g(z) \frac{\rho}{2} | x - z u |^2 $$接下来就是著名的三步交替更新x 步固定 $z,u$求解 $\min_x f(x) \frac{\rho}{2}|x - z u|^2$z 步固定 $x,u$求解 $\min_z g(z) \frac{\rho}{2}|x - z u|^2$u 步更新乘子 $u \leftarrow u (x - z)$第三步里$u$ 累积了 $x$ 与 $z$ 的历史偏差。它的作用就像一个传话人如果 $x$ 老是不愿意靠近 $z$$u$ 就会越来越大在下一步把 $x$ 往 $z$ 的方向拽。整个过程不需要解原问题只需要反复解两个“被 $u$ 和 $z$ 扰动过”的简单子问题。直观理解原残差 $|x-z|$ 衡量两个副本之间是否达成一致对偶残差则衡量 $u$ 的变化是否稳定下来两者都趋于零时说明找到了原问题的最优解。2.3 ADMM的适用边界要心里有数必须说清楚ADMM不是万能药。它的前提是分裂之后每个子问题都能高效求解。如果一个子问题本身依然难啃那ADMM只是把一个难问题换成了两个更难的问题。我在实践中的判断标准很简单——把目标函数写出来问自己两个问题第一拆出来后每个子问题有没有闭式解或者廉价迭代第二乘子更新会不会引入额外的存储或通信开销如果答案都是肯定的ADMM大概率是合适的选择。3. 从目标函数到可跑代码一个相关滤波ADMM实例3.1 一个带空间掩码约束的典型问题为了让讨论落地我构造一个干净但足够说明问题的场景。假设训练目标仍然是岭回归但额外要求滤波器 $w$ 只能在事先指定的区域 $\mathcal{R}$ 内非零区域之外强制为零。用数学语言写就是$$ \min_w \frac{1}{2} | y - \Phi w |^2 \frac{\lambda}{2} | w |^2, \quad \text{s.t.} \quad w_i 0, \ i \notin \mathcal{R} $$其中 $\Phi$ 是由特征样本构成的循环矩阵多通道情况可以按通道求和后放在一起。这种问题在实际跟踪里很常见——搜索区域很大但有效的滤波器支撑区域很小这正是背景感知类跟踪器的核心想法。如果不加这个掩码约束直接用频域闭式解几行代码就搞定了。但有了约束之后直接频域解出来的 $w$ 没有办法保证区域外为零而把非零位置强行截断成零又会让解偏离原目标。这时候ADMM的价值就体现出来了。3.2 分裂设计与增广拉格朗日引入辅助变量 $g$要求 $g w$并把掩码约束放到 $g$ 头上$$ \min_{w,g} \frac{1}{2} | y - \Phi w |^2 \frac{\lambda}{2} | w |^2, \quad \text{s.t.} \quad g w, \ g_i 0, \ i \notin \mathcal{R} $$对应的增广拉格朗日是$$ L(w,g,u) \frac{1}{2} | y - \Phi w |^2 \frac{\lambda}{2} | w |^2 \frac{\rho}{2} | w - g u |^2 $$现在 $w$ 子问题完全不被掩码约束烦扰可以放开手脚用频域处理$g$ 子问题则只需要做一个简单的投影。两边的负担都变得极轻。3.3 三个子问题各显神通w 子问题对 $w$ 求梯度并令其为零得到线性方程组$$ (\Phi^H \Phi (\lambda \rho) I) , w \Phi^H y \rho(g - u) $$由于 $\Phi$ 是循环矩阵$\Phi^H \Phi$ 可以在频域对角化于是整个解变成逐元素的频域计算$$ \hat{w} \frac{\hat{\Phi}^H \odot \hat{y} \rho (\hat{g} - \hat{u})}{|\hat{\Phi}|^2 \lambda \rho} $$这里 $\odot$ 表示逐元素乘法$\hat{\cdot}$ 表示傅里叶变换。每算一步只用两次FFT和若干逐元素运算成本非常低。g 子问题$g$ 这边是纯粹的空间投影只需要把 $w u$ 里位于支撑区域外的位置清零$$ g \Pi_{\mathcal{C}}(w u) $$u 子问题乘子更新就是简单的一行$$ u \leftarrow u (w - g) $$把这三个子问题串起来一次完整迭代的总复杂度大约 $O(D \log D)$$D$ 是信号长度。这个复杂度对于在线跟踪来说完全可接受。3.4 一个能直接参照的Python伪代码下面是一个单通道版本的简化伪代码展示了循环体的核心逻辑import numpy as np def admm_track_update(Y, Phi, mask, rho0.1, lam0.01, iters5): # Y: 期望响应的FFT, Phi: 样本循环矩阵的FFT Phi2 np.abs(Phi) ** 2 PhiY np.conj(Phi) * Y w np.zeros_like(Y, dtypenp.complex128) g np.zeros_like(Y, dtypenp.complex128) u np.zeros_like(Y, dtypenp.complex128) for _ in range(iters): # w子问题频域闭式解 w (PhiY rho * (g - u)) / (Phi2 rho lam) # g子问题空间投影 g w u g[~mask] 0 # 掩码外置零 # u子问题乘子更新 u u (w - g) return np.fft.ifft(w).real请注意伪代码里g[~mask] 0前的操作都是在频域复数上进行的实际工程实现要小心不同域之间的转换。我们下面马上讲这些细节。4. 真正跑起来才知道的事加速、调参与收敛判断4.1 让每次迭代更便宜的几个技巧ADMM的收敛速度不算快通常几十轮迭代才能达到高精度但跟踪任务要的是“够用就好”。所以工程上要做的是把每次迭代的成本压到最低。第一个技巧是预计算不变量。只要训练样本没变$\Phi^H y$ 和 $|\Phi|^2$ 就不需要重复计算放在循环外面。我在早期版本里没注意这个每轮迭代都重算一遍白白浪费了大量FFT开销。第二个技巧是注意复数运算的细节。频域里计算 $\hat{\Phi}^H$ 一定要用np.conj(Phi)漏掉共轭会得到完全错误的解复数数组相乘要用逐元素乘法而不是np.dot或者矩阵乘法否则维度搞错不说语义也不对。第三个技巧是避免循环内反复分配内存。如果是在GPU上跑频繁创建临时数组会带来大量kernel launch开销。预先分配好w、g、u的缓冲区每次迭代原地更新速度能明显改善。4.2 rho 怎么选一个从实践中来的经验区间$\rho$ 是ADMM里最需要调的超参数。它的作用可以理解为“两边意见不一致时的调节力度”$\rho$ 太大$w$ 和 $g$ 会很快达成一致但原目标函数本身可能还没优化到位$\rho$ 太小约束长期得不到满足收敛速度又会拖慢。我在相关滤波类跟踪器上的经验区间是 $\rho \in [0.01, 1]$具体取值跟信号能量有关通常先做一次归一化再定。调试时有一个很实用的自适应策略实时观察原残差 $|w - g|$ 和对偶残差的变化如果原残差比对偶残差大太多就把 $\rho$ 调大反过来则调小。用这个策略往往能把固定 $\rho$ 时不收敛的问题救回来。4.3 收敛怎么判断残差才是硬指标数学上ADMM的收敛判据通常是原残差和对偶残差同时小于某个阈值。但在跟踪场景里每一帧只迭代3到5次根本等不到严格收敛。所以实践中更常见的是固定迭代次数只要子问题的解“比上一帧更好”就行。这里有个容易忽略的点跟踪是一个连续过程如果每一帧都只迭代两三次误差会逐帧累积。我遇到过一个很隐蔽的漂移问题排查了很久才发现是ADMM提前停止导致的残差残留。解决方式也很朴素在检测到响应图峰值下降明显的时候把这一帧的迭代次数临时从3提升到8目标跟踪的精度立刻回升了一截。4.4 三个具体实现的坑踩过才知道第一频域共轭方向搞反。这个错误最隐蔽因为程序不会报错只是结果不对。我在调试时习惯把解析闭式解和频域数值解做对比一旦偏差超过机器精度第一反应就是检查共轭。第二复数除法的除零问题。当 $\rho$ 取得比较小时分母 $|\hat{\Phi}|^2 \lambda \rho$ 在某些频率上可能非常小导致数值爆炸。稳妥做法是给分母加上一个很小的正数比如1e-8。第三float32下的数值稳定性。GPU上的默认float32精度在$\rho$很小时容易出事乘法累积误差会被放大。我的做法是前期调试用float64验证逻辑正确后再切回float32同时对分母做clip。5. 我实测中最容易翻车的几个环节5.1 分裂点没选好子问题反而更难解ADMM能不能用很大程度上取决于“把哪一步分裂出来”。我有一个反面例子早期做带时间正则的跟踪器时想当然地把时间正则项和频域项放在同一个子问题里。结果那个子问题既不能频域对角化也不能时间方向解耦成了一个不上不下的线性系统每次迭代还得内嵌一个共轭梯度法整体速度慢得离谱。后来我把时间正则单独拆给 $g$ 子问题让 $w$ 子问题维持纯频域闭式解速度立刻恢复了。这个经验用一句话概括分裂的目标不是形式上的对称而是让每个子问题都有最廉价的求解方式。拿到一个目标函数先狠狠盯住哪一块在频域好解、哪一块在空间域好解然后再动手设计约束。5.2 多通道特征下的维度对齐问题相关滤波跟踪器几乎不会用单通道特征一般都是HOG、颜色直方图或深度特征的组合。多通道扩展在公式上很简单——通道之间独立算内积再求和但实现时一个常见翻车点是维度对齐。频域里每个通道的FFT长度必须一致逐元素运算时要把所有通道的数组广播到相同形状。我第一次实现时某个通道的特征图尺寸少了两像素结果FFT长度对不上程序倒是正常运行了只是跟踪精度掉了好几个点。建议调试时先单通道跑通验证框架本身没问题再逐步增加通道这样一旦出错能快速定位是通道对齐还是算法逻辑的问题。5.3 早停策略要配合残差监控前面提到固定迭代次数会带来误差累积这里再说细一点。我习惯在每个子问题旁边记录残差范数打印出来观察它的变化趋势。如果残差在第2次和第5次迭代之间已经掉了两个数量级那固定3次是安全的如果残差还在稳步下降那说明这次迭代可能不够。跟踪任务的特别之处在于每一帧的迭代起点是上一帧的解所以很多帧其实收敛得非常快只有目标外观突变时会需要更多迭代。与其对所有帧用同一个迭代次数不如做一个简单的响应感知策略——响应图峰值方差大时增加迭代次数。这个策略靠谱且容易实现。5.4 一个可复现的排查流程遇到ADMM求解失败时我的排查顺序是先构造一个已知闭式解的极小问题比如随机高斯数据 无掩码约束验证ADMM实现能收敛到闭式解然后加入掩码约束检查 $g$ 子问题投影逻辑最后再把迭代次数调到50以上对比固定3次迭代的跟踪结果。每一层都能暴露不同类别的bug这比直接上数据集调试高效得多。6. 换个场景稀疏表示跟踪里的LASSO也能用ADMM6.1 稀疏跟踪碰到的问题不是“稠密”而是“稀疏”相关滤波之外另一类经典跟踪方法是基于稀疏表示的。核心想法是把目标候选区域表示成字典原子的稀疏组合希望大部分系数为零只保留少数几个贡献最大的原子。这类方法要解的优化问题长这样$$ \min_{\alpha} \frac{1}{2} | D \alpha - y_{\text{obs}} |^2 \lambda | \alpha |_1 $$其中 $D$ 是字典矩阵$y_{\text{obs}}$ 是观测向量。这里麻烦的不是平方项而是 $\ell_1$ 范数——它不可导直接梯度下降非常别扭。但这种形式恰好是ADMM的舒适区。6.2 拆分成最小二乘和软阈值两个子问题引入辅助变量 $\beta$令 $\beta \alpha$$$ \min_{\alpha,\beta} \frac{1}{2} | D \alpha - y_{\text{obs}} |^2 \lambda | \beta |_1, \quad \text{s.t.} \quad \beta \alpha $$增广拉格朗日展开后两个子问题分别是α 子问题这是一个带二次罚项的最小二乘$$ \alpha (D^T D \rho I)^{-1} (D^T y_{\text{obs}} \rho(\beta - u)) $$β 子问题这是一个带 $\ell_1$ 正则的投影闭式解就是软阈值函数$$ \beta \mathcal{S}_{\lambda/\rho}(\alpha u) $$其中软阈值函数定义为 $\mathcal{S}_\tau(a) \operatorname{sign}(a) \cdot \max(|a| - \tau, 0)$。6.3 软阈值的一行代码软阈值在Python里一行就能写完beta np.sign(a) * np.maximum(np.abs(a) - lam / rho, 0)这个算子在稀疏优化里几乎无处不在值得背下来。它做的事情很直观把绝对值小于阈值的系数直接砍成零把大于阈值的系数朝零方向收缩。阈值的大小由 $\lambda / \rho$ 决定——$\lambda$ 越大稀疏性越强$\rho$ 越大$\beta$ 越接近 $\alpha$ 的普通软投影。我最初写稀疏跟踪器时用通用凸优化库解 $\ell_1$ 问题每一帧要花几百毫秒改成ADMM之后同样精度下只用了原来零头的时间。这个差距在实时跟踪任务里就是“能不能跑”和“能跑多快”的差别。7. 上手ADMM的最小思维流程与个人建议7.1 拿到一个目标函数按五步走第一把目标函数写完整标出每一项的作用第二识别哪些项在频域/空间域或某个子空间里有廉价解法第三设计辅助变量把目标拆成一个容易处理的项加上一个约束第四固定 $\rho$ 初值通常从0.1开始跑一轮看残差曲线第五确认每个子问题的更新公式后再动手写代码不要边写边猜公式。这个流程看起来简单但能避免很多因为“先写代码再想公式”造成的返工。7.2 几条越早知道越好的实操经验一先在合成数据上验证实现。用随机高斯矩阵构造一个可以解析求出最优解的小规模问题对比ADMM迭代结果和解析解。这一步花不了十分钟但能省下一个星期。二调参时每次只动一个变量。$\rho$、$\lambda$、迭代次数三者互相影响如果同时调整出了问题根本不知道是谁引起的。我自己的习惯是先固定 $\rho$ 和迭代次数只调 $\lambda$收敛以后再回来微调 $\rho$。三保存中间变量。调试ADMM最痛苦的是看不到中间过程。建议在循环体里记录每一轮 $w$、$g$、$u$ 的范数变化我每次开新项目都会先把这个日志加上后续所有性能问题都能从日志里直接找到线索。四不要神化ADMM。很多问题用共轭梯度、近端梯度甚至直接闭式解就够了ADMM只是工具箱里的强力备选之一。判断标准依然是那句话拆开后每个子问题是不是真的便宜。如果是就放心大胆地用它。实战中把ADMM用得顺手之后很多看起来复杂的跟踪器都能被拆成几个简单步骤的循环。面对一个全新的优化问题时我现在的第一反应不是去查求解器而是问自己这个问题最舒服的分解方式是什么这样的思路转变比记住任何具体公式都更值得。