論文の概要: Complexity Aspects of Fundamental Questions in Polynomial Optimization
- arxiv url: http://arxiv.org/abs/2008.12170v1
- Date: Thu, 27 Aug 2020 14:58:02 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-24 08:45:53.120131
- Title: Complexity Aspects of Fundamental Questions in Polynomial Optimization
- Title（参考訳）: 多項式最適化における基本問題の複雑性
- Authors: Jeffrey Zhang
- Abstract要約: P=NPがなければ、二次プログラムの局所最小値のユークリッド距離内の点を見つけるSDPは存在しないことを示す。
また、最適値が有限であるプログラムが最適解を持つか否かをテストすることはNPハードであることを示す。
最終章では,SDPの階層化に寄与する強制力の特性について紹介する。
- 参考スコア（独自算出の注目度）: 3.42658286826597
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this thesis, we settle the computational complexity of some fundamental
questions in polynomial optimization. These include the questions of (i)
finding a local minimum, (ii) testing local minimality of a point, and (iii)
deciding attainment of the optimal value. Our results characterize the
complexity of these three questions for all degrees of the defining polynomials
left open by prior literature.
Regarding (i) and (ii), we show that unless P=NP, there cannot be a
polynomial-time algorithm that finds a point within Euclidean distance $c^n$
(for any constant $c$) of a local minimum of an $n$-variate quadratic program.
By contrast, we show that a local minimum of a cubic polynomial can be found
efficiently by semidefinite programming (SDP). We prove that second-order
points of cubic polynomials admit an efficient semidefinite representation,
even though their critical points are NP-hard to find. We also give an
efficiently-checkable necessary and sufficient condition for local minimality
of a point for a cubic polynomial.
Regarding (iii), we prove that testing whether a quadratically constrained
quadratic program with a finite optimal value has an optimal solution is
NP-hard. We also show that testing coercivity of the objective function,
compactness of the feasible set, and the Archimedean property associated with
the description of the feasible set are all NP-hard. We also give a new
characterization of coercive polynomials that lends itself to a hierarchy of
SDPs.
In our final chapter, we present an SDP relaxation for finding approximate
Nash equilibria in bimatrix games. We show that for a symmetric game, a
$1/3$-Nash equilibrium can be efficiently recovered from any rank-2 solution to
this relaxation. We also propose SDP relaxations for NP-hard problems related
to Nash equilibria, such as that of finding the highest achievable welfare
under any Nash equilibrium.
- Abstract（参考訳）: 本論文では,多項式最適化における基本的な問題の計算複雑性を解消する。
これらの質問は
(i)局所的な最小値を見つけること
(ii)点の局所極小性をテストすること、及び
(iii)最適値の達成を決定すること。
以上の結果から, 定義多項式のすべての次数に対するこれらの3つの質問の複雑さが, 先行文献によって解かれる。
周辺
(i)および
(ii)、P=NPがなければ、局所最小値$n$-変数二次プログラムのユークリッド距離$c^n$(任意の定数$c$)内の点を見つける多項式時間アルゴリズムは存在しないことを示す。
対照的に、立方体多項式の局所最小値は半定値プログラミング(SDP)によって効率的に見つけることができる。
立方体多項式の2階点は、その臨界点がNPハードであるにもかかわらず、効率的な半定値表現を持つことを証明する。
また、立方体多項式の点の局所極小に対して、効率よく検証可能な必要十分条件を与える。
周辺
(iii) 有限最適値の2次制約付き二次プログラムが最適解を持つかどうかをテストすることはNPハードである。
また、目的関数の公約性、実現可能な集合のコンパクト性、および実現可能な集合の記述に関連するアルキメデス的性質がすべてNPハードであることを示す。
また,sdpsの階層化に寄与する強制多項式の新たなキャラクタリゼーションについても述べる。
最後の章では、ビマトリクスゲームにおける近似ナッシュ平衡を求めるためのSDP緩和について述べる。
対称ゲームの場合、この緩和のために任意のランク2解から$1/3$-Nash平衡を効率的に回収できることが示される。
また,nash平衡下で最高の達成可能福祉を求めることなど,nash平衡に関連するnp問題に対するsdp緩和も提案する。
関連論文リスト
- 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) - Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum [30.01198677588252]
1次アルゴリズムは、$varepsilon-stationary pointを見つけるのに少なくとも$mathcalO(varepsilonepsilon-4)$ complexityを必要とする。
本稿では,高効率な変動複雑性を生かした新しい運動量アルゴリズムを提案する。
本手法の有効性は実世界のデータセットを用いてロジスティック回帰を用いて検証する。
論文 参考訳（メタデータ） (2024-06-18T20:14:52Z) - Polynomial-Time Solutions for ReLU Network Training: A Complexity
Classification via Max-Cut and Zonotopes [70.52097560486683]
我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。
特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
論文 参考訳（メタデータ） (2023-11-18T04:41:07Z) - Exponential Hardness of Reinforcement Learning with Linear Function
Approximation [20.066210529358177]
指数時間仮説に基づく線形強化学習において,特徴・地平線で指数関数的な計算下界を示す。
また、地平線依存に最適化された下界が$exp(sqrtH)$の最もよく知られた上界とほぼ一致することを示す。
論文 参考訳（メタデータ） (2023-02-25T00:19:49Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - On the energy landscape of symmetric quantum signal processing [1.5301252700705212]
我々は、ある特定の大域的解(「大域的最小」と呼ばれる)が、コスト関数が大域的関数であるような0ドルに属することを証明した。
最適化アルゴリズムの部分的説明について説明する。
論文 参考訳（メタデータ） (2021-10-11T04:16:48Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - Complexity aspects of local minima and related notions [3.42658286826597]
我々は (i) 臨界点、 (ii) 二次点、 (iii) 局所ミニマ、 (iv) 多変量に対する厳密な局所ミニマの概念を考える。
立方体が臨界点を持つかどうかを決定することはNPハードであることを示す。
本稿では,3階ニュートン法の設計における局所最小値立方体探索の可能性について概説する。
論文 参考訳（メタデータ） (2020-08-14T00:50:13Z) - On the complexity of finding a local minimizer of a quadratic function
over a polytope [1.0048921884287543]
P=NPがなければ、ポリトープ上の$n$2次関数の局所最小値の$cn$以内の点を見つけるユークリッド時間アルゴリズムは存在しない。
また,2次関数が非有界ポリヘドロン上の局所最小値を持つか否か,およびクォートが局所最小値を持つか否かを判定する問題も示唆している。
論文 参考訳（メタデータ） (2020-08-12T20:09:34Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳（メタデータ） (2020-04-25T05:45:59Z) - SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
SURFは分布を断片的に近似するアルゴリズムである。
実験では最先端のアルゴリズムよりも優れています。
論文 参考訳（メタデータ） (2020-02-22T01:03:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。