論文の概要: Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization

• arxiv url: http://arxiv.org/abs/2211.09121v3
• Date: Sat, 8 Jul 2023 11:11:36 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-13 20:04:23.563275
• Title: Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization
• Title（参考訳）: 生成モデリングと制約付き組合せ最適化のための対称テンソルネットワーク
• Authors: Javier Lopez-Piqueres, Jing Chen, Alejandro Perdomo-Ortiz
• Abstract要約: ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
• 参考スコア（独自算出の注目度）: 72.41480594026815
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Constrained combinatorial optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In some heuristic solvers, these are typically addressed by introducing certain Lagrange multipliers in the cost function, by relaxing them in some way, or worse yet, by generating many samples and only keeping valid ones, which leads to very expensive and inefficient searches. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric tensor networks (TNs) and leverage their applicability as quantum-inspired generative models to assist in the search of solutions to combinatorial optimization problems. This allows us to exploit the generalization capabilities of TN generative models while constraining them so that they only output valid samples. Our constrained TN generative model efficiently captures the constraints by reducing number of parameters and computational costs. We find that at tasks with constraints given by arbitrary equalities, symmetric Matrix Product States outperform their standard unconstrained counterparts at finding novel and better solutions to combinatorial optimization problems.
• Abstract（参考訳）: ポートフォリオ最適化からロジスティクスまで、業界に多い制約付き組合せ最適化の問題。 これらの問題を解決する大きな障害の1つは、有効な探索空間を制限する非自明なハード制約の存在である。 いくつかのヒューリスティックな解法において、これらは典型的にはコスト関数に特定のラグランジュ乗数を導入し、それらを何らかの方法で緩和し、さらに悪いことに、多くのサンプルを生成して有効なものだけを保持することにより、非常に高価で非効率な探索をもたらす。 本研究では, ax=b 形式の任意の整数値等式制約を u(1) 対称テンソルネットワーク (tns) に直接エンコードし, 組合せ最適化問題の解探索を支援する量子モデルとしてその適用性を活用する。 これにより、TN生成モデルの一般化能力を利用でき、それらを制約することで、有効なサンプルのみを出力できる。 制約付きTN生成モデルは,パラメータ数と計算コストを削減し,制約を効率的に捕捉する。 任意の等式によって与えられる制約のあるタスクにおいて、対称行列積状態は、組合せ最適化問題に対する新しいより良い解を見つけるために、標準の制約のないタスクよりも優れることがわかった。

関連論文リスト

• Cons-training tensor networks [2.8834278113855896]
  テンソルネットワークと呼ばれる新しいファミリーを導入する。 textitconstrained matrix product state (MPS) これらのネットワークは、不等式を含むちょうど任意の離散線型制約をスパースブロック構造に含んでいる。 これらのネットワークは、特に、可能空間上で厳密にサポートされた分散をモデル化するために調整されている。
  論文  参考訳（メタデータ） (2024-05-15T00:13:18Z)
• Multi-Agent Bayesian Optimization with Coupled Black-Box and Affine Constraints [21.38692458445459]
  ブラックボックス制約と既知のアフィン制約を結合した分散マルチエージェントベイズ最適化の問題について検討する。 単一エージェントの場合と同様の後悔/違反境界を実現するアルゴリズムが提案されている。
  論文  参考訳（メタデータ） (2023-10-02T08:07:36Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Polynomial Optimization: Enhancing RLT relaxations with Conic Constraints [0.0]
  円錐最適化は、非スケール問題に対するトラクタブルで保証されたアルゴリズムを設計するための強力なツールとして登場した。 最適化問題に対するRLT緩和の強化について,9種類の制約を加えて検討する。 我々は、これらの変種とその性能を、互いに、そして標準RCT緩和に関してどのように設計するかを示す。
  論文  参考訳（メタデータ） (2022-08-11T02:13:04Z)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。 我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。 我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
  論文  参考訳（メタデータ） (2022-03-11T17:19:26Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  データ駆動最適化の問題を検討し、一定の点セットでクエリのみを与えられた関数を最大化する必要がある。 この問題は、関数評価が複雑で高価なプロセスである多くの領域に現れる。 我々は,提案手法を高容量ニューラルネットワークモデルに拡張可能なトラクタブル近似を提案する。
  論文  参考訳（メタデータ） (2021-02-16T06:04:27Z)
• A Hybrid Framework Using a QUBO Solver For Permutation-Based Combinatorial Optimization [5.460573052311485]
  本稿では,高性能な2次非制約バイナリ最適化器を用いて,大規模な置換に基づく問題を解くためのハイブリッドフレームワークを提案する。 通常はビット数に制限があるQUBOソルバを使用する際の課題を克服する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-27T07:15:25Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax Problems [26.24895953952318]
  我々は,非ガンスミニマックス問題のクラスを解くアルゴリズムを開発した。 また、単一または2つのミニバッチ誘導体でも機能する。
  論文  参考訳（メタデータ） (2020-06-27T03:05:18Z)

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

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