論文の概要: A practical, fast method for solving sum-of-squares problems for very large polynomials
- arxiv url: http://arxiv.org/abs/2410.19844v1
- Date: Mon, 21 Oct 2024 12:47:42 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-03 07:21:54.927313
- Title: A practical, fast method for solving sum-of-squares problems for very large polynomials
- Title（参考訳）: 超大多項式に対する2乗問題を解くための実用的で高速な解法
- Authors: Daniel Keren, Margarita Osadchy, Roi Poranne,
- Abstract要約: 正方形最適化(SOS:Sum of squares)は、 as の正則性を強制しなければならない問題を解くための強力な手法である。
私たちのゴールは、現在より大きく、より複雑な問題に対処できるアプローチを考案することにあります。
- 参考スコア（独自算出の注目度）: 10.645318208507213
- License:
- Abstract: Sum of squares (SOS) optimization is a powerful technique for solving problems where the positivity of a polynomials must be enforced. The common approach to solve an SOS problem is by relaxation to a Semidefinite Program (SDP). The main advantage of this transormation is that SDP is a convex problem for which efficient solvers are readily available. However, while considerable progress has been made in recent years, the standard approaches for solving SDPs are still known to scale poorly. Our goal is to devise an approach that can handle larger, more complex problems than is currently possible. The challenge indeed lies in how SDPs are commonly solved. State-Of-The-Art approaches rely on the interior point method, which requires the factorization of large matrices. We instead propose an approach inspired by polynomial neural networks, which exhibit excellent performance when optimized using techniques from the deep learning toolbox. In a somewhat counter-intuitive manner, we replace the convex SDP formulation with a non-convex, unconstrained, and \emph{over parameterized} formulation, and solve it using a first order optimization method. It turns out that this approach can handle very large problems, with polynomials having over four million coefficients, well beyond the range of current SDP-based approaches. Furthermore, we highlight theoretical and practical results supporting the experimental success of our approach in avoiding spurious local minima, which makes it amenable to simple and fast solutions based on gradient descent. In all the experiments, our approach had always converged to a correct global minimum, on general (non-sparse) polynomials, with running time only slightly higher than linear in the number of polynomial coefficients, compared to higher than quadratic in the number of coefficients for SDP-based methods.
- Abstract（参考訳）: 正方形最適化(SOS)は多項式の正則性を強制しなければならない問題を解くための強力な手法である。
SOS問題を解くための一般的なアプローチは、半有限プログラム (SDP) への緩和である。
この変換の主な利点は、効率的な解法が容易に利用できる凸問題である点である。
しかし,近年の進歩は著しいものの,SDPの解決の標準的アプローチはいまだに不十分であることが知られている。
私たちのゴールは、現在より大きく、より複雑な問題に対処できるアプローチを考案することにあります。
問題は、SDPが一般的に解決される方法にある。
State-Of-The-Artアプローチは、大きな行列の分解を必要とするインテリアポイント法に依存している。
そこで我々は,ディープラーニングツールボックスの手法を用いて最適化した場合に優れた性能を示す多項式ニューラルネットワークに着想を得た手法を提案する。
やや逆直感的な方法で、凸 SDP の定式化を非凸、非制約、および \emph{over parameterized} の定式化に置き換え、一階最適化法を用いて解決する。
このアプローチは非常に大きな問題に対処でき、多項式は400万の係数を持ち、現在のSDPベースのアプローチの範囲を超えている。
さらに,本手法の実験的成功を裏付ける理論的,実践的な結果を強調し,緩やかな局所最小化を回避し,勾配勾配に基づく単純かつ高速な解を導出する。
全ての実験において、我々の手法は、一般(非スパース)多項式において常に正しい大域的最小値に収束しており、多項式係数の2乗よりも、多項式係数の2乗よりもランニング時間がわずかに高い。
関連論文リスト
- Fast, Scalable, Warm-Start Semidefinite Programming with Spectral
Bundling and Sketching [53.91395791840179]
我々は、大規模なSDPを解くための、証明可能な正確で高速でスケーラブルなアルゴリズムであるUnified Spectral Bundling with Sketching (USBS)を提案する。
USBSは、20億以上の決定変数を持つインスタンス上で、最先端のスケーラブルなSDP解決器よりも500倍のスピードアップを提供する。
論文 参考訳（メタデータ） (2023-12-19T02:27:22Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features [65.64276393443346]
Frank-Wolfe (FW) 法は、構造化制約による最適化問題の解法として一般的な手法である。
有限サム勾配の最小化のためのアルゴリズムの2つの新しい変種を示す。
論文 参考訳（メタデータ） (2023-04-23T20:05:09Z) - Sparse resultant based minimal solvers in computer vision and their
connection with the action matrix [17.31412310131552]
いくつかのカメラ幾何問題に対して、我々の余剰手法は、最先端のGrobnerベースベースの解法よりも小さく、より安定な解法をもたらすことを示した。
コンピュータビジョンにおける最小限の問題に対して、一般的なベースベースの方法に代わる競争力のある代替手段を提供する。
論文 参考訳（メタデータ） (2023-01-16T14:25:19Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-12-19T14:48:54Z) - Sparse Polynomial Optimization: Theory and Practice [5.27013884159732]
本書は、この課題に重要な科学的意味を持って取り組むためのいくつかの取り組みを提示している。
これは計算複雑性の観点からうまくスケールする代替の最適化スキームを提供する。
制約のない問題や制約のない問題に対して、緩和の疎開的階層を提示する。
論文 参考訳（メタデータ） (2022-08-23T18:56:05Z) - Momentum-inspired Low-Rank Coordinate Descent for Diagonally Constrained
SDPs [12.7944665592057]
本稿では,制約付き半有限計画法(SDP)を高速化した非自明なプログラムを用いて大規模に解くための,新しい,実用的で証明可能なアプローチを提案する。
論文 参考訳（メタデータ） (2021-06-16T13:35:40Z) - STRIDE along Spectrahedral Vertices for Solving Large-Scale Rank-One
Semidefinite Relaxations [27.353023427198806]
我々は、制約のない最適化問題(POP)の高次半定値プログラミング緩和を考察する。
POPから独立してSDPを解く既存のアプローチは、そのようなSDPの典型的な非エネルギー性のため、大きな問題にスケールできないか、あるいは緩やかな収束に苦しむことができない。
我々は SpecTrahedral vErtices (STRIDE) と呼ばれる新しいアルゴリズムフレームワークを提案する。
論文 参考訳（メタデータ） (2021-05-28T18:07:16Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。