論文の概要: Towards graph neural networks for provably solving convex optimization problems

• arxiv url: http://arxiv.org/abs/2502.02446v1
• Date: Tue, 04 Feb 2025 16:11:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-05 15:06:18.873247
• Title: Towards graph neural networks for provably solving convex optimization problems
• Title（参考訳）: 凸最適化問題に対するグラフニューラルネットワークの実現に向けて
• Authors: Chendi Qian, Christopher Morris,
• Abstract要約: 提案するMPNNフレームワークは,検証可能な実現可能性保証を用いて凸最適化問題を解決する。 実験の結果,提案手法は既存の神経ベースラインよりも解の質や実現可能性に優れていた。
• 参考スコア（独自算出の注目度）: 5.966097889241178
• License:
• Abstract: Recently, message-passing graph neural networks (MPNNs) have shown potential for solving combinatorial and continuous optimization problems due to their ability to capture variable-constraint interactions. While existing approaches leverage MPNNs to approximate solutions or warm-start traditional solvers, they often lack guarantees for feasibility, particularly in convex optimization settings. Here, we propose an iterative MPNN framework to solve convex optimization problems with provable feasibility guarantees. First, we demonstrate that MPNNs can provably simulate standard interior-point methods for solving quadratic problems with linear constraints, covering relevant problems such as SVMs. Secondly, to ensure feasibility, we introduce a variant that starts from a feasible point and iteratively restricts the search within the feasible region. Experimental results show that our approach outperforms existing neural baselines in solution quality and feasibility, generalizes well to unseen problem sizes, and, in some cases, achieves faster solution times than state-of-the-art solvers such as Gurobi.
• Abstract（参考訳）: 近年、メッセージパスグラフニューラルネットワーク(MPNN)は、可変制約相互作用をキャプチャする能力により、組合せ最適化と連続最適化の問題を解く可能性を示している。 既存のアプローチはMPNNを利用して解を近似したり、伝統的な解法を温めたりするが、特に凸最適化設定において実現可能性の保証が欠如していることが多い。 本稿では,実現可能性保証を用いた凸最適化問題を解決するために,反復的なMPNNフレームワークを提案する。 まず,2次問題を線形制約で解くために,MPNNが標準的なインテリアポイント法を確実にシミュレートできることを示す。 第2に、実現可能性を確保するために、実現可能な点から始まる変種を導入し、実行可能な領域内の探索を反復的に制限する。 実験結果から,提案手法は解法の品質と実現可能性において既存のニューラルネットワークよりも優れており,未確認問題のサイズによく対応し,場合によってはGurobiのような最先端の解法よりも高速な解解時間を実現する。

関連論文リスト

• Differentiable Projection-based Learn to Optimize in Wireless Network-Part I: Convex Constrained (Non-)Convex Programming [15.689556794350674]
  本稿では,一般凸制約を考慮した(実現不可能な)最適化問題に対処する。 従来の凸最適化法は、これらの問題を最も一般的な形で効率的に扱うのに苦労することが多い。
  論文  参考訳（メタデータ） (2025-01-29T11:52:27Z)
• Annealing Machine-assisted Learning of Graph Neural Network for Combinatorial Optimization [2.0643665408482517]
  Annealing Machines (AM) は複雑な問題を解決する能力の増大を示している。 グラフニューラルネットワーク(GNN)は最近、問題解決に適応している。 本稿では,AMが提示する精度とGNNの表現の柔軟性とスケーラビリティを両立することを目的としたマージ手法を提案する。
  論文  参考訳（メタデータ） (2025-01-10T10:36:46Z)
• A Primal-dual algorithm for image reconstruction with ICNNs [3.4797100095791706]
  我々は、正規化器が入力ニューラルネットワーク(ICNN)によってパラメータ化されるデータ駆動変分フレームワークにおける最適化問題に対処する。 勾配に基づく手法はそのような問題を解決するのに一般的に用いられるが、非滑らかさを効果的に扱うのに苦労する。 提案手法は, 速度と安定性の両方の観点から, 下位段階の手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2024-10-16T10:36:29Z)
• An Expandable Machine Learning-Optimization Framework to Sequential Decision-Making [0.0]
  逐次的意思決定問題を効率的に解決する統合予測最適化(PredOpt)フレームワークを提案する。 本稿では,機械学習(ML)における逐次依存,実現可能性,一般化といった課題に対処し,インスタンス問題に対する最適解の予測を行う。
  論文  参考訳（メタデータ） (2023-11-12T21:54:53Z)
• Exploring the Power of Graph Neural Networks in Solving Linear Optimization Problems [5.966097889241178]
  グラフニューラルネットワーク(MPNN)は、混合整数最適化問題を高速化する。 線形最適化をエミュレートするMPNNの有効性はほとんど不明である。 線形最適化問題を解くための軽量プロキシとしてMPNNがどのように機能するかを強調した。
  論文  参考訳（メタデータ） (2023-10-16T17:31:25Z)
• 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)
• A Stable and Scalable Method for Solving Initial Value PDEs with Neural Networks [52.5899851000193]
  我々は,ネットワークの条件が悪くなるのを防止し,パラメータ数で時間線形に動作するODEベースのIPPソルバを開発した。 このアプローチに基づく現在の手法は2つの重要な問題に悩まされていることを示す。 まず、ODEに従うと、問題の条件付けにおいて制御不能な成長が生じ、最終的に許容できないほど大きな数値誤差が生じる。
  論文  参考訳（メタデータ） (2023-04-28T17:28:18Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• dNNsolve: an efficient NN-based PDE solver [62.997667081978825]
  ODE/PDEを解決するためにデュアルニューラルネットワークを利用するdNNsolveを紹介します。 我々は,dNNsolveが1,2,3次元の幅広いODE/PDEを解くことができることを示す。
  論文  参考訳（メタデータ） (2021-03-15T19:14:41Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  データ駆動最適化の問題を検討し、一定の点セットでクエリのみを与えられた関数を最大化する必要がある。 この問題は、関数評価が複雑で高価なプロセスである多くの領域に現れる。 我々は,提案手法を高容量ニューラルネットワークモデルに拡張可能なトラクタブル近似を提案する。
  論文  参考訳（メタデータ） (2021-02-16T06:04:27Z)

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

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