Evaluating the solution performance of the augmented Lagrangian function on Ising machines

技术摘要：评估增广拉格朗日函数在伊辛机上的解性能

问题陈述
伊辛机是专门用于通过将组合优化问题映射到伊辛模型基态来解决问题的专用计算设备。将这些机器应用于受约束问题的一个重大挑战在于约束的构建方式。通常，约束通过惩罚项被纳入目标函数中，这需要一个惩罚系数（$\mu$）来平衡目标函数与约束满足度。该系数涉及一种内在的权衡：如果 $\mu$ 太小，机器会采样到不可行状态；如果 $\mu$ 太大，能量景观（energy landscape）将被约束项所主导，从而掩盖目标函数值的差异，导致难以找到高质量的可行解。虽然存在各种用于调整 $\mu$ 的调优方法，但它们通常依赖于单个参数来管理这种权衡。

方法论
本研究评估了**增广拉格朗日函数（ALF）作为伊辛机的一种替代构建方案，并将其与标准的惩罚函数（PF）构建方案进行了对比。作者利用二次背包问题（QKP）**作为基准测试，这是一个不等式约束问题，目标是在不超过重量容量的情况下最大化物品价值。

1. 构建方式：

   • 惩罚函数： 问题哈密顿量定义为 $H_P(x) = f(x) + \frac{\mu}{2}[g(x) - c]^2$，其中 $f(x)$ 是目标函数，$g(x)=c$ 是约束。
   • 增广拉格朗日函数： 哈密顿量定义为 $H_{AL}(x) = f(x) + \frac{\mu}{2}[g(x) - c]^2 - \lambda[g(x) - c]$。这引入了一个关于约束违反程度呈线性关系的拉格朗日乘子项（$\lambda$）。
   • 本研究将 ALF 视为具有固定超参数（$\mu, \lambda$）的静态构建方式，而非在搜索过程中更新这些参数的迭代算法，尽管迭代式增广拉格朗日法（ALM）作为辅助分析被提及。

2. 实验设置：

   • 求解器： 使用了 Fixstars Amplify 退火引擎（AE）。
   • 实例： 使用了三个具有已知最优解的 QKP 基准实例（$N=100, 200, 300$）。
   • 指标： 性能通过**达到 $\epsilon$ 的时间（$TT_\epsilon$）**进行评估，定义为获得一个目标误差在相对容差 $\epsilon$（设定为 0.05）之内且达到目标概率（$p_R = 0.99$）的可行解所需的总计算时间。
   • 参数： 对 $\mu$（0 到 100）和 $\lambda$（-500 到 500）进行了网格搜索。

主要贡献与结果
本研究定量评估了 ALF 构建方式如何影响解的性能，并将其与 PF 构建方式进行了对比。

• $TT_\epsilon$ 的降低： 与表现最好的 PF 构建方式相比，ALF 构建方式将 $TT_\epsilon$ 降低了约一个数量级。具体而言，对于实例 'r 100 50 5'，PF 的最小 $TT_\epsilon$ 出现在 $\mu=40$ 时，而 ALF 在更小的 $\mu$ 值下（例如 $\mu=5, \lambda=100$）就实现了显著更低的 $TT_\epsilon$ 值。
• 参数依赖性： 结果表明，ALF 允许使用相对较小的 $\mu$ 值同时获得可行解。在 PF 构建中，较小的 $\mu$ 会导致不可行性，而较大的 $\mu$ 则会降低解的质量。ALF 通过使用 $\lambda$ 项来修正能量景观，从而在 $\mu$ 较小时仍能维持目标函数的相对能量尺度，缓解了这一问题。
• 时间演化： 对代表性 ALF 设置下的当前最优解（incumbent solution）的时间演化分析表明，与 PF 相比，ALF 的解在执行时间内更早地达到了平台期（近优目标值）。此外，ALF 的可行解之间的差异也更小。
• 结构性解释： 通过“配方完成（square-completion）”分析，作者展示了 ALF 在数学上等同于移动了约束的有效容量。$\lambda$ 项实际上将惩罚项的极小值从 $H_{const}=0$ 移动到了 $H_{const}=\lambda/\mu$。当 $\lambda > 0$ 时，这会将搜索方向转向总重量较小的物品选择，从而在不需要大 $\mu$ 值的情况下，提高满足原始不等式约束的概率。

意义与主张
论文声称，增广拉格朗日函数是提高伊辛机解性能的一种极具前景的构建方式。其主要意义在于证明了引入拉格朗日乘子项可以使惩罚系数 $\mu$ 保持在较小水平。这保留了目标函数项在能量景观中的贡献，从而比标准惩罚函数更高效地发现具有较小目标误差的可行解。

作者指出，他们的结论是基于 QKP 基准实例和特定的求解器设置得出的。他们明确表示，解释为什么 ALF 能更早达到渐近值的详细动力学机制尚不明确，仍需对状态转移行为进行进一步研究。此外，虽然本研究侧重于构建方式本身，但结果表明，这些优势有可能被迭代式增广拉格朗日法（ALM）所利用，即根据约束违反情况自适应地更新参数，尽管关于迭代更新与直接参数搜索之间的系统性成本比较仍是未来的工作。