論文の概要: Deep Distributed Optimization for Large-Scale Quadratic Programming
- arxiv url: http://arxiv.org/abs/2412.12156v1
- Date: Wed, 11 Dec 2024 09:45:00 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-18 13:56:50.574933
- Title: Deep Distributed Optimization for Large-Scale Quadratic Programming
- Title（参考訳）: 大規模二次計画計画のための分散最適化
- Authors: Augustinos D. Saravanos, Hunter Kuperman, Alex Oshin, Arshiya Taj Abdul, Vincent Pacelli, Evangelos A. Theodorou,
- Abstract要約: 本稿では,大規模擬似プログラミング(QP)問題に対処するために設計された,ディープラーニング支援型分散最適化アーキテクチャを提案する。
DeepDistributedQPは、小さな問題をトレーニングし、同じポリシーを使用してもっと大きな問題(最大50K変数と150K制約)をスケールすることで、強力な一般化を示す。
- 参考スコア（独自算出の注目度）: 15.773581194857085
- License:
- Abstract: Quadratic programming (QP) forms a crucial foundation in optimization, encompassing a broad spectrum of domains and serving as the basis for more advanced algorithms. Consequently, as the scale and complexity of modern applications continue to grow, the development of efficient and reliable QP algorithms is becoming increasingly vital. In this context, this paper introduces a novel deep learning-aided distributed optimization architecture designed for tackling large-scale QP problems. First, we combine the state-of-the-art Operator Splitting QP (OSQP) method with a consensus approach to derive DistributedQP, a new method tailored for network-structured problems, with convergence guarantees to optimality. Subsequently, we unfold this optimizer into a deep learning framework, leading to DeepDistributedQP, which leverages learned policies to accelerate reaching to desired accuracy within a restricted amount of iterations. Our approach is also theoretically grounded through Probably Approximately Correct (PAC)-Bayes theory, providing generalization bounds on the expected optimality gap for unseen problems. The proposed framework, as well as its centralized version DeepQP, significantly outperform their standard optimization counterparts on a variety of tasks such as randomly generated problems, optimal control, linear regression, transportation networks and others. Notably, DeepDistributedQP demonstrates strong generalization by training on small problems and scaling to solve much larger ones (up to 50K variables and 150K constraints) using the same policy. Moreover, it achieves orders-of-magnitude improvements in wall-clock time compared to OSQP. The certifiable performance guarantees of our approach are also demonstrated, ensuring higher-quality solutions over traditional optimizers.
- Abstract（参考訳）: 二次プログラミング(QP)は最適化において重要な基礎を形成し、幅広い領域を包含し、より高度なアルゴリズムの基礎となる。
その結果、現代のアプリケーションの規模と複雑さが増大し続けており、効率的で信頼性の高いQPアルゴリズムの開発がますます重要になっている。
本稿では,大規模QP問題に対処するための分散最適化アーキテクチャを提案する。
まず、最先端演算子分割QP(OSQP)法と、ネットワーク構造問題に適した新しい手法であるDistributedQPを導出するコンセンサスアプローチを組み合わせる。
その後、このオプティマイザをディープラーニングフレームワークに展開し、DeepDistributedQPに導いた。
また、この手法は確率的近似(英語版)(PAC)-ベイズ理論(英語版)によって理論的に基礎付けられており、予期しない問題に対する最適性ギャップの一般化境界を提供する。
提案したフレームワークと、その集中バージョンであるDeepQPは、ランダムに生成された問題、最適制御、線形回帰、輸送ネットワークなど、さまざまなタスクにおいて、標準最適化よりも大幅に優れています。
特に、DeepDistributedQPは、小さな問題をトレーニングし、同じポリシーを使用してもっと大きな問題(最大50K変数と150K制約)をスケールすることで、強力な一般化を示す。
さらに、OSQPと比較して、壁面時計時間におけるオーダー・オブ・マグニチュードの改善を実現している。
従来のオプティマイザよりも高品質なソリューションが保証されている。
関連論文リスト
- Differentiation Through Black-Box Quadratic Programming Solvers [16.543673072027136]
我々は,任意の2次プログラミング(QP)ソルバに対して,プラグアンドプレイの微分を可能にするモジュール型フレームワークであるdQPを紹介する。
我々の解は、QP最適化におけるアクティブ制約セットの知識が明示的な微分を可能にするというコア理論的知見に基づいている。
我々の実装は公開され、15以上の最先端QP解決器をサポートする既存のフレームワークとインターフェースします。
論文 参考訳（メタデータ） (2024-10-08T20:01:39Z) - NeuralQP: A General Hypergraph-based Optimization Framework for Large-scale QCQPs [8.503330120957052]
本稿では,大規模二次制約付き二次プログラム(QCQP)のための汎用ハイパーグラフベースフレームワークであるNeuralQPを紹介する。
ハイパーグラフ表現を用いたUniEGNNは2次プログラミングのための内部点法(IPM)と等価であることを示す。
QPLIBによる2つのベンチマーク問題と大規模な実世界のインスタンスの実験は、NeuralQPが最先端の解法よりも優れていることを示した。
論文 参考訳（メタデータ） (2024-09-28T10:42:47Z) - Distributed Quantum Approximate Optimization Algorithm on Integrated High-Performance Computing and Quantum Computing Systems for Large-Scale Optimization [1.7099366779394252]
量子近似最適化アルゴリズム(QAOA)は、ゲートベースの量子コンピューティングシステムに量子スピードアップを提供することで最適化問題を解決することを約束している。
本稿では,分散QAOA(DQAOA)を提案する。
我々はAL-DQAOAを用いてフォトニック構造を最適化することに成功し、ゲートベースの量子コンピューティングを用いた実世界の最適化問題を解くことは我々の戦略で実現可能であることを示唆した。
論文 参考訳（メタデータ） (2024-07-29T17:42:25Z) - Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks [57.24087627267086]
通信ネットワークのノード間で分散的に格納された凸関数の総和を最小化するタスクについて検討する。
この問題を解決するのに必要な分散通信数と(サブ)漸進計算の下位境界が確立されている。
我々は,これらの下界に適合する最初の最適アルゴリズムを開発し,既存の最先端技術と比較して理論性能を著しく向上させる。
論文 参考訳（メタデータ） (2024-05-28T10:28:45Z) - Multi-Timescale Ensemble Q-learning for Markov Decision Process Policy
Optimization [21.30645601474163]
元々のQ-ラーニングは、非常に大きなネットワークにわたるパフォーマンスと複雑性の課題に悩まされている。
従来のQ-ラーニングに適応したモデルフリーアンサンブル強化学習アルゴリズムを提案する。
計算結果から,提案アルゴリズムは平均ポリシエラーを最大55%,実行時複雑性を最大50%削減できることがわかった。
論文 参考訳（メタデータ） (2024-02-08T08:08:23Z) - Analyzing and Enhancing the Backward-Pass Convergence of Unrolled
Optimization [50.38518771642365]
ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。
この設定における中心的な課題は最適化問題の解によるバックプロパゲーションであり、しばしば閉形式を欠いている。
本稿では, 非線形最適化の後方通過に関する理論的知見を提供し, 特定の反復法による線形システムの解と等価であることを示す。
Folded Optimizationと呼ばれるシステムが提案され、非ローリングなソルバ実装からより効率的なバックプロパゲーションルールを構築する。
論文 参考訳（メタデータ） (2023-12-28T23:15:18Z) - Federated Multi-Level Optimization over Decentralized Networks [55.776919718214224]
エージェントが隣人としか通信できないネットワーク上での分散マルチレベル最適化の問題について検討する。
ネットワーク化されたエージェントが1つの時間スケールで異なるレベルの最適化問題を解くことができる新しいゴシップに基づく分散マルチレベル最適化アルゴリズムを提案する。
提案アルゴリズムは, ネットワークサイズと線形にスケーリングし, 各種アプリケーション上での最先端性能を示す。
論文 参考訳（メタデータ） (2023-10-10T00:21:10Z) - Multi-Objective Optimization and Network Routing with Near-Term Quantum
Computers [0.2150989251218736]
我々は,多目的最適化問題を解くために,近距離量子コンピュータを応用できる手法を開発した。
量子近似最適化アルゴリズム(QAOA)に基づく実装に焦点を当てる。
論文 参考訳（メタデータ） (2023-08-16T09:22:01Z) - Path Regularization: A Convexity and Sparsity Inducing Regularization
for Parallel ReLU Networks [75.33431791218302]
本稿では,ディープニューラルネットワークのトレーニング問題について検討し,最適化環境に隠された凸性を明らかにするための解析的アプローチを提案する。
我々は、標準のディープ・ネットワークとResNetを特別なケースとして含む、ディープ・パラレルなReLUネットワークアーキテクチャについて検討する。
論文 参考訳（メタデータ） (2021-10-18T18:00:36Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳（メタデータ） (2020-03-11T13:52:41Z) - Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
適応性は現代最適化理論において重要であるが、研究されていない性質である。
提案アルゴリズムは,PL目標に対して既存のアルゴリズムよりも優れた性能を保ちながら,PL目標に対して最適な収束性を実現することを実証した。
論文 参考訳（メタデータ） (2020-02-13T05:42:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。