論文の概要: Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints

• arxiv url: http://arxiv.org/abs/2009.10395v2
• Date: Fri, 2 Apr 2021 20:45:08 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-15 22:09:17.119051
• Title: Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints
• Title（参考訳）: Mixed-Projection Conic Optimization: ランク制約のモデリングのための新しいパラダイム
• Authors: Dimitris Bertsimas, Ryan Cory-Wright, Jean Pauphilet
• Abstract要約: 低ランク最適化問題を証明可能な最適性に解決するためのフレームワークを提供する。 我々のフレームワークは、ラウンドリングや局所探索技術を通じて、ほぼ最適のソリューションを提供する。
• 参考スコア（独自算出の注目度）: 3.179831861897336
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a framework for modeling and solving low-rank optimization problems to certifiable optimality. We introduce symmetric projection matrices that satisfy $Y^2=Y$, the matrix analog of binary variables that satisfy $z^2=z$, to model rank constraints. By leveraging regularization and strong duality, we prove that this modeling paradigm yields tractable convex optimization problems over the non-convex set of orthogonal projection matrices. Furthermore, we design outer-approximation algorithms to solve low-rank problems to certifiable optimality, compute lower bounds via their semidefinite relaxations, and provide near-optimal solutions through rounding and local search techniques. We implement these numerical ingredients and, for the first time, solve low-rank optimization problems to certifiable optimality. Using currently available spatial branch-and-bound codes, not tailored to projection matrices, we can scale our exact (resp. near-exact) algorithms to matrices with up to 30 (resp. 600) rows/columns. Our algorithms also supply certifiably near-optimal solutions for larger problem sizes and outperform existing heuristics, by deriving an alternative to the popular nuclear norm relaxation which generalizes the perspective relaxation from vectors to matrices. All in all, our framework, which we name Mixed-Projection Conic Optimization, solves low-rank problems to certifiable optimality in a tractable and unified fashion.
• Abstract（参考訳）: 本稿では,低ランク最適化問題のモデル化と解決のためのフレームワークを提案する。 モデルランク制約に対して、z^2=z$を満たす二変数の行列類似である$Y^2=Y$を満たす対称射影行列を導入する。 正則化と強い双対性を利用することで、このモデリングパラダイムは直交射影行列の非凸集合上の可搬凸最適化問題をもたらすことが証明される。 さらに,低位問題を解くために外近似アルゴリズムを設計し,最適性を証明し,その半定値緩和により下限を計算し,丸め法と局所探索法を通じて最適に近い解を与える。 これらの数値要素を実装し, 初めて低ランク最適化問題を解き, 最適性を検証した。 現在利用可能な空間的分岐・境界符号を投影行列に合わせるのではなく、30行/カラム(600行)までの行列に正確な(近似に近い)アルゴリズムをスケールできる。 我々のアルゴリズムは、ベクトルから行列へのパースペクティブ緩和を一般化する一般的な核ノルム緩和の代替法を導出することにより、より大きな問題サイズと既存のヒューリスティックよりも優れた近似解を提供する。 全体として、私たちがMixed-Projection Conic Optimizationと呼ぶフレームワークは、トラクタブルで統一的な方法で証明可能な最適性を実現するために、低ランクの問題を解決する。

関連論文リスト

• Global Optimization: A Machine Learning Approach [7.052596485478637]
  Bertsimas と Ozturk (2023) は、ブラックボックスのグローバル最適化問題を解決する方法として OCTHaGOn を提案した。 我々は、他のMIO表現可能なMLモデルを用いて、元の問題を近似することで、このアプローチの拡張を提供する。 多くの場合において、ソリューションの実現可能性と最適性の改善を示す。
  論文  参考訳（メタデータ） (2023-11-03T06:33:38Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Optimal Low-Rank Matrix Completion: Semidefinite Relaxations and Eigenvector Disjunctions [6.537257913467247]
  低ランク行列の完備化は、与えられた観測セットをできるだけ正確に回復する最小の複雑さの行列からなる。 新たな凸緩和は、既存の方法に比べて最大値を大幅に下げる。
  論文  参考訳（メタデータ） (2023-05-20T22:04:34Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Optimal Diagonal Preconditioning: Theory and Practice [23.79536881427839]
  本稿では,列数や列数の最大化を同時に達成するために,最適対角前処理の問題を提案する。 実装が容易なベースライン分岐アルゴリズムを提案する。 次に, 片側最適対角前条件問題に特化し, 標準双対SDP問題として定式化できることを実証する。
  論文  参考訳（メタデータ） (2022-09-02T04:21:28Z)
• Low-Rank Mirror-Prox for Nonsmooth and Low-Rank Matrix Optimization Problems [19.930021245647705]
  低ランクおよび非滑らかな行列最適化問題は統計学や機械学習における多くの基本的なタスクを捉えている。 本稿では,このような問題に対する標準凸緩和について考察する。 本研究は, テクスト性相補性条件の下で, 比較的軽度な仮定の下では, 非滑らかな目的が2つの一般的なテクストミラー-プロキシ法の近似変種であるスムーズな関数の最大値として記述できることを証明した。
  論文  参考訳（メタデータ） (2022-06-23T08:10:54Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)
• Global Optimization of Gaussian processes [52.77024349608834]
  少数のデータポイントで学習したガウス過程を訓練した空間定式化を提案する。 このアプローチはまた、より小さく、計算的にもより安価なサブソルバを低いバウンディングに導く。 提案手法の順序の順序による時間収束を,総じて低減する。
  論文  参考訳（メタデータ） (2020-05-21T20:59:11Z)
• Stochastic Coordinate Minimization with Progressive Precision for Stochastic Convex Optimization [16.0251555430107]
  凸最適化のための反復座標最小化(CM)に基づくフレームワークを開発した。 最適精度制御と結果の順序-最適後悔性能を確立する。 提案アルゴリズムは,大規模最適化のためのCMのスケーラビリティと並列性特性を継承し,オンライン実装に適したアルゴリズムである。
  論文  参考訳（メタデータ） (2020-03-11T18:42:40Z)

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

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