論文の概要: Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models

• arxiv url: http://arxiv.org/abs/2409.15734v2
• Date: Thu, 26 Sep 2024 04:37:48 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-06 19:32:29.427899
• Title: Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models
• Title（参考訳）: ランダムモデルを用いた確率最適化のための信頼回帰逐次二次計画法
• Authors: Yuchen Fang, Sen Na, Michael W. Mahoney, Mladen Kolar,
• Abstract要約: 本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。 本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
• 参考スコア（独自算出の注目度）: 57.52124921268249
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we consider solving optimization problems with a stochastic objective and deterministic equality constraints. We propose a Trust-Region Sequential Quadratic Programming method to find both first- and second-order stationary points. Our method utilizes a random model to represent the objective function, which is constructed from stochastic observations of the objective and is designed to satisfy proper adaptive accuracy conditions with a high but fixed probability. To converge to first-order stationary points, our method computes a gradient step in each iteration defined by minimizing a quadratic approximation of the objective subject to a (relaxed) linear approximation of the problem constraints and a trust-region constraint. To converge to second-order stationary points, our method additionally computes an eigen step to explore the negative curvature of the reduced Hessian matrix, as well as a second-order correction step to address the potential Maratos effect, which arises due to the nonlinearity of the problem constraints. Such an effect may impede the method from moving away from saddle points. Both gradient and eigen step computations leverage a novel parameter-free decomposition of the step and the trust-region radius, accounting for the proportions among the feasibility residual, optimality residual, and negative curvature. We establish global almost sure first- and second-order convergence guarantees for our method, and present computational results on CUTEst problems, regression problems, and saddle-point problems to demonstrate its superiority over existing line-search-based stochastic methods.
• Abstract（参考訳）: 本研究では,確率的目的と決定論的等式制約による最適化問題の解法を検討する。 本稿では,2次定常点と1次定常点の両方を求めるために,Trust-Region Sequential Quadratic Programming法を提案する。 本手法は,対象関数の確率的観測から構成され,高い確率で適切な適応精度条件を満たすために,ランダムモデルを用いて目的関数を表現する。 本手法は, 1次定常点に収束するために, 問題制約の線形近似と信頼領域制約の2次近似を最小化することにより, 各イテレーションの勾配ステップを計算する。 さらに, 2階定常点に収束するため, 還元ヘッセン行列の負曲率を探索する固有ステップと, 問題制約の非線形性から生じるマラトス効果に対処する2階補正ステップも計算する。 このような効果は、メソッドがサドルポイントから離れるのを妨げる可能性がある。 勾配と固有ステップの計算は、ステップと信頼領域半径の新たなパラメータフリー分解を利用しており、実現可能性残差、最適性残差、負曲率の比率を考慮に入れている。 我々は,本手法の1次および2次収束保証を大域的に確立し,CUTEst問題,回帰問題,サドルポイント問題に関する計算結果を示す。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning [132.7040981721302]
  本研究では,訪問尺度の凸関数を最小化することを目的として,制約付き凸決定プロセス(MDP)について検討する。 制約付き凸MDPの設計アルゴリズムは、大きな状態空間を扱うなど、いくつかの課題に直面している。
  論文  参考訳（メタデータ） (2024-02-16T16:35:18Z)
• Almost-sure convergence of iterates and multipliers in stochastic sequential quadratic optimization [21.022322975077653]
  等式制約付き連続最適化問題の解法が近年注目されている。 収束保証は、ゼロを測定するための勾配の期待値に制限されている。 また,SQPアルゴリズムにより生成した予備値,ラグランジュ測度,ステーション測度に対する新たなほぼ収束保証を証明した。
  論文  参考訳（メタデータ） (2023-08-07T16:03:40Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。 ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
  論文  参考訳（メタデータ） (2023-05-28T06:33:37Z)
• A Stochastic-Gradient-based Interior-Point Algorithm for Solving Smooth Bound-Constrained Optimization Problems [12.29270365918848]
  提案アルゴリズムは、他のインテリアポイント法からの主観的特異な制約に基づいている。 提案アルゴリズムは,プロジェクション,ステップサイズ,シーケンスシーケンスのバランスを慎重に保ち,数値的および決定論的両方の設定において収束を保証する。
  論文  参考訳（メタデータ） (2023-04-28T15:30:43Z)
• A Sequential Quadratic Programming Method with High Probability Complexity Bounds for Nonlinear Equality Constrained Stochastic Optimization [2.3814052021083354]
  制約関数値と導関数は利用可能であると仮定されるが、対象関数とその関連する導関数のプログラミング近似のみを計算することができる。 1次定常性を近似するためにアルゴリズムの反復複雑性に縛られる高い確率が導出される。
  論文  参考訳（メタデータ） (2023-01-01T21:46:50Z)
• Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems [62.83783246648714]
  目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。 アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
  論文  参考訳（メタデータ） (2022-11-29T05:52:17Z)
• Stochastic Mirror Descent for Large-Scale Sparse Recovery [13.500750042707407]
  本稿では,2次近似の高次元スパースパラメータの統計的推定への応用について論じる。 提案アルゴリズムは, 回帰器分布の弱い仮定の下で, 推定誤差の最適収束を実現する。
  論文  参考訳（メタデータ） (2022-10-23T23:23:23Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)

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

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