論文の概要: Tractable hierarchies of convex relaxations for polynomial optimization
on the nonnegative orthant
- arxiv url: http://arxiv.org/abs/2209.06175v1
- Date: Tue, 13 Sep 2022 17:23:50 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-14 13:27:17.840534
- Title: Tractable hierarchies of convex relaxations for polynomial optimization
on the nonnegative orthant
- Title（参考訳）: 非負orthant上の多項式最適化のための凸緩和のトラクタブル階層
- Authors: Ngoc Hoang Anh Mai and Victor Magron and Jean-Bernard Lasserre and
Kim-Chuan Toh
- Abstract要約: 非負オルサントに含まれる半代数集合上の最適化問題 (POP) を考える。
我々は、ディキンソン・ポフによる P'olya's Positivsatz の拡張に基づく半定緩和階層を提案する。
- 参考スコア（独自算出の注目度）: 7.847440192956767
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider polynomial optimization problems (POP) on a semialgebraic set
contained in the nonnegative orthant (every POP on a compact set can be put in
this format by a simple translation of the origin). Such a POP can be converted
to an equivalent POP by squaring each variable. Using even symmetry and the
concept of factor width, we propose a hierarchy of semidefinite relaxations
based on the extension of P\'olya's Positivstellensatz by Dickinson-Povh. As
its distinguishing and crucial feature, the maximal matrix size of each
resulting semidefinite relaxation can be chosen arbitrarily and in addition, we
prove that the sequence of values returned by the new hierarchy converges to
the optimal value of the original POP at the rate $O(\varepsilon^{-c})$ if the
semialgebraic set has nonempty interior. When applied to (i) robustness
certification of multi-layer neural networks and (ii) computation of positive
maximal singular values, our method based on P\'olya's Positivstellensatz
provides better bounds and runs several hundred times faster than the standard
Moment-SOS hierarchy.
- Abstract（参考訳）: 非負のオルサントに含まれる半代数集合上の多項式最適化問題(POP)を考える(コンパクト集合上のすべてのPOPは、原点の簡単な翻訳によってこの形式に置ける)。
そのような POP は各変数を同値にすることで等価な POP に変換することができる。
対称性と因子幅の概念を用いて、ディキンソン-povhによるp\'olya's positiveivstellensatzの拡張に基づく半定値緩和の階層を提案する。
その区別と決定的な特徴として、各半有限緩和の最大行列サイズを任意に選択することができ、また、半代数集合が空でない内部を持つ場合、新しい階層によって返される値列が$O(\varepsilon^{-c})$で元のPOPの最適値に収束することを証明する。
適用すると
(i)多層ニューラルネットワークのロバスト性証明と評価
(II) 正の最大特異値の計算, P'olya の Positivstellensatz に基づく手法は, より優れたバウンダリを提供し, 標準 Moment-SOS 階層よりも数百倍高速に動作する。
関連論文リスト
- Discrete Aware Matrix Completion via Convexized $\ell_0$-Norm Approximation [7.447205347712796]
本研究では,部分的に観測された低ランク行列を構造化した状態で完成させる新しいアルゴリズムについて考察する。
The proposed low-rank matrix completion (MC) method is a improve of state-of-the-art (SotA) independently aware matrix completion method。
論文 参考訳（メタデータ） (2024-05-03T13:54:59Z) - Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits [12.674929126684528]
我々は、プレイヤーがPアクションの中から d 個の基本アイテムを含む集合のパワーセットから選択する半帯域の問題に対処する。
提案手法は半帯域フィードバックを効果的に活用し,帯域フィードバックアプローチより優れていることを示す。
論文 参考訳（メタデータ） (2024-02-23T08:07:54Z) - Upper bound hierarchies for noncommutative polynomial optimization [1.6385815610837167]
この研究は、有限個の非可換制約に対する非可換の固有値の最小化に焦点を当てている。
コンパクト集合を最小化するためのラッサール問題による上界の収束階層を導出する。
論文 参考訳（メタデータ） (2024-02-03T11:53:57Z) - A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum Optimization [6.314057999212246]
ランダムリシャッフル技術は、ニューラルネットワークのような大規模アプリケーションで使用される。
本稿では,ノルムPRRが生成するランダムリシャッフル型反復が線形設定に収束することを示す。
最後に,提案手法に適用可能な最終収束率を導出する。
論文 参考訳（メタデータ） (2023-12-02T07:12:00Z) - 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) - 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) - Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
本稿では,初期監視情報を同時に拡張し,識別親和性行列を構築することのできる,新しい半教師付きサブスペースクラスタリング手法を提案する。
6つの一般的なベンチマークデータセットの総合的な実験結果から,本手法が最先端手法よりも優れていることを示す。
論文 参考訳（メタデータ） (2022-05-21T01:47:17Z) - Log-based Sparse Nonnegative Matrix Factorization for Data
Representation [55.72494900138061]
非負の行列因子化(NMF)は、非負のデータを部品ベースの表現で表すことの有効性から、近年広く研究されている。
そこで本研究では,係数行列に対数ノルムを課した新しいNMF法を提案する。
提案手法のロバスト性を高めるために,$ell_2,log$-(pseudo) ノルムを新たに提案した。
論文 参考訳（メタデータ） (2022-04-22T11:38:10Z) - DASHA: Distributed Nonconvex Optimization with Communication
Compression, Optimal Oracle Complexity, and No Client Synchronization [77.34726150561087]
我々は,分散最適化問題に対する新しい手法であるDASHAを開発し,解析する。
MARINAとは異なり、新しいDASHAとDASHA-MVRは圧縮ベクターのみを送信し、ノードを同期しないため、学習をより実用的なものにしている。
論文 参考訳（メタデータ） (2022-02-02T20:10:40Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。
そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-30T19:17:35Z) - Simple and Near-Optimal MAP Inference for Nonsymmetric DPPs [3.3504365823045044]
非対称なカーネル行列によって定義される決定点過程に対する最大後続推定(MAP)問題について検討する。
局所探索を用いてこの問題に対する最初の乗法近似保証を得る。
近似係数が$kO(k)$ に近いので、理論上、実験的に、この問題に対する最先端の手法と好適に比較できることが示される。
論文 参考訳（メタデータ） (2021-02-10T09:34:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。