二次等式约束最小二乘问题：实现全局最优的低复杂度ADMM算法

《IEEE Signal Processing Letters》：Quadratic Equality Constrained Least Squares: Low-complexity ADMM for Global Optimality

本文针对信号处理与通信领域中广泛存在的非凸优化问题——二次等式约束最小二乘（QEC-LS）问题，提出了一种基于交替方向乘子法（ADMM）的低复杂度算法。研究证明了该算法在二次项等于正常数的条件下能够全局收敛，数值实验表明其计算效率显著优于半定松弛（SDR）和原始对偶法（PDM），为大规模实时应用提供了新解决方案。

　　

在当今信号处理与通信技术飞速发展的时代，研究人员经常需要解决一类特殊的数学优化问题——二次等式约束最小二乘（Quadratic Equality Constrained Least Squares， QEC-LS）问题。这类问题在雷达系统、无线通信、集成传感与通信（ISAC）、阵列处理和图像处理等众多领域有着广泛应用，其核心是在一个?₂-范数球面上求解最小二乘问题。

然而，这一看似简单的问题却因其非凸特性而充满挑战。传统解决方法如半定松弛（Semidefinite Relaxation， SDR）虽然能够获得全局最优解，但需要将原问题提升到更高维度的半定形式，导致计算负担急剧增加，特别在大规模问题和实时应用中变得难以承受。原始对偶法（Primal-Dual Method， PDM）虽然理论上有望解决问题，但实际应用中需要通过二分法或牛顿法求解非线性标量方程来满足功率约束，这一过程在大规模环境下极为耗时。

针对这些挑战，由Tong Wei、Huiping Huang、Linlong Wu、Chong-Yun Chi、Bhavani Shankar M. R.和Bj?rn Ottersten组成的研究团队在《IEEE Signal Processing Letters》上发表了一项创新研究，提出了一种基于交替方向乘子法（Alternating Direction Method of Multipliers， ADMM）的新型算法，以低计算复杂度实现QEC-LS问题的全局最优解。

研究团队首先通过理论分析证明了QEC-LS问题在温和条件下（P>0）强对偶性成立，这意味着即使原问题是非凸的，其对偶问题也能提供与原问题相同的最优解。基于这一重要发现，研究人员将原问题重新表述为适合ADMM框架的形式，引入了辅助变量将复杂的等式约束分解为更易处理的子问题。

关键技术方法包括：问题重构技术，将原QEC-LS问题转化为包含辅助变量的等价形式；拉格朗日对偶理论分析，证明非凸问题的强对偶性；ADMM算法设计，通过变量分裂技术将复杂问题分解为多个简单子问题；以及收敛性分析，确保算法在非凸设置下的全局收敛性。研究还进行了详细的复杂度分析，比较了不同方法的计算效率。

II. 全局ADMM解

研究团队首先将原始问题重新表述为包含辅助变量的等价形式，从而使得ADMM框架能够有效应用。通过理论证明，即使在非凸情况下，问题仍满足强对偶性，这是确保算法全局收敛的关键理论基础。ADMM算法的核心是将复杂问题分解为三个相对简单的子问题：x-更新子问题涉及求解一个正则化的最小二乘问题；z-更新子问题是一个简单的投影操作，将点投影到功率约束的球面上；v-更新子问题是对偶变量的梯度上升步骤。每个子问题都有闭式解，保证了算法的高效性。

收敛性分析

研究团队对ADMM算法的收敛性能进行了严格分析，证明了算法在迭代过程中能够满足残差收敛、目标函数收敛、对偶变量收敛和稳定点收敛四个重要性质。尽管问题是非凸的，但基于强对偶性的成立，ADMM迭代能够收敛到全局最优解。这一理论保证使得该方法在实用中具有可靠性。

复杂度分析

通过详细的复杂度比较，研究显示SDR方法的复杂度为O(N⁶)，PDM的复杂度为O(2N³+ Nlog(1/ε) + MN²)，而提出的ADMM方法复杂度为O(N³+ K(MN + N²+ 2N))，其中K是迭代次数。这表明ADMM在大规模问题上具有明显的计算优势。

III. 仿真结果

仿真实验验证了所提算法的优越性能。在收敛性方面，当惩罚参数ρ=0.2时，算法通常能在11次迭代内收敛，显示了其高效性。

-6'>

残差分析表明，原始残差和对偶残差都单调递减到零，证明了算法更新的稳定性。

计算效率比较显示，ADMM方法在达到相同目标函数值的情况下，比SDR和PDM具有更短的运行时间。当N=350时，ADMM比PDM快两倍；当N=7000时，ADMM比PDM快三倍。

-14'>

-14'>

精度分析表明，随着阈值ε的减小，ADMM与SDR之间的解误差减小，而运行时间没有显著增加，证明了算法在保证精度的同时维持了计算效率。

研究结论与意义

这项研究针对QEC-LS这一重要的非凸优化问题，提出了一种基于ADMM的低复杂度算法，并在理论上证明了其全局收敛性。与需要复杂调整或高计算成本的传统方法不同，该方法提供了一个简单而有效的迭代方案，具有可靠的收敛保证。数值实验验证了该方法在保持解的精度的同时，显著提高了计算效率，特别适用于大规模和实时应用场景。

该研究的重要意义在于为信号处理和通信领域中的非凸优化问题提供了新的解决思路，将理论保证与计算效率相结合，解决了实际应用中的关键挑战。方法的简单性和有效性使其易于在实际系统中实施，为雷达系统、无线通信、ISAC等领域的实时处理应用提供了有力的工具。未来，这一框架有望扩展到更广泛的非凸优化问题类别，进一步推动优化理论在实际工程中的应用。