技术摘要：一种用于线性约束双层优化的单圈一阶算法

问题阐述

本文研究了下层（LL）问题具有强凸性且受耦合线性约束限制的双层优化（BLO）问题。通用问题公式如下：
$$\begin{aligned} \min_{x \in \mathbb{R}^{d_x}} \quad & \Phi(x) \triangleq f(x, y^*(x)) \\ \text{s.t.} \quad & y^*(x) \in \arg \min_{y \in Y(x)} g(x, y) \end{aligned}$$
其中，下层的可行集由耦合约束 $Y(x) = \{ y \in \mathbb{R}^{d_y} \mid h(x, y) \leq 0 \}$ 定义。本文的研究重点是 $h(x, y) = Bx + Ay - b$，其中$B \in \mathbb{R}^{d_h \times d_x}$且$A \in \mathbb{R}^{d_h \times d_y}$ 的情况。

该问题的核心挑战在于：

1. 非光滑性： 由于约束的存在，超目标函数 $\Phi(x)$ 通常是不可微的。
2. 计算成本： 现有的处理约束双层优化（Constrained BLO）的方法通常依赖于隐式梯度下降，这需要计算下层问题的 Hessian 矩阵。对于大规模问题，这在计算上是难以承受的。
3. 算法复杂度： 针对耦合约束的前一阶方法通常采用双圈或三圈结构，导致收敛速率欠佳（例如 $O(\epsilon^{-3} \log(\epsilon^{-1}))$）且实现难度较大。

方法论

1. 理论重构

为了克服非光滑性并避免 Hessian 计算，作者利用惩罚法将原始问题重构为一个单层极小极大（minimax）问题。他们定义了一个惩罚函数 $\Phi_\delta(x)$：
$$\Phi_\delta(x) \triangleq \min_{y \in Y(x)} \max_{z \in Y(x)} \left[ f(x, y) + \frac{1}{\delta} (g(x, y) - g(x, z)) \right]$$
其中 $\delta > 0$ 是惩罚参数。

关键理论贡献：

• 值与导数的接近性： 本文建立了严谨的非渐近界限，证明了对于足够小的 $\delta$，值之差 $|\Phi(x) - \Phi_\delta(x)|$ 和梯度之差 $\|\nabla \Phi(x) - \nabla \Phi_\delta(x)\|$ 是接近的（具体为 $O(\delta)$）。
• 可微性： 在强凸性、Lipschitz 连续性和**线性无关约束限定（LICQ）**的假设下，作者证明了 $\Phi_\delta(x)$ 是可微的，而原始的 $\Phi(x)$ 可能不可微。这为优化 $\Phi_\delta$ 而非 $\Phi$ 提供了理论依据。

2. SFLCB 算法

基于上述重构，作者提出了 SFLCB（用于线性约束双层优化的单圈一阶算法）。

• 增广拉格朗日量： 为了在第一阶框架内有效处理线性约束 $Bx + Ay - b \leq 0$，通过引入松弛变量将不等式约束转换为等式约束。构建了一个增广拉格量函数 $K$，以确保下层变量的强凸性和对偶变量的强凹性。
• 单圈结构： 与以往需要嵌套循环来求解内部子问题的研究不同，SFLCB 采用了**单圈梯度下降-上升（GDA）**方案。它同时更新：
  • 上层变量 $x$。
  • 下层原变量 $y$ 和 $z$。
  • 拉格朗日乘子（对偶变量）$u$ 和 $v$。
• 无 Hessian 依赖： 该算法仅依赖于一阶梯度，消除了对 Hessian 矩阵计算的需求。

主要贡献

1. 重构的理论依据： 本文首次提供了严谨的非渐近分析，在存在耦合约束 $Y(x)$ 的情况下，确立了原始超目标 $\Phi$ 与惩罚函数 $\Phi_\delta$ 之间值与导数的接近性。以往的工作（如 [21]）仅在约束独立于 $x$ 的情况下建立了这一结论。
2. 改进的收敛速率： 作者证明了 SFLCB 在寻找 $\Phi_\delta$ 的 $\epsilon$-驻点时，其迭代复杂度达到 $O(\epsilon^{-3})$。这优于以往针对耦合约束的双圈算法（如 [16]），后者的复杂度为 $O(\epsilon^{-3} \log(\epsilon^{-1}))$。
3. 实际效率： 通过利用单圈结构并避免 Hessian 计算，该算法旨在比现有的隐式梯度或多圈方法更易于实现，且在大规模问题上更具扩展性。

实验结果

作者通过三个任务验证了理论发现：

1. 玩具示例： 在一个合成约束双层优化问题中，SFLCB 从各种初始化出发，始终能收敛到超目标的局部极小值。
2. SVM 超参数优化： 使用糖尿病数据集，将 SFLCB 与最先进的方法（GAM, LV-HBA, BLOCC, BiC-GAFFA）进行对比。结果显示 SFLCB 的收敛速度显著快于所有基准方法。
3. 运输网络设计： 应用于模拟运营商利润与乘客行为的合成网络（3 节点和 9 节点）。SFLCB 在上层效用方面优于 BLOCC 算法。

此外，针对惩罚参数 $\delta$ 的敏感性分析表明，适中的 $\delta$ 值能在收敛速度与近似误差之间取得平衡，这与理论预测一致。

意义与主张

本文声称，SFLCB 通过弥合理论重构与实际算法效率之间的差距，在解决线性约束双层优化方面取得了重大进展。

• 理论影响： 它将基于惩罚法的重构有效性扩展到了耦合约束领域，为该设置下的单圈方法提供了坚实的理论基础。
• 算法影响： 它提供了一种无 Hessian、单圈的算法，将收敛速率从 $O(\epsilon^{-3} \log(\epsilon^{-1}))$ 提升至 $O(\epsilon^{-3})$。
• 实践影响： 该方法被证明在超参数调优和网络设计等约束固有且计算资源有限的现实应用场景中非常有效。

作者承认，目前的分析目前仅限于确定性设置和线性约束，这表明将这些结果扩展到随机环境或更通用的约束结构是未来研究的一个有前景的方向。他们还指出，在约束情况下实现已知于无约束 BLO 的最优 $O(\epsilon^{-2})$ 速率仍是一个开放性问题。