論文の概要: Karush-Kuhn-Tucker conditions for non-commutative optimization problems
- arxiv url: http://arxiv.org/abs/2311.18707v1
- Date: Thu, 30 Nov 2023 17:00:06 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-01 15:47:54.076296
- Title: Karush-Kuhn-Tucker conditions for non-commutative optimization problems
- Title（参考訳）: 非可換最適化問題に対するKarush-Kuhn-Tucker条件
- Authors: Mateus Ara\'ujo, Igor Klep, Tam\'as V\'ertesi, Andrew J. P. Garner and
Miguel Navascues
- Abstract要約: 多くの古典的最適化問題で満たされるKa-Kuhn-Tucker最適条件の非可換な類似を導入する。
我々は、多体スピン系の基底状態の局所的性質を計算し、非可換KKT条件のパワーをテストする。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of optimizing the state average of a polynomial of
non-commuting variables, over all states and operators satisfying a number of
polynomial constraints, and over all Hilbert spaces where such states and
operators are defined. Such non-commutative polynomial optimization (NPO)
problems are routinely solved through hierarchies of semidefinite programming
(SDP) relaxations. In this work, we introduce a non-commutative analog of the
Karush-Kuhn-Tucker (KKT) optimality conditions, which are satisfied by many
classical optimization problems. In the non-commutative setting, the KKT
conditions amount to adding new SDP constraints to standard SDP hierarchies,
with the effect of boosting their speed of convergence. The new optimality
conditions also allow enforcing a new type of constraints in NPO problems:
namely, restricting the optimization over states to the set of common ground
states of an arbitrary number of operators. Like in the classical case, some
necessary conditions or constraint qualifications are needed to ensure that the
KKT conditions hold in an NPO problem. We provide three: the existence of a sum
of weighted squares resolution of the problem and the non-commutative analogs
of Linear Independence Constraint Qualification and Mangasarian-Fromovitz
Constraint Qualification. We also present sufficient conditions to justify
enforcing the KKT conditions partially. We test the power of the
non-commutative KKT conditions by computing local properties of ground states
of many-body spin systems and the maximum quantum violation of Bell
inequalities.
- Abstract（参考訳）: 我々は、非可換変数の多項式の状態平均、多くの多項式制約を満たすすべての状態と作用素、およびそのような状態と作用素が定義されるすべてのヒルベルト空間の状態平均を最適化する問題を考える。
このような非可換多項式最適化(NPO)問題は、半定値プログラミング(SDP)緩和の階層によって日常的に解決される。
本研究では,多くの古典的最適化問題で満たされるKKT最適化条件の非可換類似性を導入する。
非可換な設定では、KKT条件は標準SDP階層に新しいSDP制約を加えることとなり、収束速度を向上する効果がある。
新しい最適条件はまた、NPO問題における新しいタイプの制約、すなわち任意の数の演算子の共通基底状態の集合に対する状態に対する最適化を強制することができる。
古典的な場合と同様に、KKT条件がNPO問題に収まるためには、いくつかの必要条件や制約条件が必要である。
問題に対する重み付き二乗分解の和の存在と、線形独立制約条件とマンガサリアン・フロモヴィッツ制約条件の非可換アナログの存在について述べる。
また、KKT条件を部分的に適用するための十分な条件も提示する。
多体スピン系の基底状態の局所的性質とベルの不等式最大量子違反を計算し、非可換kkt条件のパワーをテストする。
関連論文リスト
- One for All: Universal Quantum Conic Programming Framework for Hard-Constrained Combinatorial Optimization Problems [0.0]
NP完全制約最適化問題を解くための統一量子古典的枠組みを提案する。
QCPのパラメータ化アンサッツクラスは、生成したサブコーン内の最適値を常にキャプチャすることを示す。
論文 参考訳（メタデータ） (2024-11-01T08:00:30Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Non-commutative optimization problems with differential constraints [0.0]
作用素変数のサブセットが通常の微分方程式の系を満たすような NPO 問題の変種について検討する。
これにより、元の微分問題に取り組むために、SDPの完全な階層を定義することができる。
この手法を用いて、半デバイス非依存の方法で量子時系列を外挿する。
論文 参考訳（メタデータ） (2024-08-05T15:46:57Z) - QSlack: A slack-variable approach for variational quantum semi-definite
programming [5.0579795245991495]
量子コンピュータは、最もよく知られた古典的アルゴリズムのスピードアップを提供することができる。
半定値および線形プログラムを含む最適化問題の解法を示す。
これらの問題に対する予備問題と双対問題の両方の実装が、基礎的真理に近づいていることが示される。
論文 参考訳（メタデータ） (2023-12-06T19:00:01Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳（メタデータ） (2022-11-16T18:59:54Z) - Constrained Optimization Involving Nonconvex $\ell_p$ Norms: Optimality
Conditions, Algorithm and Convergence [4.886985244621422]
我々は $ell_p$ ノルムの次数と $ell_p$ 球の正規錐の次数を計算する。
逐次最適性条件は反復的に重み付けされたアルゴリズムに対して容易に満足できることを示す。
論文 参考訳（メタデータ） (2021-10-27T02:17:42Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳（メタデータ） (2021-10-20T02:57:21Z) - Parity Quantum Optimization: Compiler [0.4194295877935867]
任意の$k$-body相互作用とサイド条件からなる最適化問題を解くことを目的としたパリティ量子最適化を導入する。
この方法は、ハイパーグラフの一般化閉サイクルを用いた任意の$k$-body項による問題グラフの分解を導入する。
論文 参考訳（メタデータ） (2021-05-13T12:35:57Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z) - Efficient Methods for Structured Nonconvex-Nonconcave Min-Max
Optimization [98.0595480384208]
定常点に収束する一般化外空間を提案する。
このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
論文 参考訳（メタデータ） (2020-10-31T21:35:42Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳（メタデータ） (2020-04-25T05:45:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。