論文の概要: Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems

• arxiv url: http://arxiv.org/abs/2211.15943v2
• Date: Mon, 29 Jan 2024 02:02:20 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-31 00:52:35.988341
• Title: Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems
• Title（参考訳）: 品質制約最適化問題に対する完全確率的信頼関係系列計画法
• Authors: Yuchen Fang, Sen Na, Michael W. Mahoney, Mladen Kolar
• Abstract要約: 目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。 アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
• 参考スコア（独自算出の注目度）: 62.83783246648714
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose a trust-region stochastic sequential quadratic programming algorithm (TR-StoSQP) to solve nonlinear optimization problems with stochastic objectives and deterministic equality constraints. We consider a fully stochastic setting, where at each step a single sample is generated to estimate the objective gradient. The algorithm adaptively selects the trust-region radius and, compared to the existing line-search StoSQP schemes, allows us to utilize indefinite Hessian matrices (i.e., Hessians without modification) in SQP subproblems. As a trust-region method for constrained optimization, our algorithm must address an infeasibility issue -- the linearized equality constraints and trust-region constraints may lead to infeasible SQP subproblems. In this regard, we propose an adaptive relaxation technique to compute the trial step, consisting of a normal step and a tangential step. To control the lengths of these two steps while ensuring a scale-invariant property, we adaptively decompose the trust-region radius into two segments, based on the proportions of the rescaled feasibility and optimality residuals to the rescaled full KKT residual. The normal step has a closed form, while the tangential step is obtained by solving a trust-region subproblem, to which a solution ensuring the Cauchy reduction is sufficient for our study. We establish a global almost sure convergence guarantee for TR-StoSQP, and illustrate its empirical performance on both a subset of problems in the CUTEst test set and constrained logistic regression problems using data from the LIBSVM collection.
• Abstract（参考訳）: 確率的目的と決定論的等式制約による非線形最適化問題を解くために,信頼領域確率的二次計画アルゴリズム(tr-stosqp)を提案する。 各ステップに1つのサンプルを生成して客観的な勾配を推定する、完全に確率的な設定を考える。 アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して、SQPサブプロブレムにおいて不確定なヘッセン行列(すなわち修正なしヘッセン行列)を利用することができる。 制約付き最適化のための信頼領域法として、線形化等式制約と信頼領域制約は、実現不可能なSQPサブプロブレムをもたらす可能性がある。 そこで本研究では,通常のステップと具体的なステップからなる試行ステップを計算するための適応緩和手法を提案する。 スケール不変性を確保しつつ,これら2つのステップの長さを制御するために,再スケール実現可能性と再スケールフルkkt残差の最適残差の比率に基づいて,信頼領域半径を2つのセグメントに適応分解する。 通常のステップはクローズドな形式を持ち,信頼領域のサブプロブレムを解くことで,コーシー還元を確実にする解が十分であるような接点ステップが得られる。 我々は, TR-StoSQP の収束保証を大域的に確立し, CUTEst テストセットにおける問題のサブセットと LIBSVM コレクションのデータを用いたロジスティック回帰問題の両方に対する経験的性能を示す。

関連論文リスト

• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。 本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
  論文  参考訳（メタデータ） (2024-09-24T04:39:47Z)
• FastPart: Over-Parameterized Stochastic Gradient Descent for Sparse optimisation on Measures [1.9950682531209156]
  本稿では,コニックパーティクルグラディエントDescent(CPGD)のスケーラビリティを高めるために,ランダム特徴と協調してグラディエントDescent戦略を利用する新しいアルゴリズムを提案する。 i) 降下軌道に沿った解の総変動規範は、安定を保ち、望ましくないばらつきを防止し、 (ii) 収率$mathcalO(log(K)/sqrtK)$$$K以上の大域収束保証を確立し、アルゴリズムの効率と有効性を示す; (iii) さらに、分析と確立を行う。
  論文  参考訳（メタデータ） (2023-12-10T20:41:43Z)
• High-probability sample complexities for policy evaluation with linear function approximation [88.87036653258977]
  本研究では,2つの広く利用されている政策評価アルゴリズムに対して,最適線形係数の予め定義された推定誤差を保証するために必要なサンプル複素量について検討する。 高確率収束保証に縛られた最初のサンプル複雑性を確立し、許容レベルへの最適依存を実現する。
  論文  参考訳（メタデータ） (2023-05-30T12:58:39Z)
• Inequality Constrained Stochastic Nonlinear Optimization via Active-Set Sequential Quadratic Programming [17.9230793188835]
  客観的・決定論的等式と不等式制約を用いた非線形最適化問題について検討する。 本稿では,有理関数として微分可能な拡張ラグランジアンを用いて,能動型逐次適応型プログラミングアルゴリズムを提案する。 アルゴリズムは、拡張ラグランジアンのパラメータを適応的に選択し、行探索を行い、ステップサイズを決定する。
  論文  参考訳（メタデータ） (2021-09-23T17:12:17Z)
• Optimal Rates for Random Order Online Optimization [60.011653053877126]
  敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。 2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
  論文  参考訳（メタデータ） (2021-06-29T09:48:46Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• An Adaptive Stochastic Sequential Quadratic Programming with Differentiable Exact Augmented Lagrangians [17.9230793188835]
  本稿では,客観的・決定論的等式を考慮した非線形最適化プログラムの解法について考察する。 本稿では,微分可能な拡張ラグランジアンをメリット関数として用いた逐次二次計画法(SQP)を提案する。 提案アルゴリズムは,行探索手順と1行探索手順を許容する最初のSQPである。
  論文  参考訳（メタデータ） (2021-02-10T08:40:55Z)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。 MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
  論文  参考訳（メタデータ） (2020-10-12T17:41:44Z)

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

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