論文の概要: On the Exactness of Dantzig-Wolfe Relaxation for Rank Constrained Optimization Problems

• arxiv url: http://arxiv.org/abs/2210.16191v3
• Date: Wed, 14 Jun 2023 13:57:16 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-17 03:14:15.884589
• Title: On the Exactness of Dantzig-Wolfe Relaxation for Rank Constrained Optimization Problems
• Title（参考訳）: ランク制約最適化問題に対するDantzig-Wolfe緩和の効果について
• Authors: Yongchun Li and Weijun Xie
• Abstract要約: i) 極点の完全性 -- 極点の全ては RCOP 集合に属する; (ii) 極点の完全性 -- 任意の m 側線型行列の不等式に対する DWR RCOP の完全性; (iii) 公正学習のための完全性。 これらの条件は、公正な学習のために2つの同質な二面的正確性を持つ不均一な制約を許容する問題に対する極端に正確性を含む、新しい結果を特定するのに非常に有用である。
• 参考スコア（独自算出の注目度）: 1.7640556247739623
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the rank-constrained optimization problem (RCOP), it minimizes a linear objective function over a prespecified closed rank-constrained domain set and $m$ generic two-sided linear matrix inequalities. Motivated by the Dantzig-Wolfe (DW) decomposition, a popular approach of solving many nonconvex optimization problems, we investigate the strength of DW relaxation (DWR) of the RCOP, which admits the same formulation as RCOP except replacing the domain set by its closed convex hull. Notably, our goal is to characterize conditions under which the DWR matches RCOP for any m two-sided linear matrix inequalities. From the primal perspective, we develop the first-known simultaneously necessary and sufficient conditions that achieve: (i) extreme point exactness -- all the extreme points of the DWR feasible set belong to that of the RCOP; (ii) convex hull exactness -- the DWR feasible set is identical to the closed convex hull of RCOP feasible set; and (iii) objective exactness -- the optimal values of the DWR and RCOP coincide. The proposed conditions unify, refine, and extend the existing exactness results in the quadratically constrained quadratic program (QCQP) and fair unsupervised learning. These conditions can be very useful to identify new results, including the extreme point exactness for a QCQP problem that admits an inhomogeneous objective function with two homogeneous two-sided quadratic constraints and the convex hull exactness for fair SVD.
• Abstract（参考訳）: 階数制約最適化問題(RCOP)では、予め定義された階数制約付き領域集合上の線形目的関数を最小化し、一般的な二辺行列の不等式を$m$とする。 多くの非凸最適化問題を解く一般的なアプローチであるダンツィヒ=ウルフ分解(DW)によって動機付けられ、RCOPのDW緩和(DWR)の強さについて検討する。 特に、我々の目標は、DWRが任意の m 個の二辺行列の不等式に対して RCOP と一致する条件を特徴づけることである。 初歩的な観点からは、最初に知られた必要条件と十分条件を同時に開発する。 (i)極点正確性 -- DWR の可能な集合のすべての極点が RCOP の極点に属する。 (ii) 凸船体精度 -- DWR 実現可能な集合は RCOP 実現可能な集合の閉凸船体と同一である。 (iii) 客観的厳密性 - dwr と rcop の最適値が一致する。 提案した条件は,2次制約付き2次プログラム(QCQP)と公正な教師なし学習において,既存の正確性を統一,洗練,拡張する。 これらの条件は、2つの同質な2辺2次制約を持つ不均一な目的関数を許容するQCQP問題の極点完全性や、フェアSVDの凸包完全性など、新しい結果の同定に非常に有用である。

関連論文リスト

• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。 本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
  論文  参考訳（メタデータ） (2024-09-24T04:39:47Z)
• Variable Substitution and Bilinear Programming for Aligning Partially Overlapping Point Sets [48.1015832267945]
  本研究では,RPMアルゴリズムの最小化目的関数を用いて要求を満たす手法を提案する。 分岐とバウンド(BnB)アルゴリズムが考案され、パラメータのみに分岐し、収束率を高める。 実験による評価は,非剛性変形,位置雑音,外れ値に対する提案手法の高剛性を示す。
  論文  参考訳（メタデータ） (2024-05-14T13:28:57Z)
• Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning [132.7040981721302]
  本研究では,訪問尺度の凸関数を最小化することを目的として,制約付き凸決定プロセス(MDP)について検討する。 制約付き凸MDPの設計アルゴリズムは、大きな状態空間を扱うなど、いくつかの課題に直面している。
  論文  参考訳（メタデータ） (2024-02-16T16:35:18Z)
• Low-Rank Extragradient Methods for Scalable Semidefinite Optimization [0.0]
  この問題が低ランクの解を許容する高次元かつ高可算な設定に焦点をあてる。 これらの条件下では、よく知られた過次法が制約付き最適化問題の解に収束することを示す理論的結果がいくつか提示される。
  論文  参考訳（メタデータ） (2024-02-14T10:48:00Z)
• ALEXR: An Optimal Single-Loop Algorithm for Convex Finite-Sum Coupled Compositional Stochastic Optimization [53.14532968909759]
  ALEXRと呼ばれる,効率的な単ループプリマルデュアルブロックコーディネートアルゴリズムを提案する。 本研究では, ALEXR の凸面および強凸面の収束速度を滑らか性および非滑らか性条件下で確立する。 本稿では,ALEXRの収束速度が,検討されたcFCCO問題に対する1次ブロック座標アルゴリズムの中で最適であることを示すために,より低い複雑性境界を示す。
  論文  参考訳（メタデータ） (2023-12-04T19:00:07Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• On the Partial Convexification for Low-Rank Spectral Optimization: Rank Bounds and Algorithms [1.7640556247739623]
  低ランクスペクトル最適化問題(LSOP)は、複数の二辺行列の不等式を対象とする線形対象を最小化する。 LSOPの解法は一般にNPハードであるが、「LSOP-R」と呼ばれる部分凸化はしばしば抽出可能であり、高品質な解が得られる。
  論文  参考訳（メタデータ） (2023-05-12T17:46:29Z)
• Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems [62.83783246648714]
  目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。 アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
  論文  参考訳（メタデータ） (2022-11-29T05:52:17Z)
• Sparse Representations of Positive Functions via First and Second-Order Pseudo-Mirror Descent [15.340540198612823]
  推定器の範囲が非負である必要がある場合、予測されるリスク問題を考察する。 Emphpseudo-gradientsを用いた近似ミラーの1階および2階の変種を開発した。 実験は、実際に不均一なプロセス強度推定に好適な性能を示す。
  論文  参考訳（メタデータ） (2020-11-13T21:54:28Z)
• Fused-Lasso Regularized Cholesky Factors of Large Nonstationary Covariance Matrices of Longitudinal Data [0.0]
  大きな共分散行列のコレスキー因子のサブ対角線の滑らかさは、時系列および長手データに対する自己回帰モデルの非定常度の度合いと密接に関連している。 行ごとに分離するColesky因子のスパース推定アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-07-22T02:38:16Z)

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

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