論文の概要: On the complexity of finding a local minimizer of a quadratic function over a polytope

• arxiv url: http://arxiv.org/abs/2008.05558v5
• Date: Thu, 14 Sep 2023 01:22:30 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-15 20:09:09.281893
• Title: On the complexity of finding a local minimizer of a quadratic function over a polytope
• Title（参考訳）: ポリトープ上の二次関数の局所最小値を求める複雑さについて
• Authors: Amir Ali Ahmadi, Jeffrey Zhang
• Abstract要約: P=NPがなければ、ポリトープ上の$n$2次関数の局所最小値の$cn$以内の点を見つけるユークリッド時間アルゴリズムは存在しない。 また,2次関数が非有界ポリヘドロン上の局所最小値を持つか否か,およびクォートが局所最小値を持つか否かを判定する問題も示唆している。
• 参考スコア（独自算出の注目度）: 1.0048921884287543
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 \ge 0$) of a local minimizer of an $n$-variate quadratic function over a polytope. This result (even with $c=0$) answers a question of Pardalos and Vavasis that appeared in 1992 on a list of seven open problems in complexity theory for numerical optimization. Our proof technique also implies that the problem of deciding whether a quadratic function has a local minimizer over an (unbounded) polyhedron, and that of deciding if a quartic polynomial has a local minimizer are NP-hard.
• Abstract（参考訳）: p=np でなければ、ユークリッド距離 $c^n$ (任意の定数 $c \ge 0$) 内の点を、ポリトープ上の$n$-変量二次関数の局所最小化器で見つける多項式時間アルゴリズムは存在しない。 この結果は($c=0$であっても)1992年に数値最適化のための複雑性理論の7つの開問題のリストに現れたパルダロスとヴァヴァシスの質問に答える。 我々の証明手法は、二次函数が(有界)ポリヘドロン上の局所最小値を持つかどうか、およびクォート多項式が局所最小値を持つかどうかを決定する問題も示唆している。

関連論文リスト

• Efficient Solution of Point-Line Absolute Pose [52.775981113238046]
  点や線である可能性のある特徴間の3D--2D対応に基づくポーズ推定の特定の問題を再検討する。 得られた解法は数値的に安定かつ高速であることを示す。
  論文  参考訳（メタデータ） (2024-04-25T12:09:16Z)
• Approximate Integer Solution Counts over Linear Arithmetic Constraints [2.28438857884398]
  本稿では,ポリトープ内の格子数に近似する新しいフレームワークを提案する。 我々のアルゴリズムは、数十次元のポリトープを解くことができ、最先端のカウンタを著しく上回る。
  論文  参考訳（メタデータ） (2023-12-14T09:53:54Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。 特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
  論文  参考訳（メタデータ） (2023-01-10T20:43:29Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。 1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。 テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
  論文  参考訳（メタデータ） (2022-11-10T00:40:37Z)
• 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)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Complexity Aspects of Fundamental Questions in Polynomial Optimization [3.42658286826597]
  P=NPがなければ、二次プログラムの局所最小値のユークリッド距離内の点を見つけるSDPは存在しないことを示す。 また、最適値が有限であるプログラムが最適解を持つか否かをテストすることはNPハードであることを示す。 最終章では,SDPの階層化に寄与する強制力の特性について紹介する。
  論文  参考訳（メタデータ） (2020-08-27T14:58:02Z)
• Complexity aspects of local minima and related notions [3.42658286826597]
  我々は (i) 臨界点、 (ii) 二次点、 (iii) 局所ミニマ、 (iv) 多変量に対する厳密な局所ミニマの概念を考える。 立方体が臨界点を持つかどうかを決定することはNPハードであることを示す。 本稿では,3階ニュートン法の設計における局所最小値立方体探索の可能性について概説する。
  論文  参考訳（メタデータ） (2020-08-14T00:50:13Z)
• Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries [55.28642461328172]
  平均的なケースの教えの複雑さは$Theta(d)$であり、最悪のケースの教えの複雑さは$Theta(n)$とは対照的である。 我々の洞察は、$phi$-separable dichotomiesの平均ケースの複雑さに厳密な拘束力を確立することを可能にする。
  論文  参考訳（メタデータ） (2020-06-25T19:59:24Z)
• Learning sums of powers of low-degree polynomials in the non-degenerate case [2.6109033135086777]
  我々は、ある非退化条件が成立すれば、同じモデルに対する下界から算術回路モデルの学習アルゴリズムを与える。 本アルゴリズムは,同じモデルに対する下界から算術回路モデルの学習アルゴリズムを得るためのスキームに基づいている。
  論文  参考訳（メタデータ） (2020-04-15T06:18:41Z)

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

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