論文の概要: MixedComplementarityProblems.jl: A Fast, Batched, Open-Source Interior Point Solver for Mixed Complementarity Problems
- arxiv url: http://arxiv.org/abs/2608.00959v1
- Date: Sun, 02 Aug 2026 03:10:50 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-04 15:07:25.035988
- Title: MixedComplementarityProblems.jl: A Fast, Batched, Open-Source Interior Point Solver for Mixed Complementarity Problems
- Title（参考訳）: Mixed ComplementarityProblems.jl: 混合相補性問題に対する高速でバッチ化されたオープンソースの内部点解法
- Abstract要約: 混合相補性問題は、非線形プログラムと非協調ゲームの一階最適性条件として生じる。
この形式の問題に対する主要な解決法はPATHであり、ロボット工学の問題を強く評価するが、クローズドソースのままである。
パラメトリックMPPの内部点法をオープンソースで純粋なJulia実装であるMixedarityProblems.jlを提案する。
- 参考スコア（独自算出の注目度）: 4.552097495048781
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Mixed complementarity problems (MCPs) arise as the first-order optimality conditions of nonlinear programs and noncooperative games, and provide a natural formulation for multi-agent trajectory optimization problems that appear throughout robotics. The dominant solver for problems of this form is PATH, which offers strong performance on robotics problems but remains closed-source. We present MixedComplementarityProblems.jl, an open-source, pure Julia implementation of an interior point method for parametric MCPs that: (i) matches PATH's reliability on standard benchmarks, (ii) natively supports batched, parallel processing of many parameter instances, either across CPU threads or on an NVIDIA GPU, and (iii) supports efficient automatic differentiation of solutions with respect to problem parameters. On a multi-agent lane-change trajectory game representative of robotics planning problems, our CPU-multithreaded batched solver clears a batch of parametric instances ~100x faster than sequential calls to PATH. A GPU backend, running the same solver implementation unmodified, also clears these batches far faster than PATH, but does not outperform the multithreaded CPU on this problem; the GPU pulls ahead only once each per-instance KKT system grows large, and we characterize this regime dependence. We describe the solver's interior point formulation, the abstraction that lets a single solver implementation run unmodified across dense, batched-sparse, and single-large linear-algebra backends, and report benchmarks against PATH on both randomly generated quadratic programs and trajectory games.
- Abstract（参考訳）: 混合相補性問題(MCPs)は、非線形プログラムと非協調ゲームの一階最適条件として発生し、ロボット工学全体で現れる多エージェント軌道最適化問題に対する自然な定式化を提供する。
この形式の問題に対する主要な解決方法はPATHであり、ロボット工学の問題を強く評価するが、クローズドソースのままである。
We present MixedComplementarityProblems.jl, a open-source, pure Julia implementation of a interior point method for parametric MCPs that。
(i)PATHの信頼性を標準ベンチマークに適合させる。
i) CPUスレッドまたはNVIDIA GPU上で、多くのパラメータインスタンスのバッチ処理と並列処理をネイティブにサポートする。
(iii)問題パラメータに関する解の効率的な自動微分を支援する。
ロボット計画問題を代表するマルチエージェントレーン変更軌道ゲームにおいて,CPUマルチスレッドバッチ型解法により,PATHへのシーケンシャルコールよりも100倍高速なパラメトリックインスタンスのバッチをクリアする。
GPUバックエンドは、同じソルバ実装を無修正で実行するが、これらのバッチをPATHよりもはるかに高速にクリアするが、この問題でマルチスレッドCPUより優れているわけではない。
本稿では,この解法の内部点の定式化について述べるとともに,乱数生成された二次プログラムとトラジェクティブゲームの両方においてPATHに対するベンチマークを報告する。
関連論文リスト
- CUDA MPC: A GPU-Native Solver for Model Predictive Control [0.0]
モデル予測制御(MPC)は、高速なダイナミックス、高次元モデル、あるいは長い水平線を持つシステムに制約対応制御を提供する。
本稿では,ハードウェアの最適化アルゴリズム,実行モデル,メモリアーキテクチャを共同設計したGPUネイティブなMPCフレームワークであるMPCを紹介する。
論文 参考訳（メタデータ） (2026-08-04T03:02:04Z) - Scaling Nonlinear Optimization: Many Problems One GPU [45.58567999526917]
IPOPTに基づく最初のGPUバッチNLPソルバである textttjaxipm を紹介する。
IPOPTに比べてスループットが32.85倍に向上します。
論文 参考訳（メタデータ） (2026-06-24T19:34:41Z) - Parallel Dynamic Programming for Conic Linear Quadratic Control [11.017626990661059]
線形二次制御問題は線形制御理論とモデル予測制御(MPC)の中心にある
本稿では,乗算器の交互方向法(ADMM)を用いて,円錐最適制御問題を計算的に要求する並列時間アプローチを提案する。
2つの実世界のアプリケーションに関する数値ベンチマークでは、マルチコアCPUハードウェアに関する既存のアプローチと比べて5倍のスピードアップを示している。
論文 参考訳（メタデータ） (2026-06-23T14:26:38Z) - Parallel-in-Time Nonlinear Optimal Control via GPU-native Sequential Convex Programming [2.8852807790754618]
本稿では,連続凸プログラミングと乗算器のコンセンサスに基づく交互方向法を組み合わせた,フルGPUネイティブなトラジェクトリ最適化フレームワークを提案する。
本研究は,有人エッジコンピューティングプラットフォームを用いて,四重項アジャイル飛行タスクと火星搭載降下問題の解法を検証した。
ベンチマークでは、高度に最適化された12コアのCPUベースラインよりも、持続的な4倍のスループットのスピードアップとエネルギー消費の51%削減が明らかにされている。
論文 参考訳（メタデータ） (2026-03-11T12:39:14Z) - It Takes Two to Tango: A Holistic Simulator for Joint Order Scheduling and Multi-Agent Path Finding in Robotic Warehouses [18.101514832695067]
WareRoverはOSとMAPFの動的結合を強制する総合シミュレーションプラットフォームである。
標準ベンチマークとは異なり、WareRoverは順序ストリーム、物理を意識した動作制約、非線形回復機構を単一の評価ループに統合する。
論文 参考訳（メタデータ） (2026-02-15T05:51:58Z) - Para-B&B: Load-Balanced Deterministic Parallelization of Solving MIP [50.917107318582715]
MIP(Mixed-integer Programming)は、連続型と整数型の両方の決定変数を組み込むことで線形プログラミングを拡張する。
本稿では,高性能MIPソルバであるHiGHSに対して,決定論的並列分岐結合の完全なオープンソース実装を初めて提案する。
本手法では,ワーカスレッド間で完全なソルバ状態を複製することにより,厳密な決定性を保証する新しいデータ並列アーキテクチャを提案する。
論文 参考訳（メタデータ） (2026-02-10T14:17:53Z) - Optimization Techniques in Quantum Information [0.0]
この論文は数学と計算の最適化と量子情報の交わりに焦点を当てている。
主なコントリビューションは、オープンソースのソフトウェアコードである。
パッケージのPolyOptimizationはギャップを埋めることを目的としており、問題のサイズを減らすために、多くのアルゴリズムとともに非常にリソース効率のよい中間層を提供する。
論文 参考訳（メタデータ） (2025-12-17T17:51:10Z) - INC: An Indirect Neural Corrector for Auto-Regressive Hybrid PDE Solvers [61.84396402100827]
本稿では,学習した補正を支配方程式に統合する間接ニューラルコレクタ(mathrmINC$)を提案する。
$mathrmINC$は、$t-1 + L$の順番でエラー増幅を減らし、$t$はタイムステップ、$L$はリプシッツ定数である。
大規模なベンチマークで$mathrmINC$をテストし、1Dカオスシステムから3D乱流まで、多くの異なる解法、神経バックボーン、テストケースをカバーした。
論文 参考訳（メタデータ） (2025-11-16T20:14:28Z) - Distributed Extra-gradient with Optimal Complexity and Communication
Guarantees [60.571030754252824]
複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。
モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。
そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
論文 参考訳（メタデータ） (2023-08-17T21:15:04Z) - Numerical Methods for Convex Multistage Stochastic Optimization [86.45244607927732]
最適化プログラミング(SP)、最適制御(SOC)、決定プロセス(MDP)に焦点を当てる。
凸多段マルコフ問題の解決の最近の進歩は、動的プログラミング方程式のコスト対ゴー関数の切断面近似に基づいている。
切削平面型法は多段階問題を多段階的に扱えるが、状態(決定)変数は比較的少ない。
論文 参考訳（メタデータ） (2023-03-28T01:30:40Z) - MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical
Models [96.1052289276254]
この研究は、人気のあるDual Block-Coordinate Ascent原則に基づく新しいMAP-solverを導入している。
驚いたことに、性能の低い解法に小さな変更を加えることで、既存の解法を大きなマージンで大幅に上回る新しい解法MPLP++を導出します。
論文 参考訳（メタデータ） (2020-04-16T16:20:53Z) - Accelerating Feedforward Computation via Parallel Nonlinear Equation
Solving [106.63673243937492]
ニューラルネットワークの評価や自己回帰モデルからのサンプリングなどのフィードフォワード計算は、機械学習においてユビキタスである。
本稿では,非線形方程式の解法としてフィードフォワード計算の課題を定式化し,ジャコビ・ガウス・シーデル固定点法とハイブリッド法を用いて解を求める。
提案手法は, 並列化可能な繰り返し回数の削減(あるいは等値化)により, 元のフィードフォワード計算と全く同じ値が与えられることを保証し, 十分な並列化計算能力を付与する。
論文 参考訳（メタデータ） (2020-02-10T10:11:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。