FINANCIAL DERIVATIVES - DANIEL PHILLIPE GONÇALVES MENEZES

danielphillipegonalv 67 views 42 slides Sep 03, 2025
Slide 1
Slide 1 of 42
Slide 1
1
Slide 2
2
Slide 3
3
Slide 4
4
Slide 5
5
Slide 6
6
Slide 7
7
Slide 8
8
Slide 9
9
Slide 10
10
Slide 11
11
Slide 12
12
Slide 13
13
Slide 14
14
Slide 15
15
Slide 16
16
Slide 17
17
Slide 18
18
Slide 19
19
Slide 20
20
Slide 21
21
Slide 22
22
Slide 23
23
Slide 24
24
Slide 25
25
Slide 26
26
Slide 27
27
Slide 28
28
Slide 29
29
Slide 30
30
Slide 31
31
Slide 32
32
Slide 33
33
Slide 34
34
Slide 35
35
Slide 36
36
Slide 37
37
Slide 38
38
Slide 39
39
Slide 40
40
Slide 41
41
Slide 42
42

About This Presentation

DANIEL PHILLIPE GONÇALVES MENEZES - ARACAJU, SERGIPE.


Slide Content

Electronic copy available at: http://ssrn.com/abstract=2172315 Super-replication of financial derivatives via convex programming
Nabil Kahal´e
Λ
First version: November 7, 2012
This version: March 22, 2016
Abstract
We give a method based on convex programming to calculate the optimal super-replicating
and sub-replicating prices and corresponding hedging portfolios of a financial derivative in
terms of other financial derivatives in a discrete-time setting. Our method produces a model
that matches the super-replicating (or sub-replicating) price within an arbitrary precision
and is consistent with the other financial derivatives prices. Applications include robust
replication in terms of call prices with various strikes and maturities of forward start op-
tions, volatility and variance swaps and derivatives, cliquets calls, barrier options, lookback
and Asian options. Numerical examples show that, in some cases, the best super-replicating
and/or sub-replicating prices are within 10% of the price obtained by a standard model,
but considerably differ from it in other cases. Our method can incorporate bid-ask spreads,
interest rates and dividends and various limitations to the diffusion model.
Keywords: Model risk, robust replication, robust hedging, convex programming, financial
derivatives.
1 Introduction
Several models based on local volatility, stochastic volatility or jump diffusion (see, e.g., (Hull
2012)) have been used to price financial derivatives. However, even if these models exactly
fit the current market prices of liquid financial products, such as vanilla call and put options,
they may produce different prices for other products such as barrier options (Britten-Jones
and A. Neuberger 2000). This gives rise to model risk in the pricing of financial derivatives,
of which practitioners are well aware (see (Committee on Banking Supervision 2009, p. 29)).
This model risk can be assessed through the calculation of model-independent bounds on the
derivative price: the larger the gap between the upper and lower bound, the larger the risk.
Another possible application of model-independent bounds comes from the observation that if
a bank sells (resp. buys) a derivative at a model-independent upper-bound (resp. lower-bound)
on its price, it can realize a non-negative net profit by using proper hedging, independently
of the future underlying securities behavior. The range of possible arbitrage free prices for a
given derivative securityψis large in general (Carassus, Gobet and Temam 2007) but can be
narrowed if the prices of liquid derivatives, such as call prices, are known at time 0. Bounds on
option prices in terms of other financial derivatives prices have been derived in the literature
in a static setting as well as in a dynamic setting, i.e. when dynamic trading in the stock is
allowed at future times.
In a static setting, (Boyle and Lin 1997) have derived a semi-definite upper-bound on a
call on the maximum of several assets in terms of their means and correlations. (Bertsimas
and Popescu 2002, Gotoh and Konno 2002) have used semi-definite programming to optimally
Λ
ESCP Europe and Labex ReFi, 79 avenue de la R´epublique, 75011 Paris, France; e-mail: nka-
[email protected].
1
Electronic copy available at: https://ssrn.com/abstract=2172315

Electronic copy available at: http://ssrn.com/abstract=2172315 super-replicate call options in single-period markets on a single asset given several moments
of the underlying asset. Tight bounds on prices of basket options (Hobson, Laurence and
Wang 2005a, Hobson, Laurence and Wang 2005b, Laurence and Wang 2005, d’Aspremont and
El Ghaoui 2006) and on spread options (Laurence and Wang 2008, Laurence and Wang 2009)
have been established in terms of prices of vanilla options with the same maturity.
In a dynamic setting, optimal bounds on specific options have been previously derived
under certain conditions. When interest rates are null, tight model-independent bounds on
lookback and barrier options have been obtained (Hobson 1998, Brown, Hobson and Rogers
2001b, Brown, Hobson and Rogers 2001a, Hobson and Pedersen 2002, Cox and Ob l´oj 2011a, Cox
and Ob l´oj 2011b, Galichon, Henry-Labordere and Touzi 2014, Henry-Labordere, Obloj, Spoida
and Touzi 2013) in terms of call prices. Under a continuity assumption on the stock price,
numerical schemes for robust hedging of financial derivatives have been given (Bonnans and
Tan 2011, Tan and Touzi 2013) in terms of a continuum set of call prices, robust pricing of
a continuously-monitored variance swap given prices for a finite number of co-maturing call
options has been obtained (Davis, Obloj and Raval 2014), and optimal bounds on continuously-
monitored variance options have been derived analytically (Cox and Wang 2013). Explicit
bounds on discretely-monitored variance swaps (Kahal´e 2014, Hobson and Klimmek 2012) have
been established in terms of a continuum set of call prices with the same maturity and shown to
be optimal when the number of time-steps goes to infinity. (Henry-Labordere and Touzi 2013)
have derived optimal bounds on variance swaps monitored att
i
when call prices are known for
maturitiest
i
, 1≤i≤m, and all strikes. A tight but non-constructive upper bound (Hobson
and Neuberger 2012) on at the money forward-start options and, under certain conditions, a
tight and explicit lower bound (Hobson and Klimmek 2015) have been obtained in terms of a
continuum set of call prices.
Most previous derivations of explicit bounds construct explicitly associated hedging strate-
gies. Also, they often identify explicit scenarios that lead to the extremum prices. However,
explicit optimal bounds on path-dependent derivatives that we are aware of make at least one
of the following simplifying assumptions: interest rates are null, call prices are known for a
continuum set of strikes, or the underlying variables prices follow a continuous process. These
assumptions do not hold in practice, though, and may introduce an important bias in the
pricing of a financial derivative. For instance, the price of a continuously-monitored variance
swap, when jumps in the stock prices are allowed, may significantly differ from the price ob-
tained under the continuity assumption (Demeterfi, Derman, Kamal and Zou 1999, Broadie
and Jain 2008, Carr and Wu 2009, Carr, Lee and Wu 2012). Also, in practice, variance swaps
are discretely monitored, but it has been often been assumed in the literature that they are
continuously monitored, which introduces another source of bias as shown in (Broadie and
Jain 2008). Furthermore, optimal explicit bounds are only known for specific options and not
known in general for a portfolio of options, even in two-periods markets. This can be explained
by noting that robust super-replication is closely related (Henry-Labordere and Touzi 2013) to
the optimal transportation problem, for which no explicit solutions are known in general.
This paper gives a unified methodology based on convex programming to calculate the best
super-replicating and sub-replicating prices and corresponding hedging portfolios of a finan-
cial derivativeψin terms of prices of a finite set oflliquid derivatives. Super-replicating (or
sub-replicating) strategies forψconsist of static positions in a zero-coupon bond and in the
lderivatives at time 0 combined with dynamic trading indunderlying liquid securities. We
assume that interest rates are deterministic and work in a multi-period setting but do not make
any continuity assumptions on the underlying variables. Under certain conditions, we show
the convex program can be solved efficiently for a large class of financial derivatives. Further-
more, our method produces a model that matches the super-replicating (or sub-replicating)
price within an arbitrary precision and is consistent with the other financial derivatives prices.
Applications include the calculation of the best super-replicating and sub-replicating prices in
2
Electronic copy available at: https://ssrn.com/abstract=2172315

terms of call options with different strikes and maturities of a wide variety of derivatives such
as
•discretely-monitored, standard and generalized variance swaps including cliquet calls and
corridor variance swaps
•discretely-monitored volatility swaps and volatility derivatives
•discretely-monitored Asian options
•discretely monitored lookback and barrier options.
We are not aware of previous model-independent optimal bounds for any of these problems
without the simplifying assumptions mentioned earlier. In particular, we give the first optimal
bounds on discretely-monitored variance and volatility swaps in terms of a finite set of call
prices without any continuity assumption on the stock, and the first optimal bounds on the price
of arithmetic Asian options. Model-independent bounds for prices of Asian options have been
previously derived (Simon, Goovaerts and Dhaene 2000, Albrecher, Mayer and Schoutens 2008),
but they are not optimal. We also give the first optimal bounds on discretely monitored lookback
and barrier options in terms of a finite set of call prices without assuming interest rates to be
null. Finally, we give optimal robust bounds on forward start options. In (Beiglb¨ock, Henry-
Labord`ere and Penkner 2013), optimal model-independent bounds for forward-start options
in terms of a finite set of call prices are calculated in a discrete-state setting using linear
programming, but no bound is given on the discretization error. In addition, our convex program
can be easily adapted to calculate the best model-free bounds on a financial derivative when
bid and ask prices of the liquid financial derivatives are not equal, or the size of the jumps the
assets can take are restricted.
A method based on linear programming with a large number of constraints is described in
(Henry-Labord`ere 2013) to robust hedging of derivatives. However, this method requires the
amount of basic securities held in a dynamic hedging position to be a function of a certain type
(e.g. a polynomial) of the securities values. It also assumes the securities paths to belong to
a certain grid generated by a Monte Carlo simulation scheme, and requires the knowledge of
a continuum set of call options prices. No estimate on the errors due to these requirements is
given in (Henry-Labord`ere 2013).
In line with previous literature on robust bounds on derivatives that depend on the under-
lyings’ values on a finite set of time-steps (see, e.g., (Simon, Goovaerts and Dhaene 2000, Al-
brecher, Mayer and Schoutens 2008, Kahal´e 2014, Hobson and Neuberger 2012, Hobson and
Klimmek 2012, Hobson and Klimmek 2015, Beiglb¨ock, Henry-Labord`ere and Penkner 2013,
Henry-Labordere and Touzi 2013)), we use a discrete-time model with an infinite state-space
without reference to a single prior measure. We only use risk-neutral probabilities with finite
support, as these are sufficient to derive optimal model-independent bounds in our framework
(see Theorem 3.2, and (Kahal´e 2010) for related results). In our numerical applications, we
discretize the state-space and show how to bound the discretization error.
The remainder of the paper is organised as follows. Definitions and preliminary results
are given in Section 2. Section 3 presents our convex program and shows that, under suitable
conditions, it can be solved using a subroutine described in Section 4. Several examples including
numerical applications are discussed in Section 5. Our numerical examples assume the call prices
on a stock are given by the Black-and-Scholes formula with a constant volatility for one or two
maturities, but do not assume the stock to follow a log-normal process with a constant volatility.
Section 6 discusses various extensions of our method. Section 7 contains concluding remarks.
Most proofs are contained in the appendix.
3
Electronic copy available at: https://ssrn.com/abstract=2172315

2 Preliminaries
2.1 The modelling framework
We aim to establish model-independent bounds in a simple setting inspired from the classical
theory of multi-period markets (see (Pliska 2005, Chapter 3) and (Follmer and Schied 2004,
Ch. 5)). For simplicity, we assume for now that interest rates and dividends are null. Section 6
shows how to incorporate interest rates and dividends in our framework. Anm-period market
Mconsists ofdbasic securities on a non-empty sample space Ω. The securities pricesS
1
0
, . . . , S
d
0
at time-step 0 are known constants. The priceS
k
i
of securitykat time-stepi, 0≤i≤m, is a
function from Ω toR. LetX
i
be the price vector (S
1
i
, . . . , S
d
i
). An investor can buyξ
k
i
positions
in securityk, 1≤k≤d, at time-stepi−1 and sell them at time-stepi. Denote byξ
i
the
d-dimensional vector (ξ
k
i
), 1≤k≤d. The vectorξ
i
is an arbitrary function of the past values
of thedsecurities, i.e. it is a function ofS
k
j
, 1≤k≤d, and 1≤j≤i−1. The cumulative
payoff of the investor, which we calla gains function,is
P
m
i=1
ξ
T
i
(X
i
−X
i−1
). We assume that
zero-coupon bonds maturing at time-stepmare liquid at time 0. A financial derivative is a
function from Ω toR. A finite-support probability on Ω is a non-negative function on Ω that
takes positive values on a finite number of elements and that sums up to 1.
Definition 2.1.A risk-neutral probability is a finite-support probabilityPonΩsuch that
E
P
(g) = 0for any gains functiong.
2.2 The super-hedging cost
Consider a financial derivativeψ. We say that a financial derivativeψ
0
super-replicatesψ, and
writeψ≤
g
ψ
0
, if there is a gains functiongsuch thatψ(ω)≤ψ
0
(ω) +g(ω) forω2Ω. Thus, the
payoff of a properly hedged long position inψ
0
is always no less than the payoff ofψ. Consider a
portfolio ofγbonds that pay 1 at time-stepm. The portfolio cost isγ. Define the super-hedging
costc(ψ) =c(ψ;M) ofψas
c(ψ) = inf{γ:γ2R, ψ≤
g
γ}, (2.1)
with the usual convention that inf(;) =∞. Thusc(ψ) is the infimum price of a bond that
super-replicatesψ. LetPbe the set of risk-neutral probabilities. SinceE
P
(ψ)≤γfor any
risk-neutral probabilityPand anyγsuch thatψ≤
g
γ,
sup
P2P
E
P
(ψ)≤c(ψ). (2.2)
2.3 The super-replicating price
Assume now thatφ= (φ
1
, . . . , φ
l
) is a vector of financial derivatives that trade at prices
π
1
, . . . , π
l
at time-step 0. Letβ= (β
1
, . . . , β
l
) be a vector of lengthl. The portfolioβ
T
φ+γ
consists ofβ
j
derivativesφ
j
, 1≤j≤l, and ofγbonds that pay 1 at time-stepm. It has a cost
ofβ
T
π+γ, whereπ= (π
1
, . . . , π
l
). Define the best super-replicating priceπ
sup

sup
(ψ, φ;M)
as
π
sup
= inf
(β,γ)2V
0
β
T
π+γ, (2.3)
where
V
0
=V
0
(ψ, φ;M) ={(β, γ)2R
l
×R, ψ≤
g
β
T
φ+γ}.
In other words,π
sup
is the infimum cost of a super-replicating portfolio composed of a bond
and of positions in the derivativesφ
j
, 1≤j≤l. DefineV=V(ψ, φ;M) as
V={(β, γ)2R
l
×R:c(ψ−β
T
φ)≤γ}. (2.4)
4
Electronic copy available at: https://ssrn.com/abstract=2172315

If (β, γ)2V
0
thenψ−β
T
φ≤
g
γand so, by (2.1), (β, γ)2V. Conversely, it follows from (2.1)
that, if (β, γ)2Vandγ
0
> γ, thenψ−β
T
φ≤
g
γ
0
, and so (β, γ
0
)2V
0
. Thus,V
0
`V`
V
0
,
where
V
0
is the closure ofV
0
, and (2.3) can be rewritten as
π
sup
= inf
(β,γ)2V
β
T
π+γ. (2.5)
Note that
V` f(β, γ)2R
l
×R:E
P
(ψ)≤β
T
E
P
(φ) +γforP2P}. (2.6)
This is because the RHS of (2.6) is closed and containsV
0
, and so it containsV.
Example 2.1.Assumem= 2,d=l= 1, and the basic security is a stock valued atS
i
at
time-stepi,0≤i≤2, withφ
1
= max(S
2
−K,0)andψ= max((S
1
+S
2
)/2−K,0). As
ψ≤
1
2
1
S
1
≥K
(S
1
−S
2
) +φ
1
,
π
sup
is upper-bounded by the price ofφ
1
.
Remark 2.1.An optimal sub-replicating price and strategy forψcan be obtained by negating
an optimal super-replicating price and strategy for−ψ.
Throughout the rest of the paper, the running time refers to the number of arithmetic
operations. Denote by0
k
the null vector and by1
k
the all-one vector inR
k
, and denote bye
i
the vector whosei-th coordinate is 1 and remaining coordinates are null.
3 Super-replication as a convex program
3.1 General assumptions
We assume throughout this section that we are given positive real numbersδ≤1/2 andqsuch
that
A1.c(ψ−β
T
φ) is upper-bounded byqfor||β|| ≤δ.
A2.For any elementπ
0
of the set
S
l
i=1
{π+δe
i
, π−δe
i
},there is a risk-neutral probabilityP
withE
P
(φ) =π
0
and−q≤E
P
(ψ).
A3.Forβ2R
l
, there is a risk-neutral probabilityPsuch that
c(ψ−β
T
φ) =E
P
(ψ−β
T
φ), (3.1)
and a subroutine that, on inputβ, calculatesc(ψ−β
T
φ) andE
P
(φ) in finite timeT.
Assumptions A1, A2 and A3 will be used to bound the running time of our convex program
(see Theorem 3.2). Each time we will use Theorem 3.2 in the examples of Section 5, we will
first prove that these assumptions hold by discretizing the state-space and using techniques
developed in Sections 4 and 5. Assumption A1 implies that (0
l
, q)2Vand so, by (2.5),
π
sup
≤q. Note that ifπ
0
belongs to{π+δe
i
, π−δe
i
}, thenπandπ
0
have the same coordinates
expect for thei-th coordinate, and|π
i
−π
0
i
|=δ. Assumption 2 holds under certain no-arbitrage
conditions (see, e.g. (Kahal´e 2010, Theorem 4.6)), but will be shown directly in our examples.
On the other hand, Assumption A3 implies that there is no duality gap in (2.2) for the derivative
ψ−β
T
φ. The performance of our super-replication algorithm depends to a large extent onT
(see Theorem 3.2, and Section 5), both in theory and in practice. When the state-space is finite
and under a geometric condition (see Assumption A4), Section 4 shows that there is no duality
gap in (2.2) for a class of derivatives, and gives a construction of the subroutine in Assumption
A3.
Remark 3.1.Ifc(−ψ)is upper-bounded by a real numberq
0
then, by(2.2),−q
0
≤E
P
(ψ)for
P2P.
5
Electronic copy available at: https://ssrn.com/abstract=2172315

3.2 The convex program
We first show that
V={(β, γ)2R
l
×R:E
P
(ψ)≤β
T
E
P
(φ) +γforP2P}. (3.2)
By (2.6), the RHS of (3.2) containsV. Conversely, assume that (β, γ) belongs to the RHS
of (3.2). By Assumption A3, there isP2Psuch thatc(ψ−β
T
φ) =E
P
(ψ−β
T
φ), and so
c(ψ−β
T
φ)≤γ. Hence, (β, γ)2V.
ThusVis a convex set and (2.5) is a convex program since it implies thatπ
sup
is the
infimum of a linear function over a convex set. Convex programs over bounded sets that admit
a separation oracle can be solved efficiently under conditions stated in Subsection 3.4. Note
thatVis unbounded since (0
l
, γ)2Vforγ≥q, but (2.5) can be rewritten as
π
sup
= inf
(β,γ)2V
0
β
T
π+γ,where (3.3)
V
0
={(β, γ)2V:β
T
π+γ≤q+ 1}.
Lemma 3.1 shows thatV
0
is bounded. For the rest of the paper, letR
0
= (2q+ 1)/δand
R
1
= 4
(1 +q)

l(1 +||π||)
δ
.
Lemma 3.1.Let
E={(β, γ)2R
l
×R:−q≤β
T
(π±δe
i
) +γfor1≤i≤l}, (3.4)
E
0
=E
0
(l, π, q, δ) ={(β, γ)2 E:β
T
π+γ≤q+ 1}. (3.5)
ThenVθ E,V
0
θ E
0
and, for(β, γ)2 E
0
,||β||

≤R
0
and||(β, γ)|| ≤R
1
. Furthermore,V
0
contains the ball of radiusδ(1 +||π||)
−1
centered at(0
l
, q+δ).
3.3 A separation oracle forV
0
A separation oracle for a convex setCθR
k
is a subroutine with the following property. The
oracle accepts as input any vectory2R
k
. Ify2Cthe oracle returns a ”Yes”, whereas ify /2C
the oracle returns a vectora2R
k
− {0}such thata
T
y≤a
T
xfor anyx2C.
Proposition 3.1.V
0
admits a separation oracle that runs inT+O(1)time, whereTis the
running time of the subroutine in Assumption A3. On any input(β, γ)2R
l
×R, the oracle
either returns a ”Yes”, or returns one of the two vectors−(π,1)or(E
P
(φ),1), whereP2Pis
such thatβ
T
E
P
(φ) +γ≤E
P
(ψ).
Proof.On input (β, γ)2R
l
×R, the separation oracle forV
0
runs through the following steps.
1. Leta
0
= (π,1). Ifa
T
0
(β, γ)> q+ 1, the oracle returns−a
0
. This is a valid return since
a
T
0

0
, γ
0
)≤q+ 1 for (β
0
, γ
0
)2V
0
, and (β, γ)62V
0
.
2. Else, calculatec(ψ−β
T
φ) via the subroutine in Assumption A3. Ifc(ψ−β
T
φ)≤γthe
oracle returns a ”Yes”.
3. Else, use the subroutine in Assumption A3 on inputβto calculatea= (E
P
(φ),1), where
Pis a risk-neutral probability such that (3.1) holds. By (3.1),γ≤E
P
(ψ−β
T
φ) and
soa
T
(β, γ)≤E
P
(ψ). On the other hand, (3.2) implies thatE
P
(ψ)≤a
T

0
, γ
0
) for

0
, γ
0
)2V. Hencea
T
(β, γ)≤a
T

0
, γ
0
). The oracle returnsa.
6
Electronic copy available at: https://ssrn.com/abstract=2172315

3.4 Cutting plane algorithms
We now show how to solve the convex program (3.3) using a cutting plane algorithm. We
assume throughout this subsection thatCis a convex subset ofR
k
that contains a ball of
radiusr, is contained in the ballB(0, R) of radiusRcentered at 0, and thatCadmits a
separation oracle. We describe a generic cutting plane algorithm (see (Gr¨otschel, Lov´asz and
Schrijver 1981, Atkinson and Vaidya 1995, Vaidya 1996, Bertsimas and Vempala 2004) and
references therein) for minimizinga
T
0
xforx2C, wherea
0
is a vector ofR
k
. The algorithm
takes as inputr,R,a
0
, a real numberffl2(0,1), and a separation oracle forC. It outputs a
vectory2Csuch thata
T
0
y≤a
T
0
x+fflfor anyx2C. The algorithm makesNiterations and
uses the following steps:
1. LetR
0
θR
k
be a bounded region that containsB(0, R).
2. Fori= 1 toN, choose a pointy
i
2 R
i−1
. Query the separation oracle forCony
i
. If
the oracle returns a ”Yes”, leta
i
=−a
0
. We say in this case thatiis a feasible index.
Otherwise, leta
i
be the vector returned by the oracle. In both cases, letR
i
be a region
such that
R
i
ι R
i−1
∩ {x2R
k
:a
T
i
y
i
≤a
T
i
x}. (3.6)
3. Outputy
j
, wherejis a feasible index such thata
T
0
y
j
≤a
T
0
y
i
for all feasible indicesi,
1≤i≤N.
The choice ofy
i
andR
i
depends on the specific cutting plane algorithm. In a basic analytic cen-
ter cutting plane algorithm (see (Atkinson and Vaidya 1995) and references therein, and (Boyd,
Vandenberghe and Skaf 2008) for a detailed description, which largely inspired our numerical
implementation),R
0
is the set of vectorsxwith||x||

≤R,R
i
is the RHS of (3.6) fori≥1,
andy
i
is the analytic center ofR
i−1
. Let
I={i2[1, N] :a
i
6=−a
0
},
˜
C={x2 R
0
:a
T
i
y
i
≤a
T
i
xfori2I}.
Note thatCθ
˜
CsinceCθ R
0
and, fori2I,a
i
is the vector returned by the separation
oracle forCon inputy
i
and so, forx2C,a
T
i
y
i
≤a
T
i
x. A cutting plane algorithm based on
the volumetric center yields the following result.
Theorem 3.1.(Vaidya 1996, Sections 2 and 4). Assumer≤1≤ ||a
0
||andR≥1. There is
a cutting plane algorithm that finds a vectory2Csuch thata
T
0
y≤a
T
0
x+fflfor everyx2
˜
C.
The algorithm makesNcalls to the separation oracle forC, where
N=O(kln(
2kR
2
||a
0
||
fflr
)), (3.7)
and runs inO(N(k
3
+T))time, whereTis the running time of the oracle.
SinceCθ
˜
C,a
T
0
y≤a
T
0
x+fflfor everyx2C. In the convex program (3.3),a
0
= (π,1), the
number of variables isk=l+ 1,C=V
0
and, by Lemma 3.1,r=δ(1 +||π||)
−1
andR=R
1
.
The separation oracle forV
0
described in Proposition 3.1 can be used in Step 2 of the cutting
plane algorithm.
3.5 A lower bound onπ
sup
via risk-neutral probabilities
Assume we use a generic cutting plane algorithm withNiterations to solve the convex pro-
gram (3.3). For anyP2Psuch thatE
P
(φ) =π, it follows from (2.5) and (3.2) that
E
P
(ψ)≤π
sup
. We calculate below a lower bound onπ
sup
by choosingPto be a weighted
7
Electronic copy available at: https://ssrn.com/abstract=2172315

average of the risk-neutral probabilities defined in Assumption A2 or generated by the cutting
plane algorithm. Fori2I,a
i
is the vector returned by the separation oracle forV
0
on input
y
i
= (β
i
, γ
i
) and so, by Proposition 3.1, there isP
i
2Psuch that
a
i
= (E
P
i
(φ),1) anda
0
i
≤E
P
i
(ψ), (3.8)
wherea
0
i
=a
T
i
y
i
. For 1≤i≤l, seta
i+N
= (π+δe
i
,1) anda
i+l+N
= (π−δe
i
,1). Finally, for
N+ 1≤i≤N+ 2l, seta
0
i
=−q, and letI
0
=I∪[N+ 1, N+ 2l]. By Assumption A2, for
N+ 1≤i≤N+ 2l, there isP
i
2Psuch that (3.8) holds. Leta
0
= (π,1) and consider the
linear program:
b
0
= max
λ
X
i2I
0
λ
i
a
0
i
(3.9)
subject to:
λ
i
≥0 fori2I
0
,and
X
i2I
0
λ
i
a
i
=a
0
. (3.10)
This program has|I
0
|+l+ 1 constraints and|I
0
|variables, with|I
0
| ≤N+ 2l. It is feasible
since the constraints (3.10) are satisfied whenλ
i
= 0 fori2Iandλ
i
= (2l)
−1
fori2
[N+ 1, N+ 2l]. By (3.8), for anyλ
i
’s satisfying (3.10),
P
i2I
0
λ
i
= 1,
P
i2I
0
λ
i
E
P
i
(φ) =πand
P
i2I
0
λ
i
a
0
i

P
i2I
0
λ
i
E
P
i
(ψ). ThusP=
P
i2I
0
λ
i
P
i
is a risk-neutral probability,E
P
(φ) =πand
P
i2I
0
λ
i
a
0
i
≤E
P
(ψ). Henceb
0
≤E
P
(ψ)≤π
sup
. The following lemma will show the tightness
of this lower bound onπ
sup
.
Lemma 3.2.For any generic cutting plane algorithm,inf
x2
˜
C
a
T
0
x≤b
0
.
Combining the preceding results yields the following.
Theorem 3.2.Under Assumptions A1, A2 and A3,V
0
admits a separation oracle that runs
inT+O(1)time, whereTis the running time of the subroutine in Assumption A3, and
V
0
θB(0, R
1
). By solving the convex program(3.3), we can calculate inO(N(l
3
+T))time a
vector(β
Λ
, γ
Λ
)2V
0
such that||β
Λ
||

≤R
0
and
π
sup
≤β
ΛT
π+γ
Λ
≤π
sup
+ffl; (3.11)
where
N=O(lln(
l(1 +q)(1 +||π||)
fflffi
)). (3.12)
In addition, by solving a linear program withO(N)variables and constraints, we can find weights
λ
i
≥0,i2I
0
, that sum up to1, withE
P
(φ) =π, whereP=
P
i2I
0
λ
i
P
i
is a risk-neutral
probability, and
β
ΛT
π+γ
Λ
≤E
P
(ψ) +ffl: (3.13)
Thus the algorithm calculatesπ
sup
with precisionffland outputs a portfolio that super-replicates
ψat cost at mostπ
sup
+ 2ffl.
Proof.As shown in Subsection 3.4, we can solve the convex program (3.3) by using the cutting
plane algorithm in (Vaidya 1996, Sections 2 and 4). The algorithms findsy= (β
Λ
, γ
Λ
)2V
0
such that (3.11) holds. Sincer=δ(1+||π||)
−1
andR=R
1
, (3.12) follows from (3.7) after some
calculations. Furthermore, since (β
Λ
, γ
Λ
)2V, the discussion in subsection 2.3 shows thatψis
super-replicated by the portfolioβ
ΛT
φ+γ
Λ
+ffl, whose costβ
ΛT
π+γ
Λ
+fflis at mostπ
sup
+ 2ffl.
Lemma 3.1 implies that||β
Λ
||

≤R
0
. On the other hand, by Lemma 3.2, if we solve the
linear program (3.9) and (3.10), we findb
0
such that inf
x2
˜
C
a
T
0
x≤b
0
≤E
P
(ψ), wherePis a
risk-neutral probability such thatE
P
(φ) =π. Since, by Theorem 3.1,a
T
0
y≤a
T
0
x+fflforx2
˜
C,
a
T
0
y≤E
P
(ψ) +ffl. Hence (3.13).
8
Electronic copy available at: https://ssrn.com/abstract=2172315

4 Recursive calculation of the super-hedging cost
Theorem 3.2 shows how to calculateπ
sup
if Assumptions A1, A2 and A3 hold. We will see in
Section 5 how to verify Assumptions A1 and A2. We show in this section that A3 holds for
a class of financial derivatives when the state-space is finite and under a geometric condition
described in Assumption A4. We also give a construction of the subroutine needed in A3 by
describing an algorithm that calculates the super-hedging cost of a financial derivative Ψ by
backward induction using concave envelopes, in the same spirit as in (Carassus, Gobet and
Temam 2007), and applying the algorithm with Ψ =ψ−β
T
φ, for a given vectorβ.
Letfbe a real-valued function defined on a subsetWofR
d
and bounded above by a linear
function. Denote by
c
Wthe convex hull ofWand by
fthe concave envelope off, i.e. the
smallest concave function on
c
Wbounded below byfonW. Ifx2
c
W, denote byQ(x, W) the
set of non-negative functionsQonWthat take positive values on a finite number of elements,
sum up to 1, with
P
y2W
Q(y)y=x. Note thatQdefines a probability onW, endowed with
its Borelσ-algebra. It can be shown (Boyd and Vandenberghe 2004, Exercise 3.30) that, for
x2
c
W,
f(x) = sup
Q2Q(x,W)
E
Q
(f), (4.1)
where
E
Q
(f) =
X
y2W
Q(y)f(y).
WhenWis finite, (4.1) can be rewritten as
f(x) = sup
Q
{
X
y2W
Q(y)f(y)|Q(y)≥0 fory2W,
X
y2W
Q(y) = 1,
X
y2W
Q(y)y=x}, (4.2)
whereQis a real-valued function onW. By linear programming duality,
f(x) = min
η
0
2R,η2R
d

0

T
x|f(y)≤η
0

T
yfory2W}. (4.3)
Let (η
0
, η) be a pair that attains the RHS of (4.3). Then, fory2W,
f(y)≤
f(x) +η
T
(y−x). (4.4)
Thus,fis upper-bounded by a linear function valued at
f(x) atx.
For 1≤i≤m, letD
i
= Im(X
1
, . . . , X
i
) be the set of paths thatXcan follow from time-step
1 throughi, and setD
0
={;}. Forθ2D
i
, let
D(θ) ={x2R
d
: (θ, x)2D
i+1
} (4.5)
be the set of possible values ofX
i+1
given thatXhas followed the pathθin the firstitime-
steps. By convention, ifi= 0 andθ=;, (θ, x) refers tox. Ifζis a real-valued function on
D
i+1
, denote byζ(θ, .) the function that mapsxtoζ(θ, x) forx2D(θ). The rest of this section
makes the following assumption. By convention,x
0
=X
0
.
A4.Ω is finite and, if 0≤i≤m−1 andθ= (x
1
, . . . , x
i
)2D
i
, thenx
i
2
[
D(θ).
Assumption A4 implies that, for any given path thatXhas followed in the firstitime-steps,
X
i
belongs to the convex hull of the set of possible values ofX
i+1
. Consider now a financial
derivative Ψ of the form Ψ = Ψ
Λ
(X
1
, . . . , X
m
), where Ψ
Λ
is a real-valued function defined on
D
m
that can be calculated in finite time. Whenm= 1, Proposition 4.1 shows that,
c(Ψ) =
Ψ
Λ
(X
0
) = sup
Q2Q(X
0
,D
1
)
E
Q

Λ
),
and soc(Ψ) is equal to the concave envelope of Ψ
Λ
evaluated atX
0
. Proposition 4.1 also shows
how to calculate by backward induction the super-hedging cost of Ψ in anm-period market, for
any integerm.
9
Electronic copy available at: https://ssrn.com/abstract=2172315

Proposition 4.1.Define the functionsΨ
Λ
i
by backward induction as follows:Ψ
Λ
m
= Ψ
Λ
and
Ψ
Λ
i
(θ) =
Ψ
Λ
i+1
(θ, .)(x
i
)for0≤i≤m−1andθ= (x
1
, . . . , x
i
)2D
i
. LetΨ
i
be the financial
derivativeΨ
Λ
i
(X
1
, . . . , X
i
). Thenc(Ψ) = Ψ
0
and
Ψ
Λ
i
(θ) = sup
Q2Q(x
i
,D(θ))
E
Q

Λ
i+1
(θ, .)). (4.6)
We can interpret Ψ
i
as the super-hedging cost at time-stepiof Ψ, and (4.6) as saying that
Ψ
i
is equal to the super-hedging cost of Ψ
i+1
in the underlying single-period market at time-step
i.
Proposition 4.2 below shows that, as in (Pliska 2005, Section 3.4), we can paste together
risk-neutral probabilities in single-period markets by multiplying them along any given path to
obtain a risk-neutral probabilityPin them-period market. It also describes how to calculate
E
P
(η), for a class of financial derivativesη.
Proposition 4.2.Forθ= (x
1
, . . . , x
i
)2D
i
, choose a probabilityP(θ)2Q(x
i
, D(θ)). There is
a risk-neutral probabilityPsuch that, for any deterministic functionη
Λ
onD
m
,E
P
(η) =η
Λ
0
(;),
whereη=η
Λ
(X
1
, . . . , X
m
), and the functionsη
Λ
i
are defined onD
i
by backward induction as
follows:η
Λ
m

Λ
and, for0≤i≤m−1andθ2D
i
,
η
Λ
i
(θ) =E
P(θ)

Λ
i+1
(θ, .)). (4.7)
Furthermore,c(Ψ) =E
P
(Ψ)if allP(θ)attain the RHS of(4.6).
We now use Propositions 4.1 and 4.2 to show that Assumption A3 holds and to give a generic
construction of the subroutine needed in Assumption A3. Assume thatψ=ψ
Λ
(X
1
, . . . , X
m
)
andφ=φ
Λ
(X
1
, . . . , X
m
), whereψ
Λ
(resp.φ
Λ
) is a function fromD
m
toR(resp.R
l
). On input
β, the subroutine uses the following steps.
1. Let Ψ =ψ−β
T
φ, Ψ
Λ
m

Λ
−β
T
φ
Λ
andφ
Λ
m

Λ
.
2. Fori=m−1 down to 0 andθ= (x
1
, . . . , x
i
)2D
i
, choose a probabilityP(θ)2
Q(x
i
, D(θ)) that maximizesE
P(θ)

Λ
i+1
(θ, .)). Set Ψ
Λ
i
(θ) =E
P(θ)

Λ
i+1
(θ, .)) andφ
Λ
i
(θ) =
E
P(θ)

Λ
i+1
(θ, .)).
3. Outputc(Ψ) = Ψ
Λ
i
(;) andE
P
(φ) =φ
Λ
0
(;), whereP2Pis obtained by pasting the
probabilitiesP(θ).
In other words, we find by backward induction, in every single-period market at time-stepi,
a probabilityP(θ) that attains RHS of (4.6), and use the probabilitiesP(θ) to calculate both
c(Ψ) andE
P
(φ). By Proposition 4.2,c(Ψ) =E
P
(Ψ).
FindingP(θ) can be done in finite time, as shown in Subsection 4.1, and so Assumption A3
holds. But, since|D
m−1
|is in general exponential inm, so is the running time of a naive imple-
mentation of Step 2. The running time can often be considerably reduced using Remarks 4.1
and 4.2 below and techniques used in the valuation of path-dependent derivatives via binomial
trees (Hull 2012, Section 26.5). The optimized subroutine replaces the loop onθin Step 2 by
a loop onx
i
and on at most one additional state variable. For instance, ifψis a variance swap
andφconsists of call options, the loop onθis replaced by a loop onx
i
. Ifψis a volatility swap
(resp. Asian option), we can replace the loop onθby a loop onx
i
and on the current realized
variance (resp. the price running sum). See Section 5 for details.
Remark 4.1.Fixi2 {0, . . . , m}. Consider a financial derivativeζwhich is a determinis-
tic function ofX
0
, . . . , X
m
, and a financial derivativeζ
0
which is a deterministic function of
X
0
, . . . , X
i
. LetΨ =ζ+ζ
0
. It can be shown by backward induction thatΨ
i

i

0
, whereΨ
i
(resp.ζ
i
) is the super-hedging cost ofΨ(resp.ζ) at time-stepi.
10
Electronic copy available at: https://ssrn.com/abstract=2172315

Remark 4.2.Fixi2 {1, . . . , m−1}. Consider a financial derivativeζof the formζ=
ζ
Λ
(X
1
, . . . , X
m
), whereζ
Λ
is a real-valued function onD
m
. Assume thatζ
Λ
(x
1
, . . . , x
m
)and
D(x
1
, . . . , x
j
)depend on(x
1
, . . . , x
i
)only through a (one or multi-dimensional) deterministic
functionh(x
1
, . . . , x
i
)forj≥i. It can be shown by backward induction that the super-hedging
costζ
i
ofζat time-stepiis a deterministic function ofX
i
and ofh(X
1
, . . . , X
i
).
4.1 Convex hull calculation
By (4.2) thru (4.4), we can use linear programming to findQ 2Q(x
i
, D(θ)) that attains the
RHS of (4.6), whereθ= (x
1
, . . . , x
i
)2D
i
. Whend= 1, this can be done more efficiently via
the following proposition.
Proposition 4.3((Andrew 1979)).Given a finite setWθRwhose elementsx
1
, . . . , x
n
are
sorted in increasing order, a real numberx2[x
1
, x
n
], and a functionfthat takes known values
onW, we can calculate inO(n)time a probabilityQ 2Q(x, W)that maximizesE
Q
(f), and a
real numberξ
Λ
such that, fory2W,
f(y)≤E
Q
(f) +ξ
Λ
(y−x). (4.8)
Furthermore,Qis supported on two points.
The algorithm, due to (Andrew 1979), first calculates the ordered subsetU(j) ofW, 2≤
j≤n, recursively as follows. LetU(2) ={x
1
, x
2
}. AssumeU(j−1) ={x
0
1
, . . . , x
0
h
}. Letkbe
the largest index such that (x
0
k
, f(x
0
k
)) is above the segment [(x
0
k−1
, f(x
0
k−1
)),(x
j
, f(x
j
))], if such
an index exists, otherwise letk= 1. SetU(j) ={x
0
1
, . . . , x
0
k
, x
j
}. Letx
0
andx
00
be consecutive
elements ofU(n) such thatx2[x
0
, x
00
]. The algorithm outputs the probabilityQthat assigns
s= (x
00
−x)/(x
00
−x
0
) tox
0
and 1−stox
00
, and
ξ
Λ
=
f(x
00
)−f(x
0
)
x
00
−x
0
. (4.9)
5 Examples
LetSbe a stock valued atS
i
at time-stepi, 0≤i≤m, whereS
0
is known. For 1≤i≤m, we
are given a (possibly empty) increasing sequenceK
i,j
of positive strikes, 1≤j≤l
i
, together
with pricesc
i,j
of calls with maturityt
i
and strikeK
i,j
. By convention,l
i
= 0 if no calls trade
at time-stepi. LetKbe the set that consists ofS
0
and ofK
i,j
, 1≤i≤m, 1≤j≤l
i
. Given
subsetsF
i
ι KofR
+
for 1≤i≤m, consider the marketM(F
1
, . . . , F
m
) whereS
i
ranges inF
i
for 1≤i≤m. We formally buildM(F
1
, . . . , F
m
) by setting Ω ={S
0
} ×F
1
× ∙ ∙ ∙ ×F
m
,with
S
i
(ω) =x
i
forω= (x
0
, . . . , x
m
)2Ω and 0≤i≤m.We assume thatF
i−1
θ
b
F
i
for 2≤i≤m,
so that Assumption A4 holds if the setsF
i
, 1≤i≤m, are finite. IfF
i
=Ffor 1≤i≤m,
denoteM(F
1
, . . . , F
m
) byM
m
(F).
Definition 5.1.Consider an ordered pair{k
Λ
, k
Λ
}of fictitious strikes such that
0≤k
Λ
<min(K)≤max(K)< k
Λ
≤ ∞.
For1≤i≤m, set
K
i,0
=k
Λ
, K
i,l
i
+1
=k
Λ
, c
i,0
=S
0
−k
Λ
andc
i,l
i
+1
= 0. (5.1)
We say that{k
Λ
, k
Λ
}is acceptable if, for1≤i≤i
0
≤m,i≤i
00
≤m,1≤j≤l
i
,0≤j
0
≤l
i
0
+1,
0≤j
00
≤l
i
00
+ 1, ifK
i
0
,j
0
≤K
i,j
≤K
i
00
,j
00
,(i, j)/2 {(i
0
, j
0
),(i
00
, j
00
)}, andK
i
0
,j
0
< K
i
00
,j
00
, then
max(0, S
0
−K
i,j
)< c
i,j
< wc
i
0
,j
0
+ (1−w)c
i
00
,j
00
, (5.2)
wherew= (K
i
00
,j
00
−K
i,j
)/(K
i
00
,j
00
−K
i
0
,j
0
). By convention,w= 1ifK
i
00
,j
00
=∞.
11
Electronic copy available at: https://ssrn.com/abstract=2172315

(5.1) can be interpreted by noting that, ifF
m
θ[k
Λ
, k
Λ
], a call price with strikek
Λ
(resp.
k
Λ
) must equalS
0
−k
Λ
(resp. 0). On the other hand, it is shown in (Davis and Hobson 2007)
that, ifF
m
θ[k
Λ
, k
Λ
] and under no-arbitrage constraints, (5.2) holds if the strict inequalities
are replaced with weak inequalities. Indeed, no-arbitrage constraints imply that call prices are
convex with respect to the strike and non-decreasing with respect to time, and (5.2) combines
a strict version of these two constraints.
Forx≥0 and 1≤i≤m, define the vectorf
i
(x) = (max(x−K
i,j
,0)), 1≤j≤l
i
, and let
b
i
2R
l
i
. Consider the vector of callsφ= (f
i
(S
i
)), and setβ= (b
i
), 1≤i≤m. Letψbe a
financial derivative that paysψ
Λ
(S
1
, . . . , S
m
), whereψ
Λ
is a deterministic function, such that
c(ψ) andc(−ψ) are finite. Consider the financial derivative Ψ =ψ−β
T
φ. We will use the
following proposition to show that Assumptions A1 and A2 hold.
Proposition 5.1.Assume that an acceptable pair{k
Λ
, k
Λ
}is contained inF
i
, for1≤i≤m.
Letδ
0

0
(k
Λ
, k
Λ
)be the minimum of1/2and of the minimum difference between the right-
hand sides and left-hand sides of the inequalities in(5.2). Then A1 and A2 hold in the market
M=M(F
1
, . . . , F
m
)ifq≥max(c(ψ;M), c(−ψ;M)) +δ
0

lS
0
and0< δ < δ
0
. Furthermore,
||π|| ≤S
0

l. (5.3)
In the following examples, we show that A3 holds as well. We then use Theorem 3.2 to
calculate an optimal super-replicating price and a corresponding hedging portfolio forψvia the
call components ofφ. An optimal sub-replicating price and a corresponding hedging portfolio
can be derived as well using Remark 2.1. In our examples, we first derive discretized optimal
model-independent bounds by assuming theF
i
’s to be finite, then give an empirical and a
theoretical estimate of the discretization error. The empirical estimate is calculated using a large
number of discretization points. Our numerical examples were obtained using an analytic center
cutting plane algorithm with at most 200 iterations that calculated the model-independent price
bound (or its discrete approximation) within an error of order 10
−5
. The simulation experiments
were performed on a desktop PC with an Intel Pentium 2.90 GHz processor and 4 Go of RAM,
running Windows 7 Professional. The codes were written in the C++ programming language,
and the compiler used was Microsoft Visual C++ 2013. The computing time is given in seconds.
5.1 Forward start options
Consider a forward start optionψ. For ease of exposition, assume the option is an at the money
call that pays max(0, S
2
−S
1
) at maturity. Extension to the general case is straightforward.
The derivative Ψ pays Ψ
Λ
(S
1
, S
2
), where
Ψ
Λ
(x
1
, x
2
) = max(0, x
2
−x
1
)−b
T
1
f
1
(x
1
)−b
T
2
f
2
(x
2
).
Forx
1
2F
1
, let
Ψ
Λ
1
(x
1
;F
2
) = sup
Q2Q(x
1
,F
2
)
E
Q

Λ
(x
1
, .)). (5.4)
IfF
1
andF
2
are finite, by Proposition 4.1, in the marketM(F
1
, F
2
), the super-hedging cost of
Ψ at time-step 1 is Ψ
Λ
1
(S
1
;F
2
), and the super-hedging cost of Ψ at time-step 0 is
c(Ψ;M(F
1
, F
2
)) = sup
Q
0
2Q(S
0
,F
1
)
E
Q
0

Λ
1
(.;F
2
)). (5.5)
We illustrate the calculation ofc(Ψ;M
2
(F)) whenS
0
= 100 andF={70,80, . . . ,130}. Assume
φconsists of the calls maturing at time-stepiwith strikeK
i,j
= 80 + 10jfor 1≤i≤2
and 1≤j≤3. Letb
1
= (−0.3,−0.2,−0.4) andb
2
= (0.5,0.4,0.3). Proposition 4.3 shows
how to calculate Ψ
Λ
1
(x
1
;F) forx
1
2Fand probabilitiesP(x
1
) andP(;) that attain the RHS
of (5.4) and (5.5), respectively. Using Proposition 4.2, we can then calculateE
P
(φ), whereP
12
Electronic copy available at: https://ssrn.com/abstract=2172315

is a risk-neutral probability such thatc(Ψ;M
2
(F)) =E
P
(Ψ). Table 1 lists the values of Ψ
whenS
1
= 90. Fig. 1 plots the function Ψ
Λ
(90, .) and its concave envelope, which shows that
Ψ
Λ
1
(90;F
1
) = 2/3×5 + 1/3×0 = 10/3. The probability that assigns a weight 2/3 to 100 and
1/3 to 70 maximises the RHS of (5.4) whenx
1
= 90. We can perform a similar calculation
for eachx
1
2Fand then calculatec(Ψ;M
2
(F)) via (5.5). Fig. 2 draws a tree by connecting
eachx
1
2F(resp.S
0
) to the support ofP(x
1
) (resp.P(;)), and Table 2 gives the probability
p
u
assigned to the largest element in the support ofP(x
1
) (resp.P(;)). It also shows that
E
P
(η) = $7.5, whereηis the ATM vanilla call maturing at the second time-step. The expected
value underPof any component ofφcan be calculated in a similar manner.
We now show how to calculate the best super-replicating (resp. sub-replicating) price
π
sup
(R
+
) (resp.π
inf
(R
+
)) ofψwithout restrictions onS
1
andS
2
other than being non-negative,
and set Ψ
Λ
1
(x
1
) = Ψ
Λ
1
(x
1
;R
+
) forx
1
≥0. It follows from (5.4) and the convexity of Ψ
Λ
(x
1
, .)
on any interval disjoint withKthat Ψ
Λ
1
(x
1
) depends only on the values of Ψ
Λ
(x
1
, .) onK ∪ {0}
and on its asymptotic slope on [max(K),∞). Furthermore, it can be shown that Ψ
Λ
1
is lin-
ear on [max(K),∞), and so we only need to know the values of Ψ
Λ
1
on [0,max(K)] and its
slope on [max(K),∞) to calculatec(Ψ;M
2
(R
+
)) via (5.5). This suggests thatπ
sup
(R
+
) is well
approximated by the best super-replicating priceπ
sup
(F
1
, F
2
) ofψin the marketM(F
1
, F
2
),
where
F
1
=K ∪ {max(K)
j
n
,0≤j≤n} ∪ {ffl
0−1
max(K)},and (5.6)
F
2
=K ∪ {0; ffl
0−1
max(K); ffl
0−2
max(K)}, (5.7)
nis a positive integer, andffl
0
2(0,1). Theorem 5.1 below shows how to calculateπ
sup
(F
1
, F
2
)
and gives an upper bound on the discretization error. The constants behind theOnotation
in (5.8) and in Section F depend onl,S
0
,k
Λ
0
, the calls strikes, maturities and prices, but do not
depend onnandffl
0
.
Theorem 5.1.Assume that{0, k
Λ
0
}is acceptable, wherek
Λ
0
is a positive real number. Then, for
ffl
0
2(0,max(K)/k
Λ
0
],π
sup
(F
1
, F
2
)can be calculated inO(N(l
3
+ln))total time with precisionffl
via the convex program(3.3), where
N=O(lln(
l(1 +S
0
)
fflffi
0
(0, k
Λ
0
)
)).
V
0
has a separation oracle that runs inO(ln)time. Furthermore,
π
sup
(F
1
, F
2
)−π
sup
(R
+
) =O(n
−2
+ffl
0
). (5.8)
Proof.Letffl
0
2(0,max(K)/k
Λ
0
) andk
Λ
=ffl
0−1
max(K). Sincek
Λ
≥k
Λ
0
, it follows from Defi-
nition 5.1 that{0, k
Λ
}is acceptable. Furthermore, an easy calculation shows thatδ
0
(0, k
Λ
)≥
δ
0
(0, k
Λ
0
). On the other hand, since−ψ≤0 andψ≤S
2
, the super-hedging costs ofψand of
−ψin the marketM(F
1
, F
2
) are at mostS
0
. Thus, by Proposition 5.1, Assumptions A1 and
A2 hold forM(F
1
, F
2
) if
q=S
0
(1 +

l) andδ=δ
0
(0, k
Λ
0
)/2. (5.9)
Proposition 4.3 shows how to calculate Ψ
Λ
1
(x
1
;F
2
) for allx
1
2F
1
,c(Ψ;M(F
1
, F
2
)), and prob-
abilitiesP(x
1
) andP(;) that attain the right-hand sides of (5.4) and (5.5), respectively, in
total timeO(|F
1
||F
2
|). By Proposition 4.2, there is a risk-neutral probabilityPinM(F
1
, F
2
)
such thatc(Ψ;M(F
1
, F
2
)) =E
P
(Ψ) and, for any financial derivativeη=η
Λ
(S
1
, S
2
), if we set
η
Λ
1
(x
1
) =E
P(x
1
)

Λ
(x
1
, .)) forx
1
2F
1
, thenE
P(;)

Λ
1
) =E
P
(η). Thus, we can then calculate
E
P
(φ) inO(l) time, and so A3 holds, withT=O(ln). The first part of the theorem then
follows from Theorem 3.2 and (5.3). The proof of (5.8) is in Section F.
13
Electronic copy available at: https://ssrn.com/abstract=2172315

Table 1: The function Ψ
Λ
(90, .).
S
2
70 80 90 100 110 120 130
Ψ
Λ
(90, .) 0 0 0 5 6 4 2
Figure 1: The solid line plots the payoff of Ψ whenS
1
= 90 and the dotted line plots the
corresponding upper hull.
It follows from Theorem 5.1 that, asfflgoes to 0, we can calculateπ
sup
(R
+
) with precision
O(ffl) in total timeO(ffl
−1/2
ln(ffl
−1
)) by settingn=ffl
−1/2
andffl
0
=ffl. (Beiglb¨ock, Henry-Labord`ere
and Penkner 2013) calculate a discrete approximation ofπ
sup
(R
+
) similar toπ
sup
(F
1
, F
2
) using
linear programming with Θ(n) variables and constraints. Our algorithm is much faster for large
values ofn.
We calculateπ
inf
(R
+
) in a similar manner using Remark 2.1 and setting
Ψ
Λ
(x
1
, x
2
) =−max(0, x
2
−x
1
)−b
T
1
f
1
(x
1
)−b
T
2
f
2
(x
2
).
We first calculate the best sub-replicating priceπ
inf
(F
0
1
, F
0
2
) ofψin the marketM(F
0
1
, F
0
2
), where
F
0
1
={0; ffl
0−1
(maxK)} ∪ K,
F
0
2
=F
0
1
∪ {ffl
0−2
(maxK)},
and 0¡ ffl
0
<1. The choice ofF
0
i
can be motivated in a way similar to that ofF
i
in (5.6)
and (5.7), by noting that Ψ
Λ
(x
1
, .) is linear on any interval disjoint withK ∪ {x
1
}, and that
Ψ
Λ
1
is convex on any interval disjoint withK. The constant behind theOnotation in (5.10)
depends onl,S
0
, the calls strikes, maturities and prices, but does not depend onffl
0
.
Theorem 5.2.Assume that{0, k
Λ
0
}is acceptable, wherek
Λ
0
is a positive real number. Then,
forffl
0
2(0,max(K)/k
Λ
0
],π
inf
(F
0
1
, F
0
2
)can be calculated inO(Nl
3
)total time with precisionfflvia
the convex program(3.3), where
N=O(lln(
l(1 +S
0
)
fflffi
0
(0, k
Λ
0
)
)).
V
0
has a separation oracle that runs inO(l
2
)time. Furthermore,
π
inf
(R
+
)−π
inf
(F
0
1
, F
0
2
) =O(ffl
0
). (5.10)
Proof.The first part of the theorem can be shown as in the proof of Theorem 5.1. The proof
of (5.10) is in Section G.
14
Electronic copy available at: https://ssrn.com/abstract=2172315

Figure 2: Connecting eachx
1
2F(resp.S
0
) to the support of a probability that maximises
the RHS of (5.4) (resp. (5.5)). For instance, the probability that assigns a weight 2/3 to 100
(represented by L) and 1/3 to 70 (represented by O) maximises the RHS of (5.4) whenx
1
= 90
(represented by F).
Table 2: The probabilitiesp
u
of an ”up” movement and the values of Ψ
i
(resp.η
Λ
i
) calculated
via Proposition 4.1 (resp. Proposition 4.2) by backward induction inside the tree of Fig. 2,
whereiis the time-step of the corresponding node.
node A B C D E F G H
p
u
1/2 1 2/3 1/2 1/2 2/3 1/2 1
Ψ
i
1.1666 -12 -3.3333 -1 1 3.3333 5 0
η
Λ
i
7.5 30 20 15 5 0 0 0
15
Electronic copy available at: https://ssrn.com/abstract=2172315

Table 3: Optimal super-replication and corresponding hedging of the forward-start option via
calls, withn= 10
6
andffl
0
= 10
−5
. The computing time is 33 seconds. The optimal super-
replicating price is $5.2756. The optimal sub-replicating price is $1.9363, and is obtained in 0.4
seconds. The Black-and-Scholes price is $3.9878.
Strike 70 80 90 100 110 120 130
b
1
0.1661 -0.2734 -0.4729 -0.4261 -0.4729 0.3096 0.0000
b
2
0.4716 0.4624 0.4366 0.4624 0.4366 0.4624 0.2461
Table 4: The discretization error for optimal super-replication of the forward-start option esti-
mated usingn= 10
6
.
n Error Computing time
100 9.7×10
−3
0.4
200 1.2×10
−3
0.4
400 7.2×10
−4
0.4
800 1.8×10
−4
0.4
1600 1.3×10
−5
0.4
In our numerical example,t
1
= 1/6 (two months) andt
2
= 5/12 (five months), wheret
i
is the maturity of time-stepi, and the market pricec
i,j
of the call maturing at time-stepi
with strikeK
i,j
= 60 + 10jis equal to the Black-and-Scholes price with the corresponding
strike, maturityt
i
and volatilityσ= 0.2 for 1≤i≤2 and 1≤j≤7. We have checked
numerically that{0; ffl
0−1
(maxK)}is acceptable. Table 3 gives the optimal super-replicating
price and the amount of call positions in an optimal super-replicating portfolio. Table 4 gives
the discretization error and computing time as a function ofn.
5.2 Variance swaps
Consider a variance swap that pays at maturityTthe amount
ψ=
m
X
i=1
H(S
i−1
, S
i
),
whereHis a deterministic bivariate function. For instance,H(x, y) =T
−1
ln
2
(y/x) for standard
variance swaps,H(x, y) =T
−1
ln
2
(y/x)1
y2I
for a corridor variance swaps, whereIis a specified
interval ofR
+
, andH(x, y) = max(0, y/x−K) for a cliquet call, whereKis a constant. In
practice,mis quite large andl
i
= 0 for most values ofi. LetH
i
(x, y) =H(x, y)−b
T
i
f
i
(y), so
that
Ψ =
m
X
i=1
H
i
(S
i−1
, S
i
). (5.11)
Letπ
sup
(F) (resp.π
inf
(F)) denote the optimal super-replicating (resp. sub-replicating) price
of a standard variance swapψin the marketM
m
(F). For standard variance swaps,Fmust be
bounded away from 0 in order for the best super-replicating price to be finite. Consider now an
interval [L, M] that containsK, withL >0, and let
F
0
=K ∪ {L(M/L)
j/n
, j2 {0, . . . , n}}. (5.12)
Giveni2[0, m], consider the financial derivativeζ=
P
m
j=i+1
H
j
(S
j−1
, S
j
). Let Ψ
i
(resp.ζ
i
)
denote the super-hedging cost of Ψ (resp.ζ) at time-stepiinM
m
(F
0
). Sinceζdoes not depend
onS
0
, . . . , S
i−1
, Remark 4.2 shows thatζ
i
=c
i
(S
i
), wherec
i
is a deterministic function onF
0
,
16
Electronic copy available at: https://ssrn.com/abstract=2172315

withc
m
= 0. Since Ψ =ζ+
P
i
j=1
H
j
(S
j−1
, S
j
), Remark 4.1 shows that
Ψ
i
=c
i
(S
i
) +
i
X
j=1
H
j
(S
j−1
, S
j
), (5.13)
and so, by (4.6), for 0≤i≤m−1,
c
i
(S
i
) = sup
Q2Q(S
i
,F
0
)
E
Q
(c
i+1
+H
i+1
(S
i
, .)). (5.14)
We can interpret (5.14) by observing that the super-hedging cost ofζat time-stepi+ 1 is
c
i+1
(S
i+1
) +H
i+1
(S
i
, S
i+1
).
Theorem 5.3.Assume that{L, M}is acceptable. LetB=mT
−1
ln
2
(M/L). Thenπ
sup
(F
0
)
andπ
inf
(F
0
)can be calculated inO(N(l
3
+n
2
m+lmn))total time with precisionfflvia the
convex program(3.3), where
N=O(lln(
l(1 +S
0
)(1 +B)
fflffi
0
(L, M)
)),
andV
0
has a separation oracle that runs inO(n
2
m+lmn)time. Furthermore,
π
sup
([L, M])−π
sup
(F
0
) =O(
M
M−L
ln
3
(
M
L
)
m
T n
2
), (5.15)
and
π
inf
([L, M])−π
inf
(F
0
) =O((ln
2
(
M
L
) + ln
3
(
M
L
))
m
T n
2
). (5.16)
Proof.Since 0≤ψ≤B, max(c(ψ;M
m
(F
0
)), c(−ψ;M
m
(F
0
)))≤B. Thus, by Proposition 5.1,
Assumptions A1 and A2 hold inM
m
(F
0
) if
q=B+S
0

landδ=δ
0
(L, M)/2.
We extend the definition ofc
i
(x) to allx2[L, M] by settingc
m
= 0 and, for 0≤i≤m−1,
c
i
(x) = sup
Q2Q(x,F
0
)
E
Q
(c
i+1
+H
i+1
(x, .)). (5.17)
By Proposition 4.3, we can calculate by backward inductionc
i
(x) forx2F
0
, 0≤i≤m−1,
and probabilitiesQ(x, i) that maximise the RHS of (5.17) inO(n
2
m) total time. Using the
same notation forθandx
i
as in Assumption A4, letPbe a risk-neutral probability obtained
by pasting the probabilitiesP(θ) =Q(x
i
, i) in the marketM
m
(F
0
). By Proposition 4.2, the
super-hedging costc(Ψ) of Ψ in the marketM
m
(F
0
) equalsE
P
(Ψ). Given a call optionη
with maturityk≤mand payoffη
Λ
(S
k
), define the functionη
Λ
i
by backward induction onF
0
,
0≤i≤k, by settingη
Λ
k

Λ
and, for 0≤i≤k−1 andx2F
0
,
η
Λ
i
(x) =E
Q(x
,
i)

Λ
i+1
).
Using Proposition 4.2, it can be shown by backward induction thatη
Λ
0
(S
0
) =E
P
(η). Hence,
we can calculate inO(n
2
m+lmn) timec(Ψ) =c
0
(S
0
) andE
P
(φ). Thus A3 holds, with
T=O(n
2
m+lmn). The first part of the theorem then follows from Theorem 3.2 and (5.3).
Section H contains the remainder of the proof.
17
Electronic copy available at: https://ssrn.com/abstract=2172315

Table 5: Optimal super-replicating and sub-replicating prices of a variance swap maturing in
one month, withm= 20. The discretization error is estimated usingn= 3200.
n
p
π
inf
(F
0
) Computing time Error
p
π
sup
(F
0
) Computing time Error
50 19.33% 0.4 1 .6×10
−3
21.67% 0.4 4 .3×10
−4
100 19.05% 0.7 5 .2×10
−4
21.72% 0.7 2 .0×10
−4
200 18.93% 1.7 9 .3×10
−5
21.75% 1.8 5 .2×10
−5
400 18.92% 5.6 2 .6×10
−5
21.76% 5.6 1 .1×10
−5
800 18.91% 21 3 .5×10
−6
21.76% 21 2 .0×10
−6
Table 6: Optimal super-replicating and sub-replicating prices of a variance swap maturing in
one month, withm= 20, andn= 800. The computing time for each price ranged between 21
and 22 seconds.
σ 10% 15% 20% 25% 30% 35% 40%
p
π
sup
(F
0
) 12.43% 16.92% 21.76% 26.81% 32.01% 37.38% 42.94%
p
π
inf
(F
0
) 8.68% 13.90% 18.91% 23.77% 28.52% 33.19% 37.78%
In our numerical example, we setS
0
= $100, withL= $50 andM= $200. We first consider
a variance swap with maturityTof one month andm= 20 daily observations. We assume the
market pricec
m,j
of the call maturing atTwith strikeK
m,j
= 65 + 5jis equal to the Black-
and-Scholes price with the corresponding strike, maturityTand volatilityσfor 1≤j≤13 and
that no other call prices are known. Thusl
m
= 13 andl
i
= 0 for 1≤i < m. We have checked
numerically that{L, M}is acceptable. Table 5 gives the optimal super-replicating and sub-
replicating prices, the computing time and the discretization error in terms ofnwhenσ= 0.2.
Table 6 lists the optimal robust bounds and the computing time in terms of the volatility,
and table 7 gives the amount of call positions in optimal super-replicating and sub-replicating
portfolios whenσ= 0.2. Table 8 gives the optimal super-replicating and sub-replicating prices,
the computing time and the discretization error in terms ofnwhenσ= 0.2, the swap and the
calls mature in one year withm= 252 daily observations.
As noted before, for standard variance swaps, sinceψis not upper-bounded on (0, M], it
follows from (2.3) thatπ
sup
((0, M]) =∞for anyM >max(K). In other words, if there is no
positive lower bound on stock prices, the best super-replicating price of a standard variance swap
is infinite. On the other hand, Section I shows how to calculateπ
inf
((0, M]) using techniques
similar to those of Theorem 5.3, without assuming any positive lower bound on stock prices.
5.3 Volatility swaps
As is sometimes the case in market practice, we assume for simplicity that the volatility swap
payment is capped atν
max

T
−1
, whereν
max
is a constant, and so the swap pays at maturity
T
ψ=

T
−1
min(ν
max
,
v
u
u
t
m
X
i=1
ln
2
(
S
i
S
i−1
)).
Table 7: Optimal super-replicating (b
sup
) and sub-replicating (b
inf
) portfolios for a variance
swap whenσ= 0.2,m= 20, andn= 800.
Strike 70 75 80 85 90 95 100 105 110 115 120 125 130
b
sup
0.434 0.054 0.030 0.023 0.018 0.014 0.012 0.012 0.011 0.011 0.010 0.010 0.057
b
inf
-0.19 -0.012 0.015 0.014 0.013 0.012 0.012 0.010 0.008 0.006 0.004 0.003 0.001
18
Electronic copy available at: https://ssrn.com/abstract=2172315

Table 8: Super-replicating and sub-replicating prices of a variance swap maturing in one year,
withm= 252. The discretization error is estimated usingn= 3200.
n
p
π
inf
(F
0
) Computing time Error
p
π
sup
(F
0
) Computing time Error
50 18.30% 3.1 4 .9×10
−4
22.76% 3.4 4 .9×10
−4
100 18.24% 8.6 2 .6×10
−4
22.81% 8.1 2 .4×10
−4
200 18.20% 26 1 .1×10
−4
22.84% 25 1 .1×10
−4
400 18.18% 93 4 .5×10
−5
22.86% 87 4 .1×10
−5
800 18.17% 343 1 .2×10
−5
22.86% 327 1 .3×10
−5
In order to construct the subroutine needed in Assumption A3, we will discretize both the
stock price and the realized volatility. We show how to discretize the realized volatility at all
time-steps. Letn
0
be an integer,
Λ ={

max
n
0
: 0≤i≤n
0
},and
ρ(z) = max{x2Λ :x≤z},
forz≥0. Define the financial derivativeν
i
, 0≤i≤m, by induction by settingν
0
= 0 and
ν
i+1
=ρ(
r
ν
2
i
+ ln
2
(
S
i+1
S
i
)). (5.18)
Consider the financial derivativeψ
0

m
. Since the functionν7→

ν
2
+a
2
is 1-Lipschitz for
any constanta, it can be shown by induction that
0≤ψ

T−ψ
0


max
n
0
. (5.19)
Thus,ψ
0
is a discrete approximation ofψ

T. Let Ψ
0

0
−β
T
φ. Given integeri2[0, m], let
ζ=ψ
0

m
X
j=i+1
b
T
j
f
j
(S
j
). (5.20)
By (5.18),ψ
0
is a deterministic function ofν
i
and ofS
j
,j≥i. Let Ψ
0
i
(resp.ζ
i
) denote the
super-hedging cost of Ψ
0
(resp.ζ) at time-stepiin the marketM
m
(F
0
), whereF
0
is given
by (5.12). By Remark 4.2, it follows thatζ
i
=c
i

i
, S
i
), wherec
i
is a deterministic function
defined on Λ×F
0
. By (5.20),c
m

m
, S
m
) =ν
m
. Since Ψ
0
=ζ−
P
i
j=1
b
T
j
f
j
(S
j
), Remark 4.1
implies that
Ψ
0
i
=c
i

i
, S
i
)−
i
X
j=1
b
T
j
f
j
(S
j
).
Thus, by (4.6) and (5.18),
c
i

i
, S
i
) = sup
Q2Q(S
i
,F
0
)
E
Q
(h
i

i
, S
i
, .)), (5.21)
where, forz >0,
h
i
(ν, x, z) =c
i+1
(ρ(
q
ν
2
+ ln
2
(z/x)), z)−b
T
i+1
f
i+1
(z).
We can interpret (5.21) by observing that the super-hedging cost ofζat time-stepi+ 1 is
c
i+1

i+1
, S
i+1
)−b
T
i+1
f
i+1
(S
i+1
), which equalsh
i

i
, S
i
, S
i+1
).
19
Electronic copy available at: https://ssrn.com/abstract=2172315

Denote byπ
sup
([L, M]) the optimal super-replicating price ofψin the marketM
m
([L, M])
and byπ
sup
(n, n
0
) the optimal super-replicating price ofψ
0
in the marketM
m
(F
0
). Define simi-
larlyπ
inf
([L, M]) andπ
inf
(n, n
0
). Theorem 5.4 shows how to calculateπ
sup
(n, n
0
) andπ
inf
(n, n
0
)
and gives an upper bound on the discretization error. The constants behind theOnotation
in (5.22), (5.23) and Section J depend onl,S
0
, the calls strikes, maturities and prices,ν
max
,L
andM, but do not depend onn,n
0
,mandT.
Theorem 5.4.Assume that{L, M}is acceptable. Thenπ
sup
(n, n
0
)andπ
inf
(n, n
0
)can be
calculated inO(N(l
3
+nn
0
m(n+l)))total time with precisionfflvia the convex program(3.3),
where
N=O(lln(
l(1 +S
0
)(1 +ν
max
)
fflffi
0
(L, M)
)).
V
0
has a separation oracle that runs inO(nn
0
m(n+l))time. Furthermore,

sup
([L, M])−π
sup
(n, n
0
)

T
−1
| ≤
2mν
max

T n
0
+O(
m
2

T n
), (5.22)

inf
([L, M])−π
inf
(n, n
0
)

T
−1
| ≤
2mν
max

T n
0
+O(
m
2

T n
). (5.23)
Proof.Since 0≤ψ
0
≤ν
max
, max(c(ψ
0
), c(−ψ
0
))≤ν
max
. Thus, by Proposition 5.1, Assumptions
A1 and A2 hold for (ψ
0
, φ) in the marketM
m
(F
0
) if
q=ν
max
+S
0

landδ=δ
0
(L, M)/2. (5.24)
Extend the definition ofc
i
(ν, x) =c
i
(ν, x, β) toi2[0, m],ν2Λ andx2F
0
by setting
c
m
(ν, x) =νand
c
i
(ν, x) = sup
Q2Q(x,F
0
)
E
Q
(h
i
(ν, x, .)). (5.25)
By Proposition 4.3, we can calculate by backward inductionc
i
(ν, x) forν2Λ,x2F
0
and
0≤i≤m−1, and probabilitiesQ(ν, x, i) that maximise the RHS of (5.25) inO(n
2
n
0
m) total
time. Define the function withivariablesν
Λ
i
, 0≤i≤m, by induction by settingν
Λ
0
= 0 and
ν
Λ
i+1
(x
1
, . . . , x
i+1
) =ρ(
r
ν
Λ
i
2
(x
1
, . . . , x
i
) + ln
2
(
x
i+1
x
i
)).
Note thatν
i

Λ
i
(S
1
, . . . , S
i
). Using the same notation forθandx
i
as in Assumption A4, let
Pbe a risk-neutral probability obtained by pasting the probabilitiesP(θ) =Q(ν
Λ
i
(θ), x
i
, i). By
Proposition 4.2,E
P

0
) is equal to the super-hedging costc(Ψ
0
) of Ψ
0
in the marketM
m
(F
0
).
Given a call optionηwith maturityk≤mand payoffη
Λ
(S
k
), define the functionη
Λ
i
by backward
induction on Λ×F
0
, 0≤i≤k, by settingη
Λ
k
(ν, x) =η
Λ
(x) and, for 0≤i≤k−1,ν2Λ, and
x2F
0
,
η
Λ
i
(ν, x) =E
Q(ν,x
,
i)

Λ
k
(ν, x, .)),
whereη
Λ
k
(ν, x, z) =η
Λ
i+1
(ρ(
q
ν
2
+ ln
2
(z/x)), z). Using Proposition 4.2, it can be shown by
backward induction thatη
Λ
0
(0, S
0
) =E
P
(η). Hence, we can calculate inO(nn
0
m(n+l)) time
c(Ψ
0
) =c
0
(0, S
0
) andE
P
(φ), and so A3 holds for (ψ
0
, φ) in the marketM
m
(F
0
), withT=
O(nn
0
m(n+l)). The first part of the theorem then follows from Theorem 3.2 and (5.3). Section J
contains the proof of (5.22) and (5.23).
Our numerical experiments use the same setting as in Subsection 5.2 and cap the volatility
swap payoff atσ

2.5. Rather than rounding with respect toνin the calculation ofc
i
(ν, x),
we have used linear interpolation, as described in Section K, which performs much better in
practice. When calculating the best super-replicating price, we setn
0
=n. When calculating the
20
Electronic copy available at: https://ssrn.com/abstract=2172315

Table 9: Optimal super-replicating and sub-replicating prices of a capped volatility swap ma-
turing in one month. The discretization error is estimated usingn= 1600 andn
0
= 137 for the
sub–replicating price, andn=n
0
= 800 for the super-replicating price.
n n
0
π
inf
Computing time Error n n
0
π
sup
Computing time Error
50 14 8.03% 3.5 3 .7×10
−3
25 25 20.18% 2.5 1 .1×10
−2
100 22 7.77% 16 9 .9×10
−4
50 50 21.23% 13 6 .3×10
−5
200 34 7.70% 82 3 .2×10
−4
100 100 21.23% 67 6 .5×10
−6
400 54 7.67% 525 5 .2×10
−6
200 200 21.23% 466 4 .6×10
−6
Table 10: Optimal super-replicating and sub-replicating prices of a capped volatility swap
maturing in one month. The super-replicating prices were obtained withn=n
0
= 200. The
sub-replicating prices were obtained withn= 400 andn
0
= 54.
σ 10% 15% 20% 25% 30% 35% 40%
π
sup
12.24% 16.59% 21.23% 26.01% 30.88% 35.82% 40.85%
Running time 471 477 469 473 485 477 494
π
inf
3.74% 5.55% 7.67% 9.61% 11.56% 13.60% 15.49%
Running time 502 531 525 545 521 537 534
best sub-replicating price, we first calculate a discrete risk-neutral probability consistent with
the call prices at maturityT(see, e.g., (Davis and Hobson 2007)), then replaceF
0
by another
set of sizen
0
=n
2/3
where, on each intervalIdelimited by consecutive elements in{L, M} ∪ K,
the points are geometrically distributed and their number is proportional to the risk-neutral
probability thatS
m
belongs toI. This resulted in significantly improved performance in all
our numerical experiments. Tables 9 and 12 estimate the discretization error for maturities of
one month and one year, respectively. Table 10 lists the optimal super-replicating and sub-
replicating prices for the swap, and Table 11 gives the amount of call positions in optimal
super-replicating and sub-replicating portfolios whenσ= 0.2.
5.4 Discussion of results
A discretization error offflcan be achieved in Theorems 5.1, 5.2, 5.3, and 5.4 by using a cutting
plane algorithm withO(ffl
−1/2
),O(1),O(ffl
−1
), andO(ffl
−3
) running time per iteration, respec-
tively, and so a global error offflon the robust prices in the infinite space markets can be
achieved withO(ffl
−1/2
ln(ffl
−1
)),O(ln(ffl
−1
)),O(ffl
−1
ln(ffl
−1
)), andO(ffl
−3
ln(ffl
−1
)) total time. Our
numerical results confirm that the tradeoff between the discretization error and the running
time of the robust pricing algorithms for forward start options, variance and volatility swaps is
best for forward start options and worst for volatility swaps. Theorems 5.3 and 5.4 show that,
for fixedN,l,nand (for volatility swaps)n
0
, robust prices of variance and volatility swaps
are computed in time asymptotically proportional to the number of periodsm, as confirmed
numerically in Section L. On the other hand, Tables 10 and 12 suggest that the model risk
for volatility swaps is higher than that for variance swaps. This may be explained by the fact
that, under a continuity assumption on the stock price, the price of a continuously-monitored
variance swap can be exactly determined (Dupire 1993, Neuberger 1994) from the prices of a
continuum set of co-maturing call options, which is not the case for continuously-monitored
volatility swaps.
5.5 Other financial derivatives
Other financial derivatives such as lookback options, options on realized variance and realized
volatility, single or double barrier options and Asian options can be handled in a similar fashion.
21
Electronic copy available at: https://ssrn.com/abstract=2172315

Table 11: Optimal super-replicating (b
sup
) and sub-replicating (b
inf
) portfolios for a capped
volatility swap whenσ= 0.2, using the same grids and in Table 10.
Strike 70 75 80 85 90 95 100 105 110 115 120 125 130
b
sup
0.402 0.044 0.039 0.036 0.033 0.031 0.028 0.026 0.024 0.023 0.021 0.019 0.024
b
inf
-0.016 -0.001 0.000 -0.001 -0.027 -0.008 0.042 -0.008 -0.027 -0.001 0.000 0.000 0.000
Table 12: Optimal super-replicating and sub-replicating prices of a capped volatility swap
maturing in one year. The discretization error is estimated usingn= 800 andn
0
= 86 for the
sub–replicating price, andn=n
0
= 400 for the super-replicating price.
n n
0
π
inf
Computing time Error n n
0
π
sup
Computing time Error
50 14 8.04% 37 1 .2×10
−2
25 25 20.98% 29 7 .0×10
−4
100 22 7.63% 179 7 .5×10
−3
50 50 20.97% 146 5 .4×10
−4
200 34 7.30% 967 4 .2×10
−3
100 100 20.94% 903 2 .8×10
−4
400 54 7.06% 6463 1 .8×10
−3
200 200 20.92% 6147 4 .3×10
−5
Consider for instance an Asian callψthat pays
max(
S
1
+∙ ∙ ∙S
m
m
−K,0).
LetF
0
=K ∪ {jM/n: 0≤j≤n}, whereM > S
0
and integernare fixed. Using the same
techniques as before, we can show that the super-hedging cost of Ψ at time-stepiinM
m
(F
0
)
is
Ψ
i
=c
i

i
, S
i
)−
i
X
j=1
b
T
j
f
j
(S
j
),
whereν
i
= Σ
i−1
j=1
S
j
. The functionsc
i
can be calculated by backward induction forx2F
0
and
ν2[0, mM], by settingc
m
(ν, x) = max((ν+x)/m−K,0) and
c
i
(ν, x) = sup
Q2Q(x,F
0
)
E
Q
(c
i+1
(ν+x, .)−b
T
i+1
f
i+1
).
In practice, we need to discretize the values thatνcan take, in the same manner as we did for
volatility swaps. We can also derive optimal replicating prices and strategies for the financial
derivatives considered in this section in terms of prices of moments (or of the logarithmic
function) of the stock price at different maturities rather than in terms of call prices.
6 Extensions
6.1 Taking interest rates and dividends into account
Interest rates can be taken into account in the usual way by replacing each security by its
discounted value. We can also incorporate deterministic dividends as well as proportional
dividends in our model by replacing each security by the value of the security plus reinvested
dividends, using a technique similar to the one in (Pliska 2005, SubSec 3.2.3).
6.2 Taking bid-ask spreads into account
Assume that the financial derivativesφ
k
, 1≤k≤l, have distinct bid and ask prices, and letπ
b
(resp.π
a
) be the lengthlvector of bid (resp. ask) prices. Results in the preceding sections can
be easily extended to this case. We have for instance the following.
22
Electronic copy available at: https://ssrn.com/abstract=2172315

Theorem 6.1.If assumptions A1 and A3 hold and there is a risk-neutral probabilityPsuch
that
E
P
(φ)2[π
b
+δ1
l
, π
a
−δ1
l
] (6.1)
and−q≤E
P
(ψ), thenπ
sup
can be calculated via the convex program with2l+ 1variables
π
sup
= inf

a

b
,γ)2V
00
a
T
0

a
, β
b
, γ),
wherea
0
= (π
a
,−π
b
,1), and
V
00
={(β
a
, β
b
, γ)2R
+l
×R
+l
×R:a
T
0

a
, β
b
, γ)≤q+ 1,(β
a
−β
b
, γ)2V}.
Furthermore, for(β
a
, β
b
, γ)2V
00
,
||(β
a
, β
b
, γ)|| ≤
4(1 +q)

2l(1 +||(π
a
, π
b
)||)
δ
, (6.2)
V
00
contains a ball of radiusr=δ||a
0
||
−1
l
−1/2
/3centered at(r1
2l
, q+δ), and admits a separation
oracle that runs inT+O(1)time, whereTis the running time of the subroutine in Assumption
A3.
The vectorβ
a
(resp.β
b
) represents the amount of assets bought (resp. sold) in order to
super-replicateψ.
6.3 Limiting the jump sizes or the realized volatility
We can tighten the bounds on the price ofψby limiting the underlying dynamics. Limitations
to the up and/or down jumps can be achieved by limiting the setD(θ) in (4.5) to the securities
values that respect these limitations. For instance, if the log-returns are constrained to be at
most 3σ
p
T/min absolute value at any time-step,Qmust be supported on the set
{z2F
0
:|ln(
z
x
)| ≤3σ
r
T
m
}
in (5.25), and the best sub-replicating price for volatility swaps becomes 10.70% whenσ= 0.2.
We can upper-limit the realized volatility toσ

2.5 by setting the payoff at maturity to−∞if
the realized volatility exceedsσ

2.5 and keeping the remaining calculations unchanged, which
yields a best sub-replicating price of 13.09%. If both the log-returns and the realized volatility
are required to satisfy the previous constrains, the best sub-replicating price becomes 13.95%,
while the best super-replicating price remains essentially the same as in the un-constrained case.
These prices have been calculated using the same setting as in Table 10. The running times for
the three experiments were respectively 432, 614, and 463 seconds.
6.4 Portfolios of financial derivatives
Consider a portfolio of financial derivatives. Using (2.3), it can be shown that the optimal
super-replicating (resp. sub-replicating) portfolio price given other derivatives prices is at most
(resp. at least) the sum of the optimal super-replicating (resp. sub-replicating) prices of the
portfolio components. Using the same setting as in Table 8 withn= 800, Table 13 lists the
optimal super-replicating and sub-replicating prices for a standard variance swap, a variance
swap whereH(x, y) =T
−1
(y/x−1)
2
, and the average of the two swaps. The gap betweenπ
inf
andπ
sup
for the average variance swap turned out to be less than that for each component. In
general, our method allows the efficient calculation of optimal robust bounds on a portfolio of
derivatives of the type considered in Section 5, such as barrier options with different barrier
levels and strikes.
23
Electronic copy available at: https://ssrn.com/abstract=2172315

Table 13: Optimal super-replicating and sub-replicating prices for variance swaps based on Log-
returns, returns, and their average, withn= 800. The running times ranged from 327 to 369
seconds.
Log-returns Returns Average

π
sup
22.86% 26.53% 22.90%

π
inf
18.17% 16.98% 19.26%
7 Conclusion
We have shown that optimal super-replicating and sub-replicating prices and corresponding
hedging portfolios can be calculated efficiently for a wide variety of exotic financial derivatives
in terms of liquid financial derivatives in a discrete-time setting. The main novelty behind our
approach is the use of convex programs, which are solved via cutting planes generated by risk-
neutral probabilities. Super-hedging costs are calculated via recursive evaluations of concave
envelopes. We have implemented our method using an analytic center cutting plane algorithm
and an optimized convex hull algorithm. Numerical calculations of optimal super-replicating
and sub-replicating prices in terms of call options were given for forward start options, variance
and volatility swaps. In our examples, we have discretized the state-space and gave theoretical
and empirical bounds on the discretization errors. These prices are close to those obtained by a
standard model in some cases and differ considerably from them in other cases. Our method is
much more flexible than known explicit methods: it can incorporate interest rates and dividends,
bid-ask spreads, limitations to the jumps or to the realized volatility of the underlying assets,
and can be used to calculate efficiently optimal prices on portfolio of options of certain type.
It can be applied to multi-period financial derivatives on multiple assets but, in general, the
corresponding running time is exponential in the number of assets. This is because, in general,
the number of points needed to discretize the possible values of the assets vector is exponential
in the number of assets.
8 Acknowledgments
This paper has been presented at the 30th French Finance Association Conference, the Euro-
pean Financial Management Association 2013 Annual Meetings, and the Advances in Financial
Mathematics 2014 conference in Paris. The author thanks seminar participants, two anonymous
referees, an anonymous associate editor, and Gustavo Manso (department editor), for helpful
comments and suggestions. This work was achieved through the Laboratory of Excellence on
Financial Regulation (Labex ReFi) under the reference ANR-10-LABX-0095. It benefitted from
a French government support managed by the National Research Agency (ANR).
References
Albrecher, H., Mayer, P. A. and Schoutens, W. (2008). General lower bounds for arithmetic
Asian option prices,Applied Mathematical Finance15(2): 123 – 149.
Andrew, A. M. (1979). Another efficient algorithm for convex hulls in two dimensions,Inf.
Process. Lett.9(5): 216–219.
Atkinson, D. S. and Vaidya, P. M. (1995). A cutting plane algorithm for convex programming
that uses analytic centers,Mathematical Programming69(1-3): 1–43.
Beiglb¨ock, M., Henry-Labord`ere, P. and Penkner, F. (2013). Model-independent bounds for
option prices-a mass transport approach.,Finance and Stochastics17(3): 477 – 501.
24
Electronic copy available at: https://ssrn.com/abstract=2172315

Bertsimas, D. and Popescu, I. (2002). On the relation between option and stock prices: a convex
optimization approach,Operations Research50(2): 358–374.
Bertsimas, D. and Vempala, S. (2004). Solving convex programs by random walks,Journal of
the ACM (JACM)51(4): 540–556.
Bonnans, J. F. and Tan, X. (2011). A model-free no-arbitrage price bound for variance options,
Applied Mathematics & Optimizationpp. 1–31.
Boyd, S. and Vandenberghe, L. (2004).Convex optimization, Cambridge university press, UK.
Boyd, S., Vandenberghe, L. and Skaf, J. (2008). Analytic center cutting-plane method. Stanford
University, California, USA, Lecture notes, http://www. stanford. edu/class/ee364b.
Boyle, P. P. and Lin, X. S. (1997). Bounds on contingent claims based on several assets,Journal
of Financial Economics46(3): 383–400.
Britten-Jones, M. and A. Neuberger, A. (2000). Option prices, implied price processes, and
stochastic volatility,Journal of Finance55(2): 839–66.
Broadie, M. and Jain, A. (2008). The effect of jumps and discrete sampling on volatility and
variance swaps,Int. J. Theor. Appl. Finance11(8): 761–797.
Brown, H., Hobson, D. and Rogers, L. C. G. (2001a). The maximum maximum of a martingale
constrained by an intermediate law,Probab. Theory Related Fields119(4): 558–578.
Brown, H., Hobson, D. and Rogers, L. C. G. (2001b). Robust hedging of barrier options,Math.
Finance11(3): 285–314.
Carassus, L., Gobet, E. and Temam, E. (2007). A class of financial products and models where
super-replication prices are explicit,inJ. Akahori, S. Ogawa and S. Watanabe (eds),Proc.
Ritsumeikan Int. Symp. on Stoch. Proc. and Apps to Math. Fin., World Scientific, Kusatsu,
Japan, pp. 67–84.
Carr, P., Lee, R. and Wu, L. (2012). Variance swaps on time-changed Levy processes,Finance
and Stochastics16(2): 335–355.
Carr, P. P. and Wu, L. (2009). Variance Risk Premiums,The Review of Financial Studies,
22(3): 1311–1341.
Committee on Banking Supervision, B. (2009). Revisions to the Basel II market risk framework,
Technical report, Bank for International Settlements.
Cox, A. M. and Ob l´oj, J. (2011a). Robust hedging of double touch barrier options,SIAM
Journal on Financial Mathematics2(1): 141–182.
Cox, A. M. and Ob l´oj, J. (2011b). Robust pricing and hedging of double no-touch options,
Finance and Stochastics15(3): 573–605.
Cox, A. M. and Wang, J. (2013). Roots barrier: construction, optimality and applications to
variance options,The Annals of Applied Probability23(3): 859–894.
d’Aspremont, A. and El Ghaoui, L. (2006). Static arbitrage bounds on basket option prices,
Math. Program.106(3, Ser. A): 467–489.
Davis, M. H. A. and Hobson, D. G. (2007). The range of traded option prices,Math. Finance
17(1): 1–14.
25
Electronic copy available at: https://ssrn.com/abstract=2172315

Davis, M., Obloj, J. and Raval, V. (2014). Arbitrage bounds for prices of weighted variance
swaps,Math. Finance24(4): 821–854.
Demeterfi, K., Derman, E., Kamal, M. and Zou, J. (1999). A guide to volatility and variance
swaps,Journal of Derivatives6(4): 9–32.
Dupire, B. (1993). Model art,Risk6: 118–120.
Follmer, H. and Schied, A. (2004).Stochastic finance; An Introduction in Discrete Time, 2nd
Edition, Walter de Gruyter, Berlin.
Galichon, A., Henry-Labordere, P. and Touzi, N. (2014). A stochastic control approach to no-
arbitrage bounds given marginals, with an application to Lookback options.,The Annals
of Applied Probability24(1): 312–336.
Gotoh, J.-y. and Konno, H. (2002). Bounding option prices by semidefinite programming: A
cutting plane algorithm,Management Science48(5): 665–678.
Gr¨otschel, M., Lov´asz, L. and Schrijver, A. (1981). The ellipsoid method and its consequences
in combinatorial optimization,Combinatorica1(2): 169–197.
Henry-Labord`ere, P. (2013). Automated option pricing: Numerical methods,International
Journal of Theoretical and Applied Finance16(8).
Henry-Labordere, P., Obloj, J., Spoida, P. and Touzi, N. (2013). Maximum maximum of
martingales given marginals. Available at SSRN 2031461.
Henry-Labordere, P. and Touzi, N. (2013). An explicit martingale version of Brenier’s theorem.
Available at SSRN: http://ssrn.com/abstract=2218488.
Hobson, D. G. (1998). Robust hedging of the lookback option,Finance and Stochastics
2(4): 329–347.
Hobson, D. G. and Pedersen, J. L. (2002). The minimum maximum of a continuous martingale
with given initial and terminal laws,Ann. Probab.30(2): 978–999.
Hobson, D. and Klimmek, M. (2012). Model-independent hedging strategies for variance swaps,
Finance and Stochastics16: 611–649.
Hobson, D. and Klimmek, M. (2015). Robust price bounds for the forward starting straddle,
Finance and Stochastics19(1): 189–214.
Hobson, D., Laurence, P. and Wang, T.-H. (2005a). Static-arbitrage optimal subreplicating
strategies for basket options,Insurance Math. Econom.37(3): 553–572.
Hobson, D., Laurence, P. and Wang, T.-H. (2005b). Static-arbitrage upper bounds for the prices
of basket options,Quant. Finance5(4): 329–342.
Hobson, D. and Neuberger, A. (2012). Robust bounds for forward start options,Math. Finance
22(1): 31–56.
Hull, J. (2012).Options, Futures and Other Derivatives, eigth edn, Pearson Education Limited,
England.
Kahal´e, N. (2010). Sparse calibrations of contingent claims,Math. Finance20(1): 105–115.
Kahal´e, N. (2014). Model-independent lower bound on variance swaps.
http://dx.doi.org/10.1111/mafi.12083. To appear in Mathematical Finance.
26
Electronic copy available at: https://ssrn.com/abstract=2172315

Laurence, P. and Wang, T.-H. (2005). Sharp upper and lower bounds for basket options,Applied
Mathematical Finance12(3): 253–282.
Laurence, P. and Wang, T.-H. (2008). Distribution-free upper bounds for spread options and
market-implied antimonotonicity gap,The European Journal of Finance14(8): 717 – 734.
Laurence, P. and Wang, T.-H. (2009). Sharp distribution free lower bounds for spread options
and the corresponding optimal subreplicating portfolios,Insurance: Mathematics and Eco-
nomics44(1): 35–47.
Neuberger, A. J. (1994). The log contract,Journal of Portfolio Management20(2): 74–80.
Pliska, S. (2005).Introduction to Mathematical Finance, Blackwell, Malden, MA.
Simon, S., Goovaerts, M. and Dhaene, J. (2000). An easy computable upper bound for the price
of an arithmetic Asian option,Insurance: Mathematics and Economics26(2): 175–183.
Tan, X. and Touzi, N. (2013). Optimal transportation under controlled stochastic dynamics,
Ann. Probab.41(5): 3201–3240.
Vaidya, P. M. (1996). A new algorithm for minimizing convex functions over convex sets,
Mathematical programming73(3): 291–341.
A Proof of Lemma 3.1
By Assumption A2 and (3.2),V` E, and soV
0
` E
0
. For (β, γ)2 E
0
and 1≤i≤l, it follows
from (3.4) that−q≤β
T
π+γ±δβ
i
. Thus, by (3.5),−q≤q+ 1±δβ
i
, and so|β
i
| ≤R
0
. Hence
||β|| ≤R
0

l. On the other hand, (3.4) implies that−q≤β
T
π+γwhich, together with (3.5),
shows that
|γ| ≤q+ 1 +|β
T
π|.
By the Cauchy-Schwartz inequality, it follows that
|γ| ≤q+ 1 +R
0
||π||

l.
Since||(β, γ)|| ≤ ||β||+|γ|andq+ 1≤R
0
, we conclude that||(β, γ)|| ≤R
1
.
Consider now a vector (β, γ)2R
l
×Rthat belongs to the ball of radiusr=δ(1 +||π||)
−1
centered at (0
l
, q+δ). Since||(β, q+δ−γ)|| ≤r≤δ,||β|| ≤δandq≤γ. Thus, by Assumption
A1 and (2.4), (β, γ)2V. On the other hand, since
a
T
0
(β, γ) =a
T
0
(β, γ−q−δ) +q+δ,
wherea
0
= (π,1), it follows from the Cauchy-Schwartz inequality thata
T
0
(β, γ)≤r||a
0
||+q+δ.
Since||a
0
|| ≤1 +||π||, we conclude thata
T
0
(β, γ)≤q+ 1. Hence (β, γ)2V
0
.
B Proof of Lemma 3.2
For shorthand, denote a vector (β, γ)2R
l
×Rbyx. Let
K={x2R
l+1
:a
0
i
≤a
T
i
xfori2I
0
}, (B.1)
K
0
={x2K:a
T
0
x≤q+ 1}. (B.2)
By (3.9) and (3.10) and linear program duality,
b
0
= inf
x2K
a
T
0
x. (B.3)
27
Electronic copy available at: https://ssrn.com/abstract=2172315

Note that the last 2lconstraints in the RHS of (B.1) are the same as those in (3.4). Thus,
K={x2 E:a
0
i
≤a
T
i
xfori2I},
K
0
={x2 E
0
:a
0
i
≤a
T
i
xfori2I}.
ButE
0
θ R
0
sinceB(0, R
1
)θ R
0
and, by Lemma 3.1,E
0
θB(0, R
1
). As
˜
C={x2 R
0
:a
0
i
≤a
T
i
xfori2I},
we conclude thatK
0
=E
0

˜
C. SinceV
0
θ E
0
by Lemma 3.1 andV
0
θ
˜
C, it follows that
V
0
θK
0
and soK
0
is non-empty. Thus, by (B.2) and (B.3),b
0
= inf
x2K
0
a
T
0
x.SinceK
0
θ
˜
C,
this concludes the proof.
C Proof of Proposition 4.1
By Assumption A4,x
i
is a convex combination of elements ofD(θ), and soQ(x
i
, D(θ)) is
non-empty. (4.6) follows immediately from (4.1). By (2.1), for anyffl ¿0, there is a gains
functiong=
P
m
j=1
ξ
T
j
(X
j
−X
j−1
) such that Ψ is upper-bounded byc(Ψ) +ffl+g. Note that,
forj2[1, m], there is a deterministic functionξ
Λ
j
onD
j−1
such thatξ
j

Λ
j
(X
1
, . . . , X
j−1
). We
show by backward induction that
Ψ
i
≤c(Ψ) +ffl+
i
X
j=1
ξ
T
j
(X
j
−X
j−1
). (C.1)
(C.1) clearly holds wheni=m. If it holds fori+ 1 then, forθ= (x
1
, . . . , x
i
)2D
i
and
x2D(θ),
Ψ
Λ
i+1
(θ, x)≤c(Ψ) +ffl+ξ
Λ
i+1
T
(x−x
i
) +
i
X
j=1
ξ
Λ
j
T
(x
j
−x
j−1
), (C.2)
where we denoteξ
Λ
j
(x
1
, . . . , x
j−1
) byξ
Λ
j
for shorthand. Since the RHS of (C.2) is a linear function
ofx, it upper bounds
Ψ
Λ
i+1
(θ, .)(x) forx2
[
D(θ). Hence Ψ
Λ
i
(θ) is well defined,
Ψ
Λ
i
(θ)≤c(Ψ) +ffl+
i
X
j=1
ξ
Λ
j
T
(x
j
−x
j−1
),
and (C.1) holds fori. Thus Ψ
0
≤c(Ψ).
Conversely, for 0≤i≤m−1, by the definition of Ψ
Λ
i
and (4.4), there is a financial derivative
ξ
i+1
which is a function ofX
0
, . . . , X
i
such that
Ψ
i+1
≤ξ
T
i+1
(X
i+1
−X
i
) + Ψ
i
.
Hence there is a gains functiongsuch that Ψ≤g+Ψ
0
. Thusc(Ψ)≤Ψ
0
, and so Ψ
0
=c(Ψ).
D Proof of Proposition 4.2
For (x
1
, . . . , x
m
)2D
m
, choose a stateω2Ω such thatX
j
(ω) =x
j
for 1≤j≤m, and set
P({ω}) = Π
m
i=1
P
(x
1
,...,x
i−1
)
({x
i
}).
28
Electronic copy available at: https://ssrn.com/abstract=2172315

The reader can verify thatPis a probability, and thatE
P
(η) =η
Λ
0
(;) ifη
Λ
is the indicator
function of a pathθ2D
m
. By linearity of expectations, if follows thatE
P
(η) =η
Λ
0
(;) for
any functionη
Λ
. Letη=
P
m
j=1
ξ
T
j
(X
j
−X
j−1
) be a gains function. Using backward induction
and (4.7), it can be shown that, for 0≤i≤m,
η
Λ
i
(X
1
, . . . , X
i
) =
i
X
j=1
ξ
T
j
(X
j
−X
j−1
).
ThusE
P
(η) = 0 andPis risk-neutral.
Assume now thatP(θ) attains the RHS of (4.6). It can be shown by backward induction that
Ψ
Λ
i
=
ˉ
Ψ
i
, where Ψ
Λ
i
is defined as in Proposition 4.1 and
ˉ
Ψ
i
is the sequence obtained by replacing
η
Λ
with Ψ
Λ
in (4.7), and so Ψ
0
=E
P
(ψ).
E Proof of Proposition 5.1
Assume thatδandqsatisfy the conditions in Proposition 5.1. For any given integersi
0
2[1, m]
andj
0
2[1, l
i
], ifc
i
0
,j
0
is replaced withc
i
0
,j
0
±δand the other call prices remain unchanged,
then (5.2) still holds. On the other hand, it follows from the proof of (Davis and Hobson 2007,
Theorem 4.2) that, if (5.2) holds, there is a risk-neutral probabilityPsupported onK∪{k
Λ
, k
Λ
}
such thatE
P
(max(0, S
i
−K
i,j
)) =c
i,j
for 1≤i≤mand 1≤j≤l
i
. Using Remark 3.1,
we conclude that A2 holds. Furthermore,c(Ψ)≤c(ψ) +||β||
1
S
0
,sincecis sub-additive and
since the super-hedging cost of a call is at mostS
0
. Since, by the Cauchy-Schwartz inequality,
||β||
1


l||β||,
c(Ψ)≤c(ψ) +

l||β||S
0
, (E.1)
and so Assumption A1 holds as well. On the other hand, it follows from (5.2) that, sincec
i,0
andc
i,l
i
+1
are upper-bounded byS
0
, so isc
i,j
. Hence (5.3).
F Remainder of the proof of Theorem 5.1
LetM
0
be a market with sample space Ω
0
. We say that a marketMis a sub-market ofM
0
if it is obtained by restricting the basic securities ofM
0
to a non-empty subset Ω of Ω
0
. To
simplify the notation, ifηis a derivative inM
0
, the restriction ofηto Ω is also denoted by
η. To upper-bound the discretization errors in Theorems 5.1, 5.2, 5.3, and 5.4, we will use the
following result, whereM(resp.M
0
) is a market with finite (resp. infinite) state-space, and
prove (F.1) by extending a hedging scheme fromMtoM
0
. The proofs of Theorems 5.1, 5.2,
5.3, and 5.4 thus allow us to construct hedging strategies inM
0
which are optimal, up toffland
the discretization error.
Proposition F.1.Letψbe a derivative inM
0
,φa vector of derivatives inM
0
, andMa
sub-market ofM
0
. Assume that Assumptions A1, A2 and A3 hold for(ψ, φ)in the marketM,
and
c(ψ−β
T
φ;M
0
)≤c(ψ−β
T
φ;M) +α, (F.1)
for||β||

≤R
0
and some constantα. Then
π
sup
(ψ, φ;M)≤π
sup
(ψ, φ;M
0
)≤π
sup
(ψ, φ;M) +α. (F.2)
Proof.For a derivativeηinM
0
and a constantγ, ifη≤
g
γinM
0
, thenη≤
g
γinM. Hence,
V
0
(ψ, φ;M
0
)θV
0
(ψ, φ;M). By (2.3), the first inequality in (F.2) follows. We now show the
29
Electronic copy available at: https://ssrn.com/abstract=2172315

second one. By Theorem 3.2, forffl ¿0, there is (β
Λ
, γ
Λ
)2V(ψ, φ;M) with||β
Λ
||

≤R
0
such
that
β
ΛT
π+γ
Λ
≤π
sup
(ψ, φ;M) +ffl:
By (2.4),c(ψ−β
ΛT
φ;M)≤γ
Λ
, and soc(ψ−β
ΛT
φ;M
0
)≤γ
Λ
+α. Thus, (β
Λ
, γ
Λ
+α)2
V(ψ, φ;M
0
). Since
β
ΛT
π+γ
Λ
+α≤π
sup
(ψ, φ;M) +α+ffl;
we infer, by applying (2.5) in the marketM
0
, thatπ
sup
(ψ, φ;M
0
)≤π
sup
(ψ, φ;M) +α+ffl.
Lettingfflgo to 0 concludes the proof.
For any finite subsetFofR, letF
Λ
=F∪[max(F),∞). Denote byg
|F
0
the restriction ofg
to a subsetF
0
ofR. By convention, max(;) =−∞.
Proposition F.2.LetFbe a finite subset ofR
+
containing{0}, andga function onR
+
which
is convex on any closed interval delimited by consecutive points inF. Then
g(x) =g
|F
Λ
(x), for
x≥0.
Proof.The proposition follows by observing that a concave function upper-boundsgonR
+
if
and only if it upper-boundsgonF
Λ
.
Proposition F.3.Letw≥0and(g
j
),j2J, a finite family of continuous functions on
an interval[y, z]such that, forj2J,g
00
j
exists on(y, z)and is lower-bounded by−w. Let
f=max
j2J
(g
j
). Iff(x)≤g(x)forx2 {y, z}, wheregis a linear function, thenf(x)≤
g(x) +w(z−y)
2
/8forx2[y, z].
Proof.The proposition follows by observing that the functionx7→g
j
(x) +w(x−y)(x−z)/2 is
convex and is upper-bounded bygon{y, z}. Thus it is thus upper-bounded bygon [y, z], and
sog
j
is upper-bounded byg+w(z−y)
2
/8 on [y, z].
Lemma F.1.LetFbe a finite subset ofR
+
with|F|>1, andga function on[min(F),∞)
which is convex on[max(F),∞)and such thatg(u) =λu+λ
0
foru≥x
0
, for some constants
x
0
≥max(F),λandλ
0
. Then, forx≥min(F),
g
|F
(x) = max
u,u
0
2F,u≤x≤u
0
,u6=u
0
(u
0
−x)g(u) + (x−u)g(u
0
)
u
0
−u
, (F.3)
with the convention that
g
|F
(x) =−∞ifx >max(F). Furthermore,
g
|F
Λ
(x) = max(
g
|F
(x),max
u2F,u≤x
g(u) +λ(x−u)), (F.4)
and there is a real numberξ
Λ
such that, fory2F
Λ
,
g(y)≤
g
|F
Λ
(x) +ξ
Λ
(y−x). (F.5)
Ifmin(F)≤x≤x
0
andx
0
= max(F), then
0≤
g
|F
Λ
(x)−
g
|F
(x)≤
x
x
0
max
u2F,u<x
(|λu+λ
0
−g(u)|). (F.6)
Proof.By Proposition 4.3, we can assume the probabilitiesQin (4.1) to be supported on two
distinct pointsuandu
0
whend= 1, withu≤x≤u
0
, which gives (F.3). On the other hand,
sincegis convex on [max(F),∞), for max(F)< y < u
0
,
g(y)−g(max(F))
y−max(F)

g(y)−g(u
0
)
y−u
0
.
30
Electronic copy available at: https://ssrn.com/abstract=2172315

Lettingu
0
go to infinity shows that, fory≥max(F),
g(y)≤g(max(F)) +λ(y−max(F)). (F.7)
Similarly, foru, u
0
2F
Λ
,u≤x≤u
0
, u6=u
0
,
g
|F
Λ
(x)≥
(u
0
−x)g(u) + (x−u)g(u
0
)
u
0
−u
.
Lettingu
0
go to infinity implies that
g
|F
Λ
(x)≥g(u) +λ(x−u). HenceA(x)≤
g
|F
Λ
(x), where
A(x) is the RHS of (F.4).
Assume nowx2[min(F),max(F)]. By Proposition 4.3, there is a real numberζsuch that,
fory2F,
g(y)≤
g
|F
(x) +ζ(y−x).
Letξ
Λ
= max(λ, ζ) andy2F. Since
g
|F
(x)≤A(x), ify≥xor ifξ
Λ
=ζ,
g(y)≤A(x) +ξ
Λ
(y−x). (F.8)
Also, it follows from the definition ofA(x) that (F.8) holds ify < xandξ
Λ
=λ. Thus, (F.8)
holds for anyy2F.
Similarly, ifx≥max(F), letξ
Λ
=λ. It follows from the definition ofA(x) that (F.8) holds
fory2F. We conclude that, forx≥min(F), there isξ
Λ
≥λsuch that (F.8) holds fory2F.
In particular,
g(max(F))≤A(x) +ξ
Λ
(max(F)−x),
which, by (F.7), implies that (F.8) holds fory2F
Λ
. Hence
g
|F
Λ
(x)≤A(x). This implies
that (F.4) and (F.5) hold.
We now prove (F.6). By (F.3) and (F.4),
g
|F
Λ
(x) = max(
g
|F
(x),max
u2F,u<x
g(u) +λ(x−u)).
On the other hand, foru2Fwithu < x≤x
0
,
g(u) +λ(x−u) =
(x
0
−x)g(u) + (x−u)g(x
0
)
x
0
−u
+
x−u
x
0
−u
(g(u)−λu−λ
0
)

g
|F
(x) +
x
x
0
max
u
0
2F,u
0
<x
(|λu+λ
0
−g(u)|).
This concludes the proof.
We now prove the remainder of the theorem. SetK
2,0
= 0,M
0
= max(K), andM
i
=
max(F
i
) for 1≤i≤2. Assume thatβ= (b
1
, b
2
) is such that||β||

≤R
0
. By (5.9),R
0
=O(1).
Since|max(x−K
i,j
,0)−x| ≤M
0
forx≥0, 1≤i≤2 and 1≤j≤l
i
,
|b
T
i
f
i
(x)−(b
T
i
1
l
i
)x| ≤R
0
M
0
l,
and so, forx
1
≥0,x
2
≥0,
Ψ
Λ
(x
1
, x
2
) = max(0, x
2
−x
1
)−b
T
2
1
l
2
x
2
−b
T
1
1
l
1
x
1
+O(1). (F.9)
It follows from (5.4) that, forx
1
2F
1
,
Ψ
Λ
1
(x
1
;F
2
) =
Ψ
Λ
(x
1
, .)
|F
2
(x
1
). (F.10)
Similarly, forx
1
≥0, Ψ
Λ
1
(x
1
) =
Ψ
Λ
(x
1
, .)(x
1
). Sinceg= Ψ
Λ
(x
1
, .) is convex on each interval
[K
2,j
, K
2,j+1
], 0≤j≤l
2
−1, it follows by applying Proposition F.2 withF=F
2
that
Ψ
Λ
1
(x
1
) =
Ψ
Λ
(x
1
, .)
|F
Λ
2
(x
1
). (F.11)
31
Electronic copy available at: https://ssrn.com/abstract=2172315

Sincegis convex on [M
2
,∞), it satisfies the conditions of Lemma F.1 withF=F
2
,x
0
=
max(M
2
, x
1
). Furthermore, by (F.9),λ=O(1),λ
0
=O(1 +x
1
) and Ψ
Λ
(x
1
, u) =O(1 +x
1
) for
u≤M
0
. Hence, by (F.6), (F.10) and (F.11), forx
1
2F
1
and some constantκ=O(1),
0≤Ψ
Λ
1
(x
1
)−Ψ
Λ
1
(x
1
;F
2
)≤κx
1
ffl
0
. (F.12)
Also, by (F.5) and (F.11), forx
1
≥0, there is a real numberξ
Λ
x
1
such that, forx
2
2F
Λ
2
,
Ψ
Λ
(x
1
, x
2
)≤Ψ
Λ
1
(x
1
) +ξ
Λ
x
1
(x
2
−x
1
). (F.13)
Sincegis convex on any interval delimited by consecutive points ofF
2
, (F.13) holds forx
2
≥0.
On the other hand, the functiongsatisfies the conditions of Lemma F.1 withF={0} ∪ K,
x
0
= max(M
0
, x
1
), andλ= 1−b
T
2
1
l
2
. LetK
0
j
, 0≤j≤l
0
, denote the elements ofFin increasing
order, withK
0
l
0
+1
=∞. (F.3), (F.4) and (F.11) imply that, forx
1
2[K
0
j
, K
0
j+1
), 0≤j≤l
0
,
Ψ
Λ
1
(x
1
) = max( max
0≤j
0
≤j<j
00
≤l
2
f
j
0
,j
00
(x
1
),max
0≤j
0
≤j
Ψ
Λ
(x
1
, K
0
j
0
) + (1−b
T
2
1
l
2
)(x
1
−K
0
j
0
)),(F.14)
where
f
j
0
,j
00
(x
1
) =
(K
0
j
00
−x
1

Λ
(x
1
, K
0
j
0
) + (x
1
−K
0
j
0

Λ
(x
1
, K
0
j
00
)
K
0
j
00
−K
0
j
0
. (F.15)
It follows that Ψ
Λ
1
(x
1
) =O(1) forx
1
2[0, M
0
], since, by (F.9), Ψ
Λ
(x
1
, K
0
j
0
) =O(1) for 0≤j
0
≤l
0
.
Furthermore, since Ψ
Λ
(x
1
, K
0
j
0
) and Ψ
Λ
(x
1
, K
0
j
00
) are linear functions ofx
1
withO(1) slope on
(K
0
j
, K
0
j+1
),
f
00
j
0
,j
00
(x
1
) =O(1), (F.16)
forx
1
2(K
0
j
, K
0
j+1
). Moreover, by (F.9), Ψ
Λ
(., K
0
j
0
) is linear with slope−b
T
1
1
l
1
on [M
0
,∞) and
so, by (F.14), the function Ψ
Λ
1
is also linear on [M
0
,∞) and satisfies the conditions of Lemma F.1
withF=F
1
,x
0
=M
1
andλ= 1−b
T
1
1
l
1
−b
T
2
1
l
2
. Note thatλandλ
0
= Ψ
Λ
1
(M
0
)−λM
0
are
O(1). Hence, by (F.6),
Ψ
Λ
1|F
Λ
1
(S
0
) =
Ψ
Λ
1|F
1
(S
0
) +O(ffl
0
), (F.17)
and there is a real numberξ
Λ
0
such that, forx
1
2F
Λ
1
,
Ψ
Λ
1
(x
1
)≤
Ψ
Λ
1|F
Λ
1
(S
0
) +ξ
Λ
0
(x
1
−S
0
). (F.18)
Consider now a probabilityQ 2Q(S
0
, F
1
). By (F.12),
E
Q

Λ
1
) =E
Q

Λ
1
(.;F
2
)) +O(ffl
0
).
Hence, by (4.1) and (5.5) and taking the supremum overQ 2Q(S
0
, F
1
), it follows that
Ψ
Λ
1|F
1
(S
0
) =c(Ψ;M(F
1
, F
2
)) +O(ffl
0
),
and so, by (F.17),
Ψ
Λ
1|F
Λ
1
(S
0
) =c(Ψ;M(F
1
, F
2
)) +O(ffl
0
). (F.19)
Since (F.18) holds forx
1
2 {M
0
, M
1
}and Ψ
Λ
1
is linear on [M
0
, M
1
], (F.18) holds forx
1
2
[M
0
, M
1
], and so it holds forx
1
2F
1
∪[M
0
,∞). Using (F.14), (F.16) and Proposition (F.3), we
conclude that, forx
1
≥0,
Ψ
Λ
1
(x
1
)≤
Ψ
Λ
1|F
Λ
1
(S
0
) +ξ
Λ
0
(x
1
−S
0
) +O(n
−2
).
Using (F.13) and (F.19), we infer that, forx
1
≥0 andx
2
≥0,
Ψ
Λ
(x
1
, x
2
)≤c(Ψ;M(F
1
, F
2
)) +ξ
Λ
0
(x
1
−S
0
) +ξ
Λ
x
1
(x
2
−x
1
) +O(n
−2
+ffl
0
).
Thus,c(Ψ;M
2
(R
+
))≤c(Ψ;M(F
1
, F
2
)) +O(n
−2
+ffl
0
) which, by Proposition F.1, implies (5.8).
32
Electronic copy available at: https://ssrn.com/abstract=2172315

G Remainder of the proof of Theorem 5.2
Since Ψ
Λ
(x
1
, x
2
) is a convex function ofx
2
on any interval of positive real numbers disjoint
withKand not containingx
1
, it can be shown using arguments similar to those in the proof of
Theorem 5.1 that, forx
1
2[K
0
j
, K
0
j+1
), 0≤j≤l
0
,
Ψ
Λ
1
(x
1
) = max(Ψ
Λ
(x
1
, x
1
),max
0≤j
0
≤j<j
00
≤l
2
f
j
0
,j
00
(x
1
),max
0≤j
0
≤j
Ψ
Λ
(x
1
, K
0
j
0
)−(1 +b
T
2
1
l
2
)(x
1
−K
0
j
0
)),
wheref
j
0
,j
00
is given by (F.15). Hence, on each intervalIdelimited by two consecutive points in
{0} ∪ K, the function Ψ
Λ
1
is convex, sincef
j
0
,j
00
is convex onI, and Ψ
Λ
1
is linear on [maxK,∞).
Thus, by Proposition F.2 and Lemma F.1, we can calculatec(Ψ;M
2
(R
+
)) in terms of the slope
of Ψ
Λ
1
on [max(K),∞) and the values of Ψ
Λ
1
on{0} ∪ K. We can then show (5.10) by arguments
similar to those in the proof of Theorem 5.1.
H Remainder of the proof of Theorem 5.3
The following lemma shows that, under smoothness conditions onH,π
sup
([L, M]) is well ap-
proximated byπ
sup
(F
0
).
Lemma H.1.Assume thatHis continuous on[L, M]
2
and there are functionsaandbon
(L, M), andw≥0, such that the following conditions hold. The functionais non-positive.
Forx2[L, M], the functiony7→H(x, y)has a second derivative lower-bounded byb(y)for
y2(L, M). Ifyandzare two elements ofF
0
andy < x < z, the second derivative of
(z−x)H(x, y) + (x−y)H(x, z)with respect toxis lower bounded by(z−y)a(x). Furthermore,
(a(x) +b(x))(z−y)
2
≥ −w, ifyandzare consecutive elements ofF
0
. Then
π
sup
(F
0
)≤π
sup
([L, M])≤π
sup
(F
0
) +m
w
8
.
Proof.Leti2[1, m−1] andx2[y, z], whereyandzare consecutive elements ofF
0
. By
Proposition 4.3, we can assume the probabilityQin (5.17) to be supported by two pointsy
0
andz
0
, and so
c
i
(x) = max
y
0
,z
0
2F
0
,y
0
≤y≤z≤z
0
g
i,y
0
,z
0
(x), (H.1)
where
g
i,y
0
,z
0
(x) =
z
0
−x
z
0
−y
0
(c
i+1
(y
0
) +H
i+1
(x, y
0
)) +
x−y
0
z
0
−y
0
(c
i+1
(z
0
) +H
i+1
(x, z
0
)). (H.2)
Note that (H.1) also holds ifi=mandg
m,y
0
,z
0
is the null function. Thus, for 1≤i≤mand
x
0
2[L, M],
c
i
(x) +H
i
(x
0
, x) = max
y
0
,z
0
2F
0
,y
0
≤y≤z≤z
0
f
i,x
0
,y
0
,z
0
(x),
where
f
i,x
0
,y
0
,z
0
(x) =g
i,y
0
,z
0
(x) +H
i
(x
0
, x).
On the other hand, by (4.8) and (5.17), there is a real numberξ
Λ
i,x
0
be such that, forx2F
0
,
c
i
(x) +H
i
(x
0
, x)≤c
i−1
(x
0
) +ξ
Λ
i,x
0
(x−x
0
).
Furthermore, by (H.2),g
i,y
0
,z
0
is continuous on [y, z] andg
00
i,y
0
,z
0
(x)≥a(x) forx2(y, z). Hence
f
i,x
0
,y
0
,z
0
is continuous on [y, z] andf
00
i,x
0
,y
0
,z
0
(x)≥a(x) +b(x) forx2(y, z). Sincef
00
i,x
0
,y
0
,z
0

−w/(z−y)
2
on (y, z), by Proposition F.3, we conclude that, forx2[y, z],
c
i
(x) +H
i
(x
0
, x)≤c
i−1
(x
0
) +ξ
Λ
i,x
0
(x−x
0
) +
w
8
. (H.3)
33
Electronic copy available at: https://ssrn.com/abstract=2172315

Thus, in the marketM
[L,M]
,
c
i
(S
i
) +H
i
(S
i−1
, S
i
)≤c
i−1
(S
i−1
) +ξ
i
(S
i
−S
i−1
) +
w
8
, (H.4)
whereξ
i
is the financial derivativeξ
i

Λ
i,S
i−1
. By (5.11) and summing (H.4) fori2[1, m], we
infer that
Ψ≤c
0
(S
0
) +
m
X
i=1
ξ
i
(S
i
−S
i−1
) +m
w
8
.
On the other hand, by applying (5.13) withi= 0, it follows that
c
0
(S
0
) =c(Ψ;M
m
(F
0
)). (H.5)
Thus,
c(Ψ;M
m
([L, M]))≤c(Ψ;M
m
(F
0
)) +m
w
8
.
We conclude the proof using Proposition F.1.
We now prove (5.15) and (5.16). LetH(x, y) =T
−1
ln
2
(y/x). Then

2
H
∂y
2
(x, y) = 2T
−1
1 + ln(x/y)
y
2
, (H.6)
and the second derivative of ((z−x)H(x, y) + (x−y)H(x, z))/(z−y) with respect toxis
2
x
2
T
−1
(1−
(z+x) ln(x/y) + (x+y) ln(z/x)
(z−y)
).
By noting thatx+y≤x+z≤2zify < x < z, and that the functionzln(z/y)/(z−y)
is increasing with respect tozand decreasing with respect toyfor 0< y < z, a standard
calculation shows that the conditions of Lemma H.1 hold with
a(x) =−
4
x
2
T
−1
Mln(M/L)
M−L
,
b(y) =−
2
y
2
T
−1
ln(M/L),and
w= 6T
−1
Mln(M/L)
M−L
((M/L)
1/n
−1)
2
.
Hence (5.15). Similarly, (5.16) follows by noting that, whenH(x, y) =−T
−1
ln
2
(y/x), the
conditions of Lemma H.1 hold with
a(x) =−
2
x
2
T
−1
, (H.7)
b(y) =−
2
y
2
T
−1
(1 + ln(M/L)),and (H.8)
w= 2T
−1
(2 + ln(M/L))((M/L)
1/n
−1)
2
.
34
Electronic copy available at: https://ssrn.com/abstract=2172315

I Calculation ofπ
inf
((0,M])for Variance Swaps
We first show the following propositions.
Proposition I.1.Assume that{0, M}is acceptable. Then, for anyL2[0, δ
0
(0, M)/2],{L, M}
is acceptable, andδ
0
(L, M)≥δ
0
(0, M)/2.
Proof.Using the same notation as in Definition 5.1, withk
Λ
= 0 andk
Λ
=M, for 1≤i≤m
and 1≤j≤l
i
, by lettingi
0
=i
00
=i,j
0
= 0 andj
00
=l
i
+ 1, (5.2) becomes
max(0, S
0
−K
i,j
)< c
i,j
< wS
0
,
and so
δ
0
(0, M)≤S
0
−c
i,j
≤K
i,j
. (I.1)
On the other hand, for 0< k
Λ
< δ
0
(0, M) andk
Λ
=M, it follows by inspection thatk
Λ
appears
in (5.2) only whenj
0
= 0, and an easy calculation shows that, whenj
0
= 0,
∂(wc
i
0
,j
0
+ (1−w)c
i
00
,j
00
)
∂k
Λ
=
w
K
i
00
,j
00
−k
Λ
(S
0
−k
Λ
−c
i
00
,j
00
)−w
≥ −1.
The second equation follows from (I.1). Thus, forL2[0, δ
0
(0, M)/2], if the value ofk
Λ
changes
from 0 toL,wc
i
0
,j
0
+ (1−w)c
i
00
,j
00
diminishes by at mostL. Hence, (5.2) stills holds ifk
Λ
=L
andk
Λ
=M, andδ
0
(L, M)≥δ
0
(0, M)−L. This concludes the proof.
Proposition I.2.LetFbe a subset ofR
+
,x
0
an element ofF, andF
0
a finite subset ofFthat
containsF∩[x
0
,∞). Letgbe a function onFandλa real number such that, for anyz2F,
g(z)≤g(x
0
) +λ(z−x
0
). (I.2)
Then, for any elementxofF∩(x
0
,∞),
g
|F
0
(x) =
g
|F∩[x
0
,∞)
(x), and there is a real numberξ
Λ
such that, forz2F,
g(z)≤
g
|F∩[x
0
,∞)
(x) +ξ
Λ
(z−x). (I.3)
Proof.Proof.Letxbe any element ofF∩(x
0
,∞). By Proposition 4.3, there is a real number
ξ
Λ
such that (I.3) holds forz2F∩[x
0
,∞). In particular,
g(x
0
)≤
g
|F∩[x
0
,∞)
(x) +ξ
Λ
(x
0
−x). (I.4)
On the other hand, (I.2) implies that
g
|F∩[x
0
,∞)
(x)≤g(x
0
) +λ(x−x
0
), and so, by (I.4),
ξ
Λ
≤λ. Thus, by (I.2),g(z)≤g(x
0
) +ξ
Λ
(z−x
0
) forz2F∩(−∞, x
0
] which, together
with (I.4), implies that (I.3) holds forz2F∩(−∞, x
0
]. Hence, (I.3) holds for anyz2F,
and so
g
|F
0
(x)≤
g
|F∩[x
0
,∞)
(x). But, since any concave function that upper-boundsgonF
0
also
upper-boundsgonF∩[x
0
,∞), we conclude that
g
|F
0
(x) =
g
|F∩[x
0
,∞)
(x).qed We now show how
to calculateπ
inf
((0, M]). Givenn >0, set
F
0
=K ∪ {
j
n
M, j2 {1, . . . , n}}.
The constants behind theOnotation in (I.5) and in the proof of Theorem I.1 depend onl,S
0
,
the calls strikes, maturities and prices,M,m, andT, but do not depend onn. The intuition
behind the proof of Theorem I.1 is that the realized variance of any path containing very low
stock prices is high. Thusπ
inf
((0, M]) can be calculated by excluding such paths and applying
the same techniques as in the proof of Theorem 5.3.
35
Electronic copy available at: https://ssrn.com/abstract=2172315

Theorem I.1.Assume that{0, M}is acceptable. LetB=mT
−1
ln
2
(4M/δ
0
(0, M)). Then, for
n≥4M/δ
0
(0, M),π
inf
(F
0
)can be calculated inO(N(l
3
+n
2
m+lmn))total time with precision
fflvia the convex program(3.3), where
N=O(lln(
l(1 +S
0
)(1 +B)
fflffi
0
(0, M)
)),
andV
0
has a separation oracle that runs inO(n
2
m+lmn)time. Furthermore,
π
inf
((0, M])−π
inf
(F
0
) =O(n
−2
). (I.5)
Proof.LetH(x, y) =−T
−1
ln
2
(y/x). Sinceψ≤0, it follows from (E.1) that Assumption A1
holds in the marketM
m
(F
0
), with
q=B+S
0

landδ=δ
0
(0, M)/4.
Since the spacing between two consecutive elements ofF
0
is at mostδ
0
(0, M)/4, there is a
real numberk
Λ
2F
0
∩[δ
0
(0, M)/4, δ
0
(0, M)/2]. By Proposition I.1,{k
Λ
, M}is acceptable
andδ
0
(k
Λ
, M)≥δ
0
(0, M)/2. On the other hand, as 0≤ |ψ| ≤Bin the marketM
m
(F
0


0
(0, M)/4, M]), by Proposition 5.1, Assumption A2 hold in this market. Since any risk-neutral
probability in a sub-market ofM
m
(F
0
) is also a risk-neutral probability inM
m
(F
0
), we conclude
that A2 holds in the marketM
m
(F
0
) as well. Finally, an argument similar to that in the proof
of Theorem 5.3 shows that A3 holds in the marketM
m
(F
0
), withT=O(n
2
m+lmn). This
shows the first part of the theorem.
We now show (I.5). LetL
i
= min(K)e
−(m−i)

lR
0
M
for 1≤i≤m, and letL
0
be the largest
element ofF
0
∩[0,min(K)e
−m

lR
0
M
], which is non-empty ifnis sufficiently large. Assume that
β= (b
1
, . . . , b
m
) is such that||β||

≤R
0
. Define ˜c
i
(x) forx2(0, M] by setting ˜c
m
= 0 and,
for 0≤i≤m−1, ˜c
i
(x) = 0 ifx2(0, L
0
], and, forx2(L
0
, M],
˜c
i
(x) = sup
Q2Q(x,F
0
)
E
Q
(˜c
i+1
+H
i+1
(x, .)). (I.6)
(I.6) is obtained from (5.17) by replacingc
i
,c
i+1
, andF
0
with ˜c
i
, ˜c
i+1
, andF
0
respectively. For
y >0 and 1≤i≤m, every component off
i
(y) is at mosty, and sob
T
i
f
i
(y)≥ −l
i
R
0
y. Hence
H
i
(x, y)≤l
i
R
0
y, and so it follows by backward induction that, forx2(0, M] and 1≤i≤m,
˜c
i
(x)≤(
P
m
j=i+1
l
j
)R
0
x. Thus, forx2(0, M],
˜c
i
(x)−b
T
i
f
i
(x)≤lR
0
x. (I.7)
We show by backward induction that, for 1≤i≤m,x2(0, L
i−1
] andz2(0, M],
˜c
i
(z) +H
i
(x, z)≤0. (I.8)
Assume first thati=m, and letx2(0, L
m−1
]. Then (I.8) holds ifz≤L
m
sincef
m
is null
on (0, L
m
]. On the other hand, ifz2(L
m
, M], thenH(x, z)≤ −lR
0
M, and so, by (I.7), (I.8)
holds again in this case. Thus the induction hypothesis holds fori=m. Assume it holds for
i+ 1. By (I.6), it follows that ˜c
i
(x)≤0 forx2(0, L
i
]. Assume now thatx2(0, L
i−1
]. Since
H(x, z)≤ −lR
0
Mforz2[L
i
, M], (I.7) implies that (I.8) holds forz2[L
i
, M]. On the other
hand, (I.8) also holds forz2(0, L
i
] sincef
i
is null on (0, L
i
]. Thus the induction hypothesis
holds fori.
Letx2(0, L
0
]∩F
0
. It follows from (I.8) that the RHS of (I.6) is at most 0. But, by
considering the probabilityQsupported on{x}, it can be seen that the RHS of (I.6) is non-
negative, and is thus null. Hence (I.6) holds forx, and so it holds for anyx2F
0
. Thus, an
argument similar to the proof of (H.5) shows that ˜c
0
(S
0
) =c(Ψ;M
m
(F
0
)).
36
Electronic copy available at: https://ssrn.com/abstract=2172315

Set
L
0
=
L
0
e+ ln(M/L
0
) +lR
0
T L
0
,
and letLbe the largest element ofF
0
∩[0, L
0
], which is non-empty ifnis sufficiently large. Fix
x2(L
0
, M] andi2[0, m−1], and letg(z) = ˜c
i+1
(z)+H
i+1
(x, z). We show that, forz2(0, M],
g(z)≤g(L) + (z−L)g
0
(L). (I.9)
Note thatg(z) =H(x, z), forz2(0, L
0
], and so (I.9) holds in this case because, by (H.6),
H(x, .) is concave on (0, L
0
]. On the other hand, forL
0
< z≤M,
g(L) + (z−L)g
0
(L) =T
−1
(2(
z
L
−1)−ln(
x
L
)) ln(
x
L
).
But
2(
z
L
−1)−ln(
x
L
) = 2(
z
L
−1)−ln(
z
L
)−ln(
x
z
)

z
L
−1−ln(
M
L
0
)
≥lR
0
T z.
The second equation follows from the inequality ln(y)≤y−1, and the third equation holds for
z≥L
0
by standard calculations. Thus
g(L) + (z−L)g
0
(L)≥lR
0
z,
which, together with (I.7), implies (I.9). Thus (I.9) holds forz2(0, M].
Let
˜
F= (0, L]∪F
0
. By (I.9), and since
˜
F∩[L, M]θF
0
θ
˜
F, we can apply Proposition I.2
withF=
˜
F,x
0
=Landλ=g
0
(L). Hence, by (I.6),
˜c
i
(x) = sup
Q2Q(x,F
0
∩[L,M])
E
Q
(˜c
i+1
+H
i+1
(x, .)),
and there is a real numberξ
Λ
i,x
be such that, forz2
˜
F,
˜c
i+1
(z) +H
i+1
(x, z)≤˜c
i
(x) +ξ
Λ
i,x
(z−x).
Since ˜c
i+1
is null on [L, L
0
], arguments similar to those used in the proof of Theorem 5.3 (see
(H.3), (H.7) and (H.8)) show that, forz2(0, M],
˜c
i+1
(z) +H
i+1
(x, z)≤˜c
i
(x) +ξ
Λ
i,x
(z−x) +w, (I.10)
wherew≥0 andw=O(n
−2
).
On the other hand, by (I.8), (I.10) holds forx2(0, L
0
] if we setξ
Λ
i,x
= 0, and so it holds for
x2(0, M]. We infer that, in the marketM
m
((0, M]),
Ψ≤˜c
0
(S
0
) +
m
X
i=1
ξ
i
(S
i
−S
i−1
) +mw,
whereξ
i
is the financial derivativeξ
i

Λ
i,S
i−1
. Hence,
c(Ψ;M
m
(0, M])≤c(Ψ;M
m
(F
0
)) +mw.
We conclude the proof using Proposition F.1.
In practice,π
inf
(F
0
) can be calculated for any integernsuch that{M/n, M}is acceptable.
Numerical calculations ofπ
inf
(F
0
), using the same setting as in Table 5, are given in Table 14.
The prices in Table 14 are very close toπ
inf
(F
0
) in Table 5.
37
Electronic copy available at: https://ssrn.com/abstract=2172315

Table 14: Optimal sub-replicating prices of a variance swap maturing in one month in
M
m
((0, M]), withM= 200 andm= 20. The discretization error is estimated usingn= 3200.
n
p
π
inf
(F
0
) Computing time Error
50 19.85% 0.4 3 .7×10
−3
100 19.19% 0.7 1 .1×10
−3
200 19.01% 1.6 3 .7×10
−4
400 18.92% 5.1 3 .4×10
−5
800 18.91% 20 1 .1×10
−5
J Remainder of the proof of Theorem 5.4
We say that a real-valued functiongdefined on a set of real numbersWisκ-Lipschitz onWif
|g(x)−g(y)| ≤κ|x−y|forx, y2W.
Lemma J.1.Letgbe a real-valued bivariate function defined on[L, M]
2
such that, for some
constantsκ
x
andκ
y
, for anyx, y2[L, M], the functionsg(., y)andg(x, .)are respectivelyκ
x
-
Lipschitz andκ
y
-Lipschitz on[L, M]. LetWbe a finite subset of[L, M]that contains{L, M}
andwthe maximum distance between consecutive elements ofW. Forx2[L, M], set
h(x) = sup
Q2Q(x,W)
E
Q
(g(x, .)). (J.1)
Thenhis(κ
x

y
)-Lipschitz on[L, M]. Furthermore, for anyx2[L, M], there is a real number
ξ
Λ
such that, fory2[L, M],
g(x, y)≤h(x) +κ
y
w+ξ
Λ
(y−x). (J.2)
Proof.Fixy, y
0
2Wwithy < y
0
. Forx2[y, y
0
], let
F(x, y, y
0
) =
(y
0
−x)g(x, y) + (x−y)g(x, y
0
)
y
0
−y
.
Since, fory < x < x
0
< y
0
,
(y
0
−y)(F(x
0
, y, y
0
)−F(x, y, y
0
)) = (x−y)(g(x
0
, y
0
)−g(x, y
0
))+
(y
0
−x)(g(x
0
, y)−g(x, y)) + (x
0
−x)(g(x
0
, y
0
)−g(x
0
, y)),
it follows after some calculations that the functionx7→F(x, y, y
0
) is (κ
x

y
)-Lipschitz on
[y, y
0
].
Fix now two consecutive elementsy
0
andy
1
ofW. By Proposition 4.3, the probabilityQ
in (J.1) can be assumed to be supported on two pointsyandy
0
ofWand so, forx2[y
0
, y
1
],
h(x) = max
y,y
0
2W,y≤y
0
,y
1
≤y
0
F(x, y, y
0
).
Since the maximum of a finite set ofκ-Lipschitz functions on [y
0
, y
1
] isκ-Lipschitz on [y
0
, y
1
],
it follows thathis (κ
x

y
)-Lipschitz on [y
0
, y
1
]. Thus,his (κ
x

y
)-Lipschitz on any interval
delimited by consecutive elements ofW, and so it is (κ
x

y
)-Lipschitz on [L, M].
By Proposition 4.3 and (4.9), there is a real numberξ
Λ
such that|ξ
Λ
| ≤κ
y
and, forz2W,
g(x, z)≤h(x) +ξ
Λ
(z−x).
(J.2) follows since, for anyy2[L, M], there isz2Wwithin distancew/2 fromy.
38
Electronic copy available at: https://ssrn.com/abstract=2172315

Forν≥0, 0≤i≤m, andx, y2[L, M], letζ
ν
(x, y) =
q
ν
2
+ ln
2
(y/x). Define by backward
induction the functions ˜c
i
(ν, x) = ˜c
i
(ν, x, β), forν≥0,x2[L, M], and 0≤i≤mby setting
˜c
m
(ν, x) = min(ν, ν
max
) and, for 0≤i≤m−1,ν2Λ,
˜c
i
(ν, x) = sup
Q2Q(x,F
0
)
E
Q
(g
i+1,ν
(x, .)), (J.3)
where
g
i,ν
(x, y) = ˜c
i

ν
(x, y), y)−b
T
i
f
i
(y), (J.4)
and, forν2R
+
−Λ,
˜c
i
(ν, x) = (1−λ)˜c
i
(ρ(ν), x) +λ˜c
i+1
(ρ(ν+
ν
max
n
0
), x), (J.5)
whereλ= (ν−ρ(ν))/(ν
max
/n
0
). (J.3) can be thought as the limit of (5.25) asn
0
goes to infinity,
while (J.5) says that ˜c
i
(ν, x) is calculated by linear interpolation forν2[0, ν
max
]−Λ, and is
set to ˜c
i

max
, x) forν≥ν
max
. As the functionν7→

ν
2
+a
2
is 1-Lipschitz for any constanta,
and since the supremum and the weighted average of 1-Lipschitz functions is 1-Lipschitz, it can
be shown by backward induction that ˜c
i
(ν, x) is 1-Lipschitz and non-decreasing with respect to
νand, forν2Λ andx2F
0
,
c
i
(ν, x)≤˜c
i
(ν, x)≤c
i
(ν, x) +
(m−i)ν
max
n
0
. (J.6)
We now prove the following.
Lemma J.2.Forν≥0,x2[L, M],0≤i≤m, the functiong
i,ν
(x, .)isκ
i
-Lipschitz on[L, M],
where
κ
i
=
2(m−i) + 1
L
+ Σ
m
j=i
||b
j
||
1
.
Proof.We prove the lemma by backward induction. The induction hypothesis holds when
i=msince the derivative ofζ
ν
(x, y) with respect toyis at most 1/y, and any call function is
1-Lipschitz. Assume it holds fori+1. Since ˜c
i+1
(., y) is 1-Lipschitz and the derivative ofζ
ν
(x, y)
with respect toxis at most 1/x, fory2[L, M], the functiong
i+1,ν
(., y) is (L
−1
)-Lipschitz on
[L, M]. Also, by the induction hypothesis, the functiong
i+1,ν
(x, .) isκ
i+1
-Lipschitz on [L, M],
forx2[L, M]. By Lemma J.1 and (J.3), it follows that ˜c
i
(ν, .) is (L
−1

i+1
)-Lipschitz on
[L, M] ifν2Λ. By (J.5), the same conclusion holds for anyν≥0. On the other hand, by (J.4),
|g
i,ν
(x, y
0
)−g
i,ν
(x, y)| ≤ |˜c
i

ν
(x, y
0
), y
0
)−˜c
i

ν
(x, y), y
0
)|+|˜c
i

ν
(x, y), y
0
)−˜c
i

ν
(x, y), y)|+
|b
T
i
(f
i
(y)−f
i
(y
0
))|.(J.7)
The first term in the RHS of (J.7) is at mostL
−1
|y
0
−y|since ˜c
i
(., y
0
) is 1-Lipschitz andζ
ν
(x, .)
is (L
−1
)-Lipschitz. The second term is at most (L
−1

i+1
)|y
0
−y|since ˜c
i
(ν, .) is (L
−1

i+1
)-
Lipschitz. The last term is at most||b
i
||
1
|y
0
−y|since any call function is 1-Lipschitz. Hence
|g
i,ν
(x, y
0
)−g
i,ν
(x, y)| ≤κ
i
|y
0
−y|,
and the induction hypothesis holds fori.
Letw=L((M/L)
1/n
−1). It follows from Lemmas J.1, J.2 and (J.3) that, forx2[L, M],
0≤i≤m, andν2Λ, there is a real numberξ
Λ
i,ν,x
such that, fory2[L, M],
g
i+1,ν
(x, y)≤˜c
i
(ν, x) +κ
1
w+ξ
Λ
i,ν,x
(y−x).
Since ˜c
i+1
(., y) is non-decreasing, it follows that, in the marketM
0
=M
m
([L, M]),
˜c
i+1

i+1
, S
i+1
)−b
T
i+1
f
i+1
(S
i+1
)≤˜c
i

i
, S
i
) +κ
1
w+ξ
Λ
i,ν
i
,S
i
(S
i+1
−S
i
). (J.8)
39
Electronic copy available at: https://ssrn.com/abstract=2172315

Define the financial derivativeξ
i+1

Λ
i,ν
i
,S
i
. By summing up (J.8) fori2[0, m−1], we get
Ψ
0
≤˜c
0
(0, S
0
) +mκ
1
w+
m−1
X
i=0
ξ
i+1
(S
i+1
−S
i
).
Thus,
c(Ψ
0
;M
0
)≤˜c
0
(0, S
0
) +mκ
1
w.
Assume now thatβ= (b
1
, . . . , b
m
) is such that||β||

≤R
0
, and letκ= 2L
−1
+lR
0
, so that
κ
1
≤mκ. By (J.6) and, sincec
0
(0, S
0
) =c(Ψ
0
;M), whereM=M
m
(F
0
), it follows that
c(Ψ
0
;M
0
)≤c(Ψ
0
;M) +

max
n
0
+m
2
κw.
Hence, by Proposition F.1,

sup

0
, φ;M
0
)−π
sup

0
, φ;M)| ≤

max
n
0
+m
2
κw.
On the other hand, by (5.19),

sup
(ψ, φ;M
0
)

T−π
sup

0
, φ;M
0
)| ≤

max
n
0
.
Thus,

sup
(ψ, φ;M
0
)

T−π
sup

0
, φ;M)| ≤2

max
n
0
+m
2
κw.
Since, by (5.24),R
0
=O(1), this implies (5.22). We can show (5.23) in a similar manner.
K Robust pricing of Volatility swaps via linear interpolation
Even though ˜c
0
(0, S
0
) = ˜c
0
(0, S
0
, β) does not appear to have a simple financial interpretation,
we can use it rather thanc
0
(0, S
0
) =c(ψ
0
−β
T
φ;M) in order to calculate the super-replicating
price of a volatility swap. This yields the following algorithm. By analogy to (2.4), let
˜
V
0
={(β, γ)2R
l
×R: ˜c
0
(0, S
0
, β)≤γ, β
T
π+γ≤q+ 1},
whereqis given by (5.24), and
˜π
sup
(n, n
0
) = inf
(β,γ)2
˜
V
0
β
T
π+γ.
We use a cutting plane algorithm to minimizeβ
T
π+γover
˜
V
0
. We construct a separation oracle
for
˜
V
0
by analogy to that ofV
0
in Proposition 3.1, as described below. Using Proposition 4.3, we
calculate by backward induction ˜c
i
(ν, x) forν2Λ,x2F
0
and 0≤i≤m−1, and probabilities
˜
Q(ν, x, i) that maximise the RHS of (J.3). Given a call optionηwith maturityk≤mand
payoff ˜η(S
k
), define the function ˜η
i
by backward induction onR
+
×F
0
, 0≤i≤k, by setting
˜η
k
(ν, x) = ˜η(x) and, for 0≤i≤k−1,ν2Λ, andx2F
0
,
η
Λ
i
(ν, x) =E
˜
Q(ν,x
,
i)

Λ
i+1
(
q
ν
2
+ ln
2
(z/x), z)),
and, forν2R
+
−Λ,
η
Λ
i
(ν, x) = (1−λ)η
Λ
i
(ρ(ν), x) +λη
Λ
i
(ρ(ν+ν
max
/n
0
), x),
whereλ= (ν−ρ(ν))/(ν
max
/n
0
). We construct a separation oracle for
˜
V
0
by replacingc(ψ−β
T
φ)
with ˜c
0
(0, S
0
) andE
P
(φ) with the vector (η
Λ
0
(0, S
0
)), whereηranges over the components ofφ,
in the algorithm described in Proposition 3.1.
40
Electronic copy available at: https://ssrn.com/abstract=2172315

Table 15: Computing times for robust prices of a variance swap withn= 400 in terms of the
number of periodsm. The time-length of each period is 1/252. The discretization error is
estimated usingn= 3200.
m
p
π
inf
(F
0
) Computing time Error
p
π
sup
(F
0
) Computing time Error
21 18.91% 6 2 .5×10
−5
21.76% 6 1 .2×10
−5
42 19.01% 12 2 .4×10
−5
21.37% 12 1 .8×10
−5
84 18.87% 24 3 .1×10
−5
21.50% 24 2 .9×10
−5
168 18.51% 48 4 .0×10
−5
22.26% 46 3 .8×10
−5
Table 16: Computing times for robust prices of a capped volatility swap in terms of the number
of periodsm, withn= 100 andn
0
= 22 for the sub–replicating price, andn=n
0
= 50 for
the super-replicating price. The time-length of each period is 1/252. The discretization error
is estimated usingn= 800 andn
0
= 86 for the sub–replicating price, andn=n
0
= 400 for the
super-replicating price.
m π
inf
Computing time Error π
sup
Computing time Error
21 7.74% 17 1 .0×10
−3
21.23% 12 6 .3×10
−5
42 7.60% 32 3 .8×10
−3
20.68% 25 2 .7×10
−4
84 7.68% 61 6 .0×10
−3
20.48% 50 3 .6×10
−4
168 7.70% 127 7 .3×10
−3
20.73% 99 4 .5×10
−4
L Computing times for variance and volatility swaps in terms
of the number of periods
This section uses the same settings as in Subsections 5.2 and 5.3. Tables 15 and 16 list the
optimal super-replicating and sub-replicating prices for variance and volatility swaps, for fixed
l,nand (for volatility swaps)n
0
, with maturities ranging from 1 to 8 months. These prices
are computed in time proportional to the number of traded daysm, which is consistent with
Theorems 5.3 and 5.4.
M Proof of Theorem 6.1
Let (β
a
, β
b
, γ)2V
00
. By the assumptions of the theorem, there is a risk-neutral probabilityP
that satisfies (6.1) and such that
−q≤E
P
(ψ)
≤(β
a
−β
b
)
T
E
P
(φ) +γ
≤(β
a
)
T

a
−δ1
l
)−(β
b
)
T

b
+δ1
l
) +γ
= (β
a
, β
b
)
T
((π
a
,−π
b
)−δ1
2l
) +γ,
where the second inequality follows from (2.6). Hence, for 1≤i≤2l,
−q≤(β
a
, β
b
)
T
((π
a
,−π
b
)±δe
i
) +γ,
and soV
00
` E
0
(2l,(π
a
,−π
b
), q, δ). Thus (6.2) follows by arguments similar to those in the proof
of Lemma 3.1.
Consider now a vector (β
a
, β
b
, γ)2R
2l
×Rthat belongs to the ball of radiusrcentered at
u= (r1
2l
, q+δ). Since||β
a
−r1
l
|| ≤r,β
a
2R
+l
. Similarly,||β
b
−r1
l
|| ≤randβ
b
2R
+l
. By the
triangular inequality,||β
a
−β
b
|| ≤2r≤δ. Furthermore,q≤γsince|q+δ−γ| ≤r≤δ. Thus,
by Assumption A1 and (2.4), (β
a
−β
b
, γ)2V. On the other hand, since (β
a
, β
b
, γ−q−δ) =

a
, β
b
, γ)−u+r(1
2l
,0),||(β
a
, β
b
, γ−q−δ)|| ≤r+r

2l. As
a
T
0

a
, β
b
, γ) =a
T
0

a
, β
b
, γ−q−δ) +q+δ,
41
Electronic copy available at: https://ssrn.com/abstract=2172315

it follows from the Cauchy-Schwartz inequality thata
T
0

a
, β
b
, γ)≤3r

l||a
0
||+q+δ. Thus
a
T
0

a
, β
b
, γ)≤q+ 1, and so (β, γ)2V
00
. The rest of the proof is similar to that of Proposi-
tion 3.1.
42
Electronic copy available at: https://ssrn.com/abstract=2172315
Tags