論文の概要: Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep
Unrolling
- arxiv url: http://arxiv.org/abs/2105.01853v1
- Date: Wed, 5 May 2021 03:36:00 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-06 12:35:23.255948
- Title: Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep
Unrolling
- Title(参考訳): プライマル・ダイアル分解とディープアンロールによる2段階確率最適化
- Authors: An Liu, Rui Yang, Tony Q. S. Quek and Min-Jian Zhao
- Abstract要約: 2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。
特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。
PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
- 参考スコア(独自算出の注目度): 86.85697555068168
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a two-stage stochastic optimization problem, in which a long-term
optimization variable is coupled with a set of short-term optimization
variables in both objective and constraint functions. Despite that two-stage
stochastic optimization plays a critical role in various engineering and
scientific applications, there still lack efficient algorithms, especially when
the long-term and short-term variables are coupled in the constraints. To
overcome the challenge caused by tightly coupled stochastic constraints, we
first establish a two-stage primal-dual decomposition (PDD) method to decompose
the two-stage problem into a long-term problem and a family of short-term
subproblems. Then we propose a PDD-based stochastic successive convex
approximation (PDD-SSCA) algorithmic framework to find KKT solutions for
two-stage stochastic optimization problems. At each iteration, PDD-SSCA first
runs a short-term sub-algorithm to find stationary points of the short-term
subproblems associated with a mini-batch of the state samples. Then it
constructs a convex surrogate for the long-term problem based on the deep
unrolling of the short-term sub-algorithm and the back propagation method.
Finally, the optimal solution of the convex surrogate problem is solved to
generate the next iterate. We establish the almost sure convergence of PDD-SSCA
and customize the algorithmic framework to solve two important application
problems. Simulations show that PDD-SSCA can achieve superior performance over
existing solutions.
- Abstract(参考訳): 目的関数と制約関数の両方において、長期最適化変数と短期最適化変数のセットを結合した2段階確率最適化問題を考える。
2段階確率最適化は様々な工学や科学的応用において重要な役割を担っているが、特に長期変数と短期変数が制約に組み合わさった場合、効率的アルゴリズムが欠けている。
密結合型確率論的制約によって引き起こされる課題を克服するため,まず2段階の原始双対分解法(PDD)を構築し,2段階の問題を長期問題と短期サブプロブレム群に分解する。
次に,2段階確率最適化問題に対するKKT解を求めるために,PDD-SSCAアルゴリズムフレームワークを提案する。
各イテレーションにおいて、PDD-SSCAはまず短期的なサブアルゴリズムを実行し、状態サンプルのミニバッチに関連する短期的なサブプロブレムの定常点を見つける。
次に,短期的部分アルゴリズムの深部展開と後方伝播法に基づいて,長期的問題に対する凸代理を構築する。
最後に、凸代理問題の最適解を解いて次の繰り返しを生成する。
PDD-SSCAのほぼ確実に収束を確立し、2つの重要なアプリケーション問題を解決するためにアルゴリズムフレームワークをカスタマイズする。
シミュレーションにより、PDD-SSCAは既存のソリューションよりも優れた性能が得られることが示された。
関連論文リスト
- Transformer-based Stagewise Decomposition for Large-Scale Multistage Stochastic Optimization [1.3124513975412255]
本稿では,トランスフォーマーに基づく段階分解アルゴリズムであるTrranSDDPを紹介する。
本研究では,値関数の分数次線形近似を効率よく生成することを示す。
論文 参考訳(メタデータ) (2024-04-03T09:08:15Z) - Online Non-convex Optimization with Long-term Non-convex Constraints [2.033434950296318]
Follow-the-Perturbed-Leader型アルゴリズムを提案する。
提案アルゴリズムは,長期(極値)制約のある河川汚染源同定問題に対処するために適用された。
論文 参考訳(メタデータ) (2023-11-04T15:08:36Z) - Quantum Annealing Solutions for the Closest String Problem with D-Wave
Systems [0.0]
クローズストストリング問題(Closest String problem)は、生物情報学や符号化理論でよく見られるNP完全問題である。
2つのQUBOの定式化が提案されており、1つはもう1つに対してわずかに修正されている。
DWaveアナライザは、特定のプラットフォーム固有の関心事に対する最適なガイドラインを提供しながら使われてきた。
論文 参考訳(メタデータ) (2023-10-19T16:03:25Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳(メタデータ) (2021-10-20T02:57:21Z) - Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained
Optimization [13.170519806372075]
2組の制約を持つ凸最適化の問題は、半定値プログラミングの文脈で頻繁に発生する。
最初の制約セットへのプロジェクションは困難であるため、プロジェクションフリーなアルゴリズムを探索する必要がある。
提案アルゴリズムの有効性は, スパース行列推定, 半定緩和によるクラスタリング, および一様スペースカット問題の適用性について検証した。
論文 参考訳(メタデータ) (2021-07-14T08:01:30Z) - STRIDE along Spectrahedral Vertices for Solving Large-Scale Rank-One
Semidefinite Relaxations [27.353023427198806]
我々は、制約のない最適化問題(POP)の高次半定値プログラミング緩和を考察する。
POPから独立してSDPを解く既存のアプローチは、そのようなSDPの典型的な非エネルギー性のため、大きな問題にスケールできないか、あるいは緩やかな収束に苦しむことができない。
我々は SpecTrahedral vErtices (STRIDE) と呼ばれる新しいアルゴリズムフレームワークを提案する。
論文 参考訳(メタデータ) (2021-05-28T18:07:16Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳(メタデータ) (2020-08-23T20:36:49Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳(メタデータ) (2020-07-14T12:38:21Z) - Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave
Min-Max Problems with PL Condition [52.08417569774822]
本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
論文 参考訳(メタデータ) (2020-06-12T00:32:21Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。