A Stochastic Primal-Dual Method for Optimization with Conditional Value at Risk Constraints
A Stochastic Primal-Dual Method for Optimization with Conditional Value at Risk Constraints
复制标题
条件风险价值约束下的随机原始对偶优化方法
DOI：
10.1007/s10957-021-01888-x
复制
发表时间：
2021
影响因子：
1.9
通讯作者：
Bose, Subhonmesh
中科院分区：
文献类型：
--
作者：
Madavan, Avinash N.;Bose, Subhonmesh
我们研究了一种一阶原始-对偶次梯度方法来优化风险约束的风险惩罚优化问题，其中风险是通过流行的条件风险价值(CVaR)度量来建模的。该算法以在线的方式处理来自潜在不确定性的独立且同分布的样本，并在恒定步长的迭代中产生一个-近似可行且-近似最优的点，该点随CVaR的风险参数可调而增加。我们使用我们的界找到了最优的步长，并精确地表征了风险规避的计算成本，如中的增长所揭示的那样。我们提出的算法对一个典型的原始-对偶随机次梯度算法进行了简单的修改。通过这一温和的变化，我们的分析出人意料地避免了许多先前工作中假设的对偶变量施加先验界或复杂的自适应界方案来执行算法的需要。我们还在样本复杂性方面与文献中得出的机会受限程序的样本复杂性进行了有趣的相似之处，这些程序具有非常不同的解决方案架构。
We study a first-order primal-dual subgradient method to optimize risk-constrained risk-penalized optimization problems, where risk is modeled via the popular conditional value at risk (CVaR) measure. The algorithm processes independent and identically distributed samples from the underlying uncertainty in an online fashion and produces an-approximately feasible and-approximately optimal point withinKiterations with constant step-size, whereincreases with tunable risk-parameters of CVaR. We find optimized step sizes using our bounds and precisely characterize the computational cost of risk aversion as revealed by the growth in. Our proposed algorithm makes a simple modification to a typical primal-dual stochastic subgradient algorithm. With this mild change, our analysis surprisingly obviates the need to impose a priori bounds or complex adaptive bounding schemes for dual variables to execute the algorithm as assumed in many prior works. We also draw interesting parallels in sample complexity with that for chance-constrained programs derived in the literature with a very different solution architecture.
登录
查看更多内容
DOI：
10.1137/16m1058492
发表时间：
2015-12
期刊：
SIAM J. Control. Optim.
影响因子：
--
作者：
Christopher W. Miller;Insoon Yang
通讯作者：
Christopher W. Miller;Insoon Yang
具有不可微成本函数的随机优化问题及其在随机规划中的应用
DOI：
--
发表时间：
1972
期刊：
IEEE Conference on Decision and Control
影响因子：
--
作者：
D. Bertsekas
通讯作者：
D. Bertsekas
DOI：
--
发表时间：
2019
期刊：
影响因子：
--
作者：
A. S. Bedi;Alec Koppel;K. Rajawat
通讯作者：
K. Rajawat
DOI：
10.1137/18m1229869
发表时间：
2018-02
期刊：
SIAM J. Optim.
影响因子：
--
作者：
Yangyang Xu
通讯作者：
Yangyang Xu
影响因子：
6.8
作者：
Michael J. Hadjiyiannis;P. Goulart;D. Kuhn
通讯作者：
Michael J. Hadjiyiannis;P. Goulart;D. Kuhn