This paper focuses on an extension of the Limit Order Book (LOB) model with general shape introduced by Alfonsi, Fruth and Schied [AFS10]. Here, the additional feature allows a timevarying LOB depth. We solve the optimal execution problem in this framework for both discrete and continuous time strategies. This gives in particular sufficient conditions to exclude Price Manipulations in the sense of Huberman and Stanzl [HS04] or Transaction-Triggered Price Manipulations (see Alfonsi, Schied and Slynko [ASS11]). These conditions give interesting qualitative insights on how market makers may create or not price manipulations.

Méthodes et modèles numériques appliqués aux risques du marché et à l'évaluation financière

Ce travail de thèse aborde deux sujets : (i) L'utilisation d'une nouvelle méthode numérique pour l'évaluation des options sur un panier d'actifs, (ii) Le risque de liquidité, la modélisation du carnet d'ordres et la microstructure de marché.

Premier thème : Un algorithme glouton et ses applications pour résoudre des équations aux dérivées partielles

Beaucoup de problèmes d'intérêt dans différents domaines (sciences des matériaux, finance, etc) font intervenir des équations aux dérivées partielles (EDP) en grande dimension. L'exemple typique en finance est l'évaluation d'une option sur un panier d'actifs, laquelle peut être obtenue en résolvant l'EDP de Black-Scholes ayant comme dimension le nombre d'actifs considérés. Nous proposons d'étudier un algorithme qui a été proposé et étudié récemment dans [START_REF] Ammar | A new family of solvers for some classes of multidimensional partial differential equations encountered in kinetic theory modeling of complex fluids[END_REF][START_REF] Bris | Results and questions on a nonlinear approximation approach for solving high-dimensional partial differential equations[END_REF] pour résoudre des problèmes en grande dimension et essayer de contourner la malédiction de la dimension. L'idée est de représenter la solution comme une somme de produits tensoriels et de calculer itérativement les termes de cette somme en utilisant un algorithme glouton. La résolution des EDP en grande dimension est fortement liée à la représentation des fonctions en grande dimension. Dans le Chapitre 1, nous décrivons différentes approches pour représenter des fonctions en grande dimension et nous introduisons les problèmes en grande dimension en finance qui sont traités dans ce travail de thèse.

La méthode sélectionnée dans ce manuscrit est une méthode d'approximation non-linéaire appelée Proper Generalized Decomposition (PGD). Le Chapitre 2 montre l'application de cette méthode pour l'approximation de la solution d'une EDP linéaire (le problème de Poisson) et pour l'approximation d'une fonction de carré intégrable par une somme des produits tensoriels. Un étude numérique de ce dernier problème est présenté dans le Chapitre 3. Le problème de Poisson et celui de l'approximation d'une fonction de carré intégrable serviront de base dans le Chapitre 4 pour résoudre l'équation de Black-Scholes en utilisant l'approche PGD. Dans des exemples numériques, nous avons obtenu des résultats jusqu'en dimension 10.

Outre l'approximation de la solution de l'équation de Black-Scholes, nous proposons une méthode de réduction de variance des méthodes Monte Carlo classiques pour évaluer des options financières.

Numerical methods and models in market risk and financial valuations area

This work is organized in two themes : (i) A novel numerical method to price options on many assets, (ii) The liquidity risk, the limit order book modeling and the market microstructure.

First theme : Greedy algorithms and applications for solving partial differential equations in high dimension

Many problems of interest for various applications (material sciences, finance, etc) involve highdimensional partial differential equations (PDEs). The typical example in finance is the pricing of a basket option, which can be obtained by solving the Black-Scholes PDE with dimension the number of underlying assets. We propose to investigate an algorithm which has been recently proposed and analyzed in [START_REF] Ammar | A new family of solvers for some classes of multidimensional partial differential equations encountered in kinetic theory modeling of complex fluids[END_REF][START_REF] Bris | Results and questions on a nonlinear approximation approach for solving high-dimensional partial differential equations[END_REF] to solve such problems and try to circumvent the curse of dimensionality.

The idea is to represent the solution as a sum of tensor products and to compute iteratively the terms of this sum using a greedy algorithm. The resolution of high dimensional partial differential equations is highly related to the representation of high dimensional functions. In Chapter 1, we describe various linear approaches existing in literature to represent high dimensional functions and we introduce the high dimensional problems in finance that we will address in this work.

The method studied in this manuscript is a non-linear approximation method called the Proper Generalized Decomposition. Chapter 2 shows the application of this method to approximate the solution of a linear PDE (the Poisson problem) and also to approximate a square integrable function by a sum of tensor products. A numerical study of this last problem is presented in Chapter 3. The Poisson problem and the approximation of a square integrable function will serve as basis in Chapter 4

for solving the Black-Scholes equation using the PGD approach. In numerical experiments, we obtain results for up to 10 underlyings.

Besides the approximation of the solution to the Black-Scholes equation, we propose a variance reduction method, which permits an important reduction of the variance of the Monte Carlo method for option pricing.

Second theme : Liquidity risk, limit order book modeling and market microstructure Liquidity risk and market microstructure have become in the past years an important topic in mathematical finance. One possible reason is the deregulation of markets and the competition between them to try to attract as many investors as possible. Thus, quotation rules are changing and, in general, more information is available. In particular, it is possible to know at each time the awaiting orders on some stocks and to have a record of all the past transactions. In this work we study how to use this information to optimally execute buy or sell orders, which is linked to the traders' behaviour that want to minimize their trading cost.

The structure of Limit Order Books (LOB) is very complex. Orders can only be made on a price grid. At each time, the number of waiting buy (or sell) orders for each price is stored. For a given price, orders are executed according to the First In First Out rule, as soon as two orders match together.

Thus, since it is really complex, an exhaustive modeling of the LOB dynamics would not lead, for example, to draw conclusions on an optimal trading strategy. One has therefore to propose models that can grasp important features of the LOB structure but that allow to find analytical results.

In [START_REF] Alfonsi | Optimal execution strategies in limit order books with general shape functions[END_REF], Alfonsi, Fruth and Schied have proposed a simple LOB model. In this model, it is possible to explicitly derive the optimal strategy for buying (or selling) a given amount of shares before a given deadline. Basically, one has to split the large buy (or sell) order into smaller ones in order to find the best trade-off between attracting new orders and the price of the orders.

Here, we focus on an extension of the Limit Order Book (LOB) model with general shape introduced by Alfonsi, Fruth and Schied. The additional feature is a time-varying LOB depth that represents a new feature of the LOB highlighted in [JJ88, GM92, HH95, KW96]. We solve the optimal execution problem in this framework for both discrete and continuous time strategies. This gives in particular sufficient conditions to exclude Price Manipulations in the sense of Huberman and

Stanzl [START_REF] Huberman | Price manipulation and quasi-arbitrage[END_REF] or Transaction-Triggered Price Manipulations (see Alfonsi, Schied and Slynko). These conditions give interesting qualitative insights on how market makers may create price manipulations.

Part I

Greedy algorithms and application for solving high-dimensional partial differential equations 1 Approximation of high-dimensional functions and the pricing problem

The approximation of high-dimensional functions is an important subject because of the large domain of applications.

The main difficulty for approximating high-dimensional functions is that when the dimension increases, the quantity of information increases exponentially fast with the dimension. This obstacle is known as the curse of dimensionality.

In Section 1.2, we present different approaches proposed in the literature for representing highdimensional functions. In particular, in Section 1.2, we discuss the linear techniques, the non-linear methods being defined in Chapter 2. We draw your attention on the fact that the non-linear techniques will be the methods used in this manuscript.

Before introducing these linear methods to approximate high-dimensional functions, let us discuss the curse of dimensionality in order to understand the difficulties behind the study of highdimensional problems.

The curse of dimensionality

Let us introduce the Hilbert space V. The main idea of the deterministic approaches is to represent solutions u ∈ V as linear combinations of tensor products. The approximation by a full tensor products writes:

u(x 1 , x 2 . . . , x d ) = N 1 � i 1 =1 N 2 � i 2 =1
. . .

N d � i d =1 u i 1 i 2 ...i d φ i 1 (x 1 )φ i 2 (x 2 ) . . . φ i d (x d ) (1.1)
where u i 1 i 2 ...i d ∈ R for all i j = 0, . . . N j , j = 1, . . . , d and

� φ i j � 1≤i j ≤N j
are the basis of the vector spaces of dimension N j for all j = 1, . . . , d which are fixed. As a consequence, this approach leads to considering a number of degrees of freedom

N N = d � j=1 N j (1.2)
that grows exponentially in terms of the dimension d.

The following result given by DeVore, Howard and Micchelli [START_REF] Devore | Optimal nonlinear approximation[END_REF] allows to see in practice the curse of dimensionality because it shows that a sampling method cannot do better than a certain error estimate depending exponentially on the dimension.

This result is based on the non-linear manifold width. Let X be a normed space and K ⊂ X a compact set. Let us consider the maps E : K � → R N for the encoding and R : R N � → X for the reconstruction. Introducing the distortion of the pair (E, R) over K

max u∈K �u -R(E(u))� X ,
we define the non-linear N -width of K as

d N (K) := inf E,R max u∈K �u -R(E(u))� X
where the infimum is taken over all the continuous maps (E, R). If X = L ∞ and K is the unit ball of C m ([0, 1] d ), it can be proven that (see [START_REF] Devore | Optimal nonlinear approximation[END_REF])

cN -m d ≤ d N (K) ≤ CN -m d
where c and C are two constant that do not depend on N . For a fixed error level, the number of degrees of freedom grows exponentially fast with the dimension. In conclusion, for high-dimensional problems, appropriate approximation tools should be studied.

In this direction, we present in the following Section 1.2 approximation methods that allow to reduce the number of degree of freedom given the tensorial form of their approximated solutions.

Some approaches to approximate high-dimensional functions

In this section, we present a short survey on methods proposed in the literature for approximating high-dimensional functions. We recall that the approach used in this work to obtain this approximations is presented in Chapter 2.

Sparse grids

The sparse grid method is a numerical discretization technique for multivariate problems. This approach is introduced in [START_REF] Smolyak | Quadrature and interpolation formulas for tensor products of certain classes of functions[END_REF] and studied by Schwab [START_REF] Petersdorff | Numerical solution of parabolic equations in high dimensions[END_REF] and Zenger [START_REF] Zenger | Sparse grids[END_REF]. In this part, we present a short survey of this method. See [START_REF] Bungartz | Sparse grids[END_REF] for a complete introduction to the sparse grid methods. This approach is also known under the name of hyperbolic cross points or splitting interpolations.

Let us consider X = [0, 1]. The use of one-dimensional multilevel (or hierarchical) basis is one of the main ideas of the sparse grid method. In the classical approach, the following standard hat function is employed to construct the hierarchical basis functions

φ(ξ) :=      1 -|ξ|, if ξ ∈ [-1, 1] 0, otherwise. (1.3)
Consequently, we can consider a set of equidistant grids of level m and mesh width h m = 2 -m on X by introducing the following points:

ξ m,i := i2 -m , 0 ≤ i ≤ 2 m .
Associated to the points ξ m,i , we define the basis function (φ m,i ) 1≤i≤2 m -1 using the standard hat function (1.3)

φ m,i (x) := φ � x -x m,i 2 -m � .
We note that this basis is the standard basis of P 1 Lagrange finite element functions with mesh size h m and with support on [ξ m,ih m , ξ m,i + h m ].

Thus, we can define the function spaces

V m := Span {φ m,i , 1 ≤ i ≤ 2 m -1}
and the hierarchical increment spaces W m W m := Span {φ m,i , i ∈ I m } , where the index set I m is defined as follows

I m := {i ∈ N, 1 ≤ i ≤ 2 m -1, i odd } .
Hence, the increment spaces verify the following relation

V m = � k≤m W k ,
where the symbol ⊕ means that the sum is direct. This decomposition (φ i,k ) k≤m,i∈I k leads to the hierarchical basis of V m because any continuous piecewise linear function u ∈ V m can be written as

u = m � k=1 � i∈I k u k,i φ k,i ,
with u k,i ∈ R for all 1 ≤ k ≤ m and i ∈ I k . We remark that the support of all the basis functions φ k,i spanning W k are mutually disjoint.

In order to explain, the tensor product construction in high-dimensional spaces, let us introduce i = (i 1 , . . . , i d ) ∈ N d and k = (k 1 , . . . , k d ) ∈ N d two multi-indices. The notation

i ≤ k means that ∀ 1 ≤ j ≤ d, i j ≤ k j
Moreover, we will consider the notation 2 i = (2 i 1 , . . . , 2 i d ) ∈ N d and 1 = (1, . . . , 1) ∈ N p .

The goal is to construct a multi-dimensional basis on X d = [0, 1] d from the one-dimensional hierarchical basis. In order to do that, we consider the d-dimensional tensorization of the one-dimensional basis (φ k,i ) 1≤k≤m,i∈I k by introducing m = (m 1 , . . . , m d ) the multi-index denoting the level of discretization in each dimension and the grid points x m,i given by x m,i = (x m 1 ,i 1 , . . . , x m d ,i d )

where i = (i 1 , . . . , i d ) ∈ N d with 1 ≤ i ≤ 2 m .

Then, for each grid point x m,i , an associated d-dimensional basis function φ m,i is defined as the product of the one-dimensional basis functions. φ m j ,i j (x j ).

Thus, using this basis of functions, we can define the spaces V m of continuous piecewise d-linear functions

V m := Span {φ m,i , 1 ≤ i ≤ 2 m -1} . (1.4)
As in the one-dimensional case, we can define the hierarchical increments W m as follows

W m := Span {φ m,i , i ∈ I m }
where

I m := � i ∈ N d , 1 ≤ i ≤ 2 m -1, i j odd for all 1 ≤ j ≤ d �
Consequently, the spaces V m verify the property

V m = � k≤m W k ,
and therefore any function u ∈ V m can be written under the form

u(x) = � 1≤k≤m � i∈I k u k,i φ k,i (x), u k,i ∈ R.
In order to introduce an optimization with respect to the number of degrees of freedom and the obtained accuracy of the approximation, we consider the sparse grid space Vn of level n defined as follows:

Vn :=

� |k| 1 ≤n+d-1 W k .
where moreover, in this case, the associated full grid space V n can be written as

V n := � |k|∞≤n W k ,
The dimension of the space Vn , that means, the number of degrees of freedom or grid points is given by

dim Vn = n-1 � i=0 2 i � p -1 + i p -1 � = O(h -1 n | log 2 (h n )| p-1 ).
We remark that the space V n can be seen as the discretization space associated with a standard P 1 finite element discretization based on a uniform discretization of mesh size h n = 2 -n , so the dimension of the space V n is of the order O(h -p n ). Consequently, the reduction in the number of degrees of freedom is significant by considering Vn instead of V n .

To show the accuracy of the approximation obtained by the sparse grid methods, we introduce the following Sobolev space

H 2,mix (X d ) := � u ∈ L 2 (X d ), ∂ α u ∈ L 2 (X d ), α ∈ N d , |α| ∞ ≤ 2 � ,
and we denote by Π Vn and Π Vn , the L 2 (X d )-orthogonal projector of L 2 (X d ) onto V n and onto Vn respectively.

For all u ∈ H 2,mix (X d ) ∩ H 1 0 (X d ), the approximation error of the function u on the sparse grid space is

�u -Π Vn u� L 2 (X d ) = O(h 2 n n d-1 ), (1.5)
and on the full grid space, the accuracy is

�u -Π Vn u� L 2 (X d ) = O(h 2 n ). (1.6)
For a given error level, in (1.5), the number of degrees of freedom does not grow exponentially with the dimension. These results (see [START_REF] Bungartz | Sparse grids[END_REF]) show the advantage of using the sparse grid space Vn with respect to the full grid space V n because the number of degrees of freedom is strongly reduced while the accuracy is insignificantly deteriorated if the exact solution is regular enough. The efficiency of the sparse tensor products is lost when the solution u is not regular or when the considered mesh is complicated. Consequently, in practice, this method may be difficult to apply for reasons such as the lack of regularity of the solution and the difficulty to implement the associated algorithms.

Canonical, Tucker and Tensor Train decompositions

In this section, we suppose that the Hilbert space V has the following form:

V = d � i=1 V i .
(1.7)

i.e., V is tensor product of Hilbert spaces of univariate functions. In other words, for all 1 ≤ i ≤ d, the function u i ∈ V i is such that u i : x i ∈ Ω i � → u(x i ) and then a function u ∈ V is such that u : (x 1 , . . . , x d ) ∈ Ω 1 × . . . × Ω d � → u(x 1 , . . . , x d ). By considering (1.7), the goal is to obtain a number of degrees of freedom which does not depend exponentially on the dimension d.

Canonical decomposition

The canonical decomposition is a classical method to represent in a tensor format a function u ∈ V . This approach looks for a representation of u as follows

(x 1 , . . . , x d ) � → u(x 1 , . . . , x d ) = r � k=1 � d � i=1 u i,k � (x 1 , . . . , x d ), (1.8)
that is, u is represented by r elementary products of single-variate functions. The number r of products of single-variate functions is called the canonical rank of the function u. In a finite dimensional case with dim(V i ) = N , for all i = 1, . . . , d, we can deduce that the complexity of the decomposition (1.8) is rdN .

Nevertheless, one disadvantage of this approach is that the set of rank-r tensors

C r := � u ∈ V, u(x 1 , . . . , x d ) = r � k=1 � d � i=1 u i,k � (x 1 , . . . , x d ), ∀1 ≤ r, u i,k ∈ V i �
is not a weakly closed subset of V when d ≥ 3 and r ≥ 2, see [START_REF] Silva | Tensor rank and the ill-posedness of the best low-rank approximation problem[END_REF]. Consequently, there may not exists a minimizer to the problem inf ũ∈Cr �u -ũ� V

In the literature, this decomposition is also called CANDECOMP or PARAFAC as in [START_REF] Bader | Tensor decompositions and applications[END_REF].

Tucker decomposition

A more robust tensor format decomposition is called the Tucker decomposition that consists in decomposing u as follows:

(x 1 , . . . , x d ) � → u(x 1 , x 2 , . . . , x d ) = r 1 � k 1 =1 . . . r d � k d =1 c k 1 ,...,k d � p � i=1 u i,k i � (x 1 , . . . , x p ),
where for all 1

≤ i ≤ d, r i ∈ N * , u i,k i ∈ V i for all 1 ≤ k i ≤ r i and c k 1 ,...,kp ∈ R.
Thus, in the Tucker decomposition, the function u is decomposed over all the possible tensor products between the functions (u i,k i ) 1≤k i r i for all 1 ≤ i ≤ d.

Let us note r T := (r 1 , . . . , r p ) ∈ (N * ) p the Tucker rank of u. The set of tensors of Tucker rank r T is weakly closed in V , then the problem of the best approximation has a solution. Nevertheless, we observe that if r T = (r, . . . , r) and dimV i = N for all 1 ≤ i ≤ d this approach leads to a complexity given by O(r d + N rd) that is exponential with the respect to the dimension d. Hence, the Tucker decomposition is not pertinent when d is large.

Tensor train

The following decomposition allows to overcome the exponential complexity obtained in the case of the Tucker decomposition and it is called tensor train decomposition. In this case, the function u is represented as follows:

(x 1 , . . . , x d ) � → u(x 1 , . . . , x d ) = r 1 � k 1 =1 . . . r d-1 � k d-1 =1 U 1 (x 1 , k 1 )U 2 (k 1 , x 2 , k 2 ) . . . U d-1 (k d-2 , x d-1 , k d-1 )U p (k d-1 , x d ).
The rank of the function u in the case of the tensor train is defined as r T T = (r 1 , . . . , r d-1 ) ∈ (N) d-1 . Based on this tensor train decomposition, a function u can be expressed as the following product of matrices

u(x 1 , . . . , x d ) = U 1 (x 1 ) . . . U p (x p )
where

x 1 � → U 1 (x 1 ) ∈ R 1×r 1 , x 2 � → U 2 (x 2 ) ∈ R r 1 ×r 2 , . . . x d-1 � → U d-1 (x d-1 )R r d-2 ×r d-1 , x d � → U d (x d ) ∈ R r d-1 ×1 .
The set of functions of tensor train rank of at most r T T is a weakly closed subset of V. Moreover, the complexity of this type of decomposition is O(r 2 N d) if r i = r and dimV i = N for all i = 1, . . . d

and not exponential with respect to d as in the case of the Tucker decomposition.

The algorithms used in practice to compute the best approximation of a given tensor in the Tucker or tensor train format, execute successive Singular Value Decomposition problems. We can mention the Higher Order Orthogonal Iteration (HOOI) [START_REF] Lathauwer | A multilinear singular value decomposition[END_REF], the Newton-Grassman approach [START_REF] Eldén | A Newton-Grassmann method for computing the best multilinear rank-(r 1 , r 2 , r 3 ). approximation of a tensor[END_REF] or the Higher Order Singular Value Decomposition (HOSVD) [START_REF] Lathauwer | On the best rank-1 and rank-(r 1 , r 2 , . . . , r n ) approximation and applications of higher-order tensors[END_REF].

High-dimensional problems in finance

In finance, many of the high-dimensional applications include high-dimensional partial differential equations (PDE). A high-dimensional PDE is an equation that depends on several independent variables. Roughly, the PDEs can be classified in elliptic, parabolic and hyperbolic. In this work, we principally study the parabolic ones, given that in finance the relation between the Black-Scholes model (see Section 1.3.2) and this type of equations give them a strong importance.

The goal of this section is to present some high-dimensional PDEs that appear in finance and that are studied in this manuscript, but before that, it is important to begin by introducing the standard framework used in mathematical finance.

Important concepts in finance

The pricing of financial options is one of the most important problems in financial mathematics.

In 1900, Bachelier [Bacal] is the first that shows that for answering this kind of problems it is important to use suitable mathematical techniques. This domain did not have a very strong development until the 70's with the Black-Scholes model developed in 1973 by Merton, Black and Scholes [START_REF] Merton | Option pricing when underlying stock returns are discontinuous[END_REF][START_REF] Black | The pricing of options and corporate liabilities[END_REF],

where they define the price of derivatives as the price needed to hedge them. After that, the financial mathematics domain was driven by the martingale theory developed in the 80's.

One of the most typical examples of derivatives proposed in markets are the options. An European call (resp. put) option is a financial contract that gives to the holder the option and not the obligation to buy (resp. sell) a number of stocks to the price K at time T . The fixed price K is known as the strike and T is the maturity of the option. The underlying is equal to S T at the maturity T and the option will be exercised if S T > K (resp. S T < K) and consequently, the holder's gain is given by S T -K (resp. K -S T ) because he can buy (resp. sell) the stock at the price K and after sell (resp. buy) it in the market at the price S T . Otherwise, the option is not exercised and the gain is equal to 0. Hence, we note that the value of the call at the maturity is given by

(S T -K) + = max(S T -K, 0).
For the counterpart (the bank) which sells the European call option, the goal is to provide the stocks at price K and thus to obtain at the maturity a wealth equal to (S T -K) + . At the time when the option is sold, the value of the asset S T is not known and then the question of the pricing, that is, how much the client has to pay to get a call option, is very important.

To answer the question of the pricing, some assumptions are usually considered. The hypothesis that appears in most models is that in a liquid market there is no arbitrage, that means, it is impossible to make profit without taking risks.

Under the assumption of no arbitrage, the price of the call option at time T is given by (S T -K) + .

In general, the price at the maturity of an option is a function of S T called the payoff. There exist different types of payoff functions, In this work, we will mainly consider the payoff:

1 ∀t∈[0,T ],
φ(S 1 T , . . . , S d T ) = � K - 1 d d � i=1 S i T � + (1.9)
called a basket put option.

Hence, the function φ depends on d different assets which, in general, do not evolve independently.

The Black-Scholes model

In section 1.3.1, we already presented the main ideas of the theory of options in the framework of financial mathematics. The goal of this section is to develop the relationship between theory and mathematical equations that are obtained based on the Black-Scholes model.

A partial differential equation for the option pricing problem

In this section, we present the framework that allows to find a PDE for pricing European options.

In order to do that, we introduce the classical Black-Scholes model that takes into account a risky asset with price S t at the time t and a risk-free asset which price at time t is S 0 t . In this model, S t and S 0 t are such that:

dS t = µS t dt + σS t dB t , and
dS 0 t = rS 0 t dt
where B t is a Brownian motion in a probability space (Ω, (F t ) t≥0 , P), and µ (the mean rate of return), σ > 0 (the volatility) and r (the risk-free interest rate) are three constants. This framework can be generalized to the case where r, µ and σ are functions of the time t and the stock S t under suitable smoothness assumptions. The filtration (F t ) t≥0 is the natural filtration of the Brownian motion B t .

Let us introduce the risk-free probability measure Q defined by its Radom-Nikodim derivative with respect to P as follows

dQ dP | Ft = exp � � t 0 µ -r σ dB s + � t 0 � µ -r σ � 2 ds � (1.10)
This new probability Q is one of the key tools to obtain the results of the Black-Scholes model.

If we introduce the stochastic process W t = B t + µ-r σ t, the process S t satisfies the following stochastic differential equation under the probability Q

dS t = S t (rdt + σdW t ) (1.11)
where W t is a Brownian motion and St S 0 t is a martingale under the probability Q.

Since we are interested in the pricing of an option, the Black-Scholes model is studied in the interval [0, T ] where T is the maturity of the option. Thus, the solution of the equation (1.11) is given by

S t = S 0 e (r-σ 2 2 )t+σWt , t ∈ [0, T ]. (1.12)
where S 0 is the value of the asset at time t = 0.

Specifically, we can observe that the process (S t ) t≥0 satisfies the equation (1.11) if the process (log(S t )) t≥0 is a Brownian motion, not necessarily standard. Looking at the expression of the process S t obtained in (1.12), we find the assumptions of the Black-Scholes model on the evolution of the asset. These are:

-Continuity of the trajectories.

-

If u ≤ t, St Su is independent of the sigma-algebra σ (S v , v ≤ u) -If u ≤ t, (St-Su) Su and (S t-u -S 0 ) S 0
have the same law.

Let us define now a strategy that allows to generate a portfolio. A strategy is a process As we mentioned in section 1.3.1, the great idea of the Black-Scholes model is to put together the pricing of the option and the quantity of money needed to hedge it. Theoretically, for a given function φ (the payoff) and a given maturity T , it is possible to create a self-financing portfolio such that P T = φ(S T ). This result is obtained using the martingale representation theorem, the fact that φ is F T -measurable and that Pt S 0 t is a martingale. Using the martingale property, the value of the portfolio at the time t is

(H t ) 0≤t≤T = (H t , H 0 t ) ∈ R 2 adapted
P t = E � e -(T -t)r φ(S T )|F t � (1.15)
Using the so-called arbitrage-free principle, it is possible to show that P t has to be the price at time t of the option which allows the holder to obtain the payoff φ(S T ) at the maturity T .

A PDE formulation of the pricing option problem can be obtained because of the Markov property of the process S t . This Markovianity means that the expectation of any function of (S t ) 0≤t≤T conditionally to F t is a function of the price of the asset S t at time t. In other words, this implies that

P t = p(t, S t ) (1.16)
where p is a function of t ∈ [0, T ] and S ∈ [0, ∞), known as the pricing function of the option. We remark that the pricing function p is a deterministic function defined for all values of t ≥ 0 and S ≥ 0.

As a consequence of the Markov property of S t , we can re-write the pricing function p under the form:

p(t, x) = E � e r(T -t) φ(S t,x T ) �
where the process S t,x u is the solution of the equation (1.11) starting from x at time t, or equivalently,

     dS t,x u = S t,x u (rdu + σdW u ), u ≥ t, S t,x t = x
Using Itô's calculus and the fact that Pt S 0 t is a martingale, we deduce that p has to verify the following PDE:

     ∂p ∂t + rS ∂p ∂S + σ 2 S 2 2 ∂ 2 p ∂S 2 -rp = 0, p(T, S) = φ(S).
(1.17) It is possible to show that if p verifies (1.17), then p(t, S t ) is the value of a self-financing portfolio such that its value is equal to φ(S T ) at time T .

The Black-Scholes formula

In this section, we present the formulas obtained for the pricing of European options. The fact that relatively simple expressions give the price of these financial contracts is one of the most important features of this model.

Let us note P (t, S) the price of the option with maturity T of payoff φ. Assuming that r and σ > 0 are constants, the price of the option in the Black-Scholes equation is given by

P (t, S) = e -r(T -t) E Q � φ � Se r(T -t) e σ(W T -Wt)-σ 2 2 (T -t)

��

(1.18)

The expression (1.18) can be written under the following form

P (t, S) = 1 √ 2π e -r(T -t) � R φ � Se (r-σ 2 2 )(T -t)+σ √ T -ty -Ke -r(T -t) � e -y 2 2 dy because under the probability Q, W T -W t is a centered Gaussian random variable with variance T -t.
If we take the case of a put option, that means that the payoff φ is such that φ(S t ) = (S t -K) + , we can get that

C(t, S) = 1 √ 2π � d 2 -∞ � Se -σ 2 2 (T -t)-σy √ T -t -Ke -r(T -t) � e -y 2 2 dy, (1.19)
where

d 1 = log � S K � + (r + σ 2 2 )(T -t) σ √ T -t and d 2 = d 1 -σ √ T -t (1.20)
The Black-Scholes formula can be derived from (1.19).

Proposition 1.1. If we assume that σ > 0 and r are two constants, the price of a European call option is given by

C(t, S) = SN (d 1 ) -Ke -r(T -t) N (d 2 ), (1.21)
and for the case of a European put option, the price is

P (t, S) = -SN (-d 1 ) + Ke -r(T -t) N (-d 2 ). (1.22)
where d 1 and d 2 are defined by (1.20) and N is the cumulative distribution function of a centered Gaussian distribution with variance equal to 1.

Finally, we can remark that if r and σ are functions of time, the formulas (1.21) and (1.22) are still valid, replacing the expressions (1.20) by

d 1 = log � S K � + � T t r u du + 1 2 � T t σ 2 u du � � T t σ 2 u du and d 2 = d 1 - � � T t σ 2 u du (1.23) 1.3.3 High-dimensional partial differential equations in finance
The goal of this section is to extend the model presented in the previous Section 1.3.2 to the case when d-assets are considered as the underlyings of an option.

Model with d risky assets

We consider that there exist d risky assets whose prices at time t are written S i (t). We assume that for all i such that 1 ≤ i ≤ d, the price S i (t) verifies the following stochastic differential equation:

dS i (t) = µ i S i (t)dt + σ i S i (t)dW i (t) (1.24)
We have to point out that (W i (t)) for 1 ≤ i ≤ d are correlated Brownian motions defined on a probability space (Ω, (F t ) t≥0 , P). Let us introduce ρ ij the correlation factor between W i (t) and W j (t).

That is

ρ ij = E [W i (t)W j (t)] t
We remark that -1 ≤ ρ ij ≤ 1 and ρ ii = 1. In addition, the volatilities σ i , for 1 ≤ i ≤ d are positive constants.

As in Section 1.3.2, we are interested in the study of an European option, but on d underlyings, with d > 1. If T is the maturity of the option of payoff f (S 1 (T ), . . . , S d (T )), it is possible to find a risk-free probability measure Q that allows to write the price of the option at time t as follows:

P t = E Q � e -r(T -t) f (S 1 (T ), . . . , S d (T ))|F t � (1.25)
Let us find, as in the case presented in Section 1.3.2, the linear parabolic partial differential equation on d + 1 variables linked with the equation (1.25) and that allows to find the price P t at time t of the option. In order to do that, we cite some results given in [START_REF] Achdou | Computational methods for option pricing[END_REF].

Proposition 1.2. Let us introduce the differential operator

L : f � → 1 2 d � i=1 d � j=1 Ξ ij S i S j ∂ 2 f ∂S i S j + r d � i=1 S i ∂f ∂S i , (1.26)
where

Ξ ij = ρ ij σ i σ j . Then, for all function u : (S 1 , . . . , S d , t) � → u(S 1 , . . . , S d , t),u ∈ C 2,1 (R d + × [0, T )) verifying |S i ∂u ∂S i | ≤ C(1 + |S i |), i = 1, .
. . , d with C that does not depend on t, the process

M t = e -rt u(S 1 (t), . . . , S d (t)) - � t 0 e -rτ � ∂u ∂t + Lu -ru � (S 1 (t), . . . , S d (t))τ
is a martingale under the filtration F t .

Theorem 1.1. Let P be a continuous function,

P ∈ C 2,1 (R d + × [0, T )) such that |S i ∂P ∂S i | ≤ C(1 + S i )
where C does not depend on t. Assuming that P verifies the equation

� ∂P ∂t + LP -rP � (S 1 , . . . , S d , t) = 0, t < T, (S 1 , . . . , S d ) ∈ R d + (1.27)
and satisfies the Cauchy condition

P (S 1 , . . . , S d , T ) = f (S 1 , . . . , S d ), (S 1 , . . . , S d ) ∈ R d + ,
then the price of the European option given by (1.25) verifies

P t = P (S 1 (t), . . . , S d (t), t)
It should be outlined that in the case of a basket option, analytical formulas such as those presented for the case of one asset can no longer be found. This implies the use of numerical methods in order to approximate the price.

Free boundary problems

In some applications we do not only need to find the solution of a PDE but it is also necessary to define constraints on an unknown boundary. The problem of the execution of an American option can be studied with this type of problem.

It is possible to show (see [START_REF] Achdou | Computational methods for option pricing[END_REF]) that the partial differential equation for the pricing of the American option can be expressed under the following form:

     min � Lu - ∂u ∂t , φ -u � = 0, in R T := (0, T ) × R d u(0, x) = φ(x), x ∈ R d (1.28)
where the parabolic operator L is defined by (1.26).

From equation (1.28), we deduce that u ≥ φ and then the region R T is divided in two parts:

the so-called exercise region where u = φ and the continuation region where u > φ and Lu -∂u ∂t = 0. We remark that, in the continuation region, the price of the option verifies the Black-Scholes PDE.

In fact, the problem (1.28) is equivalent to

                     Lu - ∂u ∂t ≤ 0, in R T u ≥ φ, in R T (u -φ) � Lu - ∂u ∂t � = 0, in R T u(0, x) = φ(0, x), x ∈ R d (1.29)
This type of problem is known as the obstacle problem and is presented in Section 5.2 where we propose an application of the algorithm introduced in Chapter 2 for treating the problem of the American options.

2

A nonlinear approximation method for solving high-dimensional partial differential equations

Many problems of interest for various applications such as kinetic models, molecular dynamics, quantum mechanics, uncertainty quantification and finance involve high-dimensional partial differential equations.

It is well known that when the number of variables of a PDEs is very large, standard algorithms such as finite differences and finite elements cannot be used in practice to solve them. As we discussed in Section 1.1, the reason is the curse of dimensionality, in other words, the number of unknowns typically grows exponentially with respect to the problem's dimension and rapidly exceeds the limited storage capacity.

The main goal of this Section is to present an algorithm which has been recently proposed by Chinesta et al. [START_REF] Ammar | A new family of solvers for some classes of multidimensional partial differential equations encountered in kinetic theory modeling of complex fluids[END_REF] for solving high-dimensional Fokker-Planck equations in the context of kinetic models for polymers and by Nouy et al. [START_REF] Nouy | Proper generalized decompositions for a priori model reduction of problems formulated in tensor product spaces: Alternative definitions and algorithms[END_REF] in uncertainty quantification framework based on previous works by Ladevèze [START_REF] Ladevèze | Nonlinear computational structural mechanics: new approaches and nonincremental methods of calculations[END_REF]. This approach is also studied in [START_REF] Bris | Results and questions on a nonlinear approximation approach for solving high-dimensional partial differential equations[END_REF] to try to circumvent the curse of dimensionality for the Poisson problem in high-dimension. This approach is a nonlinear approximation method that we will call below the Proper Generalized Decomposition (PGD).

It is related to the so-called greedy algorithms introduced in nonlinear approximation theory, see for example [START_REF] Temlyakov | Greedy approximation[END_REF]. The main idea of the PGD is to represent the solution as a sum of tensor products:

u(x 1 , . . . , x d ) = � k≥1 r 1 k (x 1 )r 2 k (x 2 ) . . . r d k (x d ) = � k≥1 � r 1 k ⊗ r 2 k ⊗ . . . ⊗ r d k � (x 1 , . . . , x d ) (2.1)
and to compute iteratively each term of this sum using a greedy algorithm. The algorithm of the PGD method can be applied to any PDE which admits a variational interpretation as a minimization problem. The practical interest of this algorithm has been demonstrated in various contexts (see for example [START_REF] Ammar | A new family of solvers for some classes of multidimensional partial differential equations encountered in kinetic theory modeling of complex fluids[END_REF] for applications in fluid mechanics).

One contribution of this work is to complete the first application of this algorithm in finance, investigating the interest of this approach for option pricing. Our aim is to study the problem of pricing vanilla basket options of European type by solving the Black-Scholes equation and to propose in addition a variance reduction method for the pricing of the same type of financial products.

This application in finance leads us to consider two extensions of the standard algorithm, which apply to symmetric linear partial differential equations: (i) non-symmetric linear problems to value European options, (ii) nonlinear variational problems to price American options.

In this chapter, our goal is to present this nonlinear approximation method that we study in this work from a general mathematical point of view.

In what follows, we introduce the approach that we study to solve high-dimensional PDEs that arise in finance. This method is called Proper Generalized Decomposition and it is connected to the greedy algorithms proposed in the nonlinear approximation theory by Temlyakov in [START_REF] Temlyakov | Greedy approximation[END_REF], Davis et al. in [START_REF] Avellaneda | Adaptive greedy approximations[END_REF] and Barron et al. in [BCDD08]. Other related works are the methods based on looking for the best n-term approximation of operators as in [START_REF] Bader | Tensor decompositions and applications[END_REF] and [START_REF] Beylkin | Numerical operator calculus in higher dimensions[END_REF].

We begin by presenting the greedy algorithms in a general framework and the link with the PGD. After that, we define the PGD and we apply it, as an example, to the Poisson problem. Finally, we recall results on convergence and speed of convergence for the Proper Generalized Decomposition.

Greedy algorithms

In what follows, we present an introduction to greedy algorithms. See [START_REF] Temlyakov | Greedy approximation[END_REF], [START_REF] Devore | Some remarks on greedy algorithms[END_REF] or [START_REF] Barron | Approximation and learning by greedy algorithms[END_REF] for more details. We consider V a real Hilbert space associated with the inner product �., .� V and with the norm �.� V . We define a dictionary D as a family of functions from V such that all the elements of the dictionary D are normalized, that means �g� V = 1 for all g ∈ D and Span(D) = V . We also assume that the dictionary is symmetric namely that g ∈ D ⇒ -g ∈ D.

The problem tackled by the greedy algorithms theory is the problem of approximating a function u ∈ V by a finite linear combination of elements of the dictionary D. Thus, to analyze the greedy algorithms, we introduce the best n-term approximation u n of the function u ∈ V where u n is a linear combination of at most n elements of the dictionary D. Mathematically, it amounts to looking for the functions g 1 , . . . , g n ∈ D such that they minimize the following error:

(g 1 , . We remark that for a general dictionary D (D is not an orthonormal basis), the solution obtained after n iterations of the algorithm is generally not the best rank-n approximation (2.14).

The difference between the OGA and the PGA is that the OGA takes the Galerkin projection on the functions g o 1 , . . . , g o n generated at each iteration. The first and second steps are the same for the OGA and the PGA.

The convergence of these algorithms is proved for all u ∈ V as we can see in the following theorem.

Theorem 2.1. For any dictionary D and any u ∈ V , we have that PGA:

�r p n � = �u -u p n � -→ n→∞ 0, OGA: �r o n � = �u -u o n � -→ n→∞ 0,
It is also possible to prove convergence rates for these algorithms. In order to do that, it is necessary to define a functional space for the function u, adapted to the convergence analysis. For a general dictionary D, we introduce the following class of functions

A 1 0 (D, M ) :=    u ∈ V : u = � k∈Λ c k v k , v k ∈ D, #Λ < ∞ and � k∈Λ |c k | ≤ M   
Let us also introduce the space A 1 (D, M ) as the closure in

H of A 1 0 (D, M ), that is, A 1 (D) := ∪ M >0 A 1 (D, M ), or, equivalently, A 1 (D) = � u ∈ V, u = ∞ � k=1 r 1 k ⊗ r 2 k ⊗ . . . ⊗ r (d) k , ∞ � k=1 �r 1 k ⊗ r 2 k ⊗ . . . ⊗ r (d) k � V < ∞ � ,
Thus, the following result proved in [START_REF] Devore | Some remarks on greedy algorithms[END_REF] holds:

Theorem 2.2. For a general dictionary D in V , the following estimates can be deduced: For a function u ∈ A 1 , there exists a constant M > 0 such that

�r p n � = �u -u p n � ≤ M n -1/6 , �r o n � = �u -u o n � ≤ M n -1/2 , for all n ∈ N * .
We note that the constant M depends on the norm �u� A 1 . In [START_REF] Konyagin | Rate of convergence of pure greedy algorithm[END_REF], Konyagin and Temlyakov obtain a better estimate for the PGA

�r p n � = �u -u p n � ≤ M n -11/62 .

The Proper Generalized Decomposition

As we said in the introduction of this Section, this approach has been recently proposed by Chinesta et al. in [START_REF] Ammar | A new family of solvers for some classes of multidimensional partial differential equations encountered in kinetic theory modeling of complex fluids[END_REF] to solve high-dimensional Fokker-Planck equations in the context of kinetic models for polymers and Nouy in [START_REF] Nouy | Proper generalized decompositions for a priori model reduction of problems formulated in tensor product spaces: Alternative definitions and algorithms[END_REF] in the context of uncertainty quantification following previous works by Ladevèze [START_REF] Ladevèze | Nonlinear computational structural mechanics: new approaches and nonincremental methods of calculations[END_REF].

In general, let V be a Hilbert space of multivariate functions u(x 1 , . . . , x d ) and let V 1 , . . . , V d be Hilbert spaces of single-variate functions depending on the one-dimensional variable x i . One of the principles of the PGD is to choose the dictionary of functions as the set of tensor products

D := � r 1 ⊗ . . . ⊗ r d |r 1 ∈ V 1 , . . . r d ∈ V d , �r 1 ⊗ . . . ⊗ r d � V = 1 � (2.3)
where r 1 ⊗ r 2 ⊗ . . . ⊗ r d (x 1 , x 2 . . . , x d ) = r 1 (x 1 )r 2 (x 2 ) . . . r d (x d ).

Let us define the following set of simple products

Σ := � r 1 ⊗ . . . ⊗ r d , r 1 ∈ V 1 , . . . , r d ∈ V d � (2.4)
Under the assumptions

(A1) Σ ⊂ V , (A2) SpanΣ �.� V = V , ( A3
) for all sequences of Σ bounded in V , there exists a subsequence which weakly converges in

V towards an element of Σ, the dictionary D defined in (2.3) is a well-defined dictionary of V . We note that the assumption (A3)

implies that the problems of the type (2.2) have at least one solution.

The PGD is based on two main ideas. The first one is to extend the solution as a sum tensor products of lower-dimensional functions

u n (x 1 , x 2 , . . . , x d ) = n � k=1 r 1 k ⊗ r 2 k . . . ⊗ r d k (x 1 , x 2 , . . . , x d ) (2.5)
where for all i = 1, . . . , d and k = 1, . . . , n, the functions r

(i) k ∈ V i .
Consequently, the function u n is a separated representation of the solution u ∈ V .

The second idea is to recast the original problem (in our case a high-dimensional PDE) as a minimization problem:

u = argmin v∈V E(v), (2.6)
where E : V � → R is functional with a unique global minimizer u ∈ V .

In general, to compute u n in the separated form (2.5), u n being the approximation of u solution of the problem (2.6), we propose to use the PGD that is defined as follows:

Iterate on n ≥ 1 (r 1 n , r 2 n , . . . , r d n ) ∈ argmin r 1 ∈V 1 , r 2 ∈V 2 ,..., r d ∈V d E � n-1 � k=1 r 1 k ⊗ r 2 k ⊗ . . . ⊗ r d k + r 1 ⊗ r 2 ⊗ . . . r d � , (2.7)
where V , V 1 , . . . , V d are Hilbert spaces.

The principle of the algorithm is to look iteratively for the best tensor product and this leads to a nonlinear approximation method which gives the solution u n as defined in (2.5). We remark that the implementation of (2.7) amounts to applying the Pure Greedy Algorithm in the Hilbert space V and for the dictionary D defined by (2.3).

Instead of solving the minimization problem (2.7), we solve the first-order optimality conditions of this minimization problem, namely the Euler equation. This yields to a system of equations where the number of degrees of freedom does not grow exponentially with respect to the dimension. This fact will be very important in order to reach high-dimensional frameworks in practical applications. More precisely, the Euler equation writes as a system of d nonlinear equations, where d is the dimension considered. The maximum dimension that can be treated by this technique is limited by the fact that a system of d nonlinear equations has to be solved. We also note that the solutions of the Euler equation are not necessarily solutions of the minimization problem given the nonlinearity of the tensor product space

V 1 ⊗ . . . ⊗ V d .
Thus, the greedy algorithm can be stated as follows: For n ≥ 0, find

� r 1 n ⊗ r 2 n ⊗ . . . ⊗ r d n � ∈ H 0 1 (Ω 1 ) × H 0 1 (Ω 2 ) × . . . × H 0 1 (Ω d ) such that (r 1 n , r 2 n , . . . , r d n ) ∈ argmin r 1 ∈V 1 , r 2 ∈V 2 ,...,r d ∈V d E � n-1 � k=1 r 1 k ⊗ r 2 k ⊗ . . . ⊗ r d k + r 1 ⊗ r 2 ⊗ . . . ⊗ r d � , (2.8) Remark 2.1. Curse of dimensionality
As we already said, in the PGD approach we look for a solution under the form:

u n (x 1 , x 2 , . . . , x d ) = n � k=1 r 1 k ⊗ r 2 k . . . ⊗ r d k (x 1 , . . . , x d ) (2.9)
In practice, the functions r i k are obtained as linear combinations of the basis functions (φ l j i ) 1≤l≤N i . Thus, we introduce the space V h i x i as the finite element spaces used to discretize the Hilbert spaces V x i that are spaces of functions depending on the one-dimensional variable x i

V h i x i = Span {φ j , 0 ≤ j ≤ N i }
where h i is the parameter of discretization

h i = 1 N i .
At the end, the problem of computing the approximation (2.9) leads to solving a problem of dimension Ñ such that

Ñ = n d � i=1 N i (2.10)
which remains lower compared with N defined in (1.2), if n is small enough.

2.3 Some particular cases: the Singular Value Decomposition and the general linear case

Tensor product of spaces

Let us define the inner product �. , .� ⊗ associated to the space Span(Σ) as follows:

∀ � r 1 , r 2 , . . . , r (d) � , � r1 , r2 , . . . , rd � ∈ V 1 × V 2 × . . . × V d , �r 1 ⊗ r 2 ⊗ . . . ⊗ r d , r1 ⊗ r2 ⊗ . . . ⊗ rd � ⊗ = �r 1 , r1 � V 1 �r 2 , r2 � V 2 . . . �r d , rd � V d
Likewise, we define the related norm �� ⊗ called cross-norm as

∀ � r 1 , r 2 , . . . , r (d) � ∈ V 1 × V 2 × . . . × V d , �r 1 , r 2 , . . . , r (d) � ⊗ = �r 1 � V 1 �r 2 � V 2 . . . �r (d) � V d .
(2.11) Thus, the tensor product of the spaces

V 1 , V 2 , . . . , V d , noted by V 1 ⊗ V 2 ⊗ . . . ⊗ V d and defined as � Span(Σ) �•� ⊗ , �•, •� ⊗ � is a Hilbert space.
In this section, we discuss two cases in which the greedy algorithm satisfies important properties.

The Singular Value Decomposition case

In this case we consider that

E(v) = �u -v� 2 V (2.12) where V = V 1 ⊗ V 2 ,
that means, the product of only two Hilbert spaces. Moreover, we assume that the norm � • � V is a cross-norm following the definition (2.11) in Section 2.3.1.

In this case, the pairs (r

1 n , r 2 n ) ∈ V 1 × V 2 ,
defined by (2.7), verify the following orthogonality relation:

�r 1 n , r 1 m � V 1 = �r 2 n , r 2 m � V 2 = 0, ∀n � = m (2.13)
This orthogonality property has several consequences:

-The Pure Greedy Algorithm and the Orthogonal Greedy Algorithm are equivalent.

-The decomposition of the function u as follows

u = ∞ � k=1 r 1 k ⊗ r 2 k is unique.
-At iteration n, the approximation

u n = � n k=1 r 1 k ⊗ r 2 k is the best rank-n term approximation of u �u - n � k=1 r 1 k ⊗ r 2 k � V = inf (r 1 k ,r 2 k )∈V1×V2, 1≤k≤n �u - n � k=1 r1 k ⊗ r2 k � V . (2.14)
It is also possible to deduce that -The solutions to the Euler-Lagrange equation which maximize the L2 -norm �� Ω |r ⊗ s| 2 � 1/2 are exactly the solutions to the minimization problem.

-In dimension d = 2, the solutions to the Euler-Lagrange equation that satisfy the second optimality conditions are the solutions of the minimization problem.

-Let λ k = �r 1 k ⊗ r 2 k � V for all 1 ≤ k ≤ ∞.
The sequence (λ k ) k ∈ N * is non-increasing and the convergence rate of the algorithm is related to this sequence as is showed in (2.15):

�u -u N � 2 V = ∞ � k=n+1 �r 1 k ⊗ r 2 k � 2 = ∞ � k=n+1 λ 2 k .
(2.15)

The linear case

In this case, we consider again a quadratic functional E(v) = �u -v� 2 V but V is the product of more than two Hilbert spaces or the norm is not a cross-norm. Here, the convergence results (2.1) and (2.2) hold but the orthogonality property (2.13) is no longer verified. This implies that the PGA and the OGA are not equivalent. The greedy algorithms do not give as solution the best rank-n decomposition as is defined in (2.14) and the sequence

λ k = �r 1 k ⊗ r 2 k � V for all 1 ≤ k ≤ ∞ is not necessarily non-increasing.

Other cases of application for the Proper Generalized Decomposition

The work of Cancès, Ehrlacher and Lelièvre [START_REF] Cancès | Convergence of a greedy algorithm for highdimensional convex nonlinear problems[END_REF] study the case when the functional E is not supposed to be a quadratic energy functional. They extend the work [START_REF] Bris | Results and questions on a nonlinear approximation approach for solving high-dimensional partial differential equations[END_REF] by considering a general strongly convex energy functional. In this section, we give an outline of this extension. In particular, these results can be used to solve an obstacle problem with uncertainty with a large number of random parameters. As the pricing of American options can be written as an obstacle problem (see Section 5.2), the method proposed in [START_REF] Cancès | Convergence of a greedy algorithm for highdimensional convex nonlinear problems[END_REF] can also be applied for the pricing of American options.

Let us consider the following assumptions: (A4) The energy functional E is differentiable and strongly convex. Mathematically, that means that there exists α > 0 such that

∀v, w ∈ V, E(v) ≤ E(u) + �∇E(w), v -w� V + α 2 �v -w� 2 V .
(A5) The gradient of E is Lipschitz on bounded sets: for each bounded subset K ⊂ V , there

exists a constant L K such that ∀v, w ∈ K, �∇E(v) -∇E(w)� V ≤ L K �v -w� V .
Thus, Cancès, Ehrlacher and Lelièvre prove in [START_REF] Cancès | Convergence of a greedy algorithm for highdimensional convex nonlinear problems[END_REF] the following theorem:

Theorem 2.3. If the conditions (A1)-(A5) are verified, then the iterations of the algorithm (2.7) are well-defined, in the sense that (2.7) has at least one minimizer (r 1 n , r 2 n , . . . , r d n ). Moreover, the sequence (u n ) n∈N strongly converges in V to u.

The following result is about the speed of convergence:

Theorem 2.4. If the spaces V 1 , V 2 , . . . , V d are finite dimensional, the convergence rate of the algorithm is exponential, in other words, there exists C, σ > 0 such that for all n ∈ N * �u -

u n � V ≤ Ce -σn
The constant C can be estimated by �u� V and the constant σ depends on the dimensions of the

spaces V 1 , V 2 , . . . , V d .
Another important result obtained by Cancès, Ehrlacher and Lelièvre [START_REF] Cancès | Convergence of a greedy algorithm for highdimensional convex nonlinear problems[END_REF] is that if we suppose in addition that (A6) There exists β, γ > 0 such that for all

� r 1 , r 2 � ∈ V 1 × V 2 , with V 1 and V 2 two Hilbert spaces. β�r 1 � V 1 �r 2 � V 2 ≤ �r 1 ⊗ r 2 � ≤ γ�r 1 � V 1 �r 2 � V 2
then it is not necessary to obtain the global minimum of (2.8) to ensure the convergence of the greedy algorithm. We note that this result is proved when it is considered a product of only two Hilbert spaces.

Theorem 2.5. Let us suppose that we are in the case of only two Hilbert spaces V 1 and V 2 and that the assumptions (A1)-(A6) are satisfied. Then, if at each iteration n ∈ N, the pair

� r 1 , r 2 � ∈ V 1 × V 2
is chosen to be a local minimum of (2.8), such that E(u n ) < E(u n-1 ), then (u n ) n∈N * still converges strongly in V towards u the solution of (2.6). Besides, if the Hilbert spaces V 1 and V 2 are finite dimensional, the rate of convergence of the algorithm is still exponential in n, i.e., there exists C, σ > 0

such that for all n ∈ N * �u -u n � V ≤ Ce -σn

The Proper Generalized Decomposition for the approximation of a square-integrable function

In order to show the implementation that we use for the algorithm (2.7), let us present the simple problem of approximating a square-integrable function f by a sum of tensor products. Mathematically, we consider the spaces

V = L 2 (Ω 1 × Ω 2 × . . . × Ω d ), V x i = L 2 (Ω i ) for i = 1, . . . , d, where Ω i ⊂ R is a bounded domain for i such that 1 ≤ i ≤ d.
We recall that we are looking for a separated representation

f = � k≥1 r 1 k ⊗ r 2 k ⊗ . . . ⊗ r d k .
So, let us consider the following minimization problem:

Find u ∈ L 2 (Ω 1 × Ω 2 × . . . × Ω d ) such that u = arg min v∈L 2 � 1 2 � Ω 1 ×Ω 2 ×...×Ω d v 2 - � Ω 1 ×Ω 2 ×...×Ω d vf � (2.16)
whose solution is obviously u = f . In this context, the algorithm of the PGD (2.7) can be rewritten as follows:

Iterate for all n ≥ 1:

Find (r 1 n , r 2 n , . . . , r d n ) ∈ V x 1 ×V x 2 ×. . .×V x d such that (r 1 n , r 2 n , . . . , r d n ) belongs to argmin r 1 ∈L 2 (Ω 1 ),...,r d ∈L 2 (Ω d ) 1 2 � Ω 1 ×Ω 2 ×...×Ω d � � � � � n-1 � k=1 r 1 k ⊗ r 2 k ⊗ . . . ⊗ r d k + r 1 ⊗ r 2 ⊗ . . . ⊗ r d � � � � � 2 - � Ω 1 ×Ω 2 ×...×Ω d � n-1 � k=1 r 1 k ⊗ r 2 k ⊗ . . . r d k + r 1 ⊗ r 2 ⊗ . . . ⊗ r d � f,
(2.17)

As proposed in [START_REF] Bris | Results and questions on a nonlinear approximation approach for solving high-dimensional partial differential equations[END_REF], instead of solving the problem (2.17), we will determine the solutions of the Euler equation for (2.17). Notice that, in general, the solutions of the Euler equation are not necessarily the solutions of the minimization problem, given the nonlinearity of the tensor product

space L 2 (Ω 1 ) ⊗ L 2 (Ω 2 ) ⊗ . . . ⊗ L 2 (Ω d ).
The Euler equation for (2.17) has the following form:

Find (r 1 n , r 2 n , . . . , r d n ) ∈ L 2 (Ω 1 )×L 2 (Ω 2 )×. . .×L 2 (Ω d ) such that for any functions (r 1 , r 2 , . . . , r d ) ∈ L 2 (Ω 1 ) × L 2 (Ω 2 ) × . . . × L 2 (Ω d ), we have � Ω 1 ×Ω 2 ×...×Ω d (r 1 n ⊗ r 2 n ⊗ . . . ⊗ r d n ) � r 1 ⊗ r 2 n ⊗ . . . ⊗ r d n + r 1 n ⊗ r 2 ⊗ . . . ⊗ r d n + . . . + r 1 n ⊗ r 2 n ⊗ . . . ⊗ r d � = � Ω 1 ×Ω 2 ×...×Ω d f n-1 � r 1 ⊗ r 2 n ⊗ . . . ⊗ r d n + r 1 n ⊗ r 2 ⊗ . . . ⊗ r d n + . . . + r 1 n ⊗ r 2 n ⊗ . . . ⊗ r d � (2.18) where f n-1 = f - � n-1 k=1 r 1 k ⊗ r 2 k ⊗ . . . ⊗ r d k .
The equation (2.18) can be written equivalently as

                 �r 2 n � 2 �r 3 n � 2 . . . �r d n � 2 r 1 n = � Ω 2 ×Ω 3 ×...×Ω d � r 2 n ⊗ . . . ⊗ r d n � f n-1 , �r 1 n � 2 �r 3 n � 2 �r 4 n � 2 . . . �r d n � 2 r 2 n = � Ω 1 ×Ω 3 ×Ω 4 ...×Ω d � r 1 n ⊗ r 3 n ⊗ r 4 n ⊗ . . . ⊗ r d n � f n-1 , . . . �r 1 n � 2 �r 2 n � 2 �r 3 n � 2 . . . �r d-1 n � 2 r d n = � Ω 1 ×Ω 2 ×Ω 3 ...×Ω d-1 � r 1 n ⊗ r 2 n ⊗ r 3 n ⊗ . . . ⊗ r d-1 n � f n-1 , (2.19)
where �r i n � 2 denotes the L 2 norm:

�r i n � 2 = � Ω i |r i n | 2 . The system (2.19
) is a non linear coupled system of equations which can be solved by a fixed point procedure as proposed in [START_REF] Ammar | A new family of solvers for some classes of multidimensional partial differential equations encountered in kinetic theory modeling of complex fluids[END_REF]. Choose (r

1,(0) n , r 2,(0) n , . . . , r d,(0) ) ∈ L 2 (Ω 1 )×L 2 (Ω 2 )×. . .×L 2 (Ω d ),
and at iteration k ≥ 0, compute (r

1,(k) n , r 2,(k) n , . . . , r d,(k) ) ∈ L 2 (Ω 1 ) × L 2 (Ω 2 ) × . . . × L 2 (Ω d ) which is the solution to                      �r 2,(k) n � 2 �r 3,(k) n � 2 . . . �r d,(k) n � 2 r 1,(k+1) n = � Ω 2 ×Ω 3 ×...×Ω d � r 2,(k) n ⊗ . . . ⊗ r d,(k) n � fn-1, �r 1,(k+1) n � 2 �r 3,(k) n � 2 �r 4,(k) n � 2 . . . �r d,(k) n � 2 r 2,(k+1) n = � Ω 1 ×Ω 3 ×Ω 4 ...×Ω d � r 1,(k+1) n ⊗ r 3,(k) n ⊗ r 4,(k) n ⊗ . . . ⊗ r d,(k) n � fn-1, . . . �r 1,(k+1) n � 2 �r 2,(k+1) n | 2 �r 3,(k+1) n � 2 . . . �r d-1,(k+1) n � 2 r d,(k+1) n = � Ω 1 ×Ω 2 ×Ω 3 ...×Ω d-1 � r 1,(k+1) n ⊗ r 2,(k+1) n ⊗ r 3,(k+1) n ⊗ . . . ⊗ r d-1,(k+1) n � fn-1, (2.20)
until convergence is reached.

It is important to note that we start with a linear problem (2.16) with exponential complexity with respect to the dimension, and we obtain at the end a nonlinear problem (2.19) with a linear complexity with respect to the dimension at each iteration . This is a general feature of the PGD method: the curse of dimensionality is circumvented, but the linearity of the original problem is lost because the space of tensor products is non-linear.

In the two-dimensional case (d = 2), the algorithm given by (2.17) is related to the Singular Value Decomposition (or rank one decomposition), as it is explained in [START_REF] Bris | Results and questions on a nonlinear approximation approach for solving high-dimensional partial differential equations[END_REF]. In this case, the solutions of the variational problem (2.17) are exactly the solutions to the Euler equation (2.18) that verify the second-order optimality conditions (See Section 2.3). This property does not hold in a d-dimensional framework with d ≥ 3.

The Proper Generalized Decomposition in the case of the Poisson problem

In this section we present the application of the Proper Generalized Decomposition for solving high-dimensional PDEs through the use of the greedy algorithms.

As in [BLM09], we take the example of the Poisson problem. Let us consider a function f ∈ L 2 (Ω), where Ω = Ω 1 × . . . × Ω d with Ω i ⊂ R are bounded domains for all i = 1, . . . d. Thus, we define the following homogeneous multivariate Dirichlet Poisson problem:

Find u ∈ H 0 1 (Ω) such that      -Δu = f in Ω u = 0 on ∂Ω (2.21) Using Lax Milgram's theorem, (2.21) is equivalent to the following minimization problem Find u ∈ H 0 1 (Ω) such that u = argmin v∈H 0 1 (Ω) � 1 2 � Ω |∇v| 2 - � Ω f v � . (2.22)
Moreover, we note that the problem (2.22) is equivalent to

Find u ∈ H 0 1 (Ω) such that u = argmin v∈H 0 1 (Ω) � Ω |∇(v -u)| 2 , (2.23)
where u is the solution of the problem (2.22).

In particular, in the case of the Poisson problem (2.21), the greedy algorithm writes:

Find � r 1 n ⊗ r 2 n ⊗ × ⊗ r d n � ∈ H 0 1 (Ω 1 ) × H 0 1 (Ω 2 ) × . . . × H 0 d (Ω) such that � r 1 n ⊗ r 2 n ⊗ . . . ⊗ r d n � ∈ argmin r 1 ∈H 0 1 (Ω 1 ),r 2 ∈H 0 1 (Ω 2 ),r d ∈H 0 1 (Ω d ) 1 2 � Ω |∇ � r 1 ⊗ r 2 ⊗ . . . ⊗ r d � | 2 - � Ω f n-1 r 1 n ⊗r 2 n ⊗. . .⊗r d n (2.24)
where

f n-1 = f + Δ � � n-1 k=1 r 1 k ⊗ r 2 k ⊗ . . . ⊗ r d k � .
The Euler-Lagrange equation related to the minimization problem (2.24) is:

Find (r 1 n , r 2 n , . . . , r d n ) ∈ H 0 1 (Ω 1 )×H 0 1 (Ω 2 )×. . .×H 0 1 (Ω d ) such that for any function (r 1 , r 2 , . . . , r d ) ∈ H 0 1 (Ω 1 )×H 0 1 (Ω 2 )×H 0 1 (Ω d ) � Ω ∇ � r 1 n ⊗ r 2 n ⊗ . . . ⊗ r d n � • ∇ � r 1 ⊗ r 2 n ⊗ . . . ⊗ r d n + r 1 n ⊗ r 2 ⊗ . . . ⊗ r d n + . . . + r 1 n ⊗ r 2 n ⊗ . . . ⊗ r d � = = � Ω f n-1 � r 1 ⊗ r 2 n ⊗ . . . ⊗ r d n + r 1 n ⊗ r 2 ⊗ . . . ⊗ r d n + . . . + r 1 n ⊗ r 2 n ⊗ . . . ⊗ r d � (2.25)
This Euler-Lagrange equation can be written as follows

                 - � �r 2 n � 2 L 2 . . . �r d n � 2 L 2 � � r 1 n � ′′ + � d i=2 � d j=2,j� =i �r j n � 2 L 2 r 1 n = � Ω 2 ×...×Ω d f n-1 r 2 n ⊗ . . . ⊗ r d n - � �r 1 n � 2 L 2 �r 3 n � 2 L 2 . . . �r d n � 2 L 2 � � r 2 n � ′′ + � d i=1,i� =2 � d j=1,j� =2,j� =i �r j n � 2 L 2 r 2 n = � Ω 1 ×Ω 3 ...×Ω d f n-1 r 1 n ⊗ r 3 n . . . ⊗ r d n . . . - � �r 1 n � 2 L 2 . . . �r d-1 n � 2 L 2 � � r d n � ′′ + � d i=1,i� =d � d j=1,j� =d,j� =i �r j n � 2 L 2 r d n = � Ω 1 ×...×Ω d-1 f n-1 r 1 n ⊗ . . . ⊗ r d-1 n (2.26)
We observe that the Euler equation (2.25) is not equivalent to the original problem (2.24) because of the nonlinearity of the tensor product space

H 1 0 (Ω 1 ) ⊗ . . . ⊗ H 1 0 (Ω d )
We remark that calculating high-dimensional integrals as:

� Ω 1 ×Ω 2 ...×Ω d f (x 1 , x 2 , . . . , x d ) r 1 n (x 1 ) ⊗ . . . ⊗ r d n dx 1 dx 2 . . . dx d (2.27)
can be very costly. The idea that we use to overcome this practical obstacle is to approximate, in a preliminary step, the data (the function f ) by a sum of tensor products using, for example, the approach presented in Section 2.5 and then to use Fubini's rule to compute the term (2.27).

As in the case of the approximation of a square-integrable function, we start from a linear problem with exponential complexity with respect to the dimension d as (2.21) and we end up with a nonlinear problem with linear complexity with respect to the dimension d given by (2.26).

We observe that (2.26) is a nonlinear coupled system of low-dimensional Poisson equations, which may be solved by a simple fixed point procedure as follows: At iteration l ≤ 1, find the functions (r

(1),l n , r

(2),l n , . . . , r

(d),l n ) ∈ H 0 1 (Ω 1 ) × H 0 1 (Ω 2 ) . . . × H 0 1 (Ω d ) solution to                          - � �r 2,l-1 n � 2 L 2 . . . �r d,l-1 n � 2 L 2 � � r 1,l n � ′′ + � d i=2 � d j=2,j� =i �r j,l-1 n � 2 L 2 r 1,l n = � Ω 2 ×...×Ω d f n-1 r 2,l-1 n ⊗ . . . ⊗ r d,l-1 n - � �r 1,l n � 2 L 2 �r 3,l-1 n � 2 L 2 . . . �r d,l-1 n � 2 L 2 � � r 2,l n � ′′ + � d i=1,i� =2 � d j=1,j� =2,j� =i �r j,l-1 n � 2 L 2 r 2,l n = � Ω 1 ×Ω 3 ...×Ω d f n-1 r 1,l n ⊗ r 3,l-1 n . . . ⊗ r d,l-1 n . . . - � �r 1,l n � 2 L 2 . . . �r d-1,l n � 2 L 2 � � r d,l-1 n � ′′ + � d i=1,i� =d � d j=1,j� =d,j� =i �r j,l n � 2 L 2 r d,l-1 n = � Ω 1 ×...×Ω d-1 f n-1 r 1,l n ⊗ . . . ⊗ r d-1,l n (2.28)
We remark that the number of degrees of freedom needed to obtain the solution u n in the form (2.5) is n

� d i=1 N i
where N i is the number of discretization points in the dimension i. So, the number of unknowns at each iteration of the algorithm (2.7) grows linearly with respect to the dimen-sion and this allows an important reduction in the number of degrees of freedom with respect to the classical approach. At each iteration of the greedy algorithm, the computational cost is given by the solution of a low-dimensional nonlinear problem which is deduced from the high-dimensional linear problem as in the example given in the previous section 2.6.

Convergence results for the Poisson problem

Le Bris, Lelièvre and Maday in [START_REF] Bris | Results and questions on a nonlinear approximation approach for solving high-dimensional partial differential equations[END_REF] prove that the PGD (2.24) converges when the PGA and OGA are used to solve the Poisson problem.

Theorem 2.6. Let us assume that the assumptions (A1), (A2) and (A3) are verified and that the functional E has the form (2.12). Then, for a function u ∈ A 1 , there exists a constant C > 0 such that

�u n -u� V ≤ Cn -1/6 , (2.29) for all n ∈ N * .
As mentioned above, the convergence rate factor of 1 6 can be improved to 11 62 and that the constant C depends on the norm �u� A 1 .

An extension of this result is proposed by Figueroa and Sully in [START_REF] Figueroa | Greedy approximation of high-dimensional Ornstein-Uhlenbeck operators with unbounded drift[END_REF] in the case of an arbitrary diffusion coefficient satisfying a uniform ellipticity assumption.

Remark 2.2. A full characterization of the set A 1 (D) is not clear. Le Bris, Lelièvre and Maday in [START_REF] Bris | Results and questions on a nonlinear approximation approach for solving high-dimensional partial differential equations[END_REF] give the following characterization of this set in terms of standard Sobolev spaces for the Poisson problem (2.21)

For any m > 1 + d 2 , H m (Ω) ∩ H 0 1 (Ω) ⊂ A 1 (D)
More characterizations for the set A 1 (D) are obtained in [START_REF] Figueroa | Greedy approximation of high-dimensional Ornstein-Uhlenbeck operators with unbounded drift[END_REF] for more general operators.

3

Approximation of a Put payoff function using the Proper

Generalized Decomposition

In this section, we discuss the implementation of the Proper Generalized Decomposition defined by (2.7) in the case of the approximation of a put payoff function (that is, a square-integrable function) by a sum of tensor products as we presented in Section 2.5. We will then provide numerical examples of the application of this approach. This particular case has the advantage of being an easy example to understand the implementation of the algorithm (2.7). Moreover, this procedure is useful in a preliminary step to approximate the initial condition of the Black-Scholes PDE (see Section 4.1.5), namely in order to get a separated representation of the payoff function.

Separated representation of a Put payoff

In this section we will apply the algorithm (2.17) to obtain an approximation of the payoff of a basket put option. This implies that we take f (x 1 , . . . ,

x d ) = � K -1 d � d i=1 x i � +
in the algorithm (2.17).

For the practical implementation of the greedy algorithm, we need to introduce the space discretization.

In practice, the spaces V Δx x i for i = 1, . . . , d that are used to discretize L 2 (Ω i ) with Ω i = (0, 1) for i = 1, . . . d are the P1 finite elements on a uniform mesh with space step Δx. The number N = 1 Δx is the number of intervals in each direction. For each k, we discretize the functions r i k for i = 1, . . . , d that appear in the approximation of the solution given by the expression (2.18) as follows:

r i,Δx k (x i ) = N � j=0 r i,j k φ j (x i ), r i,j k ∈ R, ∀j, k, (3.1)
where

φ i (x) = φ � x-x i Δx � with φ(x) =    1 -|x| if |x| ≤ 1, 0 if |x| > 0.
This type of discretization and its generalization to the d-dimensional case will be used for all the numerical simulations of this work. Put payoff First iteration of the greedy algorithm Third iteration of the greedy algorithm Fig. 3.1. Basket put option with two assets. We consider here the intersection between the surface of prices and the plane S1 = S2. To obtain this approximation we take 31 points of discretization per dimension (N= 30). In this figure, we show the approximation given after the first and third iteration of the algorithm.

In order to study numerically the problem of approximating a square-integrable function, we discuss about the fixed point procedure, the criteria of convergence of the algorithm (2.7) and the numerical integration techniques used in our numerical experiments.

Fixed point procedure

In what follows, we are going to study the convergence of the fixed point method (2.20) from a numerical point of view. This method allows us to find the solution of the Euler equation represented by the non-linear system of equations (2.19). In order to analyze the fixed point procedure used in practice in this work, we will propose three different stopping criteria for two different norms:

L ∞ and L 2 .
The first criterion consists in simply fixing arbitrarily the number of iterations. This arbitrary number of iterations can be determined, for instance, by iterating the algorithm many times and thus deduce the needed number by experience. The advantage of such a method is that we do not have to compute any norm of the error at each step of the fixed point procedure (2.20) and so we can reduce the computational time. Nevertheless, the inconvenient is that we cannot predict if the chosen number is optimal.

A second criterion, called the residues method, consists in determining the convergence of the fixed point method by calculating the following norm (L 2 or L ∞ ):

�r 1,k+1 n ⊗ r 2,k+1 n ⊗ ... ⊗ r d,k+1 n -r 1,k n ⊗ r 2,k n ⊗ ... ⊗ r d,k n � �r 1,k n ⊗ r 2,k n ⊗ ... ⊗ r d,k n � (3.2)
where n is fixed and represents the PGD iteration and k is the fixed point iteration.

The third implemented method compares the solutions obtained in two consecutive iterations of the fixed point method fixing one direction, by computing the following norm in L 2 or a L ∞ :

�r i,k+1 n -r i,k n � �r i,k n � (3.3)
Let us now, to compare the last two criteria according to the number of iterations of the fixed point procedure (2.20). Figure 3.2 illustrates the evolution of the number of iterations needed for the convergence of the fixed point procedure when we use the expressions given by (3.2) and (3.3) for a basket put option function with 5 assets. For practical considerations, we consider a maximum number of 30 fixed point iterations by dimension, so for each PGD iteration we compute a maximum of 150 fixed point iterations in a five-dimensional framework. We observe that for this example, the criterion (3.3) yields to less iterations for the fixed point procedure compared with the criterion (3.2).

Nevertheless, we cannot say that we should always use the criterion (3.3), as in the case of a basket put option with 6 assets, the criterion (3.3) needs more iterations to converge compared with the criterion (3.2) as illustrated in Figure 3.3.

As a conclusion, we can say that for our numerical experiences, we have chosen an arbitrary number of iterations for the fixed point method because neither of the two criteria (3.3) and (3.2) does not seem to influence the convergence of the PGD algorithm.

Initial condition for the fixed point procedure and for the convergence of the Proper Generalized Decomposition method

A choice that can influence the convergence of the fixed point procedure is the initial condition.

To analyze this point, we study numerically two cases: a constant initial condition and a random initial condition.

The constant initial condition is equal to the matrix

�u(x 1 ,...,x d )- � n-1 k=1 r 1 k ⊗...⊗r d k � �1�
1, where 1 is the matrix such that 1 i,j = 1 for all i, j, whereas the random initial condition is given by vectors whose coordinates are uniform random variables in the set [-1, 1]. We renormalize this vector to obtain a norm equal to the current error �u(x 1 , . . . , x d ) -

� n-1 k=1 r 1 k ⊗ . . . ⊗ r d k �,
where n is the current PGD iteration and u is the basket put payoff with d assets.

Figures 3.4 and 3.5 compare the number of fixed point iterations needed under the criterion (3.3) depending on the choice of a random or constant initial condition. Using these figures, we outline that it is not clear if it would be better to begin the fixed point procedure with a random or a constant initial condition. The choice of a random or a constant initial condition for the fixed point procedure has to be analyzed as well from the convergence of the algorithm (2.7) to the basket put option function as the number of the PGD iterations increases. option approximation in the case of 5 and 6 assets respectively obtained with a random and a constant initial condition. We note that in this case, using a random initial condition leads to a faster convergence. The experience obtained by this type of observations led us to consider random initial conditions for the fixed point procedure in our numerical examples.

Criteria of convergence used in practice

In this part, we discuss about the criteria that we used in practice to establish the convergence of the PGD algorithm (2.17). We note that the computation of

�f (x 1 , . . . , x d ) - n � k=1 r 1 k ⊗ . . . ⊗ r d k �, (3.4)
where f is the square-integrable function to approximate, involves a high-dimensional integral. We give more details on the treatment of terms of type (3.4) in Section 3.5.

A possible criterion would be to verify if

�r 1 n ⊗ . . . ⊗ r d n � is small compared with � � n-1 k=1 r 1 k ⊗ . . . ⊗ r d k �. In [BLM09]
, the authors note that using this criterion can lead to missing a term with a large contribution in terms of norm. They show that in the fixed point procedure (2.20), an optimal term They also note that it is possible that the optimal terms r 1 n , . . . , r d n obtained when solving the Euler equation are picked in an order not appropriate for computational efficiency. Moreover, they remark that the relaxation step performed in the orthogonal version of the PGD does not solve any of these difficulties.

As the computation of the term (3.4) in dimension d, when d is large, is not possible for storage reasons, from a practical point of view, we use a number of iterations for the algorithm (2.17) defined a priori. This number of iterations can be estimated using many tries with the algorithm measuring at the end the norm of the error (3.4). We remark that even when the dimension d is not large, the computation of the error term (3.4) can take a lot of time.

In our numerical experiments, we calculate the support of the payoff function and we store the points obtained in order to use them in the next iterations of the algorithm. In this manner, a backtracking algorithm is used only one time in the computation of the approximation of the function f .

Numerical integration

In order to reduce the computational time needed to calculate the integrals presented in the system of equations (2.19), we use the specific form of the payoff function in order to compute, in a preliminary step, the points that belong to the support of this function. Thus, when we calculate numerically the integral term

� Ω 1 ×Ω 2 ×...×Ω d � r 1 n ⊗ r 2 n ⊗ . . . ⊗ r d n � f dx 1 dx 2 . . . dx d (3.5) in (2.
19), we do not need to pass through the points where the function vanishes. In practice, in order to describe the support of this payoff function, we use a backtracking algorithm. This type of algorithm consists in constructing candidates sequentially and neglecting them when they do not verify the conditions required as a solution, in this case to belong to the support of the payoff.

Specifically, we consider the function (K -

1 d � d i=1 S i ) + with S i ∈ [0, S max ] for all i = 1, . . . d.
Introducing the parameter N to discretize the interval [0, S max ], we obtain that S i j = x i j S max , with x i j = (j-1) N , j = 1, . . . , N + 1. This leads us to look for those x i , i = 1, . . . d such as

dK -S max d � i=1
x i j > 0 for j = 1, . . . , N + 1. In order to do that, we need to find the combinations of (i 1 , ..., i d ) ∈ N d , such that:

i 1 N + ... + i d N ≤ d K S max
From a point (i 1 , i 2 . . . , i d ) ∈ N d that belongs to the support of the function f , we increase i 1 by 1 and we check if this new point (i 1 + 1, i 2 . . . , i d ) is in the support of f . If this is the case, we continue incrementing i 1 until the considered point is no longer in the support of f and then we pass to the following coordinate.

For instance, in a 5-dimensional case, the computational time is reduced by a factor of 4 5 by taking into account the support of the payoff in the computations of the integral term (3.5).

Remark 3.1. Concerning the computational time, we note that if the dimension increases, one iteration of the algorithm takes more time to be computed because the number of equations in the Euler system (2.19) increases linearly with respect to the dimension. The integral terms of type (3.5) also demand more time of execution because the domain has a new variable.

Numerical results

Figure 3.8 shows that, as the dimension increases, the number of iterations needed to obtain the convergence increases as well.

We also provide in Table 3.1 the number of iterations needed in order to obtain a relative error of 10 -5 when we consider 11 points of discretization per dimension (N = 10). The relative error calculated is the discrete L 2 error

e n = � 1 N � N i 1 =1 � N i 2 =1 . . . � N i d =1 (f (x i 1 , x i 2 , . . . , x i d ) -u n (x i 1 , x i 2 , . . . , x i d )) 2 � 1 N � N i 1 =1 � N i 2 =1 . . . � N i d =1 f (x 1 , . . . , x d ) 2 (3.6) where u n (x 1 , x 2 , . . . , x d ) = � n k=1 r 1 k ⊗ r 2 k ⊗ . . . ⊗ r d k
is the solution obtained with the PGD algorithm at the iteration n. It is to be outlined that computing (3.6) is more costly than the PGD method itself.

Notice that the full tensor product approximation would require 11 8 ≃ 2.10 8 degrees of freedom in an 8-dimensional case, whereas we obtain 3974 × 8 × 11 ≃ 350000 degrees of freedom. For the evaluation of this number, we used the fact that at each iteration of the algorithm we get 8 functions that are determined by 11 discretization points.

We can also study the convergence of the algorithm with respect to the L ∞ norm. Figure 3.9 illustrates the convergence curves for the L 2 and L ∞ norm when we approximate a basket put option with 3 assets. Table 3.1. Number of iterations needed to obtain a relative error of 10 -5 when we take 11 discretization points per dimension

Mass lumping technique

Until here, all the numerical results presented were obtained by computing the term (3.5) using the following approximation: �

Ω 1 ×...×Ω d � r 1 n ⊗ . . . ⊗ r d n � f (x 1 , . . . , x d )dx 1 . . . dx d ≈ � Ω 1 ×...×Ω d N � i 1 =0 . . . N � i d =0 f (x i 1 1 , . . . , x i d d )φ i 1 (x 1 ) . . . φ i d (x d )   N � j 1 =0 r j 1 1 φ j 1 (x 1 )   . . .   N � j d =0 r j d 1 φ j d (x d )   dx 1 . . . dx d = N � i 1 =0 . . . N � i d =0 f (x i 1 1 , . . . , x i d d )   i 1 +1 � j 1 =i 1 -1 r 1,j 1 n � Ω 1 φ i 1 (x 1 )φ j 1 (x 1 )dx 1   . . .   i d +1 � j d =i d -1 r d,j d n � Ω d φ i d (x d )φ j d (x d )dx d  
The mass matrix M defined below is a symmetric and tridiagonal matrix because the supports of the functions φ i and φ j are disjoint when |i -j| > 1. The expressions of the terms of this mass matrix can be determined analytically.

(M) i,i = 2 � (i+1)h ih (x -ih) 2 h 2 = 2h 3 , and (M) i,i+1 = � (i+1)h ih (x -ih)((i + 1)h -x) h 2 dx = h 6
Nevertheless, we can also apply a mass lumping approach to reduce the execution time when solving the linear system of equations obtained using the tridiagonal mass matrix M. The mass lumping technique uses the trapezoidal rule for integration that gives the following approximation of the integral:

� (i+1)h ih f (x)dx = h (f (ih) + f ((i + 1)h)) 2
Using this formula, we can replace the matrix M by N defined as follows:

N i,i = h (φ i ((i -1)h) + φ i (ih)) 2 + h (φ i ((i + 1)h) + φ i (ih)) 2 = h, and
N i,i+1 = N i-1,i = 0
Therefore, the matrix N is such that N = hI where the matrix I is the identity matrix.

Figure 3.10 shows the convergence curves obtained using the matrices M and N respectively in the system of equations (2.19). In Figure (3.10), we can also note that solving the system (2.19) with the approximation using the mass matrix M is more precise than the mass lumping technique.

In Table 3.2, we compare the computational time needed to obtain 30 iterations of the PGD algorithm (2.17) to approximate a basket put option payoff function with and without mass lumping. The advantage in terms of the execution time of the mass lumping method for numerical integration is interesting because it allows to obtain relatively fast results in high-dimensional frameworks.

Nevertheless, when we look for more accurate approximations we consider the approximation given by the mass matrix M. The numerical experiments presented in this work do not consider mass lumping approximation except if it is indicated.

Pricing of a basket put using the separated approximation of the payoff

As an example to show that the approximation by a sum of tensor products makes sense, we can use this approximation as a method to obtain prices of options in the Black-Scholes framework.

The price of a European option in the Black-Scholes model (see Section 4.1.1) is given by and thus the integral (3.7) can be calculated very efficiently using the Fubini's rule.

P t = E � e -r(T -t) f (S 1 (T ), . . . , S d (T ))|F t � = � Ω 1 ×...×Ω d e -r(T -t) f (y 1 , . . . ,
In Figure 3.11, we apply this idea for the case of a basket put option on seven assets and in Table 3.4

we show results for at-the-money basket put options according to the dimension comparing the price of the method presented in this section with a Monte Carlo method with 10 4 and 10 6 simulations.

dS i (t) S i (t) = rdt + σ i dB i (t) for all i = 1, . . . , d, (4.1)
with

d�B i , B j � t = ρ ij dt. (4.2)
The number ρ ij is the correlation between the Brownian motions B i and B j that drive the dynamics of the assets S i and S j respectively.

The coefficient σ i represents the volatility of the asset S i at time t and r is the risk-free instantaneous interest rate. To simplify, we assume that r and σ i for i = 1, . . . d are constant during the period [0, T ]. We note that the PGD method that we are proposing can be used when the risk-free interest rate is a continuous function of time and the volatility is a continuous function of time and of the asset under standard regularity assumptions (See Chapter 2 in [START_REF] Achdou | Computational methods for option pricing[END_REF]).

We recall that the price of a European option with payoff f and maturity T is given by the following formula

E � e r(T -t) f (S 1 (T ), . . . , S d (T ))|F t � .
Using the Markovianity of the process (S 1 (t), . . . , S d (t)), it can be written as:

E � e r(T -t) f (S 1 (T ), . . . , S d (T ))|F t � = P (t, S 1 (t), . . . S d (t)), (4.3)
where P is a deterministic function.

The function P (t, S 1 , . . . , S d ) satisfies the Black-Scholes PDE which can be obtained using the Feynman-Kac theorem. The Black-Scholes equation in a d-dimensional framework is a parabolic PDE that has the following form:

     ∂P ∂t + LP = 0, t < T, (S 1 , . . . , S d ) ∈ R d + , P (T, S 1 , . . . , S d ) = f (S 1 , . . . , S d ), (S 1 , . . . , S d ) ∈ R d + , (4.4)
where the operator L is given by

LP = 1 2 d � i,j=1 ∂ 2 P ∂S i ∂S j ρ ij σ i σ j S i S j + d � i=1 rS i ∂P ∂S i -rP.
Let us recall the standard framework for problem (4.4). Setting τ := Tt, the time to maturity, we get the following forward parabolic problem for P (τ, S 1 . . . , S d ) = P (t, S 1 . . . , S d )

     ∂ P ∂τ -L P = 0, 0 < τ ≤ T, (S 1 , . . . , S d ) ∈ R d + P (0, S 1 , . . . , S d ) = f (S 1 , . . . , S d ), (S 1 , . . . , S d ) ∈ R d + .
(4.5)

We note that it is possible to write the diffusion term in the operator L + r in a divergence form as follows:

L P + r P = 1 2 d � i=1 ∂ ∂S i   d � j=1 ρ i,j σ i σ j S i S j ∂ P ∂S j   + d � j=1 � rS j - 1 2 d � i=1 ∂ ∂S i (ρ i,j σ i σ j S i S j ) � ∂ P ∂S j .
Therefore, if we multiply -L P by a test function Q and then we integrate on R d + , we obtain the following bilinear form:

b t ( P , Q) = 1 2 d � i=1 d � j=1 � R d + ρ i,j σ i σ j S i S j ∂ P ∂S j ∂Q ∂S i - d � j=1 � R d + � rS j - 1 2 d � i=1 ∂ ∂S i (ρ i,j σ i σ j S i S j ) � ∂ P ∂S j Q + r � R d + P Q. (4.6)
Let us now introduce the Hilbert space

V(R d + ) = � v : v ∈ L 2 (R d + ), S i ∂v ∂S i ∈ L 2 (R d + ), i = 1, . . . , d � and its norm �v� V = � �v� 2 L 2 (R d + ) + d � i=1 � � � � S i ∂v ∂S i � � � � 2 L 2 (R d + ) � 1 2 .
We have the following result for problem (4.5) (see Theorem 2.11 in [START_REF] Achdou | Computational methods for option pricing[END_REF]).

Theorem 4.1. Let us assume that the matrix Ξ defined by Ξ i,j = ρ i,j σ i σ j is positive-definite. Then for all f ∈ L 2 (R d + ), there exists a unique function

P ∈ L 2 (0, T ; V) ∩ C 0 ([0, T ]; L 2 (R d + )), with ∂ P ∂t ∈ L 2 (0, T ; V ′ ) such that, for any function φ ∈ D(0, T ), for all v ∈ V, - � T 0 φ ′ (t) � � R d + P (t)v � dt + � T 0 φ(t)b t ( P (t), v)dt = 0 (4.7)
and

P (t = 0) = f. (4.8)
This result shows the existence and uniqueness of a weak solution for the problem (4.5).

In this work, our goal is to obtain the curve of prices for a put basket option which has a squareintegrable payoff. The price of call basket options can be obtained by the well-known put-call parity.

So, as initial condition we consider the payoff function:

f (S 1 , . . . , S d ) = � K - 1 d d � i=1 S i (0) � + (4.9)
where the constant K is the strike of the option.

Three new difficulties appear when we want to apply the PGD techniques (2.7) to solve the problem (4.5) when we compare it with the application of the PGD method to the case of the Poisson problem as we presented in Section 2.6:

1. It is a problem posed on an infinite domain.

2. It is a time-dependent problem.

3. We cannot simply recast the weak formulation (4.7) of the problem (4.5) as a minimization problem because the bilinear form (4.6) is non-symmetric.

Formulation on a bounded domain

The financial assets S i for i = 1, . . . , d take values in [0, ∞). Consequently, we have to deal with an infinite domain. Let us then introduce the following transformations: Applying the change of variable (4.10) into the equation (4.4), we obtain:

Ψ : R + � → [0, 1], s � → s s + K d , (4.10)
Ψ -1 : [0, 1] � → R + , x � → xK d(1 -x) . ( 4
     -∂u ∂t + Lu = 0, u(0, x 1 , . . . , x d ) = (K -K d � d i=1 x i 1-x i ), (4.12)
where u(t, x 1 , . . . , x d ) = P (t, S 1 , . . . , S d ) with

S i = Ψ (x i ),(x 1 , . . . , x d ) ∈ Ω = (0, 1) d and Lu = div(A∇u) + d � i=1   r + σ 2 i x i -σ 2 i + σ i 2 d � j=1,j� =i ρ i,j σ j (2x j -1)   x i (1 -x i ) ∂u ∂x i -ru,
with the matrix A given by

A i,j (x 1 , . . . , x d ) := ρ i,j σ i σ j 2 x i x j (1 -x i )(1 -x j ). (4.13)
Then let us introduce the following Hilbert space

Ṽ(Ω) = � v ∈ L 2 (Ω) | ∀ 1 ≤ i ≤ d, (1 -x i )x i ∂v ∂x i ∈ L 2 (Ω) � , (4.14)
endowed with the norm

�v� Ṽ = � �v� 2 L 2 (Ω) + |v| 2 Ṽ � 1 2 (4.15)
where

|v| 2 Ṽ = d � i=1 � � � � x i (1 -x i ) ∂v ∂x i � � � � 2 L 2 (Ω) . (4.16)
In what follows, we need the following lemma:

Lemma 4.1. The space C ∞ c (Ω) is dense in Ṽ(Ω).
This lemma can be directly deduced from Lemma 2.6 in [START_REF] Achdou | Computational methods for option pricing[END_REF].

Corollary 4.1. The following integration by parts formula holds:

� Ω div(A∇u)v = - � Ω (A∇u)∇v, ∀u, v ∈ Ṽ(Ω).
(4.17)

Proof. It follows from Lemma 4.1.

Therefore, multiplying -Lu by a test function v ∈ C ∞ c (Ω) and then using (4.17), we get the following bilinear form:

bt (u, v) = � Ω (A∇u)∇v - � Ω (a∇u)v + � Ω ruv. (4.18)
where a = (a 1 , . . . , a d ) : Ω � → R d is the vector field with i-th component given by

a i (x 1 , . . . , x d ) = x i (1 -x i )   r + σ 2 i x i -σ 2 i + σ i 2 d � j=1,j� =i ρ ij σ j (2x j -1)   , (4.19)
The following result holds for the the bilinear form defined in (4.18)

Lemma 4.2. The bilinear form bt is continuous from Ṽ × Ṽ, that is, there exists a constant c that does not depend on t such that for all functions v, w ∈

Ṽ bt (v, w) ≤ c�v� Ṽ |w| Ṽ (4.20)
Moreover, the bilinear form bt verifies a Garding inequality, that is, there exist two positive constants

c > 0 and λ > 0 such that for all functions v ∈ Ṽ b(v, v) ≥ c|v| 2 Ṽ -λ�v� 2 L 2 (Ω) (4.21)
Proof. The Garding inequality is obtained by observing that the first order term satisfies the following:

� � � � � Ω p(x 1 , . . . , x d ) ∂v ∂x i v � � � � ≤ 1 2 � � � � � Ω ∂p ∂x i (x 1 , . . . , x d )v 2 � � �
� , where p(x 1 , . . . , x d ) is a polynomial. The proof of the continuity uses the same arguments. Thus, we obtain the following result concerning the existence and uniqueness of the solution for the weak formulation associated to the problem (4.12). Proposition 4.1. For all function g ∈ L 2 (Ω), there exists a unique u ∈ L 2 (0, T ; Ṽ )∩C 0 ([0, T ]; L 2 (Ω)), with ∂u ∂t ∈ L 2 (0, T ; Ṽ′ ) such that for any function φ ∈ D(0, T ), for all function v ∈ Ṽ,

- � T 0 φ ′ (t) � Ω u(t)vdt + � T 0 φ(t) b(u, v)dt = 0, (4.22)
and

u(t = 0) = g (4.23)
Moreover, u solution of (4.22) is related to P solution of (4.7) by the functions defined in (4.10) and (4.11).

This proposition can be deduced from Lemma 4.2 using standard techniques, see [START_REF] Achdou | Computational methods for option pricing[END_REF].

The IMEX scheme and the Black-Scholes equation as a minimization problem

To apply the PGD method (2.7), our goal is to rewrite the problem (4.12) as a minimization problem. As a first step, we propose to use an Euler scheme to discretize the problem in time. Let us consider a time discretization grid of M + 1 points, τ 0 = 0 ≤ . . . ≤ τ M = T , where τ i = iΔt and Δt = T M . We introduce a time discretization of the variational formulation (4.22) where we treat explicitly the non-symmetric part of bt and implicitly its symmetric terms (IMEX scheme).

For i = 1, . . . , M , find u i ∈ Ṽ such that � Ω u i v + Δt 1 + rΔt � Ω (A∇u i )∇v - Δt 2(1 + rΔt) �� Ω (a∇u i )v + � Ω (a∇v)u i � = 1 1 + rΔt � Ω u i-1 v + Δt 2(1 + rΔt) �� Ω (a∇u i-1 )v - � Ω (a∇v)u i-1 � , ∀v ∈ Ṽ.
(4.24) Thus, using that the left hand side of the equation (4.24) is symmetric in u i and v, we are led to solve the following sequence of minimization problems For i = 1, . . . , M :

Find u i ∈ Ṽ(Ω) such that u i = argmin u∈ Ṽ(Ω) E i (u) (4.25)
where

E i (u) = 1 2 � Ω |u| 2 + Δt 2(1 + rΔt) �� Ω (A∇u)∇u - � Ω (a∇u)u � - 1 1 + rΔt � Ω u i-1 u - Δt 2(1 + rΔt) �� Ω (a∇u i-1 )u - � Ω (a∇u)u i-1 � . (4.26)
Let us introduce the bilinear symmetric form â(u, v)

â(u, v) = � Ω uv + Δt 1 + rΔt � Ω (A∇u)∇v - Δt 2(1 + rΔt) �� Ω (a∇u)v + � Ω (a∇v)u � , ∀u, v ∈ Ṽ (4.27)
and the linear form

L i-1 (v) = 1 1 + rΔt � Ω u i-1 v + Δt 2(1 + rΔt) �� Ω (a∇u i-1 )v - � Ω (a∇v)u i-1 � , ∀v ∈ Ṽ.
(4.28)

We have that

E i (u) = 1 2 â(u, u) -L i-1 (u).

Stability analysis for the IMEX scheme

In this section, we study the L 2 -stability of the IMEX scheme (4.24). Let us consider u n the solution of the problem (4.25) at time τ n . In our context, the meaning of stability is given in the following definition.

Definition 4.1. The numerical scheme (4.24) is L 2 -stable if there exists a constant C > 0 that does not depend on the discretization parameter Δt such that for any initial condition u 0 and for all n ≥ 0

�u n � L 2 ≤ C�u 0 � L 2
We will see that the scheme (4.24) is L 2 -stable under a condition on the time step Δt. For the sake of simplicity we take r = 0. Let us begin with the following lemma:

Lemma 4.3. Let us assume that the matrix Ξ defined by Ξ i,j = ρ i,j σ i σ j , i, j = 1, . . . , d, is positivedefinite. Then there exists a constant α > 0 such that

� Ω (A∇u) ∇u ≥ α|u| 2 Ṽ , ∀u ∈ Ṽ. (4.29)
Proof. Using that the matrix Ξ is positive-definite, we have

� Ω d � i,j=1 ρ ij σ i σ j 2 x i (1 -x i ) ∂u ∂x i x j (1 -x j ) ∂u x j = � Ω Y T ΞY ≥ � min λ∈Sp(Ξ) λ � |u| 2 Ṽ
where Sp(Ξ) denotes the set of eigenvalues of the matrix Ξ and Y is the vector such that Y i =

x i (1x i ) ∂u ∂x i . This proves (4.29) with α = min λ∈Sp(Ξ) λ.

Now, we can state the following proposition:

Proposition 4.2. The scheme proposed in (4.24) is L 2 -stable under the following condition on the

time step Δt Δt < 1 2 � 4(�ã�∞+� div(a)�∞) α + α 2 � (4.30)
where the constant α is defined in Lemma 4.3 and ã is the vector such that for all i = 1, . . .

d ãi =   r + σ 2 i x i -σ 2 i + σ i 2 d � j=1,j� =i ρ i,j σ j (2x j -1)   .
Proof. Let us take r = 0 and v = u i in the variational formulation (4.24). Thus, we obtain

1 2Δt �� Ω |u i | 2 -|u i-1 | 2 � + 1 2Δt � Ω |u i -u i-1 | 2 + � Ω (A∇u i )∇u i - � Ω (a∇u i )u i = 1 2 �� Ω (a∇u i-1 )u i - � Ω (a∇u i )u i-1 � ⇔ 1 2Δt �� Ω |u i | 2 -|u i-1 | 2 � + 1 2Δt � Ω |u i -u i-1 | 2 + � Ω (A∇u i )∇u i - 1 2 � Ω (a∇(u i + u i-1 ))u i - 1 2 � Ω (a∇u i )(u i -u i-1 ) = 0. (4.31)
Moreover, we note that

a i = x i (1 -x i )ã i and that ã ∈ L ∞ (Ω).
Thus, for all ǫ > 0 we have that

� � � � � Ω (a∇u i )(u i -u i-1 ) � � � � ≤ ǫ|u i | 2 Ṽ + �ã� ∞ 4ǫ � Ω |u i -u i-1 | 2 . (4.32)
Besides, using the integration by parts given by (4.17) to study the term

� Ω (a∇(u i + u i-1 ))u i , we observe that � � � � � Ω a∇u i (u i + u i-1 ) � � � � = � � � � � Ω a∇u i � 2u i + (u i-1 -u i ) � � � � � , ≤ ǫ|u i | 2 Ṽ + �ã� ∞ 4ǫ �� Ω 2|u i -u i-1 | 2 + � Ω 8|u i | 2 � (4.33)
and

� � � � � Ω div(a)u i (u i + u i-1 ) � � � � ≤ � div(a)� ∞ 4ǫ �� Ω 2|u i -u i-1 | 2 + � Ω 8|u i | 2 � + ǫ � Ω |u i | 2 . (4.34)
Then, using (4.32), (4.33) and (4.34), we deduce from (4.31) that

� 1 2Δt - �ã� ∞ ǫ - � div(a)� ∞ ǫ - ǫ 2 � � Ω |u i | 2 + (α -ǫ)|u i | 2 Ṽ + � 1 2Δt - �ã� ∞ 4ǫ - � div(a)� ∞ 4ǫ � � Ω |u i -u i-1 | 2 ≤ 1 2Δt � Ω |u i-1 | 2 . (4.35)
So, if we assume the condition (4.30) and we choose ǫ = α 2 , then we can deduce the following three inequalities:

α > ǫ, 1 2Δt - �ã� ∞ + � div(a)� ∞ ǫ - ǫ 2 > 0 and 1 2Δt > �ã� ∞ + � div(a)� ∞ 4ǫ . (4.36)
Consequently, we get

� Ω |u i | 2 ≤ 1 1 -CΔt � Ω |u i-1 | 2 ≤ (1 + 2CΔt) � Ω |u i-1 | 2 ≤ (1 + 2CΔt) M � Ω |u 0 | 2 ≤ e 2CT � Ω |u 0 | 2 , where C = 2 � (�ã�∞+� div(a)�∞) ǫ + ǫ 2 �
is a constant which is independent of the discretization parameter Δt.

Implementation of the Proper Generalized Decomposition techniques for the

Black-Scholes partial differential equation

To simplify the notation we consider the case of only three dimensions, but the definition of the algorithm and all the equations below can be easily generalized to a d-dimensional framework.

We recall that the PGD method will generate the function u i in the separated representation:

u i (x 1 , x 2 , x 3 ) = � k≥1 r i k ⊗ s i k ⊗ t i k (x 1 , x 2 , x 3 ).
The PGD algorithm (4.25) is defined as follows:

For i = 1, . . . , M , iterate on n ≥ 1 (r i n , s i n , t i n ) ∈ argmin r ∈ Ṽ(Ω 1 ), s ∈ Ṽ(Ω 2 ), t ∈ Ṽ(Ω 3 ) 1 2 â(r ⊗s⊗t, r ⊗s⊗t)-L i-1 (r ⊗s⊗t)- â � n-1 � k=1 r i k ⊗ s i k ⊗ t i k , r ⊗ s ⊗ t � (4.37)
where â is defined by (4.27) and L i-1 by (4.28).

Then, the Euler equation associated with the problem (4.37), that is used in practice to implement the algorithm, is given by:

Find (r i n , s i n , t i n ) ∈ Ṽ(Ω 1 ) × Ṽ(Ω 2 ) × Ṽ(Ω 3 ) such that for any functions (r, s, t) ∈ Ṽ(Ω 1 ) × Ṽ(Ω 2 ) × Ṽ(Ω 3 ) â(r i n ⊗ s i n ⊗ t i n , r ⊗ s i n ⊗ t i n + r i n ⊗ s ⊗ t i n + r i n ⊗ s i n ⊗ t) = Li-1(r ⊗ s i n ⊗ t i n + r i n ⊗ s ⊗ t i n + r i n ⊗ s i n ⊗ t) +â � r ⊗ s i n ⊗ t i n + r i n ⊗ s ⊗ t i n + r i n ⊗ s i n ⊗ t, n-1 � k=1 r i k ⊗ s i k ⊗ t i k � (4.38)
Henceforth, we will consider without loss of generality s = 0 and t = 0 in order to study in detail each term of this Euler equation (4.38). We recall that the Euler equation is solved using a fixed point procedure as in (2.20).

Remark 4.1. All the high-dimensional integrals in (4.38) are easily calculated using Fubini's rule because the functions in these integrals are separable except for i = 1 where the term u 0 appears as follows:

� Ω 1 ×Ω 2 ×Ω 3 r ⊗ s i n ⊗ t i n (x 1 , x 2 , x 3 )u 0 (x 1 , x 2 , x 3 )dx 1 , dx 2 dx 3 , (4.39)
The idea used to overcome this practical obstacle is to approximate, in a preliminary step, the initial condition u 0 of the Black-Scholes PDE by a sum of tensor products as explained in Section 3.1.

Once the initial condition u 0 has a separated approximation:

u 0 (x 1 , x 2 , x 3 ) = � k≥1 r 0 k ⊗ s 0 k ⊗ t 0 k (x 1 , x 2 , x 3 ).
the integral (4.39) is easy to compute using Fubini's rule.

Using the space discretization described in Section 3.1 and the notation given by (3.1), the following vectors will be used:

r i n = [r i n,0 , . . . , r i n,N ] T , s i n = [s i n,0 , . . . , s i n,N ] T , t i n = [t i n,0 , . . . , t i n,N ] T ,
Given the fact that all the terms in the equation (4.38) admits a separated representation, the equation (4.38) can be written in a matrix form.

The following matricial expressions allow us to deduce the matricial form for the equation (4.38):

� Ω 1 ×Ω 2 ×Ω 3 (r i n ⊗ s i n ⊗ t i n )(r ⊗ s i n ⊗ t i n ) = [t i n T M t i n ][s i n T M s i n ]M r i n , � Ω 1 ×Ω 2 ×Ω 3 � A∇(r i n ⊗ s i n ⊗ t i n ) � ∇(r ⊗ s i n ⊗ t i n ) = � σ 2 2 2 [t i n T M t i n ][s i n T Ls i n ] + σ 2 3 2 [t i n T Lt i n ][s i n T M s i n ] � M r i n + � ρ1,2σ1σ2 2 [t i n T M t i n ][s i n T Ds i n ] + ρ1,3σ1σ3 2 [t i n T Dt i n ][s i n T M s i n ] � (D + D T )r i n + σ 2 1 2 [s i n T M s i n ][t i n T M t i n ]Lr i n , � Ω 1 ×Ω 2 ×Ω 3 � a∇(r i n ⊗ s i n ⊗ t i n ) � (r ⊗ s i n ⊗ t i n ) = [s i n T M s i n ][t i n T M t i n ]Br i n + � ρ1,2σ1σ2 2 [s i n T Cs i n ][t i n T M t i n ] + ρ1,3σ1σ3 2 [t i n T Ct i n ][s i n T M s i n ] � Dr i n + � ρ1,2σ1σ2 2 [t i n T M t i n ][s i n T Ds i n ] + ρ1,3σ1σ3 2 [t i n T Dt i n ][s i n T M s i n ] � Cr i n + � [t i n T M t i n ][s i n T Bs i n ] + ρ2,3σ2σ3 2 [t i n T Ct i n ][s i n T Ds i n ] + [t i n T Bt i n ][s i n T M s i n ] + ρ2,3σ2σ3 2 [t i n T Dt i n ][s i n T Cs i n ] � M r i n
where the matrices M, L, B, C, D are explicitly computable tridiagonal matrices of size N × N , with N the number of intervals in each direction. The computation of the components for these matrices boils down to one-dimensional integrals.

In this way, solving (4.38) with a fixed point procedure allows us to obtain for a fixed i such that 1 ≤ i ≤ N , the n-th term of the sum

� n k=1 r i k ⊗ s i k ⊗ t i k
which is an approximation of the solution at time t i = iΔt of the problem (4.12).

Numerical results

Testing the method against an analytical solution

In this part, we apply the PGD algorithm defined in (4.37) to solve the problem (4.12) with the following initial condition:

u(0, x 1 , . . . , x d ) = � K - d � i=1 x i (1 -x i ) � + (4.40)
for which the solution is analytically known.

Using the Feynman-Kac theorem (4.3) we get that the solution of the PDE (4.5) is given by

E � e -rT (K - � d i=1 S i T ) + �
, which is possible to calculate analytically in the Black-Scholes model. We

have:

E � e -rT (K - d � i=1 S i T ) + � = e -rT KP � K > d � i=1 S i T � -e -rT E   d � i=1 S i T 1 � K> � d i=1 S i T �   (4.41)
We get the quantity

P � K > � d i=1 S i T �
as follows:

P � K > d � i=1 S i T � = P � e � d i=1 X i T < K � d i=1 S i 0 � = P � Y < log � K � d i=1 S i 0 ��
where X i T = (r -

σ 2 i 2 )T + σ i W i T and Y = � d i=1 X i
T is a normal random variable with mean equal to

� d i=1 � r - σ 2 i 2 �
T and variance given by

� d i=1 � d j=1 ρ ij σ i σ j T .
Besides, we remark that:

E   d � i=1 S i T 1 � K> � d i=1 S i T �   = E   e Y 1 {e Y < K � d i=1 S i 0 }   d � i=1 S i 0
where the last term can be calculated analytically. We remark that the analytic solution (4.41) is not separable with respect to each coordinate.

We present in figure 4.1 a numerical example of the solution obtained with our algorithm and the analytic solution. In figure 4.2 we see the same surface but intersected with the plane x 1 = x 2 . Figure 4.3 shows the convergence curves, i.e, the L 2 relative error with respect to the number of iterations of the algorithm according to the dimension. We note that the number of iterations needed to obtain convergence increases as the dimension of the problem increases.

Results on the Black-Scholes equation

In this section, we show the results that we obtained applying the PGD method described in the previous section to the Black-Scholes equation. AEx=1/10 AEx=1/20 AEx=1/30 Monte Carlo Fig. 4.5. The approximated solution obtained with our method for the problem (4.5) with the initial condition (4.9) in a four-dimensional framework. For these results, we set Δx = 0.1, 0.2 and Δt = 0.01.

In terms of computational time, the PGD approach (4.37) is not competitive compared to Monte Carlo methods when one is interested in the price of only one value of the spot, but on the other side the curve of prices is obtained for any time t ∈ [0, T ] and any price spot.

Application as a variance reduction method

In this part, we show that we can use the solution obtained by the PGD method described above in order to find a control variable to reduce the variance when calculating the price an of option.

We can re-write the equations (4.1) and (4.2) which define the Black-Scholes model as follows:

dS i t S i t = rdt + σ i d � j=1 H i,j dW j t (4.42)
where W is a d-dimensional Brownian motion and the matrix H verifies HH t = Σ where Σ is a d × d matrix such that Σ i,j = 1 if j = i and Σ i,j = ρ ij otherwise.

We recall that the price of a basket put option is given by

E � e -rT f (S 1 T , S 2 T , . . . , S d T ) � where f (S 1 T , S 2 T , . . . , S d T ) = � K -1 d � d i=1 S i T � + .
Now, for the sake of simplicity, let us consider r = 0. Generalization to r � = 0 is straightforward.

Let us introduce the Kolmogorov equation:

     ∂ t P -1 2 A : ∇ 2 P = 0 P (0, x) = f (x) (4.43)
where

A = F H(F H) T and F is a diagonal matrix such that F i,i = σ i S i for i = 1, . . . , d. Notice that P (T, S 0 ) = E � f (S 1 T , S 2 T , . . . , S d T ) � .
Therefore, we have

P (0, S T ) -P (T, S 0 ) = � T 0 F H ∇ P (T -t, S t )dB t and thus, P (T, S 0 ) = f (S T ) - � T 0 F H ∇ P (T -t, S t )dB t (4.44)
The random variable Y = � T 0 F H ∇ P (Tt, S t )dB t has zero mean and is a perfect control variable since

Var [f (S T ) -Y ] = 0.
As we do not know the solution P , in practice, we calculate an approximation P ⋆ of P using the PGD algorithm presented in Section 4.1.5. Therefore, we obtain an approximated control variable

Y ⋆ = � T 0 F H ∇ P ⋆ (T -t, S t
)dB t and we can compute an approximation of P (T, S 0 ) by Monte Carlo, computing the following quantity:

E � f (S T ) - � T 0 F H ∇ P ⋆ (T -t, S t )dB t � .
We remark that this idea can be applied to any payoff function and that for a new value of S 0 we use the same approximation P ⋆ .

In Table 4.1 and 4.2 we present the performance of our variance reduction method compared with the variance obtained with the classical method, i.e. calculating directly E[f (S T )]. For two typical values of the correlation, we observe that the reduction of the variance is important, for example, up to a factor 6 in dimension 8.

Appendix: Formulas for the matrices used to solve the Black-Scholes partial differential equation

In this section, we detail the calculations of the terms appearing in the equation (4.38). As we already remarked, the multi-dimensional integrals are in fact the multiplication of 1-dimensional integrals.

Let us now analyze some terms that appear in the left hand side of the equation (4.38). Thus we have that:

� Ω 1 ×Ω 2 ×Ω 3 (A∇(r i n ⊗ s i n × t i n ))∇(r ⊗ s i n ⊗ t i n ) = 1 2 σ 2 1 � Ω 3 |t i n | 2 � Ω 2 |s i n | 2 � Ω 1 x 2 1 (1 -x1) 2 (∂x 1 r i n )(x1)∂x 1 (r(x1))dx1 + ρ12σ1σ2 2 � Ω 3 |t i n | 2 � Ω 2 x2(1 -x2)s i n (x2)∂x 2 (s i n )(x2)dx2 � Ω 1 x1(1 -x1)∂x 1 (r i n )(x1)rdx1 + ρ13σ1σ3 2 � Ω 2 |s i n | 2 � Ω 3 x3(1 -x3)t i n (x3)∂x 3 (t i n )(x3)dx3 � Ω 1 x1(1 -x1)∂x 1 (r i n )(x1)rdx1 + 1 2 σ 2 2 � Ω 3 |t i n | 2 � Ω 2 x 2 2 (1 -x2) 2 ∂x 2 (s i n )(x2)∂x 2 (s i n )(x2)dx2 � Ω 1 r i n (x1)r(x1)dx1 + ρ12σ1σ2 2 � Ω 3 |t i n | 2 � Ω 2 x2(1 -x2)s i n (x2)∂x 2 (s i n )(x2)dx2 � Ω 1 x1(1 -x1)r i n ∂x 1 (r)(x1)dx1 + 1 2 σ 2 3 � Ω 2 |s i n | 2 � Ω 3 x 2 3 (1 -x3) 2 ∂x 3 (t i n )(x3)∂x 3 (t i n )(x3)dx3 � Ω 1 r i n (x1)r(x1)dx1 + ρ13σ1σ3 2 � Ω 2 |s i n | 2 � Ω 3 x3(1 -x3)t i n (x3)∂x 3 (t i n )(x3)dx3 � Ω 1 x1(1 -x1)r i n ∂x 1 (r)(x1)dx1.
(4.45)

We recall that we consider a discretization in space given by Δx = 1 N and that is the same for each dimension. So, in order to calculate these last terms, we define the next matrices:

L i,j = � Ω x 2 (1 -x) 2 ∂ x (φ i )(x)∂ x (φ j )(x)dx (4.46) D i,j = � Ω x(1 -x)φ i (x)∂ x (φ j )(x)dx (4.47)
The matrix L is a tridiagonal matrix of size N + 1 × N + 1 given by:

Li,j =                                                                1 5 (Δx) 3 -1 2 (Δx) 2 + 1 3 (Δx), if i = j = 0 -1 5 (Δx) 3 + 1 2 (Δx) 2 -1 3 (Δx), if i = 0, j = 1 1 30 (Δx)(10 -15(Δx) + 6(Δx) 2 ), if i = j = N -1 30 (Δx)(10 -15(Δx) + 6(Δx) 2 ), if i = N, j = N -1 2 15 (Δx)(15(Δx) 2 i 4 + 30(Δx) 2 i 2 + 3(Δx) 2 -30(Δx)i 3 -30(Δx)i + 15i 2 + 5), if j = i - 1 30 (Δx) � 30(Δx) 2 i 4 -60(Δx) 2 i 3 + 60(Δx) 2 i 2 -30(Δx) 2 i + 6(Δx) 2 -60(Δx)i 3 + 90(Δx)i 2 -60(Δx)i + 15(Δx) + 30i 2 -30i + 10 � , if j = i -1 - 1 30 (Δx) � 30(Δx) 2 i 4 + 60(Δx) 2 i 3 + 60(Δx) 2 i 2 + 30(Δx) 2 i + 6(Δx) 2 -60(Δx)i 3 -90(Δx)i 2 -60(Δx)i -15(Δx) + 30i 2 + 30i + 10 � , if j = i + 1
The matrix D is also tridiagonal of size N + 1 × N + 1 and it is such that:

D i,j =                                                              1 12 (Δx)((Δx) -2), if i = j = 0 or i = N, j = N -1 -1 12 (Δx)((Δx) -2), if i = j = N or i = 0, j = 1 1 3 (Δx)(2i(Δx) -1), if j = i 1 12 (Δx)(6i 2 (Δx) -4i(Δx) + (Δx) -6i + 2), if j = i -1 -1 12 (Δx)(6i 2 (Δx) + 4i(Δx) + (Δx) -6i -2), if j = i + 1
Another term that appear in the left hand side of the equation (4.38) is the next one

� Ω 1 ×Ω 2 ×Ω 3 (a∇(r i n ⊗ s i n ⊗ t i n ))(r ⊗ s i n ⊗ t i n ) = = � Ω 3 |t i n (x 3 )| 2 dx 3 � Ω 2 |s i n (x 2 )| 2 dx 2 � Ω 1 (r + σ 2 1 x 1 -σ 2 1 )x 1 (1 -x 1 )∂ x 1 (r i n )(x 1 )r(x 1 )dx 1 + ρ 12 σ 1 σ 2 2 � Ω 3 |t i n (x 3 )| 2 dx 3 � Ω 2 (2x 2 -1)|s i n (x 2 )| 2 dx 2 � Ω 1 x 1 (1 -x 1 )∂ x 1 (r i n )(x 1 )r(x 1 )dx 1 + ρ 13 σ 1 σ 3 2 � Ω 2 |s i n (x 2 )| 2 dx 2 � Ω 3 (2x 3 -1)|t i n (x 3 )| 2 dx 3 � Ω 1 x 1 (1 -x 1 )∂ x 1 (r i n )(x 1 )r(x 1 )dx 1 + ρ 21 σ 1 σ 2 2 � Ω 3 |t i n (x 3 )| 2 dx 3 � Ω 2 x 2 (1 -x 2 )∂ x 2 (s i n )(x 2 )s i n (x 2 )dx 2 � Ω 1 (2x 1 -1)r i n (x 1 )r(x 1 )dx 1 + � Ω 3 |t i n (x 3 )| 2 dx 3 � Ω 2 (r + σ 2 2 x 2 -σ 2 2 )x 2 (1 -x 2 )∂ x 2 (s i n )(x 2 )s i n (x 2 )dx 2 � Ω 1 r i n (x 1 )r(x 1 )dx 1 + ρ 23 σ 2 σ 3 2 � Ω 3 (2x 3 -1)|t i n (x 3 )| 2 dx 3 � Ω 2 x 2 (1 -x 2 )∂ x 2 (s i n )(x 2 )s i n (x 2 )dx 2 � Ω 1 r i n (x 1 )r(x 1 )dx 1 + ρ 31 σ 1 σ 3 2 � Ω 2 |s i n (x 2 )| 2 dx 2 � Ω 3 x 3 (1 -x 3 )∂ x 3 (t i n )(x 3 )t i n (x 3 )dx 3 � Ω 1 (2x 1 -1)r i n (x 1 )r(x 1 )dx 1 + � Ω 2 |s i n (x 2 )| 2 dx 2 � Ω 3 (r + σ 2 3 x 3 -σ 2 3 )x 3 (1 -x 3 )∂ x 3 (t i n )(x 3 )t i n (x 3 )dx 3 � Ω 1 r i n (x 1 )r(x 1 )dx 1 ρ 23 σ 2 σ 3 2 � Ω 2 (2x 2 -1)|s i n (x 2 )| 2 dx 2 � Ω 3 x 3 (1 -x 3 )∂ x 3 (t i n )(x 3 )t i n (x 3 )dx 3 � Ω 1 r i n (x 1 )r(x 1 )dx 1 (4.48)
Therefore, we define the next matrices:

B ij = � Ω (r + σ 2 x -σ 2 )x(1 -x)∂ x (φ i )(x)φ j (x)dx (4.49)
Perspectives of the application of the Proper Generalized Decomposition method for option pricing

In this section, we present some perspectives on the first part of this manuscript: the problem of the American options and the use of non-continuous dynamics for the asset value.

Pricing using the characteristic function, application to Bermudan options

Before treating the pricing of an American option, it is important to remark that the PGD approach can be applied as well in the case of another type of option apart from European and American options and that can be considered as an intermediate point between them. This type of option is known as Bermudan option and the holder of one of these contracts can exercise the option only at certain days between the present time and the maturity. For example, for an option on a single asset, if we denote the payoff by the function φ, then the pricing function is such that

p(t + i , S) = max � p(t - i , S), φ(S)
� at each exercising time t i ∈ [0, T ] and satisfies the PDE of Black-Scholes (4.4) between the exercising times.

Using the same idea as in the Section 3.8, we can compute numerical integration on the Fourier domain. This method can readily be applied for solving problems under various asset price dynamics, for which the characteristic function (the Fourier transform of the probability density function) is available. This is the case for models from the class of regular affine processes [START_REF] Duffie | Affine processes and applications in finance[END_REF] which also includes the exponentially affine jump-diffusion class of [START_REF] Duffie | Transform analysis and asset pricing for affine jumpdiffusions[END_REF]. Many methods based on Fourier transform techniques are used on the one dimensional asset class of models [CMS99, LO08, KL09]. As a future work, an idea would be to extend these methods to the multi-dimensional framework.

Let us introduce T = t 1 , . . . , t M , t 0 ≤ t 1 ≤ . . . ≤ t M = T a set of exercise dates where we define the time between two exercise dates as δ i = t it i-1 . Applying the dynamic programming principle, the pricing formula for a Bermudan option is given by

p(t M , x) = φ(t M , x), p + (t m-1 , x) = e -rδ i � R d p(t m ; y)g(y|t m-1 , t m ; x)dy, (5.1)
p(t m-1 , x) = max � φ(t m-1 , x), p + (t m-1 , x)
� for m=M,. . . ,2 and

p(t 0 , x) = e -rδ 1 � R d p(t 1 ; y)g(y|t 0 , t 1 ; x)dy
Here, the probability density function of y = X x,t t under the risk-neutral measure is denoted g(y|t, t, x). In this case, y = log

� St m K � , p(t, x
) is the value of the option, p + (t, x) is the continuation value and φ(t, x) is the payoff.

Considering a multi-dimensional truncated domain of integration to proceed numerically, we obtain that the payoff is L 2 -integrable. Mathematically, we take the function φ such that

φ(t m , x) = φ(t m , x)1 x∈Ω , 1 ≤ m ≤ M. (5.2)
where Ω is a bounded subset of R d .

Using the approximation (5.2), we can compute the Fourier transform of (5.1)

F � p + (t m-1 , .) � (ξ) = e -rδm � R 2 ×R 2 p(y, t m )g(y|t m-1 , t m , x)e ixξ dydx
Assuming that the probability density function comes from an independent increment process (for example a Lévy process), that is

g(y|t m-1 , t m , x) = g(y -x|t m-1 , t m , 0)
Then, it holds

F � p + (t m-1 , .) � (ξ) = e -rδm F (p(t m , .)) (ξ)Φ(t m-1 , t m ; -ξ) (5.3) where Φ(t, t, ξ) = � R d f (z|t, t, 0)e izξ dz.
In conclusion, we can propose the following steps to compute the price of the Bermudan option:

1. Compute an approximation of p(t m , .) as a sum of tensor products using the PGD approach (2.17) to obtain the function p as follows:

p(., t m ) = N � n=0 r 1 n ⊗ . . . ⊗ r d n 2.
Apply the Fubini's rule to get

F (p(t m , .)) = N � n=0 F(r 1 n ) ⊗ . . . ⊗ F(r d n )
3. Convolve by density function using (5.3)

F � p+ (t m-1 , .) � (ξ) = e -rδm F (p(t m , .)) (ξ)Φ(ξ).

Compute an approximation of F

� p+ (t m-1 , .) � as a sum of tensor products by the PGD method (2.17) and calculate the inverse Fourier transform using the Fubini's rule.

The problem of the American options

In this section we propose an application of the PGD method for solving the problem of the American options. This type of options can be exercised at any time up to the maturity, consequently, the price of an American option with payoff φ and maturity T is given by

p(t, x) = sup τ ∈T [t,T ] E � e - � τ t rds φ(S t,x τ ) � ,
for stopping times τ between t and T , for t ∈ [0, T ] and x ≥ 0, where T [t,T ] denotes the set of stopping times τ of the filtration F τ .

It is possible to show that the pricing of an American option amounts to solving (see [START_REF] Achdou | Computational methods for option pricing[END_REF]):

     max {∂ t u + Lu, u -φ} = 0 in [0, T ] × R d + u(0, .) = φ in R d + (5.4)
where L is defined by (1.26) and the problem (5.4) is equivalent to the following problem, called the obstacle problem

                     Lu - ∂u ∂t ≤ 0, in R T u ≥ φ, in R T (u -φ) � Lu - ∂u ∂t � = 0, in R T u(0, x) = φ(0, x), x ∈ R d (5.5)
To apply the PGD approach to the problem (5.4), we propose to use the idea presented in [START_REF] Cancès | Convergence of a greedy algorithm for highdimensional convex nonlinear problems[END_REF] and that allows to apply the PGD method to the obstacle problem (5.5) by penalizing the constraints. In order to use this idea we can discretize in time, obtaining:

     max { u n+1 -u n Δt + Lu n+1 , u n+1 -φ} = 0 in [0, T ] × R d + u(0, .) = φ in R d +
Finally, we propose to penalize the constraints:

u n+1 -u n Δt + L S u n+1 + L A u n + 1 ǫ (u n+1 -φ) + = 0 (5.6)
Again, the problem in u n+1 is symmetric and thus can be rewritten as a minimization problem needed to apply the PGD method.

There exists theoretical results that indicate that the approach (5.6) is reasonable (see [START_REF] Cancès | Convergence of a greedy algorithm for highdimensional convex nonlinear problems[END_REF]).

Introduction

Financial markets are places where buyers and sellers can exchange different types of assets. One of the goals of a financial market is to allow companies to fund themselves through different types of financial products. This implies that an important part of the economy is influenced by the financial markets. The understanding of how these financial markets work is therefore very important.

As a consequence of the technological innovations and regulatory changes, the structure of the financial markets has evolved in the past years. Initiatives such as the MiFID in Europe and the Regulation National Markets System in United States have appeared to deregulate markets and then to improve the service given to the investors by stimulating the competition between the markets. The deregulation has been one possible reason for which liquidity risk and market microstructure have become a hot topic in mathematical finance in the past years.

Market microstructure is the study of how the markets work. Thus, this branch of finance is interested in understanding the details of the trading mechanisms. Among the topics treated by the market microstructure we have the price formation and price discovery, the market structure and design issues, and the information and disclosure.

The importance of the market microstructure can also be seen from the common assumption of frictionless markets, that means markets without transaction costs. This hypothesis is considered in many important models in mathematical finance such as the well-known Black-Scholes model. Because of the assumption, the price process does not depend on the trading strategy used by the agents. As the time scale becomes smaller and smaller, this assumption is less coherent.

Liquidity risk is a decisive concept in market microstructure. This risk takes into account finding the counterpart for the buy or sell order that the trader needs to execute. Liquidity is therefore a key to knowing how prices will change after the action of the agents in the markets through some measures of the liquidity of the asset such as the bid-ask spread or the market depth.

Markets are also supposed to be perfectly liquid in classical models of mathematical finance, an assumption that guarantees the perfect hedging as in the case of the Black-Scholes model for example.

In practice, however, this is not true; trading large volumes of orders shifts the price of the asset in the opposite direction to the one most beneficial to the investor. As a consequence, the price impact can be seen as the difference between the realized price and the price before the order was executed.

We cannot take further the discussion on market impact models without introducing the concept of an order, which constitutes an instruction from customers to brokers to buy or sell on the markets.

In the financial markets, there exist different types of orders, the more standard ones being the market orders and the limit orders. On the one hand a market order allows the client to execute his order immediately and to get the best price available on the market. On the other hand, a limit order gives to the investor the possibility of buying or selling a share at a specified price. When the execution of the order is greater than the price for the trader, he will generally use a market order. A limit order might not be able to be executed at all but it would allow the investors to have control over the price that they might pay for executing their orders.

A database of limit orders constitutes a limit order book. In other words, investors place orders to buy or sell a given quantity of stock in the limit order book. If a market order arrives in the limit order book, then it is matched with the best current price proposed on the market and if a limit order is placed in the limit order book, this will be stored waiting for a market order that would execute it. Figure 6.1 illustrates a limit order book for specific shares. Orders can only be placed on a price grid and at each moment in time, the number of waiting buy (or sell) orders is stored for each price.

For a given price, orders are executed according to the FIFO rule as soon as two orders match. As we can observe, the structure of Limit Order Books (LOB) is very complex, so an exhaustive modeling of its dynamics would not lead, for example, to draw quantitative conclusions on an optimal trading strategy. One has therefore to propose models that can grasp important features of the LOB structure but that allow to find analytical results.

Quotation rules are changing and, in general, more information is now available. In particular, it is possible to know at any given time the number of awaiting orders for certain stock and to obtain a record of all past transactions. A natural question arises: how to use at the best this information to execute buy or sell orders optimally? In other words, what is the behavior of traders who want to minimize their trading cost?

Given that the size of the order can be large, the trader needs to find an optimal strategy which consists in using the resilience of the markets to help split this large order into smaller orders. This resilience of markets can be explained through the supply and demand of the assets. Hence, by splitting the large order, the trader will decrease the impact of his trade on the price of the asset. But, if the investor waits, he will increase his market risk. In other words, the market impact forces slow trading but the market risk forces quick trading. The idea is then to find a good trade-off between liquidity and the market risk.

It has been reported, for example in [START_REF] Alfonsi | Optimal execution strategies in limit order books with general shape functions[END_REF], that optimal execution is a recurrent problem for practitioners because traders liquidate about twenty percent of the daily volume of shares. More dangerous practical situations can also exist as an example of application of the optimal execution, for instance, the well-known case of Jérôme Kerviel at the Société Générale. Here the bank had to liquidate his large speculative positions. Another example of this type is when a financial institution holds a large quantity of government bonds and as the default probability of that country increases, the value of these assets quickly decreases. The institution therefore would be interested in liquidating this portfolio as quickly as possible. It is natural that in selling everything at the outset is not optimal because, given the limited liquidity of the market, this financial institution would have to sell its bonds very cheaply.

It is possible to distinguish three different time scales for the trading activity. Asset management activities generate tasks like the hedging of positions that can be set in long-scale time periods, for example, days or weeks. These activities imply that it is necessary to manage positions and to execute orders on the market in a matter of minutes. The last time scale for trading is the so-called high-frequency trading which is performed in intervals of time from 10 -6 to 1 seconds. The market impact models that we will study in this work apply to the intermediate time scale of trading, that goes typically from a minute to some hours.

In Section 6.2 we will define the optimal execution problem and we will analyze some market impact models that the literature has proposed in order to solve it. In the same section we will present the main results of these models and the connections and differences between them. We will also study the concept of price manipulation and the existence of optimal strategies for the optimal execution problem.

Market impact models

The aim of this Section is to compare the market impact models proposed by the literature and to establish links between them, emphasizing the advantages and the drawbacks of each.

Definition of the optimal execution problem

The problem that we will study in this manuscript is the optimal liquidation of a portfolio with � shares by a large trader who can place orders over a period of time [0, T ]. We consider that � > 0 (resp. � < 0) corresponds to a selling (resp. buying) program. By large investor, we understand a trader who executes a large volume of orders and therefore is able to modify the price of the exchanged asset. In practice, regulators define the concept of large trader in order to supervise markets and to avoid manipulation and fraud. In the literature, these large traders are differentiated from the normal traders (also called noise traders) who, on average, do not modify the price of the asset. In this work, we will analyze the case of only one large trader. See [START_REF] Brunnermeier | Predatory trading[END_REF] and [START_REF] Carlin | Episodic liquidity crises: Cooperative and predatory trading[END_REF] for frameworks that consider more than one trader in competition with each other.

In order to find a solution for this optimal liquidation problem, we need to analyze the impact of the actions of the agents on the markets, that is, to model the market impact. This impact is closely related to the liquidity in financial markets described by the market impact models. We could think that market impact depends on many variables like bid-ask spread or market capitalization; nevertheless, the market impact models that we will study are related to the shift in price and to the exchanged volume.

For the sake of clarity, we would like to introduce here a general framework for studying this optimal liquidation problem. First, let us assume the existence of four price processes: (A 0 t , t ≥ 0), (A t , t ≥ 0), (B 0 t , t ≥ 0) and (B t , t ≥ 0) on a given filtered probability space (Ω, (F t ), F, P). The processes (A 0 t , t ≥ 0) and (B 0 t , t ≥ 0) represent respectively the best ask price and the best bid price of the asset unaffected by the large trader. The processes (A t , t ≥ 0) and (B t , t ≥ 0) are the actual best ask price and best bid price where the orders of the large investor are taken into account.

To simplify, most of the models proposed in the literature neglect the bid-ask spread and thus consider only two processes: (S 0 t , t ≥ 0) and (S t , t ≥ 0) which represent respectively the price when the large trader is inactive and the price when the orders of the large investor have an influence on the limit order book. It is important to note that for liquid assets the size of the bid-ask spread is usually one tick as has been empirically shown, see Cont and De Larrard in [START_REF] Cont | Price dynamics in a Markovian limit order market[END_REF] and the references therein. Thus, in practice, a zero bid-ask spread for liquid assets is not far from reality in the time scale where our model is set. As the unaffected price process is determined by the actions of the noisy traders, it is usually supposed to be a martingale. Other reasons for this consideration are that the time period of trading is normally short and that including a nonzero drift would lead to profitable strategies that have to be differentiated from price manipulation strategies.

Even if in practice the problem of the optimal execution of orders make sense in the discrete-time framework, it is interesting to analyze its outcomes in both the continuous and discrete time cases. For example, an important topic to study is whether the optimal strategies are stable when we increase the number of dates for trading.

For discrete-time strategies, we assume that at most N + 1 market orders can be placed by the large trader. In this case, an admissible strategy is given by an increasing sequence τ 0 = 0 ≤ . . . ≤ τ N = T of stopping times and random variables ξ 0 , . . . , ξ N , where ξ i is the size of the order placed at time τ i , (ξ i < 0 corresponds to a sell order, and ξ i > 0 holds for a buy order) such that

• � + � N i=0 ξ i = 0, i.e.

the investor liquidates his portfolio of � shares,

• ξ i is F τ i -measurable, and

• ∃M ∈ R, ∀ 0 ≤ i ≤ N, ξ i ≥ M , a.s.
This third hypothesis will be needed for technical reasons and can be seen as the fact that the investor cannot propose (or take out) an infinite amount of liquidity on the markets.

In addition, if we analyze continuous-time strategies, we can define an admissible strategy as a stochastic process (X t ) t≥0 such that

• X 0 = � and X T + = 0,
• X is F t -adapted and left-continuous, and

• the function t ∈ [0, T +] � → X t has finite and a.s. bounded total variation. This process (X t ) t≥0 represents the number of shares that remain to liquidate at time t. We can observe that in the discrete-time strategy case, we have X t = � + � N i=0 ξ i 1 τ i <t and we can deduce the assumptions on the continuous case from the hypothesis of the discrete case.

The question about the objective of the traders which determines the choice of the criterion to state the problem of optimal execution is not closed. The trader could be interested only in minimizing the expected execution cost or he could take into account the variance of his strategy as well, arguing that the expected execution cost criterion misses the volatility risk.

There exist three types of market impacts that the literature considers according to the time that they shift the price of the underlying asset: the permanent impact is a permanent change in the price such as an impact due to a new information on fundamentals of the asset; the instantaneous or temporary impact only influences the actual order; and the transient impact modifies the price after the placement of an order but decays over time. We will see that the permanent and temporary impacts are first introduced in the literature leading to a first family of models. The consideration of the transient impact comes later to produce a second type of model.

First family of models (immediate and permanent price impact)

In the first works mentioned in the literature for treating the optimal execution problem, the impact created by the large trader was incorporated directly into the dynamic of the asset exogenously.

In these models, the price impact depends on the size of the order and on the speed of liquidation of the position. We can differentiate these models according to the time framework: discrete-time and continuoustime models.

Discrete-time models

Among these models, Bertsimas and Lo [START_REF] Bertsimas | Optimal control of execution costs[END_REF] and Almgren and Chriss [AC00] studied first the problem of the optimal execution. Precisely, they consider the following discrete-time model

S tn = S 0 tn + γ n � i=0 ξ i , n = 0, . . . , N, (6.1)
where γ > 0 and in order to take into account the impact on the price, the price process S tn consists of an arithmetic random walk and a linear function of the order size. The time schedule of trading is considered to be a uniform discretization of the period [0, T ], so t n = nT N . Bertsimas and Lo consider in [START_REF] Bertsimas | Optimal control of execution costs[END_REF] that the aim of the large trader is to minimize the average cost of his trading program. Hence the goal is to find ξ 0 , . . . , ξ N such that min ξ 0 ,...,ξ N , such that: �+

� N i=0 ξ i =0 E � C BL (ξ) � , (6.2)
where

C BL (ξ) := N � i=0 ξ i S t i . (6.3)
As we already mentioned, the strategy ξ naive that consists in selling the entire quantity � allows to eliminate the future risk on the value of the asset but its cost can be very high. Precisely, in this case, we have the following cost for this strategy

C BL (ξ naive ) = -S 0 0 � + γ� 2
and the variance of this strategy is zero.

On the other hand, the strategy that is optimal in the framework of [START_REF] Bertsimas | Optimal control of execution costs[END_REF] and that consists of a constant rate of trading given by ξ ⋆,BL i = -� N , minimizes the expected cost given by (6.3) but its variance can be large. The cost of this strategy is given by

E � N � k=0 -� N S t k � = -�S 0 0 + (N + 1)γ� 2 2N
and its variance is equal to

Var � N � k=0 � N S t k � = � 2 N 2 E � N � k=0 {2(N -k) + 1} (S 0 t k ) 2 � -� 2 (S 0 0 ) 2
The differences between these strategies ξ ⋆,BL and ξ naive illustrate the fact that for this type of model where the price impact is only permanent and temporary, the optimal strategy has to be a trade-off between the cost of the strategy and its variance.

Removing the assumption that the investor is not risk averse and based on a similar model for the price asset, in [AC00] Almgren and Chriss use a mean-variance risk criterion for the investor setting a level of risk aversion of the agent.

Thus, the goal of Almgren and Chriss in [START_REF] Almgren | Optimal execution of portfolio transactions[END_REF] is to find the optimal strategy for the problem

E � C AL (ξ) � + λVar � C AL (ξ) � (6.4)
for different values of the risk aversion parameter λ and C AL is the cost in the Almgren and Chriss framework. Indeed, they show that for each value of λ ≥ 0, there exists a unique optimal strategy that minimizes the criterion (6.4).

Let us consider a uniform time grid, that means t i = iT N for i = 0, . . . , N and δt = t it i-1 = T N . In [START_REF] Almgren | Optimal execution of portfolio transactions[END_REF], Almgren and Chriss obtain the solution for the optimal execution problem in a discrete case. Precisely, as in [START_REF] Bertsimas | Optimal control of execution costs[END_REF], the permanent and temporary impact appear directly in the dynamic of the asset

S t k = S t k-1 + σ √ δtχ k -δtg � ξ k δt � , (6.5)
where σ is the volatility of the asset, ξ k the size of the order executed at time t k and (χ k ) k=1,..,n is a sequence of i.i.d. random variables with zero mean and unit variance. The function g represents the permanent impact and, in the equation (6.5), this impact is considered in the average rate of trading

ξ k δt in the interval from t k-1 to t k .
In this model, the temporary impact is taken into account through the function h appearing in the price St k obtained by the trader in the market at the time t k

St k := S t k-1 -h � ξ k δt � .
Using that C AC := � N i=0 ξ i St i , Almgren and Chriss in [START_REF] Almgren | Optimal execution of portfolio transactions[END_REF] find an explicit optimal strategy in the case of a linear permanent impact function g and of a temporary impact function h given by

h � ξ k δt � = ǫsgn(ξ k ) + η ξ k δt
for some positive constants ǫ, η.

For a parameter of risk aversion of the trader λ > 0, this optimal strategy is determined as follows:

X ⋆,AL k = sinh(κ(T -t k )) sinh(κT ) �, k = 0, . . . , N where κ ∼ � λσ 2 η + O(δt), δt → 0.
In this case, this model allows an easy implementation and to obtain some insights about the parameters. We note also that the case λ → 0 in (4.4) gives

X ⋆ = � (T -t j )
T which is the optimal strategy already found by Bertsimas and Lo in [START_REF] Bertsimas | Optimal control of execution costs[END_REF]. We recall that the process X k denotes the amount of shares to detain at time t k but not the size of the order executed by the trader.

A disadvantage of discrete-time models as [BL98, AC00] is that the time trades are fixed in advance of the trading which is clearly not realistic.

Continuous-time models

The Almgren and Chriss model is also studied in a continuous-time framework by Almgren in [START_REF] Almgren | Optimal execution with nonlinear impact functions and trading-enhanced risk[END_REF]. He obtains analytic optimal strategies for a temporary impact given by a power-law function h( Ẋt ) = η Ẋk t where k > 0 and for a linear permanent impact given by g( Ẋt ) = γ Ẋt . We remark that Ẋt represents the speed of execution of the asset S t .

In this same continuous-time framework, let us assume that the permanent impact and the temporary impact are linear functions of X t -� and Ẋt respectively. We note that the quantity X t -� represents the amount of shares already executed in the market by the large trader. This implies that the price S t is given as follows:

S t = S 0 t + γ(X t -�) + η Ẋt (6.6)
Here, the parameter γ describes the permanent impact of the orders and η the temporary impact.

We can mention that a linear market impact of the orders is not satisfactory as shows the empirical study [START_REF] Almgren | Direct estimation of equity market impact[END_REF] by Almgren et al. For more details, see [START_REF] Almgren | Optimal execution with nonlinear impact functions and trading-enhanced risk[END_REF] and the references therein. We recall that the simplicity to handle the obtained expressions and to get closed formulas is the main reason why a linear impact is used in the literature.

We note that, if we sell the asset, the price has to decrease, so we impose γ ≥ 0, η ≥ 0, � > 0 and X T = 0. Therefore, we can define the cost as follows

C A (X t ) := E � � T 0 S t dX t � , (6.7)
that can be further written as:

E � � T 0 S t dX t � = -S 0 0 � + γE � � T 0 X t dX t � -γ�E � � T 0 dX t � + ηE � � T 0 Ẋ2 t dt � = -S 0 0 � + γ 2 � 2 + ηE � � T 0 Ẋ2 t dt � . (6.8)
Thus, we can deduce that if η = 0 (i.e. no temporary impact is considered) then the cost is independent of the strategy, and any strategy is optimal. We remark that, in discrete-time, the same conclusion can be obtained.

Otherwise, when η > 0, as we minimize the cost (6.7), we can use the Jensen inequality 1

T � T 0 Ẋ2 t dt ≥ � 1 T � T 0 Ẋt dt � 2
, (6.9)

to deduce that Ẋt = -� T (6.10) because (6.9) is an equality when (6.10) is verified.

We observe that the first family of models presents the disadvantage that the price impact functions are deterministic functions which depend only on the quantity exchanged and do not take into account the dynamic of the limit order book, neglecting the effect of the trade over the supply and demand in the limit order book. It is intuitive that when an investor wants to place orders during a period of time, the response of the limit order book to the previous exchanges has to be one of the most important points to analyze. This is the motivation for the second family of models.

Second family of models (transient price impact)

Two new aspects appear in the model considered by Obizhaeva and Wang in [START_REF] Obizhaeva | Optimal trading strategy and supply/demand dynamics[END_REF] in order to consider the limitations of the first family of models. To be more specific, they first propose a model for the dynamic of the limit order book from which they can deduce the market impact of the large trader, instead of considering that the price impact is given as a fundamental as in [START_REF] Bertsimas | Optimal control of execution costs[END_REF][START_REF] Almgren | Optimal execution of portfolio transactions[END_REF].

They also introduce the concept of transient impact which means that the price shift remains after the order is placed but it decays because of the resilience of the limit order book. Hence, the idea of transient impact naturally appears when the response of the limit order book is taken into account.

In [START_REF] Obizhaeva | Optimal trading strategy and supply/demand dynamics[END_REF], the limit order book is represented by a constant distribution of shares to sell and to buy, respectively: the ask and bid part of this limit order book. This is called a one side model because the trader is not allowed to sell when his goal is to buy � shares; or conversely, he is not allowed to buy when his purpose is to sell. When a sell market order arrives, it takes away the liquidity placed at the left of the best bid and affects the price linearly with respect to the volume exchanged (the symmetric situation happens when a buy market order arrives). The limit order book will recover from the impact of the sell market order through resilience. On the other hand, when the large trader is inactive, the best bid and the best ask move according to the action of the noise traders, which add new orders in between the bid-ask spread. The price impact created by this mechanism is neither temporary nor permanent, but transient. Considering a linear permanent impact in this model is possible and it does not change the optimal strategy. Figures 6.2, 6.3, 6.4 and 6.5 illustrate the idea of the model. A sell market order arrives to the limit order book and it is matched with the best prices offered in the bid part of the limit order book.

We can say that the resilience of the market was taken into account implicitly in the previous researches [START_REF] Bertsimas | Optimal control of execution costs[END_REF] and [START_REF] Almgren | Optimal execution of portfolio transactions[END_REF] when treating temporary impact with instantaneous recovery of the price after the execution of the order. In other words, in these models, the resilience is considered infinite. Meanwhile, the permanent price impact corresponds to a zero resilience case for the limit order book. We also see that the resilience reflects the fact that there are new orders appearing in Fig. 6.4. Limit order book of an asset in the model introduced by Obizhaeva and Wang in [START_REF] Obizhaeva | Optimal trading strategy and supply/demand dynamics[END_REF]. Bt+ is the new best bid price after the execution of the sell market order that arrives in Figure 6.3 and a new bid-ask spread is created. the bid-ask spread and not in other places like the depth of the limit order book. In other words, we remark that the density of the limit order book does not change in the depth of the limit order book. We therefore deduce that the optimal strategy in the type of model proposed by [START_REF] Obizhaeva | Optimal trading strategy and supply/demand dynamics[END_REF] has to be a trade-off between the recovery effect on the price (that is the resilience of the limit order book) and the time constraint to liquidate the portfolio. The effect of the resilience is detected in such empirical studies as [BHS95, BGPW04, BP03] and [START_REF] Rosenow | Order book approach to price impact[END_REF]. Consequently, [START_REF] Obizhaeva | Optimal trading strategy and supply/demand dynamics[END_REF] gives new types of optimal strategies, that are combinations of discrete and continuous trades, and that are unlike the optimal strategies in [START_REF] Bertsimas | Optimal control of execution costs[END_REF] and [START_REF] Almgren | Optimal execution of portfolio transactions[END_REF] that consist only of continuous trades. Figure 6.6 compares the different actions of the traders according to the different types of models.

There is an important assumption in the model proposed by Obizhaeva and Wang in [START_REF] Obizhaeva | Optimal trading strategy and supply/demand dynamics[END_REF],

that is, the quantity of shares offered on the market is constant for all prices S t . This is what is called a block-shaped limit order book. The fact that in practice there are no block-shaped limit order books, only non-constant limit order books, has been shown in empirical studies as [BGPW04, BP03, RW05, BHS95]. The constant form of the limit order book implies that the price impacts considered in this Fig. 6.6. Comparison between the optimal strategies obtained in [START_REF] Obizhaeva | Optimal trading strategy and supply/demand dynamics[END_REF] and [START_REF] Almgren | Optimal execution of portfolio transactions[END_REF]. The broken line represents the optimal strategy in the framework introduced by Obizhaeva and Wang in [START_REF] Obizhaeva | Optimal trading strategy and supply/demand dynamics[END_REF] and the continuous line is the optimal strategy deduced by Almgren and Chriss in [START_REF] Almgren | Optimal execution of portfolio transactions[END_REF].

framework are linear with respect to the volume of executed orders. However, the linearity in the impact on the traded volume is not true in reality; the impact is empirically proven to be non-linear in [START_REF] Almgren | Optimal execution with nonlinear impact functions and trading-enhanced risk[END_REF][START_REF] Almgren | Direct estimation of equity market impact[END_REF].

Let us explain this further. If we want to estimate the market impact generated by the execution of an order of size ξ t according to the model presented in [START_REF] Obizhaeva | Optimal trading strategy and supply/demand dynamics[END_REF], in other words, the change of price from S t to S t+ , we can consider the following equation:

� S t+ St qdx = ξ t (6.11)
given that the distribution of shares offered on the market is a constant q with respect to the price.

So, (6.11) implies that the price impact given by S t+ -S t is linear with respect to the volume traded

ξ t because S t+ -S t = ξ t q .
We note that the optimal strategies that result from all the models discussed above [BL98, AC00, OW05] are static (or deterministic). This means that these optimal strategies can be determined in advance to the trading and that they are independent of the martingale unaffected price process. To observe this, let us consider the cost of executing a market order of size ξ t π t (ξ t ) :=

� St+ St (S 0 t + x)qdx = S 0 t ξ t + q � St+ St xdx
Consequently, the accumulated cost of an admissible strategy ξ is

N � i=0 π t i (ξ i ) = N � i=0 S 0 t i ξ i + q N � i=0 � S t i + St i xf (x)dx (6.12)
By considering the process X t , we can re-write the first sum in the right hand of (6.12) side as follows

N � i=0 S 0 t i ξ i = N � i=0 S 0 t i (X t i+1 -X t i ) = -�S 0 0 - N � i=1 X tn (S 0 tn -S 0 t n-1 ) (6.13)
Given that the strategy ξ is admissible, the process X tn is F t n-1 -measurable. We remark that X t is also a bounded process. Therefore using the martingale property of the unaffected price process S 0 , the expectation of (6.13) is equal to -S 0 �. Moreover, we note that the difference S t+ -S t does not depend on the martingale process S 0 t and that this difference is deterministically determined when the values ξ 0 (w), ξ 1 (w), . . . , ξ N (w) are given. Hence, there exists a deterministic function

C (i) : R N +1 � → R such that N � i=0 � S t i + St xf (x)dx = C (i) (ξ 0 , . . . , ξ N )
Consequently, we obtain that

C(ξ) = -S 0 � + E � C (i) (ξ 0 , . . . , ξ N ) � ,
which implies that the optimal strategy do not react to the changes in the price process.

We observe that the second family of models still does not consider important features of the market and of the traders' behavior. In the next section, we mention some works that take into account some of these features.

Other models

We remark that in all the previous models, the large investor can only place market orders, but in the markets, investors have a large variety of types of orders. See, for instance, the work of Gueant, Lehalle and Fernandez [START_REF] Fernandez | Optimal portfolio liquidation with limit orders[END_REF] and Avellaneda and Stoikov [START_REF] Avellaneda | High-frequency trading in a limit order book[END_REF] for a large trader who can use limit orders in his strategies.

A different type of modelling is proposed by Cont and De Larrard in [START_REF] Cont | Price dynamics in a Markovian limit order market[END_REF]. Using a Markovian queueing model of the limit order book that describes essentially what is happening at the bid and ask prices, they deduce some quantities of interest such as the distribution of the duration between price changes and the probability of an upward movement in the price, conditional on the state of the order book. Nevertheless, the problem of the optimal execution is not treated.

The problem of optimal liquidation has been studied as well by Schied and Schöneborn in [START_REF] Schied | Risk aversion and the dynamics of optimal liquidation strategies in illiquid markets[END_REF].

Their model is based on a continuous version of the model used in [START_REF] Almgren | Optimal execution of portfolio transactions[END_REF] with T = ∞. Considering temporary and permanent impact that are linear and using a stochastic control approach, they also analyze the adaptive liquidation strategies that react to the price changes, which are unlike the static strategies given by the previous models. Schied and Schöneborn state that, in general, these adaptive liquidation strategies give higher expected utility than the static strategies only in the case of investors who have non-constant risk aversion. These adaptive strategies were also studied by Almgren in [START_REF] Almgren | Adaptive arrival price[END_REF].

We can go deeper in the explanation of the differences between the models with adaptive and static strategies by trying to interpret the goal of each type model. Thus, in [START_REF] Obizhaeva | Optimal trading strategy and supply/demand dynamics[END_REF] the model describes the mechanism of the limit order book dynamic from an average point of view. In practice, the limit order book is a discrete function of prices which are determined by the size of the tick. The continuous distribution of shares represented by the shape of the limit order book is then an assumption of what is happening in average on the markets. As a consequence of this fact and that the associated time scale is wider, obtaining static strategies in the framework introduced in [OW05] is something we could expect.

Another important model is given by Gatheral in [START_REF]No-dynamic-arbitrage and market impact[END_REF] who studies the concept of transient impact by introducing a decay factor. Gatheral deduces a relationship between the market impact function and its decay, assuming the next model for the evolution of market prices is

S t := S 0 + � t 0 h( ẋs )G(t -s)ds + � t 0 σdW s (6.14)
where ẋs is the rate of trading at time s < t, h( ẋs ) corresponds to the temporary impact of the activity of the large investor at time s, the function G(ts) represents the decay factor and W s is a Brownian motion. This functions h(.) and G(.) should be considered as representing the different market conditions in an average sense. We note that, for instance, in the framework of Almgren and Chriss given by [START_REF] Almgren | Optimal execution of portfolio transactions[END_REF], G(t-s) = δ(t-s) which means that the market impact decays instantaneously.

In the case of [START_REF] Obizhaeva | Optimal trading strategy and supply/demand dynamics[END_REF], we have G(t) = e -ρt with ρ > 0 and h(.) is a linear function of the rate of trading.

A first extension of the second family of models

The work of [START_REF] Alfonsi | Optimal execution strategies in limit order books with general shape functions[END_REF] extends the results in [START_REF] Obizhaeva | Optimal trading strategy and supply/demand dynamics[END_REF] by considering general shapes for the limit order book. In that paper, Alfonsi, Fruth and Schied assume that the process (S 0 t ) t≥0 is a rightcontinuous martingale on the filtered probability space (Ω, (F t ), F, P) such that S 0 0 = S 0 Pa.s.. This unaffected price is not influenced by the large investor and so it is determined by the noise traders. The martingale assumption for the unaffected process (S 0 t , t ≥ 0) is also used in [BL98, AC00] and [START_REF] Obizhaeva | Optimal trading strategy and supply/demand dynamics[END_REF]. One of the reason that explains its use, is that as we consider short trading horizons, the drift effect can be neglected. As it is mentioned in [START_REF] Klöck | Price manipulation in a market impact model with dark pool[END_REF], a non-zero drift can create profitable round trips that would have to be differentiated from the ones defined by Huberman and Stanzl in [START_REF] Huberman | Price manipulation and quasi-arbitrage[END_REF].

Moreover, the aim of the model proposed in [START_REF] Alfonsi | Optimal execution strategies in limit order books with general shape functions[END_REF] is to describe the dynamics of the price process (S t ) t≥0 affected by the action of the large trader. This dynamic comes from the reaction of the limit order book and the dynamic of the unaffected price process. In order to describe the response of the limit order book, they introduce two processes: a volume impact process E t that represents the impact of the large traders on the limit order book in terms of volume and a price impact process D t that is the price impact created by the action of the large trader. Thus, it is possible now to define the actual price process S as follows

S t = S 0 t + D t . (6.15)
Therefore, if at time t the trader places a market order of size ξ t , the volume impact of the large investor changes from E t to

E t+ := E t + ξ t (6.16)
On the other hand, if the large trader is inactive, the process (E t , t ≥ 0) decays exponentially as follows

dE t = -ρ t E t dt (6.17)
We consider that the rate at which E decreases is the deterministic and time dependent parameter t � → ρ t called the resilience. The equations (6.16) and (6.17) define completely the dynamics of the volume impact process E and this framework is named the model with volume impact reversion.

The question is now, how to relate the volume impact and the price impact created by the order placed by the trader? In order to do that, they introduce a continuous distribution of bid and ask orders out of the unaffected price S 0 t . To represent this distribution, Alfonsi, Fruth and Schied consider a continuous function f : R � → [0, ∞) verifying f (x) > 0 for a.e.x. This function is called the shape function of the limit order book. Thus, the number of shares offered between the prices S 0 t + x and S 0 t + x + dx is equal to f (x)dx. Therefore, there is a relation that links the volume impact E t with the price impact D t , given by the following equation

� Dt 0 f (x)dx = E t .
(6.18) Figure 6.8 shows the relation (6.18) between the volume impact E t and the price impact D t generated when a large trader executes an order on the market.

Fig. 6.7. The shape function f of the limit order book in the model [START_REF] Alfonsi | Optimal execution strategies in limit order books with general shape functions[END_REF]. The trader executes an order of size E0+ and then moves the price from S0 to S0+.

Let us define the antiderivative of f ,

F (y) := � y 0 f (x)dx, y ∈ R,
so we can observe that the connection between the volume impact process E and price impact process D can be stated as

E t = F (D t ) and D t = F -1 (E t ) (6.19)
We note that F is invertible because it is a strictly increasing function given the assumption f (x) > 0 for a.e. x.

We remark that if at time t ≥ 0 the large investor places an order of size ξ t , the actual price moves from S t to

S t+ := S 0 t + D t+ = S 0 t + F -1 (E t + ξ t )
We can conclude that the price impact D t+ -D t is a non-linear function of the order size ξ t except if the shape function of the limit order book f is constant between D t and D t+ . This block-shaped limit order book is the one used, for instance, by Obizhaeva and Wang in [START_REF] Obizhaeva | Optimal trading strategy and supply/demand dynamics[END_REF] and corresponds to a linear price impact.

Alternatively, as we can consider that the resilience acts on the price impact when the large trader is not placing orders instead of the exponential reversion of the volume impact, by taking

dD t = -ρ t D t dt (6.20)
The equation (6.20) means that the price impact is recovering in the limit order book. So, if we replace (6.17) by (6.20) we obtain the so called price impact reversion model.

This two different models lead to different point of views for the dynamic of the limit order book and we remark that they are not necessarily equivalent. Thereby, instead of only studying the model impact with price reversion as in the most part of the literature, we also need to analyze the model with volume impact.

Instead of defining the optimal execution problem within a class of deterministic strategies as in [START_REF] Obizhaeva | Optimal trading strategy and supply/demand dynamics[END_REF], Alfonsi, Fruth and Schied in [START_REF] Alfonsi | Optimal execution strategies in limit order books with general shape functions[END_REF] allow the strategy to belong to the larger class of adapted strategies. In [START_REF] Alfonsi | Optimal execution strategies in limit order books with general shape functions[END_REF] the large trader could a priori have sell orders in a buy program, even though they show that this is not optimal in their model, alternatively to the model suggested in [START_REF] Obizhaeva | Optimal trading strategy and supply/demand dynamics[END_REF]. Moreover, analyzing several examples, Alfonsi, Fruth and Schied in [AFS10] assure the robustness of the optimal strategy.

The techniques used to solve the optimal execution problem in [START_REF] Alfonsi | Optimal execution strategies in limit order books with general shape functions[END_REF] are based on the Lagrange multiplier method and not in dynamic programming techniques as in [START_REF] Obizhaeva | Optimal trading strategy and supply/demand dynamics[END_REF]. The idea behind is to reduce the model with the two sides of the limit order book to a model without bid-ask spread and to prove that these problems are equivalent.

The main results in the works [START_REF] Alfonsi | Optimal execution strategies in limit order books with general shape functions[END_REF] and [START_REF] Alfonsi | Optimal trade execution and absence of price manipulations in limit order book models[END_REF] are the existence and uniqueness of the optimal strategy and the fact that it is possible to exhibit analytic formulas for this optimal strategy.

Differences between the Gatheral model and the Alfonsi, Fruth and Schied model

One of the results obtained by [START_REF]No-dynamic-arbitrage and market impact[END_REF] is that the exponential decay is incompatible with the non-linear market impact, outcome that seems to be in contradiction with the conclusion in [START_REF] Alfonsi | Optimal trade execution and absence of price manipulations in limit order book models[END_REF].

This difference can be explained by taking the discrete version of the model proposed by Gatheral in [Gat10]

S G t = S 0 t + � τn<t h(ξ n )G(t -τ n ) (6.21)
where the functions h and G are defined according to (6.14).

In the continuous-time case (6.14), considering an exponential decay G(t) = e -ρt , for ρ a positive constant, in [START_REF]No-dynamic-arbitrage and market impact[END_REF] Gatheral proved that if the impact function h is not linear there will not exist price manipulation strategies in the sense of Huberman and Stanzl. This conclusion can be also applied in the discrete version of the model presented in [START_REF]No-dynamic-arbitrage and market impact[END_REF] given by (6.21) using discrete approximations of the manipulation strategies obtained in the continuous case.

In the model proposed by Alfonsi, Fruth and Schied in [AFS10], if we consider a constant resilience ρ in the model with volume impact reversion, we obtain that the volume impact process is defined as follows

E t = � τn<t ξ n e -ρ(t-τn) , (6.22)
and (6.22) implies that the actual price is given by

S t = S 0 t + F -1 � � τn<t ξ n e -ρ(t-τn) � . (6.23)
Thus, the models proposed in [START_REF]No-dynamic-arbitrage and market impact[END_REF] and in [START_REF] Alfonsi | Optimal execution strategies in limit order books with general shape functions[END_REF] are different which explains the difference in their conclusion because in (6.21) the nonlinear price impact function is applied to each trade whereas in (6.23) is a function of the total volume impact.

Price manipulation strategies

As an asset pricing model, a market impact model needs some requirements to assure its viability.

Huberman and Stanzl in [START_REF] Huberman | Price manipulation and quasi-arbitrage[END_REF] introduce the concept of price manipulation, i.e. the existence of strategies where � = 0 and that have strictly negative expected execution costs. These types of price manipulation strategies are called price manipulation strategies in the sense of Huberman and Stanzl.

The presence of these price manipulations can be seen as a weak principle of no-quasi-arbitrage because the gain is in an average sense. Thus, by repeating indefinitely the price manipulation strategies, we can obtain by a law of large numbers, an almost sure profit, that is an arbitrage in the classical sense.

So, Huberman and Stanzl affirm that the assumption of risk neutral dynamics for the unaffected price process is not sufficient for the viability of the market impact model because can exist price manipulation strategies for price impact models with martingale dynamics for prices. Besides, the problem that consists in the minimization of the costs incurred by the large trader could be not well defined due to the existence of the price manipulation strategies in the sense of Huberman and Stanzl.

For example, by studying the relationship between the market impact function h and its decay G that exclude price manipulation strategies in the sense of Huberman and Stanzl [HS04], Gatheral obtains expressions determining the value of the parameters appearing in the price impact and decay functions.

Alfonsi and Schied in [START_REF] Alfonsi | Optimal trade execution and absence of price manipulations in limit order book models[END_REF] extend the concept of price manipulation strategies by introducing the existence of strategies where the expected cost of a sell (buy) program can be decreased by intermediate buy (sell) trades, i.e. ∃X admissible strategy such that

C(X) < inf � C( X)
, X is admissible and nonincreasing or nondecreasing

� .
Alfonsi and Schied called this notion the transaction-triggered price manipulation strategies. We remark that if there is no transaction-triggered price manipulation strategies then there is no price manipulation strategies in the sense of Huberman and Stanzl.

Motivation for our work

After overviewing all these models, we can note that they do not consider entirely the liquidity changes during the trading time [0, T ] where the large trader has to liquidate his position. Some of the models presented above consider a resilience parameter that depends on time but the distribution of orders in the limit order book does not depend on time and sometimes is even constant with respect to the price. Therefore, the aim of this part of the work is to extend the model proposed by [START_REF] Alfonsi | Optimal trade execution and absence of price manipulations in limit order book models[END_REF] by introducing the time dependence of the liquidity and then by studying the consequences of this time component in markets while maintaining the tractability of the model introduced in [START_REF] Alfonsi | Optimal execution strategies in limit order books with general shape functions[END_REF].

One work that considers that the liquidity is not constant over time is the paper of Fruth, Schöneborn and Urusov [START_REF] Fruth | Optimal trade execution and price manipulation in order books with time-varying liquidity[END_REF]. Here, they analyze the optimal strategies and the existence of price manipulation strategies in a time-dependent limit order book model with deterministic depth and resilience for a non-zero and zero bid-ask spread case. In the case of a bid-ask spread different from zero, this spread increases when market orders are executed in the limit order book and so they prove the non existence of price manipulation strategies while they obtain that there are price manipulation strategies when the bid-ask spread is neglected.

Fruth, Schöneborn and Urusov in [START_REF] Fruth | Optimal trade execution and price manipulation in order books with time-varying liquidity[END_REF] are interested in the minimization of costs problem which is set in a discrete-time and continuous-time framework and is solved using dynamic programming techniques. They find that under some assumptions on the parameters of the model, the orders have to be executed according to a ratio between the number of orders remaining to liquidate and the current price impact. We remark that the time-dependent limit order book used in [START_REF] Fruth | Optimal trade execution and price manipulation in order books with time-varying liquidity[END_REF] is based on the model introduced in [START_REF] Obizhaeva | Optimal trading strategy and supply/demand dynamics[END_REF] which means that they take into account a block-shaped limit order book which implies considering a linear market impact.

In [START_REF] Bank | Optimal order scheduling for deterministic liquidity patterns[END_REF], Bank and Fruth also study the problem of letting the liquidity to change over time through the market depth and the resilience parameter. By considering also a block-shaped limit order book, they set out the minimization of costs as a convex problem in order to manipulate convex analysis techniques that allow to describe the optimal strategies using concave envelopes depending on the parameters of the model.

The work that we propose extends different points from the works [AFS10] and [START_REF] Alfonsi | Optimal trade execution and absence of price manipulations in limit order book models[END_REF]. One new aspect is that the depth of the limit order book changes along with time. It is well known that there is more activity on markets at the opening and closing of markets but less activity at noon. This led to underlining the existence of an U-shaped pattern in the intraday trading volume, price volatility and average bid-ask spread, pattern that shows the relevance of time in the dynamic of the limit order book. These intraday patterns have been highlighted by Jain and Joh in [START_REF] Jain | The dependence between hourly prices and trading volume[END_REF], Gerety and Mulher in [START_REF] Gerety | Trading halts and market activity: An analysis of volume at the open and the close[END_REF] for volumes and prices in the U.S. markets, Hamao and Hasbrouck in [START_REF] Hamao | Securities trading in the absence of dealers: trades and quotes on the Tokyo Stock Exchange[END_REF] for the Tokyo Stock Exchange and Kleidon and Werner [START_REF] Kleidon | trading of British cross-listed stocks: an intraday analysis of market integration[END_REF] for the London Stock Exchange. Hence, the idea of our model is to consider a time-dependent shape of the limit order book which is coherent with this time shift of the market conditions. For example, this shape could be calibrated to capture the deterministic changes in the liquidity during one day. See Chordia, Roll and Subrahmanyam [CRS01],

Kempf and Mayston [START_REF] Kempf | Liquidity commonality beyond best prices[END_REF] and Lorenz and Osterrieder [START_REF] Lorenz | Simulation of a limit order driven market[END_REF] for more details on deterministic liquidity patterns.

We remark that this calibration of the time-varying liquidity is consistent with the estimation of the other parameters of the model as the resilience because this resilience has to capture as well the changes in the recovery of the limit order book during a period of time.

Beyond solving the optimal execution problem in a more general context, our goal is to understand how the dynamics of the LOB may create or not price manipulations in this time-dependent framework. The study of this price manipulations strategies lead us to derive sufficient conditions to exclude them. These conditions are not only interesting from a theoretical point of view, as they also give a qualitative understanding on how price manipulations may occur when posting or cancelling limit orders. The behavior of market makers can be related to the parameters of the model which allow to explain these price manipulations strategies from the market maker point of view. It is important to note that price manipulations strategies do not exist in the model without time-dependence as it has been proven by [START_REF] Alfonsi | Optimal execution strategies in limit order books with general shape functions[END_REF].

Another contribution of this work is that we solve the optimal execution problem in a continuous time setting while [START_REF] Alfonsi | Optimal execution strategies in limit order books with general shape functions[END_REF] and [START_REF] Alfonsi | Optimal trade execution and absence of price manipulations in limit order book models[END_REF] mainly focus on discrete time strategies. In particular, using a time-continuous framework is much more suitable for stating the conditions that exclude price manipulations and for understanding the influence of the shape of the limit order book on the price manipulations strategies.

Finally, we consider that new arrival orders can appear anywhere in the limit order book and not only between the bid-ask spread as it is considered in [START_REF] Alfonsi | Optimal execution strategies in limit order books with general shape functions[END_REF] and [START_REF] Alfonsi | Optimal trade execution and absence of price manipulations in limit order book models[END_REF]. In other words, the agents (noisy traders) can place limit orders in the depth of the limit order book and not only at the best price that is either the current best ask or the current best bid.

Price new orders new orders new orders

Fig. 6.8. New orders appear in the bid-ask spread in the model [START_REF] Alfonsi | Optimal trade execution and absence of price manipulations in limit order book models[END_REF] as it is shown by the dashed line. In our framework, new orders can appear in the bid-ask spread but also in the depth of limit order book as can be seen with the continuous arrows.

Section 7 presents the model that extends [START_REF] Alfonsi | Optimal execution strategies in limit order books with general shape functions[END_REF].

Introduction

It is a rather standard assumption in finance to consider an infinite liquidity. By infinite liquidity, we mean here that the asset price is given by a single value, and that one can buy or sell any quantity at this price without changing the asset price. This assumption is in particular made in the Black and

Scholes model [START_REF] Black | The pricing of options and corporate liabilities[END_REF], and is often made as far as derivative pricing is concerned. When considering portfolio over a large time horizon, this approximation is relevant since one may split orders in small ones along the time and reduces one's own impact on the price. At most, the lack of liquidity can be seen as an additional transaction cost. This issue has been broadly investigated in the literature, see Cetin, Jarrow and Protter [START_REF] Çetin | Liquidity risk and arbitrage pricing theory[END_REF] and references within.

If we consider instead brokers that have to trade huge volumes over a short time period (some hours or some days), we can no longer neglect the price impact of trading strategies. We have to focus on the market microstructure and model how prices are modified when buy and sell orders are executed. Generally speaking, the quotation of an asset is made through a Limit Order Book (LOB) that lists all the waiting buy and sell orders on this asset. The order prices have to be a multiple of the tick size, and orders at the same price are arranged in a First-In-First-Out stack. The bid (resp. ask) price is the price of the highest waiting buy (resp. lowest selling buy) order. Then, it is possible to buy or sell the asset in two different ways: one can either put a limit order and wait that this order matches another one or put a market order that consumes the cheapest limit orders in the book. In the first way, the transaction cost is known but the execution time is uncertain. In the second way, the execution is immediate (provided that the book contains enough orders). The price per share instead depends on the order size. For a buy (resp. sell) order, the first share will be traded at the ask (resp.

bid) price while the last one will be traded some ticks upper (resp. lower) in order to fill the order size. The ask (resp. bid) price is then modified accordingly.

The typical issue on a short time scale is the optimal execution problem: on given a time horizon, how to buy or sell optimally a given amount of assets? As pointed in Gatheral [START_REF]No-dynamic-arbitrage and market impact[END_REF] and Alfonsi, Schied and Slynko [START_REF] Alfonsi | Order book resilience, price manipulation and the positive portfolio problem[END_REF], this problem is closely related to the market viability and to the existence of price manipulations. Modelling the full LOB dynamics is not a trivial issue, especially if one wants to keep tractability to solve then the optimal execution problem. Instead, simpler models called market impact models have been proposed. These models only describe the dynamics of one asset price and model how the asset price is modified by a trading strategy. Thus, Bertsimas and

Lo [START_REF] Bertsimas | Optimal control of execution costs[END_REF], Almgren and Chriss [AC00], Obizhaeva and Wang [START_REF] Obizhaeva | Optimal trading strategy and supply/demand dynamics[END_REF] have proposed different models where the price impact is proportional to the trading size, in which they solve the optimal execution problem. However, some empirical evidence on the markets show that the price impact of a trade is not proportional to its size, but is rather proportional to a power of its size (see for example Potters and Bouchaud [START_REF] Bouchaud | More statistical properties of order books and price impact[END_REF], and references within). With this motivation in mind, Gatheral [START_REF]No-dynamic-arbitrage and market impact[END_REF] has suggested a nonlinear price impact model. In the same direction, Alfonsi, Fruth and Schied [START_REF] Alfonsi | Optimal execution strategies in limit order books with general shape functions[END_REF] have derived a price impact model from a simple LOB modelling. Basically, the LOB is modelled by a shape function that describes the density of limit orders at a given price. This model has then been studied further by Alfonsi and Schied [START_REF] Alfonsi | Optimal trade execution and absence of price manipulations in limit order book models[END_REF] and Predoiu, Shaikhet and Shreve [START_REF] Predoiu | Optimal execution in a general one-sided limitorder book[END_REF].

The present paper extends this model by letting the LOB shape function vary along the time.

Beyond solving the optimal execution problem in a more general context, our goal is to understand how the dynamics of the LOB may create or not price manipulations. Indeed, a striking result in [AFS10, AS10] is that the optimal execution strategy is made with trades of same sign, which excludes any price manipulation. This result holds under rather general assumptions on the LOB shape function, when the LOB shape does not change along the time. Instead, we will see in this paper that a time-varying LOB may induce price manipulations and we will derive sufficient conditions to exclude them. These conditions are not only interesting from a theoretical point of view. They give a qualitative understanding on how price manipulations may occur when posting or cancelling limit orders. While preparing this work, Fruth, Schöneborn and Urusov [START_REF] Fruth | Optimal trade execution and price manipulation in order books with time-varying liquidity[END_REF] have presented a paper where this issue is addressed for a block-shaped LOB, which amounts to a proportional price impact.

number of limit orders available between prices S 0 t + x and S 0 t + x + dx is given by λ(t)f (x)dx. These orders are sell orders if x ≥ D t and buy orders otherwise. The functions f : R � → (0, ∞) and λ : [0, T ] � → (0, ∞) are assumed to be continuous, and represent respectively the LOB shape and the depth of the order book. We define the antiderivative of the function f , F (y) :=

� y 0 f (x)dx, y ∈ R, and assume that lim x→-∞ F (x) = -∞ and lim x→∞ F (x) = ∞, (7.4)
which means that the book contains an infinite number of limit buy and sell orders. Thus, we set the following relationship between the volume impact E t and the price impact D t :

� Dt 0 λ(t)f (x)dx = E t ,
or equivalently,

E t = λ(t)F (D t ) and D t = F -1 � E t λ(t) � . (7.5) Within this framework, a large trade ξ t changes D t to D t+ = F -1 � Et+ξt λ (t)
� and has the cost

� D t+ Dt (S 0 t + x)λ(t)f (x)dx = ξ t S 0 t + � D t+ Dt λ(t)xf (x)dx := π t (ξ t ). (7.6)
Throughout the paper, we assume that λ is C 2 and set η t = λ ′ (t) λ(t) . Thus, we have

λ(t) = λ(0) exp �� t 0 η u du � ,
and t � → η t is C 1 . Similarly, we assume that t � → ρ t is C 1 . Now, let us observe that we have assumed that the volume impact decays exponentially when the large trader is inactive. Other choices are of course possible, and a natural one would be to assume that the price impact decays exponentially

dD t = -ρ t D t dt, (7.7)
which amounts to assume that

dE t = η t E t dt -ρ t λ(t)f (F -1 (E t /λ(t)))F -1 (E t /λ(t))
dt by (7.5).

Definition 7.1. The dynamics of "model V " with volume impact reversion is the one given by (7.1), (7.2), (7.3) and (7.5). The dynamics of "model P " with price impact reversion is the one given by (7.1), (7.2), (7.7) and (7.5). In both models, we assume that the market is at equilibrium at time 0, i.e.

E 0 = D 0 = 0.
Remark 7.1. Though being simplistic, this model describes through ρ t and λ(t) the two different ways that market makers have to put (or cancel) limit orders: it is either possible to pile orders at an existing price or to put orders at a better price than the existing ones. Thus, λ(t) describes how market makers pile or cancel orders while ρ t describes the rate at which new orders appear at a better price.

Basically, one may think these functions one-day periodic, with relative high values at the opening and the closing of the market and low values around noon. The particular case λ ≡ 1 corresponds to the model introduced by Alfonsi, Fruth and Schied [START_REF] Alfonsi | Optimal execution strategies in limit order books with general shape functions[END_REF] for which new orders can only appear at a better price.

Let us make some comments of the model. Obviously, limit order books have in practice a much more sophisticated dynamics than the one presented above. Somehow, the shape function f should be seen as an average of all the order books observed during one day, while λ(t) should represent a one day periodic function which is proportional to the volume of limit orders in the book. The resilience ρ t should also be considered as a one-day periodic function that should be proportional to the volume of new limit orders that are posted at the bid or ask price. This give a way to estimate all the parameters. However, the scope of our model is not to model precisely the limit order book at a microstructure level. It aims at modelling the price impact at a mesoscopic time scale. The limit order book interpretation is mainly used to justify equation (7.6) that relates the transaction costs to the shape function f . Thus, it seems to us more appropriate to estimate the parameters using the market price impact observations. Empirically, it has been observed that the price impact is proportional to some power of the order size (see for instance ). This indicates the choice of f (x) = |x| γ which reproduces precisely such an impact. The parameter γ could be estimated like in the cited papers. Once γ is chosen, λ(t) could be estimated in the same vein from empirical data on market impact. Also, ρ t can be estimated from the average time needed for the decay of the temporary price impact.

The optimal execution problem, and price manipulation strategies

We focus on the optimal liquidation of a portfolio with � shares by a large trader who can place market orders over a period of time [0, T ]. Thus, � > 0 (resp. � < 0) corresponds to a selling (resp. buying) strategy.

We first consider discrete strategies and assume that at most N + 1 trades can occur. An admissible strategy will be then described by an increasing sequence τ 0 = 0 ≤ • • • ≤ τ N = T of stopping times and random variables ξ 0 , . . . , ξ N (ξ i stands for the trading size at time τ i ) such that -� + � N i=0 ξ i = 0, i.e. the trader liquidates indeed � shares,

-ξ i is F τ i -measurable, -∃M ∈ R, ∀0 ≤ i ≤ N, ξ i ≥ M , a.s.
The expected cost of an admissible strategy (ξ, T ) with ξ = (ξ 0 , . . . , ξ N ) and T = (τ 0 , . . . , τ N ) is given by

C(ξ, T ) = E � N � i=0 π τ i (ξ i ) � , (7.8)
where π τ i (ξ i ) stands for the cost of the i-th trade, and is defined by (7.6) in models V or P . Throughout the paper, we will assume that the goal of the large trader is to minimize his expected cost among the admissible strategies.

Remark 7.2. The choice of minimizing the expected cost enables us to characterize explicitly the optimal strategy (see Theorems 7.3, 7.4, 7.5 and 7.6). Let us mention here that other targets could be considered for the trader. Typically, one may wish to include in the optimization program some risk aversion. This has been considered for instance by Almgren and Chriss [START_REF] Almgren | Optimal execution of portfolio transactions[END_REF] or Schied [START_REF] Schied | Robust strategies for optimal order execution in the Almgren-Chriss framework[END_REF].

However, in our model we will see that the optimal strategy that minimizes the expected cost is deterministic. Thus, the risk only stems from the fluctuations of S 0 during the execution and can be in practice neglected when the deadline T is short enough, which gives a justification of our choice.

We also consider continuous time trading strategy and make the same assumptions as Gatheral et al. [START_REF] Gatheral | Transient linear price impact and Fredholm integral equations[END_REF]. An admissible strategy (X t ) t≥0 is a stochastic process such that -X 0 = � and X T + = 0, -X is (F t )-adapted and leftcontinuous, -the function t ∈ [0, T +] � → X t has finite and a.s. bounded total variation.

The process X t describes the number of shares that remains to liquidate at time t. Thus, the discrete time strategy above corresponds to X t = � + � N i=0 ξ i 1 τ i <t , and the three assumptions on (ξ, T ) precisely give the ones on X. Let us observe that processes E and D are also leftcontinuous since we have in model V (resp. model P ):

dE t = dX t -ρ t E t dt, (resp. dE t = dX t + η t E t dt -ρ t λ(t)f (F -1 (E t /λ(t)))F -1 (E t /λ(t))dt). (7.9)
We want now to write the cost associated to the strategy X. To do so, we introduce the following notations

x ∈ R, F (x) = � x 0 yf (y)dy, G(x) = F � F -1 (x) � , (7.10) so that π t (dX t ) = S 0 t dX t + λ(t)[G � Et+dXt λ(t) � -G � Et λ(t)

�

]. Since G ′ = F -1 , the cost of an admissible strategy is given by:

C(X) = E   � T 0 � S 0 t + F -1 � E t λ(t) �� dX t + � t≤T λ(t) � G � E t + ΔX t λ(t) � -G � E t λ(t) � -F -1 � E t λ(t) � ΔX t �   , (7.11)
which coincides with (7.8) for discrete strategies. Here, ΔX t = X t+ -X t denotes the jump of X at time t (jumps are countable), and dX t stands for the signed measure on [0, T ] associated to (X t , 0 ≤ t ≤ T +) (a jump ΔX T induces a Dirac mass in T ). If we introduce the continuous part of X, X c t := X t -� 0≤s<t ΔX s , we can rewrite the cost as follows:

C(X) = E   � T 0 � S 0 t + F -1 � E t λ(t) �� dX c t + � t≤T S 0 t ΔX t + λ(t) � G � E t + ΔX t λ(t) � -G � E t λ(t) ��   . (7.12)
The optimal execution problem is in fact closely related to questions around market viability and arbitrage. We recall the definition of price manipulation strategies introduced by Huberman and

Stanzl [START_REF] Huberman | Price manipulation and quasi-arbitrage[END_REF].

Definition 7.2. A round trip is an admissible strategy X for � = 0. A Price Manipulation Strategy (PMS) in the sense of Huberman and Stanzl is a round trip whose expected cost is negative, i.e.

C(X) < 0.

Heuristically, if a PMS exists, it could be repeated indefinitely and would lead to a classical arbitrage (i.e. an almost sure profit) by a law of large numbers. However, it has been pointed in Alfonsi et al. [START_REF] Alfonsi | Order book resilience, price manipulation and the positive portfolio problem[END_REF] the absence of PMS does not ensure the market stability. In fact, in some PMS free models, the optimal strategy to sell � shares consists in buying and selling successively a much higher amount of shares. To correct this, they introduce the following definition. It is rather natural choice to exclude TTPM: in presence of TTPM a large trader would increase the traded volume to minimize its cost, which produce noise and may yield to instability. Besides, the absence of TTPM implies the absence of PMS. The optimal strategy for buying ε > 0 shares is made only with intermediate buy trades and has thus a positive cost. Thus, by some cost continuity that usually holds (this is the case for models V and P ), any round trip has a nonnegative cost.

Remark 7.3. It is possible to define a two-sided limit order book model like in Alfonsi, Fruth and Schied [START_REF] Alfonsi | Optimal execution strategies in limit order books with general shape functions[END_REF] or Alfonsi and Schied ([AS10], Section 2.6). In such a model, bid and ask prices evolve as follows. A buy (resp. sell) order of the large trader shifts the ask (resp. bid) price and leaves the bid (resp. ask) price unchanged. When the large trader is idle, the shifts on the ask and bid prices goes back exponentially to zero, like in models V or P . As in [AFS10, AS10], the two-sided model coincides with the model presented here when the large trader puts only buy orders or only sell orders.

In particular, the optimal strategies are the same in both models in absence of TTPM.

Main results

The first focus of this paper is to extend the results obtained in Alfonsi et al. [START_REF] Alfonsi | Optimal execution strategies in limit order books with general shape functions[END_REF][START_REF] Alfonsi | Optimal trade execution and absence of price manipulations in limit order book models[END_REF] and obtain the optimal execution strategies for LOB with a time varying depth λ. Doing so, our goal is also to better understand how this time varying depth may create manipulation strategies. In fact, it was shown in [START_REF] Alfonsi | Optimal execution strategies in limit order books with general shape functions[END_REF] and [START_REF] Alfonsi | Optimal trade execution and absence of price manipulations in limit order book models[END_REF] for λ ≡ 1 that under some general assumptions on the shape function f , there is an optimal liquidation strategy which is made only with sell (resp. buy) orders when � > 0 (resp. � < 0). Thus, there is no PMS nor TTPM when the LOB shape is constant. This is a striking result, and one may wonder how this is modified by changing slightly the assumptions.

In Alfonsi, Schied and Slynko [START_REF] Alfonsi | Order book resilience, price manipulation and the positive portfolio problem[END_REF] is studied the case of a block-shaped LOB, where the resilience is not exponential so that the market has some memory of the past trades. Conditions on the market resilience are given to exclude PMS and TTPM. Analogously, we want to obtain here conditions on λ and ρ that rules out such strategies. This is not only interesting from a theoretical point of view.

This will give also some noticeable qualitative insights for market makers. In fact, for a market maker who places and cancels significant limit orders, these conditions will indicate if he may or not create manipulation strategies.

Before showing the results, it is worth to make further derivations on the expected cost. Let us start with discrete strategies. By using the martingale property on S 0 and the assumptions on ξ made in Section 7.1.2, we can show easily like in [START_REF] Alfonsi | Optimal trade execution and absence of price manipulations in limit order book models[END_REF] that

C(ξ, T ) = -S 0 0 � + E � N � i=0 � D τ i + Dτ i λ(τ i )xf (x)dx � .
Then, it is easy to check that

� N i=0 � D τ i + Dτ i λ(τ i )xf (x)
dx is a deterministic function of (ξ, T ) in both volume impact reversion and price impact reversion models. We respectively denote by C V (ξ, T ) and C P (ξ, T ) this function and get:

C(ξ, T ) = -S 0 0 � + E � C M (ξ, T ) � , (7.13)
where M ∈ {V, P } indicates the model chosen. Thus, if the function (x, t) � → C M (x, t) has a unique

minimizer on {(x, t) ∈ R N × R N +1 , � N i=1 x i = -�, 0 = t 0 ≤ • • • ≤ t N = T }
, the optimal strategy is deterministic and given by this minimizer. When λ is constant, it is shown in [START_REF] Alfonsi | Optimal trade execution and absence of price manipulations in limit order book models[END_REF] that under some assumptions on f depending on the model chosen, the optimal time grid t ⋆ is homogeneous with respect to ρ, i.e.

� t ⋆ i+1 t ⋆ i ρ s ds = 1 N � T 0 ρ s ds.
Instead, there is no such a simple characterization for general λ, even in the block-shaped case. Thus, we will focus on optimizing the trading strategy ξ on a fixed time grid t: t = (t 0 , . . . , t N ), such that 0 = t 0 < • • • < t N = T .

(7.14) Last, we introduce the following notations that will be used throughout the paper:

a i = e - � t i t i-1 ρudu , ãi = a i λ(t i-1 ) λ(t i ) = e - � t i t i-1 (ρu+ηu)du , âi = a i λ(t i ) λ(t i-1 ) = e - � t i t i-1
(ρu-ηu)du , 1 ≤ i ≤ N.

(7.15)

Similarly in the continuous case, we get by using the martingale assumption (see Lemma 2.3 in Gatheral, Schied and Slynko [START_REF] Gatheral | Transient linear price impact and Fredholm integral equations[END_REF]) that E[ � T 0 S 0 t dX t ] = -�S 0 0 . From (7.11) and (7.12), we get

C(X) = -�S 0 0 + E[C M (X)],
where

C M (X) = � T 0 F -1 � E t λ(t) � dX c t + � t≤T λ(t) � G � E t + ΔX t λ(t) � -G � E t λ(t) �� .
Once again, C M is a deterministic function of the strategy X in both models M ∈ {V, P }, and it is sufficient to focus on its minimization.

7.2.1 The block-shaped limit order book case (f ≡ 1)

In this section, we consider a shape function of the limit order book that has the form λ(t). This time-dependent framework generalizes the block-shaped limit order book case studied by Obizhaeva

and Wang [START_REF] Obizhaeva | Optimal trading strategy and supply/demand dynamics[END_REF] that consists in considering a uniform distribution of shares with respect to the price. We will get an explicit solution for the optimal execution problem, which extends the results

given by Alfonsi, Fruth and Schied [START_REF] Alfonsi | Constrained portfolio liquidation in a limit order book model[END_REF].

Volume impact reversion model

When f ≡ 1, the deterministic cost function is simply given by

C V (ξ, t) = N � n=0 λ(t n ) � D tn+ Dt n xf (x)dx = N � i=0 ξ i 2    ξ i λ (t i ) + 2 � j<i e - � t i t j ρsds ξ j λ(t i )    , (7.16)
which is a quadratic form:

C V (ξ, t) = 1 2 ξ T M V ξ, with M V i,j = exp � - � � � � t j t i ρsds � � � � λ(t i ∨t j )
, 0 ≤ i, j ≤ N .

Theorem 7.1. The quadratic form (7.16) is positive definite if and only if a i ãi < 1, ∀i ∈ {1, . . . , N } . (7.17)

In this case, the optimal execution problem to liquidate � shares on the time-grid (7.14) admits a unique optimal strategy ξ ⋆ which is deterministic and explicitly given by:

           ξ ⋆ 0 = -� K V λ(t 0 ) 1-a 1 1-a 1 ã1 ξ ⋆ i = -� K V λ(t i ) � a i+1 1-a i+1 ãi+1 (ã i+1 -1) + 1-ã i 1-a i ãi � , 1 ≤ i ≤ N -1 ξ ⋆ N = -� K V λ(t N ) 1-ã N 1-a N ãN , (7.18)
where

K V = λ (t 0 ) (1 -2a 1 ) + λ (t 1 ) 1 -a 1 ã1 + N � i=2 λ(t i ) (1 -ãi ) 2 1 -a i ãi .
Its cost is given by C

V (ξ ⋆ , t) = � 2 /(2K V ).
This theorem provides an explicit optimal strategy for the large trader.

C V ((0, x, -x), t) = x 2 2λ(t 2 ) � e � t 2 t 1 ηudu + 1 -2e - � t 2 t 1 ρudu � = t 2 →t 1 x 2 2λ(t 1 ) ((2ρ t 1 + η t 1 )(t 2 -t 1 ) + o(t 2 -t 1 )) (7.20)
and is negative when t 2 is close enough to t 1 .

Corollary 7.1. In a block-shaped LOB, model V does not admit price manipulation in the sense of Let us now discuss this result from the point of view of market makers. A market maker that puts a significant amount of orders may have an influence on ρ t and η t and can increase (resp. decrease) them by respectively adding (resp. canceling) an order at a better price or at an existing limit order price. What comes out from (7.19) is that no PMS may arise if one adds limit orders, whatever the way of adding new orders. Instead, PMS can occur when canceling orders. A different conclusion will hold in the price reversion model.

An analogous result to Corollary 7.1 is stated in a recent paper by Fruth, Schöneborn and Urusov [START_REF] Fruth | Optimal trade execution and price manipulation in order books with time-varying liquidity[END_REF] that has been posted while we were preparing this work. To be precise, results

in [START_REF] Fruth | Optimal trade execution and price manipulation in order books with time-varying liquidity[END_REF] are given for model P with a block-shaped LOB, and the optimal execution strategy is obtained in a continuous time setting. As we will see in the next paragraph, models V and P are mathematically equivalent when the LOB shape is constant, even though they are different from a financial point of view. By taking a regular time-grid t i = iT N , i = 0 . . . , N , and letting N → +∞, we get back the optimal strategy in continuous time (that we still denote by ξ ⋆ , by a slight abuse of notations):

                 ξ ⋆ 0 -→ N →+∞ ξ ⋆ 0 := - � λ(T )+ � T 0 ρ 2 s λ(s) ηs+2ρs ds λ(0)ρ 0 2ρ 0 +η 0 ξ ⋆ i N T /N -→ N →+∞ ξ ⋆ t := - � λ(T )+ � T 0 ρ 2 s λ(s) ηs+2ρs ds λ(t) � � ρt 2ρt+ηt � ′ + ρ t � ρt+ηt 2ρt+ηt � � , for i N such that t i N N -→ Δt→0 t ξ ⋆ N -→ N →+∞ ξ ⋆ T := - � λ(T )+ � T 0 ρ 2 s λ(s) ηs+2ρs ds λ(T )(η T +ρ T ) η T +2ρ T . (7.21)
The strategy dX ⋆ t = ξ ⋆ 0 δ 0 (dt) + ξ ⋆ t dt + ξ ⋆ T δ T (dt) with initial trade ξ ⋆ 0 , continuous trading ξ ⋆ t on [t, t + dt] for t ∈ (0, T ) and last trade ξ ⋆ T is indeed shown to be optimal in Fruth, Schöneborn and Urusov [START_REF] Fruth | Optimal trade execution and price manipulation in order books with time-varying liquidity[END_REF] among the continuous time strategies with bounded variation. We will show here again this result for more general LOB shape. The optimal strategy has the following cost:

� 2 2 � λ (T ) + � T 0 ρ 2 s λ(s) 2ρs+ηs ds � .
Besides, this provides a necessary and sufficient condition to exclude transaction-triggered price manipulation.

Corollary

-ãi 1 -a i ãi ≥ a i+1 1 -ãi+1 1 -a i+1 ãi+1
, ∀i ∈ {1, . . . , N -1} and ãN ≤ 1. (7.23) Condition (7.22) can be seen as the continuous time limit of condition (7.23).

Let us give now an illustration of the optimal strategy with a time-varying depth. We consider the case of a time-varying depth

λ(t) = λ 0 + cos(2πt), with λ 0 > 1,
which corresponds to a one-day periodic function with high values at the beginning and at the end of the day. We can show that η t ≥ -2π √ λ 2 0 -1 and with a constant resilience ρ, there is no PMS as soon as 2ρ -2π √ λ 2 0 -1 ≥ 0. Figure 7.1 shows the optimal execution strategy (7.18) with a value λ 0 that excludes PMS but allows TTPM. The optimal strategy to buy 50 shares consists in buying almost 95 shares and selling 45 shares, which roughly trebles the traded volume.

Price impact reversion model

When f ≡ 1, the deterministic cost function

� N i=0 � D t i + Dt i λ(t i )xf (x)
dx is given by

C P (ξ, t) = N � n=0 λ(t n ) � D tn+ Dt n xf (x)dx = N � i=0 ξ i 2   ξ i λ(t i ) + 2 � j<i e - � t i t j ρsds ξ j λ(t j )   . (7.24)
This is a quadratic form:

C P (ξ, t) = 1 2 ξ T M P ξ, with M P i,j = exp � - � � � � t i t j ρsds � � � � λ(t i ∧t j )
for 0 ≤ i, j ≤ N . When f ≡ 1, we get from (7.9) that model P is equivalent to model V with a resilience ρt = ρ tη t . Another way to see that both models are mathematically the same in the block-shape case is to reverse the time and consider:

∀t ∈ [0, T ], ρt = ρ T -t , λ(t) = λ(T -t) and tN-i = T -t i , for 0 ≤ i ≤ N.
Then, we have

M P i,j = e -| � t i t j ρsds| λ(t i ∧ t j ) = e -| � tN-j tN-i ρsds| λ( tN-i ∨ tN-j ) , (7.25)
and the optimal execution problem in Model P with resilience ρ, LOB depth λ(t) and time-grid t is the same as the optimal execution problem in Model V with resilience ρ, LOB depth λ(t) and time-grid t.

We immediately get the following results.

Theorem 7.2. The quadratic form (7.24) is positive definite if and only if

a i âi < 1, ∀i ∈ {1, . . . , N } (7.26)
In this case, the optimal execution problem to liquidate � shares on the time-grid (7.14) admits a unique optimal strategy ξ ⋆ which is deterministic and explicitly given by:

           ξ ⋆ 0 = -� K P λ(t 0 ) 1-â 1 1-a 1 â1 . ξ ⋆ i = -� K P λ(t i ) � a i 1-a i âi (â i -1) + 1-â i+1 1-a i+1 âi+1 � , 1 ≤ i ≤ N -1 ξ ⋆ N = -� K P λ(t N ) 1-a N 1-a N âN (7.27)
where

K P = λ(t N )(1 -2a N ) + λ(t N -1 ) 1 -a N âN + N -2 � i=0 λ(t i ) (1 -âi+1 ) 2 1 -a i+1 âi+1 .
Its cost is given by C P (ξ ⋆ , t) = � 2 /(2K P ).

By taking a regular time-grid t i = iT N , i = 0 . . . , N , and letting N → +∞, we get the optimal strategy in continuous time:

                 ξ ⋆ 0 -→ N →∞ ξ ⋆ 0 := - � λ(0)+ � T 0 ρ 2 s λ(s) 2ρs-ηs ds λ(0) ρ 0 -η 0 2ρ 0 -η 0 ξ ⋆ i N T /N -→ N →∞ ξ ⋆ t := - � λ(0)+ � T 0 ρ 2 s λ(s) 2ρs-ηs ds λ(t) � � ρt-ηt 2ρt-ηt � ′ + ρ t � ρt-ηt 2ρt-ηt � � , for i N such that T i N N -→ Δt→0 t ξ ⋆ N -→ N →∞ ξ ⋆ T := - � λ(0)+ � T 0 ρ 2 s λ(s) 2ρs-ηs ds λ(T ) ρ T 2ρ T -η T .
(7.28)

The strategy with initial trade ξ ⋆ 0 , continuous trading ξ ⋆ t on [t, t + dt] for t ∈ (0, T ) and last trade ξ ⋆ T is shown to be optimal in Fruth, Schöneborn and Urusov [START_REF] Fruth | Optimal trade execution and price manipulation in order books with time-varying liquidity[END_REF] among the continuous time strategies with bounded variation, and has the following cost: We extend in this section the results obtained on the optimal execution for block-shaped LOB to more general shapes. In particular, the necessary and sufficient conditions that we have obtained to exclude TTPM (namely (7.22) for model V and (7.30) for model P ) are still sufficient conditions to exclude TTPM for a wider class of shape functions. From a mathematical point of view, we proceed as follows. We first characterize the optimal strategy on a discrete time grid, by using Lagrange multipliers. Then, one can guess the optimal continuous time strategy, and we prove its optimality by a verification argument.

� 2 2 � λ (0) + � T 0 ρ 2 s λ(s) 2ρs

Volume impact reversion model

We first introduce the following assumption that will be useful to study the optimal discrete strategy.

Assumption 7.1. 1. The shape function f satisfies the following condition:

f is nondecreasing on R -and nonincreasing on R + 2. ∀t ≥ 0, ρ t + η t ≥ 0.

We remark that when the LOB shape does not evolve in time (η t = 0), the second condition is satisfied and we get back the assumption made in Alfonsi, Fruth and Schied [START_REF] Alfonsi | Optimal execution strategies in limit order books with general shape functions[END_REF]. We define

x ∈ R, h V,i (x) = F -1 (x) -a i F -1 (ã i x) 1 -a i , 1 ≤ i ≤ N. (7.32)
Theorem 7.3. Under Assumption 7.1, the cost function C V (ξ, t) is nonnegative, and there is a unique optimal execution strategy ξ ⋆ that minimizes C V over {ξ ∈ R N +1 , � N i=0 ξ i = -�}. This strategy is given as follows. The following equation

N � i=1 λ(t i-1 )(1 -a i )h -1 V,i (ν) + λ(t N )F (ν) = -�
has a unique solution ν ∈ R, and

ξ ⋆ 0 = λ(t 0 )h -1 V,1 (ν) , ξ ⋆ i = λ(t i )(h -1 V,i+1 (ν) -ãi h -1 V,i (ν)), 1 ≤ i ≤ N -1, ξ ⋆ N = λ(t N )F (ν) -λ(t N -1 )a N h -1 V,N (ν) .
The first and the last trade have the same sign as -�. Besides, if the following condition holds

1 ãi 1 -ãi 1 -a i ≥ 1 -ãi+1 1 -a i+1 , (7.33) the intermediate trades ξ ⋆ i , 1 ≤ i ≤ N -1, have also the same sign as -�.
This theorem extends the results of [START_REF] Alfonsi | Optimal execution strategies in limit order books with general shape functions[END_REF], where λ is assumed to be constant. In that case, (7.33) is satisfied and all the trades have the same sign. Condition (7.33) is interesting since it does not depend on the shape function, but it is more restrictive than the condition (7.23) for the block-shape case (see Lemma 7.4 for (7.33) =⇒ (7.23)). In fact, the continuous time formulation is more convenient to analyze the sign of the trades. Under Assumption 7.1, we will show that no transaction-triggered price manipulation can occur with the same condition (7.22) as for the block-shape case.

When stating the optimal continuous-time strategy, we slightly relax Assumption 7.1. This is basically due to the argument of the proof that relies on a verification argument. Instead, our proof in the discrete case relies on Lagrange multipliers which requires to show first that the cost function has a minimum, and we use ρ t + η t ≥ 0 for that. We introduce the following function

h V,t (x) = F -1 (x) + η t + ρ t ρ t x f (F -1 (x)) . (7.34)
We will show that no PMS exists and that there is a unique optimal strategy if these functions for t ∈ [0, T ] are bijective on R with a positive derivative. If Assumption 7.1 holds, this condition is automatically satisfied.

Theorem 7.4. Let f ∈ C 1 (R). We assume that for t ∈ [0, T ], h V,t is bijective on R, such that h ′ V,t > 0. Then, the cost function C V (X) is nonnegative, and there is a unique optimal admissible strategy X ⋆ that minimizes C V . This strategy is given as follows. The equation

� T 0 λ(t)ρ t h -1 V,t (ν)dt + λ(T )F (ν) = -� (7.35)
has a unique solution ν ∈ R and we set

ζ t = h -1 V,t (ν). The strategy dX ⋆ t = ξ ⋆ 0 δ 0 (dt) + ξ ⋆ t dt + ξ ⋆ T δ T (dt) with ξ ⋆ 0 = λ(0)ζ 0 , ξ ⋆ t = λ(t) � dζ t dt + (ρ t + η t )ζ t � , ξ ⋆ T = λ(T )(F (ν) -ζ T ),
is optimal. The initial trade ξ ⋆ 0 has the same sign as -�.

Thus, a sufficient condition to exclude price manipulation strategies is to assume that h V,t is bijective with h ′ V,t > 0. We have a partial reciprocal result: there are PMS as soon as h ′ V,t 1 (0) < 0 (or equivalently, 2ρ t 1 + η t 1 < 0) for some t 1 ≥ 0. Indeed, in this case we consider the following round trip on the time grid t = (0, t 1 , t 2 ) with t 2 > t 1 , where the large trader buys x > 0 at time t 1 and sells x at time t 2 . The cost of such a strategy is given by

C V ((0, x, -x), t) = λ(t 1 )G � x λ(t 1 ) � + λ(t 2 )   G    x(e - � t 2 t 1 ρsds -1) λ(t 2 )    -G    xe - � t 2 t 1 ρsds λ(t 2 )       = λ(t 1 ) � -η t 1 G � x λ(t 1 ) � + (ρ t 1 + η t 1 ) x λ(t 1 ) F -1 � x λ(t 1 ) �� (t 2 -t 1 ) + o(t 2 -t 1 ). The derivative of x � → -η t 1 G(x) + (ρ t 1 + η t 1 )xF -1 (x) is ρ t 1 h V,t 1 (x)
, which has the opposite sign of x near 0 since h V,t 1 (0) = 0 and h ′ V,t 1 (0) < 0 by assumption. Thus, we have C V ((0, x, -x), t) < 0 for x and t 2t 1 small enough. Now, let us focus on the sign of the trades given by the optimal strategy. Without further hypothesis, the condition ξ ⋆ t ≥ 0 typically involves the shape function f . However, under Assumption 7.1, we can show that TTPM are excluded under the same assumption as for the block-shape case.

Corollary 7.4. Let f ∈ C 1 . Under Assumption 7.1, the function h V,t is C 1 (R), bijective on R, and such that h ′ V,t > 0. Thus, the result of Theorem 7.4 holds and the last trade ξ ⋆ T has the same sign as -�.

Besides, if (7.22) also holds, ξ ⋆ t has the same sign as -� for any 0 < t < T , which excludes TTPM.

Let us now focus on the example of a power-law shape: we assume that

f (x) = |x| γ , γ > -1.
Strictly speaking, this does not fulfill the assumptions made before on f since it is not smooth in 0. However, the result of Theorem 7.4 still holds. In this case, F (x) = sgn(x) |x| γ+1 γ+1 is well-defined and satisfies (7.4). We have F -1 (x) = sgn(x)(γ +1)

1 γ+1 |x| 1 γ+1 and h V,t (x) = sgn(x)(γ +1) 1 γ+1 |x| 1 γ+1 � ρt(2+γ)+ηt ρt(1+γ) � .
Thus, h V,t is bijective and increasing if, and only if:

ρ t (2 + γ) + η t > 0.
In this case, we have

h -1 V,t (x) = 1 γ + 1 K t (γ)sgn(x)|x| γ+1 with K t (γ) = � ρ t (1 + γ) ρ t (2 + γ) + η t � 1+γ
.

In this case, we have by Theorem 7.4 that

               ξ ⋆ 0 = -� � T 0 λ(t)ρtKt(γ)dt+λ(T ) λ(0)K 0 (γ), ξ ⋆ t = -� � T 0 λ(t)ρtKt(γ)dt+λ(T ) λ(t) � dKt(γ) dt + (ρ t + η t )K t (γ) � ξ ⋆ T = -� � T 0 λ(t)ρtKt(γ)dt+λ(T ) λ(T )(1 -K T (γ)) (7.36)
is the unique optimal strategy. For γ = 0, we get back (7.21). If we only assume that ρ t (2 + γ) + η t ≥ 0, we still have C V (X) ≥ 0 for any admissible strategy X. The cost C V (X) is indeed continuous with respect to the resilience, and is the limit of the cost associated to resilience ρ t + ε, ε ↓ 0. On the contrary, if ρ t (2 + γ) + η t < 0, we have h ′ V,t (0) < 0 and there is a PMS as explained above.

Corollary 7.5. When f (x) = |x| γ , model V does not admit PMS if, and only if ∀t ≥ 0, ρ t (2 + γ) + η t ≥ 0.

It does not admit transaction-triggered price manipulation if and only if

∀t ≥ 0, ρ t + η t ≥ 0, and

� ρ t (1 + γ) ρ t (2 + γ) + η t � ′ + ρ t � ρ t + η t ρ t (2 + γ) + η t � ≥ 0.
These conditions come respectively from the nonnegativity of the last and intermediate trades. For given functions ρ t and η t , the no PMS condition will be satisfied for t ∈ [0, T ] when γ is large enough. This can be explained heuristically. When γ increases, limit orders become rare close to S 0 t and dense away from S 0 t , which creates some bid-ask spread. One has then to pay to get liquidity, and round trips have a positive cost. Instead, when γ is close to -1 it is rather cheap to consume limit orders, which may facilitate PMS. In Figure 7.2, we have plotted the optimal strategy for γ = -0.3 and γ = 1 with the same parameters as in Figure 7.1 for the Block shape case. We can check that the no PMS condition is satisfied in both cases.

Price impact reversion model

The results that we present for model P are similar to the one obtained for model V . We first solve the optimal execution problem in discrete time. From its explicit solution, we then calculate its continuous time limit and check by a verification argument that it is indeed optimal. Doing so, we get sufficient conditions to exclude PMS and TTPM. In particular, condition (7.30) that excludes PMS and TTPM for block-shape LOB also excludes PMS and TTPM for a general LOB shape satisfying Assumption 7.2 below.

To study the optimal discrete strategy, we will work under the following assumption. Assumption 7.2. 1. The shape function f is C 1 and satisfies the following condition:

f is nonincreasing on R -and nondecreasing on R + 2. ∀t ≥ 0, ρ t -η t > 0. 3. x � → x f ′ (x) f (x) is nondecreasing on R -, nonincreasing on R + .
The monotonicity assumption made here is the opposite to the one made in Assumption 7.

� i=1 λ(t i-1 ) � F � h -1 P,i (ν) a i � - λ(t i ) λ(t i-1 ) F (h -1 P,i (ν)) � + λ(t N )F (ν) = -�
has a unique solution ν ∈ R, and

ξ ⋆ 0 = λ(t 0 )F � h -1 P,1 (ν) a 1 � , ξ ⋆ i = λ(t i ) � F � h -1 P,i+1 (ν) a i+1 � -F (h -1 P,i (ν)) � , 1 ≤ i ≤ N -1, ξ ⋆ N = λ(t N )[F (ν) -F (h -1 P,N (ν))].
The first and the last trade have the same sign as -�.

We now state the corresponding result in continuous time and set:

x ∈ R, h P,t (x) = x   1 + ρ t ρ t � 1 + xf ′ (x) f (x) � -η t   .
(7.37) Theorem 7.6. Let f ∈ C 2 (R). We assume that one of the two following conditions holds.

1. For t ∈ [0, T ], ρ t � 1 + xf ′ (x) f (x)
� -η t > 0 for any x ∈ R and h P,t is bijective on R, such that h ′ P,t (x) > 0, dx-a.e.

For

t ∈ [0, T ], ρ t � 1 + xf ′ (x) f (x) � -η t < 0 and ρ t � 2 + xf ′ (x) f (x)
� η t > 0 for any x ∈ R, and h P,t is bijective on R, such that h ′ P,t (x) < 0, dx-a.e. Then, the cost function C P (X) is nonnegative, and there is a unique optimal admissible strategy X ⋆ that minimizes C P . This strategy is given as follows. The equation

� T 0 λ(t)[ρ t h -1 P,t (ν)f (h -1 P,t (ν)) -η t F (h -1 P,t (ν))]dt + λ(T )F (ν) = -� (7.38)
has a unique solution ν ∈ R and we set

ζ t = h -1 P,t (ν). The strategy dX ⋆ t = ξ ⋆ 0 δ 0 (dt) + ξ ⋆ t dt + ξ ⋆ T δ T (dt) with ξ ⋆ 0 = λ(0)F (ζ 0 ), ξ ⋆ t = λ(t)f (ζ t ) � dζ t dt + ρ t ζ t � , ξ ⋆ T = λ(T )(F (ν) -F (ζ T )),
is optimal. The initial trade ξ ⋆ 0 has the same sign as -�.

In particular, there is no PMS in model P as soon as Assumptions (i) or (ii) hold. Conversely, let us

assume that ρ t 1 � 2 + xf ′ (x) f (x)
� η t 1 < 0, when x belongs to a neighbourhood of 0 for some t 1 ≥ 0. This is equivalent to assume that 2ρ t 1η t 1 < 0 for some t 1 ≥ 0. Then, we set t = (0, t 1 , t 2 ) with t 2 > t 1 , and consider that the large trader buys x > 0 at time t 1 and sells x at time t 2 . The cost of such a round trip is

C P ((0, x, -x), t) = λ(t 1 )G � x λ(t 1 ) � + λ(t 2 ) � G � F � e - � t 2 t 1 ρsds F -1 � x λ(t 2 ) �� - x λ(t 2 ) � - F � e - � t 2 t 1 ρsds F -1 � x λ(t 2 ) ��� = λ(t 1 ) � -η t 1 F � F -1 � x λ(t 1 ) �� + ρ t 1 F -1 � x λ(t 1 ) � 2 f � F -1 � x λ(t 1 ) �� � (t 2 -t 1 ) + o(t 2 -t 1 ). The derivative of x � → -η t 1 F (x) + ρ t 1 x 2 f (x) is xf (x) � ρ t 1 � 2 + xf ′ (x) f (x) � -η t 1 �
and has the opposite sign of x near 0. Thus, C P ((0, x, -x), t) is negative when t 2 is close to t 1 and x is small enough, which gives a PMS.

Corollary 7.6. Let f ∈ C 2 (R). Under Assumption 7.2, the function h P,t is C 1 (R), bijective on R and such that h ′ P,t > 0. Thus, the result of Theorem 7.6 holds and the last trade ξ ⋆ T has the same sign as -�.

Besides, if (7.30) also holds, ξ ⋆ t has the same sign as -� for any 0 < t < T , which rules out TTPM.

As for model V , we consider now the case of a power-law shape f (x) = |x| γ . We can apply the results of Theorem 7.6 in this case. We can also notice from (7.9) that dE t = (η tρ t (1 + γ))E t dt.

Therefore, model P with resilience ρ t is the same as model V with resilience ρt = ρ t (1 + γ)η t .

Corollary 7.7. When f (x) = |x| γ , model P does not admit PMS if, and only if ∀t ≥ 0, ρ t (2 + γ)η t ≥ 0.

It does not admit transaction-triggered price manipulation if and only if

∀t ≥ 0, ρ t (1 + γ)η t ≥ 0, and

� ρ t (1 + γ) -η t ρ t (2 + γ) -η t � ′ + ρ t � ρ t (1 + γ) -η t ρ t (2 + γ) + η t � ≥ 0.

Numerical results

In this paragraph, we would like to briefly investigate the impact of the different parameters on the optimal strategy. As already mentioned in this paper, it has been observed in the literature that the price impact of an order is proportional to a power of its volume (see e.g. Tóth et. al [BDdL + 11]), this power being close to 1/2. This leads us to consider the power law shape f (x) = |x| γ . In this model, the shift on the price D t is proportional to E 1 γ+1 t , which indicates the choice of γ ≈ 1. Last, we consider the volume impact reversion model. As said above, this choice is not restrictive since for a power law shape function it is equivalent to the price impact reversion model, up to a change of the resilience function. We first examine how the shape function modifies the optimal strategy. We have already seen in Figure 7.2 that this function may significantly change the optimal trades, as one could expect.

However, this Figure consider two rather different values of γ with parameters implying TTPM. Now, we consider other parameters that exclude TTPM since we deem it should be the case for in practice.

We still consider a one day (i.e. one period) deadline. As recalled above, it is empirically observed that the price impact of a trade is proportional to a power of the trade size, and this power is typically close to 1/2. In Figure (7.3), we have plotted the optimal strategy for γ = 7/3 and γ = 3/7, which corresponds respectively to a power 1/(γ + 1) equal to 0.3 and 0.7. The optimal strategy for γ = 1 (i.e. a square-root impact) is plotted in the upper right part of Figure (7.4). Qualitatively, there is no striking difference between these optimal strategies that do not seem very sensitive to γ. The main change is the size of the last trade that increases when γ gets larger. In Figure 7.4 we focus on how is modified the optimal strategy when we consider constant or time dependent functions λ and ρ. Let us recall that λ models the liquidity available on the market while ρ models its resilience. It is known from Alfonsi, Fruth and Schied [AFS10] that the optimal strategy is made with intermediate trades of the same size when ρ and λ are both constant. This is again observed in the upper left graphic of Figure 7.4. Then, we consider in the upper right and the lower left graphics the case where λ depends on t and ρ is constant, and conversely. To compare, we have considered each time the same type of time-dependency, which is proportional to 4 + cos(2πt).

Qualitatively, this two graphics are rather similar. As one could expect, the size of the intermediate trades follows the trend of the market liquidity or resilience. Looking closer, this impact on the optimal strategy is more important for the liquidity oscillations than for the resilience. Last, when both liquidity and resilience depend on the time (lower right graphic), these effects add up. The intermediate trades change significantly along the time. Also, the first and last trades are larger, because they coincides to the upper value of λ and ρ. Thus, we see that the evolution of λ and ρ have a clear impact on the optimal strategy: this strategy follows the trend given by λ and ρ. This behaviour is very close to the VWAP (Volume Weighted Average Price) strategy which is widely used by practitioners.

Proofs

The block shape case

Proof of Theorem 7.1: The quadratic form (7.16) is given by C

V (ξ, t) = 1 2 ξ T M V ξ, with M V i,j = exp � - � � � � t j t i ρsds � � � � λ(t i ∨t j )
, 0 ≤ i, j ≤ N . Let us assume that a i ãi < 1, ∀i ∈ {1, . . . , N }. Then, we can define the following vectors:

y 0 = e 0 � λ(t 0 ) , y i = ãi y i-1 + e i � λ(t i ) √ 1 -a i ãi , 1 ≤ i ≤ N
where e 0 . . . e N denote the canonical basis of R N +1 . We have M V ij = y T i y j . We introduce Y the upper triangular matrix with columns y 0 , . . . , y N . By assumption, it is invertible and so is

M = Y T Y . Conversely, if M V is positive definite, the minors det((M V i,j ) 0≤i,j≤n ) = 1 λ(t 0 ) n � i=1 1 λ(t i ) (1 -a i ãi ), 1 ≤ n ≤ N
are positive, which gives (7.17).

Let us turn to the optimization problem. One has to minimize C V (ξ, t) under the linear constraint

� N i=0 ξ i = -�, which gives ξ ⋆ = - � 1 T (M V ) -1 1 � M V � -1 1, (7.39)
where 1 ∈ R N +1 is a vector of ones. Since Y is upper triangular, it can be easily inverted and we can calculate explicitly

� M V � -1
1 and get (7.18). We do not detail these calculations since the result is anyway a consequence of Theorem 7.3. � 7.3.2 General limit order book shape with model V Let us introduce some notations. For the time grid t given by (7.14), we introduce the following quantities:

α k := � t k t k-1 ρ s ds, k = 1, . . . , N. (7.40)
We can write the cost function (7.13) as follows

C V (ξ, t) = N � n=0 λ(t n ) � G � E n + ξ n λ(t n ) � -G � E n λ(t n ) �� , (7.41)
where we use the following notations (observe that E n = a n (E n-1 + ξ n-1 ))

E 0 = 0, E n = n-1 � i=0 ξ i e - � n k=i+1 α k , 1 ≤ n ≤ N. Lemma 7.1. We have ∂C V ∂ξ N = F -1 � E N +ξ N λ(t N )
� and, for i = 0, . . . , N -1,

∂C V ∂ξ i -a i+1 ∂C V ∂ξ i+1 = F -1 � E i + ξ i λ(t i ) � -a i+1 F -1 � E i+1 λ(t i+1 ) � . (7.42)
Proof. Let us first observe that ∂En ∂ξ i = 0, if i ≥ n, and ∂En ∂ξ i = e -� n k=i+1 α k if i < n. Thus, we get by using that G ′ = F -1 :

∂C V ∂ξ i = F -1 � E i + ξ i λ(t i ) � + N � n=i+1 e - � n k=i+1 α k � F -1 � E n + ξ n λ(t n ) � -F -1 � E n λ(t n ) �� = F -1 � E i + ξ i λ(t i ) � -e -α i+1 F -1 � E i+1 λ(t i+1 ) � + e -α i+1   F -1 � E i+1 + ξ i+1 λ(t i+1 ) � + N � n=i+2 e - � n k=i+2 α k � F -1 � E n + ξ n λ(t n ) � -F -1 � E n λ(t n ) ��   = F -1 � E i + ξ i λ(t i ) � -a i+1 F -1 � E i+1 λ(t i+1 ) � + a i+1 ∂C V ∂ξ i+1 .
Lemma 7.2. Under Assumption 7.1, we obtain the next conclusions.

1. For i ∈ {1, . . . , N }, the function h V,i defined in (7.32) is an increasing bijection on R that satisfies sgn

(x)h V,i (x) ≥ 1-a i ãi 1-a i F -1 (x). 2. If (7.33) holds, then we have sgn(x)h -1 V,i+1 (x) ≥ sgn(x)ã i h -1 V,i (x) for i ∈ {1, . . . , N -1}. 3. sgn(x)F (x) ≥ sgn(x)ã N h -1 V,N (x).
Proof. 1. Since the resilience ρ t is positive, we have 0 < a i < 1, and ãi ≤ 1 since ρ t + η t ≥ 0 by Assumption 7.1. We then get

∂h V,i (x) ∂x = 1 1 -a i � 1 f (F -1 (x)) - a i ãi f (F -1 (ã i x)) � ≥ 1 -a i ãi 1 -a i 1 f (F -1 (x)) > 0
because f is nondecreasing on R -and nonincreasing on R + , and F -1 is increasing.

2. We set f (x) = (F -1 ) ′ (x) = 1/f (F -1 (x)): this function is positive, nonincreasing on R -and nondecreasing on R + . Let ν ≥ 0 and y = h -1 V,i+1 (ν). We note that y ≥ 0 because h V,i+1 (0) = 0 and h V,i+1 is increasing by the first point of this lemma. Thus, we have that ν = F -1 (y)a i+1 F -1 (ã i+1 y) 1a i+1 = F -1 (ã i+1 y) + F -1 (y) -F -1 (ã i+1 y) 1a i+1 = F -1 (ã i+1 y) + 1 1a i+1 � y ãi+1 y f (ξ)dξ ≤ F -1 (y) + 1 -ãi+1 1a i+1 y f (y) =: g i+1 (y)

Hence, we obtain that g i+1 is increasing on R and then, y ≥ g -1 i+1 (ν). Let z = ãi h -1 V,i (ν) ≥ 0. We have:

ν = F -1 � z ãi � -a i F -1 (z) 1 -a i = F -1 (z) + F -1 � z ãi � -F -1 (z) 1 -a i = F -1 (z) + 1 1 -a i � z ãi z f (ξ)dξ ≥ F -1 (z) + � 1 ãi -1 � 1 -a i z f (z) =: ḡi (z)
Therefore, if (7.33) holds, we get that g i+1 (x) ≤ ḡi (x) for all x ≥ 0. Then, we have g -1 i+1 (x) ≥ g -1 i (x), and therefore y ≥ g -1 i+1 (ν) ≥ g -1 i (ν) ≥ z. The same arguments for ν ≤ 0 give y ≤ g -1 i+1 (ν) ≤ g -1 i (ν) ≤ z. 3. Using the above definition, we have sgn(x)ḡ N (x) ≥ sgn(x)F -1 (x), and therefore we get sgn(ν)F (ν) ≥ sgn(ν)ḡ -1 N (ν) ≥ sgn(ν)z = sgn(ν)ã N h -1 V,N (ν) . Proof of Theorem 7.3: We rewrite the cost function (7.41) to minimize as follows: , so that

C V (ξ, t) = N � n=0 λ(t n ) � G � E n + ξ n λ(t n ) � -G � E n λ(t n ) �� = λ(t N )G   � N i=0 ξ i e - � N
C V (ξ, t) = λ(t N )G((T ξ) N ) + N -1 � n=0 [λ(t n )G((T ξ) n ) -λ(t n+1 )G (ã n+1 (T ξ) n )] . (7.43)
Let us observe that T is a linear bijection. By Lemma 7.3 we get that C V (ξ, t) ≥ 0 and C V (ξ, t) → |ξ|→+∞ +∞, which gives the existence of a minimizer ξ ⋆ over ξ, s.t.

� N i=0 ξ i = -�. Thus, by using (7.42), there must be a Lagrange multiplier ν such that

ν = h V,i+1 � E i + ξ ⋆ i λ(t i ) � , i = 0 . . . N -1, and ν = F -1 � E N + ξ ⋆ N λ(t N ) � . (7.44)
We have

E i +ξ ⋆ i λ(t i ) = h -1 V,i+1 (
ν) and then E i+1 = λ(t i )a i+1 h -1 V,i+1 (ν), for 0 ≤ i ≤ N -1. Thus, we get

ξ ⋆ 0 = λ(t 0 )h -1 V,1 (ν) , ξ ⋆ i = λ(t i )h -1 V,i+1 (ν) -λ(t i-1 )a i h -1 V,i (ν) , 1 ≤ i ≤ N -1, ξ ⋆ N = F (ν)λ(t N ) -λ(t N -1 )a N h -1 V,N (ν)
Furthermore, we note that

N � i=0 ξ ⋆ i = -� = λ(t 0 )(1 -a 1 )h -1 V,1 (ν) + . . . + λ(t N -1 )(1 -a N )h -1 V,N (ν) + F (ν)λ(t N ).
By Lemma 7.2 The right side is an increasing bijection on R, and we deduce that there is only one ν ∈ R which satisfies the above equation. This give the uniqueness of the minimizer ξ ⋆ . Moreover, the functions F -1 and h V,i vanish in 0, and ν has the same sign as -�, which gives that ξ ⋆ 0 and ξ ⋆ N have the same sign as -� by Lemma 7.2. Besides, if (7.33) holds, the trades ξ ⋆ i have also the same sign as -�. �

Let us now prepare the proof of Theorem 7.4 and assume that h V,t is bijective increasing. We introduce for 0 ≤ t ≤ T , Let us observe that ν � → � T t λ(u)ρ u h -1 V,u (ν)du + λ(T )F (ν) is increasing and bijective on R, and (7.46) admits a unique solution. The function C V (t, T, E t , X t ) denotes the minimal cost to liquidate X t shares on the time interval [t, T ] given the current state E t . In particular, we observe that

C V (t
ζ u = h -1 V,u (
C V (T, T, E T , X T ) = λ(T ) � G � E T -X T λ(T ) � -G � E T λ(T ) �� ,
which is the cost of selling X T shares at time T . Besides, an integration by parts gives that C V (0, T, 0, �) ≥ 0.

C V (t, T, E t , X t ) = -λ(t)G � E t λ(t) � + � T t λ (u)
(7.49) Formula (7.45) can be guessed by simple but tedious calculations: one has to consider the associated discrete problem on a regular time-grid and then let the time-step going to zero. We do not present these calculations here since we will prove directly by a verification argument that this is indeed the minimal cost.

Proof of Theorem 7.4: Let (X t , 0 ≤ t ≤ T +) denote an admissible strategy that liquidates �.

We consider (E t , 0 ≤ t ≤ T +) the solution of dE t = dX tρ t E t dt, ν t the solution of (7.46) and

ζ t = h -1
V,t (ν t ). We set

C t = � t 0 F -1 � E s λ(s) � dX c s + � 0≤s<t λ(s) � G � E s + ΔX s λ(s) � -G � E s λ(s) �� + C V (t, T, E t , X t ).
Let us observe that C T = C V (X) and C 0 = C V (0, T, 0, �). We are going to show that dC t ≥ 0, and that dC t = 0 holds only for X ⋆ . This will in particular show that C V (X) ≥ 0 from (7.49).

Let us first consider the case of a jump ΔX t > 0. Then, we have

ΔC t = λ(t) � G � E t + ΔX t λ(t) � -G � E t λ(t)
�� + C V (t+, T, E t+ , X t+ ) -C V (t, T, E t , X t ).

Since ΔE t = ΔX t , the solution ν t of (7.46) is also the solution of -E t+ + � T t λ(u)ρ u h -1 V,u (ν t )du + λ(T )F (ν t ) = -X t+ , and then ΔC t = 0. Now, let us calculate dC t . We set C(t, T, E t , X t , v) = λ(T )G(F (v))λ(t)G � E t λ(t)

� + � T t λ(u) � (ρ u + η u )F -1 (h -1 V,u (v))h -1 V,u (v) -η u G(h -1 V,u (v)) � du.
Then, we have from (7.48): � dν t = 0, which gives dν t = 0 since (h -1 V,u ) ′ > 0 and f > 0. Thus, we get that ν t = ν where ν is the solution of (7.35). In particular, we get ΔX 0 = E 0+ = λ(0)h -1 V,0 (0) = ΔX ⋆ 0 and then X = X ⋆ , which gives the uniqueness of the optimal strategy. Last we observe that ν has the same sign as -� and thus ξ ⋆ 0 has the same sign as -�. � Proof of Corollary 7.4: Since ρ t + η t ≥ 0 and xf ′ (F -1 (x)) ≥ 0 by Assumption 7.1, we have

dC t = F -1 � E t λ(t) � dX c t -λ ′ (t)G � E t λ(t) � dt -F -1 � E t λ(
� T t λ(u)ρ u (h -1 V,u ) ′ (v) � F -1 (h -1 V,u (v)) + ρ u + η u ρ u h -1 V,u (v) f (h -1 V,u (v)) � du = v � λ(T )f (v) + � T t λ(u)ρ u (h -1 V,u ) ′ (v)
h ′ V,t (x) = η t + 2ρ t ρ t 1 f (F -1 (x)) - η t + ρ t ρ t xf ′ (F -1 (x)) f (F -1 (x)) 3 > 0.
Also, we have sgn(x)h V,t (x) ≥ sgn(x)F -1 (x) and then sgn(x)h -1 V,t (x) ≤ sgn(x)F (x), which gives that the last trade ξ ⋆ T has the same sign as -�. Then, we have Proof. We have

(7.33) ⇔ 1 ãi 1 -ãi 1 -a i ≥ 1 -ãi+1 1 -a i+1 ⇔ (1 -a i+1 ) -ãi (1 -a i+1 ) ≥ ãi (1 -a i ) -ãi ãi+1 (1 -a i ) ⇔ ãi+1 (1 -a i ) + 1 ãi (1 -a i+1 ) ≥ 1 -a i + 1 -a i+1 .
Since ãi+1 ≤ 1, we get 1-a i +1-a i+1 = 1-a i a i+1 +(1-a i )(1-a i+1 ) ≥ 1-a i a i+1 +ã i+1 (1-a i )(1-a i+1 ).

Thus, (7.33) implies that:

ãi+1 (1 -a i ) + 1 ãi (1 -a i+1 ) ≥ 1 -a i a i+1 + ãi+1 (1 -a i )(1 -a i+1 )
⇔ 1 -ãi + a i a i+1 ãia i ãi+1 ≥ a i+1 -ãi ãi+1 a i+1 + a i ãi a i+1 ãi+1 -ãi+1 a i+1

⇔ (1 -ãi ) (1a i+1 ãi+1 ) ≥ a i+1 (1 -ãi+1 ) (1a i ãi ) ⇔ (7.23).

General limit order book shape with model P

We first focus on discrete strategies on the time grid t such as (7.14). We introduce the following shorthand notation D n = D tn for 0 ≤ n ≤ N and have

D 0 = 0, D n = a n F -1 � ξ n-1 λ(t n-1 ) + F (D n-1 ) � , 1 ≤ n ≤ N.
We can write the cost function (7.13) as follows:

C P (ξ, t) = N � n=0 λ(t n ) � D tn+ Dt n xf (x)dx = N � n=0 λ(t n ) � G � λ(t n )F (D n ) + ξ n λ(t n ) � -G(F (D n )) � .
(7.51)

We begin with the following lemmas that we use to characterize the critical points of the optimization problem.

Lemma 7.5. For i = 0, . . . , N -1, we have the following equations:

∂C P ∂ξ i = F -1 � ξ i λ(t i ) + F (D i ) � + âi+1 f (D i+1 ) f � F -1 � ξ i λ(t i ) + F (D i ) �� � ∂C P ∂ξ i+1 -D i+1 � .
Proof. First, we have ∂Dn ∂ξ i = 0 for i ≥ n, and the following recursive equations:

∂D n ∂ξ n-1 = a n λ(t n-1 )f � F -1 ( ξ n-1 λ(t n-1 ) + F (D n-1 )) � , ∂D n ∂ξ i = âi+1 f (D i+1 ) f � F -1 ( ξ i λ(t i ) + F (D i )) � ∂D n ∂ξ i+1 for 1 ≤ i ≤ n -2.
From (7.51), we get:

∂C P ∂ξ i = F -1 � ξ i λ(t i ) + F (D i ) � + N � n=i+1 � F -1 � F (D n ) + ξ n λ(t n ) � -D n � f (D n ) ∂D n ∂ξ i = F -1 � ξ i λ(t i ) + F (D i ) � + âi+1 f (D i+1 ) f � F -1 ( ξ i λ(t i ) + F (D i )) � � F -1 (F (D i+1 ) + ξ i+1 λ(t i+1 ) ) -D i+1 � + âi+1 f (D i+1 ) f � F -1 ( ξ i λ(t i ) + F (D i )) � � ∂C P ∂ξ i+1 -F -1 � ξ i+1 λ(t i+1 ) + F (D i+1 ) � �
, which gives the result.

Lemma 7.6. Under Assumption 7.2, we have that:

1. The function x � → xf (x) is increasing on R (or equivalently, F is convex).

2. We have f � x a i � -âi f (x) > 0, i = 1, . . . , N.

The function

x ∈ R, h P,i (x) = x

� 1 a i f ( x a i ) -âi f (x) � f � x a i � -âi f (x)
is well-defined, bijective increasing and satisfies sgn(x)h P,i (x) ≥ |x|.

Proof. 1. We have (xf (x)) ′ > 0 since xf ′ (x) ≥ 0 by Assumption 7.2. 2. We have for x ∈ R,

λ(t i-1 )f ( x a i ) -λ(t i )a i f (x) ≥ λ(t i-1 )f (x)(1 -âi ) > 0 because f � x a i �
≥ f (x) and âi < 1 by Assumption 7.2. 3. The function h P,i is well-defined thanks to the second point. We have sgn(x)h P,i (x) ≥ |x| since

h P,i (x) = x   1 + a -1 i 1 -âi f (x) f ( x a i )    ,
and it is sufficient to check that f (x)/f (x/a i ) is nondecreasing on R + and nonincreasing on R -. We calculate

  f (x) f � x a i �   ′ = f ′ (x)f � x a i � -1 a i f (x)f ′ � x a i � f � x a i � 2
. This is nonnegative on R + and nonpositive on R -if and only if xf ′ (x) f (x) ≥ xf ′ (x/a i ) a i f (x/a i ) for x ∈ R, which holds by Assumption 7.2 since |x| ≤ |x|/a i .

Proof of Theorem 7.5: We remark that the cost (7.51) can be written as follows:

C P (ξ, t) = λ(t N ) F � F -1 � F (D N ) + ξ N λ(t N ) �� + N -1 � n=0 λ(t n ) � F � F -1 � F (D n ) + ξ n λ(t n ) �� - λ(t n+1 ) λ(t n ) F � a n+1 F -1 � F (D n ) + ξ n λ(t n ) ��� .
Since F is convex by Lemma 7.6 and F (0) = 0, we have F (a n+1 x) ≤ a n+1 F (x), for x ∈ R and thus

C P (ξ, t) ≥ λ(t N ) F � F -1 � F (D N ) + ξ N λ(t N ) �� + N -1 � n=0 λ(t n ) F � F -1 � F (D n ) + ξ n λ(t n ) �� (1 -ân+1 ).
In particular C P (ξ, t) ≥ 0, since F ≥ 0 and ân+1 < 1 by Assumption (7.2). Besides, by setting Thus, there must be at least one minimizer of C P (ξ, t) on {ξ ∈ R N +1 , � N i=0 ξ i = -�}, and we denote by ν a Lagrange multiplier such that ∂C P ∂ξ i = ν. By Lemma 7.5 we obtain: ν = h P,i+1 (D i+1 ), i = 0, . . . , N -1.

T (ξ) =
We also have

∂C P ∂ξ N = F -1 � F (D N ) + x N λ(t N ) �
= ν, and we get (i = 1, . . . , N -1):

ξ ⋆ 0 = λ(t 0 )F � h -1 P,1 (ν) a 1 � , ξ ⋆ i = λ(t i ) � F � h -1 P,i+1 (ν) a i+1 � -F � h -1 P,i (ν) � � , ξ ⋆ N = λ(t N ) � F (ν) -F (h -1 P,N (ν)) � .
Besides, we have

λ(t N )F (ν) + N � i=1 λ(t i-1 ) � F � h -1 P,i (ν) a i � - λ(t i ) λ(t i-1 ) F (h -1 P,i (ν)) � = -�. (7.52)
Since F is increasing bijective on R and the function y � → F (y) -λ(t i ) λ(t i-1 ) F (a i y) is increasing (its derivative is positive by Lemma 7.6), there is a unique solution to (7.52), and ν has the same sign as -�. Thus ξ ⋆ is the unique optimal strategy. Moreover, the initial and the last trade have the same sign as -� since sgn(ν)h P,N (ν) ≥ |ν|.

�

We now prepare the proof of Theorem 7.6. For sake of clearness, we will work under assumption (i) and assume that ρ t � 1 + xf ′ (x) f (x) � η t > 0 for any x ∈ R and that h P,t is bijective and increasing.

However, a close look at the proof below is sufficient that the same arguments also work under assumption (ii).

Contrary to model V , it is more convenient to work with the process D rather than E (both are related by D t = F -1 (E t /λ(t)). We introduce for 0 ≤ t ≤ T , C P (t, T, D t , X Let us observe that x � → ρ u xf (x)-η u F (x) is increasing: its derivative is equal to f (x)

� ρ u � 1 + xf ′ (x) f (x) � -η u �
and is positive by assumption. Therefore, the left hand side of (7.54) is an increasing bijection on R and there is a unique solution ν to (7.54). The function C P (t, T, D t , X t ) represents the minimal cost to liquidate X t shares on [t, T ] given the current state D t . We have in particular that

C P (T, T, D T , X T ) = λ(T ) � G � E T -X T λ(T ) � -G � E T λ(T )

��

, which is the cost of selling X T shares at time T . Besides, an integration by parts gives that C P (t, T, D t , X t ) = -λ(t) F (D t ) + Proof of Theorem 7.6: Let (X t , 0 ≤ t ≤ T +) denote an admissible strategy that liquidates �.

We consider (E t , 0 ≤ t ≤ T +) the solution of dE t = dX t +η t E t dt-ρ t λ(t)f (F -1 (E t /λ(t)))F -1 (E t /λ(t))dt, D t = F -1 (E t /λ(t)), ν t the solution of (7.54) and ζ t = h -1 P,t (ν t ). We set

C t = � t 0 D s dX c s + � 0≤s<t λ(s) � G � E s + ΔX s λ(s) � -G � E s λ(s) �� + C P (t, T, D t , X t ).
Let us observe that C T = C P (X) and C 0 = C P (0, T, 0, �). We will show that dC t ≥ 0, and that dC t = 0 holds only for X ⋆ . This will in particular prove that C P (X) ≥ 0 from (7.57).

Let us first consider the case of a jump ΔX t > 0. Then, we have On the other hand, we have (ρ uη u )f (h -1 P,u (ν t )) + ρ u h -1 P,u (ν t )f ′ (h -1 P,u (ν t ))

ΔC t = λ(t) � G � E t +
∂ v C(t, T, E t , D t , v) = λ(T )vf (v) + � T t λ(u)(h -1 P,u ) ′ (v)h -1 P,u (v) � (2ρ u -η u )f (h -1 P,u (v)) + ρ u h -1 P,u (v)f ′ (h -1 P,u (v)
� du + λ(T )f (ν t ) � dν t = 0, and thus dν t = 0 since (h -1 P,u ) ′ and x � → (ρ uη u )f (x) + ρ u xf ′ (x) are positive functions by assumption. We get that ν t = ν, where ν is the solution of (7.38). In particular, we have ΔX 0 = λ(0)F (D 0+ ) = λ(0)F (h -1 P,0 (ν)) = ΔX ⋆ 0 and then X = X ⋆ . This gives the uniqueness of the optimal strategy. Last, ξ ⋆ 0 has the same sign as -� since ν and -� have the same sign. � Proof of Corollary 7.6: By Assumption 7.2 we have ρ tη t > 0, xf ′ (x) ≥ 0 and x∂ x ( xf ′ (x) f (x) ) ≤ 0, which gives:

h ′ P,t (x) = � ρ t � 2 + xf ′ (x) f (x) � -η t � � ρ t � 1 + xf ′ (x) f (x) � -η t � -ρ 2 t x∂ x ( xf ′ (x) f (x) ) � ρ t � 1 + xf ′ (x) f (x) � -η t � 2 > 0.
Also, we have sgn(x)h P,t (x) ≥ |x|, and h P,t is thus bijective on R. We deduce that sgn(x)h

  Second thème : Risque de liquidité, modélisation du carnet d'ordres, microstructure de marché Le risque de liquidité et la microstructure de marché sont devenus des sujets très importants dans les mathématiques financières. La dérégulation des marchés financiers et la compétition entre eux pour attirer plus d'investisseurs constituent une des raisons possibles. Les règles de cotation sont en train de changer et, en général, plus d'information est disponible. En particulier, il est possible de savoir à chaque instant le nombre d'ordres en attente pour certains actifs et d'avoir un historique de toutes les transactions passées. Dans ce travail, nous étudions comment utiliser cette information pour exécuter de facon optimale la vente ou l'achat des ordres. Ceci est lié au comportement des traders qui veulent minimiser leurs coûts de transaction. La structure du carnet d'ordres (Limit Order Book) est très complexe. Les ordres peuvent seulement être placés dans une grille des prix. A chaque instant, le nombre d'ordres en attente d'achat (ou vente) pour chaque prix est enregistré. Pour un prix donné, quand deux ordres se correspondent, ils sont exécutés selon une règle First In First Out. Ainsi, à cause de cette complexité, un modèle exhaustif du carnet d'ordres peut ne pas nous amener à un modèle où, par exemple, il pourrait être difficile de tirer des conclusions sur la stratégie optimale du trader. Nous devons donc proposer des modèles qui puissent capturer les caractéristiques les plus importantes de la structure du carnet d'ordres tout en restant possible d'obtenir des résultats analytiques. Dans [AFS10], Alfonsi, Fruth et Schied ont proposé un modèle simple du carnet d'ordres. Dans ce modèle, il est possible de trouver explicitement la stratégie optimale pour acheter (ou vendre) une quantité donnée d'actions avant une maturité. L'idée est de diviser l'ordre d'achat (ou de vente) dans d'autres ordres plus petits afin de trouver l'équilibre entre l'acquisition des nouveaux ordres et leur prix. Ce travail de thèse se concentre sur une extension du modèle du carnet d'ordres introduit par Alfonsi, Fruth et Schied. Ici, l'originalité est de permettre à la profondeur du carnet d'ordres de dépendre du temps, ce qui représente une nouvelle caractéristique du carnet d'ordres qui a été illustré par [JJ88, GM92, HH95, KW96]. Dans ce cadre, nous résolvons le problème de l'exécution optimale pour des stratégies discrétes et continues. Ceci nous donne, en particulier, des conditions suffisantes pour exclure les manipulations des prix au sens de Huberman et Stanzl [HS04] ou de Transaction-Triggered Price Manipulation (voir Alfonsi, Schied et Slynko). Ces conditions nous donnent des intuitions qualitatives sur la manière dont les teneurs de marché (market makers) peuvent créer ou pas des manipulations des prix.

φ

  m,i (x 1 , . . . , x d ) := d � j=1

  |k| 1 and |k| ∞ are two norms for multi-indices k = (k 1 , . . . , k d ) ∈ N d such that |k| 1 := d � j=1 |k j | and |k| ∞ := max 1≤j≤d |k j |,

t 0 S

 0 St∈[a,b]φ(S T ) , for barrier options, φ(S T , A T ), where A t = 1 t � u du, for options on the average, φ(S 1 T , S 2 T , . . . , S d T ), for a basket option,

Figure 3 .

 3 Figure3.1 shows how the algorithm approximates the basket put payoff in a two-dimensional framework (d = 2). We observe that, as the number of iterations of the greedy algorithm increases, the approximation of the function f (x 1 , x 2 ) improves.

  Fig. 3.2. Comparison between the number of fixed point iterations obtained at each PGD iteration according to the criteria (3.2) and (3.3).

  Fig. 3.3. Comparison between the number of fixed point iterations obtained at each PGD iteration according to the criteria (3.2) and (3.3).

  Points Iterations Number of Iterations of the PGD Fixed Point Iterations of a basket Put payoff with 5 assets Constant initial condition Random intial condition

Fig. 3 . 4 .

 34 Fig. 3.4. Comparison of the number of fixed point iterations needed to obtain convergence according to the election of a random or a constant initial condition in a 5 dimensional framework.

  Fig. 3.5. Comparison of the number of fixed point iterations needed to obtain convergence according to the election of a random or a constant initial condition in a 6 dimensional framework.

Figure 3 .

 3 Figure 3.6 and figure 3.7 show a comparison between the convergence curves for a basket put

Fig. 3. 6 .Fig. 3. 7 .

 67 Fig. 3.6. Comparison of the convergence curves for a basket put option with 5 assets according to the use of a random or a constant initial condition

Fig. 3. 8 .

 8 Fig.3.8. Convergence curves for the approximation of a basket put payoff by a sum of tensor products. We observe that if the dimension increases, the number of iterations needed to obtain the convergence increases as well. The error calculated is given by (3.6).

L

  Fig.3.9. Convergence curves in the L 2 and L ∞ norm for the approximation of a basket put payoff with 3 assets by a sum of tensor products.

  .11) As remarked by Pommier in [Pom08], the change of variables (4.10) maps bijectively R + to the interval [0, 1] and appears to be efficient in practice since it leads to a refined mesh around the singularity line of the payoff function. In [Pom08], Pommier explains that if we set a classical localized boundary-domain then the volume next to this singularity decays exponentially with the dimension. This change of variables allows us not to impose artificial boundary conditions contrary to classical truncation techniques. Proposition 4.1 below shows that with the change of variables (4.10), we get a well-posed problem in a bounded domain without boundary conditions.

Fig. 4. 1 .

 1 Fig.4.1. The analytical solution and the numerical one obtained with our method for the problem (4.5) with the initial condition (4.40) in a two-dimensional framework. For this example, we consider Δt = 1 100 and Δx = 1 30 .

Fig. 4. 3 .

 3 Fig. 4.2. The analytical solution and the numerical one obtained with our method for the problem (4.5) with the initial condition (4.40) in a two-dimensional framework. We represent the intersection between the surface in figure 4.1 and the plane x1 = x2. For this example, we consider Δt = 1 100 and Δx = 1 30 .

Figure 4 .Fig. 4. 4 .

 44 Figure 4.4 represents the approximation of the solution at time T to the problem (4.5) with initial condition (4.9) obtained using the PGD approximation defined by the equations (4.38) Figure 4.5 represent the price of a basket put option when all the assets take the same value, i.e. S 1 = . . . = S d . Precisely, Figure 4.5 compares prices obtained with different discretizations Δx.

Fig. 6. 1 .

 1 Fig. 6.1. Limit order book of Vodafone shares containing the shares quoted on the London Stock Exchange. Source: http://www.londonstockexchangegroup.com/investor-relations/group-at-a-glance/electronic-trading/electronictrading-main.htm

Fig. 6. 2 .

 2 Fig.6.2. Limit order book of an asset according to the model introduced by Obizhaeva and Wang in[START_REF] Obizhaeva | Optimal trading strategy and supply/demand dynamics[END_REF]. The sell and buy orders at that moment are the ask and bid sides of the book. The bid ask spread is the difference between the best ask price At and the best bid price Bt.

Fig. 6. 3 .

 3 Fig.6.3. Limit order book of an asset in the model introduced by Obizhaeva and Wang in[START_REF] Obizhaeva | Optimal trading strategy and supply/demand dynamics[END_REF]. A sell market order arrives to the limit order book and it is matched with the best prices offered in the bid part of the limit order book.

Fig. 6. 5 .

 5 Fig.6.5. Limit order book of an asset in the model introduced by Obizhaeva and Wang in[START_REF] Obizhaeva | Optimal trading strategy and supply/demand dynamics[END_REF]. When the large trader is inactive, new orders appear in between of the best ask price and the best bid price generating a new bid-ask spread.

  Potters and Bouchaud [BP03], Almgren et al. [AHLT05], Tóth et al. [BDdL + 11]

Definition 7. 3 .

 3 A model admits transaction-triggered price manipulations (TTPM) if the expected cost of a sell (buy) program can be decreased by intermediate buy (sell) trades, i.e. ∃X admissible, C(X) < inf � C( X), X is admissible and nonincreasing or nondecreasing � .

Fig. 7. 1 .

 1 Fig. 7.1. Optimal execution strategy to buy 50 shares on a regular time grid, with N = 20, ρ = 1, λ(t) = 4 + cos(2πt) (plotted in dashed line). In solid line is plotted the function t � → � ρt 2ρt+ηt � ′ + ρt � ρt+ηt 2ρt+ηt

Fig. 7. 2 .

 2 Fig. 7.2. Optimal execution strategy to buy 50 shares on a regular time grid, with N = 20, ρ = 1, λ(t) = 4 + cos(2πt) (plotted in dashed line) and γ = -0.3 (left) or γ = 1 (right). In solid line is plotted the function t � →

Fig. 7. 3 .

 3 Fig. 7.3. Optimal execution strategy to buy 50 shares on a regular time grid, with N = 20, ρ = 10, λ(t) = 4 + cos(2πt) for γ = 7/3 (left) or γ = 3/7 (right).

Fig. 7. 4 .

 4 Fig.7.4. Optimal execution strategy to buy 50 shares on a regular time grid, with N = 20, λ(t) = 4 + ε λ cos(2πt), ρ(t) = 10 + 2.5ερ cos(2πt) and γ = 1 for (ε λ , ερ) equal to (0, 0) (upper left), (1, 0) (upper right), (0, 1) (lower left) or (1, 1) (lower right).

Lemma 7. 3 .F 0 �F

 30 Let a ∈ (0, 1) and b > 0 such that ab ≤ 1. We haveG(x) -1 b G(abx) ≥ 0 for x ∈ R, and G(x) -1 b G(abx) → |x|→+∞ +∞. Proof. Since G is convex (G ′ = F -1 is increasing) and G(0) = 0, G(abx) ≤ abG(x). If b > 1, we then have G(x) -1 b G(abx) ≥ G(x)(1a) which gives the result. If b ≤ 1, we have -1 (u)du + � ax -1 (u) -F -1 (bu) � du ≥ |x|(1a)F -1 (|ax|) → |x|→+∞ ∞.



  We define the linear map T : R N +1 → R N +1 by (T ξ) n =

  ν), ξ u = λ(u)[ dζ u du + (ρ u + η u )ζ u ]. (7.47)

�

  (ρ u + η u )F -1 (ζ u )ζ uη u G(ζ u ) � du + λ(T )G(F (ν)). (7.48) The function ζ � → (ρ u + η u )F -1 (ζ)ζη u G(ζ)is nonnegative since it vanishes at 0, and its derivative is equal to ρ u h V,u (ζ) that has the same sign as ζ. Since G ≥ 0, we get:

  0 ) , D 1 + ξ 1 λ(t 1 ) , . . . , D N + ξ N λ(t N ) � , we can easily check that |T (ξ)| → |ξ|→+∞ +∞, which gives immediately that C P (ξ, t) → |ξ|→+∞ +∞ since F (x) → |x|→+∞ +∞.

ζ

  t ) = λ(t) � G(ζ t ) -F (D t ) u ξ u du + λ(T )[ F (ν) -G(ζ T )],(7.53)whereν ∈ R, s.t. -E t + (ν)f (h -1 P,u (ν))η u F � h -1 P,u (ν) �� du + λ(T )F (ν) = -X t ,(7.54) ζ u = h -1 P,u (ν), ξ u = λ(u)f (ζ u )[ dζ u du + ρ u ζ u ].(7.55)

ρ�

  u f (ζ u )ζ 2 uη u F (ζ u ) � du + λ(T ) F (ν).(7.56)The function ζ � → ρ u f (ζ)ζ 2η u F (ζ)is nonnegative: it vanishes for ζ = 0 and its derivative is equal to ζf (ζ) and has the same sign as ζ by assumption. Since F ≥ 0, this gives C P (0, T, 0, �) ≥ 0. (7.57)

  )(h -1 P,u ) ′ (v) � (ρ uη u )f (h -1 P,u (v)) + ρ u h -1 P,u (v)f ′ (h -1 P,u (v))

  . . , g n ) ∈ argmin (d 1 ,...,dn)∈D �u -P d 1 ,...,dn u� V where P d 1 ,...,dn is the orthogonal projector on Span {d 1 , . . . , d n } with respect to the inner product of

	The above algorithms are greedy since the basis of vectors used to approximate g is built incre-
	V . mentally; at each iteration a new vector is added, but former vectors are never removed nor modified.
	Instead of fixing the functions (d 1 , . . . , d n ) ∈ D as in the linear case where the best approximation is the projection P d 1 ,...,dn , the nonlinear framework lets the functions (d 1 , . . . , d n ) ∈ D depend on the function u that has to be approximated. Hence, the principle of the greedy algorithms is to look
	iteratively for the best element in the dictionary and, in this way, they propose a constructive way to
	find the solution for the problem of approximating the function u ∈ V .
	In the sequel, we assume that for any function u ∈ V , there exists an element g ∈ D such that
		g ∈ argmax d∈D	�u, d� V	(2.2)
	Thus, if g verifies (2.2), we can deduce directly that
	(g, �u, g� V ) ∈ argmin (d,λ)∈D×R	�u -λd� V .
	There are several versions of these greedy algorithms which are introduced in [DT96]. Here, we
	present two classical versions: the Pure Greedy Algorithm (PGA) and the Orthogonal Greedy Algorithm
	(OGA).
	Pure greedy algorithm (PGA):
	1. Set r p 0 := u, u p 0 := 0 and n = 1. Choose ǫ > 0.
	2. Find g p n ∈ D such that	g p n ∈ argmax g∈D	�r p n-1 , g� V
	3. Define u p n := u p n-1 + �r p n-1 , g p n � V g p n and r p n := r p n-1 -�r p n-1 , g p n � V g p n .
	4. If �r p n � ≤ ǫ�u p n �, then stop. Otherwise, n = n + 1 and return to step 2.
	Orthogonal greedy algorithm (OGA):
	1. Set r o 0 := u, u o 0 := 0 and n = 1. Choose ǫ > 0.
	2. Find g o n ∈ D such that	g o n ∈ argmax g∈D	�r o n-1 , g�.
	3. Define H o n := Span {g o i , 1 ≤ i ≤ n}, u o n := P H o n (u) and r o n := u -P H o n (u).
	4. If �r o n � ≤ ǫ�u o n �, then stop. Otherwise, n = n + 1 and return to step 2.

Table 3

 3

	Dimension Execution time in seconds with mass lumping Execution time in seconds without mass lumping
	2	1	2
	3	2	7
	4	2	18
	5	3	34
	6	4	63
	7	6	97
	8	11	167
	9	22	298
	10	80	563

.2. Execution times according to the dimension with or without mass lumping in the approximation of a basket put payoff Fig.

3

.10. Comparison between the convergence curves of a 7 asset put payoff obtained using the method with and without mass lumping In Table

3

.2, we consider only 11 points of discretization per dimension. As the number of points of discretization increases ( N > 21 points), the advantage of the mass lumping method is more obvious as we can see in Table (3.3).

Table 3

 3

.3. Execution times according to the number of discretization points when using or not mass lumping in the approximation of a basket put payoff with 5 assets

  y d )g(T, y 1 , . . . , y d |t, S 1 (t), . . . , S d (t))dy 1 . . . dy d

	(3.7)
	where (F

t ) t≥0 is the natural filtration generated by the d assets prices S i (t) (i = 1, . . . , d), f is the payoff of the option, g(T, .|t, S 1 (t), . . . , S d (t)) is the joint density of the variables S 1 (T ), . . . , S d (T )

given the values (S 1 (t), . . . , S d (t)) of the underlying assets at time t. This joint density is a log-normal law and thus has an explicit analytical expression.

Using the greedy algorithm as we saw in the previous section, we can obtain a separable approximation of the product f (y 1 , . . . , y d )g(T, y 1 , . . . , y d |t, S 1 (t), . . . , S d (t)),

Table 4

 4 Table4.1. Variance with a correlation parameter ρi,j = 0.9 constant between all the assets.

	Dimension Without variance reduction With variance reduction
	4	0.1233	0.0012
	5	0.1204	0.0034
	6	0.1197	0.0078
	7	0.1245	0.0113
	8	0.1257	0.0254
	Dimension Without variance reduction With variance reduction
	4	0.1256	0.0023
	5	0.1248	0.0045
	6	0.1230	0.0096
	7	0.1199	0.0158
	8	0.1232	0.0296

.2. Variance with a correlation parameter ρi,j = 0.1 constant between all the assets.

  Then, for any time grid (7.14), a i ãi ≤ 1 and the quadratic form (7.16) is positive semidefinite since it is a limit of positive definite quadratic forms. Thus, the model is PMS free. Conversely let us assume that 2ρ t 1 + η t 1 < 0 for some t 1 ≥ 0. Let us consider the following round trip on the time grid t = (0, t 1 , t 2 ) with t 2 > t 1 , where the large trader buys x > 0 at time t 1 and sells x at time t 2 . The cost of such a strategy is given by

		It also gives explicit
	conditions that exclude or create PMS. First, let us assume that
	∀t ≥ 0, 2ρ t + η t ≥ 0.	(7.19)

  Huberman and Stanzl if and only if (7.19) holds.

  7.2. In a block-shaped LOB, model V does not admit transaction-triggered price manipulation if and only if ∀t ≥ 0, η t + ρ t ≥ 0, and

		�	ρ t 2ρ t + η t	� ′	+ ρ t	� ρ t + η t 2ρ t + η t	�	≥ 0.	(7.22)
	The first condition comes from the last trade and implies (7.19) since ρ t ≥ 0. It can be interpreted similarly as condition (7.19) from market makers' point of view. The second condition in (7.22) comes
	from the intermediate trades and brings on the derivatives of ρ and η. It is harder to get an intuitive
	idea of its meaning from a market maker's point of view. Last, let us mention that we can show that
	the optimal strategy on the discrete time-grid (7.14) is made with nonnegative trades if one has (7.17)
	and	1

  -ηs dsIt does not admit transaction-triggered price manipulation if and only if ∀t ≥ 0, ρ tη t ≥ 0, and� ρ tη t 2ρ tη tThe first condition in (7.30) comes from the initial trade while the second comes from intermediate trades. From market makers' point of view, (7.29) and the first condition in (7.30) give different conclusions from model V . A significant market maker will not create manipulation strategy if he puts orders at a better price (which increases ρ) or cancels orders at existing prices (which decreases η).Instead, he may create manipulation strategies if he piles orders at existing prices, or if he cancels orders that are among the best offers. The second condition of (7.30) brings on the dynamics of η and ρ and it is more difficult to give its heuristic meaning in terms of trading. Last, let us mention that the optimal strategy in discrete time given by Theorem 7.2 is made only with trades of same sign

	if, and only if, one has (7.26) and
	1 -âi+1 1 -a i+1 âi+1	≥ a i	1 -âi 1 -a i âi	, ∀i ∈ {1, . . . , N -1} and â1 < 1.	(7.31)
	7.2.2 Results for general limit order book shape
					� .
	Corollary 7.3. In a block-shaped LOB, model P does not admit price manipulation in the sense of
	Huberman and Stanzl if and only if
			∀t ≥ 0, 2ρ t -η t ≥ 0.		(7.29)
				� ′	+ ρ t	� ρ t -η t 2ρ t -η t	�	≥ 0.	(7.30)

  1 for model V . This choice is different from the one made in Alfonsi et al.[START_REF] Alfonsi | Optimal execution strategies in limit order books with general shape functions[END_REF][START_REF] Alfonsi | Optimal trade execution and absence of price manipulations in limit order book models[END_REF]. It is in fact Looking at the proofs, we can observe that the optimal strategy ξ ⋆ given by Theorem 7.5 (resp. 7.3), if it is well-defined, is still a critical point of the cost function when Assumption 7.2 (resp. 7.1) does not hold. Of course, this is not enough to conclude that ξ ⋆ is a global minimizer, but indicates that ξ ⋆ is a good candidate for that. Another way to avoid Assumption 7.2 (resp. 7.1) is to work in continuous time and check directly the hypothesis of Theorem 7.6 (resp. 7.4). Under Assumption 7.2, the cost function C P (ξ, t) is nonnegative, and there is a unique optimal execution strategy ξ ⋆ that minimizes C P over {ξ ∈ R N +1 ,

	Theorem 7.5. � N i=0 ξ i = -�}. This strategy is given as follows. The following equation
	N

more tractable from a mathematical point of view, especially here with a time-varying LOB. Let us stress here that Assumption 7.2 (resp. Assumption 7.1) is a condition under which we are able to run the proof for the discrete time optimization of the price (resp. volume) reversion models. From a practical point of view, it may seem too restrictive or unrealistic. However, these conditions are sufficient but not necessary.

  , T, E t , X t ) = λ(t) (ζ u )ξ u du + λ(T )[G(F (ν)) -G(ζ T )], (7.45) where ν ∈ R, s.t. -E t +

	� T t F -1 � T t λ(u)ρ u h -1 V,u (ν)du + λ(T )F (ν) = -X t ,	(7.46)

� G(ζ t ) -G � E t λ(t) �� +

  t) � (dX c t -(ρ t + η t )E t dt) -λ(t)(ρ t + η t )F -1 (ζ t )ζ t dt + λ ′ (t)G(ζ t )dt + ∂ C ∂v (t, T, E t , X t , ν t )dν t .

	Since

� λ(T )f (ν t ) + � T t λ(u)ρ u (h -1 V,u ) ′ (ν t )du � dν tλ(t)ρ t h -1 V,t (ν t )dt = d(E t -X t ) = -ρ t E t dt and ∂ v C(t, T, E t , X t , v) = λ(T )vf (v) +

  F -1 (ζ) + ρ t h V,t (ζ) + ρ t h ′ V,t (ζ)(ζ -Et λ(t) ) = ρ t h ′ V,t (ζ)(ζ -Et λ(t) ). Since h ′ V,t > 0, ψ t vanishes at ζ = Et λ(t), and is positive for ζ � = Et λ(t) . Thus, if X is an optimal strategy, we necessarily have ζ t = Et λ(t) , dt-a.e. Then, we get by differentiating

	� E t λ(t)	F -1	� E t λ(t)	� ζ t -	E t λ(t)
			ζ
			f (F -1 (ζ))

du � , we finally get

dC t = λ(t) � (ρ t + η t ) � ζ t F -1 (ζ t ) � + η t � G(ζ t ) -G � E t λ(t) �� + ρ t h V,t (ζ t ) �� dt := λ(t)ψ t (ζ t )dt. (7.50) We have ψ ′ t (ζ) = -(ρ t + η t ) � F -1 (ζ) + � + η t � X t -E t + � T t λ(u)ρ u h -1 V,u (ν t )du + λ(T )F (ν t ) � = 0 that � � T t λ(u)ρ u (h -1 V,u ) ′ (ν t )du + λ(T )f (ν t )

  -1 (ζ t )) + (ρ t + η t )h ′ V,t (ζ t ) ρ ′ t η tρ t η ′ t ρ t + (ρ t + η t )(2ρ t + η t ) (η t + ρ t ) 2 ρ t ζ t f ′ (ζ t ) f (F -1 (ζ t )) 3 � is nonnegative if (7.22) holds since h ′ V,t > 0 and ζ t f ′ (ζ t ) ≥ 0. � Lemma 7.4. We have (7.33) =⇒ (7.23) if ρ t + η t ≥ 0, t ≥ 0.

	ξ ⋆ t =	h ′ V,t (ζ t ) λ(t)ζ t	�
	=	λ(t)ζ t h ′ V,t (ζ t )
			dζt dt = -1 h ′ V,t (ζt)	dh V,t dt (ζ t ) and thus

� -d (η t /ρ t ) dt 1 f (F � 1 ρ t f (F -1 (ζ t )) � � -

  ΔE t = ΔX t , we have ν t = ν t+ from (7.54) and then ΔC t = 0 since F (D t ) = G(E t /λ(t)). Now, let us calculate dC t . We setC(t, T, D t , X t , v) = λ(T ) F (v)λ(t) F (D t ) + Since dD c t = -ρ t D t dt + (Dt), we have from (7.56):dC t = D t dX c tλ ′ (t) F (D t )dt + λ(t)ρ t f (D t )D 2 t dt -D t dX c tλ(t)[ρ t f (ζ t )ζ 2 tη t F (ζ t )]dt T, D t , X t , ν t )dν t . Since d(E t -X t ) = λ(t) [η t F (D t )ρ t D t f (D t )] dt, we get from (7.54)

	Since � T t	λ(u)	�	ρ u f (h -1 P,u (v))h -1 P,u (v) 2 -η u F (h -1 P,u (v))
	dX c t λ(t)f + ∂ C ∂v (t, � � T t λ(u)(h -1 P,u ) �	dν t	(7.58)
	-λ(t)

ΔX t λ(t) � -G � E t λ(t) �� + C P (t+, T, D t+ , X t+ ) -C P (t, T, D t , X t ). � du. ′ (ν t ) � (ρ uη u )f (h -1 P,u (ν t )) + ρ u h -1 P,u (ν t )f ′ (h -1 P,u (ν t )) � du + λ(T )f (ν t ) � ρ t h -1 P,t (ν t )f (h -1 P,t (ν t ))η t F � h -1 P,t (ν t ) �� dt = λ(t) [η t F (D t )ρ t D t f (D t )] dt.

  We have ψ t (D t ) = 0 and get thatψ ′ t (ζ) = h ′ P,t (ζ) [η t (F (D t ) -F (ζ)) + ρ t (ζf (ζ) -D t f (D t ))] by simple calculations. On the one hand, we have h ′ P,t (ζ) > 0. On the other hand, the bracket is positive on ζ > D t and negative on ζ < D t since its derivative is equal to (ρ tη t )f (ζ) + ρ t ζf (ζ), which is positive by assumption. Thus, D t is the unique minimum of ψ t : ψ t (D t ) = 0 andψ t (ζ) > 0 for ζ � = D t .Thus, if X is an optimal strategy, we necessarily have ζ t = D t , dt-a.e. From (7.58), we get

	�	� T t	λ(u)(h -1 P,u ) ′ (ν t )

∂ C ∂v (t, T, D t , X t , ν t )dν t = λ(t)ν t [η t (F (D t )-F (ζ t ))+ρ t (ζ t f (ζ t )-D t f (D t ))].

We finally obtain:

dC t = λ(t)ψ t (ζ t )dt, with (7.59) ψ t (ζ) = η t ( F (ζ) -F (D t )) + ρ t (D 2 t f (D t )ζ 2 f (ζ)) + h P,t (ζ) (η t (F (D t ) -F (ζ)) + ρ t (ζf (ζ) -D t f (D t ))) .

�

  -1 P,t (x) ≤ |x|, which gives that the last trade ξ ⋆ T has the same sign as -�. Let us assume moreover that (7.30) holds. Let γ t =

												λ(t)f (ζt)ζt � P,t (ζt) h ′ 1+ ζ t f ′ (ζ t ) f (ζ t ) -	ρ t η t	� 2 > 0. Then,
	ξ t = γ t	� ρ ′ t η t -ρ t η ′ t ρ 2 t	+ ρ t	� 1 +	ζ t f ′ (ζ t ) f (ζ t )	-	η t ρ t	� � 2 +	ζ t f ′ (ζ t ) f (ζ t )	-	η t ρ t	�	-ζ t ∂ x (	f (x) xf ′ (x)	)| x=ζt	�
	≥ γ t	� ρ ′ t η t -ρ t η ′ t ρ 2 t	+ ρ t	� 1 -	η t ρ t	� � 2 -	η t ρ t	��	by Assumption 7.2.
	= γ t
																	�

� 2ρ tη t ρ t � 2 �� ρ tη t 2ρ tη t � ′ + ρ t � ρ tη t 2ρ tη t ��

≥ 0 by (7.30).

Approximation of high-dimensional functions and the pricing problem

A nonlinear approximation method for solving high-dimensional partial differential equations

Application in Finance of a nonlinear approximation method for solving high-dimensional partial differential equations

Survey on market impact models

Optimal execution and price manipulations in time-varying limit order books

and

B is a tridiagonal matrix of size N + 1 × N + 1 such that:

C is also a tridiagonal matrix of size N + 1 × N + 1 such that:

We do not develop the expression of the right hand side of the equation (4.38) because its terms can be obtained using the same matrices B, C, D, L and M .

Part II

Liquidity risk, limit order book modeling and market microstructure

Here, we get back their result and extend it to general LOB shapes and thus nonlinear price impact.

The other contribution of this paper is that we solve the optimal execution in a continuous time setting while [AFS10, AS10] mainly focus on discrete time strategies. This is in particular much more suitable to state the conditions that exclude price manipulations.

7.1 Market model and the optimal execution problem

The model description

The problem that we study in this paper is the classical optimal execution problem. To deal with this problem, we consider in this paper a framework which is a natural extension of the model proposed in Alfonsi, Fruth and Schied [START_REF] Alfonsi | Optimal execution strategies in limit order books with general shape functions[END_REF] and developed by Alfonsi and Schied [AS10] and Predoiu, Shaikhet and Shreve [START_REF] Predoiu | Optimal execution in a general one-sided limitorder book[END_REF]. The additional feature that we introduce here is to allow a time varying depth of the order book. We consider a large trader who wants to liquidate a portfolio of � shares in a time period of [0, T ]. In order to liquidate these � shares, the large trader uses only market orders, that is buy or sell orders that are immediately executed at the best available current price. Thus, our large trader cannot put limit orders. A long position � > 0 will correspond to a sell program while a short position � < 0 will stand for a a buy strategy. The optimal execution problem consists in finding the optimal trading strategy that minimizes the expected cost of the large trader.

We assume that the price process without the large trader would be given by a rightcontinuous martingale (S 0 t , t ≥ 0) on a given filtered probability space (Ω, (F t ), F, P). The actual price process (S t , t ≥ 0) that takes into account the trades of the large trader is defined by:

Thus, the process (D t , t ≥ 0) describes the price impact of the large trader. We also introduce the process (E t , t ≥ 0) that describes the volume impact of the large trader. If the large trader puts a market order of size ξ t (ξ t > 0 is a buy order and ξ t < 0 a sell order), the volume impact process changes from E t to:

When the large trader is not active, its volume impact E t goes back to 0. We assume that it decays exponentially with a deterministic time-dependent rate ρ t > 0 called resilience, so that we have:

We now have to specify how the processes D and E are related. To do so, we suppose a continuous distribution buy and sell limit orders around the unaffected price S 0 t : for x ∈ R, we assume that the