N A Nguyen

S Olaru

P Rodriguez-Ayerbe

Convex Lifting: Theory and Control Applications N. A. Nguyen 1 , M. Gulan2 , S. Olaru 1 , P. Rodriguez-Ayerbe 1 Abstract-This paper presents the concept of convex lifting which will be proven to enable significant implementation benefits for the class of piecewise affine controllers. Accordingly, two different algorithms to construct a convex lifting for a given polyhedral/polytopic partition will be presented. These two algorithms rely on either the vertex or the halfspace representation of the related polyhedra. Also, we introduce an algorithm to refine a polyhedral partition, which does not admit a convex lifting, into a convexly liftable one. Furthermore, two different schemes will be put forward to considerably reduce both the memory footprint and the online evaluation effort, which play a key role in implementation of piecewise affine controllers. Finally, these results will be illustrated via numerical examples and a complexity analysis.

Index Terms-Convex lifting, model predictive control, parametric programming, explicit solutions.

I. MOTIVATION

Explicit model predictive control (MPC) has received significant attention in control community due to its relevance for rather small-dimensional systems [START_REF] Bemporad | The explicit linear quadratic regulator for constrained systems[END_REF], [START_REF] Grancharova | Explicit Nonlinear Model Predictive Control[END_REF], [START_REF] Oberdieck | Explicit hybrid model-predictive control: The exact solution[END_REF], [START_REF] Olaru | A parameterized polyhedra approach for explicit constrained predictive control[END_REF], [START_REF] Seron | Characterisation of receding horizon control for constrained linear systems[END_REF]. However, even if the controllers are explicitly obtained, there exist major problems in terms of their implementation once the number of regions in the state-space partition becomes large. In particular, it requires storing all the regions at the hardware level, making their implementation, namely on embedded computing platforms, difficult due to their limited memory storage and computational performance.

Various efficient implementation algorithms have been put forward so far [START_REF] Kvasnica | Clipping-based complexity reduction in explicit MPC[END_REF], [START_REF] Kvasnica | Complexity reduction of explicit model predictive control via separation[END_REF], however, the requirement of substantial memory for storing the given partition is inevitable. Another contribution about efficient storage strategy was presented in [START_REF] Baotic | Efficient on-line computation of constrained optimal control[END_REF]. This proposal can avoid storing the state-space partition, however, the point-location problem, determining which region the current state belongs to, becomes more demanding; see among the other point-location algorithms [START_REF] Bayat | Using hash tables to manage the time-storage complexity in a point location problem: Application to explicit model predictive control[END_REF], [START_REF]Flexible piecewise function evaluation methods based on truncated binary search trees and lattice representation in explicit MPC[END_REF], [START_REF] Tøndel | Evaluation of piecewise affine control via binary search tree[END_REF]. Therefore, it is necessary to investigate other implementation approaches for this class of controllers, which can avoid storing the state-space partition and possibly facilitate the point-location problem. This work presents the convex lifting concept, which enables efficient implementation of piecewise affine (PWA) controllers. We have recently learned that an independent study in [START_REF] Airan | Linear machine solution to point location problem[END_REF] exploited the linear machine concept, which is actually similar to the convex lifting notion Bratislava, Slovakia. martin.gulan@stuba.sk exploited in this paper. It is worth noting that existence conditions for convex liftings are not available in this reference. Also, the treatment of convexly non-liftable partitions is not investigated therein. In this paper, we present constructions based on two different polyhedra representations-the vertex one and the halfspace one. Also, an algorithm to refine a convexly non-liftable partition into a convexly liftable one is introduced.

For ease of presentation, let us start with some special cases of parametric linear programming problem where the optimal cost function presents an interesting property. To illustrate these points, consider a linear MPC problem with respect to a linear cost function. Such a problem can easily be transformed into a parametric linear programming problem as follows:

u * (x) = arg min u C T u subject to Du ≤ W + Ex. (1)
Recall that C T u * (x) was shown through Theorems IV-3 and IV-4 in [START_REF]Postoptimal analyses, parametric programming and related topics[END_REF] to be a convex, continuous, PWA function defined over a polyhedral partition {X i } i∈I N , where I N = {1, 2, . . . , N } . Let us denote the optimal cost function and optimal solution of (1) as follows:

C T u * (x) = a T i x + b i for x ∈ X i , u * (x) = H i x + G i for x ∈ X i . (2)
Since C T u * (x) is also a convex function, this optimal cost function can alternatively be written in the following form:

C T u * (x) = max j∈I N (a T j x + b j ). (3)
Accordingly, as advocated in [START_REF] Baotic | Efficient on-line computation of constrained optimal control[END_REF], if the optimal solution to the parametric linear programming problem (1) is unique, then implementation of the optimal control law u * (x) can be carried out according to Algorithm 1.

Algorithm 1 Efficient implementation of PWA controllers 1: Store (H j , G j ) and (a j , b j ). 2: At each sampling time, obtain the current state x.

3: Find index i ∈ I N such that:

a T i x + b i = max j∈I N
(a T j x + b j ).

4: Evaluate the control action u * (x) = H i x + G i . 5: Return to step 2.

A significant advantage of this implementation is that it enables to avoid storing the state-space partition and facilitates the point-location problem. However, as emphasized above, this implementation only holds if the optimal solution to (1) is unique, because in this case for any pair of different regions (X i , X j ), their optimal cost function satisfies (a i , b i ) = (a j , b j ). Note also that in the case the uniqueness of the optimal solution to (1) is fulfilled, the optimal cost function of the parametric linear programming problem (1) is, from a geometrical point of view, nothing other than a convex lifting associated with the state-space partition {X i } i∈I N (this will be formally proven later in Theorem II.7), since a convex lifting can equivalently be understood as a convex, continuous, piecewise affine function defined over a polyhedral partition such that any pair of different regions is lifted onto two distinct hyperplanes. Otherwise, in the case the optimal solution to (1) is not unique or the state-space partition is obtained from a linear MPC problem with respect to a quadratic cost function, this implementation is no longer applicable, even if the state-space partition admits a convex lifting. Motivated by this limitation, algorithms to verify the existence of a convex lifting and to construct it for a given partition are required. It is worth recalling that an algorithm to construct a convex lifting based on the vertex representation has recently been presented in [START_REF]Constructive solution to inverse parametric linear/quadratic programming problems via convex liftings[END_REF], [START_REF]Inverse parametric linear/quadratic programming problem for continuous PWA functions defined on polyhedral partitions of polyhedra[END_REF]. However, efficiency of this algorithm is limited to rather small-dimensional partitions, since it requires vertex enumeration. To overcome this issue, in this paper we complete the convex lifting methodology with an algorithm relying on the halfspace representation. Accordingly, the feasibility of the formulated optimization problem is shown to represent another necessary and sufficient condition for the existence of a convex lifting. This paper further addresses the convexly non-liftable partitions by introducing an algorithm to refine a given convexly non-liftable partition into a convexly liftable one. Moreover, applications of these results in implementation of PWA controllers are presented. Both numerical examples and complexity analysis show promising results of the proposed implementations in comparison with some existing methods. This enables PWA control laws to be implemented even on low-end embedded hardware with limited computational performance and available memory.

II. PRELIMINARIES

R, R + , N >0 denote the field of real numbers, the set of nonnegative real numbers and the positive integer set, respectively.

Given an arbitrary set S, conv(S) denotes the convex hull of S; aff(S) denotes the affine hull of S. Also, dim(S) stands for the dimension of aff(S). If S is a full-dimensional set, then int(S) denotes its interior. Given a set S ⊆ R d and a subspace S of R d , then Proj S S denotes the orthogonal projection of S onto the space S. We use |S| to denote the cardinality of the set S. If Ω denotes a polyhedral partition, then |Ω| denotes the number of its regions.

A polyhedron is defined as the intersection of finitely many closed halfspaces. A polytope is defined as a bounded polyhedron. Given a polyhedron S, we use V(S) to denote the set of its vertices and R(S) denotes the set of its extreme rays. Further, if S ⊆ R d is a full-dimensional polyhedron, a face of S is the intersection of S and one of its supporting hyperplanes. k-face represents a face of dimension k. A 0-face is called a vertex, a 1-face is called an edge, a (d -1)-face is called a facet. Also, F(S) denotes the set of all facets of the polyhedron S. Given two sets S 1 , S 2 , we use S 1 \S 2 to denote the following set:

S 1 \S 2 := {x : x ∈ S 1 , x / ∈ S 2 } .
Given a matrix G ∈ R m×n , we denote size(G, 1) = m and size(G, 2) = n. Also, G(i, •) denotes the i-th row of matrix G, while G(i, j : k) denotes the i-th row of G, truncated from the j-th column to the k-th column, for 1 ≤ i ≤ m and 1 ≤ j ≤ k ≤ n. If j = k, then G(i, j) denotes the element of the i-th row and the j-th column. Let us recall also some useful definitions.

Definition II.1 A collection of N ∈ N >0 full-dimensional polyhedra X i ⊂ R d , denoted by {X i } i∈I N , is called a polyhedral partition of a polyhedron X ⊆ R d if: 1) X = i∈I N X i , 2) int(X i ) int(X j ) = ∅ with i = j, (i, j) ∈ I 2 N . (X i , X j ) are called neighboring or adjacent if (i, j) ∈ I 2 N , i = j and dim(X i ∩ X j ) = d -1. Also, if X is a polytope then {X i } i∈I N is called a polytopic partition.
In the case X is not a polyhedron, {X i } i∈I N is still called a polyhedral/polytopic partition but of a nonconvex polyhedral set.

The definition of a cell complex was presented by Grünbaum in [START_REF] Grünbaum | Convex polytopes[END_REF]. For simplicity, a cell complex should be hereafter understood as a polyhedral partition whose face-to-face property is fulfilled, i.e., the intersection of any pair of regions is either empty or a common face. Also, if X is a polyhedron, then a cell complex of X is understood as a polyhedral partition whose facet-to-facet property is satisfied, meaning any pair of neighboring regions share a common facet. For illustration, the polytopic partition in Fig. 1 is a cell complex.

-2 -1 0 1 2 -2 -1 0 1 2 Fig. 1: A cell complex of a polytope in R 2 .
Definition II.2 For a given polyhedral partition {X i } i∈I N of a polyhedron X ⊆ R d , a piecewise affine lifting is described by a function z : X → R with:

z(x) = a T i x + b i for any x ∈ X i , (4)
and

a i ∈ R d , b i ∈ R, ∀i ∈ I N . Definition II.3 Given a polyhedral partition {X i } i∈I N of a polyhedron X ⊆ R d , a piecewise affine lifting z(x) = a T i x + b i for x ∈ X i
, is called a convex piecewise affine lifting if the following conditions hold true:

• z(x) is continuous over X ,

• for each i ∈ I N , z(x) > a T j x + b j for all x ∈ X i \X j and all j = i, j ∈ I N .

The second condition in the above definition implies that z(x) is a convex function defined over X . Moreover, the strict inequalities ensure that any pair of neighboring regions is lifted onto two distinct hyperplanes. For ease of presentation, a slight abuse of notation is used henceforth: a convex lifting is understood as a convex piecewise affine lifting.

With respect to the above definition, if a polyhedral partition {X i } i∈I N admits a convex lifting, then it has to be a cell complex. This observation was stated via Proposition 2.1 in [START_REF]Constructive solution to inverse parametric linear/quadratic programming problems via convex liftings[END_REF]. It is recalled in the sequel for completeness; the interested reader is referred to this reference for the proof.

Proposition II.4 A polyhedral partition of a polyhedron, which admits a convex lifting, is a cell complex.

According to Proposition II.4, a convex lifting is always defined over a cell complex. However, the cell complex characterization of {X i } i∈I N is a necessary condition for the existence of a convex lifting, but not a sufficient one.

Remark II.5 Note also that Proposition II.4 does not necessarily restrict {X i } i∈I N to a polyhedral partition of a polyhedron. In other words, a polyhedral partition of a suitable set X ⊆ R d , which admits a convex lifting, should also be a cell complex.

Definition II.6 A given cell complex {X i } i∈I N in R d has an affinely equivalent polyhedron if there exists a polyhedron X ⊂ R d+1 such that for each i ∈ I N :

1

) ∃F i ∈ F( X ) satisfying: Proj R d F i = X i , 2) if z(x) = min z z s.t. x T z T ∈ X , then x z(x) ∈ F i for x ∈ X i .
An illustration can be found in Fig. 2 where a cell complex in R consists of the multicolored segments along the horizontal axis. One of its affinely equivalent polyhedra in R 2 is the pink shaded region. Moreover, the lower facets of this polytope are an illustration of the facets F i appearing in Definition II.6. Note that given a polyhedron X ⊂ R d+1 , if z denotes the last coordinate of X such that x T z T ∈ X , then the optimal solution to the following parametric linear programming problem:

z * (x) = min z z subject to x T z T ∈ X (5)
is nothing other than a convex lifting for the cell complex associated with this optimal solution. This observation will be proven in the sequel. First, consider the parametric linear programming problem (1) and its optimal solution (2). We will prove that if the optimal solution to (1) is unique, then the optimal cost function of (1) is a convex lifting for the polyhedral partition associated with the optimal solution (2).

Theorem II.7 If the optimal solution to the parametric linear programming problem (1) is unique, then the optimal cost function C T u * (x) is a convex lifting for the polyhedral partition associated with u * (x).

Proof: According to Theorems IV-3 and IV-4 in [START_REF]Postoptimal analyses, parametric programming and related topics[END_REF], C T u * (x) is a convex, continuous and piecewise affine function defined over the polyhedral partition {X i } i∈I N , associated with the optimal solution u * (x). Accordingly, to prove C T u * (x) to be a convex lifting for {X i } i∈I N , it suffices to show that for any pair of different regions (X i , X j ),

(C T H i , C T G i ) = (C T H j , C T G j ).
Suppose that the converse situation happens, i.e., there exist two different regions (X i , X j ), i = j, (i, j) ∈ I 2 N such that

(C T H i , C T G i ) = (C T H j , C T G j ). We prove that both cases (H i , G i ) = (H j , G j ) and (H i , G i ) = (H j , G j ) never happen. If (H i , G i ) = (H j , G j ),
we denote the set of constraints active at u * (x) = H i x + G i for x ∈ X i as below

D [i] u ≤ W [i] + E [i] x. (6)
Since (H i , G i ) = (H j , G j ), we then obtain i] x. Note that this end holds for all x ∈ X i as a fulldimensional polyhedron, which thus yields

D [i] (H j x+G j ) = W [i] + E [
D [i] H j = E [i] , D [i] G j = W [i] . (7)
Note however that for x ∈ int(X j ), there exists at least one constraint in [START_REF] Avis | A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra[END_REF] which is inactive at u * (x) = H j x + G j , due to X j = X i and the uniqueness of the optimal solution. Without loss of generality, suppose this constraint is D [i] (1, •)u ≤ W [i] (1) + E [i] (1, •)x. Accordingly, it yields:

D [i] (1, •)(H j x + G j ) < W [i] (1) + E [i] (1, •)x. (8)
Inclusions [START_REF] Baotic | Efficient on-line computation of constrained optimal control[END_REF] and ( 8) are clearly contradictory. In other words, the case

(H i , G i ) = (H j , G j ) cannot happen. Otherwise, if (H i , G i ) = (H j , G j ), consider x 1 ∈ int(X i ), x 2 ∈ X j and a scalar α ∈ [0, 1] . Due to the convexity of C T u * (x), we can see that C T u * (αx 1 + (1 -α)x 2 ) ≤ αC T (H i x 1 + G i ) + (1 -α)C T (H j x 2 + G j ). (9)
If we choose α close enough to

1 such that αx 1 +(1-α)x 2 ∈ X i , then C T u * (αx 1 + (1 -α)x 2 ) = C T (H i (αx 1 + (1 -α)x 2 ) + G i ).
(10) Note also that according to the assumption

(C T H i , C T G i ) = (C T H j , C T G j ), it follows that αC T (H i x 1 + G i ) + (1 -α)C T (H j x 2 + G j ) = C T H i (αx 1 + (1 -α)x 2 ) + C T G i . (11)
Also, since

H i x 1 + G i , H j x 2 + G j satisfy the constraint set in (1), so does α(H i x 1 + G i ) + (1 -α)(H j x 2 + G j ).
According to ( 9), ( 10), [START_REF] Borrelli | On the computation of linear model predictive control laws[END_REF], α(

H i x 1 + G i ) + (1 -α)(H j x 2 + G j )
is also an optimal solution to (1). Due to the uniqueness of the optimal solution to (1), we obtain the following:

H i (αx 1 +(1-α)x 2 )+G i = α(H i x 1 +G i )+(1-α)(H j x 2 +G j ),
leading to

H i x 2 + G i = H j x 2 + G j . (12)
It is worth emphasizing that (12) holds true for all x 2 ∈ X j .

Since (H i , G i ) = (H j , G j ), the set of x ∈ R d satisfying H i x+ G i = H j x + G j represents a polyhedron of dimension lower than d, while X j is a full-dimensional polyhedron in R d . This is clearly contradictory. Therefore, the initial hypothesis is not true. In other words, if the optimal solution to (1) is unique, the optimal cost function C T u * (x) describes a convex lifting for the associated polyhedral partition {X i } i∈I N . Now, let us come back to prove that the optimal solution to (5) stands for a convex lifting of the associated polyhedral partition.

Lemma II.8 Given the parametric linear programming problem (5), if {X i } i∈I N denotes the polyhedral partition associated with z * (x), then z * (x) is a convex lifting for {X i } i∈I N .

Proof: First, we will prove that the optimal solution to (5) is unique. Indeed, suppose there exist two optimal solutions to (5), denoted by z * 1 (x) and z * 2 (x), respectively. Without loss of generality, suppose z * 1 (x), z * 2 (x) are defined on the same polyhedral partition {X i } i∈I N . Consider a region X i in this polyhedral partition and denote these optimal solutions over X i as follows:

z * 1 (x) = (a (1)
i ) T x + b (1) i for x ∈ X i , z * 2 (x) = (a (2)
i ) T x + b (2) i for x ∈ X i . Since z * 1 (x), z * 2 (x)
represent optimal cost function of (5), we thus obtain:

(a (1) i ) T x + b (1) i = (a (2) i ) T x + b (2) i . ( 13
)
Note that ( 13) holds for all x ∈ X i , as a full-dimensional polyhedron. Accordingly, this holds only if (a

(1) i , b (1)
i ) = (a (2) i , b (2)
i ). In other words, the optimal solution to ( 5) is unique. According to Theorem II.7, the optimal cost function of (5) represents a convex lifting of {X i } i∈I N .

III. CONSTRUCTIONS OF CONVEX LIFTING

A. Existing results on convex lifting

The definition of a convex lifting has been presented earlier.

In control theory, so far, convex liftings have been employed to solve the inverse parametric linear/quadratic programming problem [START_REF] Nguyen | Explicit robust constrained control for linear systems: analysis, implementation and design based on optimization[END_REF]- [START_REF]Inverse parametric convex programming problems via convex liftings[END_REF]. Many necessary and sufficient conditions for the existence of convex liftings for cell complexes were investigated in different studies [START_REF] Aurenhammer | Criterion for the affine equivalence of cell complexes in R d and convex polyhedra in R d+1[END_REF]- [START_REF]Voronoi diagramsa survey of a fundamental geometric data structure[END_REF], [START_REF] Crapo | Plane self stresses and projected polyhedra 1: the basic pattern[END_REF], [START_REF]Spaces of stresses, projections and parallel drawings for spherical polyhedra[END_REF], [START_REF] Maxwell | On reciprocal diagrams and diagrams of forces[END_REF], [START_REF] Rybnikov | Polyhedral partitions and stresses[END_REF], [START_REF] Schulz | Lifting planar graphs to realize integral 3-polytopes and topics in pseudo-triangulations[END_REF]. It is shown in [START_REF] Rybnikov | Polyhedral partitions and stresses[END_REF] that there exists a convex lifting for a cell complex in R d if and only if one of the following holds:

• it admits a strictly positive d-stress;

• it is an additively weighted Dirichlet-Voronoi diagram;

• it is an additively weighted Delaunay decomposition. The interested reader is referred to [START_REF] Nguyen | Explicit robust constrained control for linear systems: analysis, implementation and design based on optimization[END_REF] for further details of the above notation and to [3]- [START_REF]Voronoi diagramsa survey of a fundamental geometric data structure[END_REF], [START_REF] Rybnikov | Polyhedral partitions and stresses[END_REF] for other related results. Note that the above results cover the general class of cell complexes in R d . Unfortunately, despite the mathematical completeness of the existing results, the verification of these conditions is in general expensive. Furthermore, they do not provide any hint for the construction of a convex lifting. On the other hand, control applications require specific algorithms to verify the convex liftability of the given cell complexes and to construct their convex liftings if they exist. These elements are detailed in the following subsections. We remark that the construction of convex liftings for some special cases, e.g., Voronoi diagrams and Delaunay triangulations and their recognition were already investigated in [START_REF]Voronoi diagramsa survey of a fundamental geometric data structure[END_REF], [START_REF] Edelsbrunner | Voronoi diagrams and arrangements[END_REF], [START_REF] Hartvigsen | Recognizing voronoi diagrams with linear programming[END_REF].

B. Construction of convex lifting based on the vertex representation

The main objective of this subsection is to present an algorithm for the construction of a convex lifting for a given cell complex via linear/quadratic programming. Given a cell complex

{X i } i∈I N of a polytope X ⊂ R d , let a convex lifting z(x) of {X i } i∈I N be denoted by z(x) = a T i x + b i for x ∈ X i , one needs to determine (a i , b i ) for all i ∈ I N .
The construction of z(x) based on the vertex representation is presented in [START_REF]Constructive solution to inverse parametric linear/quadratic programming problems via convex liftings[END_REF] and is recalled in Algorithm 2 for completeness. We remark that this construction is limited to polytopic partitions since it hinges on suitable constraints imposed at the vertices of this partition. Extension of this construction to polyhedral partitions of unbounded polyhedra can be found in [START_REF]Inverse parametric linear/quadratic programming problem for continuous PWA functions defined on polyhedral partitions of polyhedra[END_REF].

Note that the cost function in ( 16) is chosen so as to avoid the unboundedness of optimal solution. Other choices are possible as long as the boundedness of optimal solution is ensured. Also, as seen in ( 15), the strict inequality in the second condition of Definition II.3 can easily be transformed into inequality constraints of an optimization problem by adding a positive constant c on the right-hand side of ( 15), thus > can be replaced with ≥ .

Algorithm 2 Construction of a convex lifting for a given cell complex

{X i } i∈I N of a polytope X ⊂ R d . Input: {X i } i∈I N and a given constant c > 0. Output: (a i , b i ), ∀i ∈ I N .
1: Register all pairs of neighboring regions in {X i } i∈I N . 2: For each pair of neighboring regions (X i , X j ),

• add continuity conditions ∀v ∈ V(X i ∩ X j ):

a T i v + b i = a T j v + b j ; (14)
• add convexity conditions ∀v ∈ V(X i )\V(X j ):

a T i v + b i ≥ a T j v + b j + c. (15)
3: Solve the following convex optimization problem by minimizing a chosen cost function, e.g., 14), ( 15). ( 16)

min ai, bi N i=1 (a T i a i + b T i b i ) subject to (
Now, we will step by step prove that the feasibility of the optimization problem ( 16) serves as another necessary and sufficient condition for the convex liftability of the given polytopic partition of a polytope.

Proposition III.1 If problem (16) is feasible, then function z(x) = a T i x + b i for x ∈ X i is a convex lifting over the given cell complex {X i } i∈I N .
The interested reader is referred to Theorem 4.1 in [START_REF]Constructive solution to inverse parametric linear/quadratic programming problems via convex liftings[END_REF] for the proof of Proposition III.1. We remark that this proposition only provides a sufficient condition for the existence of a convex lifting, while no result has been presented in [START_REF]Constructive solution to inverse parametric linear/quadratic programming problems via convex liftings[END_REF] to clarify how the choice of the scalar constant c in Algorithm 2 affects the feasibility of the optimization problem [START_REF]Postoptimal analyses, parametric programming and related topics[END_REF]. Theoretically, if the given cell complex is convexly liftable, then any positive value of c does not have any effect on the feasibility of the optimization problem [START_REF]Postoptimal analyses, parametric programming and related topics[END_REF].

Proposition III.2 Given a cell complex {X i } i∈I N of a poly- hedron X ⊆ R d , if z(x) = a T i x+b i for x ∈ X i is a convex lift- ing for this cell complex, then so is z(x) = (αa i ) T x+(αb i )+β for x ∈ X i , for any α > 0, β ∈ R.
Proof: In fact, if z(x) represents a convex lifting for the given cell complex {X i } i∈I N , then according to the definition of a convex lifting, for each pair of neighboring regions (X i , X j ), it follows that:

a T i x + b i = a T j x + b j for x ∈ X i ∩ X j , a T i x + b i > a T j x + b j for x ∈ X i \X j . (17)
Accordingly, for any α > 0, β ∈ R, (17) amounts to:

(αa i ) T x + αb i + β = (αa j ) T x + αb j + β for x ∈ X i ∩ X j , (αa i ) T x + αb i + β > (αa j ) T x + αb j + β for x ∈ X i \X j . (18)
Inclusion [START_REF] Grünbaum | Convex polytopes[END_REF] means that z(x) = (αa i ) T x + (αb i ) + β for x ∈ X i is also a convex lifting for the given cell complex for any α > 0, β ∈ R.

We now prove that the feasibility of the optimization problem ( 16) serves as a necessary and sufficient condition for the convex liftability of the given polytopic partition {X i } i∈I N of a polytope.

Theorem III.3 The given polytopic partition {X i } i∈I N of a polytope X , is convexly liftable if and only if the optimization problem ( 16) is feasible for any constant c > 0.

Proof: ←-This inclusion directly follows according to Proposition III.1.

-→ If the given polytopic partition, denoted by {X i } i∈I N , is convexly liftable, then there exists a constant c > 0 and a function z(x) = a T i x + b i for x ∈ X i such that for any pair of neighboring regions (X i , X j ), the following holds:

a T i v + b i = a T j v + b j for v ∈ V(X i ∩ X j ), a T i v + b i ≥ a T j v + b j + c for v ∈ V(X i )\V(X j ). (19)
According to Proposition III.2, if we choose α = c/c > 0, β = 0, (19) is equivalent to:

(αa i ) T v + (αb i ) = (αa j ) T v + (αb j ) for v ∈ V(X i ∩ X j ), (αa i ) T v + (αb i ) ≥ (αa j ) T v + (αb j ) + c for v ∈ V(X i )\V(X j ).
In other words, (αa i , αb i ) for all i ∈ I N also make the constraint set ( 14) and ( 15) feasible. Therefore, the optimization problem ( 16) is feasible with any given constant c > 0.

Remark III.4 Note that Theorem III.3 holds true not only for polytopic partitions of polytopes but also for cell complexes of nonconvex polyhedral sets in R d .

Remark III.5 According to Proposition II.4, if a polyhedral partition is convexly liftable, then it should be a cell complex. Therefore, the optimization problem ( 16) is infeasible for the polytopic partitions of polytopes whose facet-to-facet property is not fulfilled.

To illustrate Algorithm 2, a cell complex of a polytope is shown in Fig. 3. One of its convex liftings is also presented therein. Further, Fig. 4 depicts a cell complex of a nonconvex set which is the underlying partition. One of its convex liftings is also illustrated above.

C. Construction of convex lifting based on the halfspace representation

Recall that Algorithm 2 relies on the vertex representation of related polytopes. Note also that the pivoting algorithm by Avis and Fukuda in [START_REF] Avis | A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra[END_REF] can carry out the vertex enumeration in time O(ndv), where d denotes the dimension of the given polytope, v represents the number of vertices of this polytope and n denotes the number of facets of this polytope. However, the vertex enumeration is not necessary in many cases, particularly in control theory where the implementation of a state-space partition mostly relies on its halfspace representation. Moreover, the construction of convex liftings based on the vertex representation is limited to polytopic partitions, therefore, this construction for partitions of unbounded polyhedra may cause computational complications, see [START_REF]Inverse parametric linear/quadratic programming problem for continuous PWA functions defined on polyhedral partitions of polyhedra[END_REF]. Motivated by these limitations, this subsection presents an approach to construct convex liftings based on the halfspace representation.

Given a convexly liftable cell complex {X i } i∈I N of a polyhedron X ⊆ R d , as denoted in Definition II.3, we use

z(x) = a T i x + b i for x ∈ X i (20)
to denote a convex lifting for {X i } i∈I N . Since a convex lifting z(x) has to fulfill the continuity and convexity conditions, for any pair of neighboring regions (X i , X j ), the corresponding affine functions a T i x + b i and a T j x + b j have to satisfy:

a T i x + b i ≥ a T j x + b j for all x ∈ X i , (21a)
a T j x + b j ≥ a T i x + b i for all x ∈ X j . ( 21b
)
It can be easily observed that according to (21a) and (21b)

a T i x + b i = a T j x + b j for all x ∈ X i ∩ X j , (22)
implies the continuity of z(x) at any point x ∈ X i ∩ X j . Furthermore, given the halfspace representation of region X i , i.e., X i = x ∈ R d : R i x ≤ K i , (21a) holding for all x ∈ X i , leads to:

X i = x ∈ R d : R i x ≤ K i ⊆ P = x ∈ R d : (a j -a i ) T x ≤ b i -b j . (23)
According to the extended Farkas lemma [START_REF] Schrijver | Theory of linear and integer programming[END_REF], [START_REF] Johansson | The quadruple-tank process: a multivariable laboratory process with an adjustable zero[END_REF] leads to the existence of a suitable vector λ ij such that

λ ij ≥ 0, λ ij R i = (a j -a i ) T , λ ij K i ≤ b i -b j . (24)
Similarly, given the halfspace representation of region X j , i.e., X j = x ∈ R d : R j x ≤ K j , (21b) leads to the existence of a suitable vector λ ji such that

λ ji ≥ 0, λ ji R j = (a i -a j ) T , λ ji K j ≤ b j -b i . (25)
It should be emphasized that the constraints in ( 21) cannot guarantee that the affine functions corresponding to regions X i and X j are distinct, i.e., (a i , b i ) = (a j , b j ). Therefore, in order to ensure this property of a convex lifting, one needs to impose additional constraints. A simple way to avoid nonlinear constraints is to require

a T i x 0 + b i ≥ a T j x 0 + b j + c, (26)
for a given scalar constant c > 0 and x 0 ∈ int(X i ). Constraint ( 26) is meaningful to guarantee (a i , b i ) = (a j , b j ). In fact, if the converse situation happens, constraint (26) will be infeasible. Also, x 0 can be arbitrarily chosen as long as it lies in the interior of X i ; the Chebyshev center is also a possible candidate. Recall that Chebyshev center of a polyhedron X is the center of the largest inscribed ball of X . More precisely, finding Chebyshev center x c of polyhedron X amounts to solving the following problem max xc,r r s.t.

x c ∈ X , x ∈ R d : (x -x c ) T (x -x c ) ≤ r ⊆ X .
Note also that this problem can easily be transformed into a linear programming problem, see [START_REF] Boyd | Convex optimization[END_REF].

For completeness, a procedure to construct convex liftings based on the halfspace representation for a given convexly liftable cell complex is summarized in Algorithm 3.

Remark III.6 Note that Chebyshev center of a polyhedron may not always be unique or may lie at infinity. As emphasized above, other candidate of this point is possible as long as it lies in the interior of X i .

Remark III. [START_REF] Baotic | Efficient on-line computation of constrained optimal control[END_REF] We remark that for each pair of neighboring regions, two additional variables are added in the problem formulation, as shown in constraints ( 27), [START_REF] Nguyen | Explicit robust constrained control for linear systems: analysis, implementation and design based on optimization[END_REF]. Therefore, the number of additional variables, besides a i , b i , scales quadratically with the number of regions, since this number is bounded above by N (N -1).

Algorithm 3 Construction of a convex lifting for a given convexly liftable cell complex

{X i } i∈I N of a polyhedron X ⊆ R d . Input: {X i } i∈I N of a polyhedron X ⊆ R d , the halfspace representation of X i = x ∈ R d : R i x ≤ K i and a scalar constant c > 0.
Output: gains a i , b i .

1: Find Chebyshev center for each region X i , denoted by x i .

2: Register all pairs of neighboring regions in {X i } i∈I N . 3: For each pair of neighboring regions (X i , X j ), add the following constraints:

λ ij ≥ 0, λ ij R i = (a j -a i ) T , λ ij K i ≤ b i -b j ; ( 27
)
λ ji ≥ 0, λ ji R j = (a i -a j ) T , λ ji K j ≤ b j -b i ; ( 28
)
a T i x i + b i ≥ a T j x i + b j + c. ( 29
)
4: Solve the following convex optimization problem by minimizing a chosen cost function, e.g., 27), ( 28), ( 29). ( 30)

min ai,bi,λij ,λji N i=1 (a T i a i + b T i b i ) s.t. (
The following results present important formal properties of the construction in Algorithm 3.

Proposition III.8 If the optimization problem (30) is feasible, then the function z(x) = a T i x + b i for x ∈ X i represents a convex lifting for cell complex {X i } i∈I N .

Proof: If the optimization problem (30) is feasible, then the constraints ( 27), ( 28) and ( 29) are all feasible. According to the extended Farkas lemma [START_REF] Schrijver | Theory of linear and integer programming[END_REF], constraint (27) leads to:

a T i x + b i ≥ a T j x + b j for all x ∈ X i . (31)
Similarly, it follows from constraint (28) that

a T j x + b j ≥ a T i x + b i for all x ∈ X j . (32)
According to [START_REF] Nguyen | Any discontinuous PWA function is optimal solution to a parametric linear programming problem[END_REF] and [START_REF]Inverse parametric linear/quadratic programming problem for continuous PWA functions defined on polyhedral partitions of polyhedra[END_REF], the continuity of z(x) at the common boundary of X i and X j is verified by

a T i x + b i = a T j x + b j for all x ∈ X i ∩ X j .
This leads to the following inclusions for the vertices and the extreme rays of X i ∩ X j :

a T i v + b i = a T j v + b j for all v ∈ V(X i ∩ X j ), a T i r = a T j r for all r ∈ R(X i ∩ X j ). (33)
Moreover, constraint [START_REF] Nguyen | Fully inverse parametric linear/quadratic programming problems via convex liftings[END_REF] implies that

a T i x i + b i ≥ a T j x i + b j + c > a T j x i + b j . (34)
From ( 33) and [START_REF] Nguyen | On the lifting problems and their connections with piecewise affine control law design[END_REF], any point x, described in the following form:

x = γx i + v∈V(Xi∩Xj ) α(v)v + r∈R(Xi∩Xj ) µ(r)r with α(v), µ(r) ∈ R, γ + v∈V(Xi∩Xj ) α(v) = 1, satisfies: a T i x + b i > a T j x + b j for all γ > 0, (35a)
a T i x + b i = a T j x + b j for γ = 0. (35b)
In other words, any point x in the halfspace containing X i but not in aff(X i ∩ X j ) satisfies (35a). Otherwise, any point x ∈ aff(X i ∩ X j ) satisfies (35b).

The same inclusion holds for the other pairs of neighboring regions, leading to the fact that

a T i x + b i > a T j x + b j for all x ∈ X i \X j and j = i. ( 36
)
Therefore, function z(x) = a T i x + b i for x ∈ X i represents a convex lifting for {X i } i∈I N according to Definition II.3. Similar to Subsection III-B, any value of the given scalar c in Algorithm 3 does not affect the feasibility of the optimization problem [START_REF]Constructive solution to inverse parametric linear/quadratic programming problems via convex liftings[END_REF] as long as c > 0.

Theorem III.9 The given cell complex {X i } i∈I N of a polyhedron X ⊆ R d , is convexly liftable if and only if the optimization problem (30) is feasible for any constant c > 0.

Proof: ←-This inclusion directly follows according to Proposition III.8.

-→ If the given cell complex {X i } i∈I N is convexly liftable, then there exists a function z(x) = a T i x + b i for x ∈ X i such that for any pair of neighboring regions (X i , X j ), inclusions [START_REF] Nguyen | Any discontinuous PWA function is optimal solution to a parametric linear programming problem[END_REF] and ( 32) hold. Accordingly, the extended Farkas lemma leads to the existence of two suitable vectors λ ij , λ ji such that:

λ ij ≥ 0, λ ij R i + (a i -a j ) T = 0, λ ij K i ≤ b i -b j , (37a) λ ji ≥ 0, λ ji R j + (a j -a i ) T = 0, λ ji K j ≤ b j -b i , (37b)
where X i , X j are again given as

X i = x ∈ R d : R i x ≤ K i , X j = x ∈ R d : R j x ≤ K j .
Also, since z(x) is a convex lifting for {X i } i∈I N , there exists a constant c ij > 0 for each pair of neighboring regions (X i , X j ) such that

a T i x i + b i ≥ a T j x i + b j + c ij , (38)
where x i represents Chebyshev center of X i . Let c be the minimum value of c ij for the pairs of neighboring regions (X i , X j ), i.e.

c = min

(i,j)∈I 2 N | dim(Xi∩Xj )=d-1 c ij .
Accordingly, for any pair of neighboring regions (X i , X j ), we obtain:

a T i x i + b i ≥ a T j x i + b j + c.
By choosing δ = c/c > 0, it follows that

(δa i ) T x i + (δb i ) ≥ (δa j ) T x i + (δb j ) + c. (39)
According to (37a), (37b) and ( 39), it can be deduced that (δa i , δb i ) for all i ∈ I N make the constraints ( 27), ( 28) and ( 29) feasible, since δλ ij , δλ ji ≥ 0. In other words, the optimization problem ( 30) is feasible with any given constant c > 0.

Remark III.10 Note that according to Theorem III.9, the feasibility of the optimization problem (30) serves as another necessary and sufficient condition for the convex liftability of the polyhedral partitions of polyhedra.

Remark III.11 As proven in Proposition II.4, a polyhedral partition admitting a convex lifting should be a cell complex. Accordingly, for any polyhedral partition of polyhedron whose facet-to-facet property is not fulfilled, the optimization problem (30) is infeasible.

D. Convexly non-liftable partitions

This subsection addresses polyhedral partitions whose convex liftability is not fulfilled. This is usually the case in control theory, in particular for polyhedral partitions obtained from linear MPC problems with respect to quadratic cost functions. It is worth emphasizing that rearranging a given polyhedral partition is possible. However, any modification of the initial boundaries of the given polyhedral partition is not allowed due to the fact that it destroys the original structure of PWA controller. This may lead to the case where two different affine control laws are defined over the same region of state space. Therefore, the problem is formulated as follows: by preserving the internal boundaries, is it possible to refine a given polyhedral partition in order to recover the convex liftability property?

It will be proven that there exists at least one subdivision which can retrieve the convex liftability for a given polyhedral partition. The proof shows that the so-called hyperplane arrangement technique, defined as the decomposition of a space by a set of hyperplanes, can be used to perform this subdivision.

Theorem III.12 Given a convexly non-liftable polyhedral partition {X i } i∈I N of a polyhedron X ⊆ R d , there exists at least one subdivision preserving the internal boundaries of this partition, such that the new cell complex is convexly liftable.

The proof is referred to Appendix for reading ease. Remark III.13 Note that Theorem III.12 states the existence of a suitable refinement, while the proof points to a specific technique for the refinement. In a broader perspective, for a given polyhedral partition which does not admit a convex lifting, there exist multiple practical solutions for suitable refinements into a convexly liftable cell complex; hyperplane arrangement is only one of them. An alternative, fitting planar cell complexes into Voronoi diagrams, can be found in [START_REF] Aloupis | Fitting voronoi diagrams to planar tesselations[END_REF].

Returning to the hyperplane arrangement technique, an algorithm to carry out this decomposition is presented in Algorithm 4 for a given polyhedral partition.

To illustrate Algorithm 4, consider the cell complex in Fig. 5, the result is depicted in Fig. 6. Again, the convex liftability of this cell complex can be verified by the feasibility of problem ( 16) or [START_REF]Constructive solution to inverse parametric linear/quadratic programming problems via convex liftings[END_REF].

Algorithm 4 An algorithm to carry out the hyperplane arrangement technique for a given polyhedral partition.

Input: Convexly non-liftable partition Ω = {X i } i∈I N in R d . Output: Convexly liftable cell complex Ω = {Y j } j∈I M . 1: G = [ ] 2: For i = 1 : N 3: X i = {x : R i x ≤ K i } , G = [G; R i K i ] 4: End 5:
Remove redundant rows of matrix G. 6: For i = 1 : size(G, 1)

7: Ω = ∅ 8:
For j = 1 : |Ω| 9:

X j = {x : R j x ≤ K j } 10: Y (1) = x : R j G(i, 1 : d) x ≤ K j G(i, d + 1) 11: Y (2) = x : R j -G(i, 1 : d) x ≤ K j -G(i, d + 1) 12: If dim(Y (1) ) = d & dim(Y (2) ) < d then Ω ← Ω ∪ Y (1)

13:

Elseif dim(Y (1) (1) , Y (2) 15:

) < d & dim(Y (2) ) = d then Ω ← Ω ∪ Y (2) 14: Elseif dim(Y (1) ) = d & dim(Y (2) ) = d then Ω ← Ω ∪ Y

IV. APPLICATIONS OF CONVEX LIFTING IN CONTROL

This section aims to employ the convex lifting concept to facilitate the implementation of PWA control laws. Note that earlier studies in this subject can be found in [START_REF] Gulan | Implications of inverse parametric optimization in model predictive control[END_REF], [START_REF] Nguyen | Explicit robust constrained control for linear systems: analysis, implementation and design based on optimization[END_REF]. In control theory, since the performance of physical systems is always limited, the control signal is typically bounded [START_REF] Kvasnica | Complexity reduction of explicit model predictive control via separation[END_REF]. Therefore, without loss of generality, the constraints on current control variable denoted by u ∈ R du are assumed to be in the following form:

u min ≤ u ≤ u max .
For ease of presentation, we use u (i) to denote the i-th component of vector u. Given a PWA controller u(x), by an unsaturated region, we denote a region whose associated control law is not of componentwise saturation, i.e., u

(i) min < u (i) (x) < u (i)
max for at least one i ∈ I du and one x in this region. Furthermore, a saturated region implies a region corresponding to a componentwise saturated control law, i.e., either

u (i) (x) = u (i) min or u (i) (x) = u (i)
max for all i ∈ I du over this region. Accordingly, given a state-space partition, the unsaturated partition consists of the unsaturated regions. Such a partition may not be a partition of a polyhedron but of a nonconvex set. The developments of this section are motivated by two following observations:

• the complexity of state-space partitions is mainly due to the saturation [START_REF] Kvasnica | Clipping-based complexity reduction in explicit MPC[END_REF] and the boundaries between saturated regions of the same controller can thus be appropriately modified; • in many practical MPC setups, the unsaturated partition is convexly liftable [START_REF] Gulan | Implications of inverse parametric optimization in model predictive control[END_REF]. Note that the existence of unsaturated partition is the premise of works on complexity reduction in explicit MPC controllers, e.g., [START_REF] Kvasnica | Clipping-based complexity reduction in explicit MPC[END_REF], [START_REF] Kvasnica | Complexity reduction of explicit model predictive control via separation[END_REF]. For ease of presentation, the following assumptions are convenient for the next developments.

Assumption IV.1 The control input is a scalar variable, i.e., dim(u) = d u = 1.

Assumption IV.2

The unsaturated partition is a convexly liftable polytopic partition.

Assumption IV.3

The feasible region X is a polytope.

Assumption IV. [START_REF]Power diagrams: properties, algorithms and applications[END_REF] The given PWA control law is continuous.

Assumption IV.1 is not restrictive, since the development presented in the sequel can easily be extended to the multivariable case. Note also that even if the unsaturated partition is not convexly liftable, one can use Algorithm 4 to modify it into a convexly liftable cell complex. This is meaningful to avoid a complete hyperplane rearrangement of the original state-space partition. Therefore, Assumption IV.2 loses no generality of the proposed schemes. Also, Assumption IV.3 restricts our attention to polytopic partitions of the state space. This is not restrictive, since the construction can easily be extended to polyhedral partitions. Finally, we are exclusively interested in implementation of the continuous PWA controllers as presented in Assumption IV. [START_REF]Power diagrams: properties, algorithms and applications[END_REF].

Given a PWA controller

u(x) = H i x + G i for x ∈ X i , (40)
defined over a polytopic partition {X i } i∈I N of a polytope X ⊂ R d satisfying Assumptions IV.1, IV.2 and IV.4, let I uns ⊂ I N denote the index set such that {X i } i∈I uns represents the unsaturated partition of {X i } i∈I N and u(x). Also, we use uns (x) to denote a convex lifting for {X i } i∈I uns , i.e.,

uns (x) = (a uns i ) T x + b uns i for x ∈ X i , i ∈ I uns . ( 41
)
In order to use Algorithm 1, we need to construct a convex lifting, denoted by (x), which is defined over the whole feasible region X and coincides with uns (x) over {X i } i∈I uns .

To this end, two different constructions will be presented in the sequel; the first one aims to rearrange the saturated regions so as to reduce the number of regions and also to find a suitable convex lifting over the rearranged partition, while the second one incorporates the clipping technique within the convex lifting concept.

A. Construction based on convex lifting for the vertices of the feasible region X

The first construction aims to compute an appropriate height h * corresponding to the vertices of X . This height has to satisfy that the augmented vertices v T uns (v)

T for v ∈

i∈I uns V(X i ) and v T h * T for v ∈ V(X )\ i∈I uns V(X i ) form a convex lifting (x) over X such that (x) = uns (x) for x ∈ i∈I uns X i and (x) = h * for x ∈ V(X )\ i∈I uns V(X i ).
This construction is presented in Algorithm 5.

The following lemma represents the most important property of (x) resulted from Algorithm 5.

Lemma IV.5 (x) obtained from Algorithm 5 satisfies:

(x) = uns (x) for all x ∈ i∈I uns X i . Proof: Consider any point x T z T ∈ Π, defined in (43).
This point can be described as a convex combination of the Algorithm 5 Construction of a convex lifting over X ⊂ R d , coincident with uns (x) over the unsaturated partition {X i } i∈I uns .

Input: {X i } i∈I uns , uns (x) defined in ( 41), X and a given constant c > 0.

Output: h * , (x).

1: Solve the problem:

h * = min h h s.t. h ≥ c + (a uns i ) T v + b uns i , ∀i ∈ I uns , ∀ v ∈ V(X )\ i∈I uns V(X i ). ( 42
) 2: Construct the polytope Π Π 1 = v uns (v) : v ∈ i∈I uns V(X i ) ⊂ R d+1 , Π 2 = v h * : v ∈ V(X )\ i∈I uns V(X i ) ⊂ R d+1 , Π = conv (Π 1 ∪ Π 2 ) . ( 43
)
3: Solve the following parametric linear program:

(x) = arg min z z subject to x T z T ∈ Π. ( 44
)
points in Π 1 , Π 2 as follows:

α(v), β(v) ≥ 0, v∈ i∈I uns V(Xi) α(v) + v∈V(X )\ i∈I uns V(Xi) β(v) = 1, x T z T = v∈ i∈I V(Xi) α(v) v T uns (v) T + v∈V(X )\ i∈I uns V(Xi) β(v) v T h * T .
Denote also z(x) = max j∈I uns (a uns j ) T x+b uns j for x ∈ X . Clearly, z(x) = uns (x) for x ∈ i∈I uns X i and is known to be a convex function over X . According to [START_REF] Tøndel | Evaluation of piecewise affine control via binary search tree[END_REF], it follows that:

v∈ i∈I uns V(Xi) α(v) uns (v) + v∈V(X )\ i∈I uns V(Xi) β(v)h * ≥ v∈ i∈I uns V(Xi) α(v)z(v) + v∈V(X )\ i∈I uns V(Xi) β(v)(c + z(v)) ≥ z(x) + v∈V(X )\ i∈I uns V(Xi) β(v)c ≥ z(x).
If x ∈ X i for i ∈ I uns , then the equality only happens when

β(v) = 0 for v ∈ V(X )\ i∈I uns V(X i ).
In other words, when x ∈ i∈I uns X i the minimal cost function of (44) satisfies (x) = z(x) = uns (x).

Let {Y j } j∈I M denote the state-space partition associated with (x) obtained from Algorithm 5. The following corollary presents another property of such a function (x).

Corollary IV.6 (x) obtained from Algorithm 5, represents a convex lifting for the polytopic partition {Y j } j∈I M of the feasible region X .

Proof: The proof follows as a direct consequence of Lemma II.8. According to Lemma IV.5, for each region X i of the unsaturated partition {X i } i∈I uns , there exists a region Y j of {Y j } j∈I M such that Y j = X i . If I max ⊂ I N (I min ⊂ I N ) denotes the set of indices such that each region X j , j ∈ I max (j ∈ I min ) is associated with a saturated control action u(x) = u max (u(x) = u min ) for all x ∈ X j , then I N = I uns ∪ I max ∪ I min . Define the following controller, denoted by f pwa (x), associated with {Y j } j∈I M :

f pwa (x) =              u(x) if x ∈ Y j s.t. ∃i ∈ I uns , Y j = X i u max if x ∈ Y j s.t. Y j ⊂ i∈I max X i u min if x ∈ Y j s.t. Y j ⊂ i∈I min X i .
Note that the newly obtained PWA control law f pwa (x) is equivalent to the given one u(x) in the sense that f pwa (x) = u(x) for all x ∈ X . Therefore, it suffices to implement f pwa (x) as in Algorithm 1.

Remark IV.7 If the given PWA control law u(x) is of multiple inputs, then implementation of this controller according to the construction of convex liftings as in Algorithm 5 can be carried out componentwise. Roughly speaking, the implementation of u(x) can be summarized as follows:

• construct a convex lifting ( uns ) (i) (x) for the unsaturated partition, denoted by {X j } j∈I (i) , of the state-space partition {X j } j∈I N (I (i) ⊆ I N ) associated with the i-th component u (i) (x) of the given PWA controller u(x); • construct an extended convex lifting, denoted by (i) (x), defined over X for ( uns ) (i) (x) as in Algorithm 5; • rearrange each component u (i) (x) of the given PWA controller u(x) according to (i) (x); denote this rearranged component by ũ(i) (x); • implement each rearranged component ũ(i) (x) as in Algorithm 1. Note also that in this multiple-input case, the unsaturated partitions {X j } j∈I (i) of {X j } j∈I N associated with the components u (i) (x) of u(x) may not be identical.

B. Construction based on convex lifting and clipping

Although the construction of (x) in Algorithm 5 shows benefits in terms of efficient storage, the number of affine functions composing (x) may be still relatively large. We now present a more efficient construction that can considerably reduce the number of affine functions. This construction employs convex lifting and the concept of clipping presented in [START_REF] Kvasnica | Clipping-based complexity reduction in explicit MPC[END_REF].

As mentioned in the proof of Lemma IV.5, we can choose such a convex lifting (x) as follows:

(x) = max j∈I uns (a uns j ) T x + b uns j for x ∈ X . (45)
Obviously, this construction ensures that (x) = uns (x) for all x ∈ i∈I uns X i . Let {Y i } i∈I M denote the polytopic partition of X associated with the convex lifting (x) defined in (45). For ease of presentation, denote (x) as follows:

(x) = a T i x + b i for x ∈ Y i . (46)
According to the new state-space partition {Y i } i∈I M , a (nonequivalent) rearrangement of the given control law u(x), denoted by f pwa (x), is put forward as follows:

f pwa (x) = H i x + G i = H j x + G j for x ∈ Y i such that j ∈ I uns , X j ⊆ Y i . (47)
Note that determining the new partition {Y i } i∈I M in (46) requires solving a linear parametric program with the number of constraints equal to |I uns | = M and a 1-dimensional decision variable. Accordingly, the definition of f pwa (x) in (47) just involves set comparisons available, e.g., in MPT 3.0 [START_REF] Herceg | Multi-Parametric Toolbox 3.0[END_REF]. The following corollary represents a property of f pwa (x) given by (47).

Corollary IV.8 If u(x) defined in (40) is continuous, then f pwa (x) is continuous over i∈I uns X i .
Proof: It can be observed that f pwa (x) = u(x) over i∈I uns X i . Obviously, the proof directly follows. Note also that the continuity of f pwa (x) may not be guaranteed over X \ i∈I uns X i , as this property is not accounted for in the definition of f pwa (x) in (47). However, in implementation, f pwa (x) will be saturated over this region such that the given constraints are respected. The implementation is summarized in Algorithm 6.

Algorithm 6 Efficient implementation of PWA controllers based on convex lifting and clipping 1: Store (x) defined in (45), denoted as in (46) and the PWA controller f pwa (x) defined as in (47). 2: At each sampling time, obtain the current state x. 3: Find index i ∈ I M such that:

a T i x + b i = max j∈I M ( a T j x + b j ). 4: Evaluate the control law u * (x) =      H i x + G i if u min ≤ H i x + G i ≤ u max u max if H i x + G i > u max u min if H i x + G i < u min .
5: Return to step 2.

Note that by the saturation in Step 4, u * (x) is equivalent to the given PWA controller, i.e., u * (x) = u(x), see [START_REF] Gulan | Implications of inverse parametric optimization in model predictive control[END_REF], [START_REF] Kvasnica | Clipping-based complexity reduction in explicit MPC[END_REF].

Remark IV.9 Algorithm 6 can be easily extended to the multiple-input case. More precisely, unlike the implementation in Subsection IV-A, this implementation, based on convex lifting and clipping, only requires the construction of a single convex lifting for the unsaturated partition of {X i } i∈I N associated with u(x) instead of a convex lifting for each component of u(x). Accordingly, the given multiple-input u(x) can be implemented as in Algorithm 6 where Step 4 has to be modified to carry out the componentwise saturation. Namely, if d u denotes the dimension of u(x), then

u * (x) = (u * ) (1) (x) . . . (u * ) (du) (x) T ,
where (u * ) (j) (x) for j ∈ I du are defined as follows:

(u * ) (j) (x) =        H (j) i x + G (j) i if u (j) min ≤ H (j) i x + G (j) i ≤ u (j) max u (j) max if H (j) i x + G (j) i > u (j) max u (j) min if H (j) i x + G (j) i < u (j) min , and H (j)
i , G

min again denote the j-th row of matrices H i , G i , u max , u min .

C. Complexity analysis

In the following, we assess memory and runtime complexity of the proposed approaches in the context of implementation of PWA controllers. As a reference, the total memory consumed by the original PWA control law together with its underlying partition,

{X i } i∈I N , is N i=1 (c i + d u )(d + 1
) real numbers, where c i denotes the number of halfspaces defining the i-th region. On the other hand, storing the simpler controller obtained via Section IV-A and its associated control law requires M (1 + d u )(d + 1) real numbers, where M is the number of affine terms of the convex lifting, resulted from Algorithm 5. Finally, the memory footprint of the implementation proposed in Section IV-B amounts to |I uns |(1 + d u )(d + 1) + 2d u real numbers, where the second term denotes a negligible memory needed to encode the clipping function in Algorithm 6.

In addition, we quantify the necessary on-line computational effort. Specifically, the standard implementation of the original PWA control law via sequential search consists of the point location problem, i.e., finding index i of the region X i that contains x, and evaluation of the corresponding control law. In the worst case, this amounts to N i=1 c i (2d + 1) + 2d u d floating point operations (FLOPs). Note that the proposed implementations based on convex lifting may perform this task in a very efficient way, in particular the one described by Algorithm 6 exploiting clipping, without the need to carry out expensive point location. In total, it requires a constant number of 2|I uns |d+2d u d+2d u FLOPs, which is a significant reduction in runtime complexity, even if |I uns | = N was the case (typically

|I uns | N i=1 c i ).
It should be noted that all the above figures do not consider evaluating and storing the full optimizer as only its first element is required for implementation of PWA controllers in a receding horizon fashion.

In terms of complexity reduction in explicit MPC, one may compare the proposed convex lifting approach, e.g., with the clipping-based implementation of [START_REF] Kvasnica | Clipping-based complexity reduction in explicit MPC[END_REF] as they both exploit the concept of clipping. The latter, however, relies on replacing some of the saturated regions by extensions of the unsaturated ones, while the achievable reduction may range from none to the case when the new partition has |I uns | regions. Another technique of [START_REF] Kvasnica | Complexity reduction of explicit model predictive control via separation[END_REF] in turn requires to only store the unsaturated regions by employing a separating function. Clearly, both of the aforementioned approaches necessitate storing a modified state-space partition, and hence performing the point location at each sampling instant. Alternatively, a regionless implementation of explicit MPC was proposed in [START_REF] Borrelli | On the computation of linear model predictive control laws[END_REF], and recently extended in [START_REF] Kvasnica | On region-free explicit model predictive control[END_REF]. Its nature, however, renders it applicable for MPC problems with rather larger parametric space and short prediction horizons.

It is worth recalling that the technique presented in [START_REF] Baotic | Efficient on-line computation of constrained optimal control[END_REF] proposes for efficient implementation of PWA controllers the use of a so-called descriptor function for parametric quadratic programming and the optimal cost function for parametric linear programming, which enable to avoid storing the state-space partition. Therefore, its storage demand is N (1 + d u )(d + 1) real numbers which is much less than N i=1 (c i +d u )(d+1) real numbers required by the original implementation. However, it is usually the case that N (1+d u )(d+1)

|I uns |(1+d u )(d+ 1) + 2d u , since N |I uns |. Accordingly, the method in [START_REF] Baotic | Efficient on-line computation of constrained optimal control[END_REF] requires a larger memory footprint than the one by Algorithm 6. Moreover, the online implementation of the technique in [START_REF] Baotic | Efficient on-line computation of constrained optimal control[END_REF] requires (2d -1)N + N i=1 c i FLOPs in the worst case, which is much more demanding than the one by Algorithm 6 with

2|I uns |d + 2d u d + 2d u FLOPs since N i=1 c i N |I uns |.
On the other hand, the method in [START_REF] Bayat | Using hash tables to manage the time-storage complexity in a point location problem: Application to explicit model predictive control[END_REF] makes use of a hash table which allows for acceleration of the online evaluation, however, at the price of additional storage requirement besides the memory needed to store the state-space partition. Consequently, this method does not help reducing the memory footprint. For reading ease, a summary of these aspects is reported in Table II.

It is worth emphasizing that the method in [START_REF] Tøndel | Evaluation of piecewise affine control via binary search tree[END_REF] presents a construction of binary search trees which can achieve a logarithmic time for the point-location problem. However, the memory footprint requirement is still more demanding than the proposed method in Subsection IV-B, since in addition to the constructed binary search tree, it also requires to store all the unique hyperplanes of the state-space partition whose number is much larger than the number of unsaturated regions. To illustrate this point, in the example of Subsection V-A with N p = 20, the implementation presented in Subsection IV-B requires to store 73 hyperplanes, while the one in [START_REF] Tøndel | Evaluation of piecewise affine control via binary search tree[END_REF] needs to store 3270 hyperplanes besides a binary search tree of 5189 nodes. Combination of lattice representation of PWA functions and truncated binary search tree is introduced in [START_REF]Flexible piecewise function evaluation methods based on truncated binary search trees and lattice representation in explicit MPC[END_REF] to provide a better trade-off between the memory footprint requirement and the online evaluation over the method in [START_REF] Tøndel | Evaluation of piecewise affine control via binary search tree[END_REF]. For these elements, drawing a clear comparison between this method and the ones based on convex lifting is not straightforward.

Remark IV.10 We remark that the limited computational accuracy might practically lead to the case where several neighboring regions are associated with very similar affine functions of a convex lifting, if the scalar constant c > 0 chosen in [START_REF] Edelsbrunner | Voronoi diagrams and arrangements[END_REF] or ( 29) is too small. This case can be avoided by increasing c to a sufficiently large value, e.g., c should be greater than a tolerable error but not large in absolute value as long as it affects the slope of the respective affine functions.

In order to assess the scalability of the proposed implementations, one can see that it primarily depends on the tractability of the construction of convex liftings. As for the constructions of convex lifting in Algorithms 2 and 3, the number of constraints of the optimization problems ( 16) and (30) scales quadratically with the number of regions in the given partition. Therefore, the construction of convex liftings becomes more demanding, as the number of regions and dimension increase. However, since the construction of a convex lifting is performed offline, it is reasonable to assume that sufficient computational resources are available. In addition, one may choose among a plethora of efficient linear/quadratic programming solvers. Note also that the number of unsaturated regions is usually much smaller than the one of the original partition, i.e., |I uns | N, therefore we only need to work with partitions of much less regions. To this end, we refer the reader to Table I for illustration.

A. Example 1

To illustrate the above proposed schemes, let us consider a double integrator system given by:

x k+1 = 1 0.5 0 1 x k + 0.125 0.5 u k . (48)
We design a PWA controller based on linear model predictive control which minimizes the following quadratic cost function:

Np-1 i=0 x T k+i|k Qx k+i|k + u T k+i|k Ru k+i|k +x T k+Np|k P x k+Np|k ,
where Q = I 2 , (I denotes an identity matrix of suitable dimension), R = 10, P is set to be the solution of discretetime Riccati equation and the prediction horizon N p equal to 10. Note that x k+i|k , u k+i|k denote the state and control variables at time k + i, predicted at instant k. This problem is subject to the following constraints: where X f denotes the terminal constraint set as the maximal positively invariant set associated with the local control law u = -0.2554 -0.7590 x. The above problem is explicitly solved using MPT 3.0 [START_REF] Herceg | Multi-Parametric Toolbox 3.0[END_REF]. The resulting PWA controller is presented in Fig. 7 with the red and green controllers denoting where the control action attains the minimum and the maximum values, respectively. In particular, the corresponding state-space partition consists of 73 unsaturated regions, 160 regions where u(x) = -2 and 160 regions where u(x) = 2. Storing all the 393 regions in this case amounts to 4758 real numbers, with additional 1179 real numbers needed to encode the PWA control law. Assuming double precision arithmetics, the total memory footprint of the original MPC controller is 48 kilobytes. The worst-case computational effort required for its online evaluation is 7934 FLOPs.

-2 ≤ u k+i|k ≤ 2 for 0 ≤ i ≤ N p -1, x k+Np|k ∈ X f ,
Fig. 8 in turn depicts a convex lifting obtained from Algorithms 2 and 5. The associated state-space partition {Y j } j∈I M is shown only for illustration, where the red and green regions represent the rearrangement of the partitions {X i } i∈I min and {X i } i∈I max , respectively, according to the constructed convex lifting. The yellow regions represent {X i } i∈I uns , which does not change after the rearrangement. This regionless MPC implementation hence requires to only store the convex lifting and the corresponding PWA feedback, which in total amounts to 6.7 kB, implying a reduction by a factor of 7.2. Evaluating the optimal control action requires 559 FLOPs, which is 14.2 times less than in the case of the original explicit solution.

Finally, a convex lifting constructed per Algorithm 2 and equation ( 45) is depicted in Fig. 9. The total memory footprint of the resulting regionless controller is 3.5 kB, i.e., the memory consumption is reduced by a factor of 13.7. Accordingly, the online evaluation effort reduces to mere 298 FLOPs, which is 26.6 times faster than the worst-case runtime of the original controller.

To assess how the controller complexity in the considered MPC example scales with problem size, in particular with the prediction horizon, we report the related memory consumption data in Table III. The proposed approaches are also compared with the clipping and separation based MPC implementations of [START_REF] Kvasnica | Clipping-based complexity reduction in explicit MPC[END_REF] and [START_REF] Kvasnica | Complexity reduction of explicit model predictive control via separation[END_REF], respectively. One may observe the significant complexity reduction of explicit solutions achieved via the convex lifting based techniques (denoted by CL), in particular the latter one, described in Section IV-B. The online evaluation effort is omitted here for brevity, however, it scales better in favor of the convex lifting based approach as it does not perform the traditional point location (c.f. Section IV-C). This clearly allows for controller deployment even on low-end embedded microcontroller platforms with limited storage capacity and computational power. Similarly, the offline computational time is substantially lower for the proposed approach (1-2 s to obtain uns (x) for N p = 50). We remark that the approach is accordingly applicable for problems involving a higher number of parameters or optimization variables.

B. Example 2

In this subsection, we consider a higher-dimensional system to show more clearly the efficiency of the proposed algorithms. To this end, the quadruple tank system in [START_REF] Johansson | The quadruple-tank process: a multivariable laboratory process with an adjustable zero[END_REF] is accounted for and its mathematical model is represented as follows: The state and control variables are subject to the following constraints:

x k+1 = Ax k + Bu k ,
x k ∞ ≤ 20, u k ∞ ≤ 2.
An explicit MPC controller is computed by minimizing the same quadratic cost function as in Subsection V-A with Q = I 4 , R = I 2 , P is also obtained from the Riccati equation and N p = 20. For simplicity, terminal constraints are not considered in this example. Accordingly, one obtains a controller associated with 439 regions, 57 of which are unsaturated. The memory footprint and the online evaluation of different methods are reported in Table IV. This result again emphasizes the benefit of the convex lifting based approach in implementation of PWA controllers. Practical implementation of the proposed concept for real-time active vibration control using microcontroller hardware is also studied in [START_REF] Gulan | Embedded linear model predictive control for 8-bit microcontrollers via convex lifting[END_REF], the interested reader is referred to this reference for further detail.

VI. CONCLUSION

This paper presented the concept of convex lifting and its application in control theory. Accordingly, two different algorithms to construct convex liftings were put forward. This concept was also shown to be useful for efficient implementation of PWA controllers via two proposed schemes. They were shown to enable significant reduction of both the storage requirement and runtime complexity. Finally, a complexity analysis and numerical examples were considered to illustrate advantages of the proposed techniques compared to existing methods.

VII. ACKNOWLEDGMENT VIII. APPENDIX Proof of Theorem III.12 Let H(X i ) be the set of supporting hyperplanes of X i at its facets; also define H(X ) = i∈I N H(X i ). We will show that the decomposition of X by H(X ) leads to a new cell complex {Y j } j∈I M which is convexly liftable. As presented in Subsection III-D, such a decomposition is denoted as hyperplane arrangement. The convex liftability of such a decomposition can be proven by returning to the concept of stresses (details about stresses, star, inward unit normal vector and equilibrium can be found in [START_REF] Nguyen | Explicit robust constrained control for linear systems: analysis, implementation and design based on optimization[END_REF]).

We recall that the relative boundary of a cell complex {Y j } j∈I M of a polyhedron X is the boundary of X . An internal face of {Y j } j∈I M is a face which does not belong to its relative boundary. Considering any internal (d -2)-face F 0 of {Y j } j∈I M , this (d -2)-face F 0 is the intersection of finitely many hyperplanes in H(X ). If F (d-1) (F 0 ) denotes the set of all (d-1)-faces in the star of F 0 (i.e. the (d-1)-faces of {Y j } j∈I M sharing a common facet F 0 ), then for each F ).

Thus, a pair of coefficients of strictly positive stresses s(F )n(F 0 , F (d-1) j ) = 0.

Applying the same argument for all elements of F (d-1) (F 0 ), one can obtain a strictly positive d-stress such that F 0 is in equilibrium.

Fig. 2 :

 2 Fig. 2: Illustration of an affinely equivalent polyhedron.

Fig. 3 :

 3 Fig.3: A cell complex of a polytope and its convex lifting resulted from Algorithm 2.

Fig. 4 :

 4 Fig.4: A cell complex of a nonconvex polyhedral set and its convex lifting resulted from Algorithm 2.

Fig. 5 :

 5 Fig.5: A convexly non-liftable cell complex in R 2 .

Fig. 6 :

 6 Fig. 6: Cell complex resulted from Algorithm 4.

Fig. 7 :Fig. 8 :

 78 Fig. 7: The original PWA controller.

Fig. 9 :

 9 Fig.9: A convex lifting obtained from Algorithm 2 and equation (45) and its associated state-space partition.

  where matrices A, B are given below:

∈F

  (d-1) (F 0 ), there exists a unique F common hyperplane of H(X ) and they have a common facet F 0 . Accordingly, it can be seen that the inward unit normal vectors to the facesF (d-1) i , F (d-1) j at their common facet F 0 , denoted by n(F 0 , F (d-1) i ), n(F 0 , F (d-1) j ), respectively, satisfy: n(F 0 , F (d-1) i ) = -n(F 0 , F (d-1) j

TABLE I :

 I Computational time for the constructions of convex lifting via different numerical examples.

	d	du	N	|I uns |	Algo. 2 [s]	Algo. 3 [s]
			1089	99	0.49	0.40
	2	1	3640 5583	139 173	0.43 0.57	0.53 0.50
			5207	679	1.02	2.61
			591	115	0.77	0.71
	3	1	1887	223	2.49	1.49
			2845	377	5.75	3.13
			655	73	0.44	0.43
	4	2	437 1681	149 401	2.36 18.64	1.15 1.91
			1913	1425	1205.73	67.35
		1	57	37	0.45	0.32
			821	651	12.67	10.11
	5	2	963	729	24.12	15.47
			1382	901	86.41	16.26
		3	992	992	789.62	42.05
			V. ILLUSTRATIVE EXAMPLES

TABLE II :

 II Comparison of memory footprint and online evaluation effort of different methods Ñ denotes the number of regions of the modified partition and ci denotes the number of halfspaces of its i-th region, while |I uns | ≤ Ñ ≤ N in general.

	Method	Memory footprint [ # real numbers ]	Online evaluation [FLOPs]
	Original explicit solution	N i=1 (c i + du)(d + 1)	N i=1 c i (2d + 1) + 2dud
	Clipping-based approach [24]	i∈I Ñ (c i + du)(d + 1) a	2ddu + i∈I Ñ ci (2d + 1)
	Separation-based approach [25]	i∈I uns (c i + du)(d + 1)	2ddu + i∈I uns c i (2d + 1)
	CL-based approach per Sec. IV-B	|I uns |(1 + du)(d + 1) + 2du	2|I uns |d + 2dud + 2du
	Descriptor function [7]	|I N |(1 + du)(d + 1)	(2d -1)|I N | + N i=1 c i
	a

TABLE III :

 III Memory consumption in kilobytes for different implementations of the MPC example.

		Np = 20	30	40	50
	Original explicit solution	133.4	265.1	445.7	681.7
	Clipping-based approach [24]	49.6	95.3	242.8	401.9
	Separation-based approach [25]	12.1	14.5 a 17.0 a	21.1 a
	CL-based approach per Sec. IV-A	10.8	14.6	18.5	24.1
	CL-based approach per Sec. IV-B	4.8	5.7	6.7	8.3

a These figures were obtained from theoretical formulas since the computation failed in these cases.

TABLE IV :

 IV Comparison of different implementation methods.

		Memory	Online evaluation
	Methods	footprint [kB]	effort [FLOPs]
	Original explicit solution	167.6	30724
	Clipping-based approach [24]	26.6	5128
	CL-based approach per Sec. IV-B	6.7	476

M. Gulan is with Institute of Automation, Measurement and Applied Informatics, Faculty of Mechanical Engineering, Slovak University of Technology,

The authors would like to thank the Associate Editor and the anonymous Reviewers for their constructive and helpful comments.


R J Dikken

M Khajeh Salehani

Edge dislocation impingement on interfaces between dissimilar metals

Keywords: dislocation impingement, molecular dynamics, interfaces, defects, aluminum, nickel

In this work, the effect of material dissimilarity on the impingement behavior of a dislocation on the interface of a bi-crystal is investigated. To this end, impingement of a single edge dislocation on a Ni-Al interface is studied using molecular dynamics simulations. A dislocation is inserted in either aluminum or nickel and forced to impinge on the interface by an applied compressive load on the bi-crystal. We observe that the contact contains defects due to the lattice mismatch between the materials and hence, the dislocation may impinge on an interface defect or between two defects. Our results show that the dislocation is directly absorbed by the contact only if it impinges on an interface defect. Furthermore, it is demonstrated that dislocation transmission occurs only when it is initially in the Ni crystal. This is explained by looking at the energy of the core of a dislocation. Moreover, the importance of atomic vibrations is emphasized by performing the simulations at two temperatures 100 mK and 10 K.

I. INTRODUCTION

Plastic deformation of metals is dominantly due to glide of dislocations carrying plastic flow with an intrinsic length scale, the Burgers vector. When dislocations impinge on interfaces, like grain boundaries or contacts, several phenomena/mechanisms can occur, e.g. stagnation resulting in pile-up, absorption, transmission or renucleation [1][2][3]. Due to the large variety of variables involved, e.g. loading, temperature, crystal structure, dislocation type, relative crystal orientations, etc., it is rather difficult to predict which physical variable is dominant and which mechanism will prevail. However, both experimental [4] and computational [5][6][7][8][9][10][11] studies have shown that a critical role in the impingement behavior is played by the atomic structure of the interface.

A recent study has introduced a characterization of contacts, the atomic scale contact roughness [12]. This contact roughness depends simply on the ratio of the total number of interface atoms, i.e. atoms with different structure than atoms in the bulk, and the number of contact atoms (interface atoms which are in compressive mode) [13]. Interestingly, a clear correlation between the normal stress at which a dislocation nucleates from the interface and the contact roughness is found for different Al bi-crystals and disordered interfaces, while there is for instance no universal correlation between nucleation stress and interface energy [12,14]. Moreover, in Ref. [12] dislocation impingement on interfaces of Al bi-crystals is extensively studied and it is concluded that atomic scale contact roughness is pivotal in the impingement behavior. * R.J. Dikken@tudelft.nl In this work, the aim is to determine how the difference in material characteristics, i.e. two dissimilar metals, affects the impingement behavior of edge dislocations on interfaces. To this end, a dislocation is inserted in either aluminum or nickel, and forced to impinge on a Ni-Al interface by an applied compressive load on the bi-crystal.

This article is organized as follows. In Section II the computational approach is described. In Section III the results for impingement from both sides of a Ni-Al interface are presented. Section IV summarizes the conclusions of this study.

II. COMPUTATIONAL APPROACH AND PROBLEM FORMULATION

The simulations are performed with LAMMPS [15] using an EAM-potential [16] for nickel and aluminum that gives accurate surface and stacking fault energies, making it especially suitable to study the mechanical behavior of interfaces and dislocations [17]. Aluminum and nickel are very different in their mechanical properties. The Burgers vectors are 2.49 Å and 2.86 Å and the shear moduli are 76 GPa and 26 GPa for nickel and aluminum, respectively.

The materials studied in this work, nickel and aluminum, are chosen based on their relatively large stacking fault energy. The length of the stacking fault ribbon d SF that separates the partial dislocations of a dislocation in a FCC metal with shear modulus G and Burgers vector magnitude b is approximately proportional to the inverse of the stacking fault energy γ:

d SF ≈ Gb 2 4πγ . (1)
Therefore, the larger the stacking fault energy, the smaller the stacking fault ribbon length. This limits the required dimensions of the system that is modeled, which is computationally beneficial.

FIG. 1. Schematic representation of the system.

The system is periodic in the x-and y-direction (see Fig. 1). Both the nickel and aluminum crystals have the same crystal orientation, as shown in Fig. 1. The crystal orientation is chosen such that the system has symmetric slip systems with the (dislocation) slip line along the short periodic y-axis. The angle of the slip planes of the two slip systems with the x-axis is ±54.7 o . The y-direction, the direction parallel to the dislocation line, is taken short (L y = 2 nm), to model a pure edge dislocation which does not bow out. Hence, spurious image forces due to line bowing are avoided [18]. The simulation box dimensions are L x = 32 nm, L y = 2 nm and L z = 64 nm.

A dislocation is inserted, in either Ni or Al, through a prescribed displacement to atoms in the dark grey (hatched) region in Fig. 2. The value of displacement is b where the dislocation is inserted and zero at the bottom. This creates a surface step at the bottom of the crystal. Upon relaxation, a dislocation emerges that splits into two partial dislocations.

The dislocation is forced to move towards the interface by applying a compressive load to the bi-crystal. Eight atomic (x,y) planes at the top of the bi-crystal are displaced in the negative z-direction, while keeping eight atomic (x,y) planes at the bottom of the bi-crystal fixed in the z-direction. The loading is uniformly applied with a strain rate of 5 × 10 7 s -1 . The velocity of the load is about three orders of magnitude lower than the speed of sound in aluminum, so that setting off shock waves is avoided.

The pressure on the periodic boundaries is kept zero and the full system is thermalized to 100 mK (unless otherwise specified) using a Nosé-Hoover thermostat through a NPT ensemble in LAMMPS.

III. RESULTS

Because of the mismatch of the lattice parameter in aluminum and nickel the contact contains interface defects as shown in Fig. 3. The spacing of these defects is approximately five times the lattice parameter of aluminum. A dislocation can either impinge on an interface defect, or between two interface defects where the interface has a perfect FCC environment. Figure 4 shows the distance of the leading partial dislocation to the contact as a function of strain for both impingement on and in between defects, when the dislocation comes from the Al side of the contact. It is found that when the dislocation impinges on the defect, the distance to the contact becomes zero, indicating that the dislocation is absorbed by the contact. However, when the dislocation impinges in between defects, the dislocation stops at approximately 11 Å from the contact. Hence, only in the first case a step of size b emerges in the contact. Consequently, the additional step in the contact can have a large impact on the frictional behavior when the bi-crystal is sheared [19].

The number of atoms with HCP structure is a measure of dislocation in the crystal, since the atoms in the stacking fault ribbon are of HCP structure. In Fig. 5, the evolution of the number of HCP atoms as a function of strain, when the dislocation impinges on the contact from the Al side, is shown for both impingement on and in between interface defects. When the dislocation im- pinges on a defect, the stacking fault ribbon increases right before impingement, indicating an attractive interaction, and then decreases fast once it gets absorbed by the contact. On the other hand, when the dislocation impinges between defects, the sudden increase in number of HCP atoms is not found and as the dislocation impinges on the contact, the number of HCP atoms stays approximately constant. Eventually, the number of HCP atoms increases fast for both cases. This is due to the fact that dislocation nucleation occurs from other interface defects, at a normal stress of 3.4 GPa. A compressive test simulation without dislocation initially present in the bi-crystal shows that the nucleation stress for the same system without impingement is 3.5 GPa, only slightly higher than for the case with impingement. Hence, the nucleation stress is only minorly affected by the impingement of a single dislocation. This is in line with the observation for relatively rough contacts in Ref. [12].

The difference in the behavior of impingement on or in between defects can be explained by looking at the local normal stress σ zz , as shown in Fig. 6 and7. When a dislocation impinges on an interface defect, the normal stress field of the dislocation and the defect partially cancel each other. Inversely, when a dislocation impinges between defects the normal stress fields augment each other, which is not favorable. A different behavior is found when looking at the impingement behavior of a dislocation coming from the Ni side. Figures 8 and9 show the distance of the leading partial to the contact and the number of HCP atoms, respectively. The results show that when the dislocation impinges on or in between defects the leading partial dislocation is directly nucleated into the aluminum (red and blue curve). However, once the leading partial is nucleated, the dislocation is pinned by the contact. Only for the case in which the dislocation impinges on a defect, the dislocation is eventually depinned and moves away in the Al from the contact. To assess how realistic this is, we increase the temperature to 10 K. It is observed that the full extended dislocation is directly transmitted into the aluminum [20]. This emphasizes the importance of atomic vibrations for plasticity and also shows that quantum effects, like zero point fluctuations, are expected to be important for plasticity at low temperatures as shown in Ref. [START_REF] Proville | [END_REF]. Proville et al. [START_REF] Proville | [END_REF] show that for approximately T < 0.5T D , where T D is the Debye temperature, quantum corrections have to be applied to classical calculations to account for zero point fluctuations. This means that results of classical molecular dynamics at low temperature in the context of plasticity have to be treated with care. In conclusion, it is observed that if a dislocation impinges on the contact coming from the aluminum crystal, the Burgers vector is not transmitted into the nickel crystal. However, if the dislocation impinges on the contact coming from the nickel crystal, the Burgers vector is transmitted into the aluminum crystal. Since the Burgers vector of nickel is smaller than the Burgers vector of aluminum, there is a residual Burgers vector in the contact of 13 % of the Burgers vector in aluminum. In general, the residual Burgers vector should be small in order to have slip transmission [1]. However, a residual Burgers vector of 0.13b Al is significant and still slip trans- mission is observed. This can be explained by looking at the energetics of a dislocation. The energy of the core of a dislocation is proportional to the shear modulus and the Burgers vector squared,

E d ∝ Gb 2 . (2)
Substituting the values for shear modulus and Burgers vector in Eq. 2 shows that the energy of a dislocation is more than 2 times higher in nickel compared to aluminum and thus the total energy of the system is lower when the dislocation is in the Al crystal instead of the Ni crystal.

IV. CONCLUSION

This work provides additional insight into the impingement behavior of a dislocation on interfaces between dissimilar metals. Specifically, the impingement behavior of a single edge dislocation on a Ni-Al interface is studied using molecular dynamics simulations. Due to the lattice mismatch between the two materials, two cases arise, one where a dislocation impinges on an interface defect and one where a dislocation impinges between interface defects.

Dislocation transmission is only observed when the dislocation is initially in the material with higher elastic moduli, Ni in our case. The elastic strain energy decreases when the dislocation enters the material with lower elastic moduli, which makes the transmission energetically favorable. At realistic temperatures, a dislocation is always expected to be transmitted if the elastic moduli of the second body are lower and there is an appropriate slip system available. On the other hand, when the dislocation impinges while coming from the material with lower elastic moduli, transmission does not occur and the dislocation is directly absorbed if it impinges on an interface defect. However, if it impinges between defects, it is observed that the augmentation of the stress fields of the interface and the dislocation prevents direct absorption. The absorption of the impinged dislocation is expected to have a large impact on the frictional behavior of the contact in a subsequent sliding process.

Although this work gives a fundamental idea about dislocation impingement behavior on interface between dissimilar metals, a full and comprehensive study involving multiple materials, crystal orientations and temperatures is essential for further development and design of high-end material systems.

FIG. 2 .

 2 FIG. 2. Schematic representation of the dislocation insertion in either nickel or aluminum.

FIG. 3 .

 3 FIG. 3. The contact between Al and Ni showing interface defects.

FIG. 4 .

 4 FIG. 4. Distance of the dislocation from the contact for the impingement of a dislocation coming from the Al side of the contact on and in between interface defects (Al → Ni).

FIG. 5 .

 5 FIG. 5. The number of HCP atoms for the impingement of a dislocation coming from the Al side of the contact on and in between interface defects (Al → Ni).

FIG. 6 .

 6 FIG.6. The normal stress σzz contour right before impingement on an interface defect.

FIG. 8 .

 8 FIG. 8. Distance of the dislocation from the contact for the impingement of a dislocation coming from the Ni side of the contact on and in between interface defects (Ni → Al).

FIG. 9 .

 9 FIG. 9. The number of HCP atoms for the impingement of a dislocation coming from the Ni side of the contact on and in between interface defects (Ni → Al).