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

• arxiv url: http://arxiv.org/abs/2210.16191v1
• Date: Fri, 28 Oct 2022 14:57:13 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-31 17:01:35.291375
• Title: On the Exactness of Dantzig-Wolfe Relaxation for Rank Constrained Optimization Problems
• Title（参考訳）: ランク制約最適化問題に対するDantzig-Wolfe緩和の効果について
• Authors: Yongchun Li and Weijun Xie
• Abstract要約: 本研究では, m の2辺の線形制約付き閉ランク制約領域を交差させるよりも, 線形目的関数を最小化することを目的としたランク制約最適化問題 (RCOP) について検討する。 閉じた凸殻によって設定された領域を置き換えることで、RCOPの凸凸Dantzig-Wolfe Relaxation (DWR) が得られる。 我々は、DWRが線形目的関数の4つの好ましいクラスを許容するときに、初めて必要かつ十分な目的的正確性の条件を導出する。
• 参考スコア（独自算出の注目度）: 1.7640556247739623
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies the rank constrained optimization problem (RCOP) that aims to minimize a linear objective function over intersecting a prespecified closed rank constrained domain set with m two-sided linear constraints. Replacing the domain set by its closed convex hull offers us a convex Dantzig-Wolfe Relaxation (DWR) of the RCOP. Our goal is to characterize necessary and sufficient conditions under which the DWR and RCOP are equivalent in the sense of extreme point, convex hull, and objective value. More precisely, we develop the first-known necessary and sufficient conditions about when the DWR feasible set matches that of RCOP for any m linear constraints from two perspectives: (i) extreme point exactness -- all extreme points in the DWR feasible set belong to that of the RCOP; and (ii) convex hull exactness -- the DWR feasible set is identical to the closed convex hull of RCOP feasible set. From the optimization view, we also investigate (iii) objective exactness -- the optimal values of the DWR and RCOP coincide for any $m$ linear constraints and a family of linear objective functions. We derive the first-known necessary and sufficient conditions of objective exactness when the DWR admits four favorable classes of linear objective functions, respectively. From the primal perspective, this paper presents how our proposed conditions refine and extend the existing exactness results in the quadratically constrained quadratic program (QCQP) and fair unsupervised learning.
• Abstract（参考訳）: 本稿では,m の2辺の線形制約付き閉ランク制約領域を交差させるよりも,線形目的関数の最小化を目的としたランク制約最適化問題 (RCOP) について検討する。 閉じた凸部によって設定された領域を置き換えることで、RCOPの凸部Dantzig-Wolfe Relaxation(DWR)が得られる。 我々の目標は、DWRとRCOPが極端点、凸殻、および目的値の意味で等価である必要かつ十分な条件を特徴づけることである。 より正確には、DWR 実現可能な集合が 2 つの視点から m 個の線型制約に対して RCOP と一致するときの、最初の必要十分条件を開発する。 (i)極点完全性 --dwr実現可能集合の極端点はすべてrcopの極端点に属する。) (ii) 凸船体精度 -- DWR 実現可能な集合は RCOP 実現可能な集合の閉凸船体と同一である。 最適化の観点からも検討する。 (iii) 目的性 -- dwr と rcop の最適値は、任意の $m$ の線形制約と線形目的関数の族と一致する。 DWR が線形目的関数の 4 つの好ましいクラスをそれぞれ認めているとき、まず必要な条件と十分な目的精度の条件を導出する。 本稿では,2次制約付き2次プログラム(QCQP)と公正な教師なし学習において,提案した条件が既存の精度を洗練・拡張する方法について述べる。

関連論文リスト

• 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)

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

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