Keywords: Howard's algorithm (policy iterations), primal-dual active set algorithm, semi-smooth Newton's method, super-linear convergence, double-obstacle problem, slant differentiability

This paper deals with convergence results of Howard's algorithm for the resolution of min a∈A (B a x -b a ) = 0 where B a is a matrix, b a is a vector (possibly of infinite dimension), and A is a compact set. We show a global super-linear convergence result, under a monotonicity assumption on the matrices B a .

In the particular case of an obstacle problem of the form min(Ax -b, x -g) = 0 where A is an N × N matrix satisfying a monotonicity assumption, we show the convergence of Howard's algorithm in no more than N iterations, instead of the usual 2 N bound. Still in the case of obstacle problem, we establish the equivalence between Howard's algorithm and a primal-dual active set algorithm (M. Hintermüller et al., SIAM J. Optim., Vol 13, 2002, pp. 865-888). We also propose an Howard-type algorithm for a "double-obstacle" problem of the form max(min(Ax -b, x -g), x -h) = 0.

We finally illustrate the algorithms on the discretization of nonlinear PDE's arising in the context of mathematical finance (American option, and Merton's portfolio problem), and for the double-obstacle problem.

Quelques résultats de convergence pour l'algorithme de Howard Résumé : Nous étudions des résultats de convergence pour l'algorithme de Howard appliqué à la résolution du problème min a∈A (B a x -b a ) = 0 où B a est une matrice, b a est un vecteur (éventuellement de dimension infinie), et A est un ensemble compact. Nous obtenons une convergence surlinéaire, sous une hypothèse de monotonie des matrices B a . Dans le cas particulier d'un problème d'obstacle de la forme: min(Ax -b, x -g) = 0 où A est une matrice N × N monotone, nous prouvons que l'algorithme de Howard converge en N itérations. De plus, nous établissons l'équivalence entre l'algorithme de Howard et la méthode primal-dual (M. Hintermüller et al., SIAM J. Optim., Vol 13, 2002, pp. 865-888). Nous étendons aussi l'algorithme de Howard à la résolution du problème de double obstacle de la forme: max(min(Ax -b, x -g), x -h) = 0.

Des tests numériques sont aussi réalisés pour l'approximation d'équations aux dérivées partielles provenant de la finance (option américaine, optimisation de portefeuille), et d'un problème de double obstacle.

Mots-clés : algorithme d'Howard (itérations sur les politiques), algorithme primal-dual, méthode de Newton semi-lisse, convergence surlinéaire, problème de double obstacle

Introduction

The aim of this paper is to study the convergence of Howard's algorithm (also known as the "policy iteration algorithm") for solving the following problem:

Find x ∈ X, min a∈A (B a x -b a ) = 0, ( 1
)
where A is a non empty compact set, and for every a ∈ A, B a is a monotone matrix and b a ∈ X (here either X = R N for some N ≥ 1, or X = R N * ). Problems such as (1) come tipically from the discretization of Hamilton-Jacobi-Bellman equations [START_REF] Chancelier | Combined stochastic control and optimal stopping, and application to numerical approximation of combined stochastic and impulse control[END_REF], or from the discretization of obstacle problems.

In general, two methods are used to solve [START_REF] Achdou | Computational methods for option pricing[END_REF]. The first one is a fixed point method called "value iterations algorithm". Each iteration of this method is cheap. However, the convergence is linear and one needs a large number of iterations to get a reasonable error. The second method, called policy iteration algorithm, or Howard's algorithm, was developped by Bellman [START_REF] Bellman | Functional equations in the theory of dynamic programming. v. positivity and quasi-linearity[END_REF][START_REF] Bellman | Dynamic programming[END_REF] and Howard [START_REF] Howard | Dynamic programming and Markov processes[END_REF].

Here, we prove that (when A is a compact set) Howard's algorithm converges superlinearly. To obtain this result, we use an equivalence with a semi-smooth Newton's method.

Puterman and Brumelle [START_REF] Puterman | On the convergence of policy iteration in stationary dynamic programming[END_REF] were among the first to analyze the convergence properties for policy iterations with continuous state and control spaces. They showed that the algorithm is equivalent to a Newton's method, but under very restrictive assumptions which are not easily verifiable. Recently, Rust and Santos [START_REF] Santos | Convergence properties of policy iteration[END_REF] obtained local and global super-linear convergence results for Howard algorithm applied to a class of stationary infinite-horizon Markovian decision process (under additional regularity assumptions, the authors even obtain up to quadratic convergence; see also [START_REF] Santos | Accuracy of numerical solutions using the Euler equation residuals[END_REF]).

In the first part of this paper, we give a simple proof for the global super-linear convergence. We recall also that when X = R N (for some N ≥ 1), and when A is finite, then Howard's algorithm converges in at most (Card(A)) N iterations.

In the second part of the paper, we focalize our attention to the finite dimensional obstacle problem. More precisely, we are interested by the following problem (for N ≥ 1):

find x ∈ R N , min(Ax -b, x -g) = 0, ( 2
)
where A is a monotone N × N matrix (see Definition (2.2)), b and g in R N . This problem can be written in the form of (1), with Card(A) = 2. We prove that a specific formulation of Howard's algorithm for problem [START_REF] Akian | On an investment-consumption model with transaction costs[END_REF] converges in no more than N iterations, instead of the expected 2 N bound. We also show that Howard's algorithm is equivalent to the primal-dual active set method for (2), studied in [START_REF] Hintermuller | The primal-dual active set strategy as a semismooth newton method[END_REF][START_REF] Bergounioux | Primal dual strategy for constrained optimal control problems[END_REF][START_REF] Ito | Optimal control of elliptic variational inequalities[END_REF]. Using the equivalence of the algorithms, we also conclude that the primal-dual active set method converges in no more than N iterations. Let us briefly outline the structure of the paper. In Section 2 some notations and preliminary results are given. In Section 3 we prove the equivalence between Howard's algorithm and a semi-smooth Newton's method, and then the super-linear convergence. Section 4 is devoted to the analysis of the obstacle problem, and the equivalence between Howard's algorithm and the primal-dual active set method. In section 5 we study a policy iteration algorithm for the following double obstacle problem (for N ≥ 1):

find x ∈ R N , max(min(Ax -b, x -g), x -h) = 0.
and give also a convergence result in finite number of iterations.

Finally in Section 6 we present some numerical applications. In the context of mathematical finance, the above algorithms are applied to the resolution of implicit schemes for non-linear PDE's, in the case of the American option and for Merton's portfolio problem. The convergence for a double-obstacle problem is also illustrated and compared with a more classical "Projected Successive Over Relaxation" algorithm.

Notations and preliminaries

In all the sequel, X denotes either the finite dimensional vector space R N for some N ≥ 1, or the infinite dimensional vector space R N * . We consider the set of matrices M defined as follows:

M := R N ×N (if X = R N ), or M := R N * ×N * (if X = R N *
). We will also use the notation

I := {1, • • • , N } (if X = R N ), or I := N * (if X = R N * ).
Let (A, d) be a compact (metric) set. For each a ∈ A, the notations b a and B a will refer respectively to a vector in X and a matrix in M associated to the variable a.

Throughout all the paper, we fix two real numbers p, q ∈ [1, ∞] such that 1 p + 1 q = 1, and use the following norms:

• For x ∈ X, x p := i∈I |x i | p 1/p (if p < ∞) and x ∞ := sup i∈I |x i |. • For A ∈ M, we denote A q,∞ := max i∈I j∈I |A ij | q 1/q (if q < ∞), A ∞,∞ := sup i,j∈I |A ij |, A 1,p := i∈I j∈I |A ij | p 1/p (if p < ∞).
We also denote ℓ p := {x ∈ X, x p < ∞} , and M q,∞ := {A ∈ M, A q,∞ < ∞} .

For every x, y ∈ X, we use the notation y ≥ x if y i ≥ x i , ∀i ∈ I. We also denote x ≥ 0 if x i ≥ 0, ∀i ∈ I, and min(x, y) (resp. max(x, y)) denotes the vector with components min(x i , y i ) (resp. max(x i , y i )).

Also if (x a ) a∈A is a bounded subset of X, we denote min We consider the problem to find x ∈ X, solution of equation ( 1):

min a∈A B a x -b a = 0. Let A ∞ := A N if X = R N , or A ∞ := A N * if X = R N * ,
endowed with the topology such that

α k k→+∞ -----→ α in A ∞ , if α k i k→+∞ -----→ α i for all i ∈ I.
Remark 2.1 For α = (a i ) i∈I ∈ A ∞ , we denote B(α) and b(α) the matrice and vector such that B i,j (α) := B ai i,j and b i (α) = b ai . Then we notice that (1) is equivalent to the following equation:

find x ∈ X, min α∈A∞ B(α)x -b(α) = 0, (3)
because in (3) the ith row is a minimisation over a i (the ith component of α) only.

We consider the following assumption:

(H1) α ∈ A ∞ -→ B(α) ∈ M q,∞ and α ∈ A ∞ -→ b(α) ∈ ℓ ∞ are continuous.
In order to give a general existence result, we use here the concept of "monotone" matrices.

Definition 2.2 We say that a matrix

A ∈ M is monotone if A has a continuous left inverse 1 and ∀x ∈ X, Ax ≥ 0 ⇒ x ≥ 0.
In the finite dimensional case, A is monotone if and only if A is invertible and A -1 ≥ 0 (componentwise).

In this paper, we also assume that: (H2) ∀α ∈ A ∞ , B(α) is monotone. (H3) In the case when X = R N * , we have:

ε J := sup α∈A∞ max i≥1 |j-i|≥J |B ij (α)| q 1/q J→+∞ -----→ 0, if q < ∞, or ε J := sup α∈A∞ max i≥1, |j-i|≥J |B ij (α)| J→∞ ----→ 0, if q = ∞.
In the finite dimensional case (i.e, X = R N for some N ≥ 1), assumption (H3) is not needed. On the other hand, when q < ∞, (H3) is equivalent to sup

a∈A max i≥1 |j-i|≥J |B a ij | q 1/q J→∞ ----→ 0.
1 That is, there exists C ≥ 0, for any y ∈ ℓ ∞ , there exists x ∈ ℓ p such that Ax = y and x p ≤ C y ∞ .

RR n 0123456789

Remark 2.3 Assumption (H3) is obviously satisfied whenever there exists some K ≥ 0 such that for every α ∈ A ∞ , B(α) is a K-band matrix (i.e., ∀α, B ij (α) = 0 if |j -i| > K).

Remark 2.4 Also we notice that assumption (H1) is satisfied if (for instance) we have:

(i) for every i, j ∈ I, the function a ∈ A -→ B a ij is continuous, (ii) In the case X = R N * , assumption (H3) holds, and

η I := sup a∈A max i≥I, j≥I |B a ij | I→+∞ -----→ 0.
Howard's algorithm (Ho-1) Howard's algorithm for (3) can be defined as follows:

Initialize α 0 in A ∞ , Iterate for k ≥ 0: (i) find x k ∈ X solution of B(α k )x k = b(α k ). If k ≥ 1 and x k = x k-1 , then stop. Otherwise go to (ii). (ii) α k+1 := argmin α∈A∞ B(α)x k -b(α) .
Set k := k + 1 and go to (i).

Under assumption (H2), for every α ∈ A ∞ , the matrix B(α) is monotone, thus the linear system in iteration (i) of Howard's algorithm is well defined and has a unique solution

x k ∈ X.
It is known that Howard's algorithm is convergent [START_REF] Bonnans | Commande et optimisation de systèmes dynamiques[END_REF]. In our setting, we have the following result. Theorem 2.5 Assume that (H1)-(H3) hold. Then there exists a unique x * in ℓ p solution of (3). Moreover, the sequence (x k ) given by Howard's algorithm (Ho-1) satisfies (i) x k ≤ x k+1 for all k ≥ 0. (ii) x k → x * pointwisely. (i.e., ∀i ∈ I, lim k→∞

x k i = x * i ). (iii) If A is finite and X = R N , (Ho-1) converges in at most (Card(A)) N iterations (ie, x k is a solution for some k ≤ (Card(A)) N ).
We shall indeed prove in the next section that we have the stronger global convergence result (Theorem 3.4): lim k→∞ x k -x * p = 0, and lim

k→∞ x k+1 -x * x k -x * = 0.
Proof. We start by checking uniqueness. Let x and y two solutions of (3), and let ᾱ ∈ A ∞ be a minimizer associated to y:

ᾱ := argmin α∈A∞ (B(α)y -b(α)) . INRIA Then B(ᾱ)y -b(ᾱ) = min α∈A∞ (B(α)y -b(α)) = 0 = min α∈A∞ (B(α)x -b(α)) ≤ B(ᾱ)x -b(ᾱ).
Hence B(ᾱ)(y -x) ≤ 0, and by using (H2), we get that y ≤ x. With the same arguments, we prove also that y ≥ x. Therefore, we have y = x which proves the uniqueness result.

To prove that (x k ) k is an increasing sequence, we use:

B(α k+1 )x k -b(α k+1 ) = min α∈A∞ (B(α)x k -b(α)) ≤ B(α k )x k -b(α k ) = 0 = B(α k+1 )x k+1 -b(α k+1 ).
Then by the monotonicity assumption (H2) we obtain the result. We now prove that x k converges pointwisely towards some x * ∈ ℓ p . By the step (i) of the Howard algorithm we have andA ∞ is a compact. This implies, with the inequality (4), that (x k ) k is bounded in ℓ p . Hence x k converges pointwisely toward some x * ∈ ℓ p . Let us show that x * is the solution of (3). Define the function F for x ∈ X by: F (x) := min α∈A∞ (B(α)x -b(α)), and let F i (x) be the

x k p ≤ B -1 (α k )b(α k ) p ≤ max α∈A∞ B -1 (α) 1,p b(α) ∞ . ( 4
) Since α -→ B(α) is continuous and for every α ∈ A ∞ , B(α) is invertible, then α -→ B -1 (α) is also continuous. Moreover, α -→ b(α) is continuous,
ith component of F (x), i.e. F i (x) = min α∈A∞ B(α)x -b(α) i .
In the case when X = R N it is obvious that lim

k→+∞ F i (x k ) = F i (x *
). Now consider the case when X = R N * and assume that q < ∞ (the same following arguments hold also for q = +∞). For a given i ≥ 1, and for any J ≥ 1, we have:

|F i (x k ) -F i (x * )| ≤ max α∈A j≥1 |B ij (α)||x k j -x * j | ≤ max α∈A |j-i|≥J |B ij (α)| q 1/q |j-i|≥J |x k j -x * j | p 1/p + max α∈A |j-i|<J |B ij (α)||x k j -x * j | ≤ ε J x k -x * p + ε 1 |j-i|<J |x k j -x * j |,
where ε J , ε 1 are defined as in (H3). Hence lim sup

k→∞ |F i (x k ) -F i (x * )| ≤ ε J (max k x k p + x * p ), (5)
for all J ≥ 0. By using (H3), we conclude that:

lim k→+∞ F i (x k ) = F i (x * ), ∀i ≥ 1.
By the compactness of A and using a diagonal extraction argument, there exists a subsequence of (α k ) k denoted α φ k , that converges toward some α ∈ A ∞ . Furthermore, we have:

B(α k )x k i -B(α)x * i ≤ 2ε J + |j-i|<J B(α k ) ij x k j -B(α) ij x * j ,
and with assumption (H3), it yields: lim

k→∞ (B(α k )x k ) i -(B(α)x * ) i = 0. Passing to the limit in (B(α φ k )x φ k -b(α φ k )) i = 0, we deduce that (B(α)x * -b(α)) i = 0, for all i ∈ I.
On the other hand we have also

F i (x * ) = lim k→∞ F i (x φ k -1 ) = lim k→+∞ B(α φ k )x φ k -1 -b(α φ k ) i = [B(α)x * -b(α)] i .
Hence F i (x * ) = 0, which concludes the proof of (ii) and implies also that x * is a solution of (3).

To prove (iii) we first notice that there is at most (Card(A) N ) different variables α ∈ A ∞ . Then there exist two indices k, ℓ such that 0 ≤ k < ℓ ≤ (Card(A) N ) and α k = α ℓ (α k and α ℓ being respectiveley the kth and ℓth iterate of the Howard's algorithm). Hence x ℓ = x k , and since x k ≤ x k+1 ≤ • • • ≤ x ℓ we obtain also that x k = x k+1 . Therefore, Howard's algorithm stops at the (k + 1)th iteration, and x k+1 = x k is the solution of (3).

Superlinear convergence

First let us prove that Howard's algorithm for problem (3) is a semi-smooth Newton's method applied to find the zero of the function F : ℓ p → ℓ ∞ defined by

F (x) := min α∈A∞ (B(α)x -b(α)). (6)
For k ≥ 0, by definitions of α k+1 and x k (the kth iterate of the Howard's algorithm), we have

B(α k+1 )x k -b(α k+1 ) = F (x k ), and B(α k+1 )x k+1 -b(α k+1 ) = 0. Therefore, B(α k+1 )(x k -x k+1 ) = F (x k
), and thus

x k+1 = x k -B(α k+1 ) -1 F (x k ). ( 7
)

INRIA

The equation ( 7) can be interpreted as an iteration of a semi-smooth Newton's method, where B(α k+1 ) plays the role of a derivative of F at point x k . In order to prove the superlinear convergence, we shall prove that F is slantly differentiable in the sense of [

F(x + h) = F(x) + G(x + h)h + o(h) as h → 0, ∀x ∈ U . G is called a slanting function for F in U .
Let us denote α(x) an optimal minimizer associated to F (x), i.e., α(x) := argmin α∈A∞ (B(α)x -b(α)), and let A x ∞ be the set of the optimal minimizers associated to F (x), i.e.,

A x ∞ := α ∈ A ∞ , B(α)x -b(α) = B(α(x))x -b(α(x)) .
For every i ∈ I, we also define the set A x i of the optimal minimizers associated to the ith component of min α∈A∞ (B(α)x -b(α)), i.e.,

A x i := a ∈ A, B a x -b a i = B(α(x))x -b(α(x)) i .
With these notations, it is clear that

A x ∞ = i∈I A x i (see remark 2.1).
We first prove the following Lemma.

Lemma 3.2 Assume that (H1) holds. For every x ∈ X and for all i ∈ I,

d(α i (x + h), A x i ) → 0 as h ∈ ℓ p and h p → 0,
where α i (x + h) denotes the ith component of an optimal minimizer α(x + h).

Proof. Suppose on the contrary that there exists some δ > 0 and a subsequence h n ∈ ℓ p , with h n p → 0, such that d(

α i (x + h n ), A x i ) ≥ δ, ∀n ≥ 0. Let K δ := {a ∈ A, d(a, A x i ) ≥ δ}, the function f : A -→ R defined by f (a) := B a x -b a i , and m δ := inf a∈K δ f (a). We note that K δ is a compact set, hence m δ = f (ā) for some ā ∈ K δ . In particular ā / ∈ A x i and thus m δ = f (ā) > f (α i (x)). On the other hand, α i (x + h n ) ∈ K δ . Thus f (α i (x + h n )) -f (α i (x)) ≥ f (ā) -f (α i (x)) > 0. ( 8
)
Let C := max α∈A∞ B(α) q,∞ . We have that

F (y) -F (z) ∞ ≤ C y -z p for every y, z ∈ ℓ p . Moreover, (F (x + h) -F (x)) i = f (α i (x + h)) -f (α i (x)) + (B(α(x + h))h) i . Hence f (α i (x + h)) -f (α i (x)) ≤ 2C h p .
Taking h := h n → 0 we obtain a contradiction with [START_REF] Bonnans | Commande et optimisation de systèmes dynamiques[END_REF].

The previous Lemma leads to the following result. Proof. In the case when X = R N (for some N ≥ 1), the theorem is a simple consequence from Lemma 3.2. To prove the assertion when X = R N * , we proceed as follows. Let x, h be in ℓ p .

From the definition of F , we have for any α ∈ A x ∞ :

F (x) + B(α(x + h))h ≤ F (x + h) ≤ F (x) + B(α)h,
and thus

0 ≤ F (x + h) -F (x) -B(α(x + h))h ≤ (B(α) -B(α(x + h)))h ≤ B(α) -B(α(x + h)) q,∞ h p . (9)
Suppose that q < ∞ (the arguments are similar when q = +∞), and let J ≥ 1. We have:

B(α) -B(α(x + h)) q,∞ ≤ max i≥1 |j-i|<J B ij (α) -B ij (α(x + h)) q 1/q + 2ε J .
By Lemma 3.2 there exist α h ∈ A x ∞ such that d(α h j , α j (x + h)) → 0 as h p → 0, for all j ≤ J. Thus, by continuity, lim

h p →0 max i |j-i|<J B ij (α h ) -B ij (α(x + h)) q 1/q = 0. Hence lim sup h→0 B(α h ) -B(α(x + h)) q,∞ ≤ 2ε J .
Since the result is true for any J ≥ 1, letting J → ∞ and using assumption (H3), we obtain

lim h→0 B(α h ) -B(α(x + h)) q,∞ = 0, (10)
and this concludes the proof.

The slant differentiability of F is usefull to obtain the local super-linear convergence of the semi-smooth Newton's method defined by

x k+1 = x k -G(x k ) -1 F (x k ) (see [10, Theorem 1.1]
). We will also prove the global superlinear convergence of Howard's algorithm by using the concavity of F .

INRIA

Theorem 3.4 Assume that (H1)-(H3) are satisfied. Then (3) has a unique solution x * ∈ ℓ p , and for any initial iterate α 0 ∈ A ∞ , Howard's algorithm converges globaly super-linearly, i.e., lim k→∞ x k -x * p = 0 and

x k+1 -x * p = o x k -x * p , as k → ∞.
Proof. Existence and uniqueness of the solution, as well as the increasing property of the sequence x k have already been proved in Theorem 2.5.

There remains to show the super-linear convergence. We consider h k := x k -x * and denote α k+1 := α(x k ) = α(x * + h k ). As in the proof of Lemma 3.2, for all k ≥ 0, we can find α k, * ∈ A x * such that

B(α k+1 ) -B(α k, * ) → 0 as k → ∞. ( 11
)
Using the concavity of the function F and the fact that F (x * ) = 0 we obtain F (x k ) ≤ B(α k+1 )(x k -x * ) (indeed for any α ∈ A x * , i.e. an optimal minimizer associated to x * , we have

F (x) ≤ F (x * ) + B(α)(x -x * ) = B(α)(x -x * )).
Hence, by monotonicity of B(α k+1 ),

x k+1 = x k -B(α k+1 ) -1 F (x k ) ≥ x k -B(α k+1 ) -1 B(α k, * )(x k -x * ),
and thus

0 ≥ x k+1 -x * ≥ (I -B(α k+1 ) -1 B(α k, * ))(x k -x * ). (12)
By Theorem 3.3 and (H1), we obtain

I -B(α k+1 ) -1 B(α k, * ) k→+∞ -----→ 0 (we also use the fact that B -1 (α) is bounded on A). Hence ∃K ≥ 0, ∀k ≥ K, I -B(α k+1 ) -1 B(α k, * ) ≤ 1 2 .
We first deduce from ( 12) that x k+1 -x * p ≤ 1 2 x k -x * p and the global convergence. Then using again [START_REF] Ito | Optimal control of elliptic variational inequalities[END_REF], we obtain

0 ≥ x k+1 -x * ≥ o(x k -x * ),
and this concludes the proof of super-linear convergence.

Remark 3.5 The proof of the super-linear convergence is strongly dependent on the fact that F is concave.

Remark 3.6

The assertions of the theorems 2.5 and 3.4 also hold for the problem

find x ∈ X, min α∈ Q i∈I Ai (B(α)x -b(α)) = 0.
where A i are non empty compact sets.

Remark 3.7 (quadratic convergence in the case X = R N ) Note that stronger convergence results can be obtained under an additional assumption on the dependance of f (x, α) := B(α)x -b(α) with respect to α (as in [START_REF] Santos | Convergence properties of policy iteration[END_REF]). For instance assume that X = R N , A is a compact interval of R, and that for all

1 ≤ i ≤ N , f i (x, α) = r i (x)α 2 i + s i (x)α i + t i (x) (i.e
. quadratic in α i ), with r i (x) > 0, ∀x ∈ R N , and with r i (x) and s i (x) Lipschitz functions of x (see the exemple of Section 6.2). In this case, for every x ∈ X, a minimizeer α x is given by α x i := argmin αi∈A f i (x, α) = P A (-si(x) 2ri(x) ) where P A denotes the projection on the interval A. Hence in the neighborhood of the solution x * , we obtain that α x -α x * ≤ C x -x * (for some C > 0). This implies also that B(α x ) -B(α x * ) ≤ C x -x * , and using [START_REF] Ito | Optimal control of elliptic variational inequalities[END_REF] this leads to a global quadratic convergence result. [START_REF] Bellman | Functional equations in the theory of dynamic programming. v. positivity and quasi-linearity[END_REF] The obstacle problem, and link with the primal-dual active set strategy

We consider the following equation, called "obstacle problem" (for N ≥ 1):

find x ∈ R N , min(Ax -b, x -g) = 0, ( 13
)
where A ∈ R N ×N and b, g ∈ R N are given. Equation ( 13) is a particular case of (1), with A = {0, 1}, B 0 = A, B 1 = I N (I N being the N × N identity matrix), b 0 = b, and b 1 = g. Also it is a particular case of (3), with

B ij (α) := A ij if α i = 0 δ ij if α i = 1, and b i (α) := b i if α i = 0 g i if α i = 1, (14)
where δ ij = 1 if i = j, and δ ij = 0 if i = j.

Remark 4.1 With the notations [START_REF] Ito | Parabolic variational inequalities: the lagrange multiplier approach[END_REF], assumption (H1) is obviously satisfied since A is finite, the Howard's algorithm converges in at most 2 N iterations under assumption (H2).

Remark 4.2 In the particular case when A = tridiag(-1, 2, -1), A is monotone and one can show that (H2) is satisfied. Also, if A is a matrix such that any submatrix of the form (A ij ) i,j∈I where I ⊂ {1, . . . , N } is monotone, and with A ij ≤ 0 ∀i = j, then (H2) also holds. Also, if A is a strictly dominant M -matrix of R N ×N (i.e., A ij ≤ 0 ∀j = i, and ∃δ > 0, ∀i,

A ii ≥ δ + j =i |A ij |) then (H2
) is true (since all B(α) are all strictly dominant M -matrices, and are thus monotone).

We now consider the following specific Howard's algorithm for equation [START_REF] Ito | Semi-smooth newton methods for variationnal inequalities of the first kind[END_REF]:

Algorithm (Ho-2) Initialize α 0 in A N := {0, 1} N . Iterate for k ≥ 0: INRIA (i) Find x k ∈ R N s.t. B(α k )x k = b(α k ).
If k ≥ 1 and x k = x k-1 then stop. Otherwise go to (ii).

(ii) For every i = 1, ..., N , take

α k+1 i := 0 if (Ax k -b) i ≤ (x k -g) i 1 otherwise. Set k := k + 1 and go to (i).
Let us remark that in the case when (Ax k -b) i = (x k -g) i , we make the choice α k+1 i = 0. In the following we show that this choice leads to a drastic improvement in the convergence of Howard's algorithm.

Theorem 4.3 Assume that the matrices B(•) defined in ( 14) satisfy (H2). Then Howard's algorithm (Ho-2) applied to (13) converges in at most N + 1 iterations (i.e, x k = x k+1 for some k ≤ N + 1). In the case we start with α 0 i = 1, ∀i = 1, • • • , N , the convergence holds in at most N iterations (i.e, x k = x k+1 for some k ≤ N ).

Note that taking α 0 i = 1, for every 1 ≤ i ≤ N , implies that x 0 = g and hence the step k = 0 has no cost. The cost of the N iterations really means a cost of N resolutions of linear systems (from k = 1 to k = N ).

Proof of Theorem 4.3. First, remark that x 1 ≥ g. Indeed,

• if α 1 i = 1, then we have (x 1 -g) i = 0 (by definition of x 1 ).

• if α 1 i = 0, then (Ax 0 -b) i ≤ (x 0 -g) i .
Furthermore one of the two terms (Ax 0 -b) i or (x 0 -g) i is zero, by definition of x 0 . Hence (x 0 -g) i ≥ 0, and (x 1 -g) i ≥ 0.

We also know, by theorem 2.5, that x k+1 ≥ x k . This concludes to:

∀k ≥ 1, x k ≥ g. (15)
Now if α k i = 0 for some k ≥ 1 then (Ax k -b) i = 0 and by [START_REF] Lamberton | Introduction au calcul stochastique appliqué à la finance[END_REF] we deduce that α k+1 i = 0. This proves that the sequence (α k ) k≥1 is decreasing in A N . Also, it implies that the set of points

I k := {i, (Ax k -b) i ≤ (x k -g) i } satisfies I k ⊂ I k+1 , for k ≥ 0.
Since Card(I k ) ≤ N , there exists a first index k ∈ [0, N ] such that I k = I k+1 , and we have α k+1 = α k+2 . In particular, F (x k+1 ) = B(α k+2 )x k+1 -b(α k+2 ) = B(α k+1 )x k+1 -b(α k+1 ) = 0, and thus x k+1 is the solution for some k ≤ N . This makes at most N + 1 iterations.

In the case α 0 i = 1, ∀i, we obtain that (α k ) k≥0 is decreasing. Hence there exists a first index k ∈ [0, N ] such that α k = α k+1 , and we obtain F (x k ) = 0. This is the desired result. Now, we consider the algorithm (Ho-2') which is a variant of Howard's algorithm (Ho-2) and defined as follows: we start from a given x 0 , and then compute α 1 (by step (ii)) and x 1 (by step (i)), then α 2 and x 2 , and so on, untill x k = x k-1 . For (Ho-2'), we have a specific result, that will be usefull when studing the approximation for American options in Section 6.

Theorem 4.4 Assume that the matrices B(•) defined in (14) satisfy (H2). Assume that x 0 satisfies, ∀i,

x 0 i > g i ⇒ (Bx 0 -b) i ≤ 0. ( 16
)
Then the iterates of (Ho-2') satisfy x k+1 ≥ x k for all k ≥ 0, and the convergence is in at most N iterations (i.e., x k for some k ≥ N is solution).

Remark 4.5 Note that the assumption ( 16) is satisfied in the following cases: (i) x 0 is such that min(Bx 0 -b 0 , x 0 -g) = 0 for some b 0 ≤ b.

(ii) x 0 ≤ g.

Proof of Theorem 4.4

The only difficulty is to prove that x 1 ≥ x 0 , otherwise the proof is the same as in Theorem 4.3. First in the case α 1 i = 1, we have

x 1 i = g i and (Bx 0 -b) i ≥ (x 0 -g) i . If (x 0 -g) i > 0 then (Bx 0 -b) i > 0,
which contradicts the assumption on x 0 . Hence x 0 i ≤ g i and thus

x 0 i ≤ x 1 i . Otherwise in the case α 1 i = 0, we have(Bx 0 -b) i < (x 0 -g) i and (Bx 1 -b) i = 0. If (Bx 0 -b) i > 0 then (x 0 -g) i > 0,
which contradicts the assumption on x 0 . Hence (Bx 0 -b) i ≤ 0. In particular, (Bx 0 ) i ≤ (Bx 1 ) i . In conclusion, we have the vector inequality B(α 1 )x 0 ≤ B(α 1 )x 1 . This implies that x 0 ≤ x 1 using the monotonicity of B(α 1 ). Remark 4.6 A similar algorithm as (Ho-2) can be built for the equivalent problem

min(Ax -b, C(x -g)) = 0, where C = diag(c 1 , . . . , c N ) is a diagonal matrix with c i > 0, for i = 1, • • • , N .
Moreover, in the particular case when c i = c > 0 for i = 1, • • • , N , the Howard's algorithm is equivalent to the primal-dual active set method of Hintermüller, Ito and Kunisch [START_REF] Hintermuller | The primal-dual active set strategy as a semismooth newton method[END_REF] as explained below.

It is well known that, for a given c > 0, x is a solution of (3) if and only if there exists

λ ∈ R N + such that Ax -λ = b C(x, λ) = 0, (17)
where

C(x, λ) := min(λ, c(x -g)) = λ -max(0, λ -c(x -g)).
(note also that λ = P [0,+∞) (λ -c(x -g))). The idea developed in [START_REF] Hintermuller | The primal-dual active set strategy as a semismooth newton method[END_REF] is to use C(x, λ) = 0 as a prediction strategy as follows.

Primal-dual active set algorithm Initialize x 0 , λ 0 ∈ R N . Iterate for k ≥ 0:

INRIA (i) Set I k = {i : λ k i ≤ c(x k -g) i }, AC k = {i : λ k i > c(x k -g) i }. If k ≥ 1 and I k = I k-1 then stop. Otherwise go to (ii). (ii) Solve Ax k+1 -λ k+1 = b, x k+1 = g on AC k , λ k+1 = 0 on I k .
set k = k + 1 and return to (i).

The sets I k and AC k are called respectively the inactive and active sets. Note that the algorithm satisfies at each step, λ k+1 = Ax k+1 -b, and λ k+1 i = (Ax k+1 -b) i = 0 for i ∈ I k , and (x k+1 -g) i = 0 for i ∈ AC k . This is equivalent to say that

Bx k+1 -b = 0, ( 18
)
where

B i,. := A i,. if (Ax k -b) i ≤ c(x k -g) i cI N i,. otherwise, b i := b i if (Ax k -b) i ≤ c(x k -g) i cg i otherwise.
(I N denotes the N × N identity matrix.) Let us consider the equivalent formulation min(Ax -b, Cx -Cg) = 0, with C = diag(c, . . . , c) (by Remark 4.6), and let B(.) and b(.) be defined as in [START_REF] Ito | Parabolic variational inequalities: the lagrange multiplier approach[END_REF]. For k ≥ 0, if we set α k+1 i := 0 for i ∈ I k and α k+1 i := 1 otherwise, then we find that α k+1 is defined from x k , as in Howard's algorithm, and we have B = B(α k+1 ), b = b(α k+1 ). Therefore, ( 18) is equivalent to B(α k+1 )x k+1 -b(α k+1 ) = 0, and x k+1 is defined as in Howard's algorithm applied to min(Ax -b, Cx -Cg) = 0.

Theorem 4.7 Howard's algorithm (Ho-2) and primal-dual active set algorithm for the obstacle problem are equivalent: if we choose λ 0 := Ax 0 -b initially then the sequences (x k ) generated by both algorithms are the same for k ≥ 0.

Remark 4.8 By Theorem 4.3, the primal-dual active set strategy converges also in no more that N iterations (taking x 0 = g). This analysis gives an other justification for the small number of iterations needed in the computations done by Ito and Kunisch in [START_REF] Ito | Semi-smooth newton methods for variationnal inequalities of the first kind[END_REF].

In the same way, one can see that the Front-Traking algorithm proposed in [1, Chapter 6.5.3] for a particular obstacle problem and based on the primal-dual active set method, is equivalent to the Howard's algorithm.

where A and B denote two non empty compact sets. We denote by B(α, β) the matrices such that B(α, β) ij := B αi,βi ij for all α = (α i ) ∈ A N and β = (β i ) ∈ B N , and c(α, β) i := c αi,βi . Let F β (x) := min α∈A N B(α, β)x -c(α, β). Then we can consider the following Howard's algorithm:

Algorithm (Ho-4). Consider a given β 0 ∈ B N . Iterate for k ≥ 0:

(i) Find x k such that F β k (x k ) = 0 (resolution at fixed β k ). If k ≥ 1 and x k = x k-1 then stop. Otherwise, go to (ii). (ii) For i = 1, • • • , N , set β k+1 i = argmax βi∈A (F β (x k ) i ).
Set k := k + 1 and go to (i).

The following result can be obtained using the same argument as used in the paper (the proof is left to the reader).

Theorem 5.4 Assume that (α, β) → B(α, β) is continuous, and that all matrices B(α, β) are monotone. Then the min-max problem (23) admits a unique solution. Furthermore, the algorithm (Ho-4) satisfies x k ≥ x k+1 . If B is finite, then the convergence is obtained in at most Card(B) N iterations of the algorithm (Ho-4) (i.e., x k is a solution for some k ≤ Card(B) N ).

Applications

An American option

In this section we consider the problem of computing the price of an American put option in mathematical finance. The price u(t, s) for t ∈ [0, T ] and s ∈ [0, S max ] is known to satisfy the following non-linear P.D.E (see [START_REF] Lamberton | Introduction au calcul stochastique appliqué à la finance[END_REF] or [START_REF] Pham | Optimal stopping, free boundary, and American option in a jump-diffusion model[END_REF] for existence and unicity results in the viscosity framework):

min ∂ t u - 1 2 σ 2 s 2 ∂ ss u -rs∂ s u + ru, u -ϕ(x) = 0, t ∈ [0, T ], s ∈ (0, S max ), (24a) u(t, S max ) = 0, t ∈ [0, T ], (24b)
u(0, s) = ϕ(s), x ∈ (0, S max ). (24c)
where σ > 0 represents a volatily, r > 0 is the interest rate, ϕ(s) := max(K -s, 0) is the "Payoff" function (where K > 0, is the "strike"). The bound S max should be S max = ∞, for numerical purpose we consider S max > 0, large, but finite. Let s j = jh with h = S max /N s and t n = nδt with δt = T /N , where N ≥ 1 and N s ≥ 1 are two integers. Suppose we want to implement the following simple Implicit Euler (IE) scheme with unknown (U n j ):

min U n+1 j -U n j δt - 1 2 σ 2 s 2 j (D 2 U n+1 ) j h 2 -rs j D + U n+1 j h + rU n+1 j ; U n+1 j -g j = 0, j = 0, . . . , N s -1, n = 0, . . . , N -1, U n+1 Ns = 0, n = 0, . . . , N -1, U 0 j = g j , j = 0, . . . , N s -1
where (D 2 U ) j and (D + U ) j are the finite differences defined by

(D 2 U ) j := U j-1 -2U j + U j+1 , (D + U ) j := U j+1 -U j ,
and with g j := ϕ(s j ). Note that for j = 0 the scheme is simply

min U n+1 0 -U n 0 δt + rU n+1 0 , U n+1 0 -g 0 = 0.
(More accurate schemes can be considered, here we focus on the simple (IE) scheme for illustrative purpose mainly.) It is known that the (IE) scheme converges to the viscosity solution of (24) when δt, h → 0 (one may use for instance the Barles-Souganidis [START_REF] Barles | Convergence of approximation schemes for fully nonlinear second order equations[END_REF] abstract convergence result and monotonicity properties of the scheme). The motivation for using an implicit scheme is for unconditional stability. 3Now for n ≥ 0, we set b := U n . Thus, the problem to find x = U n+1 ∈ R Ns (i.e, x = (U n+1 0 , . . . , U n+1

Ns-1 ) T ) can be written equivalently as min(Bx -b, x -g) = 0, where B = I + δtA and A is the matrix of R Ns such that for all j = 0, . . . , N s -1:

(AU ) j = - 1 2 σ 2 s 2 j U j+1 -2U j-1 + U j+1 h 2 -rs j U j+1 -U j h + rU j ,
(assuming U Ns = 0). Then one can see that B is an M -matrix, hence (H2) is satisfied and we can apply Howard's algorithm and generate a sequence of approximations (x k ) (for a given step n of the (IE) scheme). We choose to apply the algorithm (Ho-2') with starting point x 0 := U n . For each n ∈ [0, . . . , N -1], Howard's algorithm may need up to N s iterations and the total number of Howard's iterations (for the (IE) scheme) is thus bounded by N × N s . This can be improved as follows.

Proposition 6.1 The total number of Howard's iterates (using algorithm (Ho-2')) from n = 0 up to n = N -1, is bounded by N s . On other words, the resolution of (IE) scheme uses no more than N s resolution of linear systems.

Proof. Step 1. First let us notice that that for each fixed n, x = U n+1 is the solution of min(Bx -b, x -g) where b = U n . Furthermore, let us show that U n+1 ≥ U n by recursion. For n = 0, we have U 1 ≥ g = U 0 . For n ≥ 1, let us assume that U n ≥ U n-1 . We know that BU n+1 -b ≥ 0, hence BU n+1 ≥ U n ≥ U n-1 . On the other hand, U n+1 ≥ g. Hence x = U n+1 satisfies min(Bx -U n-1 , x -g) ≥ 0. This means that U n+1 is a super-solution of min(Bx -U n-1 , x -g) = 0 (whose solution is U n ). Hence U n+1 ≥ U n .

Step 2. Then for each fixed n, the iterates (x k ) of the algorithm (Ho-2') applied to min(Bx -b, x -g) = 0 (where b = U n ) and starting from x 0 := U n form an increasing sequence. This is a consequence of Theorem 4.4 applied with b 0 := U n-1 .

Step 3. Now for each n, the number of Howard's iterations is bounded by p n := Card(j, U n+1 j > g j ) -Card(j, U n j > g j ). To see this, let m k := Card(j, x k j > g j ) -Card(j, x 0 j > g j ) for k ≥ 0 and n fixed. Since (x k ) ր, we have also (m k ) ր, bounded by p n . However in the case m k+1 = m k , and since (x k ) ր, then {i,

x k+1 i > g i } = {i, x k i > g i }.
In particular α k+1 = α k and x k+1 = x k , and the algorithm has converged at iteration k ≤ p n .

As a consequence, the total number of Howard's iterates is bounded by n=0,...,N -1 p n = Card(j, U N j > g j ) -Card(j, U 0 j > g j ), which is bounded by N s . This simple remark is particularly interesting for more complex American options, such as American options on two assets (involving a P.D.E in two space dimension). It can be used to prove that the number of iterates of an Howard algorithm for an implicit scheme can be bounded (in some situations) by the number of points which are inactive in the final solution and thus by the total number of spatial grid points used in the scheme.

We finally mention that in [START_REF] Ito | Parabolic variational inequalities: the lagrange multiplier approach[END_REF] (see also [START_REF] Achdou | Computational methods for option pricing[END_REF]), the Primal-Dual active set algorithm is used for the approximation of an American option (in a Finite element setting), and convergence in a finite number of iterations is also observed even though the matrices involved are not necessarily monotonous matrices.

Compact control set: Merton's problem

Howard's algorithm can be useful for the computation of the value functions of optimal control problems. We consider the following example, also known as Merton's problem in mathematical finance [START_REF]Stochastic differential equations[END_REF] (see for instance [START_REF] Mnif | Optimal risk control and dividend policies under excess of loss reinsurance[END_REF] or [START_REF] Bokanowski | Numerical approximation of a superreplication problem under gamma constraints[END_REF] for recent applications of Howard's algorithm to solve non-linear equations arising in finance). The problem is to find the optimal value for a dynamic portofolio. At a given time t, the holder may invest a part of the portfolio into a risky asset with interest rate µ > 0 and volatily σ > 0, and the other part into a secure asset with interest rate r > 0. The value u = u(t, s), for t ∈ [0, T ] and s ∈ [0, S max ], is a solution of the following PDE:

min α∈A ∂ t u - 1 2 σ 2 α 2 s 2 ∂ ss u -(αµ + (1 -α)r)x∂ s u = 0, t ∈ [0, T ], s ∈ (0, S max ), (25a) u
(0, s) = ϕ(s), s ∈ (0, S max ). (25b)
where A := [a min , a max ], S max = +∞, and K > 0 is the strike (see for instance Oksendal [START_REF]Stochastic differential equations[END_REF]). Existence and uniqueness results can be obtained using [START_REF] Pham | Optimisation et Contrôle Stochastique Appliqués à la Finance[END_REF].

In general the exact solution is not known. For testing purposes, we consider here the particular case of ϕ(x) = x p for some p ∈ (0, 1). In this case, the analytic solution (when S max = +∞) is known to be u(t, x) := e αopt t ϕ(x) where

α opt := max α∈A - 1 2 p(1 -p)α 2 + (αµ + (1 -α)r)p
(the constant α opt can be computed explicitly since the functional is quadratic in α).

For numerical purpose we consider the problem on a bounded interval [0, S max ] with a finite, large, S max . In this case we need to add a boundary condition at s = S max for completness of the problem. Since (x p ) ′ x p = p x , we consider the following mixed boundary condition:

∂ x u(t, S max ) = p S max u(t, S max ), t ∈ [0, T ]. ( 26
)

INRIA

A natural IE scheme for the set of equations ( 25)-( 26) is:

min α∈A U n+1 j -U n j δt - 1 2 σ 2 s 2 j α 2 U n+1 j-1 -2U n+1 j + U n+1 j+1 h 2 -(αµ + (1 -α)r)s j U n+1 j+1 -U n+1 j h = 0, j = 0, . . . , N s , n = 0, . . . , N -1, U n+1 Ns -U n+1 Ns-1 h = p S max U n+1
Ns , n = 0, . . . , N -1, U 0 j = ϕ(s j ), j = 0, . . . , N s .

Note that for j = 0 the scheme simply reads

U n+1 0 -U n 0 δt = 0.
Now for b := U n given (and for a given time iteration n ≥ 0), the computation of

x = U n+1 ∈ R Ns+1 (i.e, x = (U n+1 0 , . . . , U n+1 Ns ) T ) is equivalent to solve min α∈A (B α x -b) = 0,
where B α := I + δtA α and A α is the matrix of R (Ns+1)×(Ns+1) such that, for all j = 0, . . . , N s -1,

(A α U ) j = - 1 2 σ 2 s 2 j α 2 U j-1 -2U j-1 + U j+1 h 2 -(αµ + (1 -α)r)s j U j+1 -U j h , and
(A α U ) Ns = 1 2 σ 2 x 2 Ns α 2 h 2 -U Ns-1 + (1 - hp Smax 1 -hp Smax )U Ns -(αµ + (1 -α)r)x Ns p S max U Ns .
We obtain the monotonicity of the matrices B α under a CFL-like condition on δt, h. 4 Remark 6.2 Here the CFL condition comes from the mixed boundary condition and only plays a role on the last row of the matrices B α (for monotonicity of B α ). Note also that it is of the form δt h ≤ const (when h is small), which is less restrictive than the CFL condition we could obtain with an explicit scheme (it would of the form δt h 2 ≤ const). 4 Chose h > 0 and δt > 0 such that, for h small:

δt h max α 1 2 σ 2 x 2 Ns α 2 p Smax 1 -hp Smax + h 2 p Smax (αµ + (1 -α)r) ! ≤ 1.

RR n 0123456789

In view of the expression of (B α x) j for a given x, which is quadratic in α, the second step of Howard's algorithm can always be performed analytically (otherwise a minimizing procedure should be considered). This improves considerably the speed for finding the optimal control α (this step has a negligeable cputime with respect to the first step of Howard's algorithm where a linear system must be solved). Remark 6.3 Here we obtain that α j := argmin α∈A (B α x) j is defined by α j = P A (µ -r)d

(1) j σ 2 s j d

(2) j , for 0 < j < N s , where d

(1)

j := Uj+1-Uj h , d (2) j :
= -Uj-1+2Uj -Uj+1 h 2
(in the case d

(2) j = 0), and where P A is the projection on the interval A.

We give in Fig. 2 the approximated solution and the associated numerical control obtained with the IE scheme. In this example, the exact optimal control is α opt = 5 (constant). yet with an approximated control set. Here we can work directly with the control set A and take advantage of super linear convergence (at each time step). Furthermore, using Remark 3.7 the convergence can be shown to be quadratic. Remark 6.5 At each step we have to solve a sparse linear system. Here the system is tridiagonal and thus can be solved in O(N ) elementary operations. More generally, multigrid methods can be considered (see for instance [START_REF] Akian | On an investment-consumption model with transaction costs[END_REF])

Double obstacle problem

We consider the following discrete double obstacle problem: find

U = (U i ) 1≤i≤N in R N such that            max min - U i-1 -2U i + U i+1 ∆s 2 + m(s i ), U i -g(s i ), , U i -h(s i ) = 0, i = 1, . . . , N U 0 = u ℓ , U N +1 = u r , (27)
with u ℓ = 1, u r = 0.8 (left and right border values), ∆s = 1 N +1 and s i = i∆s, m(s) ≡ 0, g(s) := max(0, 1.2 -((s -0.6)/0.1) 2 ) and h(s) := min(2, 0.3 + ((s -0.2)/0.1) 2 ).

This problem can easily be reformulated as [START_REF] Pham | Optimisation et Contrôle Stochastique Appliqués à la Finance[END_REF] and with A, a tridiagonal N × N matrix. Note that this problem comes from the approximation by finite differences of the following continuous double-obstacle problem: find u(s) such that    min -u ′′ (s) + m(s), u(s) -g(s) , u(s) -h(s) = 0, s ∈ (0, 1), u(0) = u g , u(1) = u d .

We compare two algorithms. The first one is an analog of the PSOR algorithm for obstacle problem (see for instance [START_REF] Achdou | Computational methods for option pricing[END_REF]) and that we recall in the appendix. The second one is the Howard algorithm (Ho-3). Note that at each step of (Ho-3), the Howard's algorithm (Ho-2) is also used to compute x k such that F β k (x k ) = 0.

The results are shown in Fig. 3. The left figure shows x k at iteration k = 200 for the PSOR algorithm, where convergence is not yet obtained, and the right figure shows Howard's algorithm at iteration k = 14, where convergence has been reached (here this corresponds to a total number of 88 resolutions of linear systems).

10 ,

 10 Definition 1]. Definition 3.1 (Slant differentiability) Let Y and Z be two Banach spaces. A function F : Y → Z is said slantly differentiable in an open set U ⊂ Y if there exists a familly of mappings G : U → L(Y, Z) such that

Theorem 3 . 3

 33 We assume that (H1)-(H3) hold. The function F defined in (6) is slantly differentiable on ℓ p , with slanting function G(x) = B(α(x)).

Figure 1 :

 1 Figure 1: Plot of U n j and U n+1 j (time t n = 0.2) with respect to s j . Parameters: K = 100, σ = 1, r = 0.1, T = 1, S max = 200, N s = 50, N = 10.

Figure 2 :Remark 6 . 4

 264 Figure 2: Plot of (U N j ) (left) and of the discrete optimal control (α j ) at time t N = 1 (right), with respect to s j . Parameters: S max = 2, A = [0.4, 0.6], p = 1 2 , σ = 0.2, r = 0.1, µ = 0.2, T = 1, and N s = 200, N = 20.

Figure 3 :

 3 Figure 3: PSOR (left, with k = 200 iterations) and Howard's algorithm (right, with k = 14 iterations) for the double obstacle problem with N = 99. Values U n j are plotted with respect to s j .

INRIA

RR n 0123456789

An explicit scheme would need a condition of the form δt h 2 ≤ const in order to be stable.INRIA

Acknowldement. The Authors deeply thank Professor F. Bonnans for interesting discussions and comments on the manuscript.

Double obstacle problem

In this section we consider the problem to find x ∈ R N solution of the following "double obstacle problem": max (min (Ax -b, x -g) , x -h) = 0, [START_REF] Pham | Optimisation et Contrôle Stochastique Appliqués à la Finance[END_REF] (the equation must hold for each component) where A is a given matrix of R N ×N , and b, g, h are in R N . We aim to solve [START_REF] Pham | Optimisation et Contrôle Stochastique Appliqués à la Finance[END_REF] by a policy iteration algorithm converging in at most N 2 resolutions of linear systems. Define the functions F and G on R N by: F (x) := min(Ax -b, x -g), and G(x) := max(F (x), x -g) for x ∈ R N .

The problem [START_REF] Pham | Optimisation et Contrôle Stochastique Appliqués à la Finance[END_REF] is then equivalent to find x ∈ R N solution of G(x) = 0. We first re-write the function F as follows:

where A = {0, 1}, and B(α) is defined as in ( 14):

with δ ij = 1 if i = j, and δ ij = 0 otherwise. In the sequel, we consider that the matrices B(α) satisfy the assumption (H2) (see remark 4.2). Also we define, for every

We obtain easily that for every x ∈ R N , we have G(x) = max β∈A N F β (x), and the problem [START_REF] Pham | Optimisation et Contrôle Stochastique Appliqués à la Finance[END_REF] is equivalent to:

To solve this problem, we consider the following policy iteration algorithm:

Set k := k + 1 and go to (i).

INRIA

Note that, for every k ≥ 0, the equation F β k (x) = 0 is a simple obstacle problem in the form of [START_REF] Ito | Semi-smooth newton methods for variationnal inequalities of the first kind[END_REF]. The resolution in step (i) of the above algorithm could be performed with the Howard's algorithm (Ho-2) in at most N resolution of linear systems. On other hand, the step (ii) corresponds to the computation of a specific element of argmax βi∈A (F β (x k ) i ).

In order to study this algorithm, we start with the following preliminary results.

Proposition 5.1 Assume that the matrices B(α) satisfy the assumption (H2). Then the following assertions hold:

(ii) G is also monotone.

Proof. Throught this part, for x ∈ R N we denote α x ∈ A N a minimizer associated to F (x) defined by:

(i) Let x, y be in R N and such that F (x) ≤ F (y). We have:

Taking into account the monotonicity of B(α x ), we get x ≤ y.

We now prove the monotonicity of F β , for β ∈ A N . We assume that

Hence (B(α x )x) i ≤ (B(α x )y) i .

• On the other hand, for i such that β i = 1, we have (x -h) i ≤ (y -h) i and thus x i ≤ y i . Now let ᾱ ∈ A N be defined by ᾱi := 0 if β i = 0 and α x i = 0 1 otherwise. We see that if β i = 0 and α x i = 0 then

and otherwise, (B(ᾱ)x

Hence B(ᾱ)x ≤ B(ᾱ)y and thus x ≤ y using the monotonicity of B(ᾱ). 2 We say that a function f :

RR n 0123456789

(ii) We assume G(x) ≤ G(y). In view of [START_REF] Santos | Accuracy of numerical solutions using the Euler equation residuals[END_REF], let β y be such that G(y) = F βy (y). In particular,

Using the monotonicity of F βy , we obtain x ≤ y.

Now we can prove the main result of this section Theorem 5.2 Assume (H2'). Then there exists a unique solution of [START_REF] Pham | Optimisation et Contrôle Stochastique Appliqués à la Finance[END_REF], and algorithm (Ho-3) converges in at most N + 1 iterations. It converges in at most N iterations if we start with β 0 i = 1, ∀i. Proof. We proceed as for the proof of Theorem 4.3. The uniqueness of the solution is obtained by the monotonocity of the function G.

Now we analyse the algorithm. First we note that

Then we prove that

It suffices to prove that x 1 -h ≤ 0. In the case β 1 i = 1, we have (x 1 -h) i = 0 (by definition of x 1 ). In the case β 1 i = 0, we have F (x 0 ) i ≥ (x 0 -h) i . Furthermore one of the two terms is zero, by definition of x 0 . Hence (x 0 -h) i ≤ 0, and (x 1 -h) i ≤ 0. This concludes to [START_REF] Santos | Convergence properties of policy iteration[END_REF]. Now if β k i = 0 for some k ≥ 1 then F i (x k ) = 0 and using that (x k -h) i ≤ 0 we deduce that β k+1 i = 0. This proves that the sequence (β k ) k≥1 is decreasing in A N . The set of points

, and we have β k+1 = β k+2 . In particular, G(x k+1 ) = F β k+2 (x k+1 ) = F β k+1 (x k+1 ) = 0, which means that x k+1 is the solution. This makes a maximum of k + 1 iterations, bounded by N + 1.

In the case β 0 i = 1, ∀i, we obtain that (β k ) k≥0 is decreasing. Hence there exists a first index k ∈ [0, N ] such that β k = β k+1 , and we obtain that G(x k ) = 0 and a maximum of N iterations.

Finally, this also implies the existence of a solution of G(x) = 0, which concludes the proof.

Remark 5.3 Since each resolution of F β k (x) = 0 can be solved by Howard's algorithm using at most N iterations (i.e, resolution of linear systems), this means that the global algorithm converges in at most N 2 resolution of linear systems.

We conclude this section by an extention to a more general max-min problem. Let B a,b be a set of N × N real matrices and c a,b a set of vectors of R N , and we consider the problem of finding x ∈ R N solution of

INRIA

A PSOR algorithm for double-obstacle problem

In the case A is a triangular inferior matrix with A ii > 0, the problem has a unique solution given by:

Let us denote by x = q L (b) the result of the above algorithm. In the general case, we can consider the following iterative algorithm (which is a modification of the PSOR algorithm): we first decompose A = L + U where U is the strictly triangular superior part of A.

-start with a given x 0 in R N , -iterate for k ≥ 0:

The second step is equivalent to find x k+1 such that:

Then we have:

) and with positive diagonal coefficients (A ii ≥ 0, ∀i). There exists a unique solution to problem [START_REF] Pham | Optimisation et Contrôle Stochastique Appliqués à la Finance[END_REF], and the adapted PSOR algorithm converges to the solution. Furthermore the convergence is linear.

INRIA

Proof. The proof is similar to the proof of the PSOR algorithm (see for instance [START_REF] Achdou | Computational methods for option pricing[END_REF]). One can show that x → q L (b


Masato Nakaya

Yuji Okawa

Christian Joachim

Masakazu Aono

Tomonobu Nakayama
email: nakayama.tomonobu@nims.go.jp

Nanojunction between Fullerene and One-Dimensional Conductive Polymer on solid surfaces

Keywords: Fullerene, polymer, STM, molecular electronics, heterojunction

Nanojunction between fullerene and one-dimensional conductive polymer on solid surfaces

Construction of electronics from only molecule-based components is one of the ultimate goals in the recent molecular science and technology. [START_REF] Joachim | Electronics Using Hybrid-Molecular and Mono-Molecular Devices[END_REF][START_REF] Donhauser | Conductance Switching in Single Molecules Through Conformational Changes[END_REF][START_REF] Tao | Electron Transport in Molecular Junctions[END_REF][START_REF] Song | Single Molecule Electronic Devices[END_REF] Since the individual organic molecules behave as the unit element exhibiting peculiar physicochemical properties, creation of nanoscale hetero-junctions by interconnecting two kinds of organic molecules in the combination of donor-acceptor, host-guest and so on, offers molecular scale active elements of nanodevices exhibiting sophisticated functions such as an electrical rectification, 5 switching, [START_REF] Gao | Nanometer-Scale Conductance Transitions in an Organic Complex[END_REF][START_REF] Pathem | Molecular Switches and Motors on Surfaces[END_REF][START_REF] Yang | Switchable Host-Guest Systems on Surfaces[END_REF] photoelectric conversion, [START_REF] Imahori | Modulating Charge Separation and Charge Recombination Dynamics in Porphyrin-Fullerene Linked Dyads and Triads: Marcus-Normal versus Inverted Region[END_REF] and logical operation. [START_REF] Witlicki | Molecular Logic Gates Using Surface-Enhanced Raman-Scattered Light[END_REF] Particularly, toward realizing the molecular circuitry, [START_REF] Wada | Prospects and Problems of Single Molecule Information Devices[END_REF] creating an array of the nanojunctions between the one-dimensional (1D) conductive polymers and functional molecules is attractive, in which the 1D polymer is expected to behave not only as a wire but also as a part of nanojunction. [START_REF] Okawa | Chemical Wiring and Soldering toward All-Molecule Electronic Circuitry[END_REF][START_REF] Umeyama | Carbon Nanotube Wiring of Donor-Acceptor Nanograins by Self-Assembly and Efficient Charge Transport[END_REF] An essential requirement in this concept is to connect the functional molecules with the 1D polymer via covalent bonds, which realizes well-defined physical and/or electrical contact in the nanojunction and improves its performances such as the structural stability and/or efficiency of charged-carrier transfers. Although such the molecule-polymer system would be finely created by advanced chemical synthesis in liquid-phase, it is essentially difficult to arrange such the huge molecular assemblies on solid surfaces while remaining intact. In constant, it has been recently demonstrated that some of macromolecules such as polymers and huge molecular complexes can be synthesized on solid surfaces by controlling covalent assembly among molecular building blocks deposited onto the surfaces. [START_REF] Okawa | Chemical Wiring and Soldering toward All-Molecule Electronic Circuitry[END_REF][START_REF] Umeyama | Carbon Nanotube Wiring of Donor-Acceptor Nanograins by Self-Assembly and Efficient Charge Transport[END_REF][START_REF] Sakaguchi | Direct Visualization of the Formation of Single-Molecule Conjugated Copolymers[END_REF][START_REF] Treier | Fabrication of Surface-Supported Low-Dimensional Polyimide Networks[END_REF][START_REF] Cai | Atomically Precise Bottom-Up Fabrication of Graphene Nanoribbons[END_REF][START_REF] Nakaya | Scanning Tunneling Microscopy and Spectroscopy of Electron-Irradiated Thin Films of C60 Molecules[END_REF][START_REF] Lafferentz | Controlling On-Surface Polymerization by Hierarchical and Substrate-Directed Growth[END_REF] This methodology also allows us to investigate pristine geometry and electronic properties with atomic resolution of such the macromolecule systems using scanning tunneling microscopy and spectroscopy (STM/STS). In this article, we have constructed an array of molecules-polymer nanojunction on solid surfaces from fullerene C60 molecule [START_REF] Kroto | Buckminsterfullerene[END_REF] and 1D polymer nanowire of diacetylene (DA) compound molecules, polydiacetylene (PDA), [START_REF] Okawa | Chemical Wiring and Soldering toward All-Molecule Electronic Circuitry[END_REF] in which C60 molecule is covalently bound with an edge of π-conjugated PDA moiety.

The C60-PDA nanojunctions have been fabricated on the basis of the chemical soldering method. [START_REF] Okawa | Chemical Wiring and Soldering toward All-Molecule Electronic Circuitry[END_REF][START_REF] Okawa | Controlled Chain Polymerisation and Chemical Soldering for Single-Molecule Electronics[END_REF] The key to this method is a linear chain polymerization in the self-assembled monolayer (SAM) of DA molecules, as shown in Figures 1B andC, which is induced via electronic excitation of DA molecules by electrons inelastically tunneling between an STM tip and substrates or by photons irradiated from ultraviolet (UV) light source. To briefly describing the important aspect of the chain polymerization, DA moiety in a monomer molecule is firstly excited as a reactive diradical and then dimer is created by an addition reaction between the radical and neighboring DA molecule. Since the created dimer also has reactive terminals, 1D polymer is extended by spontaneously repeating the addition reactions along a molecular row of DA moieties in the SAM. [START_REF] Okawa | Chemical Wiring and Soldering toward All-Molecule Electronic Circuitry[END_REF][START_REF] Okawa | Controlled Chain Polymerisation and Chemical Soldering for Single-Molecule Electronics[END_REF] Interestingly, propagating reactive terminal of the PDA reacts not only with a neighboring DA molecule but also with different molecular species adsorbed on the row of DA moieties. [START_REF] Okawa | Chemical Wiring and Soldering toward All-Molecule Electronic Circuitry[END_REF][START_REF] Okawa | Controlled Chain Polymerisation and Chemical Soldering for Single-Molecule Electronics[END_REF] However, despite a simplicity, versatility, and potential ability of this method for creating an array of the polymer-molecule nanojunctions on solid surfaces, it has been demonstrated for only fabricating a nanojunction between PDA nanowire and a single phthalocyanine molecule. In the current study, we have shown that this method is also useful for covalently connecting the PDA nanowire with C60 molecule via cycloaddition reaction.

RESULTS AND DISCUSSION

Figure 2A shows STM image of clean surface of MoS2 taken after simultaneously depositing 1.0 and 0.1 ML of DA compound and C60 molecules, respectively, at room temperature (RT). In the current work, 10,12-pentacosadiynoic acid [R-C≡C-C≡C-R', where C≡C-C≡C, R, and R' correspond to the DA moiety, CH3(CH2)11, and (CH2)8COOH side chains, respectively] were used as the DA compound molecule. The region A and B in Figure 2A correspond to a SAM and monolayer islands of DA and C60 molecules, respectively, as discussed below. It is noted that similar structures have been also prepared on clean surfaces of highly oriented pyrolytic graphite (HOPG). In the high-resolution image of the region A (Figure 2B), parallel bright lines separated by two kinds of distance of about ~3.0 and ~4.0 nm are observed. In addition, an array of slightly bright spots along the bright lines with separation of ≈0.5 nm is also observed in Figure 2B. According to the previous STM studies on SAMs of the same DA compound molecules formed by Langmuir-Schaefer (LS) and drop casting methods, [START_REF] Okawa | Controlled Chain Polymerisation and Chemical Soldering for Single-Molecule Electronics[END_REF][START_REF] Giridharagopal | Substrate-Dependent Properties of Polydiacetylene Nanowires on Graphite and MoS2[END_REF][START_REF] Okawa | Linear Chain Polymerization Initiated by a Scanning Tunneling Microscope Tip at Designated Positions[END_REF][START_REF] Mandal | Rate-Determining Factors in the Chain Polymerization of Molecules Initiated by Local Single-Molecule Excitation[END_REF] the DA SAM is composed of the molecules lying flat on substrate surface and aligning parallel to each other with intermolecular distance of 0.47 nm, as shown in inset in Figure 2B. In these LS and drop-casting films, the aligned DA moieties are observed as bright lines with two types of spacing of 3.0 and 3.8 nm in STM observations, because DA molecules are arranged in a manner such that the COOH end-groups of the chain are opposite to those of a neighboring molecule. Observed periodicity in the region A agrees well with that of the LS and drop-casting films of DA molecules.

On the other hand, Figure 2C shows a high-resolution STM image taken at a boundary between the DA SAM and a C60 island with a single-molecule height. The C60 island is composed of hexagonally-ordered C60 molecules with intermolecular distance of ≈1.0 nm. This ordering is similar to that in the multilayer films consist of closely-packed C60 molecules. [START_REF] Núñez-Regueiro | Polymerized Fullerite Structures[END_REF] The arrangement of C60 molecules is maintained during the lateral growth of the C60 islands by additional deposition of C60 molecules till the monolayer C60 film covering over the DA SAM (See Supporting Information), although there is a large lattice mismatch between the monolayer film of closely-packed C60 molecules and the DA SAM. This result is different from the cases of C60 adlayer formation on SAMs of cyclothiophenes, [START_REF] Mena-Osteritz | Complexation of C60 on a Cyclothiophene Monolayer Template[END_REF] α-sexithiophenes, [START_REF] Chen | Tunable Arrays of C60 Molecular Chains[END_REF] acridine-9-carboxylic acids, [START_REF] Xu | Coverage Dependent Supramolecular Structures: C60:ACA Monolayers on Ag(111)[END_REF] zinc porphyrin derivatives, [START_REF] Bonifazi | Supramolecular Nanostructuring of Silver Surfaces via Self-Assembly of [60]Fullerene and Porphyrin Modules[END_REF] and so on, on which the arrangement of C60 molecules is strongly modified by a donor-acceptor interaction between C60 molecules and the SAMs. It is also important to point out that, in our experiments, the DA and C60 molecules were simultaneously deposited at various rates onto the MoS2 and HOPG surfaces, molecular-scale mixtures [START_REF] Wakayama | Solid-State Reactions in Binary Molecular Assemblies of F16CuPc and Pentacene[END_REF] of them have never been created on surfaces. The above experimental observations indicate that van des Waals interactions between C60 and DA molecules are much smaller than the ones in between the C60 molecules. This is consistent with another fact that the C60 molecules in the nano-island are observed as smooth sphere (Figure 2C), indicating that the each C60 molecule freely rotates on the DA SAM similar to those on the chemically inert surfaces. [START_REF] Nakaya | Reversibility-Controlled Single Molecular Level Chemical Reaction in a C60 Monolayer via Ionization Induced by Scanning Tunneling Microscope[END_REF] The C60 -DA van der Waals interactions is locally modified by inducing chain polymerizations between the DA molecules. In the following example, the chain polymerization was induced by irradiating UV light under ultrahigh-vacuum (UHV) using low-pressure mercury lamp (~254 nm in wavelength and ~1.3 mW/cm 2 in power density at the sample position) for 60 min. Figure 3A shows an STM image of a DA SAM and C60 islands after irradiating the UV light. An array of nanowires exhibiting the very bright image contrast correspond to backbones of PDA created by the chain polymerization between DA molecules, as discussed in the previous STM studies. [START_REF] Okawa | Chemical Wiring and Soldering toward All-Molecule Electronic Circuitry[END_REF][START_REF] Okawa | Controlled Chain Polymerisation and Chemical Soldering for Single-Molecule Electronics[END_REF][START_REF] Giridharagopal | Substrate-Dependent Properties of Polydiacetylene Nanowires on Graphite and MoS2[END_REF][START_REF] Okawa | Linear Chain Polymerization Initiated by a Scanning Tunneling Microscope Tip at Designated Positions[END_REF][START_REF] Mandal | Rate-Determining Factors in the Chain Polymerization of Molecules Initiated by Local Single-Molecule Excitation[END_REF] The bright image contrast of the PDA backbone simultaneously originates from its geometrical lift-up by 0.15 nm (Figure 1D) and a closure of its HOMO-LUMO gap neat Fermi level (EF) as compared with the DA monomers. [START_REF] Okawa | Chemical Wiring and Soldering toward All-Molecule Electronic Circuitry[END_REF][START_REF] Okawa | Controlled Chain Polymerisation and Chemical Soldering for Single-Molecule Electronics[END_REF][START_REF] Akai-Kasaya | Electronic Structure of a Polydiacetylene Nanowire Fabricated on Highly Ordered Pyrolytic Graphite[END_REF] Figure 3B shows the magnified image of the region surrounded by the blue line in show STM images of two C60 islands formed on a DA SAM, which were taken before and after STM-induced chain polymerization, respectively, triggered by applying sample bias voltage (Vs) of -3.3 V for 1 s at each tip position indicated by crosses in Figure 3C. After these procedures, seven PDA nanowires have been created along an array of DA moieties and terminated by edges of C60 nanoislands, as shown in Figure 3D. Upper and lower panels in Figure 3E show magnified images of the region surrounded by the blue line in Figure 3D taken before and after creating a single PDA nanowire, respectively. In comparison between them, it has been clearly observed that the single C 60 molecule exhibits brighter image contrast by connecting with the PDA nanowire. This bright appearance is considered to mainly originate from a shift in energy of the C60 frontier molecular orbitals which is considered to occur by covalent bonding to the edge of PDA nanowire as discussed latter. A C60 molecule behaves as an anchor part for the physical and electronic contacts between the C60 island and a PDA nanowire.

Actually, we have gained experimental evidences that the C60 molecule is strongly bound to the edge of PDA nanowire. In the present study, C60 molecules deposited onto DA SAMs were not observed as isolated single molecule adsorbates but mostly as islands, as mentioned above. Also two-dimensional (2D) gas phase of C60 molecules are formed as the minor structure and recognized as noisy feature around C60 islands in STM images. Figure 4A shows an STM image of the gas-phase C60 molecules around a C60 island, which taken after inducing the chain polymerization by UV light irradiation. Interestingly, we recognize that four C60 molecules are individually immobilized with each edge of four PDA nanowires in the vicinity of the 2D gas as indicated by blue dotted circles. Furthermore, the C60 molecule immobilized with PDA nanowire sometimes exhibits internal str uctures at RT as shown in inset of Figure 4A, strongly indicating that the rotational motion of the C60 molecule is inhibited owing to the covalent bonding similar to the C60 molecules cross-linked via [2+2] cycloadditive four-membered rings. 30,3 2 These result strongly indicates that the C60 molecules diffusing on the surface have accidentally encountered and reacted with a propagating forefront part of PDA in which reactive chemical species (carbene or radical) appear. [START_REF] Neumann | The Mechanism of the Low Temperature Polymerizatio n Reaction in Diacetylene Crystals[END_REF] [START_REF] Win | Methyl 1,2-Dihydrofullerenecarboxylate[END_REF][START_REF] Osterodt | C61Br2: A New Synthesis of Dibromomethanofullerene and Mass Spectrometric Evidence of the Carbon Allotropes C121 and C122[END_REF][START_REF] Fabre | The Reaction of Buckminsterfullerene with Diazotetrazole. Synthesis, Isolation, and Characterization of (C60)2C2[END_REF][START_REF] Fernández | Self-Organization of Electroactive Materials: A Head-to-Tail Donor-Acceptor Supramolecular Polymer[END_REF] the present result is the first demonstration for usage of this reaction in surface synthesis of huge molecular complexes.

It has been also found that at least the C60 frontier molecular orbitals are shifted in energy after reacting with the end of a PDA nanowire. Figure 5 shows height profiles of STM tip taken along lines intersecting an anchor C60 molecule in C60 island connected to PDA and the other molecules existing in the island, as shown by a dotted line in inset, for example. Blue and red cur ves are taken by imagings at filled (Vs < 0) and empty (Vs > 0) states of each C60-PDA junction formed on HOPG and MoS2 surfaces, respectively. In some of profiles, tip height is clearly measured higher on the anchor C60 molecule than that on the other C60 molecules in islands. This corresponds to the above mentioned result that the anchor C60 molecule exhibits brighter appearance than the others in STM images. Interestingly, the tip-height profiles over the anchor C60 molecule change depending on the value of bias voltages in both bias polarities, strongly indicating that the electronic structure of the anchor C60 molecule is modified.

Although the highest occupied molecular orbital (HOMO) and the lowest unoccupied molecular orbital (LUMO) levels of pristine C60 molecules adsorbed on the chemically inert surfaces appear at Vs of -2.5 V and +1.4 V in the STS mesurement, [START_REF] Nakaya | Reversibility-Controlled Single Molecular Level Chemical Reaction in a C60 Monolayer via Ionization Induced by Scanning Tunneling Microscope[END_REF] respectively, the tip-height difference becomes remarkable at the smaller bias region than them. This fact implies that the HOMO-LUMO gap of the anchor C60 molecule is smaller than that of the pristine C60 molecule. This consideration is qualitatively consistent with the preceding conclusion that the C60 molecule is covalently bond to the PDA nanowire, because it is known that the HOMO-LUMO gap of a C60 molecule decreases by covalent bonding with surfaces [START_REF] Sakamoto | Bonding State of the C60 Molecule Adsorbed on a Si(111)-(7×7) Surface[END_REF][START_REF] Lu | Charge Transfer and Screening in Individual C60 Molecules on Metal Substrates: A Scanning Tunneling Spectroscopy and Theoretical Study[END_REF] or other molecular species, [START_REF] Lu | Charge Transfer and Screening in Individual C60 Molecules on Metal Substrates: A Scanning Tunneling Spectroscopy and Theoretical Study[END_REF] which originates from splitting of HOMO and/or LUMO levels owing to impairing the symmetrical molecular structure.

On the other hands, since the DA SAM behaves as a thin insulating layer between C60 molecules and conductive substrate, connecting the C60 molecule to conductive polymer would increase an electronic coupling between the C60 molecule and the substrate, which is another possible cause for the bright appearance of the C60 molecule in the STM imaging of C60-PDA junctions, similar to the case of lander molecules connecting at the step edge of metallic substrate. [START_REF] Stojkovic | The Contact Conductance on a Molecular Wire[END_REF][START_REF] Moresco | Probing the Different Stages in Contacting a Single Molecular Wire[END_REF] Toward best of our understanding about present results, further clarification about geometry and energy level alignment of C60-PDA nanojunction should be carried out by STS and theoretical studies, which also could provide us insights into electrical properties of the C60-PDA nanojunction such as the low voltage electronic conductance of this molecular junction, its current-voltage characteristics and the effective charge carrier injection barrier.

CONCLUSIONS AND PROSPECTS

To summarize, a nanoscale heterojunction composed of the C60 molecule and the PDA nanowire has been constructed on a solid surface. In this nanojunction, a single C60 molecule is covalently bound to the edge of π-conjugated PDA backbone. This covalent interaction is considered to reduce the HOMO-LUMO gap of the C60 molecule in C60-PDA nanojunction. This C60-PDA nanojunction has been novel considering the huge molecular complex created by only our chemical soldering experiments on a surface. Further clarification about geometry and electronic structures of the C60-PDA molecular junction would clarify the functionality of such the complex. Particularly, conduction and injection properties of electrons, holes or polarons among closely-connected two kinds of π-conjugated molecular systems, are attractive. Another attractive challenge is to actively control the formation and annihilation of the covalent bond between the C60 molecule and PDA nanowire, such as that realized between C60 molecules. 30,31,4 3 The current results and these next challenges would lead to realization of a molecular nanoelectronics using the molecule-polymer nanojunctions.

EXPERIMENTAL METHODS

Sample preparation:

All experiments were carried out in an UHV cha mber with a base pressure of 1.0×10 -8 Pa. The DA SAM and C60 nanoislands were formed by simultaneously depositing DA compound and C60 molecules at RT, respectively, onto clean surfaces of HOPG and MoS2. The HOPG and MoS2 were cleaved in air followed by thermal annealing at 500°C in UHV. Deposition of DA and C60 molecules were carried out by the thermal evaporation of molecular powders with purity of above 97% and 99.995% from a Ta boat and BN crucible while maintaining a deposition rate of 0.1 and of 0.01 ML/min, respectively. All the STM experiments were carried out using an electrochemically etched Pt-20%Ir tip at RT. Supporting Information Available: STM observation of a DA SAM after covering with C60 monolayer films. This material is available free of charge via the Internet at http://pubs.acs.org

Figure

  Figure 3A, in which C60 molecules contacting with each edge of PDA nanowires (blue arrows) exhibit

  Figure 4B is possible chemical reaction between the PDA and the C60 molecule, in which the carbene at the forefront part of PDA reacts to 6-6 part in the C60 molecule, resulting that the double bond of C60 molecule are cleaved and then three membered ring are formed via [1+2] cycloaddition reaction as a intermolecular bond. Although similar chemical reaction has been widely used in chemical synthesis of C60 derivatives achieved by covalently connecting various carbene species to C60 molecules,

Figure 1 Figure 1 . 20 Figure 2 Figure 2 . 21 Figure 3 Figure 3 .

 1120222133 Figure 1

22

 22

Figure 4

 4 Figure 4

Figure 4 .

 4 Figure 4. Covalent bonding between a single C60 molecule and an edge of PDA nanowire. (A) STM image of the nanoisland and 2D gas of C60 molecules on the DA SAM, which taken after inducing STM-inducing chain polymerization. The sample was formed on a HOPG surface. Inset in (A) is high resolution image of single C60 molecule connecting to PDA nanowire. The imaging conditions of (A) and its inset are Vs of -2.3 V and It of 20 pA. (B) cycloaddition reaction between C60 molecules and PDA nanowire, which is possible candidates for the chemical reaction creating C60-PDA nanojunctions.

Figure 5 Figure 5 .

 55 Figure 5