論文の概要: Annealed Mean Field Descent Is Highly Effective for Quadratic Unconstrained Binary Optimization

• arxiv url: http://arxiv.org/abs/2504.08315v1
• Date: Fri, 11 Apr 2025 07:36:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-14 14:19:27.308650
• Title: Annealed Mean Field Descent Is Highly Effective for Quadratic Unconstrained Binary Optimization
• Title（参考訳）: Annealed Mean Field Descentは2次非拘束二項最適化に非常に有効である
• Authors: Kyo Kuroki, Thiem Van Chu, Masato Motomura, Kazushi Kawamura,
• Abstract要約: 本稿では,平均場アニーリング(MFA)とその変種を理論的に解析する。 この制限に対処する新しい手法であるAnnealed Mean Field Descent (AMFD)を提案する。 AMFDは多くのケースで優れた性能を示し、最先端のQUBOソルバやグロビに比べて問題依存度が低い。
• 参考スコア（独自算出の注目度）: 2.2070611256611627
• License:
• Abstract: In recent years, formulating various combinatorial optimization problems as Quadratic Unconstrained Binary Optimization (QUBO) has gained significant attention as a promising approach for efficiently obtaining optimal or near-optimal solutions. While QUBO offers a general-purpose framework, existing solvers often struggle with performance variability across different problems. This paper (i) theoretically analyzes Mean Field Annealing (MFA) and its variants--which are representative QUBO solvers, and reveals that their underlying self-consistent equations do not necessarily represent the minimum condition of the Kullback-Leibler divergence between the mean-field approximated distribution and the exact distribution, and (ii) proposes a novel method, the Annealed Mean Field Descent (AMFD), which is designed to address this limitation by directly minimizing the divergence. Through extensive experiments on five benchmark combinatorial optimization problems (Maximum Cut Problem, Maximum Independent Set Problem, Traveling Salesman Problem, Quadratic Assignment Problem, and Graph Coloring Problem), we demonstrate that AMFD exhibits superior performance in many cases and reduced problem dependence compared to state-of-the-art QUBO solvers and Gurobi--a state-of-the-art versatile mathematical optimization solver not limited to QUBO.
• Abstract（参考訳）: 近年,準拘束的二項最適化 (QUBO) として様々な組合せ最適化問題の定式化が注目されている。 QUBOは汎用フレームワークを提供するが、既存のソルバは様々な問題におけるパフォーマンスの変動に悩まされることが多い。 この論文は i) 平均場アニーリング(MFA)とその変種を理論的に解析し、その基礎となる自己整合方程式が平均場近似分布と正確な分布の間のクルバック・リーブラの最小条件を必ずしも表さないことを示した。 (II) 分散を直接最小化してこの制限に対処する新しい手法であるAnnealed Mean Field Descent (AMFD)を提案する。 5つのベンチマーク組合せ最適化問題(最大カット問題、最大独立セット問題、トラベリングセールスマン問題、擬似アサインメント問題、グラフカラー問題)の広範な実験を通して、AMFDはQUBOに限らず、最先端のQUBOソルバやGurobiよりも優れた性能を示し、問題依存を低減していることを示した。

関連論文リスト

• Non-Myopic Multi-Objective Bayesian Optimization [64.31753000439514]
  多目的最適化問題を解くために、有限水平逐次実験設計の問題を考察する。 この問題は、材料設計を含む多くの現実世界の応用で発生する。 我々はMOO問題に対する最初の非ミオピック手法を提案する。
  論文  参考訳（メタデータ） (2024-12-11T04:05:29Z)
• Optimized QUBO formulation methods for quantum computing [0.4999814847776097]
  実世界の金融シナリオにインスパイアされたNPハード最適化問題に対して,我々の手法を適用する方法について述べる。 2つのD波量子異方体にこの問題の事例を提出し、これらのシナリオで使用される標準手法と新しい手法の性能を比較した。
  論文  参考訳（メタデータ） (2024-06-11T19:59:05Z)
• Deriving Compact QUBO Models via Multilevel Constraint Transformation [0.8192907805418583]
  そこで本稿では,QUBOモデルに基づくMLCTS(Multilevel Constraint Transformation Scheme)を提案する。 概念実証では、後者の問題に対する2つのQUBOモデルの性能を、汎用ソフトウェアベースソルバとハードウェアベースのQUBOソルバで比較する。 MLCTS由来のモデルは、ハードウェアベースのアプローチで最大7倍のインスタンスを解くことで、両方のソルバのパフォーマンスを著しく向上させる。
  論文  参考訳（メタデータ） (2024-04-04T17:34:08Z)
• Towards Efficient Pareto-optimal Utility-Fairness between Groups in Repeated Rankings [7.6275971668447005]
  消費者と生産者のパレート最適バランスを保証し、ランキングの列を計算する問題に対処する。 本稿では,全ての項目が露出する点を表すペルムタヘドロンであるExpohedronを用いて,上記の問題に対する新しいアプローチを提案する。 さらに,Expohedronの囲む$n$-sphereの最適化問題を緩和し,実行時間を大幅に改善する効率的な手法を提案する。
  論文  参考訳（メタデータ） (2024-02-22T05:48:54Z)
• No-Regret Constrained Bayesian Optimization of Noisy and Expensive Hybrid Models using Differentiable Quantile Function Approximations [0.0]
  Constrained Upper Quantile Bound (CUQB) は、制約近似を避けるための概念的に単純で決定論的アプローチである。 CUQBは制約のある場合と制約のない場合の両方において従来のベイズ最適化よりも著しく優れることを示す。
  論文  参考訳（メタデータ） (2023-05-05T19:57:36Z)
• Efficient Alternating Minimization Solvers for Wyner Multi-View Unsupervised Learning [0.0]
  本稿では,計算効率のよい解法の開発を可能にする2つの新しい定式化法を提案する。 提案した解法は, 計算効率, 理論的収束保証, ビュー数による局所最小値複雑性, 最先端技術と比較して, 例外的な精度を提供する。
  論文  参考訳（メタデータ） (2023-03-28T10:17:51Z)
• Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
  本稿では,不確実量を比較する問題に対して,単純かつ効率的なアプローチを開発する。 我々はラグランジアンの内部最適化をサロゲート近似の学習問題として再考した。 提案したライト-SDは、ファイナンスからサプライチェーン管理に至るまで、いくつかの代表的な問題において優れた性能を示す。
  論文  参考訳（メタデータ） (2022-11-14T21:54:31Z)
• Algorithm for Constrained Markov Decision Process with Linear Convergence [55.41644538483948]
  エージェントは、そのコストに対する複数の制約により、期待される累積割引報酬を最大化することを目的としている。 エントロピー正規化ポリシーとベイダの二重化という2つの要素を統合した新しい双対アプローチが提案されている。 提案手法は(線形速度で)大域的最適値に収束することが示されている。
  論文  参考訳（メタデータ） (2022-06-03T16:26:38Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。