論文の概要: Numerical Methods for Convex Multistage Stochastic Optimization

• arxiv url: http://arxiv.org/abs/2303.15672v1
• Date: Tue, 28 Mar 2023 01:30:40 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-29 16:50:55.035102
• Title: Numerical Methods for Convex Multistage Stochastic Optimization
• Title（参考訳）: 凸多段確率最適化の数値解法
• Authors: Guanghui Lan and Alexander Shapiro
• Abstract要約: 最適化プログラミング(SP)、最適制御(SOC)、決定プロセス(MDP)に焦点を当てる。 凸多段マルコフ問題の解決の最近の進歩は、動的プログラミング方程式のコスト対ゴー関数の切断面近似に基づいている。 切削平面型法は多段階問題を多段階的に扱えるが、状態(決定)変数は比較的少ない。
• 参考スコア（独自算出の注目度）: 86.45244607927732
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Optimization problems involving sequential decisions in a stochastic environment were studied in Stochastic Programming (SP), Stochastic Optimal Control (SOC) and Markov Decision Processes (MDP). In this paper we mainly concentrate on SP and SOC modelling approaches. In these frameworks there are natural situations when the considered problems are convex. Classical approach to sequential optimization is based on dynamic programming. It has the problem of the so-called ``Curse of Dimensionality", in that its computational complexity increases exponentially with increase of dimension of state variables. Recent progress in solving convex multistage stochastic problems is based on cutting planes approximations of the cost-to-go (value) functions of dynamic programming equations. Cutting planes type algorithms in dynamical settings is one of the main topics of this paper. We also discuss Stochastic Approximation type methods applied to multistage stochastic optimization problems. From the computational complexity point of view, these two types of methods seem to be complimentary to each other. Cutting plane type methods can handle multistage problems with a large number of stages, but a relatively smaller number of state (decision) variables. On the other hand, stochastic approximation type methods can only deal with a small number of stages, but a large number of decision variables.
• Abstract（参考訳）: 確率的プログラミング(SP)、確率的最適制御(SOC)、マルコフ決定過程(MDP)において、確率的環境における逐次決定を伴う最適化問題を検討した。 本稿では主にSPとSOCのモデリング手法に焦点を当てる。 これらのフレームワークでは、考慮された問題が凸している自然な状況がある。 逐次最適化に対する古典的なアプローチは動的プログラミングに基づいている。 いわゆる「次元の曲線」の問題があり、状態変数の次元が増加するにつれて計算の複雑さが指数関数的に増加する。 凸多段確率問題の解法における最近の進歩は、動的プログラミング方程式のコスト対ゴ(値)関数を近似した切断平面に基づいている。 動的設定における切削平面型アルゴリズムは,本論文の主要な話題の一つである。 また,多段階確率最適化問題に適用した確率近似型手法についても論じる。 計算複雑性の観点からは、これらの2種類の手法は互いに補完的であるように見える。 切断平面型メソッドは、多数のステージを持つが、比較的少ない状態(決定)変数を持つ多段問題を扱うことができる。 一方、確率近似型法は少数の段階のみを扱うことができるが、多数の決定変数を扱うことができる。

関連論文リスト

• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• The Parametric Cost Function Approximation: A new approach for multistage stochastic programming [4.847980206213335]
  決定論的最適化モデルのパラメータ化バージョンは、プログラミングや動的プログラミングの複雑さを伴わずに不確実性を扱う効果的な方法であることを示す。 このアプローチは複雑な高次元状態変数を処理でき、シナリオツリーや値関数近似に関連する通常の近似を避けることができる。
  論文  参考訳（メタデータ） (2022-01-01T23:25:09Z)
• Neural Stochastic Dual Dynamic Programming [99.80617899593526]
  我々は、問題インスタンスを断片的線形値関数にマッピングすることを学ぶトレーニング可能なニューラルモデルを導入する。 $nu$-SDDPは、ソリューションの品質を犠牲にすることなく、問題解決コストを大幅に削減できる。
  論文  参考訳（メタデータ） (2021-12-01T22:55:23Z)
• Nonequilibrium Monte Carlo for unfreezing variables in hard combinatorial optimization [1.1783108699768]
  適応的勾配自由戦略を開発することにより,非局所非平衡モンテカルロ(NMC)アルゴリズムの量子インスパイアされたファミリーを導入する。 我々は、特殊解法と汎用解法の両方に対して、大幅な高速化と堅牢性を観察する。
  論文  参考訳（メタデータ） (2021-11-26T17:45:32Z)
• Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling [86.85697555068168]
  2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。 特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。 PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
  論文  参考訳（メタデータ） (2021-05-05T03:36:00Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。 リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。 このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
  論文  参考訳（メタデータ） (2021-02-27T19:28:39Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax Problems [26.24895953952318]
  我々は,非ガンスミニマックス問題のクラスを解くアルゴリズムを開発した。 また、単一または2つのミニバッチ誘導体でも機能する。
  論文  参考訳（メタデータ） (2020-06-27T03:05:18Z)
• Bayesian optimization of variable-size design space problems [0.0]
  このタイプの最適化問題を解決するために,ベイズ最適化に基づく2つのアプローチが提案されている。 最初のアプローチは、最も有望な設計サブスペースに計算予算を集中させるための予算配分戦略である。 第二のアプローチは、部分的に異なる変数の集合によって特徴づけられるサンプル間の共分散を計算することができるカーネル関数の定義に基づいている。
  論文  参考訳（メタデータ） (2020-03-06T16:30:44Z)
• Complexity of Stochastic Dual Dynamic Programming [7.177693955272473]
  まず, 簡単な多段最適化問題の解法として, 基本的動的切削平面法が要求する反復数, すなわち複雑性を確立する。 次に、これらの基本的なツールを洗練し、決定論的および双対動的プログラミング手法の反復複雑性を確立する。
  論文  参考訳（メタデータ） (2019-12-16T20:56:46Z)

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

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