Chen Wang
email: chen.wang@inria.fr

A QoS-Aware Middleware for Dynamic and Adaptive Service Execution

Service-Oriented Architecture (SOA) provides a flexible solution for building loosely coupled distributed applications. Complex applications can be designed by defining a business process that composes a set of independent software modules called services. In this scenario, each service can be selected and bound dynamically at run-time among a set of candidates that provide the same functionality but differs in quality of service (QoS). However, the QoS values advertised by partner services are not always ensured at run-time. In response to the dynamic execution environment, the execution of a business process has to be adapted onthe-fly in case that a global QoS violation is predicted. In this paper, we introduce a QoS-aware middleware system for dynamic and adaptive service execution. The run-time service selection is modeled as an optimization problem based on user's end-to-end QoS constraints and preferences on the service composition level. In contrast to the centralized execution engine adopted by most of traditional approaches, the execution of a service composition is decentralized in the middleware. Moreover, Program Evaluation and Review Technique (PERT) and Heartbeat Failure Detector (HB) are introduced as effective approaches to predict global QoS violations and draw appropriate adaptation decisions.

Introduction

Service-Oriented Architecture (SOA) is adopted today by many businesses as an effective approach for building software applications that promotes loose coupling between software components. From the viewpoint of SOA, complex applications, often referred as business processes or service compositions, can be built by defining a workflow that composes and coordinates different services available via the network.

In the context of dynamic execution, a workflow is defined by composing a set of abstract activities as place holders. Each activity is bound to a suitable partner service, which is selected at run-time from a set of functional equivalent candidates with different non-functional properties such as quality of service (QoS). Service selection introduces an optimization problem which can be solved either locally or globally. The local approach selects the best candidate for each activity separately. Accordingly, it is more efficient but the end-to-end QoS cannot be ensured. By contrast, the global approach identifies a service composition that can meet the requester's end-to-end QoS requirements. In [START_REF] Ardagna | Global and local qos constraints guarantee in web service selection[END_REF], the authors prove that global service selection is equivalent to a Multiple-choice Multi-dimensional Knapsack Problem (MMKP), which is NP-Hard. As a result, identifying the best service composition often results in a higher time complexity.

During the execution, run-time QoS is determined by the dynamic execution environment so that the expected QoS is not always ensured. In addition, the infrastructure failure can lead a service undeliverable. The adaptive execution reflects the capability to recompose a (part of) workflow on-the-fly in case that the global QoS violation is predicted. The prediction is based on monitoring events such as the detection of a delay on the execution of an activity or the crash of a partner service. The recomposition aims at identifying a new service composition by re-selecting services for the unexecuted activities, by which the requester's end-to-end QoS constraints can still be guaranteed. Otherwise, the primal goal is to minimize the negative effect caused by this QoS violation. For example, if an activity has to be re-executed, the global QoS constraints can hardly satisfied. In this case, the recomposition of services identifies a new composition with shortest execution time while all the other QoS dimensions are still satisfied. This paper introduces a QoS-aware middleware system for dynamic and adaptive service execution. The service selection is modeled as a Mixed Integer Linear Programming (MILP) problem based on the requester's global QoS constraints (such as limited budget and time) and preferences on different QoS attributes. Compare to traditional approaches which implement a centralized execution engine, the execution of a service composition is decentralized in the middleware system, which has advantages on dealing with scalability and fault tolerance. In addition, two approaches are introduced for monitoring run-time QoS: Program Evaluation and Review Technique (PERT) chart is used to predict the violation of global execution time caused by the delay on the execution of an activity; to deal with the infrastructure failures, an overlay is implemented based on Heartbeat Failure Detector (HB) to draw an adaptation decision as early as possible. The adaptation process is formalized as a re-composition of a part of workflow. Based on the problem complexity and the execution state, either a feasible or optimal solution is identified to meet the crucial requirement of limited execution time.

The rest of paper is organized as follows. In Section 2, the middleware architecture is presented and the system model is defined. Section 3 introduces the global service selection approach that can best meet the user's end-to-end requirements. Section 4 discusses distributed execution, run-time monitoring and adaptation. Experimental results are studied in Section 5. In Section 6, some of the main existing approaches for dynamic and adaptive service execution are introduced. Finally, conclusion and future work are addressed in Section 7.

Middleware Architecture

The middleware architecture is shown in Figure 1, all components are organized into three levels. Web Service Representation level resolves the abstract representation of Web services. In the middleware system, all available functionalities are provided by a set of Abstract Services (AS), which can be either atomic or composite. An atomic AS, defined by an Abstract Web Service (AWS) component, does not require the collaborations with other ASs to provide a certain functionality. It is the middleware-level reflection of a specific concrete Web service: on one hand, it advertises functional interfaces and quality levels related to this concrete Web service; on the other hand, it outsources the calculation to this concrete service in response to service invocations. By contrast, a composite AS is represented by an Abstract Business Process (ABP) component which defines an Abstract Workflow (AWF) to achieve the ultimate business goal. Each workflow activity only specifies functional requirement at the designing phase. Suitable service providers, referred as an AS in the middleware system, are selected and bound at run-time. Thus, an ABP plays the roles of both service provider and consumer. Different from AWS, it only interacts with the components defined within the middleware system. Web Service Execution level manages service executions and invocations. ASs advertise their services by defining and publishing offer s to the Registry component. An offer can be regarded as a contract between service requester and provider, which specifies both functional and non-functional characteristics of a service delivery. Registry acts as a directory maintaining the information of all currently available offers. Each request to an ABP is associated with a global QoS constraint specified by the requester (i.e., the total price and execution time). In response to this request, an ABP instantiates and executes its predefined workflow. The Instantiation component is responsible for building a concrete workflow by selecting a suitable AS (can be either an AWS or an ABP) for each activity. The selection is based on all currently available offers in the Registry and the global QoS constraints specified by the requester. Once a concrete workflow is constructed, the Execution component distributes its execution by creating and forwarding a group of coordination messages to all participants.

Run-time Management level monitors and adapts service executions at runtime. Since the expected QoS values are not always guaranteed at run-time due to the dynamic and distributed execution environment, the Monitoring component monitors run-time QoS of each partner service. Once a QoS violation is predicted, it updates the global view of workflow execution state and draws adaptation decision. The Adaptation component then suspends the execution by saving the breakpoints and generates an adaptation model based on the current state of workflow execution. The adaptation is modeled as a re-instantiation process: partner services are re-selected for the unexecuted activities so as to guarantee the global QoS constraints. If a solution is found, the new concrete workflow is forwarded to the Execution component to resume the execution from the breakpoints. The dynamic and adaptive execution of a service composition follows the loop of instantiation, execution, monitoring and adaptation (if necessary). In the following sections, we are going to detail each process.

The middleware system provides a set of Web-based interfaces for service providers to create and manage abstract services. If a service is already implemented, an AWS can be created automatically by providing the WSDL file related to service implementation. On the other side, if a provider defines a service by describing an abstract workflow whereas without specifying implementation detail, he can create an ABP by uploading the workflow description file (such as BPEL file). Furthermore, service providers can manage their ASs through user interface,i.e., it is possible to define quality levels by creating, modifying or canceling his offers in the Registry component. In addition, a set of Webtools are developed for administrators of the middleware system. With the aid of these tools, the administrators can manage and maintain the database of Registry, modify run-time policies for service instantiation and adaptation, view the system logs and so on.

Service Composition Model

An ABP defines an abstract workflow that specifies business logic and execution order. An abstract workflow is a collection of interrelated activities that function in a logical sequence to achieve the ultimate business goal, denoted as awf = {t i |1 ≤ i ≤ N }, where t i represents the i th workflow activity. A concrete workflow is constructed by binding each activity to a service provider. Most models proposed in the literature assume that a provider delivers a service only on one quality level. In this case, a service provider is selected from a service class, defined as a group of service providers that can deliver the same functionality. By introducing the concept of offer, our model is also applicable to the case that a provider delivers a service on more than one quality levels. An offer encapsulates both functional and non-functional aspects of a service delivery as well as the identification information of the related service provider. By this means, the service selection problem is transformed into the selection of appropriate offers: a provider is selected if and only if one of its offers is selected by a service composition. An Offer Set is defined as OS i = {o i,j |1 ≤ j ≤ M i }, where o i,j represents the j th offer that can execute activity t i andM i is the number of offers in OS i . A concrete workflow is constructed by binding each activity t i to an appropriate offer in the related offer set OS i , denoted as cwf

= {t i ← o i,ni |1 ≤ i ≤ n; 1 ≤ n i ≤ M i }.

Fig. 2. Abstract Workflow

The topology of a workflow is represented by a graph where the nodes represent abstract activities and the edges specify the dependencies between these activities. In Figure 2, an abstract workflow awf = {t 1 , t 2 , ... , t 10 } is defined. In order to reflect different workflow patterns1 (i.e. t 2 is followed by a parallel split while t 3 leads to conditional branches), the following two concepts are defined: an Execution Plan (EPL) epl p is a possible execution of workflow which contains all the parallel branches but only one of conditional branches; and an Execution Path (EPA) epa q is a sequential execution of tasks from the first activity to the last one. Let P and Q indicate respectively the number of execution plans and paths in a workflow, npl p and npa q indicate respectively the number of the activities included in the execution plan epl p and execution path epa q . The workflow shown in Figure 2 has two possible EPLs (P=2): epl 1 = {t 1 , t 2 , t 3 , t 4 , t 6 , t 7 , t 8 , t 9 , t 10 } and epl 2 = {t 1 , t 2 , t 3 , t 5 , t 6 , t 7 , t 8 , t 9 , t 10 }, and three EPAs (Q=3): epa 1 = {t 1 , t 2 , t 3 , t 4 , t 6 , t 9 , t 10 }, epa 2 ={t 1 , t 2 , t 3 , t 5 , t 6 , t 9 , t 10 } and epa 3 = {t 1 , t 2 , t 7 , t 8 , t 9 , t 10 }. prob p is the probability to execute the execution plan epl p , we have p=P p=1 prob p = 1.

Quality of Service Model

QoS Attributes The middleware system supports a large number of QoS attributes, as the limit of space, only five of them are discussed in this paper. Each offer o i,j specifies the value for the following QoS attributes.

-Price. The price q pr (o i,j ) is the fee that a service requester has to pay in order to buy the offer o i,j . Generally speaking, it can be any positive float numbers, and it is measured in dollars. -Time. The execution time q t (o i,j ) reflects the expected duration for delivering offer o i,j . It is a positive float number measured in seconds. -Availability. The availability q av (o i,j ) is a real number from 0 to 1 that reflects the probability that the offer o i,j is deliverable. -Security. The security q sec (o i,j ) reflects the ability to provide authentication, authorization, confidentiality and data encryption. It has a set of enumerated values: {HIGH, MEDIUM, LOW}. -Reputation. The reputation q rep (o i,j ) is used to measure the trustworthiness of an offer o i,j . Its value is calculated based on the user's feedback on his experience of purchasing o i,j . Its value is an integer number from 1 to 5.

A QoS attribute can be either numeric or descriptive. The quality of a numeric attribute can be expressed by a number while the descriptive attribute uses an expression to describe the quality levels. Considering the five QoS attributes mentioned above, price, time, availability and reputation are numeric QoS attributes whereas security is a descriptive attribute. Moreover, a numeric QoS attribute can be either positive or negative. For positive attributes, the higher value results in a higher quality, such as availability and reputation; by contrast, take price and execution time for example, the greater value of negative attribute leads a lower quality.

Global QoS As introduced, each execution plan reflects a possible execution of a service composition. Any two individual executions can result in different aggregated QoS values (i.e. total price and execution time), depending on which execution plan is executed. The global QoS (gqos) defines a quality level of a service composition, which generally reflects all execution possibilities. To calculate the global QoS, the first step is to compute the aggregated QoS (aqos) of each execution plan. As shown in Table 1, different aggregation functions are defined for different QoS attributes.

Suppose that the provider advertises a quality level by declaring the global QoS as gqos = (gqos pr , gqos t , gqos av , gqos sec , gqos rep ). The global price and time are determined by the worst execution case: the aggregated price and execution time cannot exceed these limits for all execution plans. Similarly, the global security of a workflow only depends on the offers that implements the lowest security level. By contrast, the availability and reputation is calculated based on the historical information over a long periods. The values of such attributes generally reflects all execution possibilities.

= t i ∈eplp ,t i ←o i,j (qpr(oi,j )) gqospr = max{aqospr(eplp), 1 ≤ p ≤ P } qt aqost(epaq) = t i ∈epaq ,t i ←o i,j (qt(oi,j )) gqost = max{aqost(epaq), 1 ≤ q ≤ Q} qav aqosav(eplp) = t i ∈eplp ,t i ←o i,j (qav(oi,j )) gqosav = P p=1 probp • aqosav(eplp) qsec aqossec(eplp) = min{q sec(o i,j )|ti ∈ eplp, ti ← oi,j } gqossec = min{qsec(oi,j )|ti ← oi,j } qrep aqosrep(eplp) = 1 nplp • t i ∈eplp ,t i ←o i,j (qrep(oi,j )) gqosrep = P p=1 probp • aqosrep(eplp)

Workflow Instantiation

The Instantiation component is defined to construct a concrete workflow cwf by assigning each activity t i of an AWF to an appropriate offer o i,j . Each instantiation request is associated with user's global QoS requirements, such as global QoS constraints gc = (gc pr , gc t , gc av , gc sec , gc rep ) and preferences pref er = (p pr , p t , p av , p sec , p rep ). The service selection is from a global perspective on the composition level ensuring that 1) the global QoS of the cwf can meet the requester's global constraints gc and 2) the user's preferences are maximized. This information provided by the requester varies a lot for different instantiation requests, and sometimes it can be incomplete (i.e. the requester specifies global constraints only on a part of QoS attributes) or inaccuracy (i.e. his preferences are expressed in a qualitative way). WF Analyzer and QoS Analyzer modules are defined to analyze the QoS information and then generate a set of inputs to Model Generator for dynamical creation of an optimization model with respect to various requests. The service selection is modeled as a Mixed Integer Linear Programming (MILP) problem. The solution set is built by inquiring the Registry for the information about all currently available offers. On the other side, The instantiation request can also come from the Adaptation component. In this case, as detailed in Section 4.3, the Adaptation component modifies the MILP model based on the execution state of a service composition. The Optimizer solves the MILP model to select the best set of offers. The selection result is sent to CWS Generator to build a concrete workflow. Finally, the concrete workflow is forwarded to the Execution component for the execution.

Framework of Workflow Instantiation Module

Workflow Analyzer

The Workflow Analyzer module simplifies a workflow by removing circles and transforms it to a Directed Acyclic Graph (DAG). Two approaches are proposed in literature: [START_REF] Zeng | Qos-aware middleware for web services composition[END_REF] introduces an "unfolding" method: all the activities between the beginning and the end of a cycle are cloned K times, where K is the maximum number of times that each cycle is executed according to the past execution logs. In [START_REF] Ardagna | Adaptive service composition in flexible processes[END_REF], loops peeling is introduced as an improvement of unfolding technique: loop iterations are represented as a sequence of branches. Each branch condition evaluates if the loop l has to continue or exit.

The objective of workflow analysis is to generate two sets of vectors expressing the workflow structure. Considering a workflow with N activities, for each EPL epl p (1 ≤ p ≤ P ) , a N -dimensional vector isEpl p = (u p,1 , ..., u p,N ) is created as follows: if activity t i is included in epl p , u p,i is set to 1; otherwise, it is set to 0. For example, after analyzing the workflow defined in Figure 2, the vector isEpl 1 = (1, 1, 1, 1, 0, 1, 1, 1, 1, 1) is generated for epl 1 . Likewise, a set of vectors isEpa q = (v q,1 , ..., v q,N )(1 ≤ q ≤ Q) are created for each EPA epa q .

QoS Analyzer

The optimization models proposed in most of literatures are static. They assume that the requester specifies global constraints and preferences on all QoS dimensions. However, in practical cases, the global QoS requirements provided by clients can be incomplete or inaccurate. QoS Analyzer is defined to deal with such information and generate a set of input for Model Generator. In order to set up a mathematical model, all descriptive QoS attributes need to be quantified first. QoS Analyzer assigns a suitable integers to each enumerated value, based on the semantic. Within the scope of this paper, only security is a descriptive attribute, and its enumerated values are assigned respectively as follows: LOW=0, MEDIUM=1 and HIGH=2. Hereafter, security is regarded as a numeric attribute. Furthermore, the system supports a large number of QoS attributes to meet the different QoS requirements of various clients. But in practice, each client always specifies global constraints on several of them. In this case, a 5-dimensional binary vector Z = (z 1 , ..., z 5 ), is created as follows: z r (1 ≤ r ≤ 5) equals to 1 if the user has specified the global constraint on the r th QoS dimension; otherwise, it is set to 0. Hereafter, to facilitate the mathematical expressions, the QoS attributes are indexed as follows: price=1, time=2, availability=3, security=4 and reputation=5. For example, if a client has limited budget and delivery time and the global QoS constraints are expressed as gc = {$10, 200s}. In this case, Z = (1, 1, 0, 0, 0).

In most of practical cases, it is hard for a client to give a complete preference on all QoS attributes; instead, his interests only focus on several of them. As an example, the client only specifies his preferences on security issue and reputation as pref er = (-, -, -, 2, 3). In this case, QoS Analyzer completes the preference vector by assigning 0 to all the QoS attributes that are not mentioned, and then normalizes the preference vector. In this example, the client's preference is finally expressed as pref er = (0, 0, 0, 0.4, 0.6). However, as discussed in [START_REF] Wang | Incomplete preference-driven web service selection[END_REF], requesters can hardly express preferences in a quantitative way. Instead, he can only tell which attribute is relatively more important for him. In this case, the requester's preferences are expressed by a set of qualitative expressions such as q t > q pr . QoS Analyzer quantizes and completes the preference vector by taking the following steps: 1) set the preferences on all the QoS dimensions that are not mentioned by the client to 0; 2) for each preference expression q L > q R , the preference on q L is set as twice as the one on q R ; 3) If two preferences are not comparable, give them the same weight; 4) finally, all attributes can be expressed using one attribute; 5) calculate the preferences on this attribute by applying k=5 k=1 p k = 1 and 6) the preferences on all attributes can be calculated. For example, if the preferences are expressed as follows: i) price>time; ii) security>time, finally it can be quantified as pref er = {0, 4, 0.2, 0, 0.4, 0}.

Integer Programming Model

Objective Function. As adopted in [START_REF] Zeng | Qos-aware middleware for web services composition[END_REF], [START_REF] Ardagna | Global and local qos constraints guarantee in web service selection[END_REF], [START_REF] Ardagna | Adaptive service composition in flexible processes[END_REF], [START_REF] Mabrouk | Qosaware service composition in dynamic service oriented environments[END_REF], Simple Additive Weighting (SAW) technique is used to set up the objective function in order to determine the best service composition. There are two phases to apply SAW:

-Scaling phase. Different QoS attributes have different value ranges and their values are not comparable. On the other hand, the values of positive attributes have to be maximized while the values of negative attributes have to be minimized. As a result, in order to use an objective function to evaluate the overall QoS performances of a service composition, the negative attributes are scaled according to Formula (1) whereas the positive ones are scaled according to Formula (2). , it is not necessary to generate all possible concrete workflows. For each offer set, the offer with the greatest/smallest value on the k th QoS dimension is selected. The computation complexity is proved as polynomial in [START_REF] Zeng | Qos-aware middleware for web services composition[END_REF].

-Weighting phase. The overall score of a service composition is calculated based on the normalized QoS values and the user's preferences on different attributes. The objective function of MILP model is to maximize this score, given by the Formula (3).

Objective : max

5 k=1 pref er k • nqos k (3)
Variables. A binary variable x i,j is created for each offer o i,j indicating whether it is selected: if o i,j is selected, x i,j is set to 1; otherwise set to 0.

Constraints. First of all, exact one offer in an offer set OS i can be selected:

C 0 : Mi j=1 x i,j = 1; ∀i, 1 ≤ i ≤ N (4)
In the following, constraints C 1 to C 5 are defined to guarantee the global QoS constraints. C 1 enables that the global constraint on price can be fulfilled:

C 1 : N i=1 Mi j=1 isEpl p,i • x i,j • q pr (o i,j ) ≤ gc pr ; ∀p, 1 ≤ p ≤ P (5)
According to Table 1, the global price is determined by the most expensive execution plan. The global constraint gc pr is satisfied when the aggregated price aqos pr of each execution plan is under this limit. Here, the information provided by WF Analyzer (isEpl p,i ) is used to determine whether an activity is included in an execution plan epl p . The global constraint on time is denoted in the similar way by C 2 . According to Table 1, the aggregated execution time is calculated based on execution path.

C 2 : N i=1 Mi j=1 isEpa p,i • x i,j • q t (o i,j ) ≤ gc t ; ∀q, 1 ≤ q ≤ Q (6)
The aggregated availability of each execution plan epl p is calculated as follows:

aqos p av = N i=1 Mi j=1 isEpl p,i • x i,j • q av (o i,j ); ∀p, 1 ≤ p ≤ P (7)
Based on Formulas (4), Formulas (7) can be linearized as follows:

lq p av = N i=1 Mi j=1 isEpl p,i • x i,j • ln(q av ( i,j )); ∀p, 1 ≤ p ≤ P (8)
where lq p av = ln(aqos p av ). According to Table 1, the global constraint on the availability is expressed as:

C 3 : P p=1 e lq p av • prob p ≥ gc av ; (9)
The global security depends on the Web service that implements the lowest security level, so the global constraints on security level is denoted as follows:

C 4 : Mi j=1 x • q sec (o i,j ) ≥ gc sec ; ∀i, 1 ≤ i ≤ N (10)
Finally, the aggregated reputation for each execution plan epl p is calculated according to Formulas [START_REF] Alrifai | Combining global optimization with local selection for efficient qos-aware service composition[END_REF]:

aqos p rep = 1 npl p • N i=1 Mi j=1 isEpl p,i • x i,j • q rep (o i,j ); ∀p, 1 ≤ p ≤ P (11)
And the global constraints on reputation is denoted by C 5 :

C 5 : P p=1 aqos p rep • prob p ≥ gc rep ; (12)
As we argued, most of literature assume that requester specifies global constraints on all QoS attributes. However, the global constraints are usually incomplete in practice. In our middleware system, Model Generator module dynamically generates constraints for the attributes with global constraints. The constraint C i (1 ≤ i ≤ 5) is added to the MILP model if and only if z i equals to 1. Remember that the QoS Analyzer generates a vector Z = (z 1 : z 5 ) indicating whether the user limits global constraint on each QoS attribute.

Workflow Execution, Monitoring and Adaptation

Execution of Workflow

Most of traditional service middlewares/platforms implement a centralized execution engine to conduct and control the executions of business processes. As discussed in [START_REF] Fernández | Decentralized Approach for Execution of Composite Web Services using the Chemical Paradigm[END_REF], centralized execution results in a series of drawbacks in dealing with scalability, fault tolerance and privacy. In our middleware system, the execution of a business process is decentralized. After the instantiation, a concrete workflow is constructed and sent to the Execution component for executing. Each execution request is associated with the invocation parameters as well as a unique ID number, which is provided by the ABP before the instantiation. Based on the concrete workflow, the Execution component generates a set of coordination messages and then forwards them to all partner services. A coordination message describes the workflow execution from a local perspective of each participant, such as its precedent(s), successor(s), the local QoS expectations as well as the execution ID.

The workflow is executed in a collaborative manner: upon receiving the coordination message, each partner service involved in the workflow knows the part it plays in the interactions so that it only interacts with its "neighbors" rather than a specific business process that a single engine executes. After the distribution of the coordination messages, the Execution component packages the execution ID number together with invocation parameters into an invocation message, and then forwards it to the AS that is bound to the first activity of the workflow. For each partner service, once all inputs with the expected execution ID are received, it starts the execution and then encapsulates the result and execution ID into a new invocation message, which is then sent to its successor(s). By this means, the workflow is executed as a dominos falling started from the first activity, and each participant evolved in a service composition executes its part according to the behaviors of other participants, there is no single point of control.

Monitor the Execution of Workflow

During the execution of workflow, run-time QoS of partner services cannot be always ensured due to various aspects, such as the network congestion or the increasing load on servers. Thus, in order to ensure requester's global constraints on each execution, the Monitor component is designed to monitor the run-time QoS of all partner services. If a global QoS violation is predicted, the adaptation decision is made in order to re-select a set of services with better QoS characteristics for the unexecuted activities. Among the five QoS attributes discussed in this paper, we assume that service providers do not change the price and security policies during the execution. The reputation depends on the preferences of requesters and its value calculated based on historical information over a relatively long period, we suppose its value changes slightly during the period of an execution. As a result, we only discuss execution time and availability at run-time.

It is not extensively studied in the related literature on how to monitor the executions of service compositions and draw the appropriate decisions to recompose the rest of workflow. In [START_REF] Zeng | Qos-aware middleware for web services composition[END_REF] [1] [START_REF] Ardagna | Adaptive service composition in flexible processes[END_REF], the authors list a number of events that can trigger the service re-composition. For example, the authors state in [START_REF] Ardagna | Adaptive service composition in flexible processes[END_REF] that the re-composition is triggered if the current value of q i differs from the expected value q i by more than a given threshold ∆ i , i.e., |q i -q i | > ∆ i . But how to evaluate the global QoS q i at run-time is not discussed in [START_REF] Ardagna | Adaptive service composition in flexible processes[END_REF]. In the following, we introduce 2 monitoring techniques: Program Evaluation and Review Technique (PERT) is used to evaluate the global execution time, and Heartbeat Failure Detector (HB) is adopted to estimate the availability of partner services.

PERT Chart. PERT is developed as a well-known approach for planning, monitoring and managing the progress of complex projects [START_REF] Wiest | A Management Guide to PERT/CPM[END_REF]. Based on the concrete workflow to be monitored, the Monitoring component builds up a variation of PERT chart by calculating the following information for each activity:

-The earliest start time T E . This is the earliest time an activity t i can start in case that all its precedents accomplish the task on schedule. T E (t i ) = max{T E (t j )+q t (t j )|t j ∈ precedent(t i )}. For the first activity t 1 , T E (t 1 ) = 0. -The latest start time T L . This is the latest time by which an activity t i can begin without causing the delay of the whole execution of workflow.

T L (t i ) = min{T L (t k ) -q t (t i )|t k ∈ successor(t i )}.
For the last activity t N , T E (t N ) = gqos t -q t (t N ). -The critical path CP . The critical path is identified by the activities that has no slack time, denoted as

CP = {t i |T E (t i ) = T L (t i )}.
-The global slack time S G . The maximum delay that an execution of workflow can produce without causing the violation of global time constraint. S G = gc t -gqos t .

Similar to the distribution of workflow execution, the PERT chart is also distributed so that each partner service has local knowledge of the global execution time. By this means, the execution time is monitored by all partner services in a decentralized manner. The Monitoring component re-calculates the PERT chart when a negative event (such as a delay) is produced. Afterwards, it updates the local view of (a part of) partner services by diffusing a set of update messages.

We assume that the system has a synchronized clock and no clock drift. In this context, each partner service bound to t i read its local time. If the expected invocation message is not received by T L (t i ), it reports the delay to the Monitoring component. And then, it extends T L (t i ) by S G +∆ t . During this period, if no invocation comes yet, it declares the possibility of the global time violation to the Monitoring component. Upon receiving the first alert message, the Monitoring component prepares the adaptation, such as saving the breakpoints and update the global view of the execution state. When the second message arrives, it draws the adaptation decision and forwards all the information related to this execution to the Adaptation component. The margin ∆ t is calculated with respect to gqos t and S G . It defines a reasonable tolerant range to prevent an early decision that may lead an unnecessary adaptation process.

Using the PERT technique, it is easy to decide whether to adapt the rest of workflow when a delay is produced during the execution of an activity. But it cannot efficiently cope with the case that a partner service is crashed. For example, the activity t i starts to execute at T, and the service bound to t i is crashed at T + ∆, where ∆ ≈ 0. In this case, the workflow execution is blocked until an instant that one of its successors, noted as t j , reports global time violation since T L (t j ) is reached. In this case, t i has to be re-executed and the delay is T L (t j )-T E (t i )+S G +∆ t . To cope with this problem by making decision earlier, an overlay is built based on failure detector .

Heartbeat Failure Detector. Failure detector is proposed as a basic building block for fault-tolerant distributed systems in 1990s [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF]. Roughly speaking, it is a sub-system responsible for detecting node failures or crashes in a distributed system. In this paper, we investigate heartbeat failure detector (HB) proposed in [START_REF] Aguilera | Heartbeat: A timeout-free failure detector for quiescent reliable communication[END_REF]. The basic idea of HB is that each component diffuses a HB message "I am alive" periodically to all the other components in the system. On the other hand, a component is suspected as crashed by others if its HB is lost. In order to draw a quick adaptation decision when a partner service becomes unavailable, a HB overlay is built on top of all ASs based on the algorithm defined in Figure 4.

1: Each partner service ps i :

2:

Initialization:

3: T 0 i ← max {0, T E (t i ) -∆ s }; 4: if t i ∈ CP : ∆=∆ CP ; else: ∆ = ∆ N C ; 5:
Task 1 : send a HB message to cs 6:

at time T k i = T 0 i +k • ∆, send the k th HB message m k i to cs; 7:
The service composition cs: if k = expected i :

12:

if ps i ∈ suspected : suspected ← suspected \{ps i } 13:

Task 2.1 : estimate the next freshness point τ k+1 i 14:

T k i ← current time; expected i ← expected i + 1; 15: if k < L: EA k+1 i = (k+1)•∆ + C 0 ; 16: else: EA k+1 i = (k+1)•∆ + 1 L • j=k j=k-L (T j i -∆• i);
17:

τ k+1 i = EA k+1 i + α 0 ; 18: else if k = expected i -1: 19: T k i ←current time; suspected ← suspected \{ps i } 20: Task 3 : up to τ k i , m k i is not received yet 21: if ps i / ∈ suspected : 22:
suspected ← suspected ∪ {ps i }; do Task 2.1 ;

23:

else: predict the crash of ps i and decide adaptation. First of all, each partner service ps i initializes the starting time T 0 i by which it is required to send HB messages. The time interval between 2 consecutive HB messages ∆ is set to ∆ CP if ps i is on the critical path and set to ∆ N C otherwise (line 4). For the service composition cs, when the HB message with the expected sequence number is received from ps i (line 11), if ps i is suspected, it is removed from the suspected list (line 12). And then, it records the receive time and update the expected sequence number. In the following, it calculates the next freshness point based on the estimation of the arrival time of the next HB and a constant safety margin α 0 (line 17). A freshness point τ k i is the firm deadline for the k th HB since cs starts to suspect ps i if the expected HB is not received. The estimation of the arrival time for the next HB is based on the approach proposed in [START_REF] Chen | On the quality of service of failure detectors[END_REF] which considers the L most recent HBs (line 16). A static estimation approach is applied for the first k HBs when k < L (line 15). Task 3 is executed if the expected HB is not received by its freshness point. If ps i is not suspected, it is added into the suspected list. In order to avoid a hurried decision, the adaptation decision is not made once ps i is suspected. Instead, we assume that it was received and estimate the next freshness point by carrying out Task 2.1 (line 22). By τ k+1 i , if the k th HB message is received, ps i is removed from the suspected list (line 19). Finally, an adaptation decision is driven by two consecutive failures on receiving a HB messages (line 23).

As discussed in [START_REF] Chen | On the quality of service of failure detectors[END_REF], the QoS of a failure detector is evaluated from two aspects: the detection time (T D ) measures how fast it can detect a failure and mistake rate (MR) reflects the percentage of fault decisions. In our algorithm, the next freshness point is determined by ∆, α 0 and average delay (line [START_REF] Napoli | A chemical based middleware for workflow instantiation and execution[END_REF][START_REF] Wiest | A Management Guide to PERT/CPM[END_REF]. Considering the average delay is negligible compare to other parameters, the detection time T D depends on both ∆ and α 0 . Once a partner service ps i is crashed, its failure is detected after two freshness points so that T D ≈ 2∆ + 2α. In [START_REF] Bertier | Implementation and performance evaluation of an adaptable failure detector[END_REF], authors evaluates this estimation approach adopted in our algorithm. It is reported that the average mistake rate M R is around 0.1%. In our algorithm, an adaptation decision is made on when 2 consecutive fault suspects are produced. Thus, the M R is negligible in the real system.

Workflow Adaptation

Once Monitoring component predicts global QoS violation with current composition cwf, it forwards all the information related to this execution to the Adaptation component. Such information includes workflow definition, binding information as well as the expected QoS and execution state of each activity. Based on the execution state, the activities of the workflow are divided into 2 parts: A F = {t i |the execution of t i is finished} and A N = {t j |t j / ∈ A F }. The adaptation attempts to identify a new service composition cwf that can still meet the global QoS constraints specified by the requester. cwf is identified by re-selecting and re-binding a set of services with better QoS characteristics for the activities in A N .

Accordingly, the adaptation can be seen as the re-instantiation of a part of workflow. The Adaptation component creates a new MILP model by modifying the former one. The modification is based on the execution state and all currently available offers. Since each activity t i in A F is already executed, the selection variables x i,j (1 ≤ j ≤ M i ) of all offers in the offer set OS i have to be fixed as new constraints. On the other hand, for A N , the offer sets are updated by inquiring the Registry component for all currently available offers. In this way, the selection is only performed for A N . Apart from the new MILP model, Adaptation component also decides an adaptation strategy for run-time re-instantiation process: either a feasible or the optimal solution is identified. The decision is made based on the information of the first instantiation process encapsulated in the cwf, such as the time costs and objective values of both a feasible solution and the optimal one. Such information can be used to predict the up-coming service selection process, i.e., as argued later by the experimental results, a feasible strategy is decided under a severe QoS constraints.

The Instantiation component solves the new MILP model under the specified strategy and finally constructs a new service composition cwf . All information related to both cwf and cwf is then forwarded to Execution component. Before resuming the execution, it compares both cwf and cwf and updates the local perspectives of all partner services. New coordination messages are created for the partner services that are involved in cwf but are not in cwf. If a service provider is not longer selected in cwf , an invalidation message is create to cancel its participation in the execution of a service composition. The changes of binding information result in updating the knowledge of neighbors for some partner services. After the distribution of such updated coordination messages, the execution is resumed from the breakpoints.

Experiment Results

Experiment Set Up. The performance of run-time service selection depends on the execution cases, i.e., the size and complexity of a workflow, the average size of offer sets, the global QoS constraints as well as the optimization strategy. First of all, we investigate the instantiation of simple workflow: two instantiation scenarios are set up based on the workflow defined in Figure 2 with respectively slack and severe global QoS constraints. For each activity t i , a complete offer set OS i is created by randomly generating more than 100 offers. Each offer o i,j is defined by initializing the values of different QoS attributes as follows: the execution time q t is generated randomly assuming a uniform distribution in the interval 10 and 200. The security level q sec is randomly chosen from the enumerated values with the same probability. The availability is determined by creating a Gaussian random number between 0 and 1 with µ=0,98 and σ=0.02. The reputation is generated in the similar way by generating a Gaussian random number r between 0 and 5 with µ=4 and σ=1. As the reputation is integer value, q rep is then set to r . Finally, the price is calculated with respect to the other 4 attributes.

For each scenario, a group of testing cases are generated by varying the size of offer sets (M i ) for each activity from 1 to 100. For each case with M i = N (1 ≤ N ≤ 100), the workflow is instantiated for 5 times. Each instantiation identifies a feasible solution as well as the optimal one based on randomly selected offer sets. The average time cost and objective value of both strategies are calculated for each testing case. The experiment results shown in Figure 5 is grouped by 10 consecutive testing cases: each point represents the average performance of 10 test cases (i.e. the objective value when N =70 is the mean value of the testing cases with N respectively from 61 to 70). Figure 5(a) reflects instantiation scenario with slack global QoS constraints. The time to identify the optimal and a feasible solution is respectively within 150ms and 100ms. In the real system, this difference is negligible. On the other side, the objective value of the optimal solution is about 30% higher than a feasible solution. Figure 5(b) illustrates the experimental results for instantiation requests associated with a severe global QoS constraints. While the number of offers per activity is less then 50, no possible concrete workflow can be identified. As the size of offer sets grows large (with from 90 to 100 offers), the optimization time increases dramatically by nearly 5 times. By contrast, the time cost for a feasible solution increases slowly and always within 500ms. On the other side, the values of objective function for both strategies differ by only 5%. Moreover, another group of experiments are made in the same way based on a more complex workflow which composes more than 50 activities and dozens of execution paths and plans. The first instantiation scenario is based on medium global QoS constraints: the optimization time raises to 1 minute for identifying the optimal solution. But a feasible solution can be always identified within 1 second. The objective values differ by 10%-15%. And then, the experiment is reconducted under severe global constraints which leads the difference of objective values around 5%. In this case, the time complexity of the optimal solution does not change a lot and a feasible solution can also be identified within 5 seconds. Considering the longer execution time for a more complex workflow, a feasible solution can meet the crucial requirement of limited execution time. From the aforementioned experimental results, we have the following conclusion: 1) the optimal service composition can be identified efficiently for the workflow with a rational size (10-15 activities) and complexity (less than 5 splits); 2) as the time complexity is exponential with respect to the complexity of workflow whereas the execution time grows linearly, a feasible solution is more efficient for the complex instantiation scenarios; 3) when the global QoS is severe, the values of objective function for a feasible solution and the optimal one differs only around 5%; In this case, a feasible solution can identified instead of the optimal one for at run-time since it has almost the same quality level but can be identified much faster.

Related Work

Dynamic service composition has attracted great interests in the research community. In [START_REF] Zeng | Qos-aware middleware for web services composition[END_REF], the authors present AgFlow: a middleware platform that enables QoS driven service composition. Two alternative service selection approaches are discussed: local optimization and global planning. The local approach implements a greedy algorithm that selects the best candidate for each activity individually; accordingly the end-to-end QoS is not guaranteed. The global approach selects the services by separately optimizing each execution path. As demonstrated in [START_REF] Ardagna | Global and local qos constraints guarantee in web service selection[END_REF], this global approach cannot always guarantee the global QoS. In [START_REF] Alrifai | Combining global optimization with local selection for efficient qos-aware service composition[END_REF], the authors presented a hybrid approach that combines global optimization with local selection. The idea is to firstly decompose global QoS constraints into a set of local ones by using Mixed Integer Programing (MIP), and then the best candidate is selected locally for each activity independently. When QoS decomposition results in a set of restrictive local constraints, the failure of local selection causes the failure of identifying a service composition, although a solution may actually exist.

In order to select services from the global perspective on service composition level and ensure the end-to-end QoS, the authors in [START_REF] Yu | Service selection algorithms for composing complex services with multiple qos constraints[END_REF] propose two models: combinatorial model and the graph model. The service selection is defined as a Multiple-choice Multiple-dimension Knapsack Problem (MMKP) in the former model and defined as a Multi-Constraint Optimal Path (MCOP) problem in the latter one. But the combinational model is only suitable for linear workflows. In [START_REF] Ardagna | Global and local qos constraints guarantee in web service selection[END_REF], the service selection is modeled as a Mixed Integer Linear Programming (MILP) problem where both local and global QoS constraints can be specified. The fulfillment of global QoS is guaranteed. Their work is later extended in [START_REF] Ardagna | Adaptive service composition in flexible processes[END_REF] by introducing loop peeling and negotiation technique. The experimental results shows that it is effective for large processes even with severe constraints. As argued in [START_REF] Alrifai | Selecting skyline services for qos-based web service composition[END_REF], linear programming method is not suitable for run-time service selection since the time complexity to obtain the optimal solution is exponential. In addition, other approaches proposes heuristic algorithms to efficiently find a near-optimal solution. In [START_REF] Yu | Efficient algorithms for web services selection with end-to-end qos constraints[END_REF], the authors extend both models they proposed in [START_REF] Yu | Service selection algorithms for composing complex services with multiple qos constraints[END_REF] to the general workflow case and introduce a heuristic algorithm for each model to find near-optimal solutions in polynomial time, which is more suitable for real-time service selections. In [START_REF] Mabrouk | Qosaware service composition in dynamic service oriented environments[END_REF], authors present a heuristic algorithm based on clustering techniques, which shows a satisfying efficiency in terms of time cost and optimality.

However, most of aforementioned approaches are based on quantitative criteria to select optimal/near-optimal solutions, such as utilizing an objective function. As discussed in [START_REF] Wang | Incomplete preference-driven web service selection[END_REF], it is difficult for users to express their preferences using quantitative metrics. The authors then introduce CP-nets for conducting qualitative Web service selection. Since qualitative preferences can be incomplete, the selection may result in a set of incomparable candidates. Their work is improved later in [START_REF] Wang | Web service selection with incomplete or inconsistent user preferences[END_REF] by using historical information to complete preferences in order to reduce the size of result set. But this work is limited to local service selection.

In our previous work [START_REF] Napoli | A chemical based middleware for workflow instantiation and execution[END_REF], a middleware architecture is introduced for dynamic service selection and execution: partner services are selected and bound at run-time and the aggregated QoS of a service composition is ensured to meet the requester's end-to-end QoS requirement. This paper improves and completes the previous work by introducing adaptive service execution. The adaptive service execution is not extensively studied in the related literature. In [START_REF] Zeng | Qos-aware middleware for web services composition[END_REF], [START_REF] Ardagna | Adaptive service composition in flexible processes[END_REF], authors list a number of events that can trigger run-time service recomposition. But all these events are described from a local perspective without the consideration of the workflow structures and the execution state. In addition, it is inefficient to deal with the case that partner services can crash permanently during the execution. We promote the aforementioned work by introducing a comprehensive middleware system that integrates service selection, execution, monitoring and adaptation to meet the requirement of dynamic and adaptive service execution. By introducing PERT and HB failure detector as two effective monitoring approaches, the system is able to react to the dynamic execution environment and draw appropriate adaptation decisions.

Conclusion

In this paper, we present a QoS-aware middleware system for dynamic and adaptive service execution. Compare to the work reported in the literature, our system has the following desirable characteristics: 1) The flexible generation of MILP model can deal with incomplete and inaccurate QoS requirements; 2) execution of a service composition is decentralized; 3) PERT and HB failure detector are explored as two efficient monitoring approaches, which can deal with both delay and crash; 4) based on the different execution requests and run-time execution states, a suitable strategy is decided for real-time adaptation. In the future, this work is extended by setting up an adaptive and distributed monitoring overlay. We are studying on a distributed algorithm by integrating both PERT and HB approaches for monitoring decentralized service execution. Moreover, the monitoring overlay is adaptable to different execution requests: based on the different execution scenarios (workflow definitions, QoS requirements etc.) the monitoring of a service execution are provided on various quality levels by dynamically configuring the parameters of the monitoring overlay.

Fig. 1 .

 1 Fig. 1. Middleware Architecture

Fig. 3 .

 3 Fig. 3. Instantiation Module

Negative

  /minimum value of gqos k . To calculate gqos max k /gqos min k

9 : 10 :

 910 suspected ← ∅; ∀ps i : expected i =0; Task 2 : receive the k th HB message m k i from ps i 11:

Fig. 4 .

 4 Fig. 4. The implementation of HB based overlay

Fig. 5 .

 5 Fig. 5. Experiment Results

Table 1 .

 1 Aggregated QoS

	QoS QoS Aggregation Function	Global QoS Calculation
	qpr aqospr(eplp)

As introduced later, any workflow can be simplified and transformed into a structured Directed Acyclic Graph (DAG), thus we do not consider loops here.

The research leading to these results has received funding from the European Communitys Seventh Framework Programme [FP7/2007-2013] under grant agreement 215483 (S-CUBE).


Patrick L Combettes
email: p.l.combettes@math.jussieu.fr

Jean-Christophe Pesquet
email: jean-christophe.pesquet@univ-paris-est.fr

Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators *

Keywords: maximal monotone operator, monotone inclusion, nonsmooth convex optimization, parallel sum, set-valued duality, splitting algorithm Mathematics Subject Classifications (2010) 47H05, 49M29, 49M27, 90C25, 49N15

We propose a primal-dual splitting algorithm for solving monotone inclusions involving a mixture of sums, linear compositions, and parallel sums of set-valued and Lipschitzian operators. An important feature of the algorithm is that the Lipschitzian operators present in the formulation can be processed individually via explicit steps, while the set-valued operators are processed individually via their resolvents. In addition, the algorithm is highly parallel in that most of its steps can be executed simultaneously. This work brings together and notably extends various types of structured monotone inclusion problems and their solution methods. The application to convex minimization problems is given special attention.

Introduction

Duality theory occupies a central place in classical optimization [START_REF] Fenchel | Convex Cones, Sets and Functions[END_REF][START_REF] Gol | shteȋn, Teoriya Dvoistvennosti v Matematicheskom Programmirovanii i ee Prilozheniya (Duality Theory in Mathematical Programming and Its Applications)[END_REF][START_REF] Moreau | Fonctionnelles Convexes, Séminaire Jean Leray sur les Équations aux Dérivées Partielles[END_REF][START_REF] Rockafellar | Duality and stability in extremum problems involving convex functions[END_REF][START_REF] Rockafellar | Conjugate Duality and Optimization[END_REF]. Since the mid 1960s it has expanded in various directions, e.g., variational inequalities [START_REF] Alduncin | Composition duality principles for mixed variational inequalities[END_REF][START_REF] Ekeland | Analyse Convexe et Problèmes Variationnels[END_REF][START_REF] Gabay | Applications of the method of multipliers to variational inequalities[END_REF][START_REF] Goh | Duality in Optimization and Variational Inequalities[END_REF][START_REF] Konnov | The splitting method with a linear search for direct-dual variational inequalities[END_REF][START_REF] Mosco | Dual variational inequalities[END_REF], minimax and saddle point problems [START_REF] Lebedev | Duality theory of concave-convex games[END_REF][START_REF] Mclinden | An extension of Fenchel's duality theorem to saddle functions and dual minimax problems[END_REF][START_REF] Moreau | Théorèmes "inf-sup[END_REF][START_REF] Rockafellar | Minimax theorems and conjugate saddle-functions[END_REF], and, from a more global perspective, monotone inclusions [START_REF] Attouch | A general duality principle for the sum of two operators[END_REF][START_REF] Bauschke | The asymptotic behavior of the composition of two resolvents[END_REF][START_REF] Briceño-Arias | A monotone+skew splitting model for composite monotone inclusions in duality[END_REF][START_REF] Eckstein | Smooth methods of multipliers for complementarity problems[END_REF][START_REF] Mercier | Inéquations Variationnelles de la Mécanique[END_REF][START_REF] Pennanen | Dualization of generalized equations of maximal monotone type[END_REF][START_REF] Robinson | Composition duality and maximal monotonicity[END_REF]. In the present paper, we propose an algorithm for solving the following structured duality framework for monotone inclusions that encompasses the above cited works. In this formulation, we denote by B D the parallel sum of two set-valued operators B and D (see (2.5)). This operation plays a central role in convex analysis and monotone operator theory. In particular, B D can be seen as a regularization of B by D, and is naturally connected to addition through duality since (B + D) -1 = B -1 D -1 . It is also strongly related to the infimal convolution of functions through subdifferentials. We refer the reader to [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF][START_REF] Luque | Convolutions of Maximal Monotone Mappings[END_REF][START_REF] Moudafi | On the stability of the parallel sum of maximal monotone operators[END_REF][START_REF] Passty | The parallel sum of nonlinear monotone operators[END_REF][START_REF] Seeger | Direct and inverse addition in convex analysis and applications[END_REF] and the references therein for background on the parallel sum.

Problem 1.1 Let H be a real Hilbert space, let z ∈ H, let m be a strictly positive integer, let A : H → 2 H be maximally monotone, and let C : H → H be monotone and µ-Lipschitzian for some µ ∈ ]0, +∞[. For every i ∈ {1, . . . , m}, let G i be a real Hilbert space, let r i ∈ G i , let B i : G i → 2 G i be maximally monotone, let D i : G i → 2 G i be monotone and such that D -1 i is ν i -Lipschitzian, for some ν i ∈ ]0, +∞[, and suppose that L i : H → G i is a nonzero bounded linear operator. The problem is to solve the primal inclusion

find x ∈ H such that z ∈ Ax + m i=1 L * i (B i D i )(L i x -r i ) + Cx, (1.1)
together with the dual inclusion

find v 1 ∈ G 1 , . . . , v m ∈ G m such that (∃ x ∈ H) z -m i=1 L * i v i ∈ Ax + Cx (∀i ∈ {1, . . . , m}) v i ∈ (B i D i )(L i x -r i ).
(1.2) Problem 1.1 captures and extends various existing problem formulations. Here are some examples that illustrate its versatility and the breadth of its scope. Then we recover a duality framework investigated in [START_REF] Briceño-Arias | A monotone+skew splitting model for composite monotone inclusions in duality[END_REF][START_REF] Eckstein | Smooth methods of multipliers for complementarity problems[END_REF][START_REF] Pennanen | Dualization of generalized equations of maximal monotone type[END_REF][START_REF] Robinson | Composition duality and maximal monotonicity[END_REF], namely (we drop the subscript '1' for brevity),

find (x, v) ∈ H ⊕ G such that z ∈ Ax + L * B(Lx -r) -r ∈ -L A -1 (z -L * v) + B -1 v. (1.4)
Example 1.3 In Example 1.2, let G = H, r = z = 0, and L = Id . Then we obtain the duality setting of [START_REF] Attouch | A general duality principle for the sum of two operators[END_REF][START_REF] Mercier | Inéquations Variationnelles de la Mécanique[END_REF], i.e., find (x, u) ∈ H ⊕ H such that 0 ∈ Ax + Bx 0 ∈ -A -1 (-u) + B -1 u.

(1.5)

The special case of variational inequalities was first treated in [START_REF] Mosco | Dual variational inequalities[END_REF].

Example 1.4 In Example 1.2, let A and B be the subdifferentials of lower semicontinuous convex functions f : H → ]-∞, +∞] and g : G → ]-∞, +∞], respectively. Then, under suitable constraint qualification, we obtain the classical Fenchel-Rockafellar duality framework [START_REF] Rockafellar | Duality and stability in extremum problems involving convex functions[END_REF], i.e.,

     minimize x∈H f (x) + g(Lx -r) -x | z minimize v∈G f * (z -L * v) + g * (v) + v | r . (1.6) Example 1.5 In Problem 1.1, set C : x → 0, z = 0, and (∀i ∈ {1, . . . , m}) G i = H, r i = 0, L i = Id , and
D i = ρ -1 i Id , where ρ i ∈ ]0, +∞[. Then it follows from [8, Proposition 23.6(ii)] that, for every i ∈ {1, . . . , m}, B i D i = (Id -J ρ i B i )/ρ i = ρ i B i is the Yosida approximation of index ρ i of B i . Thus, (1.1) reduces to find x ∈ H such that 0 ∈ Ax + m i=1 ρ i B i x.
(1.7)

This primal problem is investigated in [START_REF] Combettes | Solving monotone inclusions via compositions of nonexpansive averaged operators[END_REF]Section 6.3]. In the case when m = 1, we obtain the primal-dual problem (we drop the subscript '1' for brevity)

find (x, u) ∈ H ⊕ H such that 0 ∈ Ax + ρ Bx 0 ∈ -A -1 (-u) + B -1 u + ρu (1.8)
investigated in [START_REF] Bauschke | The asymptotic behavior of the composition of two resolvents[END_REF].

f (x) + (g ℓ)(Lx) + h(x), (1.9)
which can be rewritten as

minimize x∈H, y∈G f (x) + h(x) + g(y) + ℓ(Lx -y).
(1.10)

In the special case when h = 0, G = H, L = Id , and ℓ is a quadratic coupling function, such formulations have been investigated in [START_REF] Acker | Convergence d'un schéma de minimisation alternée[END_REF][START_REF] Attouch | A new class of alternating proximal minimization algorithms with costs-to-move[END_REF][START_REF] Aujol | Dual norms and image decomposition models[END_REF][START_REF] Chambolle | Image recovery via total variation minimization and related problems[END_REF][START_REF] Combettes | Signal recovery by proximal forward-backward splitting[END_REF].

Example 1.7 In Problem 1.1, set m = 1, G 1 = H, L 1 = Id , B 1 = D -1 1 :
x → {0}, and z = r 1 = 0. Then (1.1) yields the inclusion 0 ∈ Ax + Cx studied in [START_REF] Tseng | A modified forward-backward splitting method for maximal monotone mappings[END_REF], where an algorithm using explicit steps for C was proposed.

Example 1.8 In Problem 1.1, set A : x → {0} and C = Id . Furthermore, for every i ∈ {1, . . . , m}, let B i be the subdifferential of a lower semicontinuous convex function g i : G i → ]-∞, +∞] and let D -1 i : y → {0}. Then, under suitable constraint qualification, we obtain the primal-dual pair considered in [START_REF] Combettes | Proximity for sums of composite functions[END_REF], namely

minimize x∈H m i=1 g i (L i x -r i ) + 1 2 x -z 2 (1.11)
and minimize

v 1 ∈G 1 ,..., vm∈Gm 1 2 z - m i=1 L * i v i 2 + m i=1 g * i (v i ) + v i | r i .
(1.12)

Example 1.9 The special case of Problem 1.1 in which

A : x → {0}, C : x → 0, and (∀i ∈ {1, . . . , m}) D i : y → G i , if y = 0; ∅, if y = 0 (1.13)
yields the primal-dual pair

find x ∈ H such that z ∈ m i=1 L * i B i (L i x -r i ) (1.14) and find v 1 ∈ G 1 , . . . , v m ∈ G m such that m i=1 L * i v i = z (∃ x ∈ H)(∀i ∈ {1, . . . , m}) v i ∈ B i (L i x -r i ).
(

This framework is considered in [START_REF] Briceño-Arias | A monotone+skew splitting model for composite monotone inclusions in duality[END_REF]Theorem 3.8].

Conceptually, the primal problem (1.1) could be recast in the form of (1.14), namely

find x ∈ H such that z ∈ m i=0 L * i E i (L i x -r i ) , (1.16)
where

G 0 = H, E 0 = A + C, L 0 = Id , r 0 = 0, and (∀i ∈ {1, . . . , m}) E i = B i D i . (1.17)
In turn, one could contemplate the possibility of using the primal-dual algorithm proposed in [START_REF] Briceño-Arias | A monotone+skew splitting model for composite monotone inclusions in duality[END_REF]Theorem 3.8] to solve Problem 1.1. However, this algorithm requires the computation of the resolvents of the operators A + C and (B -1 i + D -1 i ) 1≤i≤m , which are usually intractable. Thus, for numerical purposes, Problem 1.1 cannot be reduced to Example 1.9. Let us stress that, even in the instance of the simple inclusion 0 ∈ Ax + Cx, it is precisely the objective of the forward-backward splitting algorithm and its variants [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF][START_REF] Combettes | Signal recovery by proximal forward-backward splitting[END_REF][START_REF] Mercier | Topics in Finite Element Solution of Elliptic Problems[END_REF][START_REF] Tseng | Applications of a splitting algorithm to decomposition in convex programming and variational inequalities[END_REF][START_REF] Tseng | A modified forward-backward splitting method for maximal monotone mappings[END_REF] to circumvent the computation of the resolvent of A + C, as would impose a naive application of the proximal point algorithm [START_REF] Rockafellar | Monotone operators and the proximal point algorithm[END_REF].

The goal of this paper is to propose a fully split algorithm for solving Problem 1.1 that employs the operators A, (L i ) 1≤i≤m , (B i ) 1≤i≤m , (D i ) 1≤i≤m , and C separately. An important feature of the algorithm is to activate the single-valued operators (L i ) 1≤i≤m , (D -1 i ) 1≤i≤m , and C through explicit steps. In addition, it exhibits a highly parallel structure which allows for the simultaneous activation of the operators involved. This new splitting method goes significantly beyond the state-of-the-art, which is limited to specific subclasses of Problem 1.1.

In Section 2, we briefly set our notation. The new splitting method is proposed in Section 3, where we also prove its convergence. The special case of minimization problems is discussed in Section 4.

Notation and background

Our notation is standard. We refer the reader to [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF][START_REF] Zȃlinescu | Convex Analysis in General Vector Spaces[END_REF] for background on convex analysis and monotone operator theory. Hereafter, K is a real Hilbert space.

We denote the scalar product of a Hilbert space by • | • and the associated norm by • . The symbols ⇀ and → denote respectively weak and strong convergence. Moreover, G 1 ⊕ • • • ⊕ G m is the Hilbert direct sum of the Hilbert spaces (G i ) 1≤i≤m in Problem 1.1, i.e., their product space equipped with the norm (y i ) 1≤i≤m → m i=1 y i 2 . For every i ∈ {1, . . . , m}, let T i be a mapping from G i to some set R. Then

m i=1 T i : m i=1 G i → R : (y i ) 1≤i≤m → m i=1 T i y i .
(2.1)

Let M : K → 2 K be a set-valued operator. We denote by ran M = u ∈ K (∃ x ∈ K) u ∈ M x the range of M , by dom M = x ∈ K M x = ∅ its domain, by zer M = x ∈ K 0 ∈ M x its set of zeros, by gra M = (x, u) ∈ K × K u ∈ M x its graph, and by M -1 its inverse, i.e., the set-valued operator with graph (u, x)

∈ K × K u ∈ M x . The resolvent of M is J M = (Id +M ) -1 , (2.2)
where Id denotes the identity operator on K. Moreover, M is monotone if

(∀(x, u) ∈ gra M )(∀(y, v) ∈ gra M ) x -y | u -v ≥ 0, (2.3)
and maximally so if there exists no monotone operator M : K → 2 K such that gra M ⊂ gra M = gra M . We say that M is uniformly monotone at x ∈ dom M if there exists an increasing function φ : [0, +∞[ → [0, +∞] that vanishes only at 0 such that

(∀u ∈ M x)(∀(y, v) ∈ gra M ) x -y | u -v ≥ φ( x -y ).
(2.4)

The parallel sum of two set-valued operators M 1 and M 2 from K to 2 K is

M 1 M 2 = (M -1 1 + M -1 2 ) -1 . (2.5)
We denote by Γ 0 (K) the class of lower semicontinuous convex functions ϕ

: K → ]-∞, +∞] such that dom ϕ = x ∈ K ϕ(x) < +∞ = ∅. Now let ϕ ∈ Γ 0 (K). The conjugate of ϕ is the function ϕ * ∈ Γ 0 (K) defined by ϕ * : u → sup x∈K ( x | u -ϕ(x))
, and the subdifferential of ϕ is the maximally monotone operator

∂ϕ : K → 2 K : x → u ∈ K (∀y ∈ K) y -x | u + ϕ(x) ≤ ϕ(y) (2.6)
with inverse given by (∂ϕ) -1 = ∂ϕ * .

(2.7)

Moreover, for every x ∈ K, ϕ + x -• 2 /2 possesses a unique minimizer, which is denoted by prox ϕ x.

We have prox ϕ = J ∂ϕ .

(2.8)

We say that ϕ is ν-strongly convex for some ν ∈ ]0, +∞[ if ϕ -ν • 2 /2 is convex, and that ϕ is uniformly convex at x ∈ dom ϕ if there exists an increasing function φ : [0, +∞[ → [0, +∞] that vanishes only at 0 such that

(∀y ∈ dom ϕ)(∀α ∈ ]0, 1[) ϕ(αx + (1 -α)y) + α(1 -α)φ( x -y ) ≤ αϕ(x) + (1 -α)ϕ(y). (2.9)
The infimal convolution of two functions ϕ 1 and ϕ 2 from K to ]-∞, +∞] is

ϕ 1 ϕ 2 : K → [-∞, +∞] : x → inf y∈K ϕ 1 (y) + ϕ 2 (x -y) .
(2.10)

Finally, let S be a convex subset of K. The strong relative interior of S, i.e., the set of points x ∈ S such that the cone generated by -x + S is a closed vector subspace of K, is denoted by sri S, and the relative interior of S, i.e., the set of points x ∈ S such that the cone generated by -x + S is a vector subspace of K, is denoted by ri S.

Main result

Our main result is the following theorem, which presents our new splitting algorithm and describes its asymptotic behavior.

Theorem 3.1 In Problem 1.1, suppose that z ∈ ran A + m i=1 L * i (B i D i )(L i • -r i ) + C . (3.1) Let (a 1,n ) n∈N , (b 1,n ) n∈N ,
β = max{µ, ν 1 , . . . , ν m } + m i=1 L i 2 , (3.2
)

let x 0 ∈ H, let (v 1,0 , . . . , v m,0 ) ∈ G 1 ⊕ • • • ⊕ G m , let ε ∈ ]0, 1/(β + 1)[, let (γ n ) n∈N be a sequence in [ε, (1 -ε)/β],
and set

(∀n ∈ N)                  y 1,n = x n -γ n Cx n + m i=1 L * i v i,n + a 1,n p 1,n = J γnA (y 1,n + γ n z) + b 1,n For i = 1, . . . , m       y 2,i,n = v i,n + γ n L i x n -D -1 i v i,n + a 2,i,n p 2,i,n = J γnB -1 i (y 2,i,n -γ n r i ) + b 2,i,n q 2,i,n = p 2,i,n + γ n L i p 1,n -D -1 i p 2,i,n + c 2,i,n v i,n+1 = v i,n -y 2,i,n + q 2,i,n . q 1,n = p 1,n -γ n Cp 1,n + m i=1 L * i p 2,i,n + c 1,n x n+1 = x n -y 1,n + q 1,n . (3.3)
Then the following hold.

(i) n∈N x n -p 1,n 2 < +∞ and (∀i ∈ {1, . . . , m}) n∈N v i,n -p 2,i,n 2 < +∞.
(ii) There exist a solution x to (1.1) and a solution (v 1 , . . . , v m ) to (1.2) such that the following hold.

(a) z -m j=1 L * j v j ∈ Ax + Cx and (∀i ∈ {1, . . . , m}) L i x -r i ∈ B -1 i v i + D -1 i v i . (b) (∀i ∈ {1, . . . , m}) -r i ∈ -L i (A -1 C -1 ) z -m j=1 L * j v j + B -1 i v i + D -1 i v i . (c) x n ⇀ x and p 1,n ⇀ x. (d) (∀i ∈ {1, . . . , m}) v i,n ⇀ v i and p 2,i,n ⇀ v i .
(e) Suppose that A or C is uniformly monotone at x. Then x n → x and p 1,n → x.

(f) Suppose that, for some i ∈ {1, . . . , m}, B -1

i or D -1 i is uniformly monotone at v i . Then v i,n → v i and p 2,i,n → v i . Proof. Let us first rewrite (3.3) as (∀n ∈ N)                          y 1,n = x n -γ n Cx n + m i=1 L * i v i,n + a 1,n For i = 1, . . . , m y 2,i,n = v i,n + γ n L i x n -D -1 i v i,n + a 2,i,n p 1,n = J γnA (y 1,n + γ n z) + b 1,n For i = 1, . . . , m p 2,i,n = J γnB -1 i (y 2,i,n -γ n r i ) + b 2,i,n q 1,n = p 1,n -γ n Cp 1,n + m i=1 L * i p 2,i,n + c 1,n For i = 1, . . . , m q 2,i,n = p 2,i,n + γ n L i p 1,n -D -1 i p 2,i,n + c 2,i,n x n+1 = x n -y 1,n + q 1,n For i = 1, . . . , m v i,n+1 = v i,n -y 2,i,n + q 2,i,n . (3.4)
Next, let us introduce the Hilbert space

K = H ⊕ G 1 ⊕ • • • ⊕ G m , (3.5)
and the operators

M : K → 2 K (x, v 1 , . . . , v m ) → (-z + Ax) × (r 1 + B -1 1 v 1 ) × • • • × (r m + B -1 m v m ) (3.6)
and

Q : K → K (x, v 1 , . . . , v m ) → Cx + L * 1 v 1 + • • • + L * m v m , -L 1 x + D -1 1 v 1 , . . . , -L m x + D -1 m v m . ( 3
(∀γ ∈ ]0, +∞[)(∀(x, v 1 , . . . , v m ) ∈ K) J γM (x, v 1 , . . . , v m ) = J γA (x + γz), J γB -1 1 (v 1 -γr 1 ), . . . , J γB -1 m (v m -γr m ) . (3.8)
Let us now examine the properties of Q. To this end, let (x, v 1 , . . . , v m ) and (y, w 1 , . . . , w m ) be two points in K. Using the monotonicity of the operators C and (D -1 i ) 1≤i≤m , we derive from (3.7) that

(x, v 1 , . . . , v m ) -(y, w 1 , . . . , w m ) | Q(x, v 1 , . . . , v m ) -Q(y, w 1 , . . . , w m ) = (x -y, v 1 -w 1 , . . . , v m -w m ) Cx -Cy + L * 1 (v 1 -w 1 ) + • • • + L * m (v m -w m ), -L 1 (x -y) + D -1 1 v 1 -D -1 1 w 1 , . . . , -L m (x -y) + D -1 m v m -D -1 m w m = x -y | Cx -Cy + m i=1 v i -w i | D -1 i v i -D -1 i w i + m i=1 x -y | L * i (v i -w i ) -v i -w i | L i (x -y) = x -y | Cx -Cy + m i=1 v i -w i | D -1 i v i -D -1 i w i ≥ 0. (3.9)
Hence, Q is monotone. Using the triangle inequality, the Lipschitzianity assumptions, the Cauchy-Schwarz inequality, and (3.2), we obtain

Q(x, v 1 , . . . , v m ) -Q(y, w 1 , . . . , w m ) = Cx -Cy, D -1 1 v 1 -D -1 1 w 1 , . . . , D -1 m v m -D -1 m w m + m i=1 L * i (v i -w i ), -L 1 (x -y), . . . , -L m (x -y) ≤ Cx -Cy, D -1 1 v 1 -D -1 1 w 1 , . . . , D -1 m v m -D -1 m w m + m i=1 L * i (v i -w i ), -L 1 (x -y), . . . , -L m (x -y) = Cx -Cy 2 + m i=1 D -1 i v i -D -1 i w i 2 + m i=1 L * i (v i -w i ) 2 + m i=1 L i (x -y) 2 ≤ µ 2 x -y 2 + m i=1 ν 2 i v i -w i 2 + m i=1 L i v i -w i 2 + m i=1 L i 2 x -y 2 ≤ max{µ, ν 1 , . . . , ν m } x -y 2 + m i=1 v i -w i 2 + m i=1 L i 2 m i=1 v i -w i 2 + m i=1 L i 2 x -y 2 = β (x, v 1 , . . . , v m ) -(y, w 1 , . . . , w m ) . (3.10)
To sum up, we have shown that M is maximally monotone and Q is monotone and β-Lipschitzian.

(3.11)

Next, let us observe that

(3.1) ⇔ (∃ x ∈ H) z ∈ Ax + m i=1 L * i (B i D i )(L i x -r i ) + Cx ⇔ (∃ (x, v 1 , . . . , v m ) ∈ K)            z ∈ Ax + m i=1 L * i v i + Cx v 1 ∈ (B 1 D 1 )(L 1 x -r 1 )
. . .

v m ∈ (B m D m )(L m x -r m ) ⇔ (∃ (x, v 1 , . . . , v m ) ∈ K)            0 ∈ -z + Ax + m i=1 L * i v i + Cx 0 ∈ r 1 + B -1 1 v 1 + D -1 1 v 1 -L 1 x . . . 0 ∈ r m + B -1 m v m + D -1 m v m -L m x ⇔ (∃ (x, v 1 , . . . , v m ) ∈ K) (0, . . . , 0) ∈ (-z + Ax) × (r 1 + B -1 1 v 1 ) × • • • × (r m + B -1 m v m ) + (L * 1 v 1 + • • • + L * m v m + Cx, D -1 1 v 1 -L 1 x, . . . , D -1 m v m -L m x) ⇔ (∃ (x, v 1 , . . . , v m ) ∈ K) (0, . . . , 0) ∈ (M + Q)(x, v 1 , . . . , v m ).
(3.12)

In other words, zer

(M + Q) = ∅. (3.13)
Now, let us set q n = (q 1,n , q 2,1,n , . . . , q 2,m,n ) and (ii): It follows from [10, Theorem 2.5(ii)] that there exists x ∈ zer(M + Q) such that

(∀n ∈ N)            x n = (x n , v
     a n = (a 1,n , a 2
(∀n ∈ N)       y n = x n -γ n (Qx n + a n ) p n = J γnM y n + b n q n = p n -γ n (Qp n + c n ) x n+1 = x n -y n + q n . ( 3
x n ⇀ x and p n ⇀ x.

(3.17)

Let us set

x = (x, v 1 , . . . , v m ). (3.18)
In view of (3.6) and (3.7),

x ∈ zer(M + Q) ⇔            0 ∈ -z + Ax + m i=1 L * i v i + Cx 0 ∈ r 1 + B -1 1 v 1 + D -1 1 v 1 -L 1 x . . . 0 ∈ r m + B -1 m v m + D -1 m v m -L m x ⇔            z -m j=1 L * j v j ∈ Ax + Cx L 1 x -r 1 ∈ (B -1 1 + D -1 1 )v 1 . . . L m x -r m ∈ (B -1 m + D -1 m )v m (3.19) ⇔            z -m j=1 L * j v j ∈ Ax + Cx v 1 ∈ (B 1 D 1 )(L 1 x -r 1 )
. . .

v m ∈ (B m D m )(L m x -r m ) (3.20) ⇒            z -m j=1 L * j v j ∈ Ax + Cx L * 1 v 1 ∈ L * 1 (B 1 D 1 )(L 1 x -r 1 ) . . . L * m v m ∈ L * m (B m D m )(L m x -r m ) ⇒ z ∈ Ax + m i=1 L * i (B i D i )(L i x -r i ) + Cx ⇔ x
∈ (A + C) -1 z - m j=1 L * j v j and (∀i ∈ {1, . . . , m}) L i x -r i ∈ (B -1 i + D -1 i )v i . (3.23)
Hence, (∀i ∈ {1, . . . , m})

-L i x ∈ -L i (A -1 C -1 ) z -m j=1 L * j v j L i x -r i ∈ (B -1 i + D -1 i )v i . (3.24)
Thus, (ii)(e): Let us set

(∀i ∈ {1, . . . , m}) -r i ∈ -L i (A -1 C -1 ) z - m j=1 L * j v j + B -1 i v i + D -1 i v i . ( 3
(∀n ∈ N) y 1,n = x n -γ n Cx n + m j=1 L * j v j,n p 1,n = J γnA ( y 1,n + γ n z) (3.26)
and

(∀i ∈ {1, . . . , m})(∀n ∈ N) y 2,i,n = v i,n + γ n (L i x n -D -1 i v i,n ) p 2,i,n = J γnB -1 i ( y 2,i,n -γ n r i ). (3.27)
Then, in view of (3.3),

(∀n ∈ N) y 1,n -y 1,n ≤ γ n a 1,n ≤ β -1 a 1,n (3.28)
and, using the nonexpansiveness of the resolvents [8, Proposition 23.7], we obtain

(∀n ∈ N) p 1,n -p 1,n ≤ J γnA (y 1,n + γ n z) + b 1,n -J γnA ( y 1,n + γ n z) ≤ y 1,n -y 1,n + b 1,n ≤ β -1 a 1,n + b 1,n . (3.29)
Since the sequences (a On the other hand, we deduce from (ii)(a) that there exists u ∈ H such that

u ∈ Ax and z = u + m j=1 L * j v j + Cx, (3.32)
and that (∀i ∈ {1, . . . , m}

) L i x -r i -D -1 i v i ∈ B -1 i v i . (3.33)
In addition, (3.26) yields

(∀n ∈ N) γ -1 n (x n -p 1,n ) -Cx n - m j=1 L * j v j,n + z ∈ A p 1,n (3.34)
while (3.27) yields

(∀i ∈ {1, . . . , m})(∀n ∈ N) γ -1 n (v i,n -p 2,i,n ) + L i x n -D -1 i v i,n -r i ∈ B -1 i p 2,i,n . (3.35)
Now let us set Using the Cauchy-Schwarz inequality, and the Lipschitzianity and monotonicity of C, we obtain

(∀n ∈ N) α 1,n = x n -p 1,n ε -1 p 1,n -x + µ x n -x + m i=1 L i v i,n -v i α 2,n = m i=1 (ε -1 + ν i ) v i,n -p 2,i,n p 2,i,n -v i . ( 3
(∀n ∈ N) α 1,n + x n -x m i=1 L * i (v i -v i,n ) ≥ x n -p 1,n ε -1 p 1,n -x + Cx n -Cx + p 1,n -x n m i=1 L * i (v i -v i,n ) + x n -x m i=1 L * i (v i -v i,n ) = x n -p 1,n ε -1 p 1,n -x + Cx n -Cx + p 1,n -x m i=1 L * i (v i -v i,n ) ≥ p 1,n -x γ -1 n (x n -p 1,n ) + m i=1 L * i (v i -v i,n ) + p 1,n -x n | Cx -Cx n = p 1,n -x γ -1 n (x n -p 1,n ) - m i=1 L * i v i,n -Cx n + m i=1 L * i v i + Cx + x -x n | Cx -Cx n = p 1,n -x γ -1 n (x n -p 1,n ) - m i=1 L * i v i,n -Cx n + z -u + x -x n | Cx -Cx n ≥ p 1,n -x γ -1 n (x n -p 1,n ) - m i=1 L * i v i,n -Cx n + z -u . (3.38)
Now suppose that A is uniformly monotone at x. Then, in view of (3.32), (3.34), and (3.38), there exists an increasing function φ A : [0, +∞[ → [0, +∞] that vanishes only at 0 such that

(∀n ∈ N) α 1,n + x n -x m i=1 L * i (v i -v i,n ) ≥ φ A ( p 1,n -x ). (3.39)
On the other hand, it follows from (3.36), the Lipschitzianity of the operators (D -1 i ) 1≤i≤m , (3.33), (3.35), and the monotonicity of the operators (B -1 i ) 1≤i≤m and (D

-1 i ) 1≤i≤m that (∀n ∈ N) α 2,n + x n -x m i=1 L * i ( p 2,i,n -v i ) ≥ m i=1 γ -1 n (v i,n -p 2,i,n ) -D -1 i v i,n + D -1 i p 2,i,n + L i (x n -x) | p 2,i,n -v i = m i=1 γ -1 n (v i,n -p 2,i,n ) + L i x n -D -1 i v i,n -r i -(L i x -r i -D -1 i v i ) | p 2,i,n -v i + D -1 i p 2,i,n -D -1 i v i | p 2,i,n -v i ≥ 0. ( 3
(∀n ∈ N) α 1,n + α 2,n + x n -x m i=1 L * i ( p 2,i,n -v i,n ) ≥ φ A ( p 1,n -x ). ( 3
(∀n ∈ N) α 1,n + α 2,n + x n -x m i=1 L * i ( p 2,i,n -v i,n ) ≥ φ C ( x n -x ), (3.42)
and we reach the same conclusion.

(ii)(f): Suppose that B -1 i is uniformly monotone at v i for some i ∈ {1, . . . , m}. Then, proceeding as in (3.40), there exists an increasing function φ B i : [0, +∞[ → [0, +∞] that vanishes only at 0 such that

(∀n ∈ N) α 2,n + x n -x m j=1 L * j ( p 2,j,n -v j ) ≥ m j=1 γ -1 n (v j,n -p 2,j,n ) + L j x n -D -1 j v j,n -r j -(L j x -r j -D -1 j v j ) | p 2,j,n -v j + D -1 j p 2,j,n -D -1 j v j | p 2,j,n -v j ≥ m j=1 γ -1 n (v j,n -p 2,j,n ) + L j x n -D -1 j v j,n -r j -(L j x -r j -D -1 j v j ) | p 2,j,n -v j ≥ γ -1 n (v i,n -p 2,i,n ) + L i x n -D -1 i v i,n -r i -(L i x -r i -D -1 i v i ) | p 2,i,n -v i ≥ φ B i ( p 2,i,n -v i ). (3.43)
On the other hand, according to (3.38),

(∀n ∈ N) α 1,n + x n -x m j=1 L * j (v j -v j,n ) ≥ 0. (3.44)
Hence,

(∀n ∈ N) α 1,n + α 2,n + x n -x m j=1 L * j ( p 2,j,n -v j,n ) ≥ φ B i ( p 2,i,n -v i ). (3.45)
By proceeding as previously, we infer that p 2,i,n → v i and hence, via (3.31) and (i), that p 2,i,n → v i and v i,n → v i . If D -1 i is uniformly monotone at v i , the same arguments lead to these conclusions.

In the following remarks, we comment on the structure of the proposed algorithm and its relation to existing work. (i) The algorithm achieves full splitting in that each of the operators appearing in Problem 1.1 is used separately.

(ii) The algorithm uses explicit steps for the single-valued operators and implicit steps for the set-valued operators. Since explicit steps are typically much easier to implement than implicit steps, the algorithm therefore exploits efficiently the properties of the operators.

(iii) The sequences (a 1,n ) n∈N , (b 1,n ) n∈N , and (c 1,n ) n∈N , and, for every i ∈ {1, . . . , m}, (a 2,i,n ) n∈N , (b 2,i,n ) n∈N , and (c 2,i,n ) n∈N relax the requirement for exact evaluations of the operators over the course of the iterations.

(iv) Most of the elementary steps in (3.3) can be executed in parallel.

(v) The update of the variable p 2,i,n can also be carried out using the resolvent of

B i since [8, Proposition 23.18] J γnB -1 i (y 2,i,n -γ n r i ) = y 2,i,n -γ n r i -γ n J γ -1 n B i (γ -1 n (y 2,i,n -γ n r i )).
Remark 3.3 Some noteworthy connections between Theorem 3.1 and existing work are the following.

(i) Unlike most splitting methods, the proposed algorithm is designed to solve explicitly a dual problem.

(ii) In the special case when m = 1 and D 1 is as in (1.3), the primal problem (1.1) reduces to (we drop the subscript '1' for brevity)

find x ∈ H such that z ∈ Ax + L * B(Lx -r) + Cx, (3.46)
the dual problem (1.2) reduces to

find v ∈ G such that -r ∈ -L (A + C) -1 (z -L * v) + B -1 v, (3.47)
and the algorithm is governed by the iteration

              y 1,n = x n -γ n Cx n + L * v n + a 1,n y 2,n = v n + γ n (Lx n + a 2,n ) p 1,n = J γnA (y 1,n + γ n z) + b 1,n p 2,n = J γnB -1 (y 2,n -γ n r) + b 2,n q 1,n = p 1,n -γ n Cp 1,n + L * p 2,n + c 1,n q 2,n = p 2,n + γ n (Lp 1,n + c 2,n ) x n+1 = x n -y 1,n + q 1,n v n+1 = v n -y 2,n + q 2,n . (3.48)
On the one hand, if C : x → 0, we recover the primal-dual setting of [START_REF] Briceño-Arias | A monotone+skew splitting model for composite monotone inclusions in duality[END_REF] and its algorithm ([10, Eq. (3.1)]). On the other hand, if L : x → 0, B : y → {0}, z = 0, and r = 0, (3.46) yields the problem studied in [START_REF] Tseng | A modified forward-backward splitting method for maximal monotone mappings[END_REF], and (3.48) without error terms and dual variables yields a primal algorithm proposed in that paper, namely

      y 1,n = x n -γ n Cx n p 1,n = J γnA y 1,n q 1,n = p 1,n -γ n Cp 1,n x n+1 = x n -y 1,n + q 1,n . (3.49)
Let us note that, even when we specialize (3.46) to G = H and L = Id , there does not appear to exist an alternative algorithm that splits A, B, and C and uses explicit steps on the Lipschitzian operator C.

(iii) When C : x → 0 and, for every i ∈ {1, . . . , m}, D -1 i : y → {0}, we recover the primal-dual setting of [START_REF] Briceño-Arias | A monotone+skew splitting model for composite monotone inclusions in duality[END_REF]Theorem 3.8]. However, the algorithm we obtain is different from that proposed in that paper, and novel.

(iv) In general, the weak convergence results of Theorem 3.1(ii) cannot be improved to strong convergence without additional hypotheses on the operators such as those described in (ii)(e) and (ii)(f). Indeed, in the special case when (1.1) reduces to the problem of finding a zero of A, the primal component of (3.3) reduces to the proximal point algorithm, namely (set

C : x → 0 in (3.49)) (∀n ∈ N) x n+1 = J γnA x n , (3.50)
which is known to converge weakly but not strongly [START_REF] Bauschke | A new proximal point iteration that converges weakly but not in norm[END_REF][START_REF] Güler | On the convergence of the proximal point algorithm for convex minimization[END_REF].

Minimization problems

The proposed monotone operator splitting algorithm can be applied to a broader class of problems than that within the reach of existing splitting methods. It has therefore potential applications in the areas in which these methods have been used, e.g., partial differential equations [START_REF] Gabay | Applications of the method of multipliers to variational inequalities[END_REF][START_REF] Mercier | Topics in Finite Element Solution of Elliptic Problems[END_REF], mechanics [START_REF]Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics[END_REF][START_REF] Mercier | Inéquations Variationnelles de la Mécanique[END_REF], variational inequalities [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF][START_REF] Facchinei | Finite-Dimensional Variational Inequalities and Complementarity Problems[END_REF][START_REF] Tseng | Applications of a splitting algorithm to decomposition in convex programming and variational inequalities[END_REF], game theory [START_REF] Briceño-Arias | Monotone operator methods for Nash equilibria in non-potential games[END_REF], traffic theory [START_REF] Fukushima | The primal Douglas-Rachford splitting algorithm for a class of monotone mappings with applications to the traffic equilibrium problem[END_REF], and evolution equations [START_REF] Attouch | A parallel splitting method for coupled monotone inclusions[END_REF]. In this section, we focus on the application of the results of Section 3 to convex minimization problems.

Problem 4.1 Let H be a real Hilbert space, let z ∈ H, let m be a strictly positive integer, let f ∈ Γ 0 (H), and let h : H → R be convex and differentiable with a µ-Lipschitzian gradient for some µ ∈ ]0, +∞[. For every i ∈ {1, . . . , m}, let G i be a real Hilbert space, let

r i ∈ G i , let g i ∈ Γ 0 (G i ), let ℓ i ∈ Γ 0 (G i ) be 1/ν i -
(g i ℓ i )(L i x -r i ) + h(x) -x | z , (4.1)
and the dual problem minimize

v 1 ∈G 1 ,...,vm∈Gm f * h * z - m i=1 L * i v i + m i=1 g * i (v i ) + ℓ * i (v i ) + v i | r i . (4.2)
The following result is an offspring of Theorem

let x 0 ∈ H, let (v 1,0 , . . . , v m,0 ) ∈ G 1 ⊕ • • • ⊕ G m , let ε ∈ ]0, 1/(β + 1)[, let (γ n ) n∈N be a sequence in [ε, (1 -ε)/β],
and set

(∀n ∈ N)                  y 1,n = x n -γ n ∇h(x n ) + m i=1 L * i v i,n + a 1,n p 1,n = prox γnf (y 1,n + γ n z) + b 1,n For i = 1, . . . , m       y 2,i,n = v i,n + γ n (L i x n -∇ℓ * i (v i,n ) + a 2,i,n ) p 2,i,n = prox γng * i (y 2,i,n -γ n r i ) + b 2,i,n q 2,i,n = p 2,i,n + γ n L i p 1,n -∇ℓ * i (p 2,i,n ) + c 2,i,n v i,n+1 = v i,n -y 2,i,n + q 2,i,n . q 1,n = p 1,n -γ n ∇h(p 1,n ) + m i=1 L * i p 2,i,n + c 1,n x n+1 = x n -y 1,n + q 1,n . (4.5)
Then the following hold.

(i)

n∈N x n -p 1,n 2 < +∞ and (∀i ∈ {1, . . . , m}) n∈N v i,n -p 2,i,n 2 < +∞.

(ii) There exist a solution x to (4.1) and a solution (v 1 , . . . , v m ) to (4.2) such that the following hold.

(a) z -m j=1 L * j v j ∈ ∂f (x) + ∇h(x) and (∀i ∈ {1, . . . , m}

) L i x -r i ∈ ∂g * i (v i ) + ∇ℓ * i (v i ). (b) x n ⇀ x and p 1,n ⇀ x. (c) (∀i ∈ {1, . . . , m}) v i,n ⇀ v i and p 2,i,n ⇀ v i .
(d) Suppose that f or h is uniformly convex at x. Then x n → x and p 1,n → x.

(e) Suppose that, for some i ∈ {1, . . . , m}, g

∈ ∂f (x) + m i=1 L * i (∂g i ∂ℓ i )(L i x -r i ) + ∇h(x), (4.7)
and of an m-tuple

(v 1 , . . . , v m ) ∈ G 1 ⊕ • • • ⊕ G m such that (∃ x ∈ H) z -m j=1 L * j v j ∈ ∂f (x) + ∇h(x) (∀i ∈ {1, . . . , m}) v i ∈ (∂g i ∂ℓ i )(L i x -r i ), ( 4
∂ f + h -• | z = ∂f + ∇h -z. (4.10)
As a result, we derive from (4.7) that

0 ∈ ∂ f + h -• | z (x) + m i=1 L * i ∂(g i ℓ i )(L i x -r i ) . (4.11)
However, since (4.3) and [8, Proposition 16.5(ii)] imply that

∂ f + h -• | z + m i=1 L * i ∂(g i ℓ i ) (L i • -r i ) ⊂ ∂ f + h -• | z + m i=1 (g i ℓ i ) • (L i • -r i ) , (4.12)
it follows from (4.11) that

0 ∈ ∂ f + h -• | z + m i=1 (g i ℓ i ) • (L i • -r i ) (x). ( 4
+ ∇h -1 = ∂(f + h) -1 = ∂(f + h) * = ∂ f * h * . ( 4
(∃ x ∈ H) x ∈ ∂(f * h * ) z -m j=1 L * j v j (∀i ∈ {1, . . . , m}) L i x -r i ∈ ∂ g * i + ℓ * i (v i ) (4.16)
and therefore

(∃ x ∈ H)        -(L i x) 1≤i≤m ∈ - m × i=1 L i ∂(f * h * ) z -m j=1 L * j v j (L i x) 1≤i≤m ∈ m × i=1 ∂ g * i + ℓ * i + • | r i (v i ).
(4.17)

Hence, using [8, Propositions 16.5(ii) and 16.8] and the notation (2.1), (0, . . . , 0) ∈ - In the following proposition we give conditions under which (4.3) is satisfied. Then (4.3) is satisfied if one of the following holds.

m × i=1 L i ∂(f * h * ) z - m j=1 L * j v j + m × i=1 ∂ g * i + ℓ * i + • | r i (v i ) = - m i=1 L * i * ∂(f * h * ) z - m i=1 L * i (v 1 , . . . , v m ) + ∂ m i=1 g * i + ℓ * i + • | r i (v 1 , . . . , v m ) ⊂ ∂ (f * h * ) z - m i=1 L * i • + m i=1 g * i + ℓ * i + • | r i (v 1 , . . . , v m ). ( 4
(i) (r 1 , . . . , r m ) ∈ sri S.

(ii) For every i ∈ {1, . . . , m}, g i or ℓ i is real-valued.

(iii) H and (G i ) 1≤i≤m are finite-dimensional, and there exists x ∈ ri dom f such that (∀i ∈ {1, . . . , m}) L i x -r i ∈ ri dom g i + ri dom ℓ i . Even in this special case, the algorithm resulting from (4.5) is new. This observation remains valid if we further assume that h : x → 0.

L * i (∂g i ∂ℓ i )(L i • -r i ) + ∇h -z = ∂ f + h -• | z + m i=1 L * i ∂(g i ℓ i ) (L i • -r i ) = ∂ f + h -• | z + m i=1 (g i ℓ i ) • (L i • -r i ) .

Example 1 . 2

 12 In Problem 1.1 set m = 1, C : x → 0, and D 1 : y → G 1 , if y = 0; ∅, if y = 0. (1.3)

Example 1 . 6

 16 In Problem 1.1, set m = 1, G 1 = G, L 1 = L, z = 0, and r 1 = 0, and let A and B 1 be the subdifferentials of lower semicontinuous convex functions f : H → ]-∞, +∞] and g : G → ]-∞, +∞], respectively. In addition, let C be the gradient of a differentiable convex function h : H → R, and let D be the subdifferential of a lower semicontinuous strongly convex function ℓ : G → ]-∞, +∞]. Then, under suitable constraint qualification, (1.1) assumes the form of the minimization problem minimize x∈H

  ,1,n , . . . , a 2,m,n ) b n = (b 1,n , b 2,1,n , . . . , b 2,m,n ) c n = (c 1,n , c 2,1,n , . . . , c 2,m,n ). (3.14) We first observe that our assumptions imply that n∈N a n < +∞, n∈N b n < +∞, and n∈N c n < +∞. (3.15) Furthermore, it follows from (3.7), (3.8), and (3.14), that (3.4) assumes in K the form of the errortolerant forward-backward-forward algorithm

. 16 )

 16 (i): It follows from (3.11), (3.13), (3.15), (3.16), and [10, Theorem 2.5(i)] that n∈N x n -p n 2 < +∞.

  .25) (ii)(c): This follows from (3.17), (3.18), and (3.21).(ii)(d): This follows from (3.17),(3.18), and(3.22).

. 40 )

 40 Adding (3.39) and (3.40) yields

Remark 3 . 2

 32 Here are some observations regarding the structure of algorithm (3.3).

. 18 )

 18 In other words, by Fermat's rule, (v 1 , . . . , v m ) solves (4.2). Finally, the strong convergence claims in (ii)(d) and (ii)(e) follow from Theorem 3.1(ii)(e)&(ii)(f) since the uniform convexity of a function ϕ ∈ Γ 0 (H) at a point of the domain of ∂ϕ implies the uniform monotonicity of ∂ϕ at that point[START_REF] Zȃlinescu | Convex Analysis in General Vector Spaces[END_REF] Section 3.4].

Proposition 4 . 3

 43 Suppose that (4.1) has at least one solution and set S = (L i x -y i ) 1≤i≤m x ∈ dom f and (∀i ∈ {1, . . . , m}) y i ∈ dom g i + dom ℓ i .(4.[START_REF] Fenchel | Convex Cones, Sets and Functions[END_REF]

(4. 20 )

 20 Proof. It follows from(4.19) and[START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF] Proposition 12.6(ii)] thatS = (L i x -y i ) 1≤i≤m x ∈ dom f and (∀i ∈ {1, . . . , m}) y i ∈ dom(g i ℓ i ) = (L i x -y i ) 1≤i≤m x ∈ dom(f + h -• | z ) and (y i ) 1≤i≤m ∈ m × i=1 dom(g i ℓ i ) = m × i=1 L i dom f + h -• | z -dom m i=1 (g i ℓ i ). (4.21) (i): In view of (4.21), (r 1 , . . . , r m ) ∈ sri S ⇒ (0, . . . , 0) ∈ sri m × i=1L i dom f + h -• | z -dom m i=1 (g i ℓ i )(• -r i ) . (4.22) Hence, since ( × m i=1 L i ) * = m i=1 L * i ,it follows from (4.9), (4.10), and [8, Theorem 16.37(i)] that ∂f + m i=1

(4. 23 )L

 23 Since (4.1) has at least one solution it follows from Fermat's rule that 0 is in the range of the right-hand side of (4.23), which shows that (4.3) holds.(ii)⇒(i): We have (∀i ∈ {1, . . . , m})dom g i + dom ℓ i = G i . Therefore (4.19) yields S = m i=1 G i .(iii)⇒(i): We have sri S = ri S. However, it follows from (4.21) and [8, Corollary 6.15] that ri S = ri m i ri dom f -m × i=1 ri dom g i + ri dom ℓ i . (4.24) Hence (r 1 , . . . , r m ) ∈ sri S ⇔ (∃ x ∈ ri dom f )(∀i ∈ {1, . . . , m}) L i x -r i ∈ ri dom g i + ri dom ℓ i . Remark 4.4 In Problem 4.1, if each function ℓ i is the indicator function of {0}, then (4.1) reduces to minimize x∈H f (x) + m i=1 g i (L i x -r i ) + h(x) -x | z . (4.25)

  Lemma 2.41(iii)] that φ A ( p 1,n -x ) → 0 and, in turn, that p 1,n → x. Hence, in view of (i) and (3.30), we get x n → x and p 1,n → x. Likewise, if C is uniformly monotone at x, there exists an increasing function φ C : [0, +∞[ → [0, +∞] that vanishes only at 0 such that

	.41)
	It then follows from (3.37), (ii)(c), (i), (3.31), and [8,

  strongly convex, for some ν i ∈ ]0, +∞[, and suppose that L i : H → G i is a nonzero bounded linear operator. Consider the problem

			m
	minimize x∈H	f (x) +	i=1

  3.1. Let (a 1,n ) n∈N , (b 1,n ) n∈N , and (c 1,n ) n∈N be absolutely summable sequences in H and, for every i ∈ {1, . . . , m}, let (a 2,i,n ) n∈N , (b 2,i,n ) n∈N , and (c 2,i,n ) n∈N be absolutely summable sequences in G i .

	Theorem 4.2 In Problem 4.1, suppose that
	m
	z ∈ ran ∂f +	L * i (∂g i ∂ℓ i )(L i • -r i ) + ∇h .	(4.3)
	i=1
	Furthermore, set
		m
	β = max{µ, ν 1 , . . . , ν m } +	L i 2 ,	(4.4)
		i=1

  * i or ℓ * i is uniformly convex at v i . Then v i,n → v i and p 2,i,n → v i . Proof. Let us first establish a connection between Problem 4.1 and Problem 1.1. To this end, let us define A = ∂f, C = ∇h, and (∀i ∈ {1, . . . , m}) B i = ∂g i and D i = ∂ℓ i . Proposition 17.10] that C is monotone. On the other hand, for every i ∈ {1, . . . , m}, it follows from the 1/ν i -strong convexity of ℓ i and [8, Corollary 13.33 and Theorem 18.15] that ℓ * i is Fréchet differentiable on G i with a ν i -Lipschitzian gradient, and from (2.7) that D -1 i = ∇ℓ * i . Altogether, we can apply Theorem 3.1 to obtain the existence of a point x ∈ H such that z

	(4.6)

It is clear that (4.3) yields (3.1) and, using (2.7) and (2.8), that (4.5) yields

(3.3)

. Moreover, it follows from

[START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF] Theorem 20.40

] that the operators A and (B i ) 1≤i≤m are maximally monotone, and from

[8,

  .8) that satisfy (i) and (ii). It remains to show that x solve (4.1) and (v 1 , . . . , v m ) solves (4.2). We first observe that since, for every i ∈ {1, . . . , m}, dom ℓ * i = G i [8, Proposition 24.27] yields (∀i ∈ {1, . . . , m}) ∂g i ∂ℓ i = ∂(g i ℓ i ).

	(4.9)
	On the other hand, it follows from [8, Corollary 16.38(iii) and Proposition 17.26(i)] that

This work was supported by the Agence Nationale de la Recherche under grants ANR-08-BLAN-0294-02 and ANR-09-EMER-004-03.