論文の概要: Sparse Polynomial Optimization: Theory and Practice
- arxiv url: http://arxiv.org/abs/2208.11158v2
- Date: Thu, 25 Aug 2022 08:33:03 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-26 11:23:16.831246
- Title: Sparse Polynomial Optimization: Theory and Practice
- Title（参考訳）: スパース多項式最適化:理論と実際
- Authors: Victor Magron and Jie Wang
- Abstract要約: 本書は、この課題に重要な科学的意味を持って取り組むためのいくつかの取り組みを提示している。
これは計算複雑性の観点からうまくスケールする代替の最適化スキームを提供する。
制約のない問題や制約のない問題に対して、緩和の疎開的階層を提示する。
- 参考スコア（独自算出の注目度）: 5.27013884159732
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The problem of minimizing a polynomial over a set of polynomial inequalities
is an NP-hard non-convex problem. Thanks to powerful results from real
algebraic geometry, one can convert this problem into a nested sequence of
finite-dimensional convex problems. At each step of the associated hierarchy,
one needs to solve a fixed size semidefinite program, which can be in turn
solved with efficient numerical tools. On the practical side however, there is
no-free lunch and such optimization methods usually encompass severe
scalability issues. Fortunately, for many applications, we can look at the
problem in the eyes and exploit the inherent data structure arising from the
cost and constraints describing the problem, for instance sparsity or
symmetries.
This book presents several research efforts to tackle this scientific
challenge with important computational implications, and provides the
development of alternative optimization schemes that scale well in terms of
computational complexity, at least in some identified class of problems. The
presented algorithmic framework in this book mainly exploits the sparsity
structure of the input data to solve large-scale polynomial optimization
problems. We present sparsity-exploiting hierarchies of relaxations, for either
unconstrained or constrained problems. By contrast with the dense hierarchies,
they provide faster approximation of the solution in practice but also come
with the same theoretical convergence guarantees. Our framework is not
restricted to static polynomial optimization, and we expose hierarchies of
approximations for values of interest arising from the analysis of dynamical
systems. We also present various extensions to problems involving noncommuting
variables, e.g., matrices of arbitrary size or quantum physic operators.
- Abstract（参考訳）: 多項式の不等式の集合上で多項式を最小化する問題はNP-ハード非凸問題である。
実代数幾何学の強力な結果のおかげで、この問題を有限次元凸問題のネスト列に変換することができる。
関連する階層の各ステップでは、固定サイズの半定義プログラムを解く必要があり、効率的な数値ツールで解くことができる。
しかし実用面では、フリーランチはなく、このような最適化手法は通常、厳しいスケーラビリティの問題を含んでいる。
幸いなことに、多くのアプリケーションにおいて、問題を目に見て、例えばスパーシリティや対称性といった問題を記述するコストと制約から生じる固有のデータ構造を利用することができます。
この本は、この科学的課題に重要な計算含意で取り組むためのいくつかの研究成果を提示し、少なくともいくつかの特定された問題のクラスにおいて、計算複雑性の観点からうまくスケールする代替最適化スキームの開発を提供する。
本書のアルゴリズムフレームワークは主に入力データのスパーシティ構造を利用して、大規模多項式最適化問題を解く。
我々は、制約のない問題や制約のある問題に対して、リラクゼーションの散発的な階層を提示する。
密度階層とは対照的に、実際には解のより高速な近似を提供するが、同じ理論的収束を保証する。
我々のフレームワークは静的多項式最適化に限らず、力学系の解析から生じる利害の値に対する近似の階層性を明らかにする。
また、任意のサイズの行列や量子物理演算子など、非可換変数を含む問題に対する様々な拡張も提示する。
関連論文リスト
- Structured Regularization for Constrained Optimization on the SPD Manifold [1.1126342180866644]
対称ゲージ関数に基づく構造化正規化器のクラスを導入し、より高速な非制約手法でSPD多様体上の制約付き最適化を解けるようにする。
構造正規化器は望ましい構造(特に凸性や凸の差)を保存または誘導するために選択できることを示す。
論文 参考訳（メタデータ） (2024-10-12T22:11:22Z) - Primal Methods for Variational Inequality Problems with Functional Constraints [25.261426717550293]
本稿では,関数的制約付き変分不等式問題に対処する手法として,制約付き勾配法(Constrained Gradient Method, CGM)を提案する。
滑らかな制約下での単調作用素による変分不等式問題に対するアルゴリズムの非漸近収束解析を確立する。
提案アルゴリズムは, 単調・強単調両方の演算子問合せにおいて, プロジェクションに基づく手法の複雑さに適合する。
論文 参考訳（メタデータ） (2024-03-19T16:03:03Z) - The Complexity of Optimizing Atomic Congestion [14.845310803203724]
アトミック・渋滞ゲームは、ネットワーク設計、ルーティング、アルゴリズムゲーム理論において古典的なトピックである。
非常に単純なネットワークでも問題は非常に難解なままである。
我々は、この問題の(さらに難しい)min-max変種に対する分析を拡張して結論付ける。
論文 参考訳（メタデータ） (2023-12-15T21:31:30Z) - 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) - Numerical Methods for Convex Multistage Stochastic Optimization [86.45244607927732]
最適化プログラミング(SP)、最適制御(SOC)、決定プロセス(MDP)に焦点を当てる。
凸多段マルコフ問題の解決の最近の進歩は、動的プログラミング方程式のコスト対ゴー関数の切断面近似に基づいている。
切削平面型法は多段階問題を多段階的に扱えるが、状態(決定)変数は比較的少ない。
論文 参考訳（メタデータ） (2023-03-28T01:30:40Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳（メタデータ） (2023-02-24T18:41:48Z) - Sparse resultant based minimal solvers in computer vision and their
connection with the action matrix [17.31412310131552]
いくつかのカメラ幾何問題に対して、我々の余剰手法は、最先端のGrobnerベースベースの解法よりも小さく、より安定な解法をもたらすことを示した。
コンピュータビジョンにおける最小限の問題に対して、一般的なベースベースの方法に代わる競争力のある代替手段を提供する。
論文 参考訳（メタデータ） (2023-01-16T14:25:19Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳（メタデータ） (2022-11-16T18:59:54Z) - On a class of geodesically convex optimization problems solved via
Euclidean MM methods [50.428784381385164]
ユークリッド凸化関数の違いは、統計学と機械学習の異なるタイプの問題の違いとして記述できることを示す。
最終的に、より広い範囲、より広い範囲の作業を支援するのです。
論文 参考訳（メタデータ） (2022-06-22T23:57:40Z) - Complexity continuum within Ising formulation of NP problems [0.0]
イジング・ハミルトニアンの最小化は、ある相互作用行列類に対するNPハード問題であることが知られている。
我々は、最適化単純度基準で計算学的に単純なインスタンスを特定することを提案する。
このような単純さはスピングラスからk規則の最大カット問題まで幅広いモデルで見られる。
論文 参考訳（メタデータ） (2020-08-02T11:36:38Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。