論文の概要: Learning to Design Convex Relaxations for Nonconvex Optimization

• arxiv url: http://arxiv.org/abs/2610.16948v2
• Date: Wed, 14 Oct 2026 09:30:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-15 21:06:15.396327
• Title: Learning to Design Convex Relaxations for Nonconvex Optimization
• Title（参考訳）: 非凸最適化のための凸緩和設計の学習
• Abstract要約: 凸緩和は、厳密な非問題を有効な境界を与える凸代理に置き換えることによって、非最適化を誘引可能である。 しかし、彼らのデザインは、リラクゼーションが正常に使用される場所と、どの程度の成長に値するかである。
• 参考スコア（独自算出の注目度）: 23.901760164851652
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Convex relaxations make nonconvex optimization tractable by replacing hard nonconvex problems with convex surrogates that give valid bounds. Yet their design is still largely manual: a human expert must decide where to relax, which relaxation to use, and how much formulation growth is worth paying. We show that this design process can be learned. The method proposed in this paper, AutoConvexRelax, represents the symbolic formulation of a nonconvex problem as a tripartite graph linking variables, symbolic terms, and their objective or constraint positions. It then learns a policy that composes symbolic rewrites into problem-specific relaxation trajectories as the formulation evolves. We prove that finite action sequences generated by the learned policy preserve relaxation validity under explicit domain, occurrence-context, and representation-consistency conditions. We further establish computable error bounds for mixed relaxations and sufficient conditions for feasible recovery and global-optimality certification. As a first instantiation, we apply the method to nonconvex quadratic problems and fractional problems. On 241 benchmark quadratic instances, the learned policy strengthens McCormick lower bounds by 13.52%. Its mean lower bound is 3.70% below strengthened semidefinite relaxations on the normalized comparison metric, while it uses substantially smaller formulations. The learned policy retains this trade-off on fractional instances and reaches near-semidefinite bounds on beamforming and sensor-network localization instances. These results suggest that convex relaxation design can move from a fixed handcrafted choice to an automated learning process that adapts to problem structures. Code is available at https://github.com/auto4opt/AutoConvexRelax.
• Abstract（参考訳）: 凸緩和は、厳密な非凸問題を有効な境界を与える凸代理に置き換えることで、非凸最適化を誘引可能である。 人間の専門家は、どの場所をリラックスするか、どの場所をリラックスするか、どの場所をリラックスするか、どのくらいの額の定式化に価値があるかを決めなければなりません。 この設計プロセスが学習可能であることを示す。 本稿で提案するAutoConvexRelaxは,変数,記号項,およびそれらの目的あるいは制約位置をリンクする三部グラフとして,非凸問題の記号的定式化を表す。 その後、定式化が進むにつれて、記号的書き直しを問題固有の緩和軌道に構成する方針を学ぶ。 学習したポリシによって生成された有限なアクションシーケンスは、明示的なドメイン、発生-コンテキスト、表現-一貫性条件の下で緩和の妥当性を保っていることを証明した。 さらに、混合緩和のための計算可能なエラー境界と、実現可能な回復とグローバル最適証明のための十分な条件を確立する。 最初のインスタンス化として、この手法を非凸二次問題や分数問題に適用する。 241のベンチマーク二次インスタンスでは、学習されたポリシーはマコーミックの下位境界を13.52%強化する。 平均下限は正規化比較計量の強化半定緩和より3.70%低いが、より小さい定式化を用いる。 学習されたポリシーは、分数的なインスタンスでのこのトレードオフを維持し、ビームフォーミングやセンサネットワークのローカライゼーションインスタンスのほぼ無限の境界に達する。 これらの結果から, 凸緩和設計は, 固定された手作りの選択肢から, 問題構造に適応する自動学習プロセスへと移行可能であることが示唆された。 コードはhttps://github.com/auto4opt/AutoConvexRelaxで入手できる。

関連論文リスト

• Semidefinite Relaxations for Collision-Free Motion Planning [53.160637667144876]
  C4トラジェクトリの観点で,inmathbbRn制約を通じて開始からゴールへ移動するポイントロボットに焦点をあてる。 C4トラジェクトリによる最小スナップ連続計画のプランナとしての有効性を示す。
  論文  参考訳（メタデータ） (2026-06-12T03:18:03Z)
• Scalable Bi-causal Optimal Transport via KL Relaxation and Policy Gradients [5.492352780011131]
  双方向最適輸送(bi-causal optimal transport、OT)は、予期しない情報制約下でのプロセスの比較と結合のためのフレームワークである。 両因果OTに対するスケーラブルな計算手法を開発し、予期しない情報制約が必須となる環境で適用性を広げる。
  論文  参考訳（メタデータ） (2026-05-17T05:41:01Z)
• A Pseudo-Semantic Loss for Autoregressive Models with Logical Constraints [87.08677547257733]
  ニューロシンボリックAIは、純粋にシンボリックな学習とニューラルな学習のギャップを埋める。 本稿では,ニューラルネットワークの出力分布に対するシンボリック制約の可能性を最大化する方法を示す。 また,スドクと最短経路予測の手法を自己回帰世代として評価した。
  論文  参考訳（メタデータ） (2023-12-06T20:58:07Z)
• Smooth over-parameterized solvers for non-smooth structured optimization [3.756550107432323]
  非滑らか性 (non-smoothness) は、空間性、群空間性、低ランクエッジ、鋭いエッジなどの解の構造的制約を符号化する。 我々は、基礎となる非滑らかな最適化問題の非重み付きだが滑らかな過度パラメータ化を運用する。 我々の主な貢献は変数の一部を明示的に最小化することで新しい定式化を定義する変数射影(VarPro)を適用することです。
  論文  参考訳（メタデータ） (2022-05-03T09:23:07Z)
• Matrix Completion via Non-Convex Relaxation and Adaptive Correlation Learning [90.8576971748142]
  閉形式解によって最適化できる新しいサロゲートを開発する。 そこで我々は, 上向きの相関関係を利用して, 適応的相関学習モデルを構築した。
  論文  参考訳（メタデータ） (2022-03-04T08:50:50Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  本稿では,データから学ぶための凸解析フレームワークを提案する。 三角凸分解はその上部に対応する変換によって保証されることを示す。
  論文  参考訳（メタデータ） (2021-09-17T17:46:12Z)
• A Boosting Approach to Reinforcement Learning [59.46285581748018]
  複雑度が状態数に依存しない意思決定プロセスにおける強化学習のための効率的なアルゴリズムについて検討する。 このような弱い学習手法の精度を向上させることができる効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-08-22T16:00:45Z)
• Deep Graph Matching under Quadratic Constraint [30.72996618021077]
  深部グラフマッチングフレームワークに組み込まれたtextbfquadratic 制約として,ペアワイズグラフ構造を明示的に定式化することを提案する。 二次制約はグラフ間の対構造的な相違を最小限に抑え、抽出したCNN特徴のみを用いて得られるあいまいさを軽減できる。 より正確かつ適切な監視を行うために、クラス不均衡に対する適切に設計された偽マッチング損失が提案され、過度に適合しない偽陰性や偽陽性をよりよく罰できる。
  論文  参考訳（メタデータ） (2021-03-11T12:51:12Z)
• Confounding-Robust Policy Evaluation in Infinite-Horizon Reinforcement Learning [70.01650994156797]
  教育医療などのバッチ強化学習において、観察データからのシーケンシャルな意思決定方針のオフ・アセスメントが必要である。 我々は、ある政策の境界を推定するアプローチを開発する。 より凝縮したデータを集めることで、シャープな境界への収束を証明します。
  論文  参考訳（メタデータ） (2020-02-11T16:18:14Z)

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

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