Linear Programming Formulation of CVaR Optimization
Summary
The document asks how a Monte Carlo approximation of conditional value at risk can be expressed as a linear optimization problem. The approximation uses a threshold variable and the positive part of each scenario's loss beyond that threshold. Introducing one auxiliary variable per scenario allows that positive-part term to be represented through nonnegative and lower-bound constraints, while minimizing their sum with the threshold term.
The answer suspects that a mismatch between the number of scenarios and the auxiliary-variable index range is a typo, and that the summation should use the same scenario count. It explains that the constrained formulation works because minimization pushes each auxiliary variable to the smallest value satisfying both constraints, reproducing the positive part. The threshold is optimized too and corresponds to the VaR level at the solution. The exchange gives a conceptual explanation rather than a full derivation or implementation, and it does not discuss sampling error or portfolio constraints beyond the stated formulation.
Key ideas
- CVaR scenario losses can be represented with auxiliary variables for their positive parts.
- Each auxiliary variable is constrained to be nonnegative and to exceed the scenario loss relative to the threshold.
- Minimizing the auxiliary-variable sum makes each variable take the required positive-part value.
- The threshold is optimized jointly and corresponds to the VaR level at the optimum.
- The differing scenario index ranges in the question are likely a typographical error.
Tags
Full text
# Question on Rockafellar's Paper for optimisation of CVaR
# Question on Rockafellar's Paper for optimisation of CVaR
In Rockafellar and Uryasev's Paper about CVaR Optimisation they showed in Equation (17) that using Monte-Carlo-Simulation one can use $$\tilde F_{\beta}(x,\alpha)=\alpha+\frac{1}{q(1-\beta)}\sum_{k=1}^qmax(-x^Ty_k-\alpha,0)$$ to approximate the CVaR approximation, where $\alpha$ denotes the percentile of $\beta-$CVaR, $x\in\Bbb R^n$ the portfolio and $y_k$ the return in k-th scenario. In the following paragraph he introduced some auxiliary real variable $u_k$ for $k=1,...,r$ and claim it is equivalent to minimising the linear expression $$\alpha+\frac{1}{q(1-\beta)}\sum_{k=1}^qu_k$$ subject to $u_k\geq0$ and $x^Ty_k+\alpha+u_k\geq0$.
Question:
- Why is the indices of $u_k$ running from 1 to r and not to q?
- Why are the both problem equivalent? I can rewrite the last condition in the second problem as $u_k\geq-x^Ty_k-\alpha$ and together with $u_k\geq0$ I am allowing $-x^Ty_k-\alpha\leq0$ in the sum, which has value 0 in the first problem with $max(-x^Ty_k-\alpha,0)$ in the summand.
## Answer by John (score 5, accepted)
https://quant.stackexchange.com/a/34587
On 1, I suspect that is a typo and that the second formula should sum to r.
On 2, that is applying well-known techniques in how to handle piece-wise linear functions in an optimizer. For instance, see page 4 of these lecture notes. It's basically doing the same thing with a few additional complications. In CVaR optimization, there are more things to sum and also $\alpha$ is also part of the optimization (following the optimization, $\alpha$ should equal the Value-at-Risk).
Finally, there's an issue with your math: $-x^Ty_k-\alpha\leq0$ only follows if $u_k$ is always $0$.Shown in full with attribution under the source's licence. Licence: CC BY-SA 4.0 (Stack Exchange)
This summary was written by Stratmill's research agent from the original; it is not a copy of the source.