論文の概要: Sums of Separable and Quadratic Polynomials
- arxiv url: http://arxiv.org/abs/2105.04766v1
- Date: Tue, 11 May 2021 03:26:46 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-12 13:43:42.823084
- Title: Sums of Separable and Quadratic Polynomials
- Title（参考訳）: 分離多項式と二次多項式の和
- Authors: Amir Ali Ahmadi, Cemil Dibek, Georgina Hall
- Abstract要約: 我々は分離可能プラス二次(SPQ)を研究します。
凸spq最適化問題は「小さな」半定義プログラムによって解決できることを示す。
- 参考スコア（独自算出の注目度）: 0.3222802562733786
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study separable plus quadratic (SPQ) polynomials, i.e., polynomials that
are the sum of univariate polynomials in different variables and a quadratic
polynomial. Motivated by the fact that nonnegative separable and nonnegative
quadratic polynomials are sums of squares, we study whether nonnegative SPQ
polynomials are (i) the sum of a nonnegative separable and a nonnegative
quadratic polynomial, and (ii) a sum of squares. We establish that the answer
to question (i) is positive for univariate plus quadratic polynomials and for
convex SPQ polynomials, but negative already for bivariate quartic SPQ
polynomials. We use our decomposition result for convex SPQ polynomials to show
that convex SPQ polynomial optimization problems can be solved by "small"
semidefinite programs. For question (ii), we provide a complete
characterization of the answer based on the degree and the number of variables
of the SPQ polynomial. We also prove that testing nonnegativity of SPQ
polynomials is NP-hard when the degree is at least four. We end by presenting
applications of SPQ polynomials to upper bounding sparsity of solutions to
linear programs, polynomial regression problems in statistics, and a
generalization of Newton's method which incorporates separable higher-order
derivative information.
- Abstract（参考訳）: 分離可能プラス二次多項式(SPQ)、すなわち異なる変数の単変数多項式と二次多項式の和である多項式について研究する。
非負の分離可能多項式と非負の二次多項式が平方の和であるという事実に動機づけられ、非負のspq多項式が(i)非負の分離可能多項式と非負の二次多項式の和であるか否か、(ii)平方の和である。
i) に対する解が単変量 + 2次多項式と凸SPQ多項式に対して正であることは証明するが、既に二変量四次SPQ多項式に対しては負である。
我々は、凸SPQ多項式の分解結果を用いて、凸SPQ多項式最適化問題を「小さな」半定値プログラムで解けることを示す。
質問 (ii) に対して, spq 多項式の変数の次数と個数に基づく解の完全なキャラクタリゼーションを提供する。
また,spq多項式の非負性テストは,少なくとも4つの場合,np-hardであることが証明される。
最後に、線形プログラムに対する解の上界スパース性、統計における多項式回帰問題、分離可能な高階微分情報を含むニュートン法の一般化へのspq多項式の適用を提示する。
関連論文リスト
- Efficient Solution of Point-Line Absolute Pose [52.775981113238046]
点や線である可能性のある特徴間の3D--2D対応に基づくポーズ推定の特定の問題を再検討する。
得られた解法は数値的に安定かつ高速であることを示す。
論文 参考訳（メタデータ） (2024-04-25T12:09:16Z) - Sums of squares certificates for polynomial moment inequalities [1.6385815610837167]
本稿では,通勤変数とその形式的混合モーメントの表現であるモーメント表現の枠組みを紹介し,開発する。
応用として、量子物理学からの2つの開放非線形ベル不等式が解決される。
論文 参考訳（メタデータ） (2023-06-09T08:55:26Z) - Influences of Fourier Completely Bounded Polynomials and Classical
Simulation of Quantum Algorithms [0.0]
量子クエリアルゴリズムは、フーリエ完全有界な新しいクラスによって特徴づけられることを示す。
我々は、すべてのそのような変数は影響のある変数を持つと推測する。
我々の証明は単純で、より良い定数を得ることができ、ランダム性を使用しない。
論文 参考訳（メタデータ） (2023-04-13T17:58:36Z) - State polynomials: positivity, optimization and nonlinear Bell
inequalities [3.9692590090301683]
本稿では,非可換変数の状態とそれらの積の形式状態を紹介する。
これは、すべての正の状態と正の状態が、分母を持つ正方形の和であることを示している。
また、Avinetengle Kritivsatzが状態設定で保持できないことも確認されている。
論文 参考訳（メタデータ） (2023-01-29T18:52:21Z) - A Direct Reduction from the Polynomial to the Adversary Method [92.54311953850168]
逆法に(双対の形で)方法から単純かつ直接的に還元する。
これは、双対形式におけるどんな下界も、特定の形式の逆下界であることを示している。
論文 参考訳（メタデータ） (2023-01-24T21:37:20Z) - An Exponential Separation Between Quantum Query Complexity and the
Polynomial Degree [79.43134049617873]
本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。
アルファベットのサイズについては、定値対分離の複雑さがある。
論文 参考訳（メタデータ） (2023-01-22T22:08:28Z) - Two-body Coulomb problem and $g^{(2)}$ algebra (once again about the
Hydrogen atom) [77.34726150561087]
3次元系の対称性が $(r, rho, varphi)$ であれば、変数 $(r, rho, varphi)$ は変数 $varphi$ と固有函数の分離を可能にする。
これらは水素原子に対するゼーマン効果の研究で起こる。
論文 参考訳（メタデータ） (2022-12-02T20:11:17Z) - Complexity aspects of local minima and related notions [3.42658286826597]
我々は (i) 臨界点、 (ii) 二次点、 (iii) 局所ミニマ、 (iv) 多変量に対する厳密な局所ミニマの概念を考える。
立方体が臨界点を持つかどうかを決定することはNPハードであることを示す。
本稿では,3階ニュートン法の設計における局所最小値立方体探索の可能性について概説する。
論文 参考訳（メタデータ） (2020-08-14T00:50:13Z) - SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
SURFは分布を断片的に近似するアルゴリズムである。
実験では最先端のアルゴリズムよりも優れています。
論文 参考訳（メタデータ） (2020-02-22T01:03:33Z) - A refinement of Reznick's Positivstellensatz with applications to
quantum information theory [72.8349503901712]
ヒルベルトの17番目の問題において、アルティンはいくつかの変数の任意の正定値が2つの平方和の商として書けることを示した。
レズニックはアルティンの結果の分母は常に変数の平方ノルムの$N$-次パワーとして選択できることを示した。
論文 参考訳（メタデータ） (2019-09-04T11:46:26Z) - Discrete orthogonality relations for multi-indexed Laguerre and Jacobi polynomials [0.0]
マルチインデックスのLaguerre と Jacobis も持つことを示す。
また,Hermite,Laguerre,Jacobisに基づくKrein-Adlersも保有していることを示す。
論文 参考訳（メタデータ） (2019-07-21T10:15:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。