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

技術要約：イジングマシンにおける拡張ラグランジュ関数の解性能評価

問題提起
イジングマシンは、問題をイジングモデルの基底状態にマッピングすることで組合せ最適化問題を解くために設計された特化型のコンピューティングデバイスである。制約付き問題にこれらのマシンを適用する際の大きな課題は、制約の定式化である。通常、制約はペナルティ項を通じて目的関数に組み込まれるが、これには目的関数と制約充足のバランスを取るためのペナルティ係数（$\mu$）が必要となる。この係数には固有のトレードオフが存在する。すなわち、$\mu$が小さすぎるとマシンは実行不可能な状態をサンプリングし、$\mu$が大きすぎるとエネルギー地形が制約項によって支配され、目的関数の値の差異が不明瞭になり、高品質な実行可能解を見つけることが困難になる。$\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 Annealing Engine (AE) を使用した。
   • インスタンス: 最適解が既知である3つのQKPベンチマークインスタンス（$N=100, 200, 300$）を使用した。
   • 指標: 性能は、相対誤差 $\epsilon$（0.05に設定）以内の実行可能解を得るために必要な総計算時間である Time-to-Epsilon ($TT_\epsilon$) を用いて評価された（目標確率 $p_R = 0.99$）。
   • パラメータ: $\mu$ (0 から 100) および $\lambda$ (-500 から 500) に関するグリッドサーチを実施した。

主な貢献と結果
本研究は、ALF定式化がPF定式化と比較して、解の性能にどのように影響するかについての定量的な評価を提供している。

• $TT_\epsilon$ の減少: ALF定式化は、最も優れた性能を示したPF定式化と比較して、$TT_\epsilon$ を約1桁減少させた。具体的には、インスタンス '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の設定下でのインカンベント解（現行解）の時間的推移の分析により、PFと比較して、ALFの方が実行時間の早い段階でプラトー（近最適目的関数値）に到達することが示された。さらに、ALFにおける実行可能解間の変動は、PFよりも小さかった。
• 構造的説明: 「平方完成」による分析を通じて、著者らはALFが制約の実効容量をシフトさせることと数学的に等価であることを示した。$\lambda$ 項は、ペナルティ項の最小値を $H_{const}=0$ から $H_{const}=\lambda/\mu$ へと実質的にシフトさせる。$\lambda > 0$ の場合、これは探索を合計重量がより小さい項の選択へとシフトさせ、大きな $\mu$ を必要とせずに元の不等式制約を満たす確率を高める。

意義と主張
本論文は、拡張ラグランジュ関数がイジングマシンの解性能を向上させるための有望な定式化であると主張している。主な意義は、ラグランジュ乗数項の導入により、ペナルティ係数 $\mu$ を小さく保つことができる点にある。これにより、エネルギー地形における目的関数項の寄与が保持され、標準的なペナルティ関数よりも効率的に、小さな目的関数誤差を持つ実行可能解を発見することが容易になる。

著者らは、これらの結論がQKPベンチマークインスタンスおよび特定のソルバー設定に基づいていることを注記している。また、ALFがなぜより早い段階で漸近値に到達するのかを説明する詳細な動的メカニズムは未解明であり、状態遷移挙動に関するさらなる調査が必要であると明示している。加えて、本研究は定式化自体に焦点を当てているが、得られた結果は、制約違反に基づいてパラメータを適応的に更新する反復的拡張ラグランジュ法（ALM）によって、これらの利点が活用できる可能性を示唆している。ただし、反復的な更新と直接的なパラメータ探索との系統的なコスト比較については、今後の課題として残されている。