针对分式l₁正则化优化问题的自适应ADMM算法

Adaptive ADMM for Optimization Problems with Fractional l₁ Regularization

摘要: 本文研究了一种基于分式$l_1$ 正则化的非凸优化模型，该模型能比传统$l_1$ 范数更精确地逼近$l_0$ 范数的稀疏性。为高效求解此非凸优化问题，我们设计了基于交替方向乘子法的求解框架，并提出了一种自适应的惩罚参数与正则化参数调整策略。该策略能动态调整惩罚参数以平衡原始残差与对偶残差，加速收敛；同时，能自适应地调整正则化参数以维持数据拟合项与正则项的平衡，有效引导迭代过程趋向高质量解。数值实验表明，与现有快速算法相比，本文的方法在求解精度上具有明显的优势，能够稳定地获得更低相对误差的解。而且，该自适应策略增强了对超参数初始设置的鲁棒性，使算法在宽松的参数条件下仍能保持较好的恢复性能，为解决分式$l_1$ 正则化优化问题提供了一个高精度且实用的解决方案。

Abstract: This paper investigates a nonconvex optimization model based on fractional $l_1$ regularization, which provides a superior approximation to the sparsity of the $l_0$ norm compared to conventional $l_1$ norm. To address this, our solution is built around the Alternating Direction Method of Multipliers (ADMM) framework, augmented with a novel strategy for the adaptive tuning of both penalty and regularization parameters. This strategy dynamically balances the primal and dual residuals to accelerate convergence, while adaptively maintaining the equilibrium between the data fidelity and regularization terms, thereby steering the iterations toward high-quality solutions. Our numerical tests show that the proposed method significantly outperforms existing fast algorithms in solution accuracy, reliably achieving lower relative errors. It also exhibits greater robustness, as the adaptive scheme reduces sensitivity to initial hyperparameter choices, allowing it to perform well even with less stringent parameter tuning. Consequently, our approach provides a highly practical and precise solver for problems involving fractional regularization.

1. 引言

稀疏信号恢复是现代信号处理、统计学与机器学习中的核心任务之一，其目标是从远少于信号维度的线性观测中精确恢复原始信号。该问题的一般模型是在线性模型的拟合误差上，增加一个用于诱导稀疏性的正则化项。其中，$l_1$ 范数正则化因其凸性和求解便利而在信号与图像处理，计算机视觉，生物信息学等领域被广泛应用[1]-[3]。然而，有理论与实践表明，$l_1$ 范数会对大值系数产生过度惩罚，使得恢复信号产生偏差，影响其在复杂场景下的最终精度[4]。

研究者们为了克服$l_1$ 范数的这种局限性，提出了用非凸正则化函数来替代传统的$l_1$ 范数。而且已有研究表明，使用非凸正则化函数逼近$l_0$ 范数可以得到比$l_1$ 范数更稀疏的解。分式$l_1$ 正则化模型正是其中一种具有代表性的模型，它通过超参数$r$ ，构建了分数形式的正则化函数，该函数在$r\to \infty$ 时无限趋近于理想的$l_0$ 范数。本文主要研究如下形式的分式$l_1$ 正则化优化问题：

$\underset{x\in {ℝ}^n}{\min }F\left(x\right):=\frac{1}{2}{\Vert Ax-b\Vert }_2^2+\lambda {\displaystyle \sum _{i=1}^n\frac{r\left|x_i\right|}{1+r\left|x_i\right|}}$ . (1)

其中$b$ 为观测向量，$A\in {ℝ}^{m\times n}$ 是感知矩阵($m\ll n$ )，$x\in {ℝ}^n$ 是原始信号，$\lambda >0$ 为正则化参数，$x_i$ 为$x$ 的第$i$ 个分量，$i=1,2,\cdots ,n$ ，$r>0$ 为超参数。

近年来，关于该问题的研究逐步深入。2016年，崔安刚[5]提出了FP-DC算法，通过差分算法将分式$l_1$ 正则化问题转化为一系列凸子问题求解，用实验证明了FP-DC算法恢复成功率远优于Soft算法[6]和Half算法[7]。2019年，Yazdanpanah等人[8]用分式$l_1$ 正则项替换掉$l_0$ 范数，设计出了自适应沃尔泰拉滤波器，并用实验证明了该滤波器比经典方法有更好的性能。2020年，李海洋等人[9]推导出了该模型的闭式阈值表达式，并据此提出了迭代FP阈值算法(FPTA)，实验结果表明，该算法在有噪声和无噪声的情况下均表现出了较好的恢复性能。2024年，崔安刚等人[10]进一步引入动量加速技术，提出了快速FP算法，在保持高精度的同时减少了运行时间，实现了性能的进一步优化。

因为分式函数的非凸性与非光滑性，想要对分式$l_1$ 正则化优化问题进行高效、鲁棒的数值求解会有较大困难。现有的一些算法在求解问题(1)时，往往依赖于复杂的求解或嵌套迭代过程，这不仅计算开销较大，也使得算法整体对参数设置较为敏感，在多样化的场景下不能保持稳定的性能。

而交替方向乘子法(ADMM)作为一类广泛应用于求解优化问题的算法，早已被用于求解稀疏优化问题，且能得到较好的结果[11]。本文的主要工作正是围绕ADMM框架进行，在现有的研究基础上，设计了一种针对分式$l_1$ 正则化优化问题的高精度的数值求解方案。

本文的主要贡献如下：首先，我们使用ADMM算法将该优化问题分成两个子问题，并对子问题进行分析，设计了一种向量化的数值求解策略。该策略通过变量变换与并行计算，能高效地处理子问题，避免传统求解中复杂的标量循环与条件判断，显著提升了单次迭代的计算效率。其次，我们提出了一种双参数自适应策略来解决惩罚参数和正则化参数的选择问题。该策略通过自动调整参数来维持原始残差与对偶残差之间、拟合项与正则项之间的平衡，从而无需手动调参，增强了算法的鲁棒性。最后，通过系统性的数值实验，我们将所提出的算法与主流稀疏恢复算法进行了对比。实验结果表明，我们的方法在成功恢复稀疏信号时，能得到更低的相对误差和更精确的解。

本文的后续安排如下：第2节将介绍分式$l_1$ 正则化问题与ADMM求解框架，详细阐述我们提出的带自适应机制的ADMM算法；第3节通过可靠的数值实验结果展示算法的性能；第4节对全文进行总结与展望。

2. 带自适应机制的精确ADMM算法

在本节中，我们提出了一种求解基于分式函数的$l_1$ 正则化优化问题的带自适应参数机制的精确ADMM算法。这里求出了标准ADMM算法中的子问题的解析解，并借鉴文献[12]中的自适应机制，将其扩展到标准ADMM算法，形成了自适应ADMM算法。

2.1. 标准ADMM算法

为了使用ADMM去解决问题(1)，我们首先引入了一个辅助变量$z$ 去将问题(1)转化为如下的带约束的等价形式：

$\underset{x,z}{\min }\frac{1}{2}{\Vert Ax-b\Vert }_2^2+\lambda {\displaystyle \sum _{i=1}^n\frac{r\left|z_i\right|}{r\left|z_i\right|+1}}\text{s}.\text{t}.x=z.$ (2)

问题(2)的增广拉格朗日函数为：

${ℒ}_{\rho }\left(x,z,y\right)=\frac{1}{2}{\Vert Ax-b\Vert }_2^2+\lambda {\displaystyle \sum _{i=1}^n\frac{r\left|z_i\right|}{1+r\left|z_i\right|}}+y^{\top }\left(x-z\right)+\frac{\rho }{2}{\Vert x-z\Vert }_2^2.$

其中$y\in {ℝ}^n$ 是拉格朗日乘子向量，$\rho >0$ 是惩罚参数。ADMM算法通过交替优化$x$ 、$z$ 和更新乘子$y$ 来求解，其迭代步骤如下：

$x^{k+1}=\arg \underset{x}{\min }\{\frac{1}{2}{\Vert Ax-b\Vert }_2^2+y^{\text{T}}\left(x-z^k\right)+\frac{\rho }{2}{\Vert x-z^k\Vert }_2^2\}$ ; (3)

$z^{k+1}\in \arg \underset{z}{\min }\{\lambda {\displaystyle \sum _{i=1}^n\frac{r\left|z_i\right|}{1+r\left|z_i\right|}}+y^{\text{T}}\left(x^{k+1}-z\right)+\frac{\rho }{2}{\Vert x^{k+1}-z\Vert }_2^2\}$ ; (4)

$y^{k+1}=y^k+\rho \left(x^{k+1}-z^{k+1}\right)$ .

对于问题(3)，由于目标函数是二次凸函数，其最小值点可以通过求梯度并将其设为零来得到唯一解析解。其解析解为：

$x^{k+1}={\left(A^{\top }A+\rho I\right)}^{-1}\left(A^{\top }b+\rho \left(z^k-\frac{y}{\rho }\right)\right)$ .

对于问题(4)，将与$z$ 相关的项合并，该子问题等价于：

.

其中$v^{k+1}=x_{}^{k+1}+\frac{y^k}{\rho }$ 。由于目标函数是可分离的，该问题可分解为$n$ 个独立的标量优化问题：

. (5)

这种可分离性是ADMM算法能够有效处理大规模问题的关键原因之一，因为它允许我们将一个复杂的高维优化问题分解为大量简单的、可并行处理的一维优化问题。

对于问题(5)易得：取得最优解时，$z$ 的分量$z_i^{k+1}$ 的符号和$v_i^{k+1}$ 的符号相同：如果$v_i^{k+1}\ge 0$ ，则$z_i^{k+1}\ge 0$ ；如果$v_i^{k+1}<0$ ，则$z_i^{k+1}<0$ 。

基于符号一致性，我们将问题(5)简化为：

$t^{\ast }\in \arg \underset{t\ge 0}{\min }\{\lambda r\frac{t}{1+rt}+\frac{\rho }{2}{\left(t-\left|v_i^{k+1}\right|\right)}^2\}$ . (6)

此时，$z_i^{k+1}=\text{sign}\left(v_i^{k+1}\right)\cdot t^{*}$ 。通过对该非凸函数进行深入分析，并利用其一阶最优性条件，我们可以推导出最优解可通过求解一个三次方程得到，然后将所求三次方程的所有正实根与0带入问题(5)，比较目标函数值，选择使目标函数值最小的解作为最优解。

具体地，我们在(6)的基础上，将其转化为一个在非负实数域上求解的一维优化问题：

$\underset{t\ge 0}{\min }g\left(t\right)=\lambda r\frac{t}{1+rt}+\frac{\rho }{2}{\left(t-\left|v_i^{k+1}\right|\right)}^2$ . (7)

根据一阶最优性条件，令(7)的一阶导数为0，有：

$g^{\prime }\left(t\right)=\lambda r\frac{1}{{\left(1+rt\right)}^2}+\rho \left(t-\left|v_i^{k+1}\right|\right)=0$ . (8)

在式(8)的基础上，整理可得：

$\rho r^2{t}^3-\rho r\left(r\left|v_i^{k+1}\right|-2\right)t^2+\rho \left(1-2r\left|v_i^{k+1}\right|\right)t+\left(\lambda r-\rho \left|v_i^{k+1}\right|\right)=0$ . (9)

对式(9)两端乘上$r$ ，除以$\rho$ ，令$s=rt$ ，化简得：

$s^3+\left(2-r\left|v_i^{k+1}\right|\right)s^2+\left(1-2r\left|v_i^{k+1}\right|\right)s+\left(\frac{\lambda r^2}{\rho }-r\left|v_i^{k+1}\right|\right)=0$ . (10)

问题(10)可以看作是一个关于$s$ 的一元三次方程，我们参考文献[9]，使用Cardano公式求解方程。然后将所求的所有正实根与0带入问题(7)，再比较$g\left(t\right)$ 的值，选取使$g\left(t\right)$ 值最小的解作为最优解。

在求解上面的$z$ 子问题时，我们为减少逐步求解分量的循环开销，采用了向量化的数值策略来求解所有分量。

2.2. 针对分式$l_1$ 正则化问题的自适应ADMM算法

在标准ADMM算法的基础上，我们结合了自适应$\rho$ 策略和自适应$\lambda$ 策略，提高了ADMM算法的收敛速度和解的精度。

2.2.1. 自适应ρ策略

首先，我们定义原始残差$r^k={\Vert x^k-z^k\Vert }_2$ 和对偶残差$s^k=\rho {\Vert z^k-z^{k-1}\Vert }_2$ ，其中$r^k$ 用来衡量约束违反程度，$s^k$ 用来衡量最优性条件的满足程度。

在ADMM算法中，选择合适的惩罚参数$\rho$ 对收敛速度具有重要影响。当$\rho$ 值过大时，虽然能够加强对等式约束$x=z$ 的惩罚，使原始残差快速下降，但会导致$z$ 子问题中二次项系数过大，使得$z$ 更新步长变小，收敛变慢；当$\rho$ 值过小时，虽然$z$ 子问题更容易求解，但会放松约束条件，导致$x$ 和$z$ 差异过大，使原始残差下降变慢。

为了能动态平衡原始残差和对偶残差的下降速度，我们设计了自适应$\rho$ 调整策略。在每进行10次迭代时，我们调整一次$\rho$ 值。如果$r^k>\mu s^k$ ，此时原始残差占主导，约束违反程度较大，通过将$\rho$ 更新为$\tau \rho$ 来加强对等式约束的惩罚；如果$s^k>\mu r^k$ ，此时对偶残差占主导，说明$\rho$ 值可能过大导致子问题更新不稳定，就将$\rho$ 更新为${\tau }^{-1}\rho$ ，否则保持$\rho$ 不变。其中$\mu >1$ ，$\tau >1$ 为调节参数。我们将$\rho$ 限制在一个合理区间内防止数值不稳定。

自适应$\rho$ 策略免除了手动调整$\rho$ 的过程，实验结果表明，采用自适应$\rho$ 策略后，算法不仅和原来保持了相近的恢复精度，还减少了约一半的运行时间。

2.2.2. 自适应λ策略

定义数据拟合项$f_1=\frac{1}{2}{\Vert Ax-b\Vert }_2^2$ 和稀疏正则项$f_2=\lambda {\displaystyle \sum _{i=1}^n\frac{r\left|x_i\right|}{1+r\left|x_i\right|}}$ ，两项的比例为$\text{ratio}=\frac{f_1}{f_2}$ 。

在目标函数中，正则化参数$\lambda$ 在目标函数中起到平衡数据拟合项和稀疏正则项的重要作用。当$\lambda$ 过大时，解过度稀疏，可能丢失信号细节；当$\lambda$ 过小时，解不够稀疏，拟合误差增大。我们提出了基于目标函数成分平衡的自适应$\lambda$ 策略：如果$\text{ratio}>1+\eta$ ，说明拟合项远大于正则项，为加强解的稀疏性，将$\lambda$ 增大为$\zeta \lambda$ ；如果$\text{ratio < }1+\eta$ ，说明正则项占主导，解可能过度稀疏而丢失细节，通过将$\lambda$ 减小为${\zeta }^{-1}\lambda$ 来减弱稀疏性，否则$\lambda$ 保持不变。其中$\eta >0$ ，$\zeta >1$ 为调节参数，同样，我们会将$\lambda$ 限制在一定的范围内。该策略使得$\lambda$ 能够根据迭代过程动态调整，从而引导算法趋向于一个拟合精度与稀疏性相平衡的解，降低了对初始$\lambda$ 的依赖。

该自适应$\lambda$ 策略动态平衡了拟合项与正则项，还不需要手动调整正则化参数$\lambda$ 。实验结果表明，采用自适应$\lambda$ 策略后，算法得到了比原来更精确的解。

结合了上述两种自适应策略，显著增强了ADMM算法对问题的初始参数设置的鲁棒性。

为继续提高算法效率，我们在$x$ 子问题求解过程中，预计算了矩阵$\left(A^{\top }A+\rho I\right)$ ，并对其进行Cholesky分解，再进行前向后向代换计算$x$ ，显著减少了计算量。然后充分利用MATLAB的向量运算优势，将原来的按分量循环更新改为批量向量化计算，一次性处理所有分量，提高了算法效率。

在算法迭代过程中，我们发现其产生的解分量往往很小但并非精确为零。为了得到真正的稀疏解，我们在算法迭代收敛后采用了硬阈值处理。我们设定一个合理的正阈值$\delta$ ，将所有绝对值小于$\delta$ 的$x$ 分量精确置为零。具体的，如果$\left|x_i^{k+1}\right|<\delta$ ，则令$x_i^{k+1}=0$ ，否则$x_i^{k+1}$ 不变。其中阈值$\delta$ 的选择尤为重要，较大的$\delta$ 可能会将有用的分量置为零，导致解过于稀疏，使恢复的误差增大，而较小的$\delta$ 无法将真正需要置零的分量置为零，无法产生有效的稀疏解。实验证明，在选取合适的$\delta$ 后，该方法不仅能在原来的算法上降低相对误差，还能增强解的稀疏性。

结合以上内容，我们给出针对问题(1)的带自适应策略的精确ADMM算法：

算法1：带自适应策略的精确ADMM算法

输入：$A$ , $\widehat{x}$ , ${\lambda }_0$ , ${\rho }_0$ , $r$ , $b$ , $tol$ , $\delta$ 。

初始化：初始化$x_0=z_0=y_0=0$ ，设置$k=0$ 。

步骤1： $x^{k+1}=\arg \underset{x}{\min }\{\frac{1}{2}{\Vert Ax-b\Vert }_2^2+y^{\text{T}}\left(x-z^k\right)+\frac{\rho }{2}{\Vert x-z^k\Vert }_2^2\}$ ； $z^{k+1}\in \arg \underset{z}{\min }\{\lambda {\displaystyle \sum _{i=1}^n\frac{r\left|z_i\right|}{1+r\left|z_i\right|}}+y^{\text{T}}\left(x^{k+1}-z\right)+\frac{\rho }{2}{\Vert x^{k+1}-z\Vert }_2^2\}$ ； $v_i^{k+1}=x_i^{k+1}+\frac{y_i^k}{\rho }$ ; $t^{\ast }\in \arg \underset{t\ge 0}{\min }\{\lambda r\frac{t}{1+rt}+\frac{\rho }{2}{\left(t-\left|v_i^{k+1}\right|\right)}^2\}$ ; $z_i^{k+1}=\text{sign}\left(v_i\right)\cdot t^{*}$ ; 更新$\rho$ :${\rho }^{k+1}=\{\begin{array}{ll}\tau {\rho }^k\hfill & 若r^k>\mu s^k\hfill \\ {\tau }^{-1}{\rho }^k\hfill & 若s^k>\mu r^k\hfill \\ {\rho }^k\hfill & 其他\hfill \end{array}$ ； 更新$\lambda$ :${\lambda }^{k+1}=\{\begin{array}{ll}\zeta {\lambda }^k\hfill & 若\text{ratio}>1+\eta \hfill \\ {\zeta }^{-1}{\lambda }^k\hfill & 若\text{ratio}<1+\eta \hfill \\ {\lambda }^k\hfill & 其他\hfill \end{array}$ ; $y^{k+1}=y^k+\rho \left(x^{k+1}-z^{k+1}\right)$ ； 步骤2：检查收敛条件 如果不满足终止条件$\max \left(r^k,s^k\right)\le tol$ 或未达到最大迭代次数，令$k=k+1$ ，并转至步骤1； 步骤3：如果$\left|x_i^{k+1}\right|<\delta$ ，则令$x_i^{k+1}=0$ ；

输出：$x^{*}=x^{k+1}$ 。

2.3. 计算复杂度分析

本节我们分析了算法1的计算复杂度，其主要计算成本在于每次迭代中的求解$x$ 的问题(3)和求解$z$ 的问题(4)。

首先，在求解问题(3)时，我们对矩阵$\left(A^{\top }A+\rho I\right)$ 进行了预计算和Cholesky分解，将其分解为下三角矩阵和其转置的乘积。该步骤有三重循环结构，外层循环会遍历矩阵的每一列，其计算复杂度为$O\left(n\right)$ ，中层循环会处理当前列的每个元素，其平均计算复杂度为$O\left(n\right)$ ，内层循环会计算向量内积，其平均计算复杂度也为$O\left(n\right)$ ，这种嵌套循环结构的总复杂度为$O\left(n^3\right)$ 。分解之后，我们利用下三角矩阵进行前向后向代换求解$x$ ，该步骤的平均计算复杂度为$O\left(n^2\right)$ 。我们注意到，当参数$\rho$ 改变时，需要重新计算和分解矩阵$\left(A^{\top }A+\rho I\right)$ ，此时计算复杂度为$O(n^3)$ 。当参数$\rho$ 没有变化时，不需要重新计算和分解，在迭代过程中直接进行前向后向计算，此时计算复杂度为$O\left(n^2\right)$ 。所以求解问题(3)的整体的计算复杂度最小是$O\left(n^2\right)$ ，最大是$O\left(n^3\right)$ 。

其次，在求解问题(4)时，我们需要求解$n$ 个三次方程。每个三次方程都是通过Cardano公式求解，该步骤需要进行固定数量的算数运算，所以每个方程的求解复杂度为$O\left(1\right)$ ，因此，求解$z$ 的问题(4)的总复杂度为$O\left(n\right)$ 。

最后，算法1中的求解$y$ 的复杂度为$O\left(n\right)$ ，计算残差的复杂度为$O\left(n\right)$ ，调整参数$\rho$ 和参数$\lambda$ 的复杂度为$O\left(1\right)$ 。所以算法1每次迭代的总复杂度最低为$O\left(n^2\right)$ ，最高为$O\left(n^3\right)$ 。

3. 数值实验

本章通过一系列数值实验，系统地评估了针对问题(1)所提出的自适应ADMM算法在稀疏信号恢复中的性能。所有实验均在Intel Core i5-13500HX CPU，16GB内存的个人计算机上使用MATLAB R2019a完成。

我们的实验核心聚焦于小规模的欠定系统，采用维度为128 × 512的感知矩阵$A$ ，其元素独立同分布于标准高斯分布，并进行了列归一化处理。真实的稀疏信号$\widehat{x}$ 通过随机生成，其非零元位置均匀随机选取，非零数值服从标准正态分布。$s$ 表示稀疏度，即非零元素的个数。无噪声情况下的观测向量$b$ 由$b=A\widehat{x}$ 生成，因此，我们可以知道系统$b=A\widehat{x}$ 的真实稀疏解。为检验算法鲁棒性，我们也考虑了含噪场景，即$b=A\widehat{x}+\epsilon$ ，其中$\epsilon$ 为高斯白噪声，满足$\epsilon \in N\left(0,\sigma \right)$ 。

在后续的实验中，我们设置$r$ 为0.5，$\delta$ 取10⁻⁸，对于自适应策略的相关参数$\mu$ 取10，$\tau$ 取1.5，$\eta$ 取0.4，$\zeta$ 取1.5，${\lambda }_0$ 取10⁻⁵，${\rho }_0$ 取0.5，且$\lambda$ 和$\rho$ 的更新频率为10，即每10次迭代判断一次是否需要更新$\lambda$ 和$\rho$ 。实验的停止准则设置为$\max \left(s^k,r^k\right)\le tol$ ，其中容差$tol$ 取10⁻⁸。算法的性能主要通过相对误差(Relative Error)、恢复成功率、运行时间(Runtime)来评判。相对误差表示为${\Vert x^{*}-\widehat{x}\Vert }_2/{\Vert \widehat{x}\Vert }_2$ ，实验中使用${\Vert x^{*}-\widehat{x}\Vert }_2^2/{\Vert \widehat{x}\Vert }_2^2$ 来衡量稀疏信号是否成功恢复(设置其小于10⁻⁵表示恢复成功)。

在第一个实验中，我们在稀疏信号的稀疏度为10的情况下，讨论了自适应策略的相关参数$\mu$ ，$\tau$ ，$\eta$ ，$\zeta$ 和更新频率的变化对自适应ADMM算法性能的影响。参数$\mu$ 和参数$\tau$ 是自适应$\rho$ 策略中的参数，参数$\eta$ 和参数$\zeta$ 是自适应$\lambda$ 策略中的参数，我们分别画出了$\mu -\tau$ 和$\eta -\zeta$ 与相对误差和运行时间的热力图。如图1所示，子图1(a)为$\mu -\tau$ 与相对误差的热力图，可以看到，当$\tau$ 取5时，热力图颜色较亮，求出的最优解的相对误差明显较大。当$\tau$ 取1.3，$\mu$ 取10时，热力图颜色最深，相对误差最低。子图1(b)是$\mu -\tau$ 与运行时间的热力图，可以看到$\tau$ 在1.3和1.5，$\mu$ 在20和25时，运行时间普遍较短。其中当$\tau$ 取1.3，$\mu$ 取20时运行时间最短。综合来看，取较小的$\tau$ 会得到较好的相对误差和运行时间。子图1(c)是$\mu -\tau$ 与相对误差的热力图，可以看到当$\zeta$ 不变时，$\eta$ 在一定范围内改变不会引起相对误差的变化，当$\eta$ 不变时，$\zeta$ 取1.8能使求出的最优解有最低的相对误差。子图1(d)是$\eta -\zeta$ 与运行时间的热力图，可以看到当$\eta$ 不变时，$\zeta$ 取1.8能使运行时间最少，其中$\eta$ 取0.6，$\zeta$ 取1.8能让运行时间最少。

图2是自适应参数更新频率与相对误差和运行时间的关系图。可以看到，更新频率在10到390的范围中，相对误差较为稳定，保持在10⁻⁹这个量级，其中最低的相对误差在更新频率为30时取得。随着更新频率的增大，相对误差只在较小范围内波动。更新频率从10到390变化过程中，运行时间总体呈下降趋势，且在更新频率为210时，运行时间最低。若希望算法得到较高精度的解，可以选择较低的更新频率，例如在30左右。若希望算法运行时间短，则可以选择较高的更新频率，例如在210左右。若想平衡相对误差和运行时间，可以选择150左右的更新频率。

然后，我们测试了FPTA算法、标准ADMM算法和带自适应策略的ADMM算法在不同稀疏度的稀疏信号恢复中的成功率，对于每个稀疏度，我们重复50次实验，并给出平均结果。图3的左图显示了在稀疏度为10到60范围内，三个算法恢复稀疏信号的成功率。可以看到，在稀疏度在10到35时，三个算法都有极高的恢复成功率。在稀疏度为40左右时，带自适应策略的ADMM算法和FPTA算法恢复成功率均高于标准的ADMM算法，FPTA算法的恢复成功率略高于带自适应策略的ADMM算法，但差距不大。图3的右图是三个算法的稀疏度和相对误差的平方的关系图。可以很明显的看到，在恢复成功的情况下，带自适应策略的ADMM算法的相对误差的平方明显低于FPTA算法和标准ADMM算法。即与FPTA算法相比，在信号恢复成功率差距不大的情况下，我们的带自适应策略的ADMM算法能有更低的相对误差，能得到更精确的解。

表1详细展示了无噪声的情况下标准ADMM算法、FPTA算法和自适应ADMM算法在稀疏度为10到20间的相对误差(RE)和目标函数值(Fval)。True Fval是由真实稀疏解$\widehat{x}$ 计算得到的真实目标函数值，显然，由各个算法的恢复信号计算得到的目标函数值越接近真实目标函数值越好。在表1中，标准ADMM算法的相对误差维持在10⁻⁶左右的量级，FPTA算法的相对误差稳定在10⁻⁷左右的量级，而带自适应策略的ADMM算法的相对误差稳定在10⁻⁸左右的量级，显著优于另外两种算法。同样，对比另外两种算法，带自适应的ADMM算法得到的目标函数值更加接近于真实的目标函数值。

表2详细展示了有噪声的情况下标准ADMM算法、FPTA算法和自适应ADMM算法在稀疏度为10到20间的相对误差和目标函数值。$\sigma$ 取10⁻⁵。在表2中，标准ADMM算法的相对误差维持在10⁻⁶左右的量级，FPTA算法的相对误差和带自适应策略的ADMM算法的相对误差都稳定在10⁻⁷左右的量级，但带自适应策略的ADMM算法的相对误差略低于FPTA算法的相对误差。同样，带自适应的ADMM算法得到的目标函数值更加接近于真实的目标函数值。

Figure 1. Heatmap of $\mu$ , $\tau$ , $\eta$ , $\zeta$ versus relative error and runtime

图1. $\mu$ ，$\tau$ ，$\eta$ ，$\zeta$ 与相对误差和运行时间的热力图

Figure 2. Relative error and runtime vs. update frequency

图2. 更新频率与相对误差和运行时间的关系图

Figure 3. Recovery success rate and squared relative error vs. sparsity

图3. 恢复成功率和相对误差平方与稀疏度的关系图

Table 1. Relative error and objective function value of each algorithm under noiseless conditions

表1. 无噪声情况下各算法的相对误差和目标函数值

Noiseless	ADMM		ADMM (自适应)		FPTA
s	RE	Fval	RE	Fval	RE	Fval	True Fval
12	7.09e−06	3.55863737e−05	1.13e−08	3.55865619e−05	3.68e−07	3.55865557e−05	3.55865623e−05
14	9.95e−06	4.36855718e−05	1.06e−08	4.36857762e−05	4.06e−07	4.36857662e−05	4.36857766e−05
16	8.37e−06	4.44856287e−05	1.41e−08	4.44859469e−05	4.25e−07	4.44859351e−05	4.44859476e−05
18	1.69e−05	4.87488861e−05	1.77e−08	4.87492938e−05	3.92e−07	4.87492817e−05	4.87492947e−05
20	1.36e−05	5.39375803e−05	1.44e−08	5.39379883e−05	4.16e−07	5.39379718e−05	5.39379891e−05

Table 2. Relative error and objective function value of each algorithm under noisy conditions

表2. 有噪声情况下各算法的相对误差和目标函数值

Noisy	ADMM		ADMM(自适应)		FPTA
s	RE	Fval	RE	Fval	RE	Fval	True Fval
12	8.07e−06	3.82232164e−05	3.23e−07	3.82233707e−05	3.68e−07	3.82233646e−05	3.82233690e−05
14	7.36e−06	4.96526113e−05	2.70e−07	4.96527865e−05	3.54e−07	4.96527716e−05	4.96527804e−05
16	8.71e−06	5.14598077e−05	2.73e−07	5.14600694e−05	2.76e−07	5.14600521e−05	5.14600611e−05
18	8.98e−06	5.87614854e−05	2.74e−07	5.87617812e−05	3.01e−07	5.87617621e−05	5.87617745e−05
20	1.01e−05	6.52293674e−05	2.92e−07	6.52297497e−05	3.38e−07	6.52297153e−05	6.52297363e−05

在实际的实验中，带自适应策略的ADMM算法虽然能得到比FPTA算法更精确的解，但迭代时间会比FPTA算法更长，迭代次数也更多。

4. 结论

本文提出了一种带自适应策略的精确ADMM算法，用于求解分式$l_1$ 正则化优化问题。该算法核心在于设计了自适应惩罚参数与正则化参数的动态调整机制，从而较好地解决了标准ADMM方法中普遍存在的参数敏感问题。其中，自适应$\rho$ 策略通过平衡原始残差与对偶残差的下降速度，加快了算法的收敛速度。而自适应$\lambda$ 策略能平衡目标函数中数据拟合项与稀疏正则项之间的关系，优化迭代过程。仿真实验结果显示，在稀疏信号恢复任务中，本算法表现出良好的性能。尤其在中小规模测试矩阵上，其恢复成功率与FPTA算法相近，但所求得的解在相对误差上更低，更逼近真实的稀疏信号。

带自适应策略的精确ADMM算法虽然在求最优解方面表现优异，但仍存在一些局限，例如在迭代时间和迭代次数上会落后于FPTA算法。未来的研究可以通过完善该算法的收敛性分析，探索有效的加速策略，推广到其他的正则化问题等方面，进一步提高算法的性能和实际应用价值。

基金项目

本研究受到了重庆市自然科学基金(项目编号：CSTB2022NSCQ-MSX0409)和重庆市教育委员会科技项目(基金编号：KJZD-M202201303)的资助。

NOTES

^*通讯作者。