A primal-dual aggregation algorithm for minimizing conditional value-at-risk in linear programs
A primal-dual aggregation algorithm for minimizing conditional value-at-risk in linear programs
复制标题
用于最小化线性规划中的条件风险价值的原始对偶聚合算法
DOI：
10.1007/s10589-014-9692-6
复制
发表时间：
2014
影响因子：
2.2
通讯作者：
E. Moreno
中科院分区：
文献类型：
--
作者：
Daniel G. Espinoza;E. Moreno
近年来，人们对连贯的风险度量越来越感兴趣，特别是对有条件风险价值（$$\mathrm {CVaR}$$ CVaR）。由于$$\mathrm {CVaR}$$ CVaR是一个凸函数，所以当我们希望最小化风险时，它适合作为优化问题的目标。在底层分布具有离散支持的情况下，这个问题可以表述为线性规划（LP）问题。对于更一般的分布，最近的技术，如样本平均近似法，允许通过解决一系列抽样问题来近似解决方案，尽管后一种方法可能需要大量的样本，当风险度量集中在潜在分布的尾部时。在本文中，我们提出了一个自动原始对偶聚合方案来精确解决这些具有非常多场景的特殊结构lp。该算法将场景和约束聚合在一起，以解决一个较小的问题，并利用其对偶变量的信息自动分解问题。我们将该算法与相关文献中发现的其他常见方法进行了比较，例如完整问题的改进公式、切割生成方案和商业软件中可用的其他特定于问题的方法。在组合和一般LP实例上进行了大量的计算实验。
Recent years have seen growing interest in coherent risk measures, especially in Conditional Value-at-Risk ($$\mathrm {CVaR}$$CVaR). Since $$\mathrm {CVaR}$$CVaR is a convex function, it is suitable as an objective for optimization problems when we desire to minimize risk. In the case that the underlying distribution has discrete support, this problem can be formulated as a linear programming (LP) problem. Over more general distributions, recent techniques, such as the sample average approximation method, allow to approximate the solution by solving a series of sampled problems, although the latter approach may require a large number of samples when the risk measures concentrate on the tail of the underlying distributions. In this paper we propose an automatic primal-dual aggregation scheme to exactly solve these special structured LPs with a very large number of scenarios. The algorithm aggregates scenarios and constraints in order to solve a smaller problem, which is automatically disaggregated using the information of its dual variables. We compare this algorithm with other common approaches found in related literature, such as an improved formulation of the full problem, cut-generation schemes and other problem-specific approaches available in commercial software. Extensive computational experiments are performed on portfolio and general LP instances.