論文の概要: A Penalty Approach for Differentiation Through Black-Box Quadratic Programming Solvers

• arxiv url: http://arxiv.org/abs/2602.14154v1
• Date: Sun, 15 Feb 2026 14:05:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-17 14:17:28.672831
• Title: A Penalty Approach for Differentiation Through Black-Box Quadratic Programming Solvers
• Title（参考訳）: ブラックボックス擬似計画解による分別に対するペナルティ的アプローチ
• Authors: Yuxuan Linghu, Zhiyuan Liu, Qi Deng,
• Abstract要約: dXPPは、QP解決を差別化から切り離すペナルティベースの差別化フレームワークである。 ランダムに生成されたQP、大規模なスパースプロジェクション問題、実世界のポートフォリオ最適化タスクなど、様々なタスクにおいてdXPPを評価する。
• 参考スコア（独自算出の注目度）: 29.582959310549594
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Differentiating through the solution of a quadratic program (QP) is a central problem in differentiable optimization. Most existing approaches differentiate through the Karush--Kuhn--Tucker (KKT) system, but their computational cost and numerical robustness can degrade at scale. To address these limitations, we propose dXPP, a penalty-based differentiation framework that decouples QP solving from differentiation. In the solving step (forward pass), dXPP is solver-agnostic and can leverage any black-box QP solver. In the differentiation step (backward pass), we map the solution to a smooth approximate penalty problem and implicitly differentiate through it, requiring only the solution of a much smaller linear system in the primal variables. This approach bypasses the difficulties inherent in explicit KKT differentiation and significantly improves computational efficiency and robustness. We evaluate dXPP on various tasks, including randomly generated QPs, large-scale sparse projection problems, and a real-world multi-period portfolio optimization task. Empirical results demonstrate that dXPP is competitive with KKT-based differentiation methods and achieves substantial speedups on large-scale problems.
• Abstract（参考訳）: 二次プログラム(QP)の解を微分することは微分可能最適化における中心的な問題である。 既存のほとんどのアプローチはKKT(Karush--Kuhn-Tucker)システムを通して異なるが、計算コストと数値ロバスト性は大規模に低下する可能性がある。 これらの制約に対処するために,QPを微分から分離するペナルティベースの微分フレームワークであるdXPPを提案する。 解法ステップ(前方通過)では、dXPPは解法に依存しず、任意のブラックボックスQP解法を利用することができる。 微分ステップ(後方通過)では、解を滑らかな近似的ペナルティ問題に写像し、それを通して暗黙的に微分し、原始変数においてより小さな線形系の解のみを必要とする。 このアプローチは、明示的なKKT微分に固有の困難を回避し、計算効率と堅牢性を大幅に改善する。 ランダムに生成されたQP、大規模なスパースプロジェクション問題、実世界の多周期ポートフォリオ最適化タスクなど、様々なタスクにおいてdXPPを評価する。 実験の結果、dXPPはKKTに基づく微分法と競合し、大規模問題においてかなりのスピードアップを達成することが示された。

関連論文リスト

• DInf-Grid: A Neural Differential Equation Solver with Differentiable Feature Grids [73.28614344779076]
  我々は、微分方程式(DE)を効率的に解くための微分可能グリッドベース表現を提案する。 その結果,座標法よりも5～20倍の高速化を実現し,差分方程式を数秒または数分で解き,精度とコンパクト性を維持した。
  論文  参考訳（メタデータ） (2026-01-15T18:59:57Z)
• Differentiation Through Black-Box Quadratic Programming Solvers [21.717766458737426]
  微分可能最適化は、特に二次プログラミング(QP)において重要な研究関心を集めている。 事実上任意のQPソルバのプラグアンドプレイ微分のためのモジュラーおよびソルバ非依存のフレームワークであるdQPを紹介する。 この結果に基づいて、15以上の最先端の解決者とシームレスに統合する、最小限のオーバヘッド、オープンソース実装を提供する。
  論文  参考訳（メタデータ） (2024-10-08T20:01:39Z)
• 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)
• SCQPTH: an efficient differentiable splitting method for convex quadratic programming [1.3597551064547502]
  SCQPTHは凸二次プログラムの微分可能な一階分割法である。 SCQPTHソフトウェアはオープンソースのpythonパッケージとして利用可能である。 大規模QPでは、SCQPTHは計算効率を10倍に改善できる。
  論文  参考訳（メタデータ） (2023-08-16T09:06:54Z)
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
  余分なスラック変数を必要としない代替手法を提案する。 我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。 この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
  論文  参考訳（メタデータ） (2022-11-25T06:05:18Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。 本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。 Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
  論文  参考訳（メタデータ） (2021-05-06T17:59:38Z)
• Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling [86.85697555068168]
  2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。 特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。 PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
  論文  参考訳（メタデータ） (2021-05-05T03:36:00Z)
• GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal Black Box Constraint Satisfaction [69.94831587339539]
  本稿では,マスク付き自己回帰ニューラルネットワークを用いて解空間上の均一分布をモデル化するクロスエントロピー法(CEM)を提案する。 我々のアルゴリズムは複雑な解空間を表現でき、様々な異なる解領域を追跡できる。
  論文  参考訳（メタデータ） (2020-02-17T20:21:20Z)

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

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