論文の概要: An Adaptive Stochastic Sequential Quadratic Programming with
Differentiable Exact Augmented Lagrangians
- arxiv url: http://arxiv.org/abs/2102.05320v1
- Date: Wed, 10 Feb 2021 08:40:55 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-12 01:59:20.372218
- Title: An Adaptive Stochastic Sequential Quadratic Programming with
Differentiable Exact Augmented Lagrangians
- Title(参考訳): 微分可能拡張ラグランジアンを用いた適応確率列二次計画法
- Authors: Sen Na, Mihai Anitescu, Mladen Kolar
- Abstract要約: 本稿では,客観的・決定論的等式を考慮した非線形最適化プログラムの解法について考察する。
本稿では,微分可能な拡張ラグランジアンをメリット関数として用いた逐次二次計画法(SQP)を提案する。
提案アルゴリズムは,行探索手順と1行探索手順を許容する最初のSQPである。
- 参考スコア(独自算出の注目度): 17.9230793188835
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of solving nonlinear optimization programs with
stochastic objective and deterministic equality constraints. We assume for the
objective that the function evaluation, the gradient, and the Hessian are
inaccessible, while one can compute their stochastic estimates by, for example,
subsampling. We propose a stochastic algorithm based on sequential quadratic
programming (SQP) that uses a differentiable exact augmented Lagrangian as the
merit function. To motivate our algorithm, we revisit an old SQP method
\citep{Lucidi1990Recursive} developed for deterministic programs. We simplify
that method and derive an adaptive SQP, which serves as the skeleton of our
stochastic algorithm. Based on the derived algorithm, we then propose a
non-adaptive SQP for optimizing stochastic objectives, where the gradient and
the Hessian are replaced by stochastic estimates but the stepsize is
deterministic and prespecified. Finally, we incorporate a recent stochastic
line search procedure \citep{Paquette2020Stochastic} into our non-adaptive
stochastic SQP to arrive at an adaptive stochastic SQP. To our knowledge, the
proposed algorithm is the first stochastic SQP that allows a line search
procedure and the first stochastic line search procedure that allows the
constraints. The global convergence for all proposed SQP methods is
established, while numerical experiments on nonlinear problems in the CUTEst
test set demonstrate the superiority of the proposed algorithm.
- Abstract(参考訳): 非線形最適化プログラムを確率的目的と決定論的等式制約で解く問題を考える。
関数の評価、勾配、およびヘッシアンがアクセスできないという目的を仮定し、その確率的推定は、例えばサブサンプリングによって計算できる。
本稿では,有理関数として微分可能な拡張ラグランジアンを用いた逐次二次計画法(SQP)に基づく確率的アルゴリズムを提案する。
アルゴリズムを動機付けるために、決定論的プログラム用に開発された古いSQPメソッドである \citep{Lucidi1990Recursive} を再検討する。
我々は,この手法を単純化し,確率アルゴリズムのスケルトンとして機能する適応型SQPを導出する。
導出アルゴリズムに基づいて, 勾配とヘッシアンを確率的推定に置き換えるが, ステップ化は決定論的かつ事前定式化される確率的目標を最適化するための非適応sqpを提案する。
最後に、最近の確率線探索手順 \citep{Paquette2020Stochastic} を非適応確率SQPに組み込み、適応確率SQPに到達します。
我々の知る限り、提案アルゴリズムは、行探索手順を許容する最初の確率的SQPであり、また制約を許容する最初の確率的直線探索手順である。
提案されたSQPメソッドのグローバル収束が確立され、CUTEstテストセットの非線形問題に関する数値実験が提案されたアルゴリズムの優位性を示している。
関連論文リスト
- Adaptive Step Sizes for Preconditioned Stochastic Gradient Descent [0.41104247065851574]
本稿では,勾配降下(SGD)における適応ステップサイズに対する新しいアプローチを提案する。
我々は、勾配に対するリプシッツ定数と探索方向の局所的分散の概念という、数値的にトレース可能な量を用いる。
論文 参考訳(メタデータ) (2023-11-28T17:03:56Z) - A Sequential Quadratic Programming Method with High Probability
Complexity Bounds for Nonlinear Equality Constrained Stochastic Optimization [2.535271349350579]
制約関数値と導関数は利用可能であると仮定されるが、対象関数とその関連する導関数のプログラミング近似のみを計算することができる。
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) - Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time
Guarantees [56.848265937921354]
逆強化学習(IRL)は報酬関数と関連する最適ポリシーを回復することを目的としている。
IRLの多くのアルゴリズムは本質的にネスト構造を持つ。
我々は、報酬推定精度を損なわないIRLのための新しいシングルループアルゴリズムを開発した。
論文 参考訳(メタデータ) (2022-10-04T17:13:45Z) - Statistical Inference of Constrained Stochastic Optimization via
Sketched Sequential Quadratic Programming [59.36379287247961]
この問題を解決するために,完全オンライン逐次2次プログラミング(StoSQP)手法を開発した。
最近の数値二階法の設計により、StoSQPは任意のランダムなステップサイズを適応的に選択できる。
また,2次法の計算コストを大幅に削減するため,StoSQPはランダム化反復解法を用いて2次プログラムを不正確に解けるようにした。
論文 参考訳(メタデータ) (2022-05-27T00:34:03Z) - Inequality Constrained Stochastic Nonlinear Optimization via Active-Set
Sequential Quadratic Programming [17.9230793188835]
客観的・決定論的等式と不等式制約を用いた非線形最適化問題について検討する。
本稿では,有理関数として微分可能な拡張ラグランジアンを用いて,能動型逐次適応型プログラミングアルゴリズムを提案する。
アルゴリズムは、拡張ラグランジアンのパラメータを適応的に選択し、行探索を行い、ステップサイズを決定する。
論文 参考訳(メタデータ) (2021-09-23T17:12:17Z) - Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained
Optimization [13.170519806372075]
2組の制約を持つ凸最適化の問題は、半定値プログラミングの文脈で頻繁に発生する。
最初の制約セットへのプロジェクションは困難であるため、プロジェクションフリーなアルゴリズムを探索する必要がある。
提案アルゴリズムの有効性は, スパース行列推定, 半定緩和によるクラスタリング, および一様スペースカット問題の適用性について検証した。
論文 参考訳(メタデータ) (2021-07-14T08:01:30Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - Sequential Quadratic Optimization for Nonlinear Equality Constrained
Stochastic Optimization [10.017195276758454]
この設定では、客観的関数と微分値を明示的に計算することは難しそうだと仮定する。
最先端のライン探索SQPアルゴリズムをモデルとした決定論的設定のためのアルゴリズムを提案する。
数値実験の結果は,提案手法の実用性を示すものである。
論文 参考訳(メタデータ) (2020-07-20T23:04:26Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。
本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。
ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
論文 参考訳(メタデータ) (2020-06-11T19:40:38Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳(メタデータ) (2020-06-11T17:43:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。