論文の概要: STRIDE along Spectrahedral Vertices for Solving Large-Scale Rank-One Semidefinite Relaxations

• arxiv url: http://arxiv.org/abs/2105.14033v1
• Date: Fri, 28 May 2021 18:07:16 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-06 04:12:56.220092
• Title: STRIDE along Spectrahedral Vertices for Solving Large-Scale Rank-One Semidefinite Relaxations
• Title（参考訳）: 大規模ランク1半定緩和のためのスペクトル頂点に沿ったSTRIDE
• Authors: Heng Yang, Ling Liang, Kim-Chuan Toh, Luca Carlone
• Abstract要約: 我々は、制約のない最適化問題(POP)の高次半定値プログラミング緩和を考察する。 POPから独立してSDPを解く既存のアプローチは、そのようなSDPの典型的な非エネルギー性のため、大きな問題にスケールできないか、あるいは緩やかな収束に苦しむことができない。 我々は SpecTrahedral vErtices (STRIDE) と呼ばれる新しいアルゴリズムフレームワークを提案する。
• 参考スコア（独自算出の注目度）: 27.353023427198806
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider solving high-order semidefinite programming (SDP) relaxations of nonconvex polynomial optimization problems (POPs) that admit rank-one optimal solutions. Existing approaches, which solve the SDP independently from the POP, either cannot scale to large problems or suffer from slow convergence due to the typical degeneracy of such SDPs. We propose a new algorithmic framework, called SpecTrahedral pRoximal gradIent Descent along vErtices (STRIDE), that blends fast local search on the nonconvex POP with global descent on the convex SDP. Specifically, STRIDE follows a globally convergent trajectory driven by a proximal gradient method (PGM) for solving the SDP, while simultaneously probing long, but safeguarded, rank-one "strides", generated by fast nonlinear programming algorithms on the POP, to seek rapid descent. We prove STRIDE has global convergence. To solve the subproblem of projecting a given point onto the feasible set of the SDP, we reformulate the projection step as a continuously differentiable unconstrained optimization and apply a limited-memory BFGS method to achieve both scalability and accuracy. We conduct numerical experiments on solving second-order SDP relaxations arising from two important applications in machine learning and computer vision. STRIDE dominates a diverse set of five existing SDP solvers and is the only solver that can solve degenerate rank-one SDPs to high accuracy (e.g., KKT residuals below 1e-9), even in the presence of millions of equality constraints.
• Abstract（参考訳）: 階数1の最適解を持つ非凸多項式最適化問題(POP)の高次半定値プログラミング(SDP)緩和を考察する。 POPから独立してSDPを解く既存のアプローチは、そのようなSDPの典型的な退化によって、大きな問題にスケールできないか、あるいは緩やかな収束に苦しむことができない。 本稿では,非凸POP上の高速局所探索と凸SDP上のグローバル降下をブレンドする,SpecTrahedral pRoximal gradIent Descent along vErtices (STRIDE)と呼ばれる新しいアルゴリズムフレームワークを提案する。 具体的には、SDPを解くための近位勾配法(PGM)によって駆動されるグローバルな収束軌道に従っており、同時にPOP上の高速非線形プログラミングアルゴリズムによって生成される、長いが安全に守られたランクワンの「ストライド」を探索して、高速降下を求める。 我々はSTRIDEがグローバルに収束していることを証明する。 与えられた点をSDPの実行可能な集合に投影するサブプロブレムを解決するため、連続的な微分不可能な最適化としてプロジェクションステップを再構成し、限られたメモリBFGS法を適用してスケーラビリティと精度を両立させる。 機械学習とコンピュータビジョンの2つの重要な応用から生じる2次SDP緩和を解くための数値実験を行う。 STRIDEは5つの既存のSDP解決器の多種多様な集合を支配しており、数百万の等式制約が存在する場合でも、階数1のSDPを高精度に解ける唯一の解法である(KKT残基は1e-9以下)。

関連論文リスト

• 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)
• Neural Stochastic Dual Dynamic Programming [99.80617899593526]
  我々は、問題インスタンスを断片的線形値関数にマッピングすることを学ぶトレーニング可能なニューラルモデルを導入する。 $nu$-SDDPは、ソリューションの品質を犠牲にすることなく、問題解決コストを大幅に削減できる。
  論文  参考訳（メタデータ） (2021-12-01T22:55:23Z)
• Efficient semidefinite bounds for multi-label discrete graphical models [6.226454551201676]
  このようなモデルにおける主要なクエリの1つは、Posteri(MAP)ネットワークのコストに関するSDPWCSP関数を特定することである。 従来の二重化制約手法と,行ごとの更新に基づく専用SDP/Monteiroスタイルの手法を検討する。
  論文  参考訳（メタデータ） (2021-11-24T13:38:34Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Certifiable Outlier-Robust Geometric Perception: Exact Semidefinite Relaxations and Scalable Global Optimization [29.738513596063946]
  本稿では,外接点の存在下でのロバストな幾何学的知覚のためのアルゴリズム設計のための,最初の汎用フレームワークを提案する。 我々の実験では、SDP緩和はアプリケーション間で最大で外れ率で正確であることを実証した。
  論文  参考訳（メタデータ） (2021-09-07T21:42:16Z)
• Momentum-inspired Low-Rank Coordinate Descent for Diagonally Constrained SDPs [12.7944665592057]
  本稿では,制約付き半有限計画法(SDP)を高速化した非自明なプログラムを用いて大規模に解くための,新しい,実用的で証明可能なアプローチを提案する。
  論文  参考訳（メタデータ） (2021-06-16T13:35:40Z)
• Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling [86.85697555068168]
  2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。 特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。 PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
  論文  参考訳（メタデータ） (2021-05-05T03:36:00Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Stochastic gradient algorithms from ODE splitting perspective [0.0]
  我々は、ODEの近似解の分割スキームに遡る最適化に関する異なる見解を示す。 そこで本研究では, ODE の勾配一階分割方式と降下アプローチの関連性について述べる。 我々は、機械学習アプリケーションにインスパイアされた分割の特殊なケースを考察し、それに対するグローバルスプリッティングエラーに新たな上限を導出する。
  論文  参考訳（メタデータ） (2020-04-19T22:45:32Z)

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

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