論文の概要: An Augmented Lagrangian Approach to Conically Constrained Non-monotone Variational Inequality Problems

• arxiv url: http://arxiv.org/abs/2306.01214v1
• Date: Fri, 2 Jun 2023 00:33:15 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-05 17:12:51.641816
• Title: An Augmented Lagrangian Approach to Conically Constrained Non-monotone Variational Inequality Problems
• Title（参考訳）: 円錐制約付き非単調変分不等式問題に対する拡張ラグランジアンアプローチ
• Authors: Lei Zhao, Daoli Zhu, Shuzhong Zhang
• Abstract要約: ALAVIと呼ばれる拡張ラグランジアン原始双対法を導入し、一般に制約されたVIモデルを解く。 計量準正則性条件の下では、VI モデルが非単調であっても、ALAVI の局所収束速度は線形となる。
• 参考スコア（独自算出の注目度）: 8.609626012634559
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper we consider a non-monotone (mixed) variational inequality model with (nonlinear) convex conic constraints. Through developing an equivalent Lagrangian function-like primal-dual saddle-point system for the VI model in question, we introduce an augmented Lagrangian primal-dual method, to be called ALAVI in the current paper, for solving a general constrained VI model. Under an assumption, to be called the primal-dual variational coherence condition in the paper, we prove the convergence of ALAVI. Next, we show that many existing generalized monotonicity properties are sufficient -- though by no means necessary -- to imply the above mentioned coherence condition, thus are sufficient to ensure convergence of ALAVI. Under that assumption, we further show that ALAVI has in fact an $o(1/\sqrt{k})$ global rate of convergence where $k$ is the iteration count. By introducing a new gap function, this rate further improves to be $O(1/k)$ if the mapping is monotone. Finally, we show that under a metric subregularity condition, even if the VI model may be non-monotone the local convergence rate of ALAVI improves to be linear. Numerical experiments on some randomly generated highly nonlinear and non-monotone VI problems show practical efficacy of the newly proposed method.
• Abstract（参考訳）: 本稿では、(非線形)凸凸錐制約を持つ非単調(混合)変分不等式モデルを考える。 問題となるviモデルに対して等価なラグランジアン関数様原始双対サドルポイント系を開発することにより,本論文ではalaviと呼ばれる拡張ラグランジ的原始双対法を導入し,一般制約付きviモデルを解く。 ALAVI の収束性を証明する前提条件として,本論文では主対二変量コヒーレンス条件(primal-dual variational coherence condition)と呼ぶ。 次に、上述したコヒーレンス条件を暗示するためには、既存の一般化単調性の性質が(必ずしも必要ではないが)十分であることを示し、したがって ALAVI の収束を保証するのに十分である。 この仮定の下では、ALAVI が実際に $o(1/\sqrt{k})$大域収束率を持ち、$k$ は反復数であることを示す。 新しいギャップ関数を導入することにより、写像が単調であれば、このレートはさらに$O(1/k)$になる。 最後に、計量準正則性条件の下では、VI モデルが非単調であっても、ALAVI の局所収束速度は線形になることを示す。 ランダムに生成した高非線形および非単調な VI 問題の数値実験により,提案手法の有効性が示された。

関連論文リスト

• On the Hypomonotone Class of Variational Inequalities [4.204990010424083]
  本研究では,低単調な演算子に適用した場合の過次アルゴリズムの挙動について検討する。 次数次アルゴリズムが収束しない条件を特定するための評価定理を提供する。
  論文  参考訳（メタデータ） (2024-10-11T18:35:48Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• A Primal-Dual Approach to Solving Variational Inequalities with General Constraints [54.62996442406718]
  Yang et al. (2023) は最近、一般的な変分不等式を解決するために一階勾配法を使う方法を示した。 この方法の収束性を証明し、演算子が$L$-Lipschitz と monotone である場合、この手法の最後の繰り返しのギャップ関数が$O(frac1sqrtK)$で減少することを示す。
  論文  参考訳（メタデータ） (2022-10-27T17:59:09Z)
• Solving Constrained Variational Inequalities via an Interior Point Method [88.39091990656107]
  制約付き変分不等式(cVI)問題を解くためのインテリアポイントアプローチを開発する。 本稿では,2種類の問題においてACVIの収束保証を提供する。 この設定における以前の作業とは異なり、ACVIは制約が自明でない場合にcVIを解く手段を提供する。
  論文  参考訳（メタデータ） (2022-06-21T17:55:13Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。 この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。 さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
  論文  参考訳（メタデータ） (2022-06-02T15:21:55Z)
• Tight Last-Iterate Convergence of the Extragradient Method for Constrained Monotone Variational Inequalities [4.6193503399184275]
  制約付きモノトンおよびリプシッツの変分不等式について, 過次法の最終点収束率を示す。 我々は,2乗法プログラミングのパワーと,指数関数法更新規則の低次元性を組み合わせた新しい手法を開発した。
  論文  参考訳（メタデータ） (2022-04-20T05:12:11Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。 定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。 我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
  論文  参考訳（メタデータ） (2021-06-30T18:32:46Z)
• Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance [14.06947898164194]
  ヘビーテールは様々なシナリオで勾配降下 (sgd) で現れる。 SGDの収束保証は、潜在的に無限のばらつきを持つ状態依存性および重尾ノイズ下で提供します。 その結果,SGDは無限に分散した重尾雑音下であっても,地球最適値に収束できることが示された。
  論文  参考訳（メタデータ） (2021-02-20T13:45:11Z)
• Variance-Reduced Splitting Schemes for Monotone Stochastic Generalized Equations [0.0]
  演算子を期待値とする単調な包摂問題を考える。 分割スキームの直接適用は、各ステップにおける期待値マップによる問題解決の必要性により複雑である。 本稿では,不確実性に対処する手法を提案する。
  論文  参考訳（メタデータ） (2020-08-26T02:33:27Z)
• Linear Last-iterate Convergence in Constrained Saddle-point Optimization [48.44657553192801]
  我々は、OGDA(Optimistic Gradient Descent Ascent)とOMWU(Optimistic Multiplicative Weights Update)に対する最終段階の独特さの理解を著しく拡大する。 平衡が一意である場合、線形終端収束は、値が普遍定数に設定された学習速度で達成されることを示す。 任意のポリトープ上の双線型ゲームがこの条件を満たすことを示し、OGDAは一意の平衡仮定なしで指数関数的に高速に収束することを示した。
  論文  参考訳（メタデータ） (2020-06-16T20:53:04Z)

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

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