論文の概要: Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates

• arxiv url: http://arxiv.org/abs/2307.08816v2
• Date: Tue, 27 Feb 2024 18:55:22 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-28 22:36:47.491821
• Title: Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates
• Title（参考訳）: 強化学習サロゲートによるカットプレーンアルゴリズムの高速化
• Authors: Kyle Mana, Fernando Acero, Stephen Mak, Parisa Zehtabi, Michael Cashmore, Daniele Magazzeni, Manuela Veloso
• Abstract要約: 凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
• 参考スコア（独自算出の注目度）: 49.84541884653309
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Discrete optimization belongs to the set of $\mathcal{NP}$-hard problems, spanning fields such as mixed-integer programming and combinatorial optimization. A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms, which reach optimal solutions by iteratively adding inequalities known as \textit{cuts} to refine a feasible set. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. In this work, we propose a method for accelerating cutting-plane algorithms via reinforcement learning. Our approach uses learned policies as surrogates for $\mathcal{NP}$-hard elements of the cut generating procedure in a way that (i) accelerates convergence, and (ii) retains guarantees of optimality. We apply our method on two types of problems where cutting-plane algorithms are commonly used: stochastic optimization, and mixed-integer quadratic programming. We observe the benefits of our method when applied to Benders decomposition (stochastic optimization) and iterative loss approximation (quadratic programming), achieving up to $45\%$ faster average convergence when compared to modern alternative algorithms.
• Abstract（参考訳）: 離散最適化は$\mathcal{NP}$-hard問題の集合に属し、混合整数プログラミングや組合せ最適化のような分野にまたがる。 凸離散最適化問題を解くための現在の標準的なアプローチは切断平面アルゴリズム(英語版)(cut-plane algorithm)であり、これは実現可能な集合を洗練するために \textit{cuts} として知られる不等式を反復的に加えることによって最適解に達する。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模離散最適化問題は難解さに苦しんでいる。 本研究では,強化学習による切削面アルゴリズムの高速化手法を提案する。 私たちのアプローチでは、カット生成手順の$\mathcal{np}$-hard要素の代理として学習ポリシーを使用します。 (i)収束を加速し、 (ii)最適性の保証を保持する。 提案手法は,確率最適化と混合整数二次計画法という,切削平面アルゴリズムが一般的に用いられる2種類の問題に適用する。 我々は,Benders分解(確率的最適化)および反復的損失近似(四進法プログラミング)に適用した場合の手法の利点を観察し,現代の代替アルゴリズムと比較して最大45\%の高速平均収束を実現する。

関連論文リスト

• A Pure Quantum Approximate Optimization Algorithm Based on CNR Operation [0.0]
  汎用的な純粋量子近似最適化アルゴリズムを提案する。 このアルゴリズムは$p$レベルの分割・対数構造に構成されている。 2つの最適化問題の必要なキュービット数が10である場合、アルゴリズムの性能を詳細に示す。
  論文  参考訳（メタデータ） (2023-10-27T06:54:39Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Optimizing Optimizers: Regret-optimal gradient descent algorithms [9.89901717499058]
  我々は,後悔最適アルゴリズムの存在,一意性,一貫性について検討する。 制御問題に対する一階最適条件を提供することにより、後悔最適アルゴリズムはそれらの力学において特定の構造を満たす必要があることを示す。 それらを近似する高速な数値法を提案し,長期的後悔を直接最適化する最適化アルゴリズムを生成する。
  論文  参考訳（メタデータ） (2020-12-31T19:13:53Z)
• Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization [21.555331273873175]
  ネットワークのノードにまたがるスムーズな凸関数の和を分散化最小化する作業について検討する。 本稿では,この分散最適化問題に対する2つの新しいアルゴリズムを提案し,複雑性を保証する。
  論文  参考訳（メタデータ） (2020-06-21T11:23:20Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)

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

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