Diego Arenas
email: diego.arenas@ifsttar.fr

Rémy Chevrier

Saïd Hanafi

Joaquin Rodriguez

Solving the Train Timetabling Problem, a mathematical model and a genetic algorithm solution approach

Keywords: Timetabling, TTP, Train Scheduling, Genetic Algorithms

The construction of a timetable represents a critical part on the development of the yearly service plan for railway operations. The Train Timetabling Problem (TTP) aims to find a timetable that must respond both to commercial needs and certain capacity and security related constraints. The combination of the latter, makes the TTP a complex and time consuming process. While most approaches on the literature offers exact solving models, once they are applied on real-size instances, they fail to solve the problem within a reasonable amount of time. Reason for which, heuristic or relaxation techniques are extensively used. In this paper, we first propose an alternative mathematical model to tackle the TTP. Next, we present a Genetic Algorithm implementing our model in order to rapidly obtain nearoptimal train timetables. Finally, we test the implementation of our model on a case study based on the German railway network.

Introduction

A train timetable defines the set of departure and arrival times for the train lines at the stations or other relevant locations in the rail network.

The construction of the train timetable, or train timetabling problem (TTP), represents only the first step of an even larger and more complex process: the yearly rail service planning. As its name suggests it, it consists on the definition of the plan, and the allocation of resources to provide the annual train services, i.e., timetables, crew schedules, rolling stock usage, etc. It is an iterative process where the output of one step is used as input to the next one, and when a conflict appears and can not be solved on the current level, one must go back to the previous step to make the necessary adjustments. The process is described in Figure 1 and briefly summarized on the next paragraph.

Once a feasible timetable is obtained, a route plan has to be designed. This is known as the routing and platforming problems, and consists on the allocation of platforms, inbound and outbound routes for the scheduled trains into the stations. The next step is the rolling stock planning, which specifies among other things, which engines and carriages will be used for each scheduled train of the timetable. Finally, the crew schedule, which defines the The timetable must respond to the commercial requirements of the customers, both passengers and freight traffic, while respecting also some security and capacity constraints. These constraints are determined by the characteristics of the rolling stock and the infrastructure of the network. Typically, these constraints are called hard constraints, which mean that they can not be violated, e.g., minimum running time, minimum headway time, maximum number of platforms at some station etc. While some kind of commercial requirements and quality aspects are called soft constraints, their observance is not mandatory, but their transgression often leads to economic costs or reduction of overall quality of the service, e.g., key time, connections, etc.

The combination of the requirements and constraints as well as the large number of trains and journeys to schedule, makes this problem very difficult to solve. The train timetabling problem (TTP) is proven to be NP-Hard by Caprara et al. [START_REF] Caprara | Modeling and solving the train timetabling problem[END_REF].

Furthermore, some of the commercial requirements may come into conflict with capacity constraints or with the maintenance activities of the network. These conflicts should be rapidly identified, since, in most of the cases, a negotiation between the train operating companies and the railway infrastructure manager is required, leading to further time consumption. By Taking this into account, we observe that the preparation of a yearly timetable is a complex, costly and time consuming process that usually takes several months to be fully completed.

Traditionally, the timetabling process was undertaken by the experts planners of the railway service. However, since the nineties, the benefits of using optimization models and techniques to solve the TTP were recognized and applied. The majority of these approaches are based on a mathematical formulation of the problem that could give exact solutions to the problem. However, due to its high complexity and impractical computing time, metaheuristics and relaxation techniques are applied to solve the model.

The contribution of this work is twofold. First, we propose a mathematical formulation of the TTP which can be implemented using different optimization techniques, such as lin-ear programming or meta-heuristics. Second, we develop a genetic algorithm implementing our model in order to rapidly obtain optimal or near-optimal train timetables.

The rest of the paper is structured as follows. Section 2 reviews some related work. Section 3 defines the TTP and presents our proposed formulation. Section 4 describes the implementation of our genetic algorithm to solve the TTP. Section 5 presents the case study and discuss the results of experimentation. Finally, Section 6 concludes the paper and present some perspectives for future work.

Related Work

Several approaches to tackle the TTP can be found on the literature, for a comprehensive survey of these, review Assad [START_REF] Assad | Models for rail transportation[END_REF], Cordeau et al. [START_REF] Cordeau | A survey of optimization models for train routing and scheduling[END_REF], Cacchiani and Toth [START_REF] Cacchiani | Nominal and robust train timetabling problems[END_REF].

On this section we will review some of the contributions for the non-periodic train timetabling problem, however, relevant references on the periodic timetabling field can be found on: [START_REF] Odijk | A constraint generation algorithm for the construction of periodic railway timetables[END_REF], [START_REF] Kroon | Cyclic railway timetabling: A stochastic optimization approach[END_REF], [START_REF] Liebchen | Performance of algorithms for periodic timetable optimization[END_REF] [1] and [START_REF] Siebert | An experimental comparison of periodic timetabling models[END_REF]. Most of them are based on the Periodic Event Scheduling Problem (PESP), initially proposed by Serafini and Ukovich [START_REF] Serafini | A mathematical model for periodic scheduling problems[END_REF].

One of the first contributions to solve the train scheduling or timetabling problems was made by Szpigel [START_REF] Szpigel | Optimal train scheduling on a single track railway[END_REF], he modelled the single track train scheduling problem as a job shop scheduling problem, and solved it using a branch and bound algorithm.

Higgins et al. [START_REF] Higgins | Optimal scheduling of trains on a single line track[END_REF] propose a mathematical programming model to schedule trains on a single track line, based on the Australian rail network. On this work, priorities are assigned to each train, which then are used to find optimal solutions using a branch and bound procedure.

In a subsequent work, Higgins et al. [START_REF] Higgins | Heuristic techniques for single line train scheduling[END_REF] tackle the single line train scheduling by implementing and comparing the results of different heuristics methods: local search heuristic with an improved neighbourhood structure, genetic algorithms, tabu search and two hybrid algorithms.

Oliveira et al. [START_REF] Oliveira | A job-shop scheduling model for the singletrack railway scheduling problem[END_REF] model the single-track railway scheduling problem as a special case of the job shop scheduling problem by considering the train trips as jobs, which will be scheduled on tracks regarded as resources. Then they show how the problem can be modelled with constraint programming and use Ilog Scheduler to solve it.

Caprara et al. [START_REF] Caprara | Modeling and solving the train timetabling problem[END_REF] focus on a particular case of the TTP: a single, one-way track linking two major stations, with a number of intermediate stations in between. They propose a graph theoretic formulation used to derive an integer linear programming model which is relaxed in a Lagrangian way.

Kwan and Mistry [START_REF] Kwan | A co-evolutionary algorithm for train timetabling[END_REF] use a co-evolutionary algorithm for the automatic generation of train timetables. The objectives are: first, to allocate as many capacity requests as possible, and second: to discover the conflicts that have to be solved by the train operating companies. They use three types of populations which are evolved one after another. The combination of three individuals, i.e., one of each population, result on a timetable. Within each step of the evolution, a timetable is generated and evaluated. Once the termination condition is achieved, the algorithm is stopped and the best timetable is given as result.

Borndörfer and Schlechte [START_REF] Borndörfer | Models for railway track allocation[END_REF] present two types of integer programming formulations: a standard formulation that models block conflicts in terms of packing constraints, and a novel formulation of the extended type that is based on additional configuration variables. Both formulations are then relaxed and solved using MIP solvers.

Fischer et al. [START_REF] Fischer | Towards solving very large scale train timetabling problems by lagrangian relaxation[END_REF] use a lagrangian relaxation of the conflict constraints combined with a cutting plane approach to deal with very large instances of the train timetabling problem. Tormos et al. [START_REF] Tormos | A genetic approach to robust train timetabling[END_REF] use a genetic algorithm to improve timetable robustness, by assigning time supplements in running and headway times over an optimized timetable obtained with the methods described on Ingolotti et al. [START_REF] Ingolotti | New heuristics to solve the csop railway timetabling problem[END_REF].

Wong et al. [START_REF] Wong | Optimizing timetable synchronization for rail mass transit[END_REF] present a mixed integer programming model for generating synchronized timetables, which enable smooth connections while minimizing delays for passengers, the model is then solved using a heuristic technique.

Cacchiani et al. [START_REF] Cacchiani | A column generation approach to train timetabling on a corridor[END_REF] propose a different formulation of the TTP, where each variable corresponds to a full timetable for a train, whereas, in classic formulations, where each variable is associated with a departure and/or arrival time of a train at some specific station. This approach leads to an easier and faster relaxation, thus, better and faster resulting timetables.

3 Train Timetabling Problem: definition and formulation

Problem definition

We define the TTP as: given a railway infrastructure, a list of rolling stock available and a list of train journeys to schedule, produce a timetable in which, all scheduled train journeys respect both capacity and security constraints while optimizing a given criteria.

Three important inputs are thus identified: the rolling stock, the railway infrastructure and the journey requirements. They are detailed below.

The rolling stock: On a real scenario, different types of trains circulate on the railway infrastructure. Each one of them has specific characteristics such as: speed, length, braking distance, etc.

The Infrastructure: The description of the infrastructure can be extremely detailed, however, for train timetabling purposes, only a macro perspective is used, this because higher details implies a more complex model and thus, larger processing time. For instance: several approaches sees stations as black boxes, which means that they do not deal with the stations' capacity, i.e. number of tracks for manoeuvres and platforms, this could lead to infeasible timetables which will have to be fixed later. In our model, we define three main elements to represent the infrastructure:

• Tracks: Tracks connecting two stations, each track definition contains important information as: if the track is single or both ways, the minimum running time for each train type that can circulate on it, the minimum headway time between two train types, among others.

• Knot: A knot defines the locations where trains are allowed to stop, dwell, overtake and perform other manoeuvres. They are typically stations and sidings. Information about the geographical location of the tracks connecting one knot to another is also defined, this allows to determine if a train must perform a turnaround maneuver before pursuing with its itinerary. All knot definitions are composed by a set of Inner Tracks.

• Inner tracks: These are the tracks or platforms inside a knot, they define the capacity of the knot.

The Journey Requirements: A set of train journeys to be scheduled on the timetable. Each journey J consists of a set of trips K j . A trip is defined as the circulation of the train form one knot to another, and it has associated minimal, maximal and ideal departure and arrival times. Some journeys are defined as mandatory, which means that they must be present on the generated timetable, while others will be scheduled only if it is possible. Each journey has a profit value associated, which is used to prioritize the schedule of some train journey over the others.

Definition of data and variables

Data: J: Set of required train journeys. prof j : Profit value of a journey j. K j : Set of trips for a journey j. idealDep/idealArr j,k : Ideal departure and arrival times, trip k of journey j. lbDep/ubDep j,k : Lower and Upper bounds for the departure time, trip k of journey j. lbArr/ubArr j,k : Lower and Upper bounds for arrival time, trip k of journey j. minRT /maxRT j,k,k+1 : Min/Max running time on trip k of journey j. minDT /maxDT j,k,k+1 : Min/Max dwelling time between trips k and k + 1 of journey j. minP T /maxP T j,k,k+1 : Min/Max passing time between trips k and k + 1 of journey j. minT T /maxT T j,k,k+1 : Min/Max turnaround time between trips k and k + 1 of journey j. minHT /maxHT j,k,j ,k : Min/Max headway time between train journeys j and j on trips k and k respectively.

Variables:

Dep: Departure Time for trip k of train journey j.

lbDep j,k ≤ Dep j,k ≤ ubDep j,k (1)
Arr: Arrival Time for trip k of train journey j.

lbArr j,k ≤ Arr j,k ≤ ubArr j,k (2)
sched: Binary variable that is used to determine if a train journey j is scheduled (is part of the timetable) or not.

0 ≤ sched j ≤ 1 (3)

Objective function

We define our objective function as the maximisation of the the global profit of the generated timetable, i.e., the sum of the profit value for each train scheduled (sched j = 1). The profit value of a train is proportionally decreased when the train is scheduled to depart/arrive before or after its desired departure/arrival times. However, such variations are often necessary in order to comply with the constraints defined on the next sub section. In case of any constraint transgression, the associated train is not scheduled (sched j = 0). Equation 4presents a simplified version of the objective function

M aximize J j=1 sched j • prof j - Kj k=1 penaltyArr j,k + penaltyDep j,k (4)

Constraints

As stated before, constraints can be classified into two groups, soft and hard constraints. In our formulation, soft constraints are included into the objective function, i.e. the penalization over the profit generated when a train is not scheduled to arrive or depart at the ideal desired times. Hard constraints must be always respected by all scheduled trains, they are defined as follows.

• Running Time: Minimal and maximal running time for a train journey j on trip k. These values take into account the speed, the acceleration and braking times of the train. Therefore, the running time vary depending if the train has to stop at the next knot or if it will only pass through. Hence, four types of minimal running times are predefined: stop-stop, stop-pass, pass-stop, pass-pass. The choice of which minimal running time is used is determined by the particular itinerary of the train journey.

Finally, these values also include a predefined buffer time to improve the robustness of the timetable.

minRT j,k ≤ Arr j,k -Dep j,k ≤ maxRT j,k (5)
• Dwelling Time: Minimal and maximal dwelling time for a train j that stops at a knot between trips k and k + 1. The dwelling time must be sufficient to allow passengers to disembark and board the trains. Additional time might be needed in case of connections between train journeys.

minDT j,k,k+1 ≤ Dep j,k+1 -Arr j,k ≤ maxDT j,k,k+1 (6)
• Passing Time: The minimal and maximal time that takes a train to pass trough a knot between trips k and k + 1. Normally, the speed in which a train passes through a station is reduced, and some stations are very large, therefore, this time should not be disregarded.

minP T j,k,k+1 ≤ Dep j,k+1 -Arr j,k ≤ maxP T j,k,k+1 (7)
• Turnaround Time: The minimal and maximal time that takes a train to perform a turnaround maneuver at knot between trips k and k + 1. A turnaround occurs when the concerned train arrives in a track that is located on some side of the station and it departs in other track that is located on the same side of the station.

minT T j,k,k+1 ≤ Dep j,k+1 -Arr j,k ≤ maxT T j,k,k+1 (8)
• Headway Time: The minimal and maximal time that must exist between the departure time of two trains j and j leaving from the same knot. This population based technique consist of a set of individuals, each individual represents a possible solution to the problem, or a part of it. In order to determine how good (or bad) a solution is, each individual is evaluated with a fitness function, which assigns fitness values to them. The core of the algorithm is the evolution of the population stage: an iterative process in which, best individuals are selected and combined between them (using variation operators) to form new individuals that will conform a new generation of the population. This process is repeated until certain condition is reached, e.g. number of generations, time limit, etc.

minHT j,k,j ,k ≤ Dep j ,k -Dep j,k ≤ maxHT j,k,j ,k (9)

Data Representation

In our GA implementation, each individual represents a complete timetable. To do so, we use one vector of integer values. The length of the vector is equal to

J j=1 3 • |K j |.
The vector is divided into small segments, each segment corresponding to a train journey, inside one segment, the first element represents the sched j variable, which determines if the train journey is scheduled or not on the timetable. The next element is the departure time of the train journey at its first station (Dep j,1 ). The next element represents the running time of the first trip. The next two elements designs the activity time and the inner track used by the train at the knot between the first and the second trip. The rest of the elements follow the same pattern, Figure 2 gives an example of a segment. Each element of the vector, only allows values between those defined by its respective constraint. This ensures that every timetable generated will automatically respect all running, dwelling, passing and turnaround time constraints.

Algorithm and Operators

Algorithm 1 Genetic Algorithm for solving the TTP 1: Generate initial population P using a greedy algorithm 2: while Termination conditions not met do 3:

for each individual i of P do 4: Generate a timetable using individual i 5:

Evaluate the timetable using the fitness function. Apply variation operators to generate new offspring population P 8:

Combine P and P to generate new population P 9: end while

The main algorithm is detailed in Algorithm 1. The essential components are briefly described next:

• Generate initial population: The initial population of a GA, in the vast majority of cases, have a great impact on the overall performance of the algorithm, and this case is not the exception. Since randomly generated initial populations led to relatively poor performance, we implemented a greedy algorithm that generates an initial population of solutions that maximizes the sum of profit for al scheduled train journeys. Train journeys are randomly ordered and are scheduled one by one if they do not cause any hard constraint violation.

• Generate a timetable using an individual: Having the initial departure time, and the subsequent running and activity times of each trip and knot of the train journey, is possible to calculate the departure and arrival time for each trip, and thus, the complete timetable for all scheduled journeys.

• Evaluate the timetable using the fitness function: The fitness function is an implementation of the objective function described on Equation 4 with additional penalization when hard constraints are violated. It is important to note that even if a train journey appears as not scheduled on the timetable, because it violates at least one hard constraint, it affects negatively the fitness value of the individual.

• Variation Operators: Typical crossover and mutation operators were implemented. Single and multiple point crossover techniques were taken into account.

• Combination of the current and offspring populations: We have opted for an elitist schema for the populations combination, this means that the best individuals form the parents and offspring populations are selected to conform the new population.

Experimentation

Case Study description

For experimentation we used a case study proposed by Erol et al. [START_REF] Erol | Ttplib 2008 -a library for train timetabling problems[END_REF]. The study case consists of 3 train types, and an artificial network with 15 stations, 90 station capacities (tracks inside stations) and 42 tracks, leading to 126 running and 378 headway times. Several requests sets are defined, consisting of a different number of train journeys and time horizons.

Experiment Details

The specifications of the computer used to solve the Case study are: Processor Intel Core i7 @2.9 GHz x4, 3.5 GB of RAM memory and running Ubuntu-64 v12.10 as operating system.

Additionally to our genetic algorithm, for benchmarking the results, we implemented our model using a MIP solver: CPLEX v 12.6. We set the execution time limit for the solver to 1 hour.

Experimental Results

Different requests sets based on the infrastructure described on subsection 5.1 were solved using both our genetic algorithm implementation and the MIP solver. The results are summarized on Table 1.

As many others metaheuristic techniques, GA have a stochastic nature, thus, different executions of the algorithm having the same input may result on different outputs. In order to assess the average performance of the GA, a total of 40 program executions were performed for each request set. We observe that for a small number of requests, our GA was outperformed by the CPLEX solver. Considering 8 train requests, even though the optimal value is attained by the GA, it was slightly slower than the solver. As for 11, 14 and 15 train requests, on average, our GA obtained a near optimal value was but considerably slower than CPLEX. However, as the instance grows in complexity, the advantages of the GA become more evident. On the last 3 request sets, the GA found near optimal solutions on a considerable reduced amount of processing time compared to the MIP solver.

These results shows the potential of genetic algorithms to deal with large, real size instances of the TTP. However, we believe that these results could be further improved. In many cases, the genetic algorithm converged prematurely, which means that only local optimal solutions were found. To deal with this, some adjustments to the mutation rate were made, however this action is not enough to effectively deal with this issue. We shall consider to implement a different selection method that would maintain a diverse population of solutions.

Conclusions

The Train Timetabling Problem (TTP) represents a complex and interesting research subject, research on this area should optimize the usage of railway infrastructure while respecting security issues, boost the profit generated and increase timetable robustness and connectivity.

On this paper, we present a mathematical formulation to tackle the TTP, our model takes into account macro-level representations of both infrastructure and rolling stock elements to optimize the train journey scheduling based on the global profit generated. Then, we present a genetic algorithm implementation of our model that we use to solve the TTP.

The experimental results of our genetic algorithm are very encouraging. Despite the high complexity and NP-hardness nature of the problem, the performance of the GA is very satisfactory. Near-optimal results were achieved within short computation times. Moreover, our model proved to be very flexible, it could be tuned to focus on other particular optimization aspect such as the reduction of total waiting time.

Further extension and improvements to our work include : First, to experiment with different optimization criteria, such as improving connectivity or robustness of the final timetable, or reducing the rolling stock needed or energy consumption. The purpose of this is to develop a compound multi criteria objective function that reflects better the optimization needs of the timetabling process.

Even if our mathematical model can find the optimal timetable for a given instance of the problem, on real size scenarios, the required computing time to achieve optimality would be impractical. Thus, heuristic techniques must be always adopted. In this sense, regardless the good performance of the GA, other approaches should be also explored, therefore, as a second extension of this work, we would like to implement and experiment with other heuristic techniques in order to compare their performance.

Finally, we are also considering to combine our genetic algorithm with other optimization technique: either exact, such as mathematical programming, or another heuristic, e.g. local search, to create a hybrid method. The objective of this is, not only to overcome the limitations of the genetic algorithms, e.g., a tendency to converge towards local optimal solutions, but also to take advantage of the strengths of both methods.

Figure 1 :

 1 Figure 1: The Yearly Rail Service Planning

Figure 2 :

 2 Figure 2: Data representation: Example of a segment

Table 1 :

 1 Results of experimentation

	Req.	Time	Const.	CPLEX	CPLEX	Max.	GA	GA
	Journeys	Horizon	Count	Profit	Time	Eval.	Profit	Time
	8	45	171	3500	0.05 s	1.5 K	3500	0.08 s
	11	77	247	4226.13	0.73 s	11 K	4193.66	2.43 s
	14	72	340	5789.36	0.15 s	10 K	5783.67	3.69 s
	15	22	409	5467.72	1.03 s	16 K	5456.06	5.91 s
	46	86	3524	16949.39	1 m 6 s	10 K 15294.79	28.23 s
	55	79	4721	18009.22 22 m 19 s 55 K 17460.15 3 m 44 s
	106	55	17536	25644	1 h	70 K 23508.35 17 m 13 s

Acknowledgements

The research leading to this paper and Phd.Thesis has received funding from the Institute de Recherche Technologique RAILENIUM. Espace Technopôle, Le Mont Houy, Route départamentale 958, 59300 FAMARS, France.


Mohammed Bachir
email: mohammed.bachir@univ-paris1.fr

J O Ël Blot

65K05 : 49j21

Mohammmed Bachir

Joël Blot
email: blot@univ-paris1.fr

INFINITE DIMENSIONAL MULTIPLIERS AND PONTRYAGIN PRINCIPLES FOR DISCRETE-TIME PROBLEMS

Keywords: Pontryagin principle, infinite horizon, difference equation, difference inequation, Banach spaces, Baire category. M 39A99, 46B99, 54E52

The aim of this paper is to provide improvments to Pontryagin principles in infinite-horizon discrete-time framework when the space of states and of space of controls are infinite-dimensional. We use the method of reduction to finite horizon and several functional-analytic lemmas to realize our aim.

Introduction

We treat of problems of Optimal Control in infinite horizon which are governed by discrete-time controlled dynamical systems in the following forms

x t+1 = f t (x t , u t ), t ∈ N, (1.1)
or x t+1 ≤ f t (x t , u t ), t ∈ N.

(1.2)

X and U are real Banach spaces, the state variable is x t ∈ X t ⊂ X, the control variable is u t ∈ U t ⊂ U and f t : X t × U t → X t+1 is a mapping. For (1.2), X is endowed with a structure of ordered Banach space, and its positive cone, X + := {x ∈ X : x ≥ 0}, is closed, convex and satisfies X + ∩(-X + ) = {0}. An initial state, σ ∈ X 0 is fixed. We define Ead(σ) the set of the processes ((x t ) t∈N , (u t ) t∈N ) which belong to t∈N X t × t∈N U t , which satisfy x 0 = σ and (1.1) for all t ∈ N. We define Iad(σ) the set of the processes ((x t ) t∈N , (u t ) t∈N ) which belong to t∈N X t × t∈N U t , which satisfy x 0 = σ and (1.2) for all t ∈ N.

To define criteria, we consider functions φ t : X t × U t → R for all t ∈ N. From these functions we build the functional J((x t ) t∈N , (u t ) t∈N ) := +∞ t=0 φ t (x t , u t ).

(1.3) Notice that J is not defined for all the processes ((x t ) t∈N , (u t ) t∈N ) ∈ t∈N X t × t∈N U t . And so we define the set of the processes ((x t ) t∈N , (u t ) t∈N ) ∈ Ead(σ) (respectively in Iad(σ)) such that the series +∞ t=0 φ t (x t , u t ) converges into R, and we denote this set by Edom(σ) (respectively Idom(σ)).

We also consider other criteria to define the following problems.

Date: June 28th 2016.

(PE 1 (σ)) : Find ((x t ) t∈N , (û t ) t∈N ) ∈ Edom(σ) such that J((x t ) t∈N , (û t ) t∈N ) ≥ J((x t ) t∈N , (u t ) t∈N ) for all ((x t ) t∈N , (u t ) t∈N ) ∈ Edom(σ). (PE 2 (σ)) : Find ((x t ) t∈N , (û t ) t∈N ) ∈ Ead(σ) such that lim sup T →+∞ T t=0 (φ t (x t , ût )φ t (x t , u t )) ≥ 0 for all ((x t ) t∈N , (u t ) t∈N ) ∈ Ead(σ). (PE 3 (σ)) : Find ((x t ) t∈N , (û t ) t∈N ) ∈ Ead(σ) such that lim inf T →+∞ T t=0 (φ t (x t , ût )φ t (x t , u t )) ≥ 0 for all ((x t ) t∈N , (u t ) t∈N ) ∈ Ead(σ). We also consider similar problems when the system is governed by (1.2) instead of (1.1). (PI 1 (σ)) : Find ((x t ) t∈N , (û t ) t∈N ) ∈ Idom(σ) such that J((x t ) t∈N , (û t ) t∈N ) ≥ J((x t ) t∈N , (u t ) t∈N ) for all ((x t ) t∈N , (u t ) t∈N ) ∈ Idom(σ). (PI 2 (σ)) : Find ((x t ) t∈N , (û t ) t∈N ) ∈ Iad(σ) such that lim sup T →+∞ T t=0 (φ t (x t , ût )φ t (x t , u t )) ≥ 0 for all ((x t ) t∈N , (u t ) t∈N ) ∈ Iad(σ). (PI 3 (σ)) : Find ((x t ) t∈N , (û t ) t∈N ) ∈ Iad(σ) such that lim inf T →+∞ T t=0 (φ t (x t , ût )φ t (x t , u t )) ≥ 0 for all ((x t ) t∈N , (u t ) t∈N ) ∈ Iad(σ). These problems are classical in the theory of infinite-horizon discrete-time Optimal Control, [START_REF] Michel | Some clarifications on the transversality conditions[END_REF], [START_REF] Blot | Infinite-horizon optimal control in the discrete-time framework[END_REF].

A way to establish necessary optimality conditions in the form of Pontryagin principles for the above-mentionned problems is the method of reduction to finite horizon which appears in [START_REF] Blot | Discrete time Pontryagin principle in infinite horizon[END_REF]. In [START_REF] Blot | Infinite-horizon optimal control in the discrete-time framework[END_REF] several variations of this method are given in the setting of the finite dimension, and in [START_REF] Bachir | Infinite Dimensional Infinite-horizon Pontryagin Principles for Discrete-time Problems[END_REF] we find the use of this method in the setting of the infinite dimension. The basic idea of this method is that when ((x t ) t∈N , (û t ) t∈N ) is optimal for one of the previous problems, its restriction to {0, ..., T } is an optimal solution of a finite-horizon optimization problem. Using on these finite-horizon optimization problems a Karush-Kuhn-Tucker theorem or a Multipliers Rule, we obtain multipliers indexed by the finite horizon T . The second step is to build, from these multipliers sequences, multipliers which are suitable for the infinite-horizon problems.

When X and U have an infinite dimension, several difficulties arise, notably due to the closure of the ranges of linear operators, and due to the fact that in infinite dimensional dual Banach space, the origine is contained in the weak-star closure of its unit sphere. Now we briefly describe the contents of the paper. In Section 2, we give the statements of the main results which are Pontryagin principles. In Section 3, we establish results of Functional Analysis which are useful in the sequel. In Section 4, we establish results on Lagrange and Karush-Khun-Tucker multipliers. In Section 5, we give the proofs of the results of section 2. In Section 6, we give some additional applications of results that we use in the proof of the main theorems.

The pontryagin principles.

First we specify some notation.

We denote by Int(A) the topological interior of a set A and by A its closure. When Z is a vector normed space, z ∈ Z and r ∈ (0, +∞), B Z (z, r) denotes the closed ball with z as center and r as ray. The set co(A) (respectively co(A)) stands for the convex hull (respectively the closed convex hull) of a subset A in Z, Aff(A) stands for the affine hull of a subset A in Z. The relative interior of A ⊂ Z, denoted ri(A), is the topological interior of A in the topological subspace Aff(A).

In the paper, the assumptions that we will use in our results belong to the following list of conditions.

(A1) For all t ∈ N, X t is a nonempty open subsets of X, and U t is a nonempty subsets of U . (A2) X is separable. And when ((x t ) t∈N , (û t ) t∈N ) is a given process and when σ ∈ X 0 is given, we consider the following conditions.

(A3) For all t ∈ N, φ t is Fréchet differentiable at (x t , ût ), f t is continuously Fréchet differentiable at (x t , ût ). (A4) for all t ∈ N * , we have 0

∈ Int [Df t (x t , ût )((X × T Ut (û t )) ∩ B X×U )],
where B X×U denotes the closed unit ball of X × U . (A5) For all t ∈ N, the range of D 2 f t (x t , ût ) is closed and its codimension (in X) is finite. (A6) There exists s ∈ N such that A s := D 2 f s (x s , ûs )(T Us (û s )) contains a closed convex subset K with ri(K) = ∅ and such that Aff(K) is of finite codimension in X. Recall that T Ut (û t ) := {α(u tût ) : α ∈ [0, +∞), u t ∈ U t }. We have not assume that the sets U t are open, but when we speak of the differentiability of a mapping f on X t × U t at (x t , ût ), the meaning is that there exists a differentiable function f defined on an open neighborhood of (x t , ût ) which is equal to f on the intersection of this neighborhood and X t × U t . When we speak of tangent cone, we consider the case where U t is convex.

Remark 2.1. Note that the condition (A6) is satisfied and is included in (A5), whenever there exists an s ∈ N such that T Us (û s ) = X, in particular, if ûs belongs to the interior of U s .

The first main result concerns the problems governed by (1.1). Theorem 2.2. Let ((x t ) t∈N , (û t ) t∈N ) be an optimal process of (PE k (σ)) when k ∈ {1, 2, 3}. Under [(A1)-(A6)], we assume moreover that U t is convex for all t ∈ N. Then, there exist λ 0 ∈ R and (p t ) t≥1 ∈ (X * ) N * such that the following conditions hold.

(1) (λ 0 , p t ) = (0, 0), for all t ≥ s.

(

) λ 0 ≥ 0. ( 2
) p t = p t+1 • D 1 f t (x t , ût ) + λ 0 .D 1 φ t (x t , ût ) for all t ∈ N * . ( 3
) λ 0 .D 2 φ t (x t , ût ) + p t+1 • D 2 f t (x t , ût ), u t -ût ≤ 0 for all t ∈ N and for all u t ∈ U t . 4
The second main result concerns the problems governed by (1.2).

Theorem 2.3. Let ((x t ) t∈N , (û t ) t∈N ) be an optimal process of (PI k (σ)) when k ∈ {1, 2, 3}. Under [(A1)-(A6)], we assume moreover that U t is convex for all t ∈ N and that Int(X + ) = ∅. Then, there exist λ 0 ∈ R and (p t ) t≥1 ∈ (X * ) N * such that the following conditions hold.

(1) (λ 0 , p t ) = (0, 0), for all t ≥ s.

(2) λ 0 ≥ 0, and p n ≥ 0 for all n ∈ N * .

(

) p t = p t+1 • D 1 f t (x t , ût ) + λ 0 .D 1 φ t (x t , ût ) for all t ∈ N * . 3
(4) λ 0 .D 2 φ t (x t , ût ) + p t+1 • D 2 f t (x t , ût ), u tût ≤ 0 for all t ∈ N and for all u t ∈ U t .

The proofs of Theorem 2.2 and Theorem 2.3 are based on the following two ideas: the first one is the reduction to finite horizon given by Lemma 4.1 and the second one is to find criteria ensuring that the multipliers are not trivial in the infinite horizon. This criteria will be given by Lemma 3.3.

Preliminary results of Functional Analysis

It is well known from Josefson-Nissenzweig theorem, (see [ [START_REF] Diestel | Sequences and series in Banach spaces[END_REF], Chapter XII]) that in infinite dimensional Banach space Z, there always exists a sequence (p n ) n in the dual space Z * that is weak * null and inf n∈N p n > 0. In this section, we look about reasonable and usable conditions on a sequence of norm one in Z * such that this sequence does not converge to the origin in the w * -topology. This situation has the interest, when we are looking for nontrivial multipliers for optimization problems, and was encountered several times in the literature. See for example [START_REF] Bachir | Infinite Dimensional Infinite-horizon Pontryagin Principles for Discrete-time Problems[END_REF] and [START_REF] Mcasey | A multiplier rule on a metric space[END_REF]. The key is Lemma 3.3 which permits to provide a solution to this problem. We split this section in two subsections. The first is devoted to establish an abstract result (Lemma 3.3) which permits to avoid the Josefson-Nissenzweig phenomenon. The second is devoted to the consequences of this abstract result which are useful for our optimal control problem.

We need the following classical result. Proposition 3.1. Let C be a convex subset of a normed vector space. Let x 0 ∈ Int(C) and x 1 ∈ C. Then, for all α ∈ (0, 1], we have

αx 0 + (1 -α)x 1 ∈ Int(C).
We deduce the following useful proposition. Proposition 3.2. Let (F, . F ) be a normed vector space and C be a closed convex subset of F with non empty interior. Suppose that D ⊂ C is a closed subset of C with no empty interior in (C, . F ) (for the topology induced by C). Then, the interior of D is non empty in (F, . F ).

Proof. On one hand, there exists x 0 such that x 0 ∈ Int(C). On the other hand, since D has no empty interior in (C, . F ), there exists x 1 ∈ D and ǫ 1 > 0 such that (B F (x 1 , ǫ 1 ) ∩ C) ⊂ D. Using Proposition 3.1, we obtain that for all α ∈ (0, 1], we have

αx 0 + (1 -α)x 1 ∈ Int(C). Since αx 0 + (1 -α)x 1 → x 1 when α → 0,
there exist some small α 0 and an integer number

N ∈ N * such that B F (α 0 x 0 +(1-α 0 )x 1 , 1 N ) ⊂ (B F (x 1 , ǫ 1 ) ∩ C) ⊂ D.
Thus D has a non empty interior in F .

3.1.

A key lemma. A map p from a vector space Z into R is said to be subadditive if and only if, for all x, y ∈ Z one has p(x + y) ≤ p(x) + p(y).

A map p is said to be sublinear if it is subadditive and satisfies p(λz) = λp(z) for all λ ≥ 0 and all z ∈ Z.

We give now our principal lemma. This lemma is based on the Baire category theorem.

Lemma 3.3. Let Z be a Banach space. Let K be a non empty closed convex subset of Z and suppose that ri(K) = ∅. Let T be any nonempty set and (p n ) n∈T be a collection of subadditive and lower semicontinuous functions on Z and let (λ n ) n∈T be a collection of nonnegative real number. Suppose that, for all z ∈ K, there exists

C z ∈ R such that, for all n ∈ T , p n (z) ≤ C z λ n .
Then, for all a ∈ K, there exists b a ∈ Aff(K) such that for all bounded subset B of Aff(K) there exists R B ≥ 0 such that

∀n ∈ T , sup h∈B p n (h -a) ≤ R B • (λ n + p n (b a -a)). Proof. For each m ∈ N, we set F m := {z ∈ K : ∀n ∈ T , p n (z) ≤ mλ n }. The sets F m are closed subsets of K. Notice that F m = K ∩ n∈T p -1 n (] -∞, mλ n ]) ,
where, for each n ∈ T , p -1 n (]-∞, mλ n ]) is a closed subset of Z by the semicontinuity of p n . On the other hand, we have K = m∈N F m . The inclusion ⊃ is trivial. We prove the inclusion ⊂. For each z ∈ K, there exists

C z ∈ R such that p n (z) ≤ C z λ n for all n ∈ T . If C z ≤ 0, we have that z ∈ F 0 . If C z > 0, we put m 1 := [C z ] + 1
where [C z ] denotes the integer part of C z , then we have that z ∈ F m1 . We deduce then that for all m ∈ N, the sets F ma are closed subset of Ka and that Ka = m∈N (F ma). Using the Baire category Theorem on the complete metric space Ka, we get an m 0 ∈ N such that F m0a has a nonempty interior in Ka. Since by hypothesis Ka has a nonempty interior in the normed vector subspace F := Aff(K)a of Z, then by using Proposition 3.2 we obtain that F m0a has a nonempty interior in F . So there exists z 0 ∈ F m0a and some integer number

N ∈ N * such that B F (z 0 , 1 N ) := (F ∩ B Z (z 0 , 1 N )) ⊂ F m0 -a.
In other words, for all z ∈ B F (b, 1 N ) ⊂ F m0 where b := a + z 0 ∈ F m0 ⊂ F and all n ∈ T , we have:

p n (z) ≤ m 0 λ n . (3.1)
Now, let B be a nonempty bounded subset of F , there exists an integer number N B ∈ N * such that B ⊂ B F (0, N B ). On the other hand, for all h ∈ B, there exists

z h ∈ B F (b, 1 N ) such that h = N B N • (z h -b) (it sufficies to see that z h := b + h NB .N ∈ B F (b, 1 N )
). So using (3.1) and the subadditivity of p n , we obtain that, for all n ∈ T :

p n (h) = p n (N B N • (z h -b)) ≤ N B N • p n (z h -b) ≤ N B N • (p n (z h ) + p n (-b)) ≤ N B N m 0 λ n + N B N • p n (-b) ≤ N B N m 0 λ n + N B N m 0 • p n ( -b m 0 ) = N B N m 0 λ n + p n ( -b m 0 ) .
Setting R B := N B N m 0 and b 0 := -b m0 ∈ F and by taking the supremum on B, we obtain for all n ∈ T ,

sup h∈B p n (h) ≤ R B • (λ n + p n (b 0 )). (3.2)
Now, let B be any bounded subset of the closure F of F . There exists a bounded subset of F , B, such that B = B. Hence for each z ∈ B, there exists a sequence (h k ) k in B such that h k → z when k → +∞. Thus, using the lower semicontinuity of p n for all n ∈ N and the inequality (3.2), we obtain

p n (z) ≤ lim inf k→+∞ p n (h k ) ≤ sup h∈B p n (h) ≤ R B • (λ n + p n (b 0 )),
and by taking the supremum on B, we obtain, for all n ∈ T ,

sup z∈ B p n (z) ≤ R B • (λ n + p n (b 0 )).
Since F = Aff(K)a, by changing the bounded subsets B of F by Ba, where B is a bounded subset of Aff(K) and by setting b a := b 0 + a ∈ Aff(K), we conclude the proof.

We obtain the following corollary, which may be of interest in some cases.

Corollary 3.4. Let Z be a Banach space and let A be a non empty subset of Z.

Let T be any nonempty set and (p n ) n∈T be a collection of sublinear and lower semicontinuous functions on Z and let (λ n ) n∈T be a collection of nonegative real number. Let C : Z -→ R be a upper semicontinuous function. Suppose that

∀n ∈ T , ∀z ∈ A, p n (z) ≤ C(z)λ n . (3.3)
If ri(co(A)) = ∅, then, for all a ∈ K, there exists b a ∈ Aff(co(A)) such that for all bounded subset B of Aff(co(A)) there exists R B ≥ 0 such that

∀n ∈ T , sup h∈B p n (h -a) ≤ R B • (λ n + p n (b a -a)).
Proof. We can apply Lemma 3.3, with K = co(A). For this, it suffices to establish that ∀n ∈ T , ∀z ∈ co(A), p n (z) ≤ C(z)λ n .

The previous inequality is obtained by using (3.3), the sublinearity and semicontinuity of p n for all n ∈ N, together with the upper semicontinuity of the function C.

3.2.

Preliminaries for multipliers in infinite horizon. As consequence of Lemma 3.3, we obtain the following proposition. The sequences (λ n ) n ∈ (R + ) N and (f n ) n ∈ (Z * ) N in the following result, correspond to the multipliers.

Proposition 3.5. Let Z be a Banach space. Let (f n ) n ∈ (Z * ) N be a sequence of linear continuous functionnals on Z and let

(λ n ) n ∈ (R + ) N such that λ n → 0 when n → +∞. Let K be a non empty closed convex subset of Z such that ri(K) = ∅.
Suppose that (1) for all z ∈ K, there exists a real number C z such that, for all n ∈ N, we have f n (z) ≤ C z λ n .

(

) f n w * → 0 when n → +∞. 2
Let a ∈ K and set X := Aff(K)a. Then, we have,

(i) (f n ) |X X * → 0 when n → +∞.
(ii) If moreover we assume that the codimension of X in Z is finite, then f n Z * → 0 when n → +∞.

Proof. Using Lemma 3.3 with T = N, the linear continuous functions f n and the bounded set B := S X + a of Aff(K) (where, S X denotes the sphere of X), we get a point b 0 depending only on X and a constant R B ≥ 0 such that

(f n ) |X X * = sup h X =1 f n (h) ≤ R B • (λ n + f n (b 0 )).
Since f n w * → 0 (n → +∞) and λ n → 0 (n → +∞) we obtain that (f n ) |X X * → 0 (n → +∞). Suppose now that X is of finite codimension in Z, then there exists a finite-dimensional subspace E of Z, such that Z = X ⊕ E. Thus, there exists L > 0 such that

f n Z * ≤ L (f n ) |E E * + (f n ) |X X * .
Since f n w * → 0 (n → +∞) and since the weak-star topology and the norm topology coincids on E since its dimension is finite, we have that (f n ) |E E * -→ 0 (n → +∞). On the other hand, we proved above that (f n ) |X X * → 0. Thus, f n Z * -→ 0 (n → +∞).

Remark 3.6. Proposition 3.5 shows that under the condition (1), we have that

f n w * → 0, whenever (f n ) |X X * → 0. If moreover, X is of finite codimension in Z, then f n w *
→ 0, whenever f n Z * → 0. Thus, the condition (1) is a criterion ensuring that a sequence of norm one in an infinite dual Banach space, does not converges to 0 in the weak * topology.

To ensure that the multipliers are nontrivial at the limit, the authors in [START_REF] Mcasey | A multiplier rule on a metric space[END_REF] used a lemma from [ [START_REF] Li | Optimal Control Theory for Infinite Dimensional Systems[END_REF], pp. 142, 135], which can be recovered by taking C(z) = 1 for all z ∈ Z in the following corollary. Definition 3.7. A subset Q of a Banach space Z is said to be of finite codimension in Z if there exists a point z 0 in the closed convex hull of Q such that the closed vector space generated by Qz 0 := {qz 0 | q ∈ Q} is of finite codimension in Z and the closed convex hull of Qz 0 has a no empty interior in this vector space.

Corollary 3.8. Let Q ⊂ Z be a subset of finite codimension in Z. Let C : Z -→ R be a upper semicontinuous function. Let δ > 0, (f k ) k ∈ (Z * ) and λ k ≥ 0, λ k → 0 (k → +∞) such that (i) f k ≥ δ, for all k ∈ N and f k w * → f (k → +∞). (ii) For all z ∈ Q, and for all k ∈ N, f k (z) ≤ C(z)λ k . Then, f = 0.
Proof. First, note that from the condition (ii), the linearity and continuity of f k , k ∈ N and the upper semicontinuity of C, we have also that, for all z ∈ co(Q) and for all k ∈ N, f k (z) ≤ C(z)λ k . Suppose by contradiction that f = 0, then using Proposition 3.5 and the fact that Q is of finite codimension in Z, we get that f k Z * → 0 (n → +∞), which contredicts the condition (i).

The following proposition is used in the proof of our main result Theorem 2.2. In Proposition 3.9, the sequence (β (n) ) n≥2 in(R + ) and the list (f

(n) t ) 1≤t≤n+1 ∈ (X * ) n+1
, correspond to the non trivial multipliers at the finite horizon n, for all n ≥ 2. The aim is to find conditions under which, these sequences have subsequences which converge to non trivial multipliers at the infinite horizon. Proposition 3.9. Let Z be a separable Banach space and Z * its topological dual. Let K be a closed convex subset of Z such that ri(K) = ∅ and that Aff(K) is of finite codimension in Z. Let (β (n) ) n≥2 be a sequence of nonegative real number and (f

(n) t ) 1≤t≤n+1 ∈ (Z * ) n+1
, for all n ≥ 2. Let s ∈ N * be a fixed natural number. Suppose that:

(1) for all n ≥ 2, β n + f n s Z * = 1, (2) there exists a t , b t ≥ 0 such that f n t Z ≤ a t β n + b t f n s Z for all n ≥ 2 and for all 1 ≤ t ≤ n + 1, (3) for all z ∈ K, there exist a real number c z such that:

f n s (z) ≤ c z β n for all n ≥ 2.
Then there exist a strictly increasing map

k → n k , from N into N, β ∈ R + and (f t ) t≥1 ∈ (Z * ) N such that: (i) β n k -→ β when k → +∞, (ii) for each t ∈ N, f n k t w * -→ f t when k → +∞, (iii) (β, f s ) = (0, 0).
Proof. From ( 1) and ( 2) we get that, for each t ≥ 1, the sequences (f n t ) 1≤t≤n+1 and (λ n 0 ) n≥2 are bounded. Hence, using the Banach-Alaoglu theorem and the diagonal process of Cantor, we get a strictly increasing map k → n k , from N into N, a nonegative real number β ∈ R + , and a sequence (f t ) t≥1 ∈ (Z * ) N * satisfying (i) and (ii). Suppose by contradiction that (β, f s ) = (0, 0), i.e. β n k -→ 0 and

f n k

Multipliers

In this section, after the recall of the method of reduction to finite horizon, we establish multiplier rules (Lemma 4.5 and Lemma 4.6), in the spirit of Fritz John's theorem, for the problems of finite horizon.

First we recall the method of reduction to finite horizon. When ((x t ) t∈N , (û t ) t∈N ) is an optimal solution of (PE k (σ)), k ∈ {1, 2, 3}, we build the following finitehorizon problem.

(EF(σ))

   Maximize J T (x 1 , ..., x T , u 0 , u..., u T ) := T t=0 φ t (x t , u t ) when ∀t ∈ {0, ..., T }, x t+1 = f t (x t , u t ) x 0 = σ, x T +1 = xT +1 .
Similarly, when ((x t ) t∈N , (û t ) t∈N ) is an optimal solution of (PI k (σ)), k ∈ {1, 2, 3}, we build the following finite-horizon problem

(IF(σ))    Maximize J T (x 1 , ..., x T , u 0 , u..., u T ) := T t=0 φ t (x t , u t ) when ∀t ∈ {0, ..., T }, x t+1 ≤ f t (x t , u t ) x 0 = σ, x T +1 = xT +1 .
The proof of the following result is similar to the proof given in [START_REF] Blot | Discrete time Pontryagin principle in infinite horizon[END_REF].

Lemma 4.1. Let k ∈ {1, 2, 3}. When ((x t ) t∈N , (û t ) t∈N ) is an optimal solution of (PE k (σ)) (respectively (PI k (σ))), for all T ∈ N, T ≥ 2, then the restriction (x 1 , ..., xT , û0 , ..., ûT ) is an optimal solution of (EF(σ) (respectively (IF(σ))).

To work on these problems, we introduce several notations. We write x T := (x 1 , ..., x T ) ∈ T t=1 X t and u T := (u 0 , ..., u T ) ∈ T t=0 U t . For all t ∈ {0, ..., T }, we define the mapping g T t :

T t=1 X t × T t=0 U t → X t+1 by setting g T t (x T , u T ) :=    -x 1 + f 0 (σ, u 0 ) if t = 0 -x t+1 + f t (x t , u t ) if t ∈ {1, ..., T -1} -x T +1 + f T (x T , u T ) if t = T. (4.1) We define g T : T t=1 X t × T t=0 U t → T t=0 X t by setting g t (x T , u T ) := (g T 0 (x T , u T ), ..., g T T (x T , u T )). (4.2)
And so the problem (EF(σ)) is exactly

Maximize J T (x T , u T ) when g T (x T , u T ) = 0 (4.3)
and the problem problem (IF(σ)) is exactly

Maximize J T (x T , u T ) when g T (x T , u T ) ≥ 0 (4.4)
Under (A3), g T is of class C 1 at (x T , ûT ) as a composition of mappings of class C 1 , and the calculation of its differential gives

Dg T (x T , u T )•(δx T , δu T ) = (Dg T 0 (x T , u T )•(δx T , δu T ), ..., Dg T T (x T , u T )•(δx T , δu T
)) and we have

Dg T 0 (x T , u T ) • (δx T , δu T ) = -δx 1 + D 2 f 0 (σ, u 0 )
• δu 0 , and when t ∈ {1, ..., T -1},

Dg T t (x T , u T ) • (δx T , δu T ) = -δx t+1 + D 1 f t (x t , u t ) • δx t + D 2 f t (x t , u t ) • δu t , and
Dg T T (x T , u T ) • (δx T , δu T ) = D 1 f T (x T , u Y ) • δx T + D 2 f T (x T , u T ) • δu T .
Thus in order to study ImDg T (x T , ûT ) we need to treat the equation

Dg T (x T , ûT ) • (δx T , δu T ) = (b 1 , ..., b T +1 ). It is the following system            b 1 = -δx 1 + D 2 f 0 (σ, u 0 ) • δu 0 b 2 = -δx 2 + Df 1 (x 1 , û1 ) • (δx 1 , δu 1 ) .... b T = -δx T + Df T -1 (x T -1 , ûT -1 ) • (δx T -1 , δu T -1 ) b T +1 = Df T (x T , ûT ) • (δx T , δu T ). (4.5) Lemma 4.2. Under (A1) and (A3), the set ImD 1 g T (x T , ûT ) is closed into X T +1 . Proof. Suppose that a sequence ((b n 1 , ..., b n T +1 )) n ∈ (ImD 1 g T (x T , ûT )) N converges to some (b 1 , b 2 , ..., b T +1 ). We prove that (b 1 , b 2 , ..., b T +1 ) ∈ ImD 1 g T (x T , ûT ). In- deed, there exists (δx n 1 , δx n 2 , ..., δx n T ) ∈ X T satisfying b n 1 = -δx n 1 b n 2 = -δx n 2 + Df 1 (x 1 , û1 ) • δx n 1 .... b n T = -δx n T + Df T -1 (x T -1 , ûT -1 ) • δx n T -1 b n T +1 = Df T (x T , ûT ) • δx n T .            (4.6)
Proof. Using Lemma 4.1, we know that (x T , ûT ) = (x 1 , ..., xT , û0 , ..., ûT ) is an optimal solution of (EF(σ)). We want to use Theorem 4.4 where the inequality constraints are absent, and so we don't nee to the first assumption of Theorem 4.4, and among the conclusions we lost that the p t are positive. We have not inequality constraints and so we can delete Γ and conditions on the cone C, and we have H = g T . Using Lemma 4.3, we know that ImDg T (x T , ûT ) is closed in X T +1 . And so there exists λ 0 ∈ [0, +∞) (that is the conclusion (ii)) and Λ 2 ∈ (X * ) T +1 such (λ 0 , Λ 2 ) = (0, 0). Denoting by p (T ) t the coordinates of Λ 2 in X * , we obtain the conclusion (i). From conclusion (ii) of Theorem 4.4, using the partial differentials with respect to u T and with respect to u T , and using the openess of

T t=1 X t , we obatin λ 0 D 1 J T (x T , ûT ) + Λ 2 • Dg T 1 (x T , ûT ) = 0 λ 0 D 2 J T (x T , ûT ) + Λ 2 • Dg T 2 (x T , ûT ), u T -ûT ≤ 0 for all u T ∈ T t=0 U t .
This gives the conclusions (c) and (d). Lemma 4.6. Under (A1), (A3) and (A5), we assume moreover that U t is convex for all t ∈ N and that Int(X + ) = ∅. Then, for all T ∈ N, T ≥ 2, there exist λ T 0 ∈ R and (p T t ) 1≤t≤T +1 ∈ (X * ) T +1 such that the following conditions hold. (a) λ T 0 and (p T t ) 1≤t≤T +1 are not simultaneously equal to zero. (b) λ T 0 ≥ 0, and p t ≥ 0 for all t ∈ {1, ..., T + 1}.

(c) p T t = p T t+1 • D 1 f t (x t , ût ) + λ T 0 D 1 φ t (x t , ût ) for all t ∈ {1, ..., T }. (d) λ T 0 D 2 φ t (x t , ût ) + p T t+1 • D 2 f t (x t , ût
), u tût ≤ 0 for all t ∈ {0, ..., T } and for all u t ∈ U t .

Proof. We procced as in the proof of Lemma 4.5 without deleting the inequality constraints, but deleting the equality constraints.

We need the following lemma for the proof of our main result Theorem 2.2. Lemma 4.7. Under the assumptions of Lemma 4.5 or Lemma 4.6, suppose moreover that (A4) is satisfied. Then, for all T ∈ N, T ≥ 2, there exist λ T 0 ∈ R and (p T t ) 1≤t≤T +1 ∈ (X * ) T +1 such that the following conditions hold.

(1) For all T ≥ 2, for all s ∈ {1, ..., T } and all 1 ≤ t ≤ T + 1, there exists a t , b t ≥ 0 such that p T t ≤ a t λ T 0 + b t p T s .

(2) For all s ∈ {1, ..., T }, (λ T 0 , p T s ) = 0. (3) For all s ∈ {1, ..., T }, for all z ∈ A s := D 2 f s-1 (x s-1 , ûs-1 )(T Us-1 (û s-1 )), there exists C z ∈ R such that: ∀T ≥ 2, p T s (z) ≤ C z λ T 0 . Proof. By adding (c) and (d) of Lemma 4.5 (respectively Lemma 4.6) we obtain for all t ∈ {1, ..., T }, for all h ∈ X and for all

u t ∈ U t p T t+1 , D 1 f t (x t , ût )(h) + D 2 f t (x t , ût ) • (u t -ût ) +λ T 0 .[D 1 φ t (x t , ût )(h) + D 2 φ t (x t , ût ) • (u t -ût )] ≤ p T t (h).
Equivalently, for all t ∈ {1, ..., T } and for all (h, k) ∈ X × T Ut (û t )

p T t+1 , Df t (x t , ût ) • (h, k) ≤ p T t (h) -λ T 0 Dφ t (x t , ût )(h, k). (4.8)
Thus we get for all t ∈ {1, ..., T } and for all (h, k)

∈ X × T Ut (û t ) p T t+1 , Df t (x t , ût ) • (h, k) ≤ p T t h X + λ T 0 Dφ t (x t , ût ) • (h, k) X×U . (4.9)
Since, for all t ∈ N * , 0 ∈ Int (Df t (x t , ût )((X × T Ut (û t )) ∩ B X×U )), there exists a constant r t > 0 such that B X (0, r t ) ⊂ Df t (x t , ût )((X × T Ut (û t )) ∩ B X×U ). Thus, from (4.9) we obtain

p T t+1 ≤ 1 r t ( p T t + λ T 0 Dφ t (x t , ût ) ). ( 4

.10)

On the other hand, using (c) of Lemma 4.5 (respectively Lemma 4.6), we get, for all t ∈ {1, ..., T }, [START_REF] Bachir | Infinite Dimensional Infinite-horizon Pontryagin Principles for Discrete-time Problems[END_REF]. Suppose that there exists s ∈ {1, ..., T } such that (λ T 0 , p T s ) = (0, 0). Using the above inequality we obtain that λ T 0 and (p T t ) 1≤t≤T +1 are simultaneously equal to zero which contredicts the part (a) of Lemma 4.5 (respectively Lemma 4.6). Thus, (λ T 0 , p T s ) = (0, 0) which gives the part (2). Now, using (d) of Lemma 4.5 (respectively Lemma 4.6) for an arbitrary s ∈ {1, ..., T }, for all T ≥ 2, and for all u s ∈ U s , we have

p T t ≤ p T t+1 • D 1 f t (x t , ût ) + λ T 0 D 1 φ t (x t , ût )| . ( 4
p T s • D 2 f s-1 (x s-1 , ), u s-1 -ûs-1 ≤ -λ T 0 D 2 φ s-1 (x s-1 , ûs-1 ), u s-1 -ûs-1 . For all z ∈ A s := D 2 f s-1 (x s-1 , ûs-1 )(T Us-1 (û s-1
)), using the definition of the set T Us-1 (û s-1 ), there exist (u y k s-1 ) k ∈ U N s-1 and (α k ) k ∈ (R + ) N such that y z := lim k→+∞ (α k (u y k s-1ûs-1 )) and z = D 2 f s-1 (x s-1 , ûs-1 ) • y z . So, using the above inequality and doing k → +∞, we get p T s (z) ≤λ T 0 D 2 φ s-1 (x s-1 , ûs-1 ), y z , and so there exists C z := -D 2 φ s-1 (x s-1 , ûs-1 ), y z such that, for all T ≥ 2, we have p T s (z) ≤ C z λ T 0 . This gives the part (3).

The proof of the main results.

This section is devoted to the proofs of the Pontryagin principle for systems governed by a difference equation, and of the Pontryagin principle for systems governed by a difference inequation Proof of Theorem 2.2. Let us prove the existence of the sequences (p t ) t∈N * ∈ (X * ) N * and λ 0 ≥ 0 satisfying the theorem. By Lemma 4.5, for all T ∈ N, T ≥ 2, there exist λ T 0 ∈ R and (p T t ) 1≤t≤T +1 ∈ (X * ) T +1 such that the following conditions hold.

(a) λ T 0 and (p T t ) 1≤t≤T +1 are not simultaneously equal to zero.

(b) λ T 0 ≥ 0. (c) p T t = p T t+1 • D 1 f t (x t , ût ) + λ T 0 D 1 φ t (x t , ût ) for all t ∈ {1, ..., T }. (d) λ T 0 .D 2 φ t (x t , ût ) + p T t+1 • D 2 f t (x t ,
ût ), u tût ≤ 0 for all t ∈ {0, ..., T } and for all u t ∈ U t .

From (A6), there exist s ∈ N such that the set A s := D 2 f s (x s , ûs )(T Us (û s )) contains a closed convex subset K with ri(K) = ∅ and Aff(K) is of finite codimension in X. Since the set of the lists of multipliers of a maximization problem is a cone, using the above consequences of Lemma 4.5, we can normalize the pair (λ T 0 , p T s ) = (0, 0) and so we can assume that λ T 0 + p T s X * = 1. By combining Lemma 4.7 and Proposition 3.9 applied with K, we get a strictly increasing map k → T k , from N into N, and λ 0 ∈ R + and (p t ) t≥1 ∈ (X * ) N such that: (i) λ T k 0 -→ λ 0 ≥ 0 when k → +∞, (ii) for each t ∈ N, p T k t w * -→ p t when k → +∞, (iii) (λ 0 , p s ) = (0, 0). Thus, by doing k → +∞ in (c) and (d) we obtain (3) and (4). From (i) we get [START_REF] Li | Optimal Control Theory for Infinite Dimensional Systems[END_REF]. Now, if there exists t > s such that (λ 0 , p t ) = (0, 0), we proceed recursively using (3) to obtain that (λ 0 , p s ) = (0, 0) which is a contradiction with (iii). Thus, for all t ≥ s, (λ 0 , p t ) = (0, 0) this gives the part (1).

Proof of Theorem 2.3. We proceed as in the proof of Theorem 2.2, replacing the use of Lemma 4.5 by the use of Lemma 4.6.

6. Appendix: Some additional applications.

In this section we establish some additional consequences of the abstract result (Lemma 3.3). We begin by the following extension of [Theorem 2.5.4 [START_REF] Hille | Functional Analysis and Semigroups[END_REF]]. The [Theorem 2.5.4 [START_REF] Hille | Functional Analysis and Semigroups[END_REF]] can be obtained by taking K = Z, a = 0 and B = B Z (0, 1) in Proposition 6.1. Proposition 6.1. Let Z be a Banach space, T be any nonempty set and (p n ) n∈T be a collection of lower semicontinuous and subadditive functions from Z into R. Let K be a closed convex subset of Z such that ri(K) = ∅. Suppose that for each z ∈ K we have sup n∈T p n (z) < +∞. Then, for each a ∈ K and each bounded subset B of Aff(K), we have Proof. The proof is immediat by using Lemma 3.3 with λ n = 1 for all n ∈ T .

The above proposition is in fact an extention to subadditive functions of the classical Banach-Steinauss theorem. Corollary 6.2. (Banach-Steinauss) Let X be a Banach space and Y be a normed vector space. Let T be any nonempty set. Suppose that (T n ) n∈T is a collection of continuous linear operators from X to Y . Suppose that for each x ∈ X one has Proof. The proof follows immediately from Proposition 6.1 applied with: K = X, a = 0, the bounded set S X (the unit sphere of X) and with the collection of the continuous subadditive functions p n (x) := T n (x) Y for all n ∈ T and all x ∈ X.

  k → +∞. Using the condition (3) and Proposition 3.5 we have that f n k s Z * -→ 0 when k → +∞. Since β n k -→ 0 when k → +∞, we have also β n k + f n k s Z * -→ 0 which is a contradiction with the condition (1).

  sup n∈T sup z∈B p n (za) < +∞.

T

  n (x) Y = sup n∈T T n B(X,Y ) < +∞.

  .11) Thus, by combining (4.10) and (4.11) for all T ≥ 2, for all s ∈ {1, ..., T }, and all 1 ≤ t ≤ T + 1, there exist a t , b t ≥ 0 such that

	p T t	≤ a t λ T 0 + b t p T s .
	This gives the part

Since (b n 1 ) n converges to b 1 , we get that (δx n 1 ) n converges to some δx 1 and so (Df 1 (x 1 , û1 ) • δx n 1 ) n converges to Df 1 (x 1 , û1 ) • δx 1 by continuity. Since (b n 2 ) n converges to b 2 , we get that (δx n 2 ) n converges to some δx 2 and so b 2 = -δx 2 + Df 1 (x 1 , û1 ) • δx 1 . We proceed inductively to obtain

The proof of the following result is similar to the proof of Lemma 3.10 in [START_REF] Bachir | Infinite Dimensional Infinite-horizon Pontryagin Principles for Discrete-time Problems[END_REF], replacing Lemma 3.5 in [START_REF] Bachir | Infinite Dimensional Infinite-horizon Pontryagin Principles for Discrete-time Problems[END_REF] by Lemma 4.2.

Lemma 4.3. Under (A1), (A3) and (A5), the range ImDg T (x T , ûT ) is closed in X T +1 .

The following theorem was established in the book of Jahn [START_REF] Jahn | Introduction to the theory of nonlinear optimization[END_REF] (Theorem 5.3 in p.106-111, and Theorem 5.6, p. 118).

Theorem 4.4. Let Ξ, Y and Z three real Banach spaces, and ξ ∈ Ξ. We assume that the following conditions are fulfilled.

(1) Y is ordered by a cone C with a nonempty interior.

(2) Ŝ is a convex subset of Ξ with a nonempty interior.

(3

If ξ is a solution of the following minimization problem Minimize I(ξ) when ξ ∈ S then there exist λ 0 ∈ [0, +∞), Λ 1 ∈ Y * a positive linear functional, Λ 2 ∈ Z * such that the following conditions are satisfied:

Lemma 4.5. Let ((x t ) t∈N , (û t ) t∈N ) be an optimal process of (PE k )(σ)) when k ∈ {1, 2, 3}. Under (A1), (A3) and (A5), we assume moreover that U t is convex for all t ∈ N. Then, for all T ∈ N, T ≥ 2, there exist λ T 0 ∈ R and (p T t ) 1≤t≤T +1 ∈ (X * ) T +1 such that the following conditions hold.

(a) λ T 0 and (p T t ) 1≤t≤T +1 are not simultaneously equal to zero.

), u tût ≤ 0 for all t ∈ {0, ..., T } and for all u t ∈ U t .

We also have the following corollary. Corollary 6.3. Let A be a nonempty set and (Z, . ) be a Banach space. Let ϕ : A × Z -→ R be a map such that:

(1) For all x ∈ A, the map z → ϕ(x, z) is lower semicontinuous and sublinear.

(2) For all z ∈ Z, the map x → ϕ(x, z) is bounded.

Then, there exists a real number C ∈ R such that sup x∈A ϕ(x, z) ≤ C z , for all z ∈ Z.

Proof. We apply Proposition 6.1 with T = A, p x := ϕ(x, .), using ( 1) and ( 2), there exists C ∈ R such that sup x∈A sup z =1 ϕ(x, z) ≤ C. Thus, by the homogeneity of p x , we have ϕ(x, z) ≤ C z , for all x ∈ A and all z ∈ Z.

Finally, we get the following proposition, which gives, a necessary and sufficient condition such that the Dirac masses are continuous functionals. Proposition 6.4. Let X be a nonempty set and (B(X), . ∞ ) be the Banach space of all bounded real-valued functions. Let Y ⊂ B(X) be a subspace and . Y be a norm on Y such that (Y, . Y ) is a Banach space. Let us denote by δ x the Dirac mass or the evaluation at x ∈ X defined by δ x : f → f (x) for all f ∈ B(X). Then, the following assertions are equivalent.

(a)