Lecture Notes on Risk Optimization

Giovanni Pantuso
Department of Mathematical Sciences, University of Copen-
hagen
Email address: gp@[Link]
 2010 Mathematics Subject Classification. Primary

Abstract.

Last updated on November 17, 2025

 Contents

Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
Chapter 1. Risk in Optimization Problems . . . . . . . . . . . . . . . . . . . . 1
1.1. Illustrative examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2. Common approaches to optimization under uncertainty . . . . . . 5
1.3. Measures of Risk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4. Coherent measures of risk . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.5. Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Chapter 2. Stochastic Dominance . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1. Utility Theory: A Brief Overview . . . . . . . . . . . . . . . . . . . . . . 21
2.2. Stochastic Orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3. Optimization with FSD constraints . . . . . . . . . . . . . . . . . . . . 29
2.4. Optimization with SSD constraints . . . . . . . . . . . . . . . . . . . . . 32
2.5. Considering Losses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Chapter 3. Probabilistic Programming . . . . . . . . . . . . . . . . . . . . . . . 39
3.1. Chance Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2. Maximization of Probability . . . . . . . . . . . . . . . . . . . . . . . . . 45
Chapter 4. Conditional Value at Risk . . . . . . . . . . . . . . . . . . . . . . . . 47
4.1. CVaR for continuous distributions . . . . . . . . . . . . . . . . . . . . . . 49
4.2. CVaR for general distributions . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.3. Coherence of CVaR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.4. Optimization of CVaR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
Appendix A. Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
A.1. Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
A.2. Convex Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

v
 Preface

These lecture notes consist of a small number of essays on topics related to

optimization under uncertainty. In particular, they take the perspective of a
decision maker who wants make safe decisions as to protect against excessively
negative outcomes.
The topic of risk management has interested generations of economists and
mathematicians, in particular insurance mathematicians. There is a vast and
diverse body of literature. Starting already with the work of von Neumann
and Morgenstern on utility theory, it emerged how risk management has a
strong optimization connotation. A decision problem under uncertainty was
posed as the problem of maximing the expectation of utility function which
measures the satisfaction generated by choices with uncertain rewards. Later,
the optimization character of risk management was even more evident with
the work of Markowitz on portfolio optimizatiom. In his work, a decision
problem under uncertainty was posed as the problem of trading-off risk and
reward. That is, as the problem of maximizing rewards while constraining risk
or, alternatively, as minimizaing risk while meeting a given reward goal. Risk
and reward had a specific mathematical shapes: variance and mean.
It was in the 1900s and 2000s that risk optimization started gaining mo-
mentum, mainly thanks to the advances in convex optimization techniques.
The optimization community started developing frameworks for including risk
measurements, or more in general, risk concerns, into optimization problems.
We obtained ways to optimize while ensuring stochastic dominance relationship
– a partial order on spaces of random variables – while ensuring probabilities of
compliance, and while minimizing tail risk. Several measures of risk were pro-
duced with the goal of improving the limitations of Markowitz’s variance. This
proliferation of alternative ways of measuring risk dictated the establishment
of principles which determine what a good measure of risk is. These princeples
were formalized into a collection of axioms which describe the characteristics
of a good (called “coherent”) measure of risk.
Today, risk analysis and statistics (of the extremes) are well-consolidated
topics, especially in insurance mathematics. However, unfortunately, the same

vii
viii PREFACE

does not apply to risk optimization. The literature is sparse and varies signif-
icantly in terms of expected audience, focus, and quality of exposition. The
author of these notes is not aware of textbooks or collections of material de-
veloped for pedagogical purposes.
The present notes were/are developed for a course named Risk Optimiza-
tion at the University of Copenhagen. They represent an attempt of the author
to collect the most important results and illustrate them in a coherent manner,
with homogeneous notation and assumptions, and with key proofs worked out
in a clear manner. The author makes no secret that writing this document
has been and is (the document is continuously updated) perhaps the most
challenging teaching initiative he has undertaken. The variety of the material
found, the absence of a guiding textbook, the cryptic way in which some top-
ics are presented in the literature required significant effort. The majority of
the proofs provided in these notes have been completely rewritten to facilitate
comprehension and consistence with the notation and assumptions or, in many
cases, developed from scratch when missing in the literature.
I am immensely grateful to the students who, reading this document, will
take the time to report imprecisions, corrections, errors, suggestions. I am
immensely grateful to the students who have done it already.
 CHAPTER 1

Risk in Optimization Problems

In several areas of applied mathematics, we face the problem of determin-

ing a best decision (i.e., a design, an estimate, or model) in the presence of
uncertainty about the values of key parameters and data in the problem. The
uncertainty may be determined by different factors. These include, for exam-
ple, the human inhability to predict the future, incomplete knowledge about
a system, and inaccuracy of approximations. One might hope that histori-
cal observations about the uncertainties can inform us and ideally eliminate
the uncertainty. However, despite the availability of big data, this hope is
rarely fulfilled. Real-world data sets tend to be noisy, biased, corrupted, or
simply insufficiently large. It is therefore prudent to optimize decisions while
accounting conservatively for the uncertainty. Even in situations where we
have a fair understanding of the uncertainty, our desire to avoid exceptionally
“bad” outcomes motivates conservativeness in decision making and modeling.
Various fields have approached decision making under uncertainty some-
what differently. Nevertheless, there emerge overarching themes. Primarily,
the need to capture risk-averseness in mathematical models of decisions. The
concept of risk measures provides a unifying mathematical framework.
The canonical decision problem involves a quantity of interest given by
a function f (x, ξ), which depends on a parameter ξ and a decision (control)
x. For example, f (x, ξ) might quantify the performance of an engineering
system designed according to our decision x, given an environmental condition
represented by ξ. In supervised learning, f (x, ξ) might specify the prediction
error of a statistical model designed according to x, given feature and label
data ξ. Without fully knowing ξ, the problem is to determine a decision x
such that f (x, ξ) is minimized or, alternatively, f (x, ξ) does not exceed a given
threshold. That is, we assume, unless otherwise specified, that f models a loss,
that is something we wish to keep as low as possible.
However, when ξ is unsettled – as in the examples above – the problem is
ill-posed. Formally, we model x as an element of a suitable subset X of Rn and

1
2 1. RISK IN OPTIMIZATION PROBLEMS

ξ as a random variable1 on a given probability space (Ω, F, P) with values in

RN – note the use of bold font to distinguish from its realizations ξ, for which
we use plain font. As a consequence x 7→ f (x, ξ) is itself a random variable.
What does it mean to minimize the value of a random variable? What does it
mean that a random variable should not exceed a threshold?
There are several ways to proceed. One can estimate the value of ξ and
use that value in decision making. Alternatively, if there is a set Ξ of possible
values of ξ, then one may consider the quantity of interest in the worst case
across these values, i.e., supξ∈Ξ f (x, ξ). Yet another, possibility is to model
the uncertainty associated with ξ using a probability distribution. This brings
in the vast and sophisticated tools of probability theory and statistics. In
assessing a decision x, one can, for example, leverage the expected value of
f (x, ·) computed with respect to the adopted probability distribution. Thus,
the problem becomes to find a decision that is satisfactory on average. Risk
measures capture all these possibilities and many more. Through choices of
probability distributions, risk measures allow us to accurately choose accord-
ing to different risk attitudes. When restricted suitably to the class of coherent
measures of risk, they also exhibit theoretically and computationally advanta-
geous properties. In particular, desirable properties of f (x, ξ) in x commonly
carry over to the resulting optimization problem. Risk measures originated
in financial engineering as an approach to quantify the reserves banks, insur-
ance companies, and other financial institutions need to cover potential future
losses. Nevertheless, risk measures are applicable and are applied well beyond
financial engineering to, for example, operations management, reliability anal-
ysis, engineering design, defense planning, statistics, and machine learning. In
these lectures we take an application-agnostic perspective.
In what follows we first introduce a number of examples of optimization
under uncertainty, then discuss different approaches to decision-making under
uncertainty.

1.1. Illustrative examples

Example 1.1. (An abstract numerical example) Assume that the quan-
tity of interest is modeled by
f (x, ξ) = (ξ − 2/3)x − 1/3

1Formally, a random variable is an F/T -measurable function ξ : (Ω, F) → (S, T ) where

(Ω, F) and (S, T ) are measurable spaces. Once this is stipulated, to avoid technical distrac-
tion, this level of formalism will be often omitted and unnecessary in what follows.
 1.1. ILLUSTRATIVE EXAMPLES 3

Assume the solution space is defined by X = {−1, 1}. That is, there are
only two possible decisions. Assume further that ξ ∼ T(0, 0, 2), where
T(0, 0, 2) denotes the triangular distribution on [0, 2] with mode at 0.
Therefore, we are essentially faced with the choice between two random
variables, f (−1, ξ) and f (1, ξ). Using the triangular distribution of ξ we
can obtain the probability density functions of f (−1, ξ) and f (−1, ξ).
These are depicted in Figure 1.1.

f (1, ξ) f (−1, ξ)

−5/3 −1 1/3 1

Figure 1.1. Density of the random variable f (−1, ξ) and

f (1, ξ).
Which decision is better, x = −1 or x = 1? If we look at the expected
values of f (−1, ξ) and f (1, ξ), they are not of much help: both of them
are −1/3. But still, the random variables are very different. With f (1, ξ)
we can incurr a loss as high as 1. With f (−1, ξ) we can incurr a loss
as high as 1/3. Thus, from a worst-case perspective, f (−1, ξ) appears
better.

Example 1.2 (Statistics). Some problems in statistics and machine

learning can be viewed as attempting to make a decision under uncer-
tainty. In supervised learning, the goal is to find a statistical model that
best predicts an unknown output based on a given input. Typically, a
statistical model is specified by a vector c = (c0 , . . . , cn ) of coefficients,
with the resulting prediction being g(c, ξ) for input ξ = (ξ1 , . . . , ξn ) ∈
Rn . If the statistical model is affine, then
Xn
g(c, ξ) = c0 + ci ξ i
i=1

(The model g(c, ξ) may of course take many other forms, possibly utiliz-
ing neural networks). Given an input-output pair (y, ξ), we would like
the model’s prediction g(c, ξ) to be close in some sense to the actual
output value y.
4 1. RISK IN OPTIMIZATION PROBLEMS

In regression analysis, the output quantity is a scalar and “close” is

commonly quantified using
f ((y, ξ), c) = (y − g(x, ξ))2
or
f ((y, ξ), c) = |y − g(x, ξ)|
In a k-class classification problem, the output y ∈ {1, . . . , k} specifies a
class and the statistical model g(c, ξ) = (g1 (c, ξ), . . . , gk (c, ξ)) produces
a k-dimensional vector of probabilities representing the likelihood that
input ξ corresponds to the various classes. In predicting y from ξ, the
cross-entropy of g(c, ξ) relative to a probability mass function concen-
trated at y ∈ {1, . . . , k} becomes the quantity of interest
f ((y, ξ), c) = − log gy (c, ξ)
Regardless of the specific details, when selecting a statistical model we
are uncertain about the input-output pair (y, ξ) for which the model
should be accurate. In fact, we probably would like the statistical model
to make accurate predictions for many input-output pairs. Consequently,
we are faced with the problem of selecting c, under uncertainty about
(y, ξ), such that a quantity of interest f ((y, ξ), c) is “optimized”.

Example 1.3 (Support Vector Machine). In binary classification, we

seek to predict an output ν ∈ {−1, 1} from an input ξ using a statistical
model g(c, ξ), where c is a vector of coefficients. That is, we are interested
in predicting the sign from ξ. Support vector machines achieve this by
considering the so-called hinge loss which is defined as follows
h(c, (ξ, ν)) = max{0, 1 − νg(c, ξ)
as a quantity of interest. The hinge loss is, actually, a surrogate for the
actual measure of prediction accuracy we are interested in. That is, our
actual goal is to minimize the loss function
(
0, if νg(c, ξ) > 0
ℓ0−1 =
1, if νg(c, ξ ≤ 0
That is, if the predicted sign matches the true sign (νg(c, ξ) > 0), the loss
function counts a zero, otherwise it counts a 1. However, the ℓ0−1 func-
tion is non-convex and discontinuous and makes optimization harder.
 1.2. COMMON APPROACHES TO OPTIMIZATION UNDER UNCERTAINTY 5

For this reason one typically uses the hinge loss, which is instead con-
vex. The hinge loss takes value 1 − νg(c, ξ) if νg(c, ξ) < 1, meaning
that the sample is either misclassified (νg(c, ξ) ≤) or correctly classified
with low confidence (0 < νg(c, ξ) < 1). Instead, it takes value 0 if the
sample is correctly classified with high confidence (νg(c, ξ) > 1).
Another concern in this setting is fairness. That is, when making mis-
takes, does the statistical model g(c, ·) exhibit a bias such as when being
applied with an input ξ corresponding to an under-represented group?
To reduce bias in the statistical model, we may consider a secondary
quantity of interest
f2 (c, (ξ, ζ)) = (ζ − ζ̄)g(c, ξ)
where ζ is an additional input representing sensitive attributes (e.g.,
gender, race, ethnicity, age) and ζ̄ is the average across a population
of attributes. The secondary quantity of interest can be used to quan-
tify the covariance between attributes and predictions produced by the
statistical model and thus serves as a metric of fairness.
Hence, the prediction technique known as Support Vector Machine con-
sists essentially in solving an optimization problem under uncertainty
with the goal of minimizing one or more loss functions.

Example 1.4 (Newsvendor Problem).

1.2. Common approaches to optimization under uncertainty

In this section we take a tour of some of the most frequent approaches to
optimization under uncertainty. Consider an classical optimization problem.
(1.1) min f (x)
x∈X
n
where X = {x ∈ R |fi (x) ≤ 0, i = 1, . . . , m}. Now assume uncertainty af-
fects the objective function or the constraints, or both. That is, the objective
function becomes
f (x, ξ)
where ξ is a random variable with values in RN . Likewise, the constraints take
the form
fi (x, ξ) ≤ 0, i = 1, . . . , m
The problem becomes ill-defined. What does it mean to minimize the random
variable f (x, ξ)? What does it mean that the random variables fi (x, ξ), i =
1, . . . , m should be nonnegative?
6 1. RISK IN OPTIMIZATION PROBLEMS

Let us see a number of different ways to approach this problem.

1.2.1. Using Predictions. A common approach to deal with uncertainty
is the following. A single realization ξ¯ of ξ is identified as furnishing a best
estimate of the unknown information. Then, one can solve the deterministic
problem
(1.2) ¯
min f (x, ξ)
x∈X (ξ̄)

where
¯ ≤ 0, i = 1, . . . , m}
X (ξ) = {x ∈ Rn |fi (x, ξ)
Essentially, this serves as a way of avoiding the issue. Although this ap-
proach might seem justifiable when the uncertainty is minor and well concen-
trated around ξ, ¯ it is otherwise subject to serious criticism. A solution x̄ to
(1.2) could lead, when the future state turns out to be some ξ other than ξ, ¯
to a constraint value fi (x̄, ξ) > 0, or a cost f (x̄, ξ) disagreeably higher than
¯ No provision has been made for the risk inherent in
the expected f (x̄, ξ).
these eventualities. Simply put, a decision x̄ coming out of (1.2) fails to hedge
against the uncertainty and thus “puts all the eggs in one basket”. It does not
incorporate any appraisal of how harmful an ultimate constraint violation or
cost overrun might be to the application being modeled.
The weakness in this response to uncertainty can also be appreciated from
another angle. If the parameters ξ of the functions involved are continuous
random variables, the behavior of solutions to (1.2) (an optimization problem
depending on ξ¯ as a parameter) could be very poor. In fact, even in linear
programming it is well understood that tiny changes in coefficients can pro-
duce big changes, even jumps, in solutions. The dangers of not hedging could
be seriously compounded by such instability. Hence, relying solely on a fore-
cast point is, in general, a very bad idea, no matter how good our prediction
machinery is.
1.2.2. Worst-Case Analysis. Another familiar approach is to rely on
determining the worst that might happen. That is, we solve the following
problem
(1.3) min{ess sup f (x, ξ)| ess sup fi (x, ξ) ≤ 0, i = 1, . . . , m}
ξ∈Ξ ξ∈Ξ

where Ξ is the support of ξ.

This very conservative formulation aims at ensuring that the constraints
will be satisfied, no matter what the future brings. It devotes attention only
to the worst possible outcomes, even if they are associated only with highly
unlikely future states. Assessment of performance in more likely circumstances
 1.2. COMMON APPROACHES TO OPTIMIZATION UNDER UNCERTAINTY 7

is not addressed. The goal is to eliminate all risk. However, there is a price
for that. The feasible set might be very small, possibly empty. Nonetheless a
strong attraction of this formulation is that the potential trouble over specify-
ing a probability distribution for ξ is effectively bypassed.
1.2.3. Using Expectations. Still another idea of long standing, is to
utilize the expectations of the random variables x 7→ fi (x, ξ) as numbers that
depend only on x. That is, one could consider the problem
(1.4) min{E [f (x, ξ)] |E [fi (x, ξ)] ≤ 0, i = 1, . . . , m}
Using expectations in the constraints seems generally ridiculous. If a constraint
corresponded to the safety of a structure, for example, or the avoidance of
bankruptcy, who would be satisfied with it only being fulfilled on the average?
As far as the objective is concerned, this is, instead a normal way of pro-
ceeding, and it has a long history. Expectations are primarily suitable for
situations where the interest lies in long-range operation, and where stochastic
ups and downs can safely average out. This can, in turn, give rise to a variety
of models.
When all decisions are made at once, before the realization of the un-
certainty, and all randomness is confined in the coefficients of the objective
function we obtain the following model
(1.5) min{E [f (x, ξ)] |fi (x) ≤ 0, i = 1, . . . , m}
A very broad class of problems can be modeled by linear objective functions.
That is, given a random variable ξ with values in Rn , we obtain
min{E ξ ⊤ x |fi (x) ≤ 0, i = 1, . . . , m}
 
(1.6)
However, since the x is independent of the random experiment, we can rewrite
(1.7) min{E [ξ]⊤ x|fi (x) ≤ 0, i = 1, . . . , m}
Problem (1.7) is now a deterministic optimization problem.
Let us return briefly to the case of uncertainty-affected constraints. We
will now see that also in this case we may obtain expectation-based problems.
Consider again problem (1.4), but assume that the uncertainty affects only the
right-hand side coefficients of the constraints. That is, where the constraints
are of the form
(1.8) min{f (x)|fi (x) = ξi (ω) a.s. , i = 1, . . . , m}
with ξi ∈ R, i = 1, . . . , m. We consider, without loss of generality, equality
constraints. The same reasoning extends, with small adjustments, to inequality
constraints. Notice the slight change of notation in stressing the dependence
of ξ on ω. This will slightly facilitate our discussion. The constraints have
8 1. RISK IN OPTIMIZATION PROBLEMS

to hold for P-almost all ω ∈ Ω. However, the constraints are ill-defined. The
right-hand sides x 7→ fi (x) are constants. Requiring constants to be equal to
random variables a.s. does not make sense (unless the random variable is itself
constant w.p.1). Hence, we could consider the following modification
(1.9) fi (x) + wi+ (ω) − wi− (ω) = ξi (ω) a.s., i = 1, . . . , m
Here we introduce additional F-measurable decision variables wi+ (ω) and wi− (ω)
with values in R≥0 which can adapt to the realization of ω and ensure that,
for P-almost every ω, the constraints are satisfied. Now the constraints are
meaningful. Variables wi+ (ω) and wi− (ω) can be seen as “corrections” to the
effect fi (x) of an a-priori decision x. In the stochastic programming literature,
the wi+ (ω) and wi− (ω) variables are called second-stage variables while x are
called first-stage variables.
It remains however to clarify how to include these new variables in the
objective function. A common trick is to penalize the new variables with
some costs qi+ and qi− . We assume these are deterministic, but they may as
well be random variables – nothing would change except some mathematical
properties of the problem which are outside the scope of our discussion. We
obtain
( " m #
X
(qi+ )⊤ wi+ (ω) + (qi− )⊤ wi− (ω)


(1.10) min
+ −
f (x) + E
x,w ,w
i=1
)
|fi (x) + wi+ (ω) − wi− (ω) = ξi (ω) a.s., i = 1, . . . , m

We have hereby informally introduced a rather broad class of problems known

as two-stage stochastic programs with recourse that generalize (1.7). In these
problems, decisions are divided into first- and second-stage decisions, with
the former being fixed before any uncertainty has materialized, and the latter
being adaptable to the future state of the world. A more general model is
( )
⊤
 
min f (x) + E q(ω) y(ω) W (ω)y(ω) + T (ω)x = h(ω) a.s.
x∈X ,y∈Y

Here y : Ω → Rn2 are F-measurable decision variables and the uncertainty

potentially affects all coefficients of the a.s. (second-stage) constraints, as
well as the cost of the second-stage variables y. Here, W : Ω → Rm×n2 and
T : Ω → Rm×n are random matrices while h : Ω → Rm and q : Ω → Rn2
are random vectors. There is a rich theoretical background behind problem
(1.11) which is beyond the scope of these lectures. In general, problems of this
type are well suited for situation where the interest lies in long-range costs over
 1.3. MEASURES OF RISK 9

repeated implementations of the solutions proposed and where the extremes do

not matter much. To the contrary, many applications have a distinctly short-
run focus with serious risks in the foreground. In that case, using expectations
in the objective is as questionable as using expectations in the constraints.
1.2.4. Probability of Compliance. A popular alternative to address
the drawback of the the worst-case approach is to explicitly handle the proba-
bility of compliance. That is, to require that require that the desired inequal-
ities are hold at least with a specified probability. We obtain the so called
probabilistic constraints (or chance constraints). The resulting probabilistic
programming problems are of the form
min{f (x)|P (fi (x, ξ) ≤ 0) ≥ αi , i = 1, . . . , m}
x∈X

Alternatively, we may wish to maximize the probability of compliance (mini-

mizing the probability of not complying). We obtain
max P (fi (x, ξ) ≤ 0, i = 1, . . . , m)
x∈X

We will see these problems into more details in Chapter 3.

1.2.5. Risk-Reward Optimization. Markowitz [Mar52] was among the
first who recognized the optimization aspects of risk management. In partic-
ular, he identified risk with volatility (variance) and highlighted the conflict
between risk and reward. The problems that Markowitz had in mind where fi-
nancial portfolio optimization problems. Therefore, in this section we consider
random variables which model payoffs, or things we want more of, instead of
losses.
Markowitz problem can be simply stated as follows
min σ 2 (X(x, ξ))|E [X(x, ξ)] ≥ r0

x∈X

where X(x, ξ) is the capital yielded by an investment x in risky assets with ran-
dom returns ξ and σ 2 : L2 (Ω, F, P) → R is the variance of the capital. The set
X contains deterministic constraints stating for example whether short-selling
is allowed. This problem has been particularly appealing for its simplicity and
ease of solution. When X is convex and X is linear in x, the problem is convex
and thus easily tractable.

1.3. Measures of Risk

Moving beyond financial applications, from a more general point of view,
Markowitz formalized the idea that decisions under uncertainty may be eval-
uated in terms of trade-offs between risk and reward. Specifically, he identi-
fied risk with volatility and reward with expectations. Although the original
10 1. RISK IN OPTIMIZATION PROBLEMS

Markowitz model is still widely used today, it has been acknowledged that
variance as a measure of risk does not always produce adequate estimates of
risk exposure. In particular, variance has two central limitations. First, it pe-
nalizes equally deviations above and below the mean, that is the gains and the
losses. Second, variance is ineffective for measuring the risk of low probability
events. The acknowlegnement of these limitations led to the development of a
variety of measures of risk.
Before formally introducing the concept of measure of risk a short comment
on the notation is required. Consistently with the rest of this chapter, and
unless otherwise specified, we consider random variables that model losses,
that is, things we want less of. This is stressed by the notation L used for
random variables. Their realizations are denoted by plain font, so that L is
a realization of L. It should be understood that, in our context, the random
variables of interest are mathematical objects that depend on our decisions x
and on an random set of parameters ξ. That is, our random variable L is
determined by x 7→ l(x, ξ) where l is a function of x and ξ. To avoid overly
complicated notation, we often suppress the dependence of L on x and ξ or
even on the underlying probability space (Ω, F, P). However, in some occasions
we will use l(ω) in place of l(x, ξ(ω)) when the value of x is supposed given
and we require stressing the dependence on the outcome ω ∈ Ω.
We are now ready to formally introduce risk measures.

Definition 1.1 (Risk Measure). A measure of risk (or risk measure) is

a functional ρ : L → R, where L is a suitable space of random variables.
Therefore, a risk measure ρ assigns a random variable L a number ρ (L)
as a quantification of its risk.

We have already implicitly already introduced some risk measures in Sec-

tion 1.2. The prediction approach to optimization under uncertainty is equiva-
lent to defining a risk measure ρ (L) = L̄. This risk measure quantifies risk as
the loss incurred in a specific realization L̄ of the uncertainty. The worst-case
approach is equivalent to defining a risk measure ρ (L) = ess sup L. This risk
measure quantifies risk as the largest possible loss. Similarly, the expectation-
based approach is equivalent to defining a risk measure ρ (L) = E [L]. This
risk measure quantifies risk as the expected loss. Finally, as commented earlier,
Markowitz measured risk using variance, so that ρ (L) = σ 2 (L).
Many other risk measures have been proposed with the goal of address
the weaknesses of variance. They are based on the principle of measuring the
“undesired” variation of the random outcome. Markowitz himself proposed
 1.3. MEASURES OF RISK 11

the use of semivariance

2
(L) = E (L − E [L])2+ = ∥(L − E [L])+ ∥22
 
ρ (L) = σ−
1/p
where ∥·∥p = E [|·|p ] is the ℓp -norm in Lp and (a)+ = max{0, a}. So the
semivariance succesfully captures only the variation of the losses above the
mean and ignores the downward – desired – variation. When L is a discrete
random variable with realizations L1 , . . . , LK and probabilities π1 , . . . , πK , the
semivariance takes the form
K
X
2
σ− (L) = πk (Lk − E [L])2+
k=1

This can be implemented as follows

(1.11) µk ≥ L k − m k = 1, . . . , K
(1.12) µk ≥ 0 k = 1, . . . , K
K
X
(1.13) m= π k Lk
k=1
K
X
2
(1.14) σ− = πk µ2k
k=1

A similar measure of risk is the mean semideviation

ρ (L) = E [(L − E [L])+ ]
Also in this case, when L is discrete it can be implemented as follows
(1.15) µk ≥ Lk − m k = 1, . . . , K
(1.16) µk ≥ 0 k = 1, . . . , K
K
X
(1.17) m= πk Lk
k=1
K
X
(1.18) ρ= πk µ k
k=1

Hence, the mean semideviation can be implemented using linear constraints.

Both the semivariance and the mean semideviation associate, according to
their definitions, (asymmetric) risk with L falling above its expected value.
However, in many applications it is preferable to view the risk of L as its
deviation with respect to a certain predefined benchmark level τ . We obtain a
12 1. RISK IN OPTIMIZATION PROBLEMS

new measure of risk called the expected regret (or mean above-target deviation)
and defined as
ρ (L) = ER(L) = E [(L − τ )+ ]
When L is a discrete random variable, ER becomes
µk ≥ L k − τ k = 1, . . . , K
µk ≥ 0 k = 1, . . . , K
K
X
ρ= π k µk
k=1

The measures introduced above can be seen as a special case of a more

general measure of risk called the Upper Partial Moment (or Lower Partial
Moment for random variables modeling profits) and defined as
ρ (L) = U P Mp (L, τ ) = E [(L − τ )p+ ]
for p ≥ 0 and τ ∈ R. Constraining risk, measured by an upper partial moment,
can be expressed as
U P Mp (L, τ ) ≤ R
for some target τ ∈ R and upper bound 0 < R ∈ R. For τ = E [L] and
p = 1 and p = 2 we recover the mean semideviation and the semivariance,
respectively. For p = 1 and a given τ we recover the expected regret. Another
special case of Upper Partial Moment is obtained, for a given τ , by setting
p = 2. The corresponding measure is called a semideviation above a fixed
target τ . Finally, observe that for p = 0, U P M0 can be understood as the
probability of loss.
This concept is strictly related to chance constraints and to a risk measure
called Value-at-Risk (VaR). It is one of the most widely known and applied risk
measures in the area of financial risk management. Assume the distribution
function of our loss random variable L is known and denoted by FL . That is,
for given x,
FL (z) = P ({ω ∈ Ω|L(ω) ≤ z})
We define the VaR of L at conficence level α ∈ (0, 1) as follows.

Definition 1.2 (Value-at-Risk). Let L be a random variable with dis-

tribution function FL . For α ∈ (0, 1) we define the Value-at-Risk at
confidence level α as
(1.19) VaRα (L) = min{z|FL (z) ≥ α}
 1.3. MEASURES OF RISK 13

That is, we understand VaR as the smallest value z for which the probability
of the interval (−∞, z] is at least α. In other words, knowing the value of
VaRα (L) tells us that there is a 95% probability that the loss will not be
higher than VaRα (L). So there is a 5% probability we could lose more than
that.
Recall that, given x, for any 0 < α < 1, z ∈ R is an α-quantile if
P ({ω ∈ Ω|L(ω) < z}) ≤ α ≤ P ({ω ∈ Ω|L(ω) ≤ z}) = FL (z)
The set of α-quantiles is a non-empty closed interval for every 0 < α < 1.
Thus, by definition, VaRα (L) is a lower α-quantile of the random variable L.
VaR is a relatively simple risk management notion. The intuition behind
the α-quantile of a loss distribution has a clear interpretation: how much you
may lose with a certain confidence level. VaR is a single number measuring risk,
defined by some specified confidence level such as 0.95. Two distributions can
be ranked by comparing their VaR for the same confidence level. Specifying
VaR for all confidence levels in (0, 1) completely defines the distribution. Fur-
thermore, VaR is superior to, for example, the variance or standard deviation
since it focuses on the undesired portion of the loss distribution. In addition,
one of the main properties of VaR is the stability of estimation procedures. VaR
disregards the tail of the distribution. As such, it is not affected by very high
tail losses, which are usually difficult to measure. These advantages made VaR
extremely popular in finance and engineering.
These nice properties of VaR are however counterbalanced by its (lack of)
mathematical properties. As a function of the confidence level α, for discrete
distributions, VaR is a non-convex, discontinuous function. That is, a small
change in α might lead to a significant increase in VaR. VaR does not account
for properties of the distribution beyond the confidence level. To adequately
estimate risk in the tail, one may need to calculate VaR at different confidence
levels. The fact that VaR disregards the tail of the distribution may lead
to unintentional bearing of high risks. Risk control using VaR may lead to
undesirable results for skewed distributions.
VaR constraints are closely related to chance constraints. Recalling the
definition of VaR in (1.19), we have
VaRα (L) ≤ z ⇐⇒ P ({ω ∈ Ω|L(ω) ≤ z}) ≥ α
Recalling that in optimization problems L is a function of the decision vari-
ables, that is l(x, ξ(ω)), we have
P (l(x, ξ(ω)) ≤ z) ≥ α
This is a chance constraint.
14 1. RISK IN OPTIMIZATION PROBLEMS

Example 1.5 (Portfolio optimization with VaR constraint.). We consider

n investment opportunities, with random return rates ξ = (ξ1 , . . . , ξn )
in the next year. We have certain initial capital and our aim is to invest
it in such a way that the expected value of our investment after a year is
maximized, under the condition that the chance of losing no more than
a given amount, say ν, is at least α ∈ (0, 1). Such a requirement is a
VaR constraint. That is, the least amount lost with a probability of at
least α must be smaller than the given ν.
Let x1 , . . . , xn be the fractions of our capital invested in the n assets.
After a year our investment has value
Xn
ξ i xi
i=1

To model the VaR constraint, we let our loss random variable be l(x, ξ) =
P n
i=1 −ξi xi and model VaR as
( n
! )
X
VaRα (L) = min z|P − ξ i xi ≤ z ≥ α
i=1
We formulate this problem as
Xn
max E [ξi ] xi
i=1
n
X
xi = 1
i=1
( n
! )
X
min z |P − ξ i xi ≤ z ≥α ≤ν
i=1
x≥0

1.4. Coherent measures of risk

Historically, the development of risk measures used in the Markowitz risk-
reward framework has been to a large extent application-driven. Financial
applications have been predominant. New risk measures have been designed
in an attempt to represent particular risk preferences or attitudes. To some
extent, this undermined their general applicability. In response to this, an
axiomatic approach to the construction of risk measures has been proposed by
[ADEH99]. They undertook the task of determining a set of requirements
 1.4. COHERENT MEASURES OF RISK 15

that a “good” risk measure must satisfy. In particular, [ADEH99] identified

four axioms of a “good” risk measure. They called the risk measures that
satisfy these axioms as coherent risk measures.
A coherent risk measure is defined as a mapping2
rmf : L2 (Ω, F, P) → R that satisfies the following four axioms
A1 L ≤ 0 a.s. =⇒ ρ (L) ≤ 0 for all L ∈ L2 (Ω, F, P).
A2 convexity: ρ (λL + (1 − λ)L′ ) ≤ λρ (L) + (1 − λ)ρ (L′ ) for all L, L′ ∈
L2 (Ω, F, P) and λ ∈ [0, 1].
A3 positive homogeneity: ρ (λL) = λρ (L) for all L ∈ L2 (Ω, F, P) and
λ ≥ 0.
A4 translation invariance: ρ (a + L) = ρ (L) + a for all L ∈ L2 (Ω, F, P)
and a ∈ R.
These axioms have clearly been developed with a financial applications in
mind. Nevertheless, they bear meaning which is easily transferable to other
domains. Axiom (A1) implies that a negative loss (i.e., a gain) should be
measured by a negative risk. That is, if the random variable never takes
positive values, the risk (which is associated to a loss) is negative.
Axiom (A2), convexity, sets the foundation for the principle of decreasing
risk by diversification. This will be substantiated by an additional property
called subadditivity, which we will see later. In addition, convexity allows
building coherent risk measures by combining coherent risk measures. To that
extent, it is sufficient to use operations that preserve convexity. For example,
given coherent risk measures ρ (L)i , i = 1, . . . , n, we can obtain a new coherent
risk measure as
Xn
ρ (L) = λi ρ (L)i
i=1
Pn
with i=1 λi = 1 and λi ≥ 0 or
ρ (L) = max{ρ (L)1 , . . . , ρ (L)n }
Axiom (A3), positive homogeneity, entails that if the value of L is scaled
uniformly by a factor λ, then the risk scales accordingly. This is natural in a
financial context: doubling the position value in a risk asset obviously doubles
the risk.
Finally, axiom (A4), translation invariance, is also supported by a financial
interpretation. If L is the loss of a financial position, adding a sure cash loss
to this position increases the risk by the same amount.

2It is possible to allow the risk measure to take values in the extended real line. This
requires imposing additional mathematical properties on ρ.
16 1. RISK IN OPTIMIZATION PROBLEMS

After the original work of [ADEH99], the axioms of coherence have been
presented in different forms. New axioms, which imply (A1)-(A4) have often
replaced them. As an example, we may substitute axiom (A4) (translation
invariance) with the following simpler axiom
(A4’) ρ (C) = C for all constant C ∈ R.
The following proposition shows that we can imply (A4) building on (A2),
(A3) and (A4’).

Proposition 1.3 (Translation invariance). Assume ρ satisfies (A2),

(A3) and (A4’). Then ρ satisfies (A4).

Proof. We prove (A4) in two parts. We first show that

ρ (L + a) ≥ ρ (L) + a
and then that
ρ (L + a) ≤ ρ (L) + a
effectively implying the required equation.
First inequality.
ρ (L) + a =ρ (L + a − a) + a
 
1 1
=ρ 2(L + a) + (−2a) + a
2 2
(A2) 1 1
≤ ρ (2(L + a)) + ρ (−2a) + a
2 2
(A3) 1
= ρ (L + a) + ρ (−2a) + a
2
(A4′ ) 1
= ρ (L + a) + (−2a) + a
2
=ρ (L + a)
Thus we obtain ρ (L) + a ≤ ρ (L + a).
For the second inequality we observe that.
 
2 2
ρ (L + a) =ρ L+ a
2 2
(A2) 1 1
≤ ρ (2L) + ρ (2a)
2 2
(A3)
= ρ (L) + ρ (a)
 1.4. COHERENT MEASURES OF RISK 17

(A4′ )
= ρ(L) + a
Thus, we obtain ρ (L + a) ≤ ρ (L) + a. □

Additional properties of coherent risk measures can be derived from the

ones stated. Convexity (A2) and positive homogeneity (A3) imply the follow-
ing important result.

Proposition 1.4 (Subadditivity). Assume that ρ satisfies (A2) and

(A3). Let L, L′ be two random variables in L2 (Ω, F, P). Then
ρ (L + L′ ) ≤ ρ (L) + ρ (L′ )

Proof. We proceed as follows

   
′ 2 ′ 1 1 ′
ρ (L + L ) =ρ (L + L ) = ρ 2L + 2L
2 2 2
By convexity we have
 
1 1 ′ 1 1
ρ 2L + 2L ≤ ρ (2L) + ρ (2L′ )
2 2 2 2
By positive homogeneity the righ-hand side is equivalent to
ρ (L) + ρ (L′ )
as required. □

Subadditivity encodes mathematically the principle of lowering risk by di-

versification. The risk of the sum of the random variables is smaller than the
risk of the individual random variables separated. This is the mathematical
expression of the fundamental principle of risk reduction via diversification.
From (A1), (A2) and (A3) we derive the following important result.

Proposition 1.5 (Monotonicity). Let ρ be a coherent measure of risk.

Given any two random variables L, L′ ∈ L2 (Ω, F, P) with L ≤ L′ a.s.,
then ρ (L) ≤ ρ (L′ ).
18 1. RISK IN OPTIMIZATION PROBLEMS

Proof.
ρ (L) =ρ (L′ + L − L′ )
 
1 ′ 1 ′
=ρ (2L) + 2(L − L )
2 2
(A2),(A3) 2 2
≤ ρ (L′ ) + ρ(L − L′ )
2 2
=ρ (L′ ) + ρ (L − L′ )
Observe that, a.s., we have L − L′ ≤ 0. Thereofore, ρ (L − L′ ) ≤ 0.
This entails
ρ (L) ≤ ρ (L′ )
as required. □

It is easy to verify how some of the risk measures introduced above are
(not) coherent, see Exercises 1.1 to 1.3. Value-at-Risk is in general not a
coherent measure of risk. In fact, it may fail to satisfy convextiy. Upper
Partial Moments are also not necessarily coherent. For example, for any non-
constant random variable, the semideviation is positive even if the random
variable is almost surely negative. In fact, this type of measures are ofter
referred to as deviation measures to distinguish them from risk measures.
 1.5. EXERCISES 19

1.5. Exercises
Exercise 1.1. The prediction approach can be considered as a risk mea-
sure
ρ (L) = L(ω)
for some ω in a subset of Ω of positive measure. Check whether ρ (·) is a
coherent risk measure.
Exercise 1.2. The worst-case approach can be considered as a risk mea-
sure
ρ (L) = ess sup L
Check whether ρ (·) is a coherent risk measure.
Exercise 1.3. The expected value approach can be considered as a risk
measure
ρ (L) = E [L]
Check whether ρ (·) is a coherent risk measure.
 CHAPTER 2

Stochastic Dominance

The definition of risk varies from a field to another. Throughout Chap-

ter 1 we assumed that the random variable of interest quantifies loss and we
discussed ways of measuring and, hereby, containing or minimizing the risk
of losses. This is consistent, for example, with actuarial mathematics, where
risk is typically connected to a non-negative random variable quantifying the
loss incurred by a customer or by an insurer. The same applies to engineer-
ing, where the random variable of interest models some undesireble event that
must be prevented, such as the collapse of a structure. In economics and in fi-
nance, risk is typicaly related to a gain instead of a loss. There is, for example,
some risky asset on which an investor has committed, and the goal is to make
sure the gain is the largest possible or large enough. The topics presented in
this chapter were developed with this goal in mind. Therefore, for consistency
with the literature, in the rest of this chapter we assume that random variables
model gains. That is, there is something we want more of and we want to
prevent getting too little of. Of course, the theory presented holds also for loss
random variables, provided that we adjust some definitions along the way.

2.1. Utility Theory: A Brief Overview

In every-day life one has to choose an action from a given set of alternatives
with uncertain consequences. Consider, for example, an investor who has to
allocate their resources to different investment opportunities, or an individual
who has to decide whether or not to buy a lottery ticket. The utility theory of
von Neumann and Morgenstern [VNM47] represents one of the major pillars
of decision science. Utility theory formalizes the manner in which a decision
maker chooses among alternatives with uncertain consequences. Each alterna-
tive results in one out of several possible consequences. Formally, the building
elements of utility theory are
◦ A a set of alternative actions (also called lotteries to stress the ran-
domness of their outcomes or consequences) from which the decision
maker may choose.
◦ C a set of consequences
21
22 2. STOCHASTIC DOMINANCE

To each action there corresponds not necessarily an individual consequence,

but rather a subset of consequences from C. Hence, the uncertainty. This
uncertainty is resolved only once the future state of the world materializes and
assigns an element of C to an element of A. This future state of the world is
outside the control of the decision maker.
Utility theory is postulated in terms of certain defining axioms. These
axioms describe what it means for someone to make rational decisions when
faced choices with uncertain consequences. A rational decision-maker is some-
one who makes choices that are logically consistent and aimed at maximizing
their personal utility. These axioms are the following.
(1) Completeness. This axiom states that for any two lotteries A and
B, a rational decision-maker can always compare them and express a
preference. That is:
◦ They prefer X over Y (denoted X ≻ Y ), or
◦ They prefer Y over X (denoted Y ≻ X), or
◦ They are indifferent between X and Y (denoted X ∼ Y ).
The implication in terms of rational behavior is that the decision-
maker is always able to make a choice and does not remain indecisive.
(2) Transitivity. This axiom ensures that a rational decision-maker’s
preferences are consistent across multiple comparisons. If X ≻ Y and
Y ≻ Z then X ≻ Z. The rational implication is that preferences are
logically consistent across choices.
(3) Independence of Irrelevant Alternatives (IIA). This axiom states
that if a decision-maker prefers lottery X over lottery Y (X ≻ Y ),
then their preference remains the same regardless of the presence of
a third option Z. The rational implication is that the decision-maker
is not swayed by options that are not directly involved in the choice
being made.
(4) Continuity. The continuity axiom is slightly more technical, but
it can be described intuitively. If a decision-maker prefers X to Y ,
and Y to Z, then there should exist a “mixture” of X and Z that
the decision-maker would consider equally preferable to Y . In other
words, if X ≻ Y ≻ Z, then there exists some probability p such
that the decision-maker would be indifferent between Y and a lottery
where they get X with probability p and Z with probability 1 − p.
The rational implication is that a rational decision-maker should be
able to handle uncertainty in a continuous, consistent way.
In summary these axioms define how a rational decision-maker behaves when
faced with choices. They ensure that the decision-maker can always make
a comparison, is consistent, is unaffected by irrelevant alternatives, and can
 2.1. UTILITY THEORY: A BRIEF OVERVIEW 23

handle uncertainty in a logical manner also in a continuum of possible choices.

If someone violates any of these axioms, their choices may not be considered
rational in the formal sense of decision theory.
Utility theory argues that when the preference relation (≻, or ⪰ for non-
strict preferences) satisfies the axioms of completeness, transitivity, continuity,
and independence, then there exists a real-valued function
u:R→R
such that a lottery X is preferred to a lottery Y , i.e., X ⪰ Y , if and only if
E [u(X)] ≥ E [u(Y )]
Thus, a decision problem under uncertainty for a rational decision maker re-
duces to maximizing their expected utility.
If the decision maker is rational, in the sense that they prefer more to less,
then the utility function is necessarily increasing. In addition, how a decision
maker feels about uncertainty (or risk) can be captured by the curvature of
their utility function. Specifically, it comes down to how they value expected
outcomes versus the outcomes of the lottery.
In particular, the decision-maker is said to be risk-averse if their utility
function is concave. This entails that the marginal utility of an additional unit
becomes smaller, the larger is the amount already obtained. This, in turn,
entails that the utility of receiving the expected value for sure is greater than
or equal to the expected utility of a lottery. That is, assume the lottery gives
an outcome O1 with probability p and an outcome O2 with probability (1 − p).
Then, by concavity of u we have that
u(pO1 + (1 − p)O2 ) ≥ pu(O1 ) + (1 − p)u(O2 )
Hence, the decision maker would prefer the sure thing to the risky bet.

Example 2.1 (Risk Aversion). Suppose you offer a person a gamble

with 50% chance of winning $100, and 50% chance of winning $0. The
expected monetary√value of this gamble is $50. Assume the person’s
utility function is x, hence concave. Then the expected utility of the
gamble is 0.5u(100) + 0.5u(0) = 0.5 · 10 + 0.5 · 0 = 5 while the utility of
getting the
√ $50 (equal to the expected value of the gamble) for sure is
u(50) = 50 ≈ 7.07. So the decision maker prefers $50 for sure over the
gamble. This shows risk aversion: they would rather take money with
certainty than a risky option with the same expected value.
24 2. STOCHASTIC DOMINANCE

A risk-neutral decision maker is indifferent between a sure outcome and

a gamble with the same expected value. This is modeled by a linear utility
function. The decision maker assigns equal utility to the gamble and to its
expected outcome. This means they are indifferent between taking a sure
amount or a gamble with the same expected value.

Example 2.2 (Risk Neutrality). Consider the same gamble as in the

previous example: 50% chance of winning $100, 50% chance of winning
$0. For a risk-neutral decision maker with u(x) = x, the expected utility
of the gamble is $50 while the utility of getting $50 for sure is u(50) = 50.
Hence, the decision maker is indifferent between taking the gamble or
$50 for sure. They are neutral towards risk.

A risk-seeking decision maker prefers a risky gamble over its expected value.
This is modeled by a convex utility function. In this case we have that
u(pO1 + (1 − p)O2 ) ≤ pu(O1 ) + (1 − p)u(O2 )
indicating that the expected utility of the gamble (right-hand side) is greater
than the utility of the sure outcome (the expected value, left-hand side). This
implies the decision maker prefers the gamble to the sure thing.

Example 2.3 (Risk Seeking). Consider again the same gamble: 50%
chance of winning $100, 50% chance of winning $0. For a risk-seeking
decision maker with u(x) = x2 , the expected utility of the gamble is
0.5u(100) + 0.5u(0) = 0.5 · 10000 + 0.5 · 0 = 5000. The utility of getting
$50 for sure is: u(50) = 502 = 2500. Hence, the decision maker prefers
the gamble to $50 for sure. This shows risk proclivity: they would rather
take the risky option even if it has the same expected value as the certain
option.

Describing completely the utility function for each individual decision maker
is nearly impossible in practice. For this reason, one typically relates to specific
classes of utility functions (e.g., concave, linear, convex) representing specific
types of risk attitudes.

2.2. Stochastic Orders

The concept of Stochastic Dominance (also called stochastic order ) is closely
related to that of utility theory. It also represents a way of ordering choices
 2.2. STOCHASTIC ORDERS 25

with uncertain consequences. Stochastic order relations are a special case of

partial order relations. Let us recall the definition of a partial order.

Definition 2.1 (Partial order). A binary relation ⪰ on an arbitrary set

S is called a (partial) order if it satisfies the following conditions:
(1) Reflexivity: x ⪰ x for all x ∈ S.
(2) Transitivity: if x ⪰ y and y ⪰ z then x ⪰ z for x, y, z ∈ S.
(3) Antisymmetry: if x ⪰ y and y ⪰ x then x = y.

Particularly, stochastic dominance defines a partial order on the space of

real-valued random variables on some probability space (Ω, F, P). Let X :
Ω → R be a random variable with reals values defined on (Ω, F, P). Let
PX : B → [0, 1] be its distribution defined on (R, B) where B is the Borel
σ-algebra on R. Let FX : R → [0, 1] be its distribution function. That is
FX (t) = PX ((−∞, t]) = P ({ω ∈ Ω|X(ω) ≤ t})
for all real t. Particularly, we simplify P ({ω ∈ Ω|X(ω) ≤ t}) using P(X ≤
t). Often it is convenient not to distinguish between an order relation for
distribution functions and the corresponding relations for random variables.
If random variables X and Y have distributions PX and PY and distribution
functions FX and FY , then the notation PX ⪰ PY and X ⪰ Y will be used
interchangeably. Note that there can be different random variables with the
same distribution, so that the relation ⪰ is antisymmetric as a relation among
distributions but not as a relation among random variables1.
The most natural candidate for a stochastic order is that of pointwise
comparison of the distribution functions.

Definition 2.2 (First-order stochastic dominance). Consider random

variables X and Y defined on a probability space (Ω, F, P). Then, we
say that random valiable X dominates random variable Y with respect
to the first-order stochastic dominance (FSD) relation, written X ⪰(1)
Y , if
P (X ≤ t) ≤ P (Y ≤ t) ∀t ∈ R
The FSD relation can be expressed equivalently in terms of the distri-
bution functions induced by X and Y , that is
FX (t) ≤ FY (t) ∀t ∈ R

1It
might be useful to review the concepts of equality and equality in distribution for
random variables.
26 2. STOCHASTIC DOMINANCE

where FX and FY are the distribution functions of random variables X

and Y , respectively.

If FX (t) ≤ FY (t) for all real t, then X assumes small values with lower
probability than Y does2. That is, given a t, the probability of the event
X ≤ t is smaller than the probability of the event Y ≤ t, and this holds for
all t ∈ R. In the given form, this can be thought of as a generalization of the
order ≥ on the reals, since for real numbers a and b, a ≥ b implies a ⪰(1) b,
with a and b considered as degenerated random variables. In fact, we have
that
◦ for t < b ≤ a, we have P (b ≤ t) = 0 = P (a ≤ t).
◦ for b ≤ t < a, we have P (b ≤ t) = 1 ≥ 0 = P (a ≤ t).
◦ for b ≤ a ≤ t, we have P (b ≤ t) = 1 ≥ 1 = P (a ≤ t).
The following results bridge utility theory and stochastic dominance. We
start with this preliminary result.

Theorem 2.3. Let X and Y be random variables with distribution func-

tions FX and FY . Then X ⪰(1) Y if and only if there exists a probability
space (Ω, F, P) and random variables X̂ and Ŷ on it, with distribution
functions FX and FY , such that X̂(ω) ≥ Ŷ (ω) for all ω ∈ Ω.

Proof. ( =⇒ ). For a distribution function F and 0 < u < 1,

denote the inverse distribution function as
F −1 (u) = inf{x|F (x) ≥ u}

2Inthis discussion we are assuming random variables represent gains or things we want
more of. We may as well pose the entire discussion around loss random variables. In that
case we would say that random variable L1 dominates random variable L2 with respect to
FSD relation, L1 ⪰(1) L2 if
P (L1 ≤ t) ≥ P (L2 ≤ t)

for all t ∈ R. Here, L1 is preferred to L2 if L1 assumes smaller values than L2 . However,

most of the development on stochastic dominance assumed gain random variables, hence for
consistency we adhere to that choice. In any case, the theory presented here holds, with the
necessary adjustments, regardless of the interpretation of the random variables. The reader
who has in mind an application with a loss random variable can simply assume that the
gain random variable is the negative losse, that is X = −L.
 2.2. STOCHASTIC ORDERS 27

Let U be a random variable uniformly distributed on (0, 1). Define

−1
X̂ = FX (U ) and Ŷ = FY−1 (U ). Then X̂ has distribution FX and Ŷ
has distribution FY . Since X ⪰(1) Y we have that FX (t) ≤ FY (t) for
−1
all t ∈ R. This implies that, for any u, FX (u) ≥ FY−1 (u) since a smaller
cumulative probability FX (t) at a given t corresponds to a larger value
−1
t for the same u. Therefore, X̂ = FX (U ) ≥ FY−1 = Ŷ for all ω ∈ Ω.
( ⇐= ). This implication is obvious. □

Definition 2.4. A function f : R → R is called increasing if x ≤ y

implies f (x) ≤ f (y).

The following theorem ties together utility theory and stochastic domi-
nance.

Theorem 2.5. Let X and Y be random variables. Let f be an arbitrary

increasing function for which E [f (X)] and E [f (Y )] exist. Then
X ⪰(1) Y ⇐⇒ E [f (X)] ≥ E [f (Y )]

Proof. ( =⇒ ). According to Theorem 2.3 it can be assumed,

without loss of generality, that X ≥ Y for all ω ∈ Ω. Thus, if f is
increasing, then f (X(ω)) ≥ f (Y (ω)) for all ω too. E [f (X)] ≥ E [f (Y )]
follows from the monotonicity of expectations.
( ⇐= ). We have that E [f (X)] ≥ E [f (Y )] for all increasing functions.
Assume X does not stochastically dominate Y . This implies that there
exists some t ∈ R for which FX (t) > FY (t). Consider, as a specific
increasing function, the indicator function i(x) = 1x≥t (x). Let us now
compute the expectations
E [i(X)] = E [1X≥t (X)] = P (X ≥ t) = 1 − FX (t)
and
E [i(Y )] = E [1Y ≥t (Y )] = P (X ≥ t) = 1 − FY (t)
Since E [f (X)] ≥ E [f (Y )] for all increasing functions, it follows that
1 − FX (t) ≥ 1 − FY (t)
This, in turn, implies
−FX (t) ≥ −FY (t) =⇒ FX (t) ≤ FY (t)
28 2. STOCHASTIC DOMINANCE

This contradicts the assumption that FX (t) > FY (t). □

Essentially, Theorem 2.5 states that any rational decision maker (i.e., whose
utility function is increasing in the sense that they prefer more to less) would
choose X over Y if X ⪰(1) Y . Random variable X gives a higher expected
utility. The following corollary is an immediate consequence of Theorem 2.5.

Corollary 2.6. Let X and Y be random variables. Assume their ex-

pectation is bounded, that is, X, Y ∈ L1 (Ω, F, P). If X ⪰(1) Y then
E [X] ≥ E [Y ]

Proof. The proof follows immediately from Theorem 2.5 using

f (x) = x. □

The concept of FSD can be generalized as follows

Definition 2.7 (Second-order stochastic dominance). A random out-

come X ∈ L1 (Ω, F, P) is said to dominate random outcome Y ∈
L1 (Ω, F, P) with respect to the second-order stochastic dominance (SSD)
relation, X ⪰(2) Y , if
Z t Z t
FX (x) dx ≤ FY (y) dy ∀t ∈ R
−∞ −∞

Intuitively, SSD corresponds to stating that X assumes larger values than

Y with higher probability across a range of thresholds t 3. It is easy to observe
that X ⪰(1) Y =⇒ X ⪰(2) Y .
The link between utility theory and stochastic dominance principles is
strengthened by SSD. Particularly, [RS70] show that
X ⪰(2) Y
3Again,if we consider loss random variables, L1 is said to dominate random outcome
L2 with respect to the SSD relation, L1 ⪰(2) L2 if
Z t Z t
FL1 (l) dl ≥ FL2 (l) dl ∀t ∈ R
−∞ −∞

Intuitively, L1 assumes smaller values than L2 with higher probability across a range of
thresholds t. .
 2.3. OPTIMIZATION WITH FSD CONSTRAINTS 29

is equivalent to
E [u(X)] ≥ E [u(Y )]
for all non-decreasing concave functions u : R → R. This implies that every
risk-averse decision makers would choose X over Y , provided that X ⪰(2) Y .
The deep connections between the expected utility theory and stochastic
dominance have been exploited in numerous developments pertinent to decision
making under uncertainty and risk. One of the most recent advances in this
context involves optimization problems with stochastic dominance constraints.
That is, we are interested in problems of the following types

(2.1) max f (x) : w(x, ξ) ⪰(1) Y
x∈X

and

(2.2) max f (x) : w(x, ξ) ⪰(2) Y
x∈X
n
where X ⊆ R contains all the feasible decisions that can be made and the
function f : Rn → R represents the criteria that guides the choice of a decision.
The function w : Rn × RN → R represents a random outcome of interest
determined by decision x and by an exogenous random variable ξ with values
in RN . Hence, we wish that w stochastically dominates a benchmark random
variable Y .
Unfortunately, the way in which the order relationships ⪰(1) and ⪰(2) have
been presented above does not immediately suggest ways in which one could
immediately find analytical or numerical solutions to (2.1) and (2.2). However,
there are a number of results that, under specific assumptions, help transform-
ing these problems into more manageable optimization problems.

2.3. Optimization with FSD constraints

Problem (2.1) has a couple of major difficulties. First, for arbitrary x and
t, it is not obvious how to obtain the probability P (w(x, ξ) ≤ t) under general
conditions. This task will most like require solving multidimensional integrals.
Second, the condition P (w(x, ξ) ≤ t) ≤ P (Y ≤ t) has to be verified for every
t ∈ R, that is, for invinitely many values t. Finally, one has to find the best
x that satisfies these conditions. These tasks appear, and to a large extent
are, daunting. Nevertheless, when specific assumptions hold, these tasks may
significantly simplify. The following proposition shows that when Y has a
discrete distribution, first-order stochastic dominance can be verified only at
a finite number of t points.
30 2. STOCHASTIC DOMINANCE

Proposition 2.8. Let W be an arbitrary random variable and Y be a

discrete random variable with support
{y1 , . . . , yK }
Furthermore, let y0 be an arbitrary number y0 < y1 with P (Y ≤ y0 ) = 0.
If
(2.3) P (W < yk ) ≤ P (Y ≤ yk−1 ) k = 1, . . . , K
then
W ⪰(1) Y

Proof. Recall the definition of first-order stochastic dominance

P (W ≤ t) ≤ P (Y ≤ t) ∀t ∈ R
Assume, without loss of generality, that y1 < y2 < · · · < yK We need to
show that
P (W < yk ) ≤ P (Y ≤ yk−1 ) k = 1, . . . , K
implies
P (W ≤ t) ≤ P (Y ≤ t) ∀t ∈ R
We consider three cases, t < y1 , t ∈ [yk , yk+1 ) for some 1 ≤ k < K, and
t ≥ yK .
Case 1: t < y1 . In this case we have
P (W ≤ t) ≤ P (W < y1 ) ≤ P (Y ≤ y0 ) = 0 = P (Y ≤ t)
where the first inequality holds because t < y1 . The second inequality
holds by assumption. The first equality holds by definition of y0 . The
last equality holds because t < y1 and hence has probability zero. In
particular, since necessarily P (W ≤ t) ≥ 0 the assertion holds as an
equality.
Case 2: yk−1 ≤ t < yk for some 2 ≤ k < K. In this case we have that
P (W ≤ t) ≤P (W < yk ) By monotonicity
≤P (Y ≤ yk−1 ) By assumption
=P (Y < yk ) Y is discrete, so the next jump is Y = yk
=P (Y ≤ t) Y is discrete, so for all yk−1 ≤ t < yk we have
P (Y ≤ t) = P (Y ≤ yk−1 ) . The next jump is yk .
 2.3. OPTIMIZATION WITH FSD CONSTRAINTS 31

Case 3: t ≥ yK . In this case we have

P (Y ≤ t) = P (Y ≤ yK ) = 1 ≥ P (W ≤ t)
for all t by definition of P. □

Hence, when the benchmark is a discrete random variable, enforcing first-

order stochastic dominance reduces to enforcing a finite number of inequalities.
Nevertheless, inequalities (2.3) are still problematic. While the right-hand side
reduces to a constant, the left-hand side might still requires multidimensional
integration. The problem simplifies substantially when both Y and W are
discrete. In that case, the expectation on the left-hand side reduces to a sum,
and FSD can be enforced using mixed-integer linear programming techniques.
Assume that the yk values are sorted such that y1 < y2 < · · · < yK and have
probabilities q1 , . . . , qK . Assume that W is supported by {w1 , . . . , wS } with
probabilities p1 , . . . , pS . Thus, we enforce W ⪰(1) Y by means of
S
X k−1
X
(2.4) ps βsk ≤ qj k = 1, . . . , K
s=1 j=1

(2.5) Msk βsk ≥ yk − ws k = 1, . . . , K, s = 1, . . . , S

(2.6) βsk ∈ {0, 1} k = 1, . . . , K, s = 1, . . . , S
where MP sk is an upper bound to yk − ws . Observe that, since the yk values are
sorted, k−1j=1 qj represents P (Y ≤ yk−1 ). In (2.5) we have that ws < yk =⇒
βsk = 1. Hence, Ss=1 ps βsk represents P (W < yk ). Thus, constraints (2.4)
P
represent the condition
P (W < yk ) ≤ P (Y ≤ yk−1 )
for k = 1, . . . , K.
If we consider random variable W to be the random outcome of optimiza-
tion variables, that is w(x, ξ), and assume that ξ has a finite support ξ1 , . . . , ξS
with probabilities p1 , . . . , pS , we can rewrite optimization problem (2.1) as fol-
lows:
(2.7a) max f (x)
S
X k−1
X
(2.7b) ps βsk ≤ qj k = 1, . . . , K
s=1 j=1

(2.7c) Msk βsk ≥ yk − w(x, ξs ) k = 1, . . . , K, s = 1, . . . , S

(2.7d) βsk ∈ {0, 1} k = 1, . . . , K, s = 1, . . . , S
32 2. STOCHASTIC DOMINANCE

(2.7e) x∈X
When functions f and w are linear in x and X is either polyhedral or X ⊆ Zn ,
problem (2.7) is an mixed-integer linear programming (MILP) problem.

2.4. Optimization with SSD constraints

Also in the case of SSD there are result that allow us to obtain tractable
optimization problems. The first such result show that SSD can be expressed
in terms of expected short-falls.

Proposition 2.9. Let W ∈ L1 (Ω, F, P) be a random variable with

distribution function FW . Then, for η ∈ R
Z η
FW (t) dt = E [(η − W )+ ]
−∞
where (·)+ = max{0, ·}.

Proof. Let fW be the density function of W . By definition of fW

we have that
Z η Z η Z t 
FW (t) dt = fW (W ) dW dt
−∞ −∞ −∞
By changing the order of integration (with particular attention to the
region of integration), we obtain
Z η Z η 
dt fW (W ) dW
−∞ t=W
Z η
= (η − W )+ fW (W ) dW
−∞
=E [(η − W )+ ]
as required. □

This result has immediate implications on second-order stochastic domi-

nance. This is explained in the following result.

Corollary 2.10. Let W and Y be random variables defined in

L1 (Ω, F, P). Then
W ⪰(2) Y ⇐⇒ E [(η − W )+ ] ≤ E [(η − Y )+ ] ∀η ∈ R
 2.4. OPTIMIZATION WITH SSD CONSTRAINTS 33

Proof. Recall the definition of SSD

Z η Z η
FW (t) dt ≤ FY (t) dt ∀η ∈ R
−∞ −∞
By Proposition 2.9 we can write both left- and right-hand side as ex-
pected shortfalls, that is
E [(η − W )+ ] ≤ E [(η − Y )+ ] ∀η ∈ R
obtaining the claimed result. □

The result provided in Corollary 2.10 is indeed useful. The first immediate
consequence is given in the next corollary.

Corollary 2.11. Z η
FW (t) dt
−∞
is a convex function of η and W .

Proof. By Proposition 2.9 we have

Z η
FW (t) dt = E [(η − W )+ ] = E [max{0, η − W }]
−∞
Convexity follows immediately from (i) the expectation operator pre-
serving convexity and (ii) the max function being convex in its argu-
ments. □

With Corollary 2.10 and Corollary 2.11 we have essentially established that
we can express SSD constraints using expectations and that these expressions
are convex in the random variables of interest. In other words, this allows us
to reformulate problem (2.2) as follows
(2.8) max {f (x) : E [(η − w(x, ξ))+ ] ≤ E [(η − Y )+ ] ∀η ∈ R}
x∈X

If w is convex in x then the SSD conditions are convex for given η. Hence,
if X is convex, the feasible region of this problem is convex in that it is the
intersection of convex constraints. If also f is convex in x we have a convex
optimization problem. However, problem (2.8) still requires infinitely many
constraints. The following proposition explains that, when the benchmark Y
is a discrete random variable (as it is the case in most practical applications),
the situation may significantly simplify.
34 2. STOCHASTIC DOMINANCE

Proposition 2.12. Let W be an arbitrary random variable and Y be a

discrete random variable with realizations y1 , . . . , yK . Then, inequalities
E [(yk − W )+ ] ≤ E [(yk − Y )+ ] k = 1, . . . , K
are equivalent to
E [(η − W )+ ] ≤ E [(η − Y )+ ] ∀η ∈ R

Proof. ( ⇐= ). This implication holds trivially. If the constraints

are satisfied for all η ∈ R, then they are satisfied by the given values
yk ∈ R.
( =⇒ ). This part requires some work. Assume
E [(yk − W )+ ] ≤ E [(yk − Y )+ ] k = 1, . . . , K
Assume further, without loss of generality, that y1 < y2 < · · · < yK .
We prove this result considering three different cases, namely η < y1 ,
η ∈ [yi , yi+1 ] for some 1 ≤ i < K and, finally, η > yK .
Case 1: η < y1 . Observe that, for η < y1 we have
0 = E [(η − Y )+ ]
Since y1 is the smallest value we have
0 = E [(η − Y )+ ] = E [(y1 − Y )+ ]
Then, by our initial assumption, we can state
0 = E [(y1 − Y )+ ] ≥ E [(y1 − W )+ ]
Furthermore, η < y1 implies
0 = E [(η − Y )+ ] = E [(y1 − Y )+ ] ≥ E [(y1 − W )+ ] ≥ E [(η − W )+ ] ≥ 0
where the non-negativity of E [(η − W )+ ] holds by definition of (·)+ .
Therefore, we obtain that
E [(η − Y )+ ] ≥ E [(η − W )+ ] ∀η < y1
which satisfies the implication in the interval (−∞, y1 ).
Case 2: yk ≤ η ≤ yk+1 and 1 ≤ k ≤ K. Recall that by Corollary 2.11
E [(η − W )+ ] is convex in η. Thus, for all η ∈ [yk , yk+1 ] we have
E [(η − W )+ ] ≤λE [(yk − W )+ ] + (1 − λ)E [(yk+1 − W )+ ]
≤λE [(yk − Y )+ ] + (1 − λ)E [(yk+1 − Y )+ ]
=E [λ(yk − Y )+ ] + E [(1 − λ)(yk+1 − Y )+ ]
 2.4. OPTIMIZATION WITH SSD CONSTRAINTS 35

Now, it is easy to verify that for given Y , λ(yk − Y )+ + (1 − λ)(yk+1 −

Y )+ = (λyk + (1 − λ)yk+1 − Y )+ (to see this, check the expression for
y ≤ yk and for y ≥ yk+1 ). Hence, we can write
E [λ(yk − Y )+ ] + E [(1 − λ)(yk+1 − Y )+ ]
=E [(λyk + (1 − λ)yk+1 − Y )+ ]
=E [(η − Y )+ ]
where λ = (yi+1 − η)/(yi+1 − yi ).
Case 3: η > yK . In this case we have
E [(η − Y )+ ] =E [(yK − Y )+ ] + η − yK
Z η
≥E [(yK − W )+ ] + FW (t) dt = E [(η − W )+ ]
yK
where the last equality holds since by Proposition 2.9
Z yk
E [(yK − W )+ ] = FW (t) dt
−∞
and
Z yk Z η Z η
FW (t) dt + FW (t) dt = FW (t) dt = E [(η − W )+ ]
−∞ yK −∞
□

Hence, by Proposition 2.12, when the benchmark Y is a discrete random

variable, the infinitely many inequalities in problem (2.8) are equivalent to
only K inequalities, one for each point in the support of Y . This is quite a
step forward in terms of tractablility.
What remains to address are the expected shortfalls in terms of W . At the
moment these are general multidimensional integrals for which an analytical
solution may not exist. However, when also W has a discrete distribution,
things become more manegeable. Let w1 , . . . , wS be the support of W with
probabilities p1 , . . . , pS . Let also q1 , . . . , qK and y1 , . . . , yK be the probabili-
ties and support, respectively, of the benchmark Y . We introduce new vari-
ables usk ≥ 0 to represent the quantities max{0, yk − wi } for s = 1, . . . , S,
k = 1, . . . , K that appear in the left-hand side of the inequality defined in
Proposition 2.12. Thus, W ⪰(2) Y if and only if there exists u ∈ RS·K + such
that
S
X K
X
ps usk ≤ qj (yk − yj )+ k = 1, . . . , K
s=1 j=1
36 2. STOCHASTIC DOMINANCE

usk ≥ yk − ws s = 1, . . . , S, k = 1, . . . , K
usk ≥ 0 s = 1, . . . , S, k = 1, . . . , K

Observe that the quantities (yk − yj )+ can be pre-calculated and should there-
fore be considered as input data.
Now let us put W and Y in an optimization context. Here, random vari-
able W is the random outcome of a specific choice of values for the optimization
variables, that is x 7→ w(x, ξ). Assume ξ has a finite support ξ1 , . . . , ξS with
probabilities p1 , . . . , pS . Then, our optimization problem (2.8) becomes

(2.9a) max f (x)

S
X K
X
(2.9b) ps usk ≤ qj (yk − yj )+ k = 1, . . . , K
s=1 j=1

(2.9c) usk ≥ yk − w(x, ξs ) s = 1, . . . , S, k = 1, . . . , K

(2.9d) usk ≥ 0 s = 1, . . . , S, k = 1, . . . , K
(2.9e) x∈X

When function f and w are linear in x and X is polyhedral, problem (2.9) is

an LP problem. When X ⊆ Z problem (2.9) is an MILP problem.

Example 2.4. Let ξ : Ω → RN be a random variable representing the

returns of N assets. Our aim is to invest our capital in these assets to
obtain some desirable characteristics of the total return. Let x1 , . . . , xN
denote the fraction of the capital allocated to assets 1, . . . , N , respec-
tively. The total return is clearly
N
X
W = ξ i xi
i=1
Our goal is that of maximizing the expected return. In addition, we
have some reference random return Y (e.g., an existing portfolio or a
market index) and we require out outcome to dominate Y in the second
order. Recall that, by means of SSD, we guarantee that no risk-averse
decision maker will prefer Y over our portfolio. We obtain the following
optimization problem
" N #
X
(2.10) max E ξ i xi
i=1
 2.5. CONSIDERING LOSSES 37

N
X
(2.11) xi = 1
i=1
N
X
(2.12) ξi xi ⪰(2) Y
i=1
(2.13) xi ≥ 0 i = 1, . . . , N
Assume now, that the returns have discrete distribution with ξis be-
ing the return of asset i = 1, . . . , N under scenario s = 1, . . . , S, with
probability ps . Assume further that the distribution of Y is discrete
with realizations y1 , . . . , yK and probabilities q1 , . . . , qK . We obtain the
problem
S
X N
X
(2.14) max ps ξis xi
s=1 i=1
N
X
(2.15) usk ≥ yk − ξis xi k = 1, . . . , K, s = 1, . . . , S
i=1
s
X K
X
(2.16) ps usk ≤ qj (yk − yj )+ k = 1, . . . , K
s=1 j=1
N
X
(2.17) xi = 1
i=1
(2.18) xi ≥ 0 i = 1, . . . , N
(2.19) usk ≥ 0 k = 1, . . . , K, s = 1, . . . , S

2.5. Considering Losses

The results presented in the previous sections can be translated into equiv-
alent results when random variables W and Y represent losses, see, e.g.,
[GNS08, GGS11]. Particularly, we obtain that

P (W ≤ yk ) ≥ P (Y ≤ yk ) k = 1, . . . , K

implies

P (W ≤ η) ≥ P (Y ≤ η) ∀η ∈ R
38 2. STOCHASTIC DOMINANCE

and hence W ⪰(1) Y . These conditions can be enforced using binary variables
βsk and linear constraints as follows
S
X k
X
ps βsk ≤ 1 − qi k = 1, . . . , K
s=1 i=1
ws − yk ≤ M βsk s = 1, . . . , S, k = 1, . . . , K
βsk ∈ {0, 1} s = 1, . . . , S, k = 1, . . . , K
where ws − yk > 0 =⇒ βsk = 1 and, in the first set of constraints, the left-
hand side represents the probability of W exceeding yk while the right-hand
side represents the probability of Y exceeding yk .
Similarly, for SSD we obtain that
Z η Z η
FW (α) dα ≤ FY (α) dα ∀η ∈ R
−∞ −∞
holds if and only if
E [(W − η)+ ] ≤ E [(Y − η)+ ] ∀η ∈ R
In turn, when Y is a discrete random variable, this is implied by
E [(W − yk )+ ] ≤ E [(Y − yk )+ ] k = 1, . . . , K
When also W is a discrete random variable, the latter condition, can be en-
forced introducing SK auxiliary variables usk as follows
S
X K
X
ps usk ≤ qi (yi − yk )+ k = 1, . . . , K
s=1 i=1
usk ≥ ws − yk s = 1, . . . , S, k = 1, . . . , K
usk ≥ 0 s = 1, . . . , S, k = 1, . . . , K
 CHAPTER 3

Probabilistic Programming

In Probabilistic Programming we enforce statements on the probability of

certain events. In fact, in some circumstances, we may require that certain
constraints hold with a certain probability. These constraints are called chance
or probabilistic constraints and take the general form

P ({ω ∈ Ω|fi (x, ξ(ω)) ≤ 0, i = 1, . . . , m}) ≥ α

or, more concisely

(3.1) P (fi (x, ξ) ≤ 0, i = 1, . . . , m) ≥ α

for some 0 < α < 1.

Alternatively, that the probability of certain conditions being verified is
maximized or minimized. That is, we solve a problem of type

max P (fi (x, ξ) ≤ 0, i = 1, . . . , m)

x∈X

3.1. Chance Constraints

Chance constraints are, in some cases, closely related to VaR constraints.
Let us revisit an example presented initially in the context of VaR. It presents
a case where VaR can be stated equivalently as as a problem with chance
constraints.

Example 3.1 (Portfolio optimization with chance constraint.). Let us

revisit Example 1.5. Recall that we consider n investment opportunities,
with random return rates ξ1 , . . . , ξn in the next year. We have certain
initial capital and our aim is to invest it in such a way that the expected
value of our investment after a year is maximized, under the condition
that the chance of losing no more than a given amount, say ν, is at least
α ∈ (0, 1). Such a requirement can be stated as a chance constraint.

39
40 3. PROBABILISTIC PROGRAMMING

Let x1 , . . . , xn be the fractions of our capital invested in the n assets.

After a year our investment has value
Xn
ξ i xi
i=1
We formulate this problem as
Xn
max E [ri ] xi
i=1
n
X
xi = 1
i=1
n
!
X
P − ξ i xi ≤ ν ≥α
i=1
x≥0
Observe that the chance constraint states that the probability that the
loss (i.e., the negative of the return) is smaller than ν is larger than α.

The problem illustrated in Example 3.1 shows a special case of chance

constraints with m = 1. We call it an individual chance constraint to distin-
guish it from the general case (3.1), which we call a joint chance constraint.
Joint chance constraints enforce a certain probability that the m constraints
hold simultaneously. Individual chance constraints, instead, impose a possibly
weaker requirement. They take the form

(3.2) P (fi (x, ξ) ≤ 0) ≥ αi i = 1, . . . , m

with 0 < αi < 1, i = 1, . . . , m. They enforce that each constraint holds with a
certain probability αi , specific to the constraint. Note that these m separate
probabilistic requirements do not necessarily enforce that the constraints hold
jointly. The set of events for which each constraint hold may be different, and
their intersection may not have probability at least α. That is, let Ωi ⊆ Ω
be the set of events for which fi (x, ξ(ω)) ≤ 0 holds. Assume P (Ωi ) ≥ α, for
i = 1, . . . , m. Then, the individual chance constraints hold. However, this
does not necessarily imply that P (∩m i=1 Ωi ) ≥ α as required by the joint chance
constraint.
 3.1. CHANCE CONSTRAINTS 41

Example 3.2. Assume we have two constraints, c1 and c2 . Assume ξ has

three equally-likely possible realizations, ξ1 , ξ2 , ξ3 . Assume we impose
individual chance constraints on the two constraints, with a probability
α1 = α2 = α = 2/3. A possible solution is the following

Holds under scenario

Constraint ξ1 ξ2 ξ3 P (ci holds ) α
c1 Yes No Yes 2/3 2/3
c2 Yes Yes No 2/3 2/3

Table 3.1. Example of individual versus joint chance

constraints.
We observe that both individual chance constraints are satisfied with the
desired 2/3 probability. However, if we were to enforce a joint chance
constraint with the same probability 2/3, this constraint would not hold.
In fact, the probability that the two constraints hold jointly is only 1/3.

Of particular practical interest are linear chance constraints. These emerge

when the functions fi are affine in x. That is, the constraints fi (x, ξ) ≤ 0, i =
1, . . . , m, form a linear system of inequalities. That is, we have ξ ∈ R(n+1)×m
so that each constraint becomes ξi⊤ x ≤ ξ0i , i = 1, . . . , m.
The way we treat these constraints depends greatly on whether they are
individual or joint chance constraints and on whether the randomness occurs
in the coefficients ξi of x or in the right-hand side elements ξ0i , or both. This
determines whether we can find a deterministic equivalent for the problem or
not.
To illustrate where the difficulty might arise, consider the set of feasible
solutions to an individual chance constraint, that is
Ki (αi ) = x|P ξi⊤ x ≤ ξ0i ≥ αi


and the set of solutions which satisfy all individual chance constraints, that is
m
\
K= Ki (αi )
i=1
In a similar way, consider the set of feasible solutions to a joint chance con-
straint
K(α) = x|P ξi⊤ x ≤ ξ0i , i = 1, . . . , m ≥ α


Unfortunately, the sets Ki (αi ), K and K(α) are, in general, non-convex as

illustrated in the following example.
42 3. PROBABILISTIC PROGRAMMING

Example 3.3. Non-convex feasible region.

Suppose Ω = {ω1 , ω2 } with P ({ω1 }) = P ({ω2 }) = 1/2. Assume further
that we have two joint chance constraints, that is
 
f1 (x, ξω) ≤ 0
P ≥α
f2 (x, ξω) ≤ 0
Particularly, assume that f1 (x, ξω) = −x − ξ01 (ω) and f2 (x, ξω) = x −
ξ02 (ω). Hence, the uncertainty is only in the right-hand side constants.
In particular, we have
◦ ξ01 (ω1 ) = 0, ξ01 (ω2 ) = −2
◦ ξ02 (ω1 ) = 1, ξ02 (ω2 ) = 3
Therefore, for ω1 the constraints take the form
 
−x ≤ 0
x≤1
and for ω2 we have  
−x ≤ −2
x≤3
It is evident that, for 0 < α < 1/2 we have that the feasible region
is made of all solutions x which satisfy the constraints either for ω1 or
for ω2 (or for both). For ω1 , the constraints are satisfied for all x in
[0, 1]. For ω2 , the constraints are satisfied for all x in [2, 3]. Hence, for
0 < α < 1/2 we have K(α) = [0, 1] ∪ [2, 3], which is non-convex and
disjoint.

Individual chance constraints are, in some cases, easy to treat. This is

the case when fi (x, ξ) ≤ 0 takes the form fi (x) ≤ ξ0i . That is, the left-hand
side is a deterministic function of x and the uncertainty is concentrated in the
right-hand parameter ξ0i . In this case, the constraint becomes
P (fi (x) ≤ ξ0i ) ≥ αi
Let Fξ0i be the distribution function of ξ0i , i.e., Fξ0i (z) = P (ξ0i ≤ z). Then
P (fi (x) ≤ ξi0 ) = P (ξ0i ≥ fi (x)) = 1 − Fξ0i (fi (x))
Thus, we can rewrite the constraint as follows
1 − Fξ0i (fi (x)) ≥ αi =⇒ −Fξ0i (fi (x)) ≥ αi − 1
=⇒ Fξ0i (fi (x)) ≤ 1 − αi =⇒ Fξ−1
0i
(Fξ0i (fi (x))) ≤ Fξ−1
0i
(1 − αi )
=⇒ fi (x) ≤ Fξ−1
0i
(1 − αi )
 3.1. CHANCE CONSTRAINTS 43

which is a deterministic constraint equivalent of the individual chance con-

straint. We simply need to compute Fξ−1 0i
(1 − α), the 1 − α-quantile of the
distribution of ξ0i .
With ≥-type constraint, the transformation is even simpler. A constraint
P (fi (x) ≥ ξ0i ) ≥ αi
can be rewritten as
Fξ0i (fi (x)) ≥ αi
which gives us the deterministic equivalent
fi (x) ≥ Fξ−1
0i
(αi )
There are other treatable cases. For example, when fi (x, ξ) ≤ 0 is a linear
constraint of type ξi⊤ x ≤ ξ0i , with ξi ∈ Rn and ξ0i = ξ0i fixed, and ξi follows
a multivariate normal distribution, one can prove that Ki (αi ) is convex. In
the case of joint chance constraints, one can show that, if fi (x, ξ) = fi (x)
for i = 1, . . . , m, i.e., the left-hand sides are deterministic and the right-hand
sides ξ0i follow a joint quasi-concave distribution (e.g., multivariate normal,
exponential, uniform) then the feasible region of the joint chance constraint,
i.e., K(α), is convex.
Nevertheless, chance-constrained problems are in general still largely in-
tractable except for some special cases. There are two primary reasons for this
difficulty:
(1) In general, for given x, computing P (fi (x, ξ) ≤ 0) accurately (thus
checking if x is feasible) can be hard. In the (typical) multidimen-
sional case, this task requires a multidimensional integration which
very often do not have analytical solutions, neither can be computed
numerically with high accuracy. In any case, this computation would
apply to an individual x. Solving the problem would still be an open
question.
(2) The feasible region of the problem is in general nonconvex. This en-
tails that, even if computing P (fi (x, ξ) ≤ 0) is easy (e.g., a closed
form expression exists), in general one has to solve a nonlinear non-
convex optimization problem, which is a challenging task on its own
and heavily depends on the particular functional form.

3.1.1. Chance-Constrained problems with discrete distributions.

When the distribution of ξ is discrete, chance-constrained problems become
easier to handle. Assume we have a finite number of possible outcomes ξ 1 , . . . , ξ K
with probabilities π 1 , . . . , π K . Then, it is possible to model both individual and
joint chance constraints as integer programming problems.
44 3. PROBABILISTIC PROGRAMMING

Consider an individual chance constraint of the form

P (fi (x, ξ) ≤ 0) ≥ αi
for some i. In case of a discrete distribution, the i-th constraint can be rewrit-
ten as
fi (x, ξ k )) ≤ 0 + Mik (1 − yik ) k = 1, . . . , K
K
X
π k yik ≥ αi
k=1
yik ∈ {0, 1} k = 1, . . . , K
Observe that the first set of constraints enforces the implication
yik = 1 =⇒ fi (x, ξ k ) ≤ 0
while the second set of constraints ensures that the cumulative probability of
the scenarios for which the constraint holds is larger than the desired αi . Here,
Mik is a constant that satisfies the inequality
Mik ≥ max fi (x, ξ k )
x
Consider now a joint chance constraint of the form
P (fi (x, ξ) ≤ 0, i = 1, . . . , m) ≥ α
The constraint can be rewritten as
fi (x, ξ k ) ≤ 0 + Mik (1 − yk ) i = 1, . . . , m, k = 1, . . . , K
K
X
πk y k ≥ α
k=1
yk ∈ {0, 1} k = 1, . . . , K
Observe that, in this case, the first set of constraints enforces the implication
yk = 1 =⇒ fi (x, ξ k ) ≤ 0, i = 1, . . . , m
To mitigate the computational challenges that arise when the random vari-
ables follow a continuous distribution, chance constraints are typically approxi-
mated. One such approximations is obtained by replacing the random variable
ξ by an empirical distribution corresponding to a Monte Carlo sample. That
is, K copies are taken of ξ, identical in their joint distribution1. From each,
a realization ξ k is taken and is assigned probability πk = K −1 . Then, the
1Let
X and Y two real-valued random variables defined on a probability space (Ω, F, P).
Let FX and FY their distributions. The random variables are equal if X(ω) = Y (ω) for all
ω ∈ Ω. The random variables are equal in distribution if FX (t) = FY (t) for all t ∈ R. In the
 3.2. MAXIMIZATION OF PROBABILITY 45

approximation is built by replacing the original ξ by the new discrete random

variable ξ 1 , . . . , ξ K . The resulting approximation is called a Sample Average
Approximation (SAA) and forms an integer programming problem as we have
seen before. Integer programming problems can themselves be difficulty to
solve. However, integer programming techniques can be used to ameliorate
this difficulty. Under reasonable regularity assumptions, requiring e.g., that X
is closed and convex and f (x) is continuous, it can be shown that the optimal
value and solution to the SAA converge to the optimal value and solution to
the original problem with probability one as K → ∞. Finally, observe that
SAA constraints
K
X 1
yk ≥ α
k=1
K
can be made tighter as follows
K
X
yk ≥ ⌈Kα⌉
k=1

3.2. Maximization of Probability

Chance constraints rely on target probabilities for the verification of desir-
able events. In some circumstances it might be difficult to express a realistic
probability of having certain events materialized. In this case, the possibility
emerges that target probabilities are either set conservatively low or unrealis-
tically high.
A possible solution in these cases is to optimize, that is, maximize or min-
imize probabilities. We take the perspective of a decision maker that wishes
to maximize the probability of certain desirable events. The problem becomes
(3.3) max P (fi (x, ξ) ≤ 0, i = 1, . . . , m)
x∈X

where the desirable event consists in the joint verification of the m inequalities
fi (x, ξ) ≤ 0, i = 1, . . . , m.
Problem (3.3) shares some of the difficulties illustrated for chance con-
straints. Primarily, the difficulty in precisely computing the probability for
given solutions x. Also in this case, numerical solution is simplified by the
availability of discrete/empirical distributions.
Consider the problem of maximizing the probability of verification of an
individual inequality. That is, problem (3.3) with m = 1. We let fi (x, ξ) =

latter care there is no evidence that the two random variables are equal. That is, in general
X(ω) ̸= Y (ω).
46 3. PROBABILISTIC PROGRAMMING

f (x, ξ). We can then write (3.3) as

maxα
f (x, ξ k )) ≤ 0 + Mk (1 − yk ) k = 1, . . . , K
K
X
π k yk ≥ α
k=1
yk ∈ {0, 1} k = 1, . . . , K
0≤α≤1
Observe that, in this problem, α is not a parameter but a decision variable.
Consider now the problem of maximizing the joint probability of verifica-
tion of m > 1 constraints. We obtain the problem
maxα
fi (x, ξ k ) ≤ 0 + Mik (1 − yk ) i = 1, . . . , m, k = 1, . . . , K
K
X
πk y k ≥ α
k=1
yk ∈ {0, 1} k = 1, . . . , K
0≤α≤1
 CHAPTER 4

Conditional Value at Risk

Conditional Value-at-Risk (CVaR) was born as a percentile measure of risk

alternative to VaR. CVaR is meant to represent the expectation of the loss,
conditional on it being greater than or equal to VaR. A number of alternative
definitions of CVaR exist. In what follows we focus on two of these which are
particularly relevant in the context of optimization.
Let us first recall some notation. For given x, let l(x, ξ) be a random
variable representing loss – or a quantity of which we want as little as possible.
As usual, it is to be understood as the random loss incurred as a consequence
of a particular decision x. To simplify exposition, let us refer to l(x, ξ) simply
as L, at least until x becomes necessary again. In fact, in the first part we
will discuss CVaR for a general loss random variable, independently of its use
in optimization. That is, for now we forget this loss is generated by some
decision x. We assume that E [L] < ∞ and let FL be the distribution function
of L, that is FL (z) = P ({ω ∈ Ω|l(x, ξ(ω)) ≤ z}). For now, we assume that
this distribution is known, though this assumption is usually not satisfied in
the context of optimization.
CVaR is meant to represent the expectation of L assuming that L is greater
than (or greater than or equal to) VaR. Mathematically, we have
(4.1) CVaRα (L) = E [L|L ≥ VaRα (L)]
This definition is sound for random variables L with continuous distribution
functions. However, as we will see, in the general case when FL has jumps – and
particularly when the distribution is discrete – this definition is problematic.
Indeed, the definition above may not represent the expectation in the 1 −
α tail of the distribution as the interval [VaRα (L) , ∞) may have a different
probability. Surprisingly, when L has a discrete distribution, CVaR is simply
not equal to the average of the outcomes larger than VaR. CVaR might have to
be obtained by averaging a fractional number of realizations of L. For this
reason, we will first address the case when FL is continuous and then the case
when FL admits jumps.
Before that, we provide a couple of results which will be useful in the rest
of the chapter.
47
48 4. CONDITIONAL VALUE AT RISK

Proposition 4.1. Assume E [L] < ∞. Then, for all z ∈ R

Z ∞
E [(L − z)+ ] = (1 − FL (t)) dt
z

Proof. We start by rewriting (L − z)+ as an integral. That is

Z ∞
max{0, L − z} = 1 (L > t) dt
z
Observe that the equivalence is indeed valid. For a given value L of L
we have
◦ If L ≤ z then L > t is always false for t ∈ [z, ∞). Then the
value of the integral is 0.
◦ If L > z we can write
Z ∞ Z L Z ∞
1 (L > t) dt = 1 dt + 0 dt = L − z
z z L
Therefore z 1 (L > t) dt = max{0, L − z} = (L − z)+ .
R∞
Let us now consider the random variable L and take the expectation
Z ∞ 
E 1 (L > t) dt
z
Since the integrand 1 (L > t) is nonnegative, we can swap the order of
integration. We obtain
Z ∞ Z ∞
E [1 (L > t)] dt = P (L > t) dt
z z
Z ∞
= 1 − P (L ≤ t) dt
z
Z ∞
= 1 − FL (t) dt
z
□

The next corollary provides some additional evidences on the quantity

E [(L − z)+ ].
 4.1. CVaR FOR CONTINUOUS DISTRIBUTIONS 49

Corollary 4.2. f (z) = E [(L − z)+ ] is convex and differentiable. Fur-

thermore, its derivative is
f ′ (z) = −(1 − FL (z))

4.1. CVaR for continuous distributions

In this section, we consider a loss random variable L with continuous distri-
bution. We start by introducing an alternative, equivalent, definition of CVaR.
This definition is
 
1
(4.2) CVaRα (L) = min z + E [(L − z)+ ]
z∈R 1−α

This definition appears, by now, less intuitive. However, it will turn out partic-
ularly useful in the context of optimization. We will now show that, assuming
L has a continuous distribution, the two definitions coincide. We proceed in
two steps. In each step we will show that each definition of CVaR is equivalent
to the quantity
1
VaRα (L) + E [(L − VaRα (L))+ ]
1−α
and hence are equal to each other.
Let us proceed with the first result showing that CVaR can be obtained as
the sum of VaR and the expectation of the loss above VaR.
Explain Stjeltes integral and integration wrt a distribution function.

Theorem 4.3. Given a random variable L with continuous and strictly

increasing distribution function FL we have that
CVaRα (L) =E [L|L ≥ VaRα (L)]
1
=VaRα (L) + E [(L − VaRα (L))+ ]
1−α

Proof. Following definition (4.1), we obtain.

E [L|L ≥ VaRα (L)]
Z ∞
1
= t dFL (t)
P(L ≥ VaRα (L)) VaRα (L)
50 4. CONDITIONAL VALUE AT RISK

Z ∞ 
1
= (t + VaRα (L) − VaRα (L)) dFL (t)
1−α VaRα (L)
Z ∞ Z ∞ 
1
= (t − VaRα (L)) dFL (t) + VaRα (L) dFL (t)
1−α VaRα (L) VaRα (L)
Z ∞ 
1
= (t − VaRα (L)) dFL (t) + VaRα (L) (1 − α)
1 − α VaRα (L)
Z ∞ 
1
=VaRα (L) + (t − VaRα (L))+ dFL (t)
1 − α −∞
1
=VaRα (L) + E [(L − VaRα (L))+ ]
1−α
□

We have hereby established the first equivalence. The following result

provides some information regarding the calculation of quantiles.

Proposition 4.4 (Quantiles). Given a random variable L and α ∈

(0, 1), arbitrary, the problem
(4.3) min {αE [(L − z)+ ] + (1 − α)E [(L − z)− ]}
z

has solution. Furthermore, any α-quantile is a solution (i.e., a minimizer)

to the problem. Note: (z)+ = max{0, z} and (z)− = max{0, −z}.

Proposition 4.4 is very often used in the context of Quantile Regression.

In Theorem 4.3 we have shown that (4.1) is equivalent to

1
VaRα (L) + E [(L − VaRα (L))+ ]
1−α

We will now show that the same equivalence can be made with the second
definition of CVaR, namely (4.2). This will essentially establish the equivalence
between the two definitions.

Proposition 4.5.
 
1 1
min z + E [(L − z)+ ] = VaRα (L) + E [(L − VaRα (L))+ ]
z∈R 1−α 1−α
 4.1. CVaR FOR CONTINUOUS DISTRIBUTIONS 51

Proof. Consider the argument of the minimization in (4.3) for a

given realization L of L, that is
α(L − z)+ + (1 − α)(L − z)−
Observe that n = (n)+ − (n)− and hence (n)− = (n)+ − n. Substituting
for (n)− we get
α(L − z)+ + (1 − α)(L − z)−
=α(L − z)+ + (1 − α)(L − z)+ − (1 − α)(L − z)
=(L − z)+ − (1 − α)(L − z)
=(L − z)+ + (1 − α)(z − L)
1−α
= (L − z)+ + (1 − α)(z − L)
1−α  
1
=(1 − α) z − L + (L − z)+
1−α
 
1
=(1 − α) z + (L − z)+ − (1 − α)L
1−α
Taking the again expectation, we can reformulate the problem as
   
1
min (1 − α) z + E [(L − z)+ ] − (1 − α)E [L]
z∈R 1−α
Since (1 − α) and E [L] are constants, we can simplify the problem
without changing its optimal solutions. We get
 
1
min z + E [(L − z)+ ]
z∈R 1−α
This corresponds to the left-hand-side in the statement of the proposi-
tion.
Recalling Proposition 4.1, the problem can be rewritten as
 Z ∞ 
1
min z + (1 − FL (t)) dt
z∈R 1−α z
Observe that the objective function is convex in z (see ??). So we have
the unconstrained minimization of a convex function. Therefore, to solve
the problem it is sufficient to find the values of z for which its derivative
takes value 0. That is,
1
1− (1 − FL (z)) = 0
1−α
52 4. CONDITIONAL VALUE AT RISK

Clearly, this holds when FL (z) = α. Thus, all the z which are α-quantiles
of FL solve this problem. In particular, it follows that z = VaRα (L) is
also an optimal solution. Thus, we obtain
 
1 1
min z + E [(L − z)+ ] = VaRα (L) + E [(L − VaRα (L))+ ]
z∈R 1−α 1−α
as required. □

Putting the two equations together, we obtain

CVaRα (L) =E [L|L ≥ VaRα (L)]
1
=VaRα (L) + E [(L − VaRα (L))+ ]
 1−α 
1
= min z + E [(L − z)+ ]
z∈R 1−α
Of particular importance in the context of optimization is the last equation
 
1
(4.4) CVaRα (L) = min z + E [(L − z)+ ]
z∈R 1−α
It states that CVaR can be found by solving a minimization problem. Thus,
CVaR can be calculated without first having to calculate VaR. Rather, the
second-last equation shows that VaR is obtained as a byproduct of the cal-
culation of CVaR. VaR is the solution to the minimization problem. Finally, the
optimization problem is convex in L and z. In fact, L − z is linear in L and
z, the composite function (L − z)+ = max{0, L − z} is convex in L and z,
and the expectation preserves convexity. Thus, CVaR emerges as the optimal
objective value of an unconstrained convex optimization problem.

4.2. CVaR for general distributions

Let us formalize a bit this situation. Having defined FL (z) = P (L ≤ z) let
us introduce the probability of L being strictly smaller than z.

Definition 4.6 (Left-limit of FL ). For z ∈ R and a random variable L

with distribution function FL we define
FL (z − ) = P (L < z)

This allows us to characterize a probability atom.

 4.2. CVaR FOR GENERAL DISTRIBUTIONS 53

Definition 4.7 (Probability atom). We say that z is an atom if

FL (z) − FL (z − ) = P (L = z) > 0

This situation is illustrated in the following example.

Example 4.1. Consider an experiment where we roll a dice and whe

let our random variable L be the number shown on the face of the
dice. Clearly, the distribution of L is discrete and its distribution is a
step function with support {1, . . . , 6}. The distribution is illustrated in
Figure 4.1.
It is easy to see that every element of the support is an atom. Take, for
example L = 3. We have
FL (3)−FL (3− ) = P (L ≤ 3)−P (L < 3) = 3/6−2/6 = 1/6 = P (L = 3) > 0

Figure 4.1. Distribution of the random variable L.

54 4. CONDITIONAL VALUE AT RISK

Recall the definition of VaR

VaRα (L) = min{z|FL (z) ≥ α}
Note that, since FL is a distribution function, it is right-continuous, hence the
minimum exists. When FL is continuous and strictly increasing, then VaRα (L)
is the unique α-quantile z that satisfies
FL (z) = α
On the other hand, if FL is not strictly increasing, then it has flat zones,
see, e.g., Figure 4.1. In this case, there are multiple solutions z that satisfy
FL (z) = α. Simply speaking, all the z in the flat intervals share the same
cumulative distribution. In this case VaRα (L) is still uniquely determined as
the lower end-point of the interval of z values that satisfy the equality. The
upper end point is defined as follows

Definition 4.8 (Upper VaR). The upper-VaR is defined as

VaR+
α (L) = inf{z|FL (z) > α}

The values VaRα (L) and VaR+ α (L) are always the same, except for the
case when FL (z) is constant at level α over an interval of values z. The
interval is [VaRα (L) , VaR+ +
α (L)) if there is a jump at VaRα (L), otherwise it is
[VaRα (L) , VaRα (L)]. In the latter case the function is continuous at VaR+
+
α (L)
+
and resumes increasing after VaRα (L), though without a jump.

Example 4.2. Consider again Example 4.1. Observe that for all z ∈
[3, 4) we have
FL (z) = P (L ≤ z) = 3/6
Therefore, we have VaR3/6 (L) = 3 and VaR+
3/6 (L) = 4.

If there is an atom at VaRα (L), then there exists an interval of values of α

which give the same value of VaRα (L). That is, the least value for which the
probability becomes at least α might be the same. In this case, the graph of
FL has a vertical gap with vertical endpoints
α− (L, α) = P (L < VaRα (L))
and
α+ (L, α) = P (L ≤ VaRα (L)) = FL (VaRα (L))
 4.2. CVaR FOR GENERAL DISTRIBUTIONS 55

Example 4.3. Consider again Example 4.1. If we let α = 7/12 = 0.58,

we obtain that
VaR7/12 (L) = min{z|FL (z) ≥ 7/12} = 4
The graph of FL has a vertical jump with endpoints
α− (L, α) = P L < VaR7/12 (L) = P (L < 4) = 3/6

and
α+ (L, α) = P L ≤ VaR7/12 (L) = FL (VaR7/12 (L)) = 4/6

In this case, the equation P (L ≤ z) = FL (z) = α has no solutions z if

α ∈ (α− (L, α), α+ (L, α)).
The cases illustrated above raise challenges in the treatment of general loss
distributions. Observe, for example, how in the case with flat areas, a small
change in the confidence level α determines a big jump in the value of VaR.
These situations are particularly true for discrete distributions, since their FL
is a step function, constant between jumps.

Example 4.4. Consider again Example 4.1. If we let α = 3/6 = 0.50,

we obtain that VaR3/6 (L) = min{z|FL (z) ≥ 3/6} = 3. However, if
we let α = 3/6 + 1/100 = 306/600 = 0.51, we obtain VaR0.51 (L) =
min{z|FL (z) ≥ 0.5} = 4. That is, to increase the confidence level of
just 1/100 we need to go past the entire flat area [3, 4) and settle for
VaR0.51 (L) = 4. Hence, a marginal increase in the confidence level de-
termines a significant jump in VaR.

Also the definition of CVaR becomes problematic in the case of general

distributions. Identifying CVaR as the mean in the α-tail distribution is not
straightforward anymore. Consider the case where the loss distribution has
a jump at VaRα (L) and α− (L, α) < α < α+ (L, α). In that case, the in-
terval [VaRα (L) , ∞) has probability larger than 1 − α. In fact, the interval
[VaRα (L) , ∞) has probability 1 − P (L < VaRα (L)) = 1 − α− (L, α). Now,
α− (L, α) < α < FL (VaRα (L)) = α+ (L, α). Hence, 1 − P (L < VaRα (L)) >
1 − α.
If we instead consider the interval (VaRα (L) , ∞), this interval has prob-
ability 1 − FL (VaRα (L)) = 1 − α+ (L, α), which is smaller than 1 − α since
56 4. CONDITIONAL VALUE AT RISK

FL (VaRα (L)) > α1. Hence, neither the interval (VaRα (L) , ∞) nor the interval
[VaRα (L) , ∞) represent the interval of probability 1 − α we are looking for. In
this case, the issue materializes of what should be meant by the 1 − α-tail of
the distribution.

Example 4.5. Consider again Example 4.1. If we let α = 3/6 = 0.50.

The distribution has a jump at VaR0.50 (L) = 3. We would expect to
define CVaR0.5 (L) as the expectation of the 1 − 0.5 tail of the distribu-
tion of L. However, the interval [VaR0.50 (L) , ∞) = [3, ∞) has prob-
ability 1 − P (L < 3) = 1 − 2/6 = 4/6 = 0.66 > 1 − 0.5. The in-
terval (VaR0.50 (L) , ∞) has probability 1 − FL (VaRα (L)) = 1 − 3/6 =
0.5. Hence, the probabilities of the intervals [VaR0.50 (L) , ∞) and
(VaR0.50 (L) , ∞) are different, and only the latter interval has proba-
bility 1 − α. Observe, that in this case α = α+ (L, α).
Let now α = 7/12 = 0.58. Then VaR0.58 (L) = 4. We would expect to
define CVaR0.58 (L) as the expectation of the 1 − 0.58 = 0.42 tail of the
distribution of L. However, the interval [VaR0.58 (L) , ∞) = [4, ∞) has
probability 1−P (L < 4) = 1−3/6 = 0.50 > 0.42. Similarly, the interval
(VaR0.55 (L) , ∞) has probability 1 − FL (VaR0.58 (L)) = 1 − 4/6 = 1/3 =
0.33 < 0.42. Hence, the probabilities of the intervals [VaR0.58 (L) , ∞)
and (VaR0.58 (L) , ∞) are different, and neither intervals have probability
1 − α. In this case 3/6 = α− (L, α) < α < α+ (L, α) = 4/6.

This issue is resolved by defining a specific α-tail distribution as follows.

Definition 4.9 (Generalized α-tail distribution.). Let L be a random

variable with distribution function FL . We define the generalized α-tail
distribution FLα : R → [0, 1] as
(
0 if z < VaRα (L)
FLα (z) = FL (z)−α
1−α
if z ≥ VaRα (L)

The generalized distribution assigns positive probability only to the in-

terval [VaRα (L) , ∞) and zero to (−∞, VaRα (L)). It is truly a distribution
function. In fact, it inherits from FL the properties of being non-decreasing
and right-continuous (it is simply FL shifted by α and scaled by (1−α)−1 > 0).
Furthermore, it is easy to verify that FLα (z) → 1 as z → ∞: when FL (z) = 1
1(Observe that only in the case where α = α+ (L, α) we obtain that the interval
(VaRα (L) , ∞) has probability 1 − α).
 4.2. CVaR FOR GENERAL DISTRIBUTIONS 57

also FLα (z) = 1. FLα rescales the portion of the graph of FL between the
horizontal lines at levels α and 1 so that it spans instead between 0 and 1.

Example 4.6. Consider again Example 4.1. Let α = 3/6 = 0.50. We

have that VaR0.5 (L) = 3 and
FL (3) − α 3/6 − 0.5
FLα (3) = = =0
1−α 1 − 0.5
Consider the point z = 4 ≥ VaR0.5 (L). We have that
FL (4) − α 4/6 − 0.5
FLα (4) = = = 0.33
1−α 1 − 0.5
Finally, consider the point z = 6 ≥ VaR0.5 (L). We have that
FL (6) − α 1 − 0.5
FLα (6) = = =1
1−α 1 − 0.5
Let α = 7/12 = 0.58. We have that VaR0.58 (L) = 4 and
FL (4) − α 4/6 − 7/12 1/12
FLα (4) = = = = 1/5 = 0.2
1−α 1 − 7/12 5/12
7/12
Hence, FL assigns probability 0.2 to VaR7/12 (L), scaling it down from
4/6 = 0.66. Observe that this probability is α+ (L, α)−α = 4/6−7/12 =
1/12 scaled by 1 − α. Consider the point z = 5 ≥ VaR0.57 (L). We have
that
FL (5) − α 5/6 − 7/12
FLα (5) = = = 3/5
1−α 1 − 7/12
Finally, consider the point z = 6 ≥ VaR0.58 (L). We have that
FL (6) − α 1 − 7/12
FLα (6) = = =1
1−α 1 − 7/12

Notice how FLα (z) splits the VaRα (L) atom into a piece of probability
α+ (L, α) − α and a piece of probability α − α− (L, α) (both scaled by 1 − α).
Adjoining the α+ (L, α) − α-probability piece to the interval (VaRα (L) , ∞)
effectively yields an interval of probability 1 − α inasmuch
(α+ (L, α) − α) + (1 − α+ (L, α)) = 1 − α
which becomes 1 after the scaling. Notice that, if the probablity atom could
not be split, we would have to choose between the intervals (VaRα (L) , ∞) and
[VaRα (L) , ∞). Neither of these has probability 1 − α.
It is now useful to introduce the expectations over the intervals (VaRα (L) , ∞)
and [VaRα (L) , ∞). We will call them “upper” and “lower” CVaR, respectively.
58 4. CONDITIONAL VALUE AT RISK

We will see that when FL is continuous and strictly increasing, the two quanti-
ties are identical and coincide with CVaR. This is however, not necessarily true
in more general cases.

Definition 4.10 (CVaR). The CVaR is defined as

(4.5) CVaRα (L) = EFLα [L]
It corresponds to the expectation of the loss distribution associated with
the generalized α-tail distribution function.

Definition 4.11 (Upper and Lower CVaR). The upper CVaR is defined
as
(4.6) CVaR+
α (L) = E [L|L > VaRα (L)]
The lower CVaR is defined as
(4.7) CVaR−
α (L) = E [L|L ≥ VaRα (L)]

Observe that the difference is only in the strictness of the inequality. The
argument of the upper CVaR spans from VaRα (L), exclusive, to ∞. The argu-
ment of the lower CVaR spans from VaRα (L), inclusive, to ∞. Hence the term
lower indicates that it starts from a smaller value (VaRα (L)), while the term
upper indicates that is starts past the value of VaRα (L).
Observe also that CVaR−α (L) always exists. This is because P (L ≥ VaRα (L)) ≥
1 − α > 0 if α ∈ (0, 1). However, CVaR+ α (L) only makes sense as long as
P (L > VaRα (L)) > 0, that is, when FL (VaRα (L)) < 1. This does not neces-
sarily follow from having α ∈ (0, 1) since there might be an atom at VaRα (L)
of probability large enough to cover the interval 1 − α− (L, α).
To align with the new definition of CVaRα (L) = EFLα [L], we can also see the
upper CVaR as CVaR+ α (L) = EFL α+ [L] that is as the mean of the loss distribution

associated with the distribution function

(
0 if z < VaRα (L)
FLα+ (z) = FL (z)−α+ (L,α)
1−α+ (L,α)
if z ≥ VaRα (L)

Compared to FLα , FLα+ does not split the VaRα (L) atom. On the contrary,
it assigns probability zero to it. Hence, probabilty mass is only assigned to
values in the interval (VaRα (L) , ∞). Similarly, we can see the lower CVaR as
CVaR−α (L) = EF α− [L] that is as the mean of the loss distribution associated
L
 4.2. CVaR FOR GENERAL DISTRIBUTIONS 59

with
(
0 if z < VaRα (L)
FLα− (z) = FL (z)−α− (L,α)
1−α− (L,α)
if z ≥ VaRα (L)

Compared to FLα , FLα− does not split the VaRα (L) atom. Rather, it assigns to
the atom the entire probability of the jump, that is α+ (L, α) − α− (L, α).
For general distribution functions the lower CVaR and the upper CVaR may
be different. In addition, the lower CVaR is in general discontinuous and non-
convex with respect to α. In what follows, we summarize the relationship
between CVaR and upper and lower CVaR by means of a number of propositions.
Before that, we provide a useful fact.

Proposition 4.12. Consider z ∈ R with FL (z) < 1. Then, the function

ΓL (α, z) := FLα (z) is decreasing in α.

Proof. We have
FL (z) − α
ΓL (α, z) = FLα (z) =
1−α
and
dΓL (α, z) FL (z) − 1
= <0
dα (1 − α)2
Therefore, ΓL (α, z) is decreasing in α. □

Proposition 4.12 shows that, for given z ∈ R, we have FLα1 (z) > FLα2 (z) for
α1 < α2 . It is also easy to see that FLα1 (z) = FLα2 (z) only when FL (z) = 1.

Proposition 4.13. Assume that there is no probability atom at

VaRα (L). Then
CVaR− +
α (L) = CVaRα (L) = CVaRα (L)

Proof. If there is no jump at VaRα (L) then we have α+ (L, α) =

α = α− (L, α). This, in turn, implies FLα− (z) = FLα+ (z) = FL (z) for all
z ∈ R. Hence, the definitions of CVaR− +
α (L), CVaRα (L) and CVaRα (L)
coincide. □
60 4. CONDITIONAL VALUE AT RISK

Proposition 4.14. Assume a probability atom at VaRα (L) exists and

FL (VaRα (L)− ) = P (L < VaRα (L)) = α− (L, α) < α < FL (VaRα (L)) =
α+ (L, α) < 1 one has
CVaR− +
α (L) < CVaRα (L) < CVaRα (L)

Warning 4.15. This proof is a work in progress. Not all details have
been carefully verified. Use it as an exercise. Feedback is welcome! Do
you see a simpler strategy?

Proof. Recall that

◦ CVaR− α (L) = EFL α− [L]

◦ CVaRα (L) = EFLα [L]

◦ CVaR+ α (L) = EFL α+ [L]

In particular, the distribution functions change only for the value of α

used.
Let us consider, without loss of generality, CVaRα (L). We have
Z ∞
CVaRα (L) = L dFLα ← Stieltjes integral (a density is not assumed)
−∞
Z ∞
= L dµFLα ← Lebesgue integral wrt Lebesgue-Stieltjes measure Definition A.12
−∞
Z Z
= L dµFLα + L dµFLα
(−∞,VaRα (L)) [VaRα (L),∞)
| {z }
=0
Z
= VaRα (L) + L − VaRα (L) dµFLα
[VaRα (L),∞)
Z Z
=VaRα (L) dµFLα + L − VaRα (L) dµFLα
[VaRα (L),∞) [VaRα (L),∞)
| {z }
=1
Z
=VaRα (L) + (L − VaRα (L))+ dµFLα
[VaRα (L),∞)
| {z }
L≥VaRα (L)
 4.2. CVaR FOR GENERAL DISTRIBUTIONS 61

Z
+ (L − VaRα (L))+ dµFLα
(−∞,VaRα (L))
| {z }
=0
=VaRα (L) + EFLα [(L − VaRα (L))+ ]
Z ∞
=VaRα (L) + (1 − FLα (t)) dt
VaRα (L)
| {z }
Proposition 4.1

By Proposition 4.12, it follows that, for all t with FL (t) < 1, we have
(4.8) FLα− (t) > FLα (t) > FLα+ (t)
The three values are equal only in the point t for which FL (t) = 1.
However, since α+ (L, α) < 1 we known that this value t does not have
all the probability mass.
By inequalities (4.8) and monotonicity of integrals, it follows that
Z ∞
VaRα (L) + (1 − FLα− (t)) dt = CVaR−
α (L)
VaRα (L)
Z ∞
<VaRα (L) + (1 − FLα (t)) dt = CVaRα (L)
VaR (L)
Z ∞α
<VaRα (L) + (1 − FLα+ (t)) dt = CVaR+
α (L)
VaRα (L)

Which completes the proof. □

Corollary 4.16. Assume a probability atom at VaRα (L) exists and

FL (VaRα (L)) = α. Then
CVaR− +
α (L) < CVaRα (L) = CVaRα (L)

Proof. The proof follows the same logic as for Proposition 4.14 with
the exception that we have α+ (L, α) = α. □

Proposition 4.17. Assume a probability atom at VaRα (L) exists and

FL (VaRα (L)) = 1. Then
CVaR−
α (L) = CVaRα (L) = VaRα (L)
62 4. CONDITIONAL VALUE AT RISK

and CVaR+
α (L) is undefined.

Proof. When a probability atom at VaRα (L) exists and

FL (VaRα (L)) = 1 we have that α+ (L, α) = 1 = FL (VaRα (L)) = 1.
Following, FLα+ is ill-defined inasmuch as FL (z) − α+ (L, α) = 0 for all
α−
z ≥ VaRα (L). Consequently, CVaR+ α (L) is ill-defined too. Then, FL
α− − −
assigns probability FL (VaRα (L)) − α (L, α)/(1 − α (L, α)) = 1 and
FLα assigns probability FL (VaRα (L))−α/(1−α) = 1 to VaRα (L). Hence,
CVaR−α (L) = CVaRα (L) = VaRα (L). □

We can now show that CVaRα (L) can also be expressed as a weighted
average of VaRα (L) and CVaR+
α (L).

Proposition 4.18 (CVaR as a weighted average). Let λα (L) be the prob-

ability assigned to VaRα (L) by FLα , that is
FL (V aRα (L)) − α
λα (L) =
1−α
If FL (VaRα (L)) < 1 then
CVaRα (L) = λα (L)VaRα (L) + (1 − λα (L))CVaR+
α (L)
If FL (VaRα (L)) = 1 then
CVaRα (L) = VaRα (L)

Proof. Consider the case when FL (VaRα (L)) < 1. Observe that in
this case FLα assigns to VaRα (L) probability FL (VaR1−α
α (L))−α
. The remaining
1−FL (VaRα (L))
part of the α-tail distribution has probability 1−α
, so that
FL (VaRα (L)) − α 1 − FL (VaRα (L)) 1−α
+ = =1
1−α 1−α 1−α
Hence, the expectation in the α-tail of the distribution must be
 
FL (VaRα (L)) − α FL (VaRα (L)) − α
CVaRα (L) = VaRα (L)+ 1 − CVaR+
α (L)
1−α 1−α
That is
CVaRα (L) = λα (L)VaRα (L) + (1 − λα (L)) CVaR+
α (L)
 4.2. CVaR FOR GENERAL DISTRIBUTIONS 63

For the case FL (VaRα (L)) = 1 the equality is provided by Proposi-

tion 4.17. □

Corollary 4.19.
CVaRα (L) ≥ VaRα (L)

Proof. This is evident from Proposition 4.18. Particularly,

CVaRα (L) > VaRα (L) always except for the case when FL (VaRα (L)) =
1. □

Corollary 4.20.
1
CVaRα (L) = VaRα (L) + E [(L − VaRα (L))+ ]
1−α

Proof. For the case FL (VaRα (L)) = 1 the equality is provided by

Proposition 4.17.
For FL (VaRα (L)) < 1 Proposition 4.18 shows that
CVaRα (L) = λα (L)VaRα (L) + (1 − λα (L))CVaR+
α (L)
with
FL (VaRα (L)) − α
λα (L) =
1−α
Therefore, we obtain
CVaRα (L) =λα (L)VaRα (L) + (1 − λα (L))CVaR+
α (L)
=λα (L)VaRα (L) + (1 − λα (L))E [L|L > VaRα (L)]
=λα (L)VaRα (L) + (1 − λα (L))E [L + VaRα (L) − VaRα (L) |L > VaRα (L)]
=λα (L)VaRα (L) + (1 − λα (L)) (VaRα (L) + E [L − VaRα (L) |L > VaRα (L)])
=VaRα (L) + (1 − λα (L))E [L − VaRα (L) |L > VaRα (L)]
1
=VaRα (L) + (1 − λα (L)) E [(L − VaRα (L))+ ]
P (L > VaRα (L))
1
=VaRα (L) + (1 − λα (L)) E [(L − VaRα (L))+ ]
1 − FL (VaRα (L)
64 4. CONDITIONAL VALUE AT RISK

 
FL (VaRα (L)) − α 1
=VaRα (L) + 1 − E [(L − VaRα (L))+ ]
1−α 1 − FL (VaRα (L)
 
1 − FL (VaRα (L)) 1
=VaRα (L) + E [(L − VaRα (L))+ ]
1−α 1 − FL (VaRα (L)
1
=VaRα (L) + E [(L − VaRα (L))+ ]
1−α
Obtaining the claimed result. □

Proposition 4.21 (CVaR for scenario models). Assume L follows a dis-

crete distribution with support over the points L1 < L2 < · · · < LS and
probabilities π1 , . . . , πS > 0. So FL is a step function with jumps at
those points. Let sα be the unique index such that
sα
X α −1
sX
πs ≥ α > πs
s=1 s=1
Then
VaRα (L) = Lsα
and " s #
α S
1 X X
CVaRα (L) = ( πs − α)Lsα + πs L s
1 − α s=1 s=s +1 α

Proof. TBD. □

Example 4.7. Consider again Example 4.1.

Let α = 4/6. We have that VaR4/6 (L) = 4 and FL (4) = α+ (L, α) =
4/6 therefore in this case α+ (L, α) = α. Furthermore, α− (L, α) =
P (L < 4) = 3/6.
Let us compute the lower CVaR.
1 1 1 1
CVaR−
4/6 (L) =E [L|L ≥ 4] = [ 4 + 5 + 6]
P (L ≥ 4) 6 6 6
1 1 1 1
= [ 4 + 5 + 6]
1 − P (L < 4) 6 6 6
 4.2. CVaR FOR GENERAL DISTRIBUTIONS 65

1 1 1 1
= [ 4 + 5 + 6]
1− α− (L, α) 6 6 6
1 15
= [ ]=5
1 − 3/6 6
Let us compute the upper CVaR.
1 1 1
CVaR+
4/6 (L) =E [L|L > 4] = [ 5 + 6]
P (L > 4) 6 6
1 1 1
= [ 5 + 6]
1 − P (L ≤ 4) 6 6
1 1 1
= +
[ 5 + 6]
1 − α (L, α) 6 6
1 11
= [ ] = 5.5
1 − 4/6 6
Let us compute CVaR from the formula in Proposition 4.18. We obtain
FL (4) − 4/6
λ4/6 (L) = =0
1 − 4/6
hence
CVaR4/6 (L) = λ4/6 (L)VaR4/6 (L)+ 1 − λ4/6 (L) CVaR+


4/6 (L) = 0∗4+1∗5.5

Hence, coherently with Corollary 4.16 we obtain that if FL (VaRα (L)) =

α then CVaRα (L) = CVaR+α (L).

Example 4.8. Consider again Example 4.1.

Let α = 11/12. We have that VaR11/12 (L) = 6 and FL (6) = α+ (L, α) =
6/6 = 1 therefore in this case FL (VaR11/12 (L)) = 1. Furthermore,
α− (L, α) = P (L < 6) = 5/6.
Let us compute the lower CVaR.
1 1
CVaR−11/12 (L) =E [L|L ≥ 6] = [ 6]
P (L ≥ 6) 6
1 1
= [ 6]
1 − P (L < 6) 6
1 1
= −
[ 6]
1 − α (L, α) 6
66 4. CONDITIONAL VALUE AT RISK

1 6
= [ ]=6
1 − 5/6 6
Let us compute the upper CVaR.
CVaR+
11/12 (L) =E [L|L > 6]

which is undefined. Let us compute CVaR from the formula in Proposi-

tion 4.18. We obtain
FL (6) − 11/12 1 − 11/12
λ11/12 (L) = = =1
1 − 11/12 1 − 11/12
hence
CVaR11/12 (L) = λ11/12 (L)VaR11/12 (L)+ 1 − λ11/12 (L) CVaR+


11/12 (L) = 1∗6+0 = 6

Hence, coherently with Proposition 4.17 we obtain that if

FL (VaRα (L)) = 1 then CVaRα (L) = CVaR−
α (L) = VaRα (L) and
+
CVaRα (L) is undefined.

Example 4.9. Consider again Example 4.1.

Let α = 9/12. We have that VaR9/12 (L) = 5 and FL (5) = α+ (L, α) =
5/6. Furthermore, α− (L, α) = P (L < 5) = 4/6. Therefore in this case
α+ (L, α) = FL (VaR9/12 (L)) > α > α− (L, α).
Let us compute the lower CVaR.
1 1 1
CVaR−9/12 (L) =E [L|L ≥ 5] = [ 5 + 6]
P (L ≥ 5) 6 6
1 1 1
= [ 5 + 6]
1 − P (L < 5) 6 6
1 1 1
= −
[ 5 + 6]
1 − α (L, α) 6 6
1 1 1
= [ 5 + 6] = 5.5
1 − 4/6 6 6
Let us compute the upper CVaR.
1 1
CVaR+ 9/12 (L) =E [L|L > 5] = [ 6]
P (L > 5) 6
1 1
= [ 6]
1 − P (L ≤ 5) 6
 4.2. CVaR FOR GENERAL DISTRIBUTIONS 67

1 1
= [ 6]
1−α+ (L, α) 6
1 6
= [ ]=6
1 − 5/6 6
Let us compute CVaR from the formula in Proposition 4.18. We obtain
FL (5) − 9/12 10/12 − 9/12
λ9/12 (L) = = = 1/3
1 − 9/12 1 − 9/12
hence
1 2
CVaR9/12 (L) = λ9/12 (L)VaR9/12 (L)+ 1 − λ9/12 (L) CVaR+


9/12 (L) = 5+ 6 = 5.66
3 3
+
Hence, coherently with Proposition 4.17 we obtain that if α (L, α) =
FL (VaR9/12 (L)) > α > α− (L, α) then CVaR− α (L) < CVaRα (L) <
+
CVaRα (L).

We now return to the formula introduced in the discussion about CVaR for
continuous distributions, that is
1
Gα (L, z) = z + E [(L − z)+ ]
1−α
We move towards showing that, as in the continuous case, the minimization
of this formula yields CVaR.

Proposition 4.22. As a function of z Gα (L, z) is convex and bounded,

hence continuous.

Proof. The first term of Gα (L, z) is linear in z. In the second term

is the max function is convex, the inner function L − z is convex and
the expectation preserves convexity. Hence, the function is convex in z.
Gα (L, z) < ∞ follows from the assumption that L ∈ L1 (Ω, F, P). Since
the function is convex and bounded it is also continuous. □

Remark 4.23. Gα (L, z) is not necessarily differentiable.

Proposition 4.24. VaRα (L) ∈ argminz∈R Gα (L, z)

68 4. CONDITIONAL VALUE AT RISK

Proof. We start from the fact that Gα (L, z) is convex, bounded and
continuous in z, see Proposition 4.22. Hence, minimizing with respect
to z yields a convex unconstrained optimization problem. A necessary
condition for optimality is that the minimizer is a stationary point, that
is the value of the first derivative is zero at the minimizer. In addition,
for a convex unconstrained optimization problem this condition is also
sufficient.
However, the above conditions do not guarantee the existence of a min-
imizer. This is something we need to find out. Unfortunately, this
will not be as easy as finding whethere a root of the first derivative of
Gα (L, z) exists. In fact, Gα (L, z) is not necessarily differentiable, see
Remark 4.23. Having Gα (L, z) convex and bounded in z ensures that it
has left and right derivatives at any point z, and that both derivatives
are non-decreasing functions of z, [R. 70, Theorem 24.1]. Nevertheless,
the two derivatives may be different. The first task in this proof is now
that of finding an expression for the left and right derivatives.
We start by formulating the difference quotient
Gα (L, z ′ ) − Gα (L, z) z ′ + 1−α E [(L − z ′ )+ ] − z + 1−α E [(L − z)+ ]
1 1
=
z′ − z z′ − z
z − z + 1−α E [(L − z ′ )+ − (L − z)+ ]
′ 1
=
z′ − z
1
E [(L − z ′ )+ − (L − z)+ ]
=1 + 1−α ′
 z − z′ 
1 (L − z )+ − (L − z)+
=1 + E
1−α z′ − z
Let us begin with the right derivative. Assume z ′ > z and let us assess
the argument of the expectation in the difference quotient

−1 if L > z ′
(L − z ′ )+ − (L − z)+ 
= 0 if L ≤ z
z′ − z ∈ [−1, 0) if z < L ≤ z ′


Observe that for L = z ′ the fraction takes value −1. Let us now check
the expectation of this quantity. This expectation can be written as
−1P (L > z ′ ) + ζP (z < L ≤ z ′ )
Now, P (L > z ′ ) = 1 − P (L ≤ z ′ ) = 1 − FL (z ′ ) and P (z < L ≤ z ′ ) =
1 − P (L ≤ z) − P (L > z ′ ) = 1 − FL (z) − (1 − FL (z ′ )) = 1 − FL (z) − 1 +
 4.2. CVaR FOR GENERAL DISTRIBUTIONS 69

FL (z ′ ) = −FL (z) + FL (z ′ ). Therefore, we obtain that

(L − z ′ )+ − (L − z)+
 
E ′
= −1(1 − FL (z ′ )) + ζ(FL (z ′ ) − FL (z))
z −z
with ζ ∈ (0, −1]. Observe that FL (z ′ ) ↘ FL (z) as z ′ ↘ z. Therefore,
(L − z ′ )+ − (L − z)+
 
lim E ′
= lim −1(1−FL (z ′ ))+ζ(FL (z ′ )−FL (z)) = −(1−FL (z))
′
z ↘z z −z ′
z ↘z

Returning to the difference quotient we obtain

Gα (L, z ′ ) − Gα (L, z ′ ) (L − z ′ )+ − (L − z)+
 
1
lim = lim 1+ E
z ′ ↘z z′ − z z ′ ↘z 1−α z′ − z
1 1 − α + FL (z) − 1
=1 + (FL (z) − 1) =
1−α 1−α
FL (z) − α
=
1−α
Let us focus now on the left derivative. Assume z ′ < z and let us assess
the argument of the expectation in the difference quotient
 
−1 if L > z −1 if L ≥ z
(L − z ′ )+ − (L − z)+

 
′
= 0 if L ≤ z = 0 if L ≤ z ′
z′ − z ∈ [−1, 0) if z ′ < L ≤ z ∈ [−1, 0) if z ′ < L < z
 

The equivalent definitions are possible due continuity of the fraction in

L at the points L = z and L = z ′ . Let us now check the expectation of
this quantity. This expectation can be written as
−1P (L ≥ z) + ζP (z ′ < L < z)
with ζ ∈ (−1, 0). Now, P (L ≥ z) = 1 − P (L < z) = 1 − FL (z − ).
Likewise, P (z ′ < L < z) = 1 − P (L ≤ z ′ ) − P (L ≥ z) = 1 − FL (z ′ ) −
(1 − FL (z − )) = 1 − FL (z ′ ) − 1 + FL (z − ) = −FL (z ′ ) + FL (z − ). Therefore,
we obtain that
(L − z ′ )+ − (L − z)+
 
E ′
= −1(1 − FL (z − )) + ζ(FL (z − ) − FL (z ′ ))
z −z
with ζ ∈ (−1, 0). Observe that, since the distribution of L is not nec-
essarily left continuous, we have that FL (z ′ ) ↗ P (L < z) = FL (z − ) as
z ′ ↗ z. Therefore,
(L − z ′ )+ − (L − z)+
 
lim E ′
= lim −1(1−FL (z ′ ))+ζ(FL (z − )−FL (z ′ )) = −(1−FL (z − ))
z ′ ↗z z −z z ′ ↗z
70 4. CONDITIONAL VALUE AT RISK

Returning to the difference quotient we obtain

Gα (L, z ′ ) − Gα (L, z ′ ) (L − z ′ )+ − (L − z)+
 
1
lim = lim 1+ E
z ′ ↗z z′ − z z ′ ↗z 1−α z′ − z
1 1 − α + FL (z − ) − 1
=1 + (FL (z − ) − 1) =
1−α 1−α
FL (z − ) − α
=
1−α
We have now obtained expressions for the left and right derivatives, that
is, respectively
d− Gα (L, z) FL (z − ) − α
=
dz 1−α
and
d+ Gα (L, z) FL (z) − α
=
dz 1−α
We have already mentioned above that these two functions are non-
decreasing in z. However, this is also evident from their expressions since
FL is non-decreasing and α is constant. To assess whether optimizers
exist, let us study their asymptotic behavior. We have that
d− Gα (L, z) FL (z − ) − α
lim = lim =1
z→∞ dz z→∞ 1−α
and
d+ Gα (L, z) FL (z) − α
lim = lim =1
z→∞ dz z→∞ 1−α
Furthermore,
d− Gα (L, z) FL (z − ) − α α
lim = lim =− <0
z→−∞ dz z→−∞ 1−α 1−α
and
d+ Gα (L, z) FL (z) − α α
lim = lim =− <0
z→−∞ dz z→−∞ 1−α 1−α
Thus, asymptotically, the two derivarives coincide. The derivatives are
negative towars −∞ and positive towards ∞. This entails that Gα
decreases and then increases. In addition, this entails that the level sets
{z ∈ R|Gα (L, z) ≤ c} are bounded for every choice of c ∈ R. That is,
given an arbitrary choice of c, the values of z for which Gα (L, z) ≤ c are
bounded, as the function will eventually increase above c when moving
towards −∞ or +∞. Since this is valid for every c, this is also value for
the minimum value of minz∈R Gα (L, z): that is, the minumum is attained
 4.3. COHERENCE OF CVAR 71

in a bounded interval, which might be a single point. Furthermore, we

−
know from [R. 70, Theorem 24.1] that for all z ∈ R we have d Gdz α (L,z)
≤
d+ Gα (L,z)
dz
. Particularly, the mimimizers are characterized by the fact that
d− Gα (L, z) d+ Gα (L, z)
≤0≤
dz dz
This is due to the fact that the derivative at the minimizer is null (nec-
essary condition of optimality). A strict inequality characterizes unique
minimizers, otherwise, if there are multiple minimizers we might indeed
have an equality. Substituting the expression of the derivatives we obtain
FL (z − ) − α FL (z) − α
≤0≤
1−α 1−α
or
FL (z − ) − α ≤ 0 ≤ FL (z) − α
From here, we obtain that the values of z that satisfy this chain of
inequalities are those that give
FL (z − ) ≤ α ≤ FL (z)
The lowest value that satisfies this inequality VaRα (L) while the highest
value is VaR+
α (L). This completes the proof. □

Corollary 4.25. CVaRα (L) = minz∈R Gα (L, z)

Proof. This follows immediately from Proposition 4.24, where we

learn that
1
min Gα (L, z) = Gα (L, VaRα (L)) = VaRα (L)+ E [(L − VaRα (L))+ ]
z∈R 1−α
and Corollary 4.20 where we learn that
1
VaRα (L) + E [(L − VaRα (L))+ ] = CVaRα (L)
1−α
□

4.3. Coherence of CVaR

In this section we show that CVaR is a coherent measure of risk, see Sec-
tion 1.4. We prove each individual axiom separately. We start by proving
monotonicity which, in turn, will help us prove validity of axiom (A1).
72 4. CONDITIONAL VALUE AT RISK

Proposition 4.26. CVaR is monotonic. That is, we have

CVaRα (L1 ) ≤ CVaRα (L2 )
for all L1 ≤ L2 a.s.

Proof. From L1 ≤ L2 a.s., it follows that, for given z ∈ R, we have

L1 − z ≤ L2 − z a.s., and, in turn, (L1 − z)+ ≤ (L2 − z)+ a.s. and,
consequently, E [(L1 − z)+ ] ≤ E [(L2 − z)+ ]. Therefore,
1 1
z+ E [(L1 − z)+ ] ≤ z + E [(L2 − z)+ ]
1−α 1−α
for all z ∈ R. Taking the minimum of both sides we obtain
1 1
min{z + E [(L1 − z)+ ]} ≤ min{z + E [(L2 − z)+ ]}
z∈R 1−α z∈R 1−α
that is
CVaRα (L1 ) ≤ CVaRα (L2 )
as required. □

Proposition 4.27. Let L ≤ 0 a.s. Then CVaRα (L) ≤ 0.

Proof. Define L2 = 0 a.s. and apply Proposition 4.26.

□

Proposition 4.28. CVaR is convex.

Proof. Consider two random variables L1 and L2 and let, for i =

1, 2
1
CVaRα (Li ) = zi + E [(Li − zi )+ ]
1−α
Take λ ∈ (0, 1) and consider
1
CVaRα (λL1 + (1 − λ)L2 ) = zλ + E [(λL1 + (1 − λ)L2 − zλ )+ ]
1−α
where zλ ∈ argminz Gα (λL1 + (1 − λ)L2 ).
 4.3. COHERENCE OF CVAR 73

Consider now the point λz1 + (1 − λ)z2 . By optimality of zλ we have the

inequality
1
zλ + E [(λL1 + (1 − λ)L2 − zλ )+ ]
1−α
1
≤λz1 + (1 − λ)z2 + E [(λL1 + (1 − λ)L2 − λz1 − (1 − λ)z2 )+ ]
1−α
1
=λz1 + (1 − λ)z2 + E [(λ(L1 − z1 ) + (1 − λ)(L2 − z2 ))+ ]
1−α
Now, observe that a 7→ E [(a)+ ] is convex and that (a+b)0 ≤ (a)+ +(b)+ .
Therefore, we can state
1
λz1 + (1 − λ)z2 + E [(λ(L1 − z1 ) + (1 − λ)(L2 − z2 ))+ ]
1−α
1
≤λz1 + (1 − λ)z2 + (λE [(L1 − z1 )+ ] + (1 − λ)E [(L2 − z2 )+ ])
 1 − α   
1 1
=λ z1 + E [(L1 − z1 )+ ] + (1 − λ) z2 + E [(L2 − z2 )+ ]
1−α 1−α
=λCVaRα (L1 ) + (1 − λ)CVaRα (L2 )
As required. □

Proposition 4.29. CVaR is positive homogeneous.

Proof. By Corollary 4.25 we have

1
CVaRα (L) = min{z + E [(L − z)+ ]}
z∈R 1−α
Consider, for a constant λ ≥ 0
1
CVaRα (λL) = min{z + E [(λL − z)+ ]}
z∈R 1−α
Define z ′ = z/λ and substitute. The previous expression is then equal
to
1
min {λz ′ + E [(λL − λz ′ )+ ]}
′
z ∈R 1−α
1
= min {λz ′ + E [λ(L − z ′ )+ ]}
′
z ∈R 1−α
74 4. CONDITIONAL VALUE AT RISK

1
= min{λz ′ + λ E [(L − z ′ )+ ]}
′
z ∈R 1−α
1
=λ min {z ′ + E [(L − z ′ )+ ]}
′
z ∈R 1−α
=λCVaRα (L)
As required.
□

Proposition 4.30. CVaR is translation invariant.

Proof. By Corollary 4.25 we have

1
CVaRα (L) = min{z + E [(L − z)+ ]}
z∈R 1−α
Consider, for a constant a ∈ R
1
CVaRα (L + a) = min{z + E [(L + a − z)+ ]}
z∈R 1−α
Define z ′ = z − a and substitute. The previous expression is then equal
to
1
min {z ′ + a + E [(L − z ′ )+ ]}
′
z ∈R 1−α
Since a is a constant, the former expression is equivalent to
′ 1
a + min {z + E [(L − z ′ )+ ]} = a + CVaRα (L)
z ′ ∈R 1−α
□

Proposition 4.31. CVaR is a coherent measure of risk.

Proof. Follows immediately from Propositions 4.27 to 4.30. □

4.4. Optimization of CVaR

Let us now return to our optimization over x. Let us define

1
CVaRα (x) := CVaRα (L(x, ξ)) = min{z + E [(L(x, ξ) − z)+ ]}
z∈R 1−α
 4.4. OPTIMIZATION OF CVAR 75

Now that we know how to compute CVaR given x (that is for a random vari-
able x 7→ L(·, ξ)) the problem becomes that of optimizing CVaR. That is, the
problem of finding x which minimizes CVaR. The problem can be stated as
  
 ⊤ ⊤ 1
min c x + CVaRα (x) = min c x + min z + E [(L(x, ξ) − z)+ ]
x∈X x∈X z∈R 1−α
Note that, as it is clear from the proof of Proposition 4.24, the inner minimum
exists. Observe that, for fixed x, the inner minimum can be found by mini-
mizing the second terms over z. Thus, the problem can be stated equivalently
as
 
⊤ 1
(4.9) min c x+z+ E [(L(x, ξ) − z)+ ]
x∈X ,z∈R 1−α
Thus we find x which minimizes CVaR by minimizing jointly in x and z.
Let us now turn our attention to the optimization problem that arises when
we constrain CVaR, that is
min c⊤ x
s.t. CVaRα (x) ≤ λ
x∈X
where λ is a given upper bound that CVaR should not exceed. Replacing
CVaRα (x) by its minimization formula we obtain
min c⊤ x
 
1
s.t. min z + E [(L(x, ξ) − z)+ ] ≤λ
z∈R 1−α
x∈X
For fixed x, the CVaR constraint holds if and only if there exists z ∈ R for which
1
z + 1−α E [(L(x, ξ) − z)+ ] ≤ λ. Thus, we can rewrite the constraint obtaining
the following optimization problem in x and z
(4.10) min c⊤ x
1
(4.11) s.t. z + E [(L(x, ξ) − z)+ ] ≤ λ
1−α
(4.12) x ∈ X,z ∈ R
Obviously, for given x, if there exists a z for which the constraint holds, then
the constraint holds also for the z that minimizes the left-hand side. Observe,
however, that at optimum, z does not necessarily represent VaR, which is de-
fined as the least of the α-quantiles of the distribution of L(x, ξ). In a similar
way, the left-hand side of the CVaR constraint does not necessarily provide
76 4. CONDITIONAL VALUE AT RISK

CVaR. It may provide a quantity higher than CVaR. However, if the problem
has solution, then we can conclude that CVaR is below λ, as required.
Given the convexity of CVaR in x, these optimization problems are convex
whenever X is convex. This entails that, in principle, one could solve them
efficiently. When the distribution of L is known, it is in many cases possible to
obtain closed form expressions of CVaR, see e.g., [AKM05, NZC14, NKU21].
However, in practice closed form expressions of CVaR as a function of x are not
easily available. The expectation in its minimization formula is, in general,
a multidimensional integral for which a closed form expression is not usually
achievable. Therefore, in practice we rely on discrete approximations of ξ.
In fact, when ξ is a discrete random variable, the two optimization problems
become easy to deal with. Let ξ be a discrete random variables with realiza-
tions ξ1 , . . . , ξS and probabilities π1 , . . . , πS . Let S = {1, . . . , S}. In this case
problem (4.9) becomes
1 X
min c⊤ x + z + π s ws
1 − α s∈S
s.t. ws ≥ L(x, ξs ) − z ∀s ∈ S
ws ≥ 0 ∀s ∈ S
x ∈ X,z ∈ R
When L(x, ξs ) is linear in x this is a linear programming (LP) problem. In a
similar way, problem (4.10) becomes
min c⊤ x
1 X
s.t. z + πs w s ≤ λ
1 − α s∈S
ws ≥ L(x, ξs ) − z ∀s ∈ S
ws ≥ 0 ∀s ∈ S
x ∈ X,z ∈ R
which is likewise an LP problem When L(x, ξs ) is linear in x.
 APPENDIX A

Background

A.1. Random Variables

Definition A.1 (Measurable function). Let (Ω, F) and (S, T ) be two

measurable spaces. A function f : Ω → S is F/T −measurable if, for all
S ′ ∈ T we have that f −1 (S ′ ) ∈ F. When the two σ-algebras are clear
from the context, we usually just say that the function is measurable.

Definition A.2 (Measurability of compositions). Let f be measurable

from (Ω, F) into (S, T ) and g be measurable from (S, T ) into (V, Y).
Then g ◦ f is measureable fromb (Ω, F) into (V, Y).

Definition A.3 (Image measure). Let (Ω, F) and (Γ, G) be two mea-
surable spaces. Let f : Ω → Γ be an F/G-measurable function. Let
P be a measure on (Ω, F). We define the image measure Pf as the
measure on (Γ, G) given by
Pf (B) = P(f −1 (B)) ∀B ∈ G

Let (Ω, F, P) be a probability space. The idea underlying a random variable

is the following: Chance determines the random outcome ω and ω determines
quantities of interest. We call such quantities of interest random variables.
Hence, a random variable will be a function X : Ω → S, where S is typically
Rn . This function has to be sufficiently nice so that we can assign probabilities
to subsets of its values. That is, whenever S ′ ⊂ S is a reasonable enough subset
of the possible values, the set of outcomes ω for which X(ω) ∈ S ′ should be
an event to which we can assign a measure. That is, the set
{ω ∈ Ω|X(ω) ∈ S ′ } ∈ F
That is, we require X to be a measurable function. The set which has to be
measurable is called the pre-image of X, or X −1 (S ′ ).

77
78 A. BACKGROUND

Definition A.4 (Random variable). Let (Ω, F, P) be a probability

space. Let (S, T ) be a measurable space. A random variable with values
in S is an F/T -measurable function X : Ω → S.

Usually S are equipped with the Borel σ-algebras B(S) generated by their
open subsets. A B(Ω)/B(S)-measurable function f : Ω → S is called a Borel-
measurable function or simply a Borel function.
Suppose that X : Ω → S is a random variable. Then there is a probabil-
ity measure on S which describes how the values of the random variable are
distributed.

Definition A.5 (Law (or distribution) of the random variable). The

law or distribution of the random variable X : Ω → S is the probability
measure PX on (S, T ) defined by
PX [S ′ ] = P[X −1 (S ′ )] = P ({ω ∈ Ω|X(ω) ∈ S ′ })
for all S ′ ∈ T .

Definition A.6 ((Cumulative) distribution function). Let X : Ω → R

be a random variable with values in (R, B). This entails that the law PX
is a probability measure on (R, B). Then the (cumulative) distribution
function of PX is the function FX : R → [0, 1] defined by

FX (x) = PX [(−∞, x]]

for all x ∈ R.

Proposition A.7 (Distribution functions characterize measures). Let

P1 and P2 two probability measures on (R, B) and F1 and F2 their re-
spective distribution functions. Then
F1 = F2 ⇐⇒ P1 = P2

Since distribution functions characterize probability measures it is natural

to ask which functions can qualify as distribution functions.
 A.1. RANDOM VARIABLES 79

Proposition A.8 (Properties of distribution functions). Let F : R →

[0, 1] be a distribution function of a probability measure P on (R, B).
Then F satisfies the following properties
(1) F is increasing, that is x ≤ y implies F (x) ≤ F (y).
(2) F is right-continuous, that is, if xn ↓ x ∈ R as n → ∞ then
F (xn ) ↓ F (x).
(3) limx→∞ F (x) = 1.

Definition A.9 (Probability density of a continuous random variable).

Let X : Ω → R be a random variable with values in (R, B). If there
exists a Borel function
fX : R → [0, ∞)
such that Z Z
PX (B) = P ({ω ∈ Ω|X(ω) ∈ B}) = fX (x) dx = fX (x)1B (x) dΛ(x)
B R
a
for all B ∈ B, then we say that X has a continuous distribution and
that fX is a density function of X.
aHere Λ denotes the Lebesgue measure on R restricted to B.

Definition A.10 (Expectation). For a random variable X : Ω → R

defined on (Ω, F, P) we define the expectation as
Z Z
E [X] = X dP = X(ω) P(dω)
Ω Ω

Definition A.11 (Integration wrt image measures). Let (Ω, F, P) be a

measure space. Let (Γ, G) be a measurable space. Let X : Ω → Γ be
an F/G-measurable function. Let f : Γ → R be a nonnegative G/B-
measurable functiona. Then
Z Z
f dPX = f ◦ X dP

where PX is the image measure of X.

aB denotes the Borel σ-algebra on R.

Let us briefly introduce a generalization of the Lebesgue measure on R.

80 A. BACKGROUND

Definition A.12 (Lebesgue-Stieltjes measure). Let F : R → R be an

increasing (i.e., non-decreasing), right-continuous function. Then, there
exists a unique Borel measure µF : B → [0, ∞] such that
µF ((a, b]) = F (b) − F (a)
for all a < b.

Lebesgue-Stieltjes measures assign each half-open interval (a, b] the mea-

sure µF ((a, b]) = F (b)−F (a). The use of half-open intervals is significant. This
is because the Lebesgue-Stieltjes measure is defined by a right-continuous but
not necessarily left-continuous function F . As such, it may assign nonzero mea-
sure to a sigle point. That is, µF (a) = µF ((a, a]) = F (a) − F (a− ) = F (a) −
limϵ→0+ F (a − ϵ). A prime example, are distribution functions with jumps.
Thus, unlike the Lebesgue measure, we need not have µF ([a, b]) = µF ((a, b]).
Observe that we recover the Lebesgue measure by using F (x) = x. That is,
we obtain µF ((a, b]) = b − a.

Definition A.13 (Expectations wrt distribution functions). Let X :

Ω → [0, ∞) be a non-negative random variable. Let FX : R → [0, 1] be
its distribution function. Then
Z Z
E [X] = X dFX = X dµFX

where µF is the Lebesgue-Stieltjes measure generated by FX on R.

Therefore, integration with respect to a distribution function essentially

means integration with respect to the Lebesgue-Stieltjes measure it generates
on R.

Theorem A.14 (Expected value in terms of distribution function). Let

X : Ω → [0; ∞) be a non-negative random variable. Let FX : R → [0, 1]
be its distribution function

FX (x) = P (X ≤ x)
Then we have Z ∞
E [X] = (1 − FX (x)) dx
0
 A.1. RANDOM VARIABLES 81

Definition A.15 (Lp spaces). We say that an F-measurable function

f is integrable with respect to the measure P if
Z
|f | dP < ∞

We call L1 (P) the set of integrable functions. In a similar way we de-

fine Lp (P) as the set of p-times integrable functions with respect to the
measure P, that is Z
|f |p dP < ∞
We may write Lp (Ω, F, P) to remove any possible ambiguity.

Theorem A.16 (Triangle inequality). For all f ∈ L1 (P) it holds that

Z Z
f dP ≤ |f | dP

Hence absolute integrability implies integrability.

Definition A.17 (Expected value). Let (Ω, F, P) be a probability space.

The expected value of a real-valued random variable X : O⇕⌉}⊣ → R is
defined as Z
E [X] := X(ω) dP(ω)
Ω

Since the expectation is by definition the integral of X with respect to the

measure P, all the properties about integrals extend to expectations. Particu-
larly, linearity, monotonicity, and the triangle inequality.

Theorem A.18 (Monotonicity of expectations). . Let (Ω, Σ, P) be a

probability space. Let X and Y be integrable random variables such that
X(ω) ≤ Y (ω) for all ω ∈ Ω. Then E [X] ≤ E [Y ].
R R
Proof. Since E [X] = X dP and E [Y ] = Y dP, the claim
follows from monotonicity of the integral of integrable functions.
□
82 A. BACKGROUND

Definition A.19 (Expected values in terms of laws). Let X : Ω → R

be a random variable with law PX . Let g : R → R be a Borel function
with g ∈ L1 (PX ). Then we have
Z
E [g(X)] = g(x) dPx (x)
R

A.2. Convex Optimization

Consider an optimization problem in the form

(A.1a) min f0 (x)

(A.1b) fi (x) ≤ 0 i = 1, . . . , m
(A.1c) hi (x) = 0 i = 1, . . . , p

Assume that
m p
\ \
n
X = {x ∈ R |fi (x) ≤ 0} ∩ {x ∈ Rn |hi (x) = 0}
i=1 i=1

and that X is nonempty.

Definition A.20 (Lagrangian function). We define the Lagrangian

function L : Rn × Rm × Rp → R associated with problem (A.1) as
m p
X X
L(x, λ, ν) = f0 (x) + λi fi (x) + νi hi (x)
i=1 i=1

p
We refer to λ := (λi )m
i=1 and ν := (νi )i=1 as the Lagrange multipliers.

Definition A.21 (Lagrangian Problem). For given λ ∈ Rm we define

the Lagrange Problem g : Rm × Rp → R associated with problem (A.1)
as
m p
X X
g(λ, ν) = inf L(x, λ, ν) = inf f0 (x) + λi fi (x) + νi hi (x)
x∈X x∈X
i=1 i=1

Observe that g(λ, ν) is a concave function. This is due to the fact that it
is the pointwise infimum of a family of linear functions in (λ, ν).
 A.2. CONVEX OPTIMIZATION 83

Proposition A.22 (Lower bounds). Let z ∗ be the optimal objective

value to problem (A.1). Then, for all λ ≥ 0 and ν we have
g(λ, ν) ≤ z ∗

Proof. Assume x′ is a feasible solution to problem (A.1).

Then, fi (x′ ) ≤ 0 for i = 1, . . . , m and hi (x′ ) = 0,for i = 1, . . . , p.
Then we have
m p
X X
′
λi fi (x ) + νi hi (x′ ) ≤ 0
i=1 i=1
since, by assumption, λ ≥ 0. Therefore,
m p
X X
′ ′ ′
L(x , λ, ν) = f0 (x ) + λi fi (x ) + νi hi (x′ ) ≤ f0 (x′ )
i=1 i=1
Hence
g(λ, ν) = inf L(x, λ, ν) ≤ L(x′ , λ, ν) ≤ f0 (x′ )
x∈X

Since the inequality holds for all feasible x′ it holds for the optimal
solution x∗ which yields f0 (x∗ ) = z ∗ , as required. □

The Lagrangian function provides a lower bound for each (λ, ν) with λ ≥ 0.
Therefore, it is reasonable to look for the best (that is, the largest) of such
lower bounds. This can be found by solving the following optimization problem

(A.2) max g(λ, ν)

λ≥0

Problem (A.2) is called the Lagrangian dual problem associated with problem
(A.1). Observe that a pair (λ, ν) is dual feasible if λ ≥ 0 and g(λ, ν) > −∞,
that is, it provides a non-trivial lower bound. Observe that problem (A.2) is
convex regardless of whether (A.1) is convex. This is because we maximize a
concave objective function subject to convex constraints.

Proposition A.23 (Weak duality). Let w∗ be the optimal objective

value to (A.2) and z ∗ the optimal objective value to (A.1). Then,
w∗ ≤ z ∗
84 A. BACKGROUND

Proof. This follows immediately from Proposition A.22. In

particular, w∗ is, by definition, the best lower bound. □

Definition A.24 (Strong duality). If the equality w∗ = z ∗ holds, we

say that strong duality holds.

In general, strong duality cannot be assumed for general problems. How-

ever, if the primal is convex, i.e., of the form

(A.3) min f0 (x)

(A.4) fi (x) ≤ 0 i = 1, . . . , m
(A.5) Ax = b

with fi (x), i = 0, . . . , m, are convex, we usually have strong duality. There

are many results which establish conditions that need to hold (in addition to
convexity) in order for strong duality to hold. These conditions are called
constraint qualifications.

Definition A.25 (Interior point). Let S ⊂ Rn . Then x ∈ S is called

an interior point of S if ∃ ϵ > 0 such that {y ∈ Rn |∥x − y∥2 < ϵ} ∈ S.

Definition A.26 (Interior of a set). Let S ⊂ Rn . The interior of S,

intS can be defined in the following equivalent ways:
◦ intS is the largest open subset of S completely contained in S
◦ intS is the union of all open sets of Rn contained in S
◦ intS is the union of all interior points of S .

Definition A.27 (Affine Set). A subset S of Rn is called an affine set

if for any a, b ∈ S and all λ ∈ R we have that λa + (1 − λ)b ⊆ S.

Hence, an affine set is a set that contains all the lines passing through any
two points in the set.
 A.2. CONVEX OPTIMIZATION 85

Definition A.28 (Affine Hull of a Set). The affine hull af f (S) of S is

the set of all affine combinations of elements of S, that is,
\
af f S = {X |X is affine and S ⊆ X }

Hence af f S is the smallest affine set which contains our target set S.

Example A.1. Consider R3 and the set S = {(x, y, 0)|x2 + y 2 ≤ 1}.

Observe that all the points in S are on the R2 plane. Therefore, this set
has no interior points (its interior is empty). This is because there is no
point x in S for which the open ball {y ∈ Rn |∥x − y∥2 < ϵ} is contained
in ∈ S (the ball includes points with z ̸= 0). Here ∥·∥2 is the Euclidean
metric in R3 . The affine hull of S is the smallest affine set that contains
S. This set is R2 .

Definition A.29 (Relative interior of a set). The relative interior riS

of a set S considered as a subset of its affine hull af f (S).

Example A.2. Consider the closed unit square in R3

I 2 = {(x, y, 0)|x ≤ 0, y ≤ 1}
We have that
int(I 2 ) = ∅
however, its affine hull is the the x − y plane
af f (I 2 ) = {(x, y, 0)|x, y ∈ R}
therefore
riI 2 = {(x, y, 0)|x < 0, y < 1}
that is, the interior of I 2 when I 2 is seen as a subset of its affine hull
which is R2 .

One simple constraint qualification is the following.

Theorem A.30 (Slater’s Theorem). If there exists x ∈ relintX such that

fi (x) < 0 for i = 1, . . . , m
86 A. BACKGROUND

and
Ax = b
then strong duality holds.

The conditions stated in Theorem A.30 are referred to as Slater’s condi-

tions. A point which satisfies Slater’s condition is called a strictly feasible
solution due to the strict inequality.
Slater’s conditions can be even less stringent when additional properties
hold on the constraints. Particularly, if f1 , . . . , fk are affine functions, then
strong duality holds under the following weaker conditions: There exists x ∈
relintX such that
fi (x) ≤ 0
for i = 1, . . . , k
fi (x) < 0
for i = k + 1, . . . , m and
Ax = b
. In other words, the affine inequalities do not need to hold strictly. This
immediately leads to the following results.

Proposition A.31 (Strong duality with linear constraints). When the

constraints are all linear and the domain of f0 is open, then strong duality
holds.

From Proposition A.31 it is possible to obtain useful additional results. Let

x be a primal optimal solution and (λ∗ , ν ∗ ) a dual optimal solution. Then,
∗

this implies the following

f0 (x∗ ) = g(λ∗ , ν ∗ )
p
( m
)
X X
inf fo (x) + λ∗i fi (x) + νi∗ hi (x)
x∈X
i=1 i=1
m p
X X
≤ fo (x∗ ) + λ∗i fi (x∗ ) + νi∗ hi (x∗ )
i=1 i=1
∗
≤ f0 (x )
When strong duality holds, the last two inequalities hold with equality. This
allows us to draw interesting conclusions. The first conclusion is that x∗ min-
imizes the Lagrangian function L(x, λ∗ , ν ∗ ) (observe however that there can
 A.2. CONVEX OPTIMIZATION 87

me other minimizers). The second important conclusion is that we necessarily

need

m
X
λ∗i fi (x∗ ) = 0
i=1

Since each term in the sum is non-positive, this in turn implies

λ∗i fi (x∗ ) = 0 i = 1, . . . , m

This condition is known as complementarity slackness.

Definition A.32 (Complementarity slackness). Assume strong duality

holds. The condition
λ∗i fi (x∗ ) = 0 i = 1, . . . , m
is known as complementarity slackness. It can be expressed as
λ∗i > 0 =⇒ fi (x∗ ) = 0
or, equivalently,
fi (x∗ ) < 0 =⇒ λ∗ = 0

Proposition A.33 (KKT conditions). Assume f0 , . . . , fm and hi , . . . , hp

are differentiable. Let x∗ and (λ∗ , ν ∗ ) be any primal and dual opti-
mal solutions with zero duality gap. Then, the following system of
(in)equalities holds
(A.6) fi (x∗ ) ≤ 0 i = 1, . . . , m
(A.7) hi (x∗ ) = 0 i = 1, . . . , p
(A.8) λ∗i ≥0 i = 1, . . . , m
(A.9) λ∗i fi (x ) = 0
∗
i = 1, . . . , m
m p
X X
(A.10) ∇f0 (x∗ ) + λ∗i ∇fi (x∗ ) + νi∗ ∇hi (x∗ ) = 0
i=1 i=1
This system of equalities and inequalities are known as the Karush-
Kuhn-Tucker (KKT) conditions.
88 A. BACKGROUND

Proof. The first and second (in)equalities ensure primal fea-

sibility. The third condition ensures that the Lagrange multipliers
are non-negative so that they effectively penalize violations of the
inequality constraints and yield a dual lower bound. Following,
we have complementarity conditions Definition A.32 which, as we
have seen, hold for any primal and dual solution whenever strong
duality holds. Finally, the last condition states since x∗ minimizes
L(x, λ∗ , ν ∗ ) over x, it follows that its gradient is null, that is
m p
X X
∗ ∗ ∗ ∗ ∗ ∗
∇L(x , λ , ν ) = ∇f0 (x ) + λi ∇fi (x ) + νi∗ ∇hi (x∗ ) = 0
i=1 i=1
□

To summarize, for any optimization problem with differentiable objective

and constraint functions for which strong duality holds, any pair of primal and
dual optimal points must satisfy the KKT conditions.

Proposition A.34 (KKT for convex problems). Assume f0 , . . . , fm are

convex and h1 , . . . , hp are affine. Let x∗ , λ∗ , ν ∗ be any points that satisfy
the KKT condition. Then x∗ is primal optimal, (λ∗ , ν ∗ ) dual optimal,
and the duality gap is zero.

Summarizing, for any convex optimization problem with differentiable ob-

jective and constraint functions, any points that satisfy the KKT conditions
are primal and dual optimal, and have zero duality gap. The KKT conditions
play an important role in optimization. In a few special cases it is possible to
solve the KKT conditions (and therefore, the optimization problem) analyti-
cally.

Example A.3. Consider the following problem

 
1 ⊤ ⊤
min x Qx + q x + r|Ax = b
2
where Q is symmetric and positive semidefinite. The KKT conditions
for this problem are
Ax∗ = b
 A.2. CONVEX OPTIMIZATION 89

Qx∗ + q + A⊤ ν ∗ = 0
These form a system of m + n linear equations in m + n variables, i.e., x∗
and ν ∗ , which is easily solved. The solution to this system of equations
provides the optimal primal and dual solution to the problem.
 Bibliography

[ADEH99] Philippe Artzner, Freddy Delbaen, Jean-Marc Eber, and David Heath, Coherent
measures of risk, Mathematical finance 9 (1999), no. 3, 203–228.
[AKM05] Andriy Andreev, Antti Kanto, and Pekka Malo, On closed-form calculation of
cvar.
[GGS11] Ralf Gollmer, Uwe Gotzes, and Rüdiger Schultz, A note on second-order stochas-
tic dominance constraints induced by mixed-integer linear recourse, Mathematical
Programming 126 (2011), 179–190.
[GNS08] Ralf Gollmer, Frederike Neise, and Rüdiger Schultz, Stochastic programs with
first-order dominance constraints induced by mixed-integer linear recourse, SIAM
Journal on Optimization 19 (2008), no. 2, 552–571.
[Mar52] Harry Markowitz, Portfolio selection, Journal of Finance (1952), no. 7, 77–91.
[NKU21] Matthew Norton, Valentyn Khokhlov, and Stan Uryasev, Calculating cvar and
bpoe for common probability distributions with application to portfolio optimiza-
tion and density estimation, Annals of Operations Research 299 (2021), 1281–
1315.
[NZC14] Saralees Nadarajah, Bo Zhang, and Stephen Chan, Estimation methods for ex-
pected shortfall, Quantitative finance 14 (2014), no. 2, 271–291.
[R. 70] R. Tyrrell Rockafellar, Convex Analysis, Princeton University Press, 1970.
[RS70] Michael Rothschild and Joseph E Stiglitz, Increasing risk i: A definition, Journal
of Economic Theory 2 (1970), 225–243.
[VNM47] John Von Neumann and Oskar Morgenstern, Theory of games and economic
behavior, 2nd rev, Princeton university press, 1947.

91