利用ADMM方法通过松弛变量求解二次规划而不增加问题规模

《European Journal of Control》：Solving Quadratic Programs with Slack Variables via ADMM without Increasing the Problem Size

　　摘要：像交替方向乘子法（ADMM）这样的近端方法在求解带约束的二次规划问题时非常有效。为了解决不可行的二次规划问题，通常会引入松弛变量以确保问题的可行性，但这会改变问题的结构、增大问题规模并降低数值求解速度。在本文中，我们提出了一种简单的ADMM方案，用于处理带有松弛变量的二次规划问题，且无需增加原问题的规模。唯一的修改是在z更新步骤中的投影方式略有不同，而算法的其他部分则保持不变。我们证明了该方法等同于对带有额外松弛变量的二次规划问题应用ADMM，即便实际上并未添加松弛变量。数值实验表明该方法的求解速度更快。

引言：数值优化是控制领域中众多算法和应用的基石。例如，模型预测控制（MPC）算法通过反复求解优化问题来选择控制输入，其应用范围广泛，包括机器人技术Adabag等人（2024年）、Tranzatto等人（2022年）、Wensing等人（2023年），汽车领域Del Re等人（2010年）、Lew等人（2025年），以及电力系统Vazquez等人（2014年）、Venkat等人（2008年）。MPC往往依赖于反复求解形式为minx12x?Qx+q?xs.t.?≤Ax≤u的带约束二次规划问题，其中x∈Rn为优化变量，Q∈Rn×n为半正定矩阵，q∈Rn，A∈Rp×n，?≤u∈Rp。像交替方向乘子法（ADMM）Boyd等人（2011年）、O’donoghue等人（2016年）、Stellato等人（2020年）这样的近端方法已被证明在解决此类问题方面十分有效。

在许多应用中，二次规划问题可能会变得不可行。例如，当赛车在摩擦极限状态下运行时Lew等人（2025年），由于模型不匹配，它可能会暂时偏离道路边缘。为在这种情况下维持系统运行，人们可能需要一种能够近似求解二次规划问题的方法。因此，实际应用中常常采用带软约束的二次规划问题来处理，其中ξ∈Rp为额外的松弛变量，α?>?0为惩罚系数：minx,ξ12x?Qx+q?x+α2∥ξ∥22s.t.?≤Ax+ξ≤u。通过在约束条件中引入松弛变量ξ，带松弛变量的二次规划问题始终是可行的，并且通过选择足够大的惩罚系数α，其解可以尽可能接近标准二次规划问题的解。从可行性角度来看，这种放宽后的问题与在成本函数中加入惩罚项具有类似的效果Feller和Ebenbauer（2017年）、Oancea等人（2023年）。

标准方法：带松弛变量的二次规划问题可以重新表述为标准二次规划问题，因为它等价于以下问题：minxˉ=(x,ξ)12xˉ?Qˉxˉ+qˉ?xˉs.t.?≤Aˉxˉ≤u，其中xˉ=[xξ]，Qˉ=[Q00α]，qˉ=[q0]，Aˉ=[AI]。这样，带松弛变量的二次规划问题就变成了带有额外优化变量ξ的标准二次规划问题，可以使用诸如OSQP这样的通用二次规划求解器来求解Stellato等人（2020年）。不过，这种方法存在两个局限性。首先，由于问题规模增大，与直接求解标准二次规划问题相比，其数值求解速度会更慢（假设标准二次规划问题是可行的）。其次，针对特定应用的算法（如MPC算法）会利用(Q, q, A, ?, u)的结构来提高效率（如Adabag等人2024年），而通过这种标准重述方式引入松弛变量ξ后，结构的改变可能会减缓算法的开发与数值实现进程。

贡献：我们提出了一种用于求解带松弛变量的二次规划问题的ADMM方法，相比标准方法，它不仅求解速度更快，而且实现起来更为简单。该方法仅对标准ADMM中用于标准二次规划问题的投影步骤进行了轻微修改（见表1），从而无需引入松弛变量即可求解带松弛变量的二次规划问题，同时保持了问题规模不变，进而提升了求解速度，同时还保留了其他ADMM方法所具有的收敛性保证。我们给出了该算法的两种推导方式，其中一种表明所提出的方法其实只是基于一种特殊的分裂策略得到的用于带松弛变量二次规划问题的ADMM方案，该策略能够消除松弛变量。我们还公开了该ADMM方法的代码及相关实验结果。

章节节选：

用于二次规划问题的ADMM：我们首先描述如Boyd等人（2011年）所阐述的用于求解二次规划问题的标准ADMM方案。在整篇论文中，我们对定义二次规划问题的矩阵(Q, A)做如下假设：假设1：对于任何ρ?>?0，矩阵Q+ρA?A都是可逆的。虽然我们将放宽这一假设的工作，比如使用Stellato等人（2020年）提出的分裂策略，留到未来的研究中，但需要指出的是，对于不满足假设1的二次规划问题，可以通过添加足够多的无效约束?∞≤xi≤∞，使得A?A变为可逆矩阵。

用于带松弛变量二次规划问题的ADMM：我们提出了一种简单的ADMM方案（ADMMSlack），用于在不向问题中添加松弛变量ξ的情况下求解带有松弛变量的二次规划问题QPslack。在本节中，我们首先通过平滑指示函数来推导该方案。在下一节中，我们将证明该方案实际上能够求解QPslack。考虑如下问题：minx,z12x?Qx+q?x+I?[?,u](z)s.t.Ax=z，其中I?[?,u](·)表示平滑指示函数，其定义为I?[?,u](z)=∑i=1pI?i(zi)，而I?i(zi)的取值为：若?i≤zi≤ui，则I?i(zi)=0；若ziui，则I?i(zi)=α2(zi?ui)2。

ADMMSlack实际上是另一种分裂策略下的用于QPslack的ADMM：ADMMSlack最初是作为针对QP?的ADMM方案推导出来的，与QPslack之间并没有明显的关联。在本节中，我们将展示ADMMSlack实际上也可以等价地视为用于求解QPslack的ADMM方案，即先依次优化x，然后再优化(z, ξ)，将松弛变量ξ视为另一个辅助变量。首先需要注意的是，QPslack也等价于如下问题：minx,z,ξ12x?Qx+q?x+α2∥ξ∥22s.t.Ax=z,?≤z+ξ≤u，这又等价于minx,z,ξ12x?Qx+q?x+α2∥ξ∥22+I[?,u](z+ξ)s.t.Ax=z。接着，我们定义增广拉格朗日函数L(x,z,ξ,μ):=

数值结果：我们将所提出的ADMMSlack方案与标准ADMM方案在含有松弛变量的问题上进行了比较，相关算法总结见表1。这两种ADMM方案都在包含松弛变量的随机MPC问题上进行了测试，问题形式为：minx,u,ξ∑k=0N12∥xk∥Q2+∑k=0N?112∥uk∥R2+α2∥ξ∥2s.t.xk+1=Axk+Buk+ξkA,k=0,?,N,x0=xs+ξs,x￣≤xk+ξkx≤x￣,k=0,?,N,u￣≤uk+ξku≤u￣,k=0,?,N?1，其中∥x∥Q2:=x?Qx，N=20，α=10，松弛变量ξ:=((ξkA)k=0N,ξs,(ξkx)k=0N,(ξku)k=0N?1)。我们对这些MPC问题进行了随机采样。

结论：使用ADMM方案处理松弛变量并不一定需要增加问题的规模。这一发现可以被整合到其他求解器中，以提高它们在处理带有松弛变量的二次规划问题时的性能。虽然我们主要研究了基于‖ξ‖2的二次惩罚方式，但研究其他惩罚方式，如1-范数‖ξ‖1，也将具有很大的意义。

CRediT作者贡献说明：Thomas Lew：概念构思、形式分析、研究调查、方法设计、软件开发、验证、初稿撰写、审稿与编辑。Marcus Greiff：概念构思、形式分析、研究调查、方法设计、验证、审稿与编辑。John Subosits：审稿与编辑、监督指导、验证工作、资源协调、项目管理、方法设计、研究调查、资金筹集。Brian Plancher：概念构思、形式分析、研究调查、利益冲突声明撰写。作者声明他们不存在任何可能影响本文研究成果的已知财务利益或个人关系。

Thomas Lew|Marcus Greiff|John Subosits|Brian Plancher
美国加利福尼亚州洛斯阿尔托斯市丰田研究院