論文の概要: Transforming optimization problems into a QUBO form: A tutorial

• arxiv url: http://arxiv.org/abs/2410.21074v1
• Date: Mon, 28 Oct 2024 14:38:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-29 12:21:06.708529
• Title: Transforming optimization problems into a QUBO form: A tutorial
• Title（参考訳）: 最適化問題をQUBO形式に変換する:チュートリアル
• Authors: Alexander M. Semenov, Sergey R. Usmanov, Aleksey K. Fedorov,
• Abstract要約: 2次最適化の実際的な問題には、線形制約によって相互に相互に交わされる変数の多次元配列が含まれることが多い。 本論文は,元問題文の3つの主要な変換を同定し,考察する。 計算の連続式を提示し、証明し、これらの変換の実装を簡素化する。
• 参考スコア（独自算出の注目度）: 45.31975029877049
• License:
• Abstract: Practically relevant problems of quadratic optimization often contain multidimensional arrays of variables interconnected by linear constraints, such as equalities and inequalities. The values of each variable depend on its specific meaning and can be binary, integer, discrete, and continuous. These circumstances make it technically difficult to reduce the original problem statement to the QUBO form. The paper identifies and considers three main transformations of the original problem statement, namely, the transition from a multidimensional to a one-dimensional array of variables, the transition in mixed problems to binary variables, and the inclusion of linear constraints in the objective function in the form of quadratic penalties. Convenient formulas for calculations are presented and proven, simplifying the implementation of these transformations. In particular, the formulas for the transition in the problem statement from a multidimensional to a one-dimensional array of variables are based on the use of the Kronecker product of matrices. The considered transformations are illustrated by numerous examples.
• Abstract（参考訳）: 2次最適化の実際的な問題には、等式や不等式のような線形制約によって相互に連結された変数の多次元配列を含むことが多い。 各変数の値は、その特定の意味に依存し、バイナリ、整数、離散、連続である。 これらの状況により、QUBO形式にオリジナルの問題文を還元することが技術的に困難になる。 本稿は,元問題文の3つの主要な変換,すなわち,多次元から1次元の変数列への遷移,混合問題から2変数への遷移,および2次ペナルティの形での目的関数への線形制約の包含について考察する。 計算の連続式を提示し、証明し、これらの変換の実装を簡素化する。 特に、多次元から一次元の変数列への問題文の遷移の公式は、行列のクロネッカー積(英語版)(Kronecker product of matrices)を用いている。 考慮された変換は、多くの例によって説明される。

関連論文リスト

• Online Stability Improvement of Groebner Basis Solvers using Deep Learning [29.805408457645886]
  異なる変数や単項順序が異なる消去テンプレートにつながることを示す。 次に、元の係数の集合が、優れた解法の選択を訓練するのに十分な情報を含むことを証明した。
  論文  参考訳（メタデータ） (2024-01-17T16:51:28Z)
• Data-driven path collective variables [0.0]
  本稿では,集合変数の生成,最適化,比較のための新しい手法を提案する。 結果として得られる集合変数は1次元、解釈可能、微分可能である。 2つの異なるアプリケーションに対して,本手法の有効性を示す。
  論文  参考訳（メタデータ） (2023-12-21T14:07:47Z)
• Outlier detection in regression: conic quadratic formulations [3.04585143845864]
  多くのアプリケーションにおいて、アウトレーヤの存在、すなわち、破損した入力データポイントの存在を考慮することが重要である。 文献における既存のアプローチは、通常、ビッグM制約を用いた立方体項の線形化に依存し、弱い緩和と実際のパフォーマンスの低下に悩まされている。 この研究では、大きなMの制約を伴わないより強い二階円錐緩和を導出する。
  論文  参考訳（メタデータ） (2023-07-12T07:44:13Z)
• Manifold Gaussian Variational Bayes on the Precision Matrix [70.44024861252554]
  複雑なモデルにおける変分推論(VI)の最適化アルゴリズムを提案する。 本研究では,変分行列上の正定値制約を満たすガウス変分推論の効率的なアルゴリズムを開発した。 MGVBPはブラックボックスの性質のため、複雑なモデルにおけるVIのための準備が整ったソリューションである。
  論文  参考訳（メタデータ） (2022-10-26T10:12:31Z)
• Equivariant Disentangled Transformation for Domain Generalization under Combination Shift [91.38796390449504]
  ドメインとラベルの組み合わせは、トレーニング中に観察されるのではなく、テスト環境に現れる。 我々は、同型の概念、同値性、および整合性の定義に基づく結合シフト問題の一意的な定式化を提供する。
  論文  参考訳（メタデータ） (2022-08-03T12:31:31Z)
• Efficient QUBO transformation for Higher Degree Pseudo Boolean Functions [0.46040036610482665]
  より高次擬似ブール問題をQUBO形式に変換する方法を持つことは有用である。 本稿では, 加算変数数とペナルティ係数を最小化することにより, 既存の立方体-四方体変換法を改善する。
  論文  参考訳（メタデータ） (2021-07-24T22:13:42Z)
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
  最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。 驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。 提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
  論文  参考訳（メタデータ） (2020-08-12T08:52:50Z)
• Modeling Linear Inequality Constraints in Quadratic Binary Optimization for Variational Quantum Eigensolver [0.0]
  本稿では, 変分量子固有解法における配向型変分形式の利用について紹介する。 通常、いくつかの最適化問題に現れる4つの制約がモデル化されている。 提案手法の主な利点は、変分形式のパラメータの数が一定であることである。
  論文  参考訳（メタデータ） (2020-07-26T23:36:22Z)
• Eigendecomposition-Free Training of Deep Networks for Linear Least-Square Problems [107.3868459697569]
  我々は、ディープネットワークのトレーニングに固有分解のないアプローチを導入する。 この手法は固有分解の明示的な微分よりもはるかに堅牢であることを示す。 我々の手法は収束特性が良く、最先端の結果が得られます。
  論文  参考訳（メタデータ） (2020-04-15T04:29:34Z)
• Multi-Objective Matrix Normalization for Fine-grained Visual Recognition [153.49014114484424]
  双線形プールは細粒度視覚認識(FGVC)において大きな成功を収める 近年,行列パワー正規化は双線形特徴量において2次情報を安定化させることができることが示されている。 両線形表現を同時に正規化できる効率的な多目的行列正規化法(MOMN)を提案する。
  論文  参考訳（メタデータ） (2020-03-30T08:40:35Z)

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

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