Martin Gugat
email: martin.gugat@fau.de

Emmanuel Trélat
email: emmanuel.trelat@upmc.fr

Enrique Zuazua
email: zuazua@bcamath.org

Optimal Neumann control for the 1D wave equation: Finite horizon, infinite horizon, boundary tracking terms and the turnpike property

Keywords: Vibrating string, Neumann boundary control, turnpike phenomenon, exponential stability, energy decay, exact control, infinite horizon optimal control, similarity theorem, receeding horizon

come     Optimal Neumann control for the 1D wave equation: finite horizon, infinite horizon, boundary tracking terms and the turnpike property

Introduction

The turnpike property has been discussed recently for the optimal control of linear systems governed by partial differential equations, see [START_REF] Porretta | Long Time versus Steady State Optimal Control[END_REF]. Turnpike theory has originally been discussed in economics, see [START_REF] Dorfman | Linear Programming and Economic Analysis[END_REF]. For systems governed by ordinary differential equations the turnpike property has been discussed for example in [START_REF] Trélat | The turnpike property in finite-dimensional nonlinear optimal control[END_REF], also for the nonlinear case. The turnpike property states loosely speaking that if the objective function penalizes both control cost and the difference of the 1 optimal trajectory to a given desired stationary state, the optimal controls will steer the system quickly to the desired stationary state and then the system will remain on this path most of the time. In Section 4 of [START_REF] Porretta | Long Time versus Steady State Optimal Control[END_REF], optimal control problems with the wave equation are considered on a given finite time interval [0, T ]. The control is distributed in the interior of the domain and no conditions for the terminal state at the time T are prescribed. In this paper we consider problems of optimal boundary control of the wave equation. We consider both problems with infinite time horizon and problems with finite time horizon. For the finite time problems, we prescribe exact terminal conditions. If the objective function only penalizes the control cost, for the 1D case in [START_REF] Gugat | Norm-Minimal Neumann Boundary Control of the Wave Equation[END_REF] it has been shown that the optimal controls are periodic, so in particular they do not have the turnpike structure. This illustrates that the turnpike property heavily depends on the choice of the objective functions, that has to couple the control cost with the penalization of the distance to the desired state.

We consider a system governed by the one-dimensional wave equation on a finite space interval, with a homogeneous Dirichlet boundary condition at one side, and a Neumann boundary control action at the other:

∂ tt y(t, x) = ∂ xx y(t, x),
(t, x) ∈ R × (0, 1),

y(t, 0) = 0, ∂ x y(t, 1) = u(t), t ∈ R, (1)
where the control u belongs to the class of square-integrable functions. Let y 0 ∈ H 1 (0, 1) be such that y 0 (0) = 0, and let y 1 ∈ L 2 (0, 1) be arbitrary. For every u ∈ L 2 (0, +∞), there exists a unique solution y ∈ C 0 (0, +∞; H 1 (0, 1)) ∩ C 1 (0, +∞; L 2 (0, 1)) of ( 1) such that y(0, •) = y 0 (•) and ∂ t y(0, •) = y 1 (•).

As is well known, the system is exactly controllable if and only if T 2 (see for example [START_REF] Gugat | L p -optimal boundary control for the wave equation[END_REF]). In this paper, given any λ ∈ [0, 1] and any T ∈ [0, +∞], we consider the optimal control problem (OCP) T λ of finding a control u ∈ L 2 (0, T ) minimizing the objective functional

J T λ (u) = T 0 (1 -λ) (∂ x y(t, 0)) 2 + λu(t) 2 dt, (2)
such that the corresponding solution of (1), with y(0, •) = y 0 (•) and ∂ t y(0, •) = y 1 (•), satisfies y(T, •) = ∂ t y(T, •) = 0 at the final time (exact null controllability problem). If T = +∞, then one can drop the final constraint requirement, which, by the way, happens to be automatically satisfied in the sense of a limit (this is a well known result coming from Riccati theory).

For λ = 1, this very classical optimal control problem (minimization of the L 2 norm of the control) has been considered, e.g., in [START_REF] Krabs | On time-minimal distributed control of vibrations[END_REF][START_REF] Lions | Exact controllability, stabilization and perturbations for distributed systems[END_REF][START_REF] Russell | Nonharmonic Fourier series in the control theory of distributed parameter systems[END_REF] (see also [START_REF] Colombo | Optimal Control in Networks of Pipes and Canals[END_REF] for optimal control problems consisting of satisfying consumer demands at the boundary of the system, such as in gas transportation networks), and it is easy to see that the optimal control is periodic (see [START_REF] Gugat | Norm-Minimal Neumann Boundary Control of the Wave Equation[END_REF]), with a period equal to 4, that is, twice the time needed by a wave starting at the boundary point where the control acts to return to that point. Note that, in this case, the optimal control is as well given by the Hilbert Uniqueness Method (see [START_REF] Lions | Exact controllability, stabilization and perturbations for distributed systems[END_REF]).

If λ < 1, then the objective functional involves a nontrivial boundary tracking term. This tracking term may be considered as a boundary observation of the space derivative of the state at the uncontrolled end of the string. As we are going to prove, in that case, the optimal control action is then essentially concentrated at the beginning and at the end of the time interval [0, T ]. More precisely, the optimal control can be written as the sum of an exponentially decaying term and of an exponentially increasing term.

As a consequence, if T is large then the optimal control, solution of (OCP) T λ , approximately consists of three pieces: the first and the third pieces are in short-time, and are transient arcs; the middle arc is in long time, and is exponentially close to 0. This is a turnpike phenomenon (see [START_REF] Porretta | Long Time versus Steady State Optimal Control[END_REF][START_REF] Trélat | The turnpike property in finite-dimensional nonlinear optimal control[END_REF]), meaning that the optimal trajectory, starting from given initial data, very quickly approximately reaches the steady-state (0, 0) (within exponentially short time, say ε > 0), then remains exponentially close to that steady-state within long time (say, over the time interval [ε, T -ε]), and, in the last short-time part [T -ε, T ], leaves this neighborhood in order to quickly reach its target.

In this approximate picture, if T = +∞ (infinite horizon), then the last transient arc does not exist since the infinite-horizon target is the steady-state (0, 0). In that case, the norm of the optimal control decays exponentially in time, and the same is true for the optimal state. Indeed, smallness of the observation term for a sufficiently long time interval with zero control implies proportional smallness of the state (this follows from an observability inequality, see [START_REF] Zuazua | Propagation, observation, and control of waves approximated by finite difference methods[END_REF]).

Another possible picture illustrating the turnpike behavior is the following. For T large, the optimal trajectory of (OCP) T λ approximately consists of three arcs: the first arc is the solution of (OCP) ∞ λ (infinite horizon problem), forward in time, and converges exponentially to 0. The second arc, occupying the main (middle) part of the time interval, is the steady-state 0. The third arc is the solution of (OCP) ∞ λ , but backward in time. Note that the optimal control problem (OCP) ∞ λ fits into the well known Linear Quadratic Riccati theory. In all cases, we will provide completely explicit formulas for the optimal controls, which explain and imply the turnpike behavior observed for λ < 1. This is in contrast with the case λ = 0 for which the control action is distributed uniformly along the time interval [0, T ]. In addition, we will also establish a similarity theorem showing that, for every T that is a positive even integer, there exists an appropriate weight λ < 1 for which the optimal solutions of (OCP) T λ and of (OCP

) ∞ λ coincide along [0, 2].
In this paper we focus on problems governed by the 1D wave equation. In order to illustrate the generality of the turnpike phenomenon, before we turn to the 1D wave equation we consider an example in a more general framework with a strongly continuous semigroup in the following section.

A general remark

Let a Hilbert space X be given. Let A be the generator of a strongly continuous semigroup (T t ) t 0 (for the definitions see for example [START_REF] Triggiani | Control Theory for Partial Differential Equations: Volume 2, Abstract Hyperbolic-like Systems over a Finite Time Horizon[END_REF], [START_REF] Tucsnak | Observation and Control for Operator Semigroups[END_REF]). Let U be another Hilbert space that contains the controls. Let the linear operator B : U → X be given. Let a time T > 0, a weight γ > 0 for the control cost and an initial state y 0 ∈ X be given. For u ∈ L 2 ((0, T ); U ) and t ∈ [0, T ], define

Φ t (u) = t 0 T t-σ Bu(σ) dσ.
We consider a system that is governed by the differential equation y (t) = A y(t) + B u(t), t ∈ [0, T ] with the initial condition y(0) = y 0 ∈ X. We assume that there exists a time T min > 0 such that for all T T min the considered system is exactly controllable in the sense that Ran Φ T = X.

Let us assume that T T min , then there exists a control function u ∈ L 2 ((0, T ); U ) such that the terminal constrain y(T ) = 0 holds. Let λ ∈ (0, 1) be given. Consider the problem of optimal exact control  

 min T 0 (1 -λ) y(t), y(t) X + λ u(t), u(t) U dt subject to y (t) = A y(t) + B u(t), t ∈ [0, T ]; y(0) = y 0 , y(T ) = 0. (3)
The static optimal control problem corresponding to (3) is min(1 -λ) y, y X + λ u, u U subject to 0 = A y + B u.

(4)

Obviously the solution of ( 4) is zero. The solution of the static optimal control problem (4) determines the turnpike which in our case is (u tp , y tp ) = (0, 0). Results about the convergence of the long time average of the optimal controls to the turnpike control can be found in [START_REF] Carlson | Existence of overtaking solutions to infinite dimensional control problems on unbounded time intervals[END_REF], [START_REF] Zaslavski | Existence and Structure of Optimal Solutions of Infinite-Dimensional Control Problems[END_REF].

In order to determine the structure of the optimal control that solves (3) we look at the necessary optimality conditions. For all δ 1 ∈ L 2 ((0, T ); U ), p ∈ C((0, T ); X), δ 2 ∈ C((0, T ); X) with δ 2 (0) = 0, δ 2 (T ) = 0 we have

0 = T 0 λ u(s), δ 1 (s) U + (1 -λ) y(s), δ 2 (s) X + δ 2 (s) -A δ 2 (s) -B δ 1 (s), p(s) X ds.
This yields the optimality system

   y = Ay + Bu, p = -A * p + y, u = 1-λ λ B * p (5)
with the conditions y(0) = y 0 , y(T ) = 0. Hence we get

-Ap = AA * p -Ay = AA * p -y + 1 -λ λ BB * p. (6)
By taking the time derivative in the first order equation for p we get the second order equation p = -A * p + y . This implies y = p + A * p .

Now we can use [START_REF] Gugat | L p -optimal boundary control for the wave equation[END_REF] to eliminate y from (6) and get

-Ap = AA * p -p -A * p + 1 -λ λ BB * p.
This yields

p = (AA * + 1 -λ λ BB * ) p + (A -A * ) p . (8)

Skew-adjoint operators

Now we consider the case where A is skew-adjoint, that is A * = -A. In [START_REF] Porretta | Long Time versus Steady State Optimal Control[END_REF], turnpike inequalities for the case of the wave equation where A * = -A are given in Section 4. Equation ( 8) yields

p = L p + 2A p (9)
where L = AA * + 1-λ λ BB * . If there exist solutions D + , D -of the operator equation

D 2 = L + 2AD
this yields solutions of the form

p(t) = exp(D + t) p 1 + exp(D -t)p 2
where p 1 , p 2 ∈ X are chosen such that for the state y = p + A * p we have y(0) = 0 and y(T

) = 0. Note that L + A 2 = 1-λ λ BB * is positive in the sense that x, (L + A 2 )x X 0 for all x ∈ X. If A B B * is skew adjoint (for example if B is the identity) we have D ± = A ± (L + A 2 ) 1/2 .
Now we assume that A and B B * are diagonalizable with the same sequence of orthonormal eigenfunctions (ϕ k ) k and that the real parts of the eigenvalues of B B * are bounded from below by ω 2 > 0. Then (9) yields a sequence of ordinary differential equations for

h k (t) = p(t), ϕ k X namely h k = ϕ k , L ϕ k X h k + 2 ϕ k , A ϕ k X h k . (10)
With the roots δ + k , δ - k of the characteristic polynomial

p k (z) = z 2 -2 ϕ k , A ϕ k X z -ϕ k , L ϕ k X we get the solutions h k (t) = u k exp(δ - k t) + v k exp(δ + k t) where Re(δ + k ) ω > 0 and Re(δ - k )
-ω < 0. The coefficients u k and v k are chosen such that p (0) = y 0 + Ap(0) and p (T ) = Ap(T ), because then we have y(0) = y 0 and y(T ) = 0. In fact, this yields a constant C min that is independent of y 0 and T such that for all T T min , we have the inequality

k |u k | 2 + | exp(2 δ + k T )| |v k | 2 C min y 0 2 X .
Using Parseval's equation we get the inequality

p(t) X e -ωt k |u k | 2 1/2 + e -ω(T -t) k | exp(2 δ + k T )| |v k | 2 ) 1/2 (11)
e -ωt + e -ω(T -t) 2 C min y 0 X . (12)
Inequality ( 11)-( 12) is a turnpike inequality for p. It states that the norm of p(t) is bounded above by a sum of a part that is exponentially decreasing with time and a second part that is exponentially increasing towards T . The optimal control has the form u = 1-λ λ B * p, so it also shows a turnpike structure. Note that the optimal control norms are decreasing with T , hence they are uniformly bounded.

Self-adjoint operators

Now we consider the case that A is self-adjoint. In [START_REF] Porretta | Long Time versus Steady State Optimal Control[END_REF], turnpike inequalities for the parabolic case where A * = A are given in Section 3. Equation ( 8) yields

p = L p (13)
where

L = AA * + 1 γ BB * . Thus we get p(t) = cosh(t L 1 2 ) p(0) + L -1 2 sinh(t L 1 2 ) p (0)
with the cosh and sinh operators as defined in [START_REF] Fattorini | Ordinary differential equations in linear topological spaces, Pts. II[END_REF]. For the optimal state we have

y = p + A * p.
The equations y(0) = y 0 , y(T ) = 0 yield a system of linear equations for p(0), p (0). In particular we have p (0) = y 0 -A * p(0). Now let us assume that L is diagonalizable and the eigenvalues of L are bounded from below by ω 2 > 0. Then we have the turnpike inequality

p(t) 1 2 exp(-ωt) ( p(0) + L -1/2 p (0) ) + 1 2 exp(-ω(T -t)) ( exp(L 1/2 T )p(0) + exp(L 1/2 T )L -1/2 p (0) ).
The optimal control has the form

u(t) = 1 γ B * cosh(t L 1 2 )p(0) + 1 γ B * L -1 2 sinh(t L 1 2 )p (0). ( 14
)
This means that also the optimal control can be represented as the sum of families of increasing and decreasing exponentials with rates ω.

The main results

Now we come to our results about optimal control problems for a system governed by [START_REF] Carlson | Existence of overtaking solutions to infinite dimensional control problems on unbounded time intervals[END_REF]. Let y 0 ∈ H 1 (0, 1) be such that y 0 (0) = 0, and let y 1 ∈ L 2 (0, 1) be arbitrary.

Explicit formulas

We have the following result, giving the explicit solution of (OCP) T λ , for any λ ∈ [0, 1] and any T ∈ [2, +∞]. Note that, when T = +∞, we have to assume that λ < 1 to ensure well-posedness.

Theorem 1. For every T ∈ [2, +∞] and every λ ∈ [0, 1], the problem (OCP) T λ has a unique optimal control solution denoted by u T λ . 1. We assume that T = 2n for some n ∈ N * .

• If λ = 1, then the optimal control u T 1 , solution of (OCP) T 1 is 2-anti-periodic, and thus 4-periodic, meaning that

u T 1 (t + 2k) = (-1) k u T 1 (t), ( 15
)
for every t ∈ (0, 2) and for every k ∈ N such that t + 2k T , and moreover,

u T 1 (t) = 1 2n (y 0 (1 -t) -y 1 (1 -t)) , t ∈ (0, 1), 1 2n (y 0 (t -1) + y 1 (t -1)) , t ∈ (1, 2). (16)
• If λ < 1, then the optimal control solution of (OCP) T λ is the sum of an exponentially decaying term and of an exponentially increasing one. More precisely, defining the real number z λ ∈ (-1, 0) by

z λ = -λ 2 -λ + 2 √ 1 -λ , (17)
we have

u T λ (t + 2k) = z k λ f + (t) + 1 z k λ f -(t), ( 18
)
for every t ∈ (0, 2) and every k ∈ N such that t + 2k T , where

f + (t) = 1 + z λ 1 -z 2n λ F (t -1), f -(t) = 1 + 1 z λ 1 -1 z 2n λ F (t -1), (19)
with F ∈ L 2 (-1, 1) defined by

F (t) = 1 2 (y 0 (-t) -y 1 (-t)) , t ∈ (-1, 0), 1 2 (y 0 (t) + y 1 (t)) , t ∈ [0, 1). ( 20
)
2. We assume that T = +∞ and that λ < 1.

If λ = 0, then the optimal control u ∞ 0 , solution of (OCP) ∞ 0 , coincides along the time interval [0, 2] with the optimal control u 2 1 , solution of (OCP

) 2 1 . If 0 < λ < 1, the optimal control u ∞ λ , solution of (OCP) ∞ λ , is given along the time interval [0, 2] by u ∞ λ (t) = 1+z λ 2 (y 0 (1 -t) -y 1 (1 -t)) , t ∈ (0, 1), 1+z λ 2 (y 0 (t -1) + y 1 (t -1)) , t ∈ (1, 2), (21)
and moreover, we have

u ∞ λ (t + 2k) = z k λ u ∞ λ (t), ( 22
)
for every t ∈ (0, 2) and every k ∈ N * .

The corresponding optimal state y ∞ λ decays exponentially, in the sense that there exists

C 0 > 0 such that 1 0 (∂ x y ∞ λ (t + 2 k, x)) 2 + (∂ t y ∞ λ (t + 2 k, x)) 2 dx C 0 |z λ | 2k 1 0 y 0 (x) 2 + y 1 (x) 2 dx, (23)
for every t ∈ (0, 2) and every k ∈ N * .

Theorem 1 is proved in Section 4.2.

For λ = 1, that is, when there is no tracking term in the objective functional, the explicit solution of (OCP) T 1 given above has already been computed in [6, Theorem 2.1]. In this case, the problem consists of minimizing the L 2 norm of the (Neumann) control. The optimal control u T 1 , whose explicit formula is given above, can also be characterized as well with the famous Hilbert Uniqueness Method (see [START_REF] Lions | Exact controllability, stabilization and perturbations for distributed systems[END_REF]) and is then often referred to as the HUM control.

Here, there is no dissipation induced by the objective functional (no tracking term), the optimal control is periodic, and is uniformly distributed over the time interval [0, T ], in the sense that there is no energy decay.

In contrast, if λ < 1, the control is the sum of two terms, one of which is exponentially decreasing, and the other being exponentially increasing. For T large enough, this implies the turnpike phenomenon, stated in details in Section 3.2.

Remark 1. For λ = 0, the solution of (OCP) ∞ 0 coincides with the solution of the problem of optimal feedback control studied in [START_REF] Gugat | Optimal boundary feedback stabilization of a string with moving boundary[END_REF].

Remark 2. The estimate (23) is clearly equivalent to 1 0 (∂ x y ∞ λ (t, x)) 2 + (∂ t y ∞ λ (t, x)) 2 dx C 1 e -µt 1 0 y 0 (x) 2 + y 1 (x) 2 dx,
for every time t 0, for some positive constants C 1 and µ not depending on the initial state (see also [START_REF] Gugat | An example for the switching delay feedback stabilization of an infinite dimensional system: The boundary stabilization of a string[END_REF]Lemma 2]).

Remark 3. It is well known that the solution of the infinite horizon problem (OCP) ∞ λ can also be expressed in feedback form (Linear Quadratic Riccati theory), see for example [START_REF] Flandoli | Algebraic Riccati equations with non-smoothing observation arising in hyperbolic and Euler-Bernoulli boundary control problems[END_REF]. More precisely, the velocity feedback

∂ x y(t, 1) = z λ + 1 z λ -1 ∂ t y(t, 1)
generates the same state as the one generated by the optimal control u ∞ λ .

Remark 4. In the above results, we considered only the null steady-state, but we can easily replace it with any other steady-state, as follows. Any steady-state of (1) is given by ȳ(x) = σx, for some σ ∈ R. Then, all results therein can be written in terms of such a steady-state: it suffices to replace, everywhere, y(t, x) with y(t, x) -σx, and ∂ x y(t, x) with ∂ x y(t, x) -σ. For instance, the right boundary condition becomes ∂ x y(t, 1) = σ + u(t), the final conditions become y(T, x) = σx and ∂ t y(T, x) = 0, and the objective functional becomes

J T λ (u) = T 0 (1 -λ) (∂ x y(t, 0) -σ) 2 + λu(t) 2 dt.

Consequence: the turnpike behavior

From Theorem 1 and from the previous discussions, we infer the following consequence on the qualitative behavior of the optimal solution.

Corollary 1. For every λ ∈ [0, 1), then there exist C 1 > 0 and µ > 0 such that, for every T 2, for all initial conditions (y 0 , y 1 ) ∈ H 1 (0, 1) × L 2 (0, 1) with y 0 (0) = 0, the optimal solution of (OCP) T λ satisfies the estimate

1 0 ∂ x y T λ (t, x) 2 + ∂ t y T λ (t, x) 2 dx C 1 e -µt(T -t) 1 0 y 0 (x) 2 + y 1 (x) 2 dx, (24)
for every t ∈ [0, T ].

In the estimate ( 24), what is important to see is that the term e -µt(T -t) is equal to 1 at times t = 0 and t = T , but it is exponentially small in the middle of the interval. It becomes even smaller and smaller when T is taken larger. This estimate implies the turnpike behavior described previously: short-time arcs at the beginning and at the end of the interval are devoted to satisfy the terminal constraints, and in-between, the trajectory remains essentially close to rest.

Similarity result

We next state the following similarity result: for any final time T that is a positive even integer, there exists a weight λ such that the optimal solutions of (OCP) ∞ 1 and (OCP) ∞ λ coincide along the subinterval [0, 2] of [0, T ].

Theorem 2. Given any T ∈ 2N * , we choose λ > 0 such that

z λ = 2 T -1. ( 25
)
Then we have

u T 1 (t) = u ∞ λ (t), ∀t ∈ (0, 2), (26)
and

u T 1 (•) -u ∞ λ (•) L 2 (2k,2k+2) 1 -|z λ | k 2 T y 0 L 2 (0,1) + y 1 L 2 (0,1) . ( 27
)
for every k ∈ {0, 1, . . . , (T -2)/2}.

The proof of Theorem 2 is done in Section 4.3.

Numerical illustration

We set y 0 (x) = 4 sin(πx/2) and y 1 (x) = 0, for every x ∈ [0, 1]. From Theorem 1, if 0 < λ < 1 then the optimal control solution of (OCP) T λ is given by These figures illustrate that the norm of the optimal state decays faster if λ is smaller, as expected. However, smaller values of λ cause larger oscillations. Note that z λ = -2/3 if λ = 24/25, and z λ = -9/11 if λ = 99/100. Moreover, as pointed out in [START_REF] Gugat | Norm-Minimal Neumann Boundary Control of the Wave Equation[END_REF]

u T λ (t + 2k) = |z λ | k (1 + z λ ) π sin π 2 (t + 2k) ,
, if T ∈ 2N * then u T 1 (t + 2k) = 2
T π sin π 2 (t + 2k) , for all t and k such that t + 2k ∈ [0, T ] (see also [START_REF] Gugat | Norm-Minimal Neumann Boundary Control of the Wave Equation[END_REF]Figure 4] for the corresponding optimal state, with T = 10, up to the factor 2π).

Proofs

Well-posedness of the initial-boundary value problem

Let y 0 ∈ H 1 (0, 1) be such that y 0 (0) = 0, and let y 1 ∈ L 2 (0, 1) be arbitrary. Let T 2, and let u ∈ L 2 (0, T ) be fixed. As a preliminary result, we study the well-posedness of the initial boundary value problem (1) for a fixed control u, and with the fixed initial data (y 0 , y 1 ). The analysis is similar to the one done in [START_REF] Gugat | An example for the switching delay feedback stabilization of an infinite dimensional system: The boundary stabilization of a string[END_REF].

We search a solution given as the sum of two traveling waves, i.e.,

y(t, x) = α(x + t) + β(x -t),
where the functions α and β are to be determined from the initial data and from the boundary data. First of all, to match the initial conditions, we must have

α(t) = 1 2 y 0 (t) + t 0 y 1 (s) ds + C 0 , (28)
β(t) = 1 2 y 0 (t) - t 0 y 1 (s) ds -C 0 , (29)
where C 0 is a real number. Besides, the boundary condition y(t, 0) = 0 implies that

β(-s) = -α(s), (30)
for almost every s > 0. The boundary condition at x = 1 leads to α (1 + t) = u(t) -β (1 -t), and in time, we get

α(t + 1) = β(1 -t) + t 0 u(s) ds + α(1) -β(1).
Using ( 28) and (29), we have α(1) -β(1) = 1 0 y 1 (s) ds + 2C 0 , and therefore, choosing C 0 = -1 2 1 0 y 1 (s) ds, we get α(1) -β(1) = 0 and

α(t + 1) = β(1 -t) + t 0 u(s) ds. (31)
Using (30), the values of α for t ∈ (0, 1), given by (28), determine those of β for t ∈ (-1, 0). The values of β for t ∈ (0, 1) are given by (29). Now, knowing β on the interval (-1, 1), we deduce from (31) the values of α on the interval [START_REF] Carlson | Existence of overtaking solutions to infinite dimensional control problems on unbounded time intervals[END_REF][START_REF] Coron | Global steady-state stabilization and controllability of 1D semilinear wave equations[END_REF]. Using (30), we get α(t + 1) = -α(t -1) + t 0 u(s) ds, for t 1, or equivalently,

α(t + 2) = -α(t) + t+1 0 u(s) ds, (32)
for t 0. Using (32) enables us to determine α iteratively: starting with α on the interval [START_REF] Carlson | Existence of overtaking solutions to infinite dimensional control problems on unbounded time intervals[END_REF][START_REF] Coron | Global steady-state stabilization and controllability of 1D semilinear wave equations[END_REF], the values of u(t) yield those of α on [START_REF] Coron | Global steady-state stabilization and controllability of 1D semilinear wave equations[END_REF][START_REF] Flandoli | Algebraic Riccati equations with non-smoothing observation arising in hyperbolic and Euler-Bernoulli boundary control problems[END_REF], and then using (32), we determine α on [START_REF] Gugat | L p -optimal boundary control for the wave equation[END_REF][START_REF] Gugat | Optimal boundary feedback stabilization of a string with moving boundary[END_REF], etc.

In order to express everything in terms of α only (without using β), we extend the domain of α so that it contains (-1, 0). We get the values of α on (-1, 0) by using (30) for s ∈ (0, 1), which yields α(t) = -β(-t) for t ∈ (-1, 0) with the values of β on (0, 1) given by (29). Then, using (31), we get α(t + 2) = -α(t) + t+1 0 u(s) ds for t ∈ (-1, 0). We have the following lemma.

Lemma 1. Let y 0 ∈ H 1 (0, 1) be such that y 0 (0) = 0, and let y 1 ∈ L 2 (0, 1) be arbitrary. We set

C 0 = - 1 2 1 0 y 1 (s) ds, (33)
and we define α ∈ L 2 (-1, 1) by

α(t) =    1 2 -y 0 (-t) + -t 0 y 1 (s) ds + C 0 if t ∈ (-1, 0), 1 2 y 0 (t) + t 0 y 1 (s) ds + C 0 if t ∈ [0, 1). ( 34
)
Let T = 2K ∈ N * , and let u ∈ L 2 (0, T ) be fixed.

The function α, defined by iteration according to

α(t + 2k) = -α(t + 2(k -1)) + t+2k-1 0 u(s) ds, (35)
for every t ∈ (-1, 1) and every k ∈ N such that t < T + 1 -2k, is well defined on the interval (-1, T + 1), and belongs to H 1 (-1, T + 1).

Proof: From the construction, it is clear that α| (k-1,k) ∈ H 1 (k, k + 1), for every k ∈ N. To prove that α ∈ H 1 (-1, T + 1), it suffices to prove that α is continuous. Since α(0 + ) = α(0 -) = C 0 , α is continuous at t = 0. Using (34), α is continuous as well on (-1, 1).

At t = 1, using (33) we get α(1

+ ) = α(1 -) = 1 2 y 0 (1)
, and hence α is continuous at t = 1. Then, at this step, we have obtained that α is continuous on (-1, 3).

We then proceed by induction. Let k ∈ N * . We assume that α is continuous on the interval (-1, 1 + 2k). Then α((-1 + 2k) -) = α((-1 + 2k) + ). Using (35), we have

α((1 + 2k)-) = -α((1 + 2(k -1)) -) + 2k 0 u(s) ds = -α((-1 + 2k) -) + 2k 0 u(s) ds = -α((-1 + 2k) + ) + 2k 0 u(s) ds = α((-1 + 2(k + 1)) + ) = α((1 + 2k) + ).
Since α is defined by (34), we infer that α is continuous on (-1, 1 + 2(k + 1)) for k + 1 K. Lemma 1 is proved.

Using Lemma 1, we are now in a position to compute the solution of the initial boundary value problem under consideration in this subsection. Proposition 1. Let y 0 ∈ H 1 (0, 1) be such that y 0 (0) = 0, and let y 1 ∈ L 2 (0, 1) be arbitrary. Let T ∈ 2N * , and let u ∈ L 2 (0, T ) be fixed. We consider the function α defined in Lemma 1 by (34). Then the solution of (1), associated with the control u and with the initial data (y 0 , y 1 ), is given by y

(t, x) = α(t + x) -α(t -x), (36)
for all (t, x) ∈ (0, T ) × (0, 1).

Proof: The construction of α implies that y, defined by (36), is a solution of the initial boundary value problem under consideration. We conclude by Cauchy uniqueness.

Proof of Theorem

y T λ (T, •) = 0, ∂ t y T λ (T, •) = 0. ( 37
)
It suffices to prove that α (z) = 0, for z ∈ (T -1, T + 1). From (36), we have y T λ (t, x) = α λ (t + x) -α λ (t -x), with α λ defined by (34). The definition [START_REF] Zuazua | Propagation, observation, and control of waves approximated by finite difference methods[END_REF] implies that F (t) = α λ (t).

Hence, we have

α λ (t -1) = 1 -z 2n λ 1 -z 2n λ F (t -1) = 1 1 -z 2n λ + z 2n λ z 2n λ -1 F (t -1) = 1 1 -z 2n λ + 1 1 -z -T λ F (t -1) = 1 1 + z λ f + (t) + 1 1 + 1 z λ f -(t),
where the last equality follows from [START_REF] Zaslavski | Existence and Structure of Optimal Solutions of Infinite-Dimensional Control Problems[END_REF].

By (35) we have

α λ (t + 1) = -α λ (t -1) + u ∞ λ (t), (38)
for t ∈ (0, 2). Using [START_REF] Tucsnak | Observation and Control for Operator Semigroups[END_REF], this yields α λ (t + 1) = -α λ (t -1) + f + (t) + f -(t), for t ∈ (0, 2), and then, using [START_REF] Zaslavski | Existence and Structure of Optimal Solutions of Infinite-Dimensional Control Problems[END_REF],

α λ (t + 1) = z λ 1 + z λ f + (t) + 1 z λ 1 + 1 z λ f -(t).
By induction, thanks to (38) and ( 18), this implies that

α λ (t -1 + 2k) = z k λ 1 + z λ f + (t) + 1 z k λ 1 + 1 z λ f -(t), (39)
for every t ∈ (0, 2) and every k ∈ N such that 2k T . Taking k = T /2, we get

α λ (t -1 + T ) = z n λ 1 + z λ f + (t) + 1 z n λ 1 + 1 z λ f -(t). (40)
Using [START_REF] Zaslavski | Existence and Structure of Optimal Solutions of Infinite-Dimensional Control Problems[END_REF], we infer that

α λ (t -1 + T ) = z n λ 1 -z 2n λ + 1 z n λ 1 -1 z 2n λ F (t -1) = 0, (41)
and hence the state y T λ satisfies the terminal conditions (37). For a control of the form u = u T λ + h, the generated state is y = y T λ + y h , where y h is the state generated by the perturbation control h, with the boundary conditions y h (t, 0) = 0, ∂ x y h (t, 1) = h(t), and null initial conditions. We only consider variations h for which y h (T, •) = 0 and ∂ t y h (T, •) = 0. Using (36), we have

y h (t, x) = α h (t + x) -α h (t -x). Since y h (0, •) = ∂ t y h (0, •) = 0, we must have α h (t -1) = α h (t) = 0. Moreover, owing to the terminal constraints, we must have α h = 0 along (T -1, T + 1).
The value of the objective functional of (OCP

) T λ is T 0 (1 -λ)(∂ x y(t, 0)) 2 + λu(t) 2 dt = T 0 (1 -λ) (∂ x y T λ (t, 0)) 2 + (∂ x y h (t, 0)) 2 + 2∂ x y T λ (t, 0)∂ x y h (t, 0) + λ u T λ (t) 2 + h(t) 2 + 2u T λ (t)h(t) dt.
We consider the linear part

L λ (h) = 2 T 0 (1 -λ)∂ x y T λ (t, 0)∂ x y h (t, 0) + λu T λ (t)h(t) dt. Since ∂ x y T λ (t, 0) = 2α λ (t), ∂ x y h (t, 0) = 2α h (t), and u T λ (t) = ∂ x y T λ (t, 1) = α λ (t + 1) + α λ (t -1), h(t) = ∂ x y h (t, 1) = α h (t + 1) + α h (t -1), we get L λ (h) = T 0 8(1 -λ)α λ (t)α h (t) + 2λ (α λ (t + 1) + α λ (t -1)) (α h (t + 1) + α h (t -1)) dt = T -1 j=0 1 0 8(1 -λ)α λ (t + j)α h (t + j) + 2λ (α λ (t + 1 + j) + α λ (t -1 + j)) (α h (t + 1 + j) + α h (t -1 + j)) dt = 8(1 -λ) T -1 j=1 1 0 α h (t + j)α λ (t + j) dt + 2λ T -2 j=1 1 0 α h (t + j) (α λ (t + 2 + j) + α λ (t + j)) dt + 2λ T -2 j=1 1 0 α h (t + j) (α λ (t + j) + α λ (t -2 + j)) dt = 2 T -2 j=1 1 0 α h (t + j) 4(1 -λ)α λ (t + j) λ (α λ (t + 2 + j) + α λ (t -2 + j) + 2α λ (t + j)) dt
Defining the characteristic polynomial by

p λ (z) = λz 2 + (4 -2λ)z + λ, (42)
we have p λ (z λ ) = 0 and p λ (1/z λ ) = 0. Using (39), we have

λα λ (t + 2 + j) + (4 -2λ)α λ (t + j) + λα λ (t -2 + j) = 0,
for every t ∈ (0, 1) and every j ∈ {1, 2, . . . , T -2}. This implies that L λ (h) = 0. Now, concerning the value of the objective functional of (OCP) T λ , for any h such that y h (T, •) = 0 and ∂ t y h (T, •) = 0, we infer that

+∞ 0 (1 -λ) (∂ x y(t, 0)) 2 + λu(t) 2 dt +∞ 0 (1 -λ) ∂ x y T λ (t, 0) 2 + λu T λ (t) 2 dt,
with a strict inequality whenever h = 0. It follows that u T λ is the unique optimal solution of (OCP) T λ , as soon as λ > 0. If λ = 0, then the result also follows from the representation of L 0 (h). However, in this case the characteristic polynomial p 0 (z) = 4z has only one root given by z 0 = 0. Theorem 1 is proved for T < +∞.

Case T = +∞

We are going to use the previously established well-posedness results.

Let y ∞ λ be the state generated by the control u ∞ λ defined in the theorem. For a control of the form u = u ∞ λ + h, the generated state is y = y ∞ λ + y h , where y h is the state generated by the control h, with null initial conditions and with the boundary conditions y h (t, 0) = 0 and ∂ x y h (t, 1) = h(t). The value of the objective functional of (OCP

) ∞ λ is +∞ 0 (1 -λ)(∂ x y(t, 0)) 2 + λu(t) 2 dt = +∞ 0 (1 -λ) (∂ x y T λ (t, 0)) 2 + (∂ x y h (t, 0)) 2 + 2∂ x y ∞ λ (t, 0)∂ x y h (t, 0) + λ u ∞ λ (t) 2 + h(t) 2 + 2u ∞ λ (t)h(t) dt.
We consider the linear part

L λ (h) = 2 +∞ 0 ((1 -λ)∂ x y ∞ λ (t, 0)∂ x y h (t, 0) + λu ∞ λ (t)h(t)) dt.
Using (36), we have y ∞ λ (t, x) = α λ (t + x) -α λ (t -x) and y h (t, x) = α h (t + x) -α h (t -x), with α λ given by (34), and α h = 0 on (-1, 1). It follows that ∂ x y ∞ λ (t, 0) = 2α λ (t), ∂ x y h (t, 0) = 2α h (t), and

u ∞ λ (t) = ∂ x y ∞ λ (t, 1) = α λ (t + 1) + α λ (t -1), h(t) = ∂ x y h (t, 1) = α h (t + 1) + α h (t -1),
and therefore,

L λ (h) = +∞ 0 8(1 -λ)α λ (t)α h (t) + 2λ (α λ (t + 1) + α λ (t -1)) (α h (t + 1) + α h (t -1)) dt = +∞ j=0 1 0 8(1 -λ)α λ (t + j)α h (t + j) + 2λ (α λ (t + 1 + j) + α λ (t -1 + j)) (α h (t + 1 + j) + α h (t -1 + j)) dt = 2 1 0 4(1 -λ)α h (t)α λ (t) + λ (α h (t -1) (α λ (t + 1) + α λ (t -1)) + α h (t) (α λ (t + 2) + α λ (t))) dt + 2 +∞ j=1 1 0 α h (t + j) 4(1 -λ)α λ (t + j) + λ (2α λ (t + j) + α λ (t -2 + j) + α λ (t + 2 + j)) dt.
By Lemma 1, for t ∈ (0, 1) the values of α h (t -1) and α h (t) are determined from the initial data, and since they are equal to zero, we have α h (t -1) = α h (t) = 0. This yields

L λ (h) = 2 +∞ k=1 1 0 α h (t + k) 4(1 -λ)α λ (t + k) + λ (2α λ (t + k) + α λ (t -2 + k) + α λ (t + 2 + k)) dt. (43)
If λ > 0 then the roots of the characteristic polynomial p λ defined by (42) are z λ and 1 z λ . In particular, we have p λ (z λ ) = 0. Note that, by Lemma 1, for t ∈ (0, 1) the values of α λ (t -1) and of α λ (t) are determined from the initial data. By (35), we have

α λ (t + 1) = -α λ (t -1) + u ∞ λ (t), (44)
for t ∈ (0, 2). Using the representation (21) of u ∞ λ (t) for t ∈ (0, 1), and using (34), we infer that α λ (t + 1) = z λ α λ (t -1) for t ∈ (0, 1). Similarly, using (35), we have α λ (t + 2) = -α λ (t) + u ∞ λ (t + 1) for t ∈ (0, 1). Using the representation (21) of u ∞ λ (t) for t ∈ (1, 2), and using (34), we infer that α λ (t + 2) = z λ α λ (t) for t ∈ (0, 1). It follows that α λ (t + 1) = z λ α λ (t -1) for t ∈ (0, 2). By induction, using (44), ( 22) and ( 21), we get that

α λ (t -1 + 2k) = z k λ α λ (t -1), (45)
for every t ∈ (0, 2) and every k ∈ N. Therefore, we have obtained that

λα λ (t + 2 + k) + (4 -2λ)α λ (t + k) + λα λ (t -2 + k) = p λ (z λ )α λ (t -2 + k) = 0,
for every t ∈ (0, 1) and every k ∈ N * . We conclude that L λ (h) = 0. Concerning the value of the objective functional of (OCP) ∞ λ , we infer that

+∞ 0 (1 -λ) (∂ x y(t, 0)) 2 + λu(t) 2 dt +∞ 0 (1 -λ) (∂ x y ∞ λ (t, 0)) 2 + λu ∞ λ (t) 2 dt,
with a strict inequality whenever h = 0. It follows that u ∞ λ is the unique optimal solution of (OCP) ∞ λ for λ > 0. For λ = 0 the result also follows from the representation (43) of L 0 (h), with the difference that, in this case, the characteristic polynomial is p 0 (z) = z having the unique root z 0 = 0.

The inequality (23) follows from (45), since for the optimal state we have the energy

1 0 (∂ x y ∞ λ (t + 2k, x)) 2 + (∂ t y ∞ λ (t + 2k, x)) 2 dx = t+2k+1 t+2k-1 α λ (s) 2 ds = t+1 t-1 α λ (s + 2k) 2 ds = |z λ | 2k t+1 t-1 α λ (s) 2 ds,
for every t ∈ (0, 2) and every k ∈ N. Theorem 1 is proved for T = +∞.

Remark 5. The computation of the solution with the characteristic polynomial p λ is related to techniques used for linear difference equations, or for finite-dimensional linear systems with tridiagonal matrices (see [START_REF] Meurant | A Review on the Inverse of Symmetric Tridiagonal and Block Tridiagonal Matrices SIAM[END_REF]).

Proof of Theorem 2

We assume that T = 2n. Using (25), we have 1 2n = 1+z λ 2 , and then, using ( 16) and the representation (21) of u ∞ λ , we infer (26). We have

2 0 u ∞ λ (t) 2 dt 1/2
(1 + z λ ) y 0 L 2 (0,1) + y 1 L 2 (0,1) .

The inequality (27) follows similarly, using ( 15) and ( 22), since

u T λ -u ∞ λ L 2 (2k,2k+2) = 1 -|z λ | k 2 0 u ∞ λ (t) 2 dt 1/2 .
Theorem 2 is proved.

Conclusion

We have discussed the influence of the objective function and of the time horizon on optimal Neumann boundary controls for the 1D wave equation. If the objective function is the control norm (λ = 1) and if the terminal state is prescribed exactly, then the control action is distributed uniformly over the whole time horizon, and coincides with the control given by the Hilbert Uniqueness Method, which is periodic.

In contrast, if the objective function involves an additional tracking term (λ < 1), then the optimal control action is essentially concentrated at the starting time 0 and at the terminal time T , and in-between it is exponentially close to 0. We have given explicit formulas, showing that the control is the sum of an exponentially decreasing term and of an exponentially increasing one. If the time horizon is infinite (without final conditions), then only the first term remains, and the optimal control exponentially stabilizes the system, accordingly to the classical Riccati theory. The norms of the control action and of the optimal state decay then exponentially in time. These results show that as soon as the objective functional of the optimal control problems for the considered system contains a nontrivial tracking term, the optimal solution has a special behavior referred to as the turnpike phenomenon.

Finally, we have shown that, if the final time T is a positive even integer, then there exists a weight λ such that the solution of the problem of exact controllability with minimal control norm coincides with the solution of the infinite horizon optimal control problem along the time interval [0,[START_REF] Colombo | Optimal Control in Networks of Pipes and Canals[END_REF]. This result justifies a receding horizon control strategy, where the first part of a finite horizon optimal control is used and then the procedure is updated in order to control the system over an infinite time horizon.

As already said, the turnpike property has been much investigated in finite dimension (see [START_REF] Trélat | The turnpike property in finite-dimensional nonlinear optimal control[END_REF] and references therein for a general result). In the infinite-dimensional setting, in [START_REF] Porretta | Long Time versus Steady State Optimal Control[END_REF] distributed control has been considered both for the heat equation and the wave equation.

The turnpike phenomenon put in evidence in the present paper shows an interesting qualitative bifurcation of the HUM control as soon as the objective functional involves a tracking term. However, here, we have been able to show it by means of explicit computations.

Several open questions are in order. First of all, it makes sense to consider an objective functional in which the tracking term is replaced with a discrepancy between the solution and a time-independent function, which is not necessarily a steady-state. According to the results of [START_REF] Trélat | The turnpike property in finite-dimensional nonlinear optimal control[END_REF], we expect then that the turnpike property still holds true, and that, in large time, the optimal trajectory remains essentially close to the optimal steady state state, defined as the the closest steady-state to the objective. However, in that case, we certainly do not have explicit formulas as derived in the present paper. Moreover, here we only considered a functional penalizing the normal derivative at x = 0, and then we can only consider a time-independent function that is a steady-state, as said in Remark 4. But if instead, we were considering for instance the full norm in H 1 (0, 1), then we could consider in the objective functional a term of the form y(t, •) -a(•) 2 , where a(•) need not be a steady-state.

Then, what can be expected is that, in large time, the optimal trajectory remains essentially close to the steady-state of the form σx that is the closest possible to the target a(•).

  for t ∈ (0, 2) and k ∈ N.The graph of ∂ x y T λ (t, x) is provided on Figure1, for T = 20, with λ = 24/25 on Figure1(a) and λ = 99/100 on Figure1(b). The control u T λ (t) = ∂ x y T λ (t, 1) is the boundary trace at the back.

  (a) λ = 24/25 and T = 20. (b) λ = 99/100 and T = 20.

Figure 1 :

 1 Figure 1: Plot of ∂ x y(t, x).

1

 1

4. 2 . 1

 21 Case T < +∞ Let y T λ be the state generated by the control u T λ defined in the theorem. Let us first prove that y T λ satisfies the terminal constraints

Acknowledgment. This work is supported by DFG in the framework of the Collaborative Research Centre CRC/Transregio 154, Mathematical Modelling, Simulation and Optimization Using the Example of Gas Networks, project C03 and project A03, by the Advanced Grant FP7-246775 NUMERIWAVES of the European Research Council Executive Agency, FA9550-14-1-0214 of the EOARD-AFOSR, FA9550-15-1-0027 of AFOSR, the BERC 2014-2017 program of the Basque Government, the MTM2011-29306-C02-00 and SEV-2013-0323 Grants of the MINECO and a Humboldt Award at the University of Erlangen-Nuremberg.

For more general multi-D wave equations, the situation is open. Even if explicit computations can only be done in specific cases, we expect that the turnpike phenomenon is generic within the class of optimal control problems for controllable wave equations, and that HUM controls characterized by the adjoint system develop a quasi-periodic pattern, but when characterized by a more robust optimality cost, then, satisfy the turnpike property.

Another open issue is the investigation of semilinear wave equations (see [START_REF] Coron | Global steady-state stabilization and controllability of 1D semilinear wave equations[END_REF]), for which steadystates may play an important role. Of course, in that case, we cannot expect that the turnpike property hold globally, but it should also hold as well at least in some neighborhood of an optimal steady-state (see discussions in [START_REF] Trélat | The turnpike property in finite-dimensional nonlinear optimal control[END_REF]).


Real-Time NMR Studies of Electrochemical Double Layer Capacitors

Hao Wang 1, 2 , Thomas K.-J. Köster 1, 2 , Nicole M. Trease 2 , Julie Ségalini 3 , Pierre-Louis Taberna 3 , Patrice Simon 3 , Yury Gogotsi 4 , Clare P. Grey *1, 2 ABSTRACT: 11 B NMR spectroscopy has been used to investigate the sorption of BF 4 -anions on a highly porous, high surface area carbon and different binding sites were identified. By implementing in situ NMR approaches, the migration of ions between the electrodes of the supercapacitors, and the changes in nature of ion binding to the surface have been observed in real-time.

Over the last several decades, the demand for energy has increased dramatically. With the increased use of renewable energy sources comes the challenge as to how energy can be stored and converted. 1,2 Both batteries and supercapacitors show great potential as electrical energy storage devices. Although batteries show higher energy densities, they have lower power handling abilities and shorter cycle lives. 3 Since the 1980s, Electrochemical Double Layer Capacitors (EDLCs or supercapacitors) have been developed to meet this demand, due to their extremely rapid rates of charge and discharge, and their essentially unlimited cycle life. 4 The storage of electrical energy in supercapacitors relies on the formation of an electrochemical double layer on the interface between a solid electrode and a liquid electrolyte solution. Upon charging, energy is stored as the cations and anions are electrostatically attracted to different electrodes, forming the double layers. Among all potential materials for supercapacitors, carbon has been widely used as the electrode, because of its high porosity, good electronic conductivity and low cost. 5 The porosity of carbon is crucial because it increases the effective surface area. 6 Furthermore, in 2006 Chmiola et al. reported that the normalized capacitance of carbon derived from titanium carbide dramatically increased when the average size of carbon pores matched the size of the solvated ion. 7 This finding could not be explained with traditional concepts of double layer formation and have triggered considerable work to understand the nature of electrolyte sorption inside the carbon. Many questions concerning this process remain unsolved. 5,8,9 Desolvation of ions has been experimentally demonstrated using in situ Quartz Micro-balance (QCM) measurements while charging porous carbon electrodes. 10 In principle, NMR spectroscopy can help to unravel the different processes that occur at the electrodes in supercapacitors, as it provides molecular-level, quantitative, and element-selective information about the structure and dynamics of the ions in the electrolyte and at the electrolyteelectrode interface. Indeed, in situ NMR has, for example, been used to look at the adsorption of methanol (and electrochemically produced CO and CO 2 ) on Pt fuel-cell electrodes as a function of potential and to investigate dynamic and structural processes in lithium ion batteries. [11][12][13][14][15] Previous ex situ magic angle spinning (MAS) NMR experiments have been conducted on carbon-based supercapacitors made with a tetraethylammonium (TEA + ) tetrafluoroborate (BF 4 -) salt in acetonitrile as the electrolyte. In these experiments, the supercapacitors were disassembled at different charge/discharge states, and 11 B NMR spectra were separately acquired for the cathode and the anode. 16,[START_REF] Deschamps | Experimental NMR Conference Pacific[END_REF] Although providing useful information, questions remain concerning the possibility of discharging the electrodes during the process of disassembly, and the changes in binding that arise due to the inevitable evaporation of the solvent. To overcome these limitations, we have applied in situ NMR experiments on supercapacitors for the first time. In situ NMR experiments not only allow the changes in local environments of the ions in the carbon electrodes in real time to be tracked, but also allow the dynamics of the different process that occur on changing the potential to be monitored. 14,[START_REF] Trease | Experimental NMR Conference Pacific[END_REF] This paper reports results from these studies, focusing on the behavior of the BF 4 anion. As in previous studies, we chose to focus the majority of our studies on 11 B rather than [START_REF] Harris | [END_REF] F NMR, since the electrodes comprise a composite mixture of carbon and polytetrafluoroethylene (PTFE).

First, to investigate the possible environments of the BF 4 -anions on the surface of uncharged carbon electrodes (in the supercapacitor system), sorption studies were performed. 11 B NMR spectra were acquired for carbon films of YP-17 (specific surface area 1709 m 2 /g), which were soaked with different amounts of 1.5M TEA-BF 4 in acetonitrile (Figure 1; see supporting information for more details). We performed static experiments rather than MAS, since the centrifugal forces in the spinning caused electrolyte to be extruded from the carbon pores. No significant losses in spectral resolution were observed. Three different environments were identified: for low electrolyte loadings (2 µL electrolyte; 6.1 mg of YP-17), a broad peak appears at -4.2 ppm, which is ascribed to strongly bound BF 4 -ions on the carbon surfaces. As more electrolyte is added, a second peak appears at higher frequencies (approximately 1.7 ppm with 5 µL), which is ascribed to ions that are only weakly affected by the carbon, i.e., the weakly bound ions in the outer sorption layers and/or ions contained within the larger mesopores, which will be in dynamic exchange with the ions in the outer sorption layers. Exchange occurs between the strongly (lower frequency resonances) and the weakly bound ions (higher frequency resonances) on the timescale of approximately 50 -500 ms, as shown by twodimensional (2D), magnetization exchange experiments (Figure S17) confirming that the weakly bound ions are in close proximity to the strongly bound ions. Both peaks shift slightly to higher frequency as more electrolyte is added reaching -1.7 and 4.3 ppm for 10 µL of electrolyte. Finally, three peaks (-1.7, 4.3 and 0.6 ppm) were observed when the film was fully soaked with electrolyte (15 µL). The third peak (sharp, 0.6 ppm), which only appears at the highest electrolyte levels, is ascribed to free ions in the bulk electrolyte that are not contained within the carbon pores. These assignments are consistent with earlier studies that find that free molecules (i.e., in the bulk electrolyte) are associated with higher chemical shifts than molecules adsorbed onto the surface of carbon. [START_REF] Harris | [END_REF] Following these studies, the shifts for the adsorbed species are ascribed to the magnetic susceptibility of the carbon and aromatic "ring-current" effects due to the carbon rings of the graphitic domains. Consistent with this assignment, is the observation (in a separate set of sorption experiments; Figure S8 andS11) of a set of lower frequency resonances (relative to the positions of the resonances of the weakly bound/free electrolyte peaks) when TEA-BF 4 sorption is probed with [START_REF] Harris | [END_REF] F NMR (for the anions), and with 1 H NMR for the TEA cations, confirming that this is local field affect rather than a chemical one due chemisorption. The previous studies of molecules adsorbed on carbons have similarly seen a shift of the resonance of the adsorbed species to higher frequencies as the loading level is increased, where the shift was ascribed to the exchange of ions in close proximity of the carbon surface with ions in outer layers. [START_REF] Harris | [END_REF]20 It is, however, important to note that the size of the shift seen in our studies as a function of sorption level varies somewhat depending on the orientation of the film in the field and the geometry of the bag, and these variations are, at least in part ascribed to macroscopic susceptibility effects (see supporting information). 21 Based on the intensities of the peak assigned to the strongly bound ions in the 10 and 15 µL sorption experiments we can estimate packing densities of approximately 0.37 and 0.53 anions/nm 2 , respectively, if we assume the ions are uniformly packed on the carbon surface (see supporting information). These numbers should be compared with the diameter of a solvated BF 4 -of 1.16 nm 22 . Assuming that the fully solvated BF 4

-anions are close packed on the carbon surface (1709 m 2 /g), the highest possible density of solvated anions is 0.86 anions/nm 2 . This calculation ignores the effect of the cations. To include them, we consider a centered cubic lattice formed of 1.30 nm cations and 1.16 nm anions (Figure S1), the centered lattice having a cell parameter of 2.46 nm (1.30 + 1.16 nm). A packing density of 0.33 anions/nm 2 is predicted. Numbers estimated in a separate sorption experiment for both the anions and cations are similar, but with very slightly more strongly bound cations than anions (see supporting information). Our estimates for the ion packing density are consistent with a high density of solvated cations and anions on the surfaces of the carbons and are surprisingly high given the curvatures and small nanometer sizes of many of the carbon pores (see below).

Previous sorption studies found that the spin-lattice (T 1 ) relaxation times are significantly reduced for molecules adsorbed on a carbon surface. 23 In a separate sorption experiment with 20 µL of electrolyte/6.1 mg carbon, a longer T 1 value of 8.1 s was obtained for the free electrolyte, whereas shorter values are obtained for the signals of weakly and strongly bound ions (4.0 and 3.2 s, respectively). The T 1 time of the resonance assigned to the weakly bound ions (in the mesopores) confirms that these ions are influ-enced by the carbon, and that the weakly bound resonance is not simply due to free electrolyte. The slow exchange between the two species (as probed by the 2D experiments) will, at least in part, be responsible for the reduction in T 1 time of this resonance. The reduction of 11 B spin lattice relaxation times near the carbon surface is ascribed to the interaction of the 11 B nuclear spins with the fluctuating unpaired spins at the Fermi level of the carbon conduction band.

Having identified different types of binding for BF 4 -ions in carbon electrodes, the migration and binding of ions in an actual supercapacitor was followed by in situ NMR spectroscopy. In these experiments, the NMR spectra of a supercapacitor were measured under simultaneous control of its state of charge via an external cycler. To perform these experiments, a supercapacitor based on the flexible plastic bag cell design reported previously was developed 13,14 (Figure 2a; see supporting information). Two pieces of carbon film with the same weight (11.2 mg/each) were cut and pressed onto pieces of carbon coated aluminum mesh and a polypropylene separator was placed between them. This assembly was soaked with the 1.5 M TEA-BF 4 in acetonitrile solution (approximately 50 µL) and was sealed inside a plastic bag in an argon atmosphere. In this design, which we refer to as "normal" in the following, the two electrodes are placed on top of each other. The bag cell was then put in the coil of the NMR probe, and connected with a cycler through the carbon coated aluminum mesh current collector (Figure S2). 11 B in situ NMR spectra of this bag cell were acquired as a function of state of charge (Figure 3). At 0 V, the spectrum is similar to the carbon soaked with TEA-BF 4 solution. The free electrolyte peak is very weak, and the lineshape seen in the spectrum is intermediate between those of 6.1 mg carbon with 10 and 15 µL of TEA-BF 4 solution in Figure 1. Importantly, the results indicate that most of the BF 4 -ions are located in the vicinity of the carbon probably due to the limited volume of the plastic bags (and thus electrolyte). As the voltage increased from 0 to 2 V, the high and low frequency peaks appear to merge, and at 2 V, only one resonance, with a shoulder to lower frequency can be seen. In the cell design described above (Figure 2a), NMR signals from both electrodes of the supercapacitor are investigated simultaneously and it is not clear how to separate the resonances associated with the different electrodes. To address this, a second design was used where the electrodes are no longer facing each other but rather are sheared so that they are separated by a 4 mm gap (Figure 2b). This configuration allows the NMR spectra of the individual electrodes to be monitored separately by placing only one electrode inside the NMR coil. The 11 B in situ NMR spectra of the supercapacitor charged from 0 to 2 V and charged from 0 to -2 V (Figure 4a -c) now show the individual spectra of the positive and negative electrodes. At 0 V, the same three electrolyte features are again identified: the strongly bound ions, weakly bound ions and the free electrolyte. The free electrolyte peak is slightly more intense in this design, presumably because the larger bag used in this experiment means that more electrolyte can be added. As this resonance overlaps strongly with the weakly bound ion peak (i.e., from the ions nearby the carbon), its relative amount is difficult to quantify accurately. All the resonances are shifted by approximately 4.4 ppm compared with the sorption study, including the free electrolyte peak, which we ascribe to bulk susceptibility effects associated with the orientation of the carbon and bag geometry (with respect to the magnetic field) used in this experiment, as discussed in the supporting information. As shown in the supporting information, small variations in the relative concentrations of the different peaks and their shifts are noted from experiment to experiment, but the results described here are consistent from one experiment to the next. Compared with the normal supercapacitors (Figure 3), the "long" capacitors require a much longer time for the current to reach equilibrium after the applied potential has been changed (see supporting information). On charging from 0 to +2V, the signal at lower frequencies becomes narrower and moves to higher frequencies towards the peak that was previously assigned to the weakly bound ions (Figure 4a). This is consistent with the results of the normal cell design. The peak assigned to the weakly bound ions becomes narrower. A different behavior is observed when charging from 0 to -2V (Figure 4b). Most noticeable is the loss in intensity of the resonance due to the strongly bound ions (below -0.5V) and its gradual shift to higher frequency. This resonance can no longer be observed at -2V. Again the peak at higher frequencies becomes narrower but now also shifts to lower frequency, so that at -2V a sharper, more Lorentzian lineshape is observed. A plot of the total integrated signal intensity shows, as expected, a steady decrease in BF4 -concentration from +2V to -2V. T 1 relaxation times were measured in a separate experiment. The spin lattice relaxation times of the strongly bound BF 4 -ions decrease from 2.1 to 0.3 s as the voltage was increased from -2 to 2V (Figure 5). This noticeable decrease in relaxation time is assigned to increased anion-carbon interactions at positive potentials and possibly effects due to changes in the density of states at the Fermi level of carbon, due to injection of (positive) charge. It is also of note that the T 1 times of frequency signal represents an average of both environments). The weakly bound ions are af-fected by the applied voltage (5.0 s at -2 V, 0.5 s at +2 V), showing that the influence of the carbon on the relaxation behavior is not restricted to the first adsorbed layer, consistent with a slow exchange of the weakly bound ions with the strongly bound ions, in the timescale of the T 1 experiment (i.e., 1 -5 s). (Note that we cannot unambiguously separate the signals of weakly bound and free ions, so the T 1 data for the high-frequency signal represents an average of both environments. The great majority of the BET "surface" of a high surface-area carbon actually arises from an internal "surface" and the outer surface of carbon particles can be neglected (less than 1% of total surface area). In YP-17, 28% of the pores are less than 1 nm, 40% are between 1 and 1.5 nm, while the rest are greater than 1.5 nm. BF 4 -is small enough to occupy sites in even the smallest of pores, but only, in this case, and as proposed by Chmiola et al. if it is stripped of some of its solvation shell on charging. 7 Without further experiments it is difficult to test this hypothesis. However, an important observation in our experiments is that we observe the strongest influence of the electrode potential on the resonance assigned to the strongly bound anions. Charging of the carbon causes a change in the local environments of these anions, as seen by their different shifts and the shorter T 1 s (on positive charging). Since these ions (or their nuclear spins) are in close proximity to electrons near the carbon Fermi level, changes in the electron density at the carbon surface (and thus on phenomena such as the ring currents) can have a significant effect on the NMR spectra of the BF 4 -ions, as suggested in recent ex situ studies of supercapacitors. [START_REF] Deschamps | Experimental NMR Conference Pacific[END_REF] Changes in the average distances to which these ions approach the carbon, and also their average lifetime in these strongly bound sites, will also affect their observed chemical shifts.

In conclusion, in situ NMR experiments have been performed on Electrochemical Double Layers Capacitors (supercapacitors). The experiments allow distinct ionic coordination sites to be identified and represent a simple method with which to study the migration of ions in working supercapacitors. In the normal supercapacitor design (Figure 3), it is surprising that most of the anions in the electrolyte are located nearby the carbon, which we ascribed to the very high internal surface area of the carbon used here, the relatively non-polar solvent and limited volume of electrolyte. As expected, the anions move to the positively charged electrode on charging from -2 to +2 V. Loss of the strongly bound anions, that form the 1 st layer of the "double layers" in a negatively charged electrode, in a conventional model of a charged surface, is clearly visible after < -1V. Any ions that are present in this layer (if any) undergo rapid exchange with the ions in more distant layers. On charging both the concentration of the anions changes, as does the nature and strength of the anion binding to the surface. The method holds much promise for the study of other supercapacitors systems and extensions to investigate the structure and dynamics of the processes that occur in a wider range of carbons/electrodes are underway. Applications of similar NMR methodologies to investigate solid -liquid interfacial structures and double-layer formation in a wide range of systems can be readily envisaged.

ASSOCIATED CONTENT

Supporting Information. Preparation of carbon films, configuration of bag cells, ex situ and in situ NMR spectroscopy methods and experiments, additional sorption experiments with 0.5 M and 1.5 M electrolyte, comparison between spectra of carbon films aligned perpendicular and parallel to the field, current relaxation curves of normal vs. "long" supercapacitors when a constant voltage was applied, second "long" supercapacitor result. This material is available free of charge via the Internet at http://pubs.acs.org.

Figure 1 .

 1 Figure 1. 11 B NMR spectra of YP-17 carbon films with different amounts of 1.5M TEA-BF 4 in acetonitrile in plastic bags.

Figure 2 .

 2 Figure 2. a: Configuration of a normal supercapacitor cell for in situ NMR study. b: Configuration of a "long" supercapacitor with two separated electrodes.

Figure 3 .

 3 Figure 3.In situ11 B static NMR spectra of a normal YP-17 supercapacitor held at different voltages. In this experiment, both electrodes were placed inside the NMR coil as illustrated in Figure2a.

Figure 4 .

 4 Figure 4. In situ 11 B static NMR spectra of a"long" YP-17 supercapacitor held at different voltages. In these experiments, only one electrode is placed inside the NMR coil (see Figure 2b.) a: supercapacitor charged from 0 to 2 V (positive electrode). b: supercapacitor charged from 0 to -2 V (negative electrode). c: stacked plot of Figure 4a and 4b. d: Integrated areas of the spectra in Figure 4a -c as a function of applied voltage.

Figure 5 .

 5 Figure 5. 11 B T 1 times for the "long" YP17 supercapacitor. Triangles and circles represent data for low-frequency (strongly bound anions) and high-frequency peaks (weakly bound and free ions), respectively.

AUTHOR INFORMATION

Corresponding Author cpg27@cam.ac.uk ACKNOWLEDGMENT. T.K. thanks the Deutscher Akademischer Austauschdienst for a postdoctoral research stipend. C.P.G. and H.W. thank NYSERDA and the EU ERC programs for support. P.S. and Y.G. would like to thank the Partner University Fund (PUF) for funding their collaborative efforts.


Dimitri P Bertsekas

Didier El Baz

DISTRIBUTED ASYNCHRONOUS RELAXATION METHODS FOR CONVEX NETWORK FLOW PROBLEMS by

We consider the solution of the single commodity strictly convex network flow problem in a distributed asynchronous computation environment.

The dual of this problem is unconstrained, differentiable, and well suited for solution via Gauss-Seidel relaxation. We show that the structure of the dual allows the successful application of a distributed asynchronous method whereby relaxation iterations are carried out in parallel by several processors in arbitrary order and with arbitrarily large interprocessor communication delays.

Introduction

Consider a directed graph with set of nodes N and set of arcs A. Each arc (i,j) has associated with it a cost function gij: R+(--,+-]. We denote by f.. the flow of the arc (i,j) and consider the problem of minimizing total cost subject to a conservation of flow constraint at each node minimize g (fi )

(1) (i,j)EA 3 13 subject to mi - f. = 0, ViEN. (m,i)EA (i,j)EA

We assume that problem (1) has at least one feasible solution.

We also make the following standing assumptions on gij: a) gij is strictly convex, and lower semicontinuous.

b)

The conjugate convex function of gij, defined by gj (tij) = sup {t.f gj(fi )}, (2) f3 .

1 ij i j gij ij 1]
is real valued, i.e.

-a <gj (tij)<for all real tij. (Because of the strict convexity assumed in a) above, gj. is also continuously differentiable

1J

and its gradient denoted Vgj (t. .) is the unique f. attaining the supremum 13j 13 13 in (2)--see [START_REF] Rockafellar | Convex Analysis[END_REF], pp. 218,253).

It is easily seen from ( 2) that Assumption b) implies that lim g .(f )=-. Therefore the objective function of the primal problem (1)

Ifiji Z1] 1]
has bounded level sets ( [START_REF] Rockafellar | Convex Analysis[END_REF], Section 8). It follows that there exists an optimal solution for problem [START_REF] Rockafellar | Network Flows and Monotropic Optimization[END_REF] which must be unique in view of the strict convexity assumed in a).

The problem above is of great practical interest and has been studied for a long time.

Except for strict convexity our assumptions are not overly restrictive.

For example they are satisfied in the following two cases:

1) The constrained case where gj is of the form

co if f ij i[k ij'cij ] gi~ (f IT^) = 13(3) gijfij) gj(f ij) otherwise
where kij and cij are given lower and upper bounds on the arc flow, and gij is a strictly convex, real valued function defined on the real line R.

2) The unconstrained case where gij is strictly convex, real valued and its right and left derivatives gij and gij satisfy

lim gij (fij) lim gij(fij) = -". (4
) f .. Xo f.. + -00

13 13
A dual problem for (1) is given by minimize q(p) subject to no constraints on the vector p = {piieN}, [START_REF] Powell | On Search Directions for Minimization Algorithms[END_REF] where q is the dual functional given by

q(p) = *.(pi-p). ( 6
) (ij)EA 1
We refer to p as a price vector and its components Pi as prices. The ith price is really a Lagrange multiplier associated with the ith conservation of flow constraint. The duality between problems (1) and ( 5) is well known and is explored in great detail in the recent book by Rockafellar [START_REF] Rockafellar | Network Flows and Monotropic Optimization[END_REF]. The earlier book by Rockafellar [START_REF] Rockafellar | Convex Analysis[END_REF] gives the necessary and sufficient condition for optimality of a pair (f,p). A feasible flow vector f = {fij.(i,j)eA} is optimal for (1) and a price vector p = {pili£NI is optimal for (5) if and only if for all arcs (i,j) ( [START_REF] Rockafellar | Convex Analysis[END_REF], pp. 337-338) pi-Pj is a subgradient of gij at fij.

An equivalent condition is f.gij = Vg(pi-pj), ¥ (i,j)mA. ( 7
)
Any one of these equivalent relations is referred to.as the complementary slackness condition, and is shown in Figure 1.

gij(fij ) = fijl + I (fij)2 ij ij 2j ij
Since the dual problem is unconstrained and differentiable it is natural to consider algorithmic solution by a descent iterative method.

The Gauss-Seidel relaxation method is particularly interesting in this respect since it admits a simple implementation. Given a price vector p, a node i is selected and its price Pi is changed (relaxed) to a value Pi such that Vg* (p

) = Vg.j (pi-pj (8) (m,i)EA mi m i (i,j)EA 1] 1
It is easily seen (compare with the definition (6) of the dual cost q) that this equation is equivalent to q =0, so the dual cost is minimized at Pi with respect to the ith price, all other prices being kept constant. The algorithm proceeds by relaxing the prices of all nodes in cyclic order and repeating the process. The convergence of this algorithm does not follow immediately from standard results on relaxation methods [START_REF] Zangwill | Nonlinear Programming[END_REF], [START_REF] Sargent | On the Convergence of Sequential Minimization Algorithms[END_REF], [START_REF] Polak | Computational Methods in Optimization: A Unified Approach[END_REF] since these results require some assumption that is akin to strict convexity of the dual objective function which does not hold here (for a counterexample see Powell [START_REF] Powell | On Search Directions for Minimization Algorithms[END_REF]). However Cottle and Pang [START_REF] Cottle | On the Convergence of a Block Successive Overrelaxation Method for a Class of Linear Complementarity Problems[END_REF] have shown convergence of a network algorithm based on relaxation. It applies to transportation problems with quadratic cost function, and involves certain restrictions in the way relaxation is carried out.

Their results is substantially extended in Bertsekas, Hossein, and Tseng [START_REF] Bertsekas | Relaxation Methods for Network Flow Problems with Convex Arc Costs[END_REF].

Our main objective in this paper is to explore the convergence properties of distributed versionsof the relaxation method just described.

Here we assume that each price pi is under the control of a separate processor who changes Pi to Pi on the basis of (8) and communicates the new value to the other processors. One can consider a parallel computation procedure carried out in an orderly manner whereby all processors exchange their current prices before carrying out their relaxation iteration. Mathematically this would be equivalent to a Jacobi type of relaxation procedure.

We would like to consider, however, a much more general procedure whereby the communication between processors is not regular, and the information available at some processors regarding prices of other processors may be arbitrarily outof-date.

In addition we allow some processors to iterate more frequently than others. Models of such asynchronous algorithms have been formulated some time ago and by now there is considerable understanding of their convergence properties (see [START_REF] Chazan | Chaotic Relaxation[END_REF]- [START_REF] Authie | Distributed Asynchronous Iterative Control Algorithms, Optimal Routing Application[END_REF]; [START_REF] Bertsekas | Convergence Theories of Distributed Iterative Processes: A Survey[END_REF] is a survey). It turns out that the dual problem [START_REF] Powell | On Search Directions for Minimization Algorithms[END_REF] has structure that allows us to show that the asynchronous relaxation method has satisfactory convergence properties. This is particularly true when the dual problem ( 5) has an essentially unique optimal solution. Otherwise satisfactory convergence depends on the starting point.

These results are all new and are shown in Section 3. The next section analyzeSthe structure of the dual solution set and provides some preliminary analysis.

The results of this paper carry over verbatim to the case where the conservation of flow constraint has the form

I fmi - f. =b , ViN (m,i)£A (i,j)EA
where bi are given scalars with I bi=0.

The dual cost of ( 6 The results of this paper can also be extended in a simple manner to network problems with positive gains and strictly convex arc costs. This extension was mentioned to us by P. Tseng who also showed [START_REF] Tseng | Relaxation Methods for Monotropic Programming Problems[END_REF] two additional interesting facts.

First that Proposition 2 holds even if the strict convexity assumption of a) is removed thereby including the important class of linear minimum cost flow problems.

Second that, within the class of monotropic programming problems, the largest class for which the monotonicity property of Proposition 1 holds is the class of network flow problems with positive gains.

Our notational conventions are that a subscript denotes a node or processor index, and a superscript denotes a time or iteration index. All vector inequalities should be interpreted in a coordinatewise sense.

In order to simplify notation we have implicitly assumed that there is at most one arc associated with any ordered pair of nodes i and j, so that the arc notation (i,j) has unambiguous meaning. However this assumption is not essential to any of our results.

Structure of the Optimal Dual Solution Set

Our standing assumptions a),b) guarantee that the primal problem (1) has a unique optimal solution. Existence of an optimal solution of the dual problem can be guaranteed under an additional (mild) regular feasibility assumption in which case the existence theorem of [START_REF] Rockafellar | Network Flows and Monotropic Optimization[END_REF], p. 360 applies.

On the other hand the optimal solution of the dual problem is never unique since adding the same constant to all coordinates of a price vector p leaves the dual cost unaffected.

We can remove this degree of freedom by constraining the price of one node, say node N, to be zero.

(With slight abuse of notation we number nodes as 1,2,...,N).

Thus we consider the reduced dual optimal solution set P* defined by

P*= {p*jq(p*) = min q(p), PN* = 0} (9) N p
where q is the dual objective function

q(p) = E gj (Pi-Pj) . ( 10
) (i,j)EA
For the most part of the paper, we will operate under the following assumption: Assumption 1:

The reduced dual optimal solution set P* is nonempty and compact.

Assumption 1 is not overly restrictive. For example let {f jl(i,j)EA} be 13 the unique primal optimal solution, and consider the set of arcs A = {(i,j) f*. lies in the interior of the set {fij gijg (fij)<o}} ( 11)

1] 13 1]7 1J
Then Assumption 1 is satisfied if the subgraph (N,A) is connected.

To see this note that for all arcs (i,j)EA we have a bounded set of subgradients of gij at fi. thereby implying a bounded set of price differences Pi-Pj corresponding to dual optimal solutions [cf. [START_REF] Cottle | On the Convergence of a Block Successive Overrelaxation Method for a Class of Linear Complementarity Problems[END_REF]].

Note that in the unconstrained case mentioned in the previous section every arc belongs to A so, if the original graph is connected, Assumption 1 is satisfied. The constrained case of the previous section can be converted to the unconstrained case by replacing constraints by nondifferentiable penalty functions (see [START_REF] Bertsekas | Constrained Optimization and Lagrange Multiplier Methods[END_REF],

Section 5.5).

For example, assuming a dual optimal solution exists, a constraint f.. > 0 can be eliminated by adding to the cost gij a penalty 1] -c max{0,-f .. } + [max{0O,-f. i}] with c positive and sufficiently large.

Consider now the set

P = I = 0{ppN (12)
and for i=l,...,N-l, the point-to-set mapping Ri which assigns to a price

- 1 R.(p) < P. (p') if p < p'. (16) 1
Proof:

To show continuity of R. we argue by contradiction. Suppose there exists a convergent price vector sequence pk + p such that the corresponding sequence {R i ( p )} does not converge to R i (p). By passing to a subsequence if necessary suppose that for some 6 > 0 we have

R i (p) > R(p) + 6 y k (18)
(the proof is very similar if 6 < 0 and the inequality is reversed). By the definition of R. we have

m M ii 1 j

Since p + p it follows using (18) that for sufficiently large k we have

k k Pm-R i( pk) > Pm-Ri(p) V (m,i)eA 1 1 m 1 R(p )-pj < Ri(p)-p.
V (i,j)£A.

Therefore for sufficiently large k we have using the convexity of g*i, g* gmin ij

Vgi(Pm-Ri(P ())

VV (m,i)pA, - k k gij (Ri(p )-pj) < Vgij(Ri(p)-pj), V (i,j)cA. 1 - 131ij(Ri p-pj)
Using these relations together with [START_REF] Bertsekas | Relaxation Methods for Network Flow Problems with Convex Arc Costs[END_REF], [START_REF] Tseng | Relaxation Methods for Monotropic Programming Problems[END_REF] we obtain for all sufficiently

large k A k- k mi ,Vg .(p -Rj(p)) = Vgi(pm~-Ri(p )), V (m,i)cA (21)
A k k f.. For k sufficiently large so that (21), ( 22) hold we have

R.i(p) = max{pilpi c Pm-Imi, (m,i) £A, PiFiij-pj, (i,j)cA} --^ .£ k A k R.i(p ) = max^p ji Pp k
, (m,i)EA, Pi Iij-P (i,j)cA} Since pp, it is evident from these relations that R i (pk) -R.(p) thereby contradicting [START_REF] Bertsekas | Constrained Optimization and Lagrange Multiplier Methods[END_REF].

To show monotonicity of Ri we again argue by contradiction. Suppose there exist p and p' such that pj > pj, V j=l,...,N-l but Ki(P) > Ri(p' ) . It follows then that

PRi (P') > Pm i (P) V (m,i)£A R.i(p')-p' < R.(p)-p, V (i,j)eA.
Therefore

Vgm(P'-R (P')) > Vg* i(m-Rp (p)), V (m,i)EA ( 23
) miPm i 1 Vgj (Ri(P')-p!) < Vg'j(Ri(p)-pj) V (i,j)cA (24)
Since by definition we have

Vg* (PM (P')) = g(R(P t )-') (25) mi m 1 ij(Ri -P m 1 C Vgmi(Pm-R.(p)) Vgj (R (P) Pj) (26) m 3
it follows that equality holds in ( 23), (24), i.e.

A f We have for all (m,i)eA

= Vg* (Pm-Ri(PI)) Vg*(p R(p)) f i =Vmi m i (Pmi m fij = Vgij(R i (p')-j ) = Vgij (R i ( P)-p j)
Pm i ( p ) £ Imi' Pm -R i (p) Imi
and since p < 'p we obtain

in-m P R. (p) < ' -R.(p') -6 < Pm - (p') Therefore p' -R.(p') I 6 V (m,i)£A -m 1 'Imi'
and similarly R.i(P') + 6 -pj £ V (i,j)sA.

It follows that

Ri(P') + 6£ Ri(P')

thereby contradicting the maximal nature of Ri [cf. [START_REF] Tsitsiklis | Problems in Decentralized Decision Making and Computation[END_REF]].

The proof of continuity and monotonicity of R. is analogous with the

--1.
one just given for Ri and is omitted Q.E.D.

The monotonicity and continuity of the mappings Ri and R.i imply a thus far unreported and somewhat surprising property of the optimal dual solution set. It is easily seen that we have Ri(p) < Pi, for all i so, using the monotonicity of Ri shown in Proposition 1, we obtain

k+l -1 p< R (p) < R (p) V k (29)
where R: R N-1 + R N-1 is the mapping

R(p) = [R 1 (p),..,R N_ 1 (p)] ( 30
)
and R is the composition of R with itself k times. From (29) we see that the sequence R (p) converges to some p and by continuity of R we must have

A A A A A A p = R(p)
as well as p > p. Since p = R(p) implies that pep* it follows from the choice of p that p -p. Also from (28), (29) and the fact p < R(p) for all peP* we obtain p = p > p for all peP* which shows that p is a maximal element of P*. The proof for existence of a minimal element p is entirely similar. Q.E.D.

Convergence Analysis of Asynchronous Relaxation

The model of distributed asynchronous computation we adopt is described in [START_REF] Bertsekas | Distributed Dynamic Programming[END_REF], [START_REF] Bertsekas | Distributed Asynchronous Computation of Fixed Points[END_REF].

With each node i = 1,...,N-l we associate a processor that computes from time to time some element of Ri(p) (here p is the latest price vector available to processor i),and sets the price Pi to this element. This price is then communicated at some later time to all other processors. Computation and communication at the various processors need not be synchronized. The precise model is as follows:

At each time instant, node i can be in one of three possible states compute, transmit, or idle. In the compute state node i computes a new price Pi. In the transmit state node i communicates the price Pi obtained from its own latest computation to one or more nodes m(mfi). In the idle state node i does nothing related to the solution of the problem.

We assume that computation and transmission for each node takes place in time intervals [tl,t 2 ] with t 1 < t 2 , but do not exclude the possibility that a node may be simultaneously transmitting to more than one node nor do we assume that the transmission intervals to these nodes have the same origin and/or termination. We also make no assumptions on the length, timing and sequencing of computation and transmission intervals other than the following:

Assumption 2: For every node i and time t > 0 there exists a time t' > t such that [t,t'] contains at least one computation interval for i and at least one transmission interval from i to each node m such that (m,i)cA or (i,m)eA.

Assumption 2 is very natural. It states in essence that no node "drops out of the algorithm" permanently--perhaps due to a hardware failure.

Without this assumption there is hardly anything we can hope to prove.

k P = p R (p) < p < R (p)} , k = 1,2,... ( 35
)
Note that the sequence P -} is nested and that the common intersection of the sequence is the set P of (33).

We will apply now a convergence theorem given in Section 3 of [START_REF] Bertsekas | Distributed Asynchronous Computation of Fixed Points[END_REF] (orProp. 3.1 of [START_REF] Bertsekas | Convergence Theories of Distributed Iterative Processes: A Survey[END_REF]).

According to this theorem the desired result will be proved if the following three conditions are satisfied. (Rather than consulting the references just cited, the reader may wish to think through the proof of this since it is rather simple). It is easily seen that all the conditions stated above are satisfied in our case so the desired conclusion follows.

Q.E.D.

Proposition 3 shows that the ARM has satisfactory convergence when P* has a unique element. One way to guarantee this is to consider the optimal solution f* of the primal problem (1) and the set of arcs A = {(i,j)eA i gij is differentiable at f*j}.

Then,if the graph (N,A) is connected,P* consists of a unique point in view of the complementary slackness condition [START_REF] Rockafellar | Convex Analysis[END_REF].

In order to improve the convergence properties when P* has more than one point it is necessary to modify the ARM so that a computation at node i replaces Pi with R.

Q.E.D.

There is a similar result for the minimal ARM whereby pis replaced by p and condition (36) is replaced by p (i) < p for all i. The following example demonstrates that the results of Proposition 3 and 4 cannot be improved.

Example: Consider the 3-node network shown in Figure 2. The reduced dual optimal solution set is derived from condition [START_REF] Rockafellar | Convex Analysis[END_REF] and is given by

P* = P 3 = 0, 1 -1 P2 < 1
The results of Proposition 3 and 4 are illustrated in Figure 3. To see that the ARM as well as the maximal and minimal ARM may not converge to a dual optimal solution, let the buffer contents of processors 1 and 2 be both equal to (-1,1) and let both processors update the respective price coordinates and then exchange the results of the computation. Then the buffer contents will be (1,-1), and by repeating this process one more time the buffer contents will become again (-1,1) thereby completing a cycle. Therefore in general we cannot expect convergence of the ARM to the optimal solution set if the latter contains more than one element. Similarly the maximal and minimal ARM need not converge to p and p respectively if the initial buffer contents do not belong to the appropriate regions [cf. (36)].

Note that this counterexample applies also to a synchronous Jacobi method.

Figure 1 :

 1 Figure 1: Complementary slackness condition diagram for cost function

  ) must then include ~~iEN the term I b.p., and the relaxation equation (8) must include an additional iN I I term bi in its right side. This extension is important from the practical point of view, but we have restricted attention to the case where b.=O, ViSN in order to 1 simplify notation.

. 1 - 1

 11 vector pcP the set of all prices Pi that minimize the dual cost along the ith price starting from p, i.e. (cf. (8)). R.(p) = {p.j P.= P' l is well known that a real valued convex function having one compact level set, has all its level sets compact ([7], p.70). Therefore under Assumption 1 the sets Ri(p), pEP are all nonempty, compact intervals. It follows that under Assumption 1 the (point-to-point) mappings R i (p) = ^ max Pi are well defined on the set P. We call R. (Ri) the ith maximal (minimal) relaxation mapping. It gives the maximal (minimal) minimizing point of the dual cost along the ith coordinate starting from its argument. The point-toset mapping R. is called the ith relaxation mapping. Some key facts are given in the following proposition. Proposition 1: Let Assumption 1 hold. The mappings Ri and R.i are continuous on P. They are also monotone on P in the sense that for any p, p'£P, i = 1,...,N-1 we have R.(p) < R (p') if p < p',

=

  Vgi(R i(p)-pj) = Vgj(R(p )-p), Imi and Iij given byImi = {tl Vgi(t) = mi , V(m,i)eAI.j = {t| Vg j(t) =f} (i,j)EA.

6 =

 6 R.(p) -R.(p').

Proposition 2 : 6 {Pi ± 6 ,

 266 Let Assumption 1 hold. Thereexist a maximal and a minimal optimal solution of the dual problem, i.e. there exist peP* and peP* such that p < p < p, VpeP* . (27) Proof: Since P* is nonempty and compact it contains a noninferior element p for which there is no vector pEP* such that p 7 p and pi > Pi for all i. From the definition of Ri and the optimality of p we have Pi < Ri(p) for all i. Furthermore for all i the vector (pl,-...Pi l,Ri(p),Pi+l -,,pN belongs to P* so from noninferiority of p it follows that Ri (p)< p.. Therefore we have Pi = Ri (p) for all i. Let now p be a price vector obtained from p according to Pi +

(

  The existence of such vectors was established in the proof of Proposition 2).Consider the sets -k

a) 0 (

 0 If peP then for every i the vector p' with coordinates t p. if j i Ri(p) if j = i (cf. the equation (32) associated with computation at node i)pEP and paP then, for every i and m, the vector p' equation (31) associated with transmission from node m to node i), also belongs to P c) c) If p(l),...,p(N-l) belong to P then the vector p' with coordinates p = R.(p(j)) , j = 1,...,N-1 pI = cf. a computation (32) at each node followed by a transmission to every other node), belongs to Pk+l

(p) 1 (

 1 not just any element of Ri(p)). We call this the maximal ARM. If in place of R. (p) we use R. (p) the resulting method is called the minimal ARM.

  proof is identical to the one of Proposition 3 except that the set P of (35) should be replaced by P

Figure 2 The

 2 Figure 2

[15] El Ba;, D., "Etude d'algorithmes iteratifs de calcul parallele application a la resolution distribuee du probleme du routage optimal dans un resau maillea commutation de paquets", These de Docteur Ingenieur, Toulouse, 1984.

t Work supported by the National Science Foundation under Contract NSF ECS-8217668 and the Defense Advanced Research Projects Agency under Contract ONR-N00014-84-K-0357. *Room No. 35-210, and supported by an INRIA Grant.

Each node i has a buffer Bim for each mii where it stores the latest transmission from m, as well as a buffer B.. where it stores its own price estimate Pi. The contents for each buffer Bim at time t are t t denoted pt(i). Thus pm(i) is, for every t, i and m an estimate of the price Pm available at node i at time t. It is important to realize in t t what follows that the buffer contents pm(i), and pt(i') at two different nodes i and i' need not coincide at all times.

If ism and i', m the buffer contents pt(i), and pt(i') need not coincide at any time t. The vector of all buffer contents of node i is denoted pt(i), i.e.,

The rules according to which the buffer contents pm(i) are updated are as follows:

(1) If [tl,t 2 ] is a transmission interval from node m to node i, the contents of the buffer Bmm at time tl are transmitted and entered in the buffer B. at time t2, i.e. t2 t 2 1

] is a computation interval for node i, the content of the buffer Bii is replaced at time t 2 with an element of Ri (p (i)), i.e.

(3) The contents of a buffer Bii can change only at the end of a computation interval for node i. The contents of a buffer Bim, iim can change only at the end of a transmission interval from m to i.

The algorithm based on (32) will be called Asynchronous Relaxation Method (ARM).

Our objective is to derive conditions under which limit points of the sequences {pt(i)} are optimal solutions of the dual problem [START_REF] Powell | On Search Directions for Minimization Algorithms[END_REF]. The following proposition is our main result. The proof is based on a general convergence theorem given in [START_REF] Bertsekas | Distributed Asynchronous Computation of Fixed Points[END_REF] (see also [START_REF] Bertsekas | Convergence Theories of Distributed Iterative Processes: A Survey[END_REF]) and applicable to asynchronous iterative algorithms such as the one just described. The key property that makes asynchronous convergence possible is the monotonicity of the mappings Ri and Ri shown in Proposition 1. This property is also present in dynamic programming models and has been similarly exploited to show the validity of asynchronous versions of the successive approximation method [START_REF] Bertsekas | Distributed Dynamic Programming[END_REF].

Proposition 3: Let Assumptions 1 and 2 hold. For any initial buffer contents p (i) P, i = 1,...,N-1, each limit point of the sequences fpt(i)} generated by the ARM belongs to the set

where p and p are the maximal and minimal dual optimal solutions. In particular, if the reduced dual optimal solution set P* consists of a unique vector p* we have