論文の概要: Differentiation Through Black-Box Quadratic Programming Solvers
- arxiv url: http://arxiv.org/abs/2410.06324v1
- Date: Thu, 10 Oct 2024 14:56:48 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-01 06:29:16.954966
- Title: Differentiation Through Black-Box Quadratic Programming Solvers
- Title（参考訳）: ブラックボックス擬似計画解による微分
- Authors: Connor W. Magoon, Fengyu Yang, Noam Aigerman, Shahar Z. Kovalsky,
- Abstract要約: 我々は,任意の2次プログラミング(QP)ソルバに対して,プラグアンドプレイの微分を可能にするモジュール型フレームワークであるdQPを紹介する。
我々の解は、QP最適化におけるアクティブ制約セットの知識が明示的な微分を可能にするというコア理論的知見に基づいている。
我々の実装は公開され、15以上の最先端QP解決器をサポートする既存のフレームワークとインターフェースします。
- 参考スコア（独自算出の注目度）: 16.543673072027136
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In recent years, many deep learning approaches have incorporated layers that solve optimization problems (e.g., linear, quadratic, and semidefinite programs). Integrating these optimization problems as differentiable layers requires computing the derivatives of the optimization problem's solution with respect to its objective and constraints. This has so far prevented the use of state-of-the-art black-box numerical solvers within neural networks, as they lack a differentiable interface. To address this issue for one of the most common convex optimization problems -- quadratic programming (QP) -- we introduce dQP, a modular framework that enables plug-and-play differentiation for any QP solver, allowing seamless integration into neural networks and bi-level optimization tasks. Our solution is based on the core theoretical insight that knowledge of the active constraint set at the QP optimum allows for explicit differentiation. This insight reveals a unique relationship between the computation of the solution and its derivative, enabling efficient differentiation of any solver, that only requires the primal solution. Our implementation, which will be made publicly available, interfaces with an existing framework that supports over 15 state-of-the-art QP solvers, providing each with a fully differentiable backbone for immediate use as a differentiable layer in learning setups. To demonstrate the scalability and effectiveness of dQP, we evaluate it on a large benchmark dataset of QPs with varying structures. We compare dQP with existing differentiable QP methods, demonstrating its advantages across a range of problems, from challenging small and dense problems to large-scale sparse ones, including a novel bi-level geometry optimization problem.
- Abstract（参考訳）: 近年,多くのディープラーニング手法が最適化問題(線形プログラム,二次プログラム,半定値プログラムなど)を解くレイヤを組み込んでいる。
これらの最適化問題を微分可能な層として統合するには、その目的と制約に関して最適化問題の解の微分を計算する必要がある。
これまでのところ、ニューラルネットワーク内での最先端のブラックボックス数値解法の使用は、差別化可能なインターフェースが欠如しているため、禁止されている。
この問題に対処するため、最も一般的な凸最適化問題である2次プログラミング(QP)の1つに、ニューラルネットワークと双方向最適化タスクへのシームレスな統合を可能にする、任意のQPソルバに対してプラグインとプレイの差別化を可能にするモジュラーフレームワークであるdQPを紹介します。
我々の解は、QP最適化におけるアクティブ制約セットの知識が明示的な微分を可能にするというコア理論的知見に基づいている。
この知見は、解の計算と微分のユニークな関係を明らかにし、任意の解の効率的な微分を可能にし、原始解のみを必要とする。
我々の実装は公開され、15以上の最先端のQP解決ツールをサポートする既存のフレームワークとインターフェースされ、それぞれが学習設定における差別化レイヤとしてすぐに使える完全に差別化可能なバックボーンを提供する。
dQPのスケーラビリティと有効性を示すため,様々な構造を持つ大規模ベンチマークデータセットを用いて評価を行った。
我々はdQPを既存の微分可能QP法と比較し、小型で高密度な問題から新しい二段階幾何最適化問題を含む大規模なスパース問題まで、様々な問題にその利点を示す。
関連論文リスト
- WANCO: Weak Adversarial Networks for Constrained Optimization problems [5.257895611010853]
まず、拡張ラグランジアン法を用いてミニマックス問題をミニマックス問題に変換する。
次に、それぞれ原始変数と双対変数を表すために、2つの(または複数の)ディープニューラルネットワークを使用します。
ニューラルネットワークのパラメータは、敵のプロセスによって訓練される。
論文 参考訳（メタデータ） (2024-07-04T05:37:48Z) - Learning Solution-Aware Transformers for Efficiently Solving Quadratic Assignment Problem [27.33966993065248]
本研究は,2次割当て問題(QAP)を効率的に解くための学習ベースソリューションに焦点を当てる。
QAPに関する現在の研究は、限られた規模と非効率性に悩まされている。
そこで本研究では,QAPの学習と改善のカテゴリにおける第1の解法を提案する。
論文 参考訳（メタデータ） (2024-06-14T10:15:03Z) - Optimized QUBO formulation methods for quantum computing [0.4999814847776097]
実世界の金融シナリオにインスパイアされたNPハード最適化問題に対して,我々の手法を適用する方法について述べる。
2つのD波量子異方体にこの問題の事例を提出し、これらのシナリオで使用される標準手法と新しい手法の性能を比較した。
論文 参考訳（メタデータ） (2024-06-11T19:59:05Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。
1つの典型的な戦略はアルゴリズムのアンローリングであり、これは反復解法の操作による自動微分に依存している。
本稿では,非ロール最適化の後方通過に関する理論的知見を提供し,効率よく解けるバックプロパゲーション解析モデルを生成するシステムに繋がる。
論文 参考訳（メタデータ） (2023-01-28T01:50:42Z) - Learning differentiable solvers for systems with hard constraints [48.54197776363251]
ニューラルネットワーク(NN)によって定義される関数に対する偏微分方程式(PDE)制約を強制する実践的手法を提案する。
我々は、任意のNNアーキテクチャに組み込むことができる微分可能なPDE制約層を開発した。
その結果、NNアーキテクチャに直接ハード制約を組み込むことで、制約のない目的のトレーニングに比べてテストエラーがはるかに少ないことがわかった。
論文 参考訳（メタデータ） (2022-07-18T15:11:43Z) - A Constrained Optimization Approach to Bilevel Optimization with
Multiple Inner Minima [49.320758794766185]
そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。
このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
論文 参考訳（メタデータ） (2022-03-01T18:20:01Z) - Message Passing Neural PDE Solvers [60.77761603258397]
我々は、バックプロップ最適化されたニューラル関数近似器で、グラフのアリーデザインのコンポーネントを置き換えるニューラルメッセージパッシング解決器を構築した。
本稿では, 有限差分, 有限体積, WENOスキームなどの古典的手法を表現的に含んでいることを示す。
本研究では, 異なる領域のトポロジ, 方程式パラメータ, 離散化などにおける高速, 安定, 高精度な性能を, 1次元, 2次元で検証する。
論文 参考訳（メタデータ） (2022-02-07T17:47:46Z) - Efficient differentiable quadratic programming layers: an ADMM approach [0.0]
乗算器の交互方向法(ADMM)に基づく代替ネットワーク層アーキテクチャを提案する。
後方微分は、修正された固定点反復の残差写像の暗黙の微分によって行われる。
シミュレーションの結果は、中規模の問題に対してOptNet二次プログラミング層よりも約1桁高速であるADMM層の計算上の利点を示している。
論文 参考訳（メタデータ） (2021-12-14T15:25:07Z) - Physics and Equality Constrained Artificial Neural Networks: Application
to Partial Differential Equations [1.370633147306388]
偏微分方程式(PDE)の解を学ぶために物理インフォームドニューラルネットワーク(PINN)が提案されている。
本稿では,この目的関数の定式化方法が,PINNアプローチにおける厳密な制約の源であることを示す。
本稿では,逆問題と前方問題の両方に対処可能な多目的フレームワークを提案する。
論文 参考訳（メタデータ） (2021-09-30T05:55:35Z) - Efficient and Modular Implicit Differentiation [68.74748174316989]
最適化問題の暗黙的な微分のための統一的で効率的かつモジュール化されたアプローチを提案する。
一見単純な原理は、最近提案された多くの暗黙の微分法を復元し、新しいものを簡単に作成できることを示している。
論文 参考訳（メタデータ） (2021-05-31T17:45:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。