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.


翻译:涉及随机环境下顺序决策的优化问题已在随机规划(SP),随机最优控制(SOC)和Markov决策过程(MDP)中研究。在本文中,我们主要集中于SP和SOC建模方法。在这些框架中,当所考虑的问题是凸的时,自然存在凸优化问题。顺序优化的经典方法基于动态规划。它存在所谓的“维度灾难”问题,即其计算复杂性随状态变量维数的增加呈指数级增加。解决凸多级随机问题上的最新进展基于动态规划方程中成本的割平面逼近。该文主要讨论在动态环境下的割平面类型算法。我们还讨论了应用于多级随机优化问题的随机逼近类型方法。计算复杂性方面,这两种方法似乎是互补的。割平面类型方法可以处理具有大量级别但相对较少状态(决策)变量的多级别问题。另一方面,随机逼近类型的方法只能处理级数较少但决策变量较多的问题。

0
下载
关闭预览

相关内容

南大《优化方法 (Optimization Methods》课程,推荐!
专知会员服务
77+阅读 · 2022年4月3日
因果推断,Causal Inference:The Mixtape
专知会员服务
103+阅读 · 2021年8月27日
专知会员服务
50+阅读 · 2020年12月14日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
vae 相关论文 表示学习 1
CreateAMind
12+阅读 · 2018年9月6日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【论文】图上的表示学习综述
机器学习研究会
14+阅读 · 2017年9月24日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Arxiv
0+阅读 · 2023年5月17日
Arxiv
10+阅读 · 2021年11月3日
VIP会员
相关VIP内容
相关资讯
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Top
微信扫码咨询专知VIP会员