Ngocanh A Nguyen

Sorin Olaru

P Rodriguez-Ayerbe

Pedro Rodriguez

Any discontinuous PWA function is optimal solution to a parametric linear programming problem

Recent studies have investigated the continuous functions in terms of inverse optimality. The continuity is a primordial structural property which is exploited in order to link a given piecewise affine (PWA) function to an optimization problem. The aim of this work is to deepen the study of the PWA functions in the inverse optimality context and specifically deal with the presence of discontinuities. First, it will be shown that a solution to the inverse optimality problem exists via a constructive argument. The loss of continuity will have an implication on the structure of the optimization problem which, albeit convex, turns to have a set-valued optimal solution. As a consequence, the original PWA function will represent an optimal solution but the uniqueness is lost. From the numerical point of view, we introduce an algorithm to construct an optimization problem that admits a given discontinuous PWA function as an optimal solution. This construction is shown to rely on convex liftings. A numerical example is considered to illustrate the proposal.

I. INTRODUCTION

Piecewise affine (PWA) functions have been shown to provide relevance in control design through many studies e.g. [START_REF] Bemporad | The explicit linear quadratic regulator for constrained systems[END_REF], [START_REF] Johansen | On multi-parametric nonlinear programming and explicit nonlinear model predictive control[END_REF], [START_REF] Seron | Characterisation of receding horizon control for constrained linear systems[END_REF], [START_REF]Approximate explicit receding horizon control of constrained nonlinear systems[END_REF], [START_REF] Pistikopoulos | Multi-parametric programming[END_REF], [START_REF] Bemporad | An algorithm for approximate multiparametric convex programming[END_REF], [START_REF] Olaru | A parameterized polyhedra approach for explicit constrained predictive control[END_REF], [START_REF] Pistikopoulos | Perspectives in multiparametric programming and explicit model predictive control[END_REF], [START_REF] Grancharova | Explicit Nonlinear Model Predictive Control[END_REF]. It is known that from the practical point of view, PWA control law has two major limitations in terms of implementation once the number of regions in the state space becomes large:

• it requires substantial memory to store the state space partition and the associated control law gains, • the point-location problem, determining to which region the current state belongs, becomes more expensive. Due to the above limitations, many studies have been focused on the complexity reduction of PWA control laws e.g. [START_REF] Kvasnica | Complexity reduction of explicit model predictive control via separation[END_REF], [START_REF] Kvasnica | Clipping-based complexity reduction in explicit mpc[END_REF], [START_REF] Nguyen | Constrained Control of Uncertain, Time-Varying, Discrete-Time Systems: An Interpolation-Based Approach[END_REF], [START_REF] Gulan | Implications of inverse parametric optimization in model predictive control[END_REF]. Recently, inverse parametric convex programming problem has received an increasing attention in control community as a promising approach to realize this purpose. It is shown in [START_REF] Baes | Every continuous nonlinear control system can be obtained by parametric convex programming[END_REF] that any continuous nonlinear function is obtainable through a parametric convex programming problem without any hint for the construction of such an inverse optimality problem. Subsequently, some recent studies focus on the recovery of continuous PWA functions defined over polyhedral partitions via the decomposition into the difference of two convex functions as in [START_REF] Hempel | Every continuous piecewise affine function can be obtained by solving a parametric linear program[END_REF], or via convex liftings as in [START_REF] Nguyen | Inverse parametric convex programming problems via convex liftings[END_REF], [START_REF]On the lifting problems and their connections with piecewise affine control law design[END_REF]. As emphasized, all these studies focus on the continuous PWA functions, and the present study aims to compensate the lack of interest for the discontinuous PWA functions by investigating the inverse optimality. Note also that due to the continuity of the given PWA function, the optimal solution to inverse optimality formulation is unique. However, the uniqueness may no longer be preserved for discontinuous PWA functions. Therefore, finding an optimization problem, whose optimal solution is unique and equivalent to the given discontinuous PWA function, may render this optimization problem nonlinear (non-convex) at least from the point of view of the cost function.

Motivated from the above discussion, in this paper, we restrict our effort to show how to construct a convex optimization problem that admits the given discontinuous PWA function as an optimal solution at the price of non-unicity. Note also that the equivalence between PWA functions is understood in the sense that the boundary between two neighboring regions sharing the same affine function, can be adjusted (subdivided). This optimization problem will be shown to be of parametric linear programming type.

II. PROBLEM FORMULATION

A. Generalities and basic notions

Throughout the paper, R, R + , N, N >0 denote the field of real numbers, the set of non-negative real numbers, the set of nonnegative integers and the positive integer set, respectively. The following index set is also defined, for ease of presentation, with respect to a given N ∈ N >0 :

I N = {i ∈ N >0 | i ≤ N }.
Given a finite set S := {s 1 , . . . , s L }, then Card(S) denotes the cardinal number of S, i.e. Card(S) = L. conv(X ) denotes the convex hull of X . Moreover, if R is a set of vectors, by cone(R), we denote the cone which has elements of R as its extreme rays.

A polyhedron is defined as the intersection of a finite number of halfspaces. A polytope is defined as a bounded polyhedron. Given a full dimensional polyhedron P ⊂ R d , then V(P ) denotes the set of its vertices, and R(P ) denotes the set of its extreme rays. We use k-face to denote a face of dimension k of P . A 0-face is also called a vertex, an 1-face is alternatively called an edge, a (d -1)-face amounts to a facet. Also, F(P ) denotes the set of facets of P . Furthermore, by int(S), we denote the interior of a full dimensional set S. If S is a vector space, and S is an arbitrary set, then Proj S S represents the orthogonal projection of the set S onto the space S. Also, we use dim(S) to denote the dimension of the affine hull of S.

Given two full dimensional sets P 1 , P 2 ⊂ R d , then the Minkowski sum of these two sets, denoted by P 1 ⊕ P 2 , is defined as follows:

P 1 ⊕ P 2 = y ∈ R d | ∃x 1 ∈ P 1 , x 2 ∈ P 2 , y = x 1 + x 2 .
The following definitions represent extensions of the ones introduced in [START_REF]On the lifting problems and their connections with piecewise affine control law design[END_REF], [START_REF] Nguyen | Inverse parametric convex programming problems via convex liftings[END_REF], [START_REF]On the complexity of the convex liftings-based solution to inverse parametric convex programming problems[END_REF].

Definition 1: A collection of N ∈ N >0 full-dimensional polyhedra X i ⊂ R d 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 , Also, (X i , X j ) are called neighbours if (i, j) ∈ I 2 N , i = j and dim(X i ∩ X j ) = d -1.
The notion of cell complex was presented by Grünbaum in [START_REF] Grünbaum | Convex polytopes[END_REF]. For simplicity, a cell complex can be understood as a polyhedral partition whose facet-to-facet property is fulfilled i.e. any pair of neighboring regions share a common facet.

For ease of presentation, a slight abuse of notation is used in the remainder of this paper: X denotes simultaneously a polyhedral partition/cell complex of a polyhedron and this polyhedron itself. Its meaning will be clear from the context.

Note that a PWA function f pwa (x) : R d → R n defined over a polyhedral partition X = i∈I N X i ⊆ R d , can be described as follows:

f pwa (x) = h i x + g i for x ∈ X i .
With respect to Definition 1, a PWA function is continuous as long as for any neighboring regions (X i , X j ),

h i x + g i = h j x + g j , ∀x ∈ X i ∩ X j .
Otherwise, if f pwa (x) is discontinuous, this discontinuity happens at frontiers between neighboring regions. Thus, such a discontinuous function f pwa (x) can be defined as follows:

f pwa (x) = h i x + g i for x ∈ int(X i ), h i x + g i or h j x + g j for x ∈ X i ∩ X j ,
for every pair of neighboring regions (X i , X j ). An alternative way to deal with the discontinuities is to allow multiple values in the codomain R n for a given point x. In this case, we are not dealing anymore with a function but a set-valued map. Definition 2: For a given polyhedral partition X = i∈I N X i ⊆ R d , a piecewise affine lifting is described by a real-valued function z : X → R with:

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

a i ∈ R d , b i ∈ R, ∀i ∈ I N . Definition 3: Given a polyhedral partition X = i∈I N X i ⊆ R d , a piecewise affine lifting z(x) = a i x + b i ∀x ∈ X i , is called convex piecewise affine lifting if the following conditions hold true: • z(x) is continuous over X , • for each i ∈ I N , z(x) > a j x + b j for all x ∈ X i \X j
and all j = i, j ∈ I N . For ease of presentation, a convex piecewise affine lifting is called, throughout the rest of this paper, convex lifting. It is shown in [START_REF] Rybnikov | Polyhedral partitions and stresses[END_REF], [START_REF]Recognition of additively weighted voronoi diagrams and weighted delaunay decompositions[END_REF] that a polyhedral partition which admits a convex lifting, is a cell complex. Therefore, a convex lifting is always defined over a cell complex instead of a polyhedral partition.

As discussed above, a given polyhedral partition has to fulfill some conditions for the existence of a convex lifting. A summary of these conditions can be found in [START_REF] Rybnikov | Polyhedral partitions and stresses[END_REF], [START_REF]On the lifting problems and their connections with piecewise affine control law design[END_REF].

Definition 4: A given cell complex X = i∈I N X i ⊆ 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 .

B. Problem formulation

As mentioned above, the solutions to inverse parametric linear/quadratic programming problems in [START_REF] Hempel | Every continuous piecewise affine function can be obtained by solving a parametric linear program[END_REF], [START_REF]On the lifting problems and their connections with piecewise affine control law design[END_REF], [START_REF] Nguyen | Inverse parametric convex programming problems via convex liftings[END_REF] are known to only recover continuous PWA functions and to exclude the class of discontinuous PWA functions. This paper concentrates on inverse optimality for the latter class of functions and shows that it can be obtained via convex liftings. This problem can be stated as follows: Problem statement: Let a polyhedral partition of a polyhedron X = i∈I N X i ⊆ R dx , and a discontinuous PWA function:

f pwa (•) : X → R du . The goal is to determine J(x, z, u), H x , H u , H z , K such that:    f pwa (x) ∈ Proj R du arg min [z u T ] T J(x, z, u), s.t: H x x + H z z + H u u ≤ K. (2)
The following assumption is necessary for guaranteeing a well-posed problem.

Assumption 1: Polyhedral partition X is convexly liftable. Note that Assumption 1 is not restrictive, in view of Theorem IV.2 in [START_REF]On the lifting problems and their connections with piecewise affine control law design[END_REF]. This theorem is recalled here for completeness.

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

In virtue of this result, if a given polyhedral partition is not convexly liftable, one can subdivide it into a convexly liftable partition such that the internal boundaries are maintained. This new partition is equivalent to the initial one. Therefore, we can focus on convexly liftable partitions throughout the rest of this paper.

Note that this result holds true not only for polytopic partitions (bounded polyhedral partitions) as shown in [START_REF]On the lifting problems and their connections with piecewise affine control law design[END_REF] but also for polyhedral partitions of a polyhedron. The proof is similar to the one presented therein and is omitted for brevity.

III. CONSTRUCTIVE SOLUTION

A. Parametric linear programming

Constructive solution to inverse optimality problem in this paper is based on convex liftings. It is worth mentioning that the algorithm to construct convex liftings, put forward in [START_REF]On the lifting problems and their connections with piecewise affine control law design[END_REF], is not directly applicable for polyhedral partition of polyhedra, since this algorithm is based on the constraints imposed at related vertices. An extension to convex liftings for polyhedral partitions of a polyhedron is referred to [START_REF] Nguyen | Inverse parametric linear/quadratic programming problem for continuous pwa functions defined on polyhedral partitions of polyhedra[END_REF]. Based on the above necessary condition, we can state the main result of this paper.

We consider a cell complex of a polyhedron X = i∈I N X i ⊆ R dx satisfying Assumption 1 and a possibly discontinuous PWA function f pwa (•) : X → R du defined as follows:

f pwa (x) = h i x + g i for x ∈ int(X i ), h i x + g i or h j x + g j for x ∈ X i ∩ X j , (3)
where (X i , X j ) are neighbors. We use (x) to denote a convex lifting of this cell complex, i.e.

(x) = a i x + b i , for x ∈ X i . (4)
Also, by f

(i)
pwa (x), we denote the i th component of the function f pwa (x) at x for i ∈ I du . The following sets are defined:

V x = i∈I N V(X i ), R x = i∈I N R(X i ), f (i) pwa (x) = max j∈I N |x∈Xj h (i) j x + g (i) j , f (i) pwa (x) = min j∈I N |x∈Xj h (i) j x + g (i) j . (5)
Note that f

(i) pwa (x) f (i) pwa (x)
is defined as the maximal (minimal) value among the values of the i th component of the affine functions composing f pwa (x) at x, defined over the regions which contain x.

U(x) =         u (1) (x)
. . .

u (du) (x)    u (i) (x) ∈ f (i) pwa (x), f (i) pwa (x)      , V [x T z u T ] T =      x (x) u(x)   x ∈ V x , u(x) ∈ U(x)    , R [x T z u T ] T =        r (r) h(r)   r ∈ R x , (r) = a i r h(r) = h i r if r ∈ R(X i )      , Π v = conv(V [x T z u T ] T ), Π r = cone(R [x T z u T ] T ), Π = Π v ⊕ Π r . ( 6
) Note that V [x T z u T ] T R [x T z u T ]
T represents the set of extended vertices (extreme rays) of the partition X in the augmented space. Also from the above construction, if for a given x ∈ X , we have f (i) pwa (x) = f (i) pwa (x) for all i ∈ I du , then the function f pwa (x) is continuous at x. In this case, Card(U(x)) = 1. The following observation is useful for the next development.

Proposition 3.1: For any x ∈ X and U(x) defined in (6), U(x) = V(conv(U(x))).

Proof: Suppose V(conv(U(x))) ⊂ U(x), then there exists a point u 0 (x) ∈ U(x) for a given x ∈ X such that u 0 (x) can be described via a convex combination of the other points u(x) ∈ U(x), u(x) = u 0 (x), then

u 0 (x) = u(x) =u0(x), u(x)∈U(x) α(u(x))u(x), α(u(x)) ≥ 0, u(x) =u0(x), u(x)∈U(x) α(u(x)) = 1. (7)
We need to find a contradiction. Indeed, u

(1) 0 (x) takes value in the discrete set f

(1) pwa (x), f (1) pwa (x) , and any of these two values cannot be described by a convex combination of the other one if they are different. Thus, u

(1)

0 (x) = u(x) =u0(x), u(x)∈U(x) α(u(x))u (1) (x) holds true if u (1) (x) = u (1) 0 (x), meaning: u(x) =u0(x),u(x)∈U(x),u (1) (x)=u (1) 0 (x) α(u(x)) = 1, α(u(x)) = 0 for u (1) (x) = u (1) 0 (x).
The same argument, applied for the other components u

(i) 0 (x), i ∈ I du , leads to: α(u(x)) = 1, for u(x) = u 0 (x), α(u(x)) = 0, for u(x) = u 0 (x).
This inclusion is clearly contradictory with [START_REF] Hempel | Every continuous piecewise affine function can be obtained by solving a parametric linear program[END_REF]. Proposition 3.2:

V [x T z u T ] T = V(Π v ).
Proof: Suppose there exists a point of V [x T z u T ] T , denoted by x T (x) u T 0 (x) T , which can be described via a convex combination of the other points in this set. Formally, this leads to the following relationship:

  x (x) u 0 (x)   =   v (v) u(v)   =   x (x) u 0 (x)   ,   v (v) u(v)   ∈ V [x T z u T ] T α     v (v) u(v)       v (v) u(v)   , (8) where α     v (v) u(v)     ≥ 0,   v (v) u(v)   =   x (x) u 0 (x)     v (v) u(v)   ∈ V [x T z u T ] T α     v (v) u(v)     = 1.
Due to the fact that any x T (x)

T , x ∈ V x , cannot be described via a convex combination of the other

v T (v) T , v = x, v ∈ V x , then relation (8) only holds true for v = x, leading to α     v (v) u(v)     = 0 for v = x.
The remaining coefficients only depend on u(x), therefore for ease of presentation, we denote the remaining coefficients by α(u(x)) instead of α

    x (x) u(x)     .
To complete the proof, we need to show that

u 0 (x) = u(x) =u0(x), u(x)∈U(x) α(u(x))u(x), α(u(x)) ≥ 0, u(x) =u0(x), u(x)∈U(x) α(u(x)) = 1, (9)
leads to a contradiction. This end is easily deduced from Proposition 3.1 and the proof is complete. Based on the above inclusions, the main result of the paper is presented below.

Theorem 3.3: Any possibly discontinuous PWA function (3) defined over a partition of a polyhedron satisfying Assumption 1, is the image via the orthogonal projection onto R du of an optimal solution to the following optimization problem:

min [z u T ] T z s.t. x T z u T T ∈ Π, ( 10
)
where Π is defined as in [START_REF] Gulan | Implications of inverse parametric optimization in model predictive control[END_REF].

Proof: Given a point x ∈ X i in the cell complex X , due to the Minkowski-Weyl theorem (see Corollary 7.1b in [START_REF] Schrijver | Theory of linear and integer programming[END_REF]), x can be written as a convex combination as follows:

x = v∈V(Xi) α(v)v + r∈R(Xi) β(r)r,
where α(v), β(r) ≥ 0, v∈V(Xi) α(v) = 1. Due to Assumption 1, let (x) denote a convex lifting of the cell complex X , i.e. (x) = a i x + b i for x ∈ X i . For an x ∈ X i , it follows that:

(x) = a i x + b i = v∈V(Xi) α(v)(a i v + b i ) + r∈R(Xi) β(r) a i r.
Thus, if we define the following sets:

V [x T z] T = x (x) | x ∈ V x , R [x T z] T = r (r) | r ∈ R x , (r) = a i r if r ∈ R(X i ) , then Π [x T z] T = conv(V [x T z] T ) ⊕ cone(R [x T z] T
) is an affinely equivalent polyhedron of the cell complex X . Following the definition of an affinely equivalent polyhedron, for a region X i in the given cell complex X , there exists a lower facet of Π

[x T z] T , denoted by F [x T z] T such that Proj R dx F [x T z] T = X i
and the optimal solution to the following optimization problem:

min z z s.t. x T z T ∈ Π [x T z] T , falls in F [x T z] T for x ∈ X i .
Note however that, due to the construction in ( 6), every d x -face, denoted by F # and defined as follows: [START_REF] Kvasnica | Complexity reduction of explicit model predictive control via separation[END_REF] satisfies: Proj R dx +1 F # = F [x T z] T . Also, consider a point x ∈ X i , optimizer of the optimization problem (10) at x, locates on such a d x -face F # . Due to this non-uniqueness, we can choose the following d x -face, denoted by F , defined as in [START_REF] Kvasnica | Complexity reduction of explicit model predictive control via separation[END_REF] with u(v) = h i v + g i for v ∈ X i . Then, for any x ∈ X i , the optimizer, located on F , satisfies:

F # = F # 1 ⊕ F # 2 , F # 1 = conv v T (v) u T (v) T | v ∈ V(X i ) , F # 2 = cone r T a i r (h i r) T T | r ∈ R(X i ) , u(v) ∈ conv(U(v)),
  x z * (x) u * (x)   = v∈V(Xi) α(v)   v (v) h i v + g i   + r∈R(Xi) β(r)   r a i r h i r   , meaning u * (x) = h i x + g i = f pwa (x).
Remark 1: Note that one can easily fix a large enough box in R du to bound every U(x), ∀x ∈ V x . Such a constraint can avoid the computation of U(x) at each vertex of the cell complex X . However, such a choice ignores the structure of the given PWA function and cannot exploit its continuity property whenever this exists. Algorithm 1 summarizes the construction presented above.

Algorithm 1 Constructive solution to inverse optimality problem for discontinuous PWA functions

Input: A discontinuous PWA function (3), i.e. f pwa (x) defined over convexly liftable cell complex X . Output: H x , H u , H z , K, J(x, z, u).

1: Compute a convex lifting (x) of the cell complex X . 2: Construct a constraint set Π as in [START_REF] Gulan | Implications of inverse parametric optimization in model predictive control[END_REF]. 3: Define J(x, z, u) = z. 4: Solve the following parametric linear programming problem:

min [z u T ] T z s.t.
x T z u T T ∈ Π.

B. Connections to parametric quadratic programming

Similar to the above construction, a simple extension from parametric linear programming to a parametric quadratic programming problem is introduced below.

Theorem 3.4: Given a possibly discontinuous PWA function (3) defined over a partition of a polyhedron satisfying Assumption 1, one of its associated convex lifting (4), let σ(x) be a function σ(x) ≤ (x) for x ∈ X . The given PWA function [START_REF] Bemporad | The explicit linear quadratic regulator for constrained systems[END_REF] is the image via the orthogonal projection onto R du of an optimal solution to the following parametric quadratic programming problem:

min [z u T ] T (z -σ(x)) 2 s.t. x T z u T T ∈ Π, (12)
where Π is defined as in [START_REF] Gulan | Implications of inverse parametric optimization in model predictive control[END_REF].

Proof: Due to the assumption that σ(x) ≤ (x) for x ∈ X , the optimization problem [START_REF] Nguyen | Constrained Control of Uncertain, Time-Varying, Discrete-Time Systems: An Interpolation-Based Approach[END_REF] amounts to the minimization of z subject to the same constraints. Therefore, by Theorem 3.3, f pwa (x) is a sub-component of an optimal solution to problem [START_REF] Nguyen | Constrained Control of Uncertain, Time-Varying, Discrete-Time Systems: An Interpolation-Based Approach[END_REF]. The proof is complete. To conclude the analysis of piecewise affine functions and their inverse optimality, the following theorem presents the main message of the paper.

Theorem 3.5: Any possibly discontinuous PWA function, defined over a polyhedral partition of a polyhedron, can be equivalently obtained as a selection among the optimal solutions of a parametric linear/quadratic programming problem.

Proof: Let f pwa (x) denote a given PWA function, defined over a polyhedral partition X . If the partition X is convexly liftable, Theorems 3.3, 3.4 show in a constructive manner parametric linear/quadratic programming problems for which f pwa (x) is a sub-component of an optimal solution.

Otherwise, if X is not convexly liftable, as per Theorem 2.1, one can subdivide X into a convexly liftable cell complex such that the internal boundaries are maintained. According to this new cell complex, f pwa (x) is also subdivided into an equivalent PWA function, say f pwa (x). Note also that this equivalent function f pwa (x) is defined over a convexly liftable partition. Again, according to Theorems 3.3, 3.4, f pwa (x) can be obtained via parametric linear/quadratic programming problems.

IV. NUMERICAL EXAMPLE

Consider a simple discontinuous PWA function f pwa (x), defined over a partition in R as follows:

f pwa (x) =                             
0.8116x + 0.5328 for -0.4 ≤ x < -0.3 0.3507x + 0.9390 for -0.3 ≤ x < -0.2 0.8759x + 0.5502 for -0.2 ≤ x < -0.1 0.6225x + 0.5870 for -0.1 ≤ x < 0 0.2077x + 0.3012 for 0 ≤ x < 0.1 0.4709x + 0.2305 for 0.1 ≤ x < 0.2 0.8443x + 0.1948 for 0.2 ≤ x < 0.3 0.2259x + 0.1707 for 0.3 ≤ x ≤ 0.4

One can easily check the discontinuity of this function via its values at the vertices of the regions in the parameter space partition (see Fig. 1). A convex lifting of this partition denoted by (x), is presented below:

(x) =                              -3.5x + 0.4 for -0.4 ≤ x ≤ -0.3 -2.5x + 0.7 for -0.3 ≤ x ≤ -0.2 -1.5x + 0.9 for -0.2 ≤ x ≤ -0.1 -0.5x + 1 for -0.1 ≤ x ≤ 0 0.5x + 1 for 0 ≤ x ≤ 0.1 1.5x + 0.9 for 0.1 ≤ x ≤ 0.2 2.5x + 0.7 for 0.2 ≤ x ≤ 0.3 3.5x + 0.4 for 0.3 ≤ x ≤ 0.4
Also, this convex lifting is shown in Fig. 2. Following the approach presented previously, an optimization problem that admits the given PWA function as an optimal solution, is presented in [START_REF] Nguyen | Inverse parametric linear/quadratic programming problem for continuous pwa functions defined on polyhedral partitions of polyhedra[END_REF].

The given discontinuous PWA function is presented in Fig. 1 wherein the line along the horizontal axis describes the parameter space x and the multicolored lines above describe the given PWA function. Also, in the extended space of parameter x, the original function f pwa (x), lifting (x), the green lines in Fig. 3 represent the given PWA function. The shaded pink polytope represents a set of constraints Π in the inverse optimization problem. Note also that the solid pink lines describe an optimal solution to this optimization problem. Moreover, the images of these lines onto the space of (x, f pwa (x)) coincide with the given PWA function. It is also worth emphasizing that for each segment of state space partition, the set of optimal solutions to the above optimization problem represents a facet of the pink polytope Π, which is orthogonal to the space (x, z). As illustrated in Fig. 4, the pink facets represent the set of optimal solutions to the optimization problem [START_REF] Nguyen | Inverse parametric linear/quadratic programming problem for continuous pwa functions defined on polyhedral partitions of polyhedra[END_REF].

min [z u T ] T z s.t.                                         -0.
                                        z u ≤                                         -0.
                                        x +                                         -0.
                                        (13)
V. CONCLUSIONS This paper presents an inverse optimality result for the class of discontinuous PWA functions. The solution is based on convex liftings and leads to a linear programming type of solution. It is also emphasized that optimal solution to such an optimization problem is no longer unique but a set of solutions containing the given discontinuous PWA function. A numerical example is considered to illustrate these results. The result is mainly theoretical and sheds light on the difficulties of discontinuous PWA control law design via convex optimization. Basically, it shows that convex lifting can emulate the polyhedral partition and translate to the constraint set of an optimization problem. However, in order to recover the unicity of the optimizer, the cost function needs to embed the discontinuity via a nonlinear function.

Fig. 1 .

 1 Fig. 1. A discontinuous PWA function defined over a partition in R.

Fig. 2 .

 2 Fig. 2. A convex lifting of the given cell complex.

Fig. 3 .

 3 Fig. 3. Graphical illustration of the recovered optimization problem.


Inverse parametric linear/quadratic programming problem for continuous PWA functions defined on polyhedral partitions of polyhedra N. A. Nguyen 1 , S. Olaru 1 , P. Rodriguez-Ayerbe 1 Abstract-Constructive solution to inverse parametric linear/quadratic programming problems has recently been investigated and shown to be solvable via convex liftings [START_REF]On the lifting problems and their connections with piecewise affine control law design[END_REF], [START_REF] Nguyen | Inverse parametric convex programming problems via convex liftings[END_REF]. These results were stated and solved starting from polytopic partitions of a polytope in the parameter space. Therefore, the case of polyhedral partitions of unbounded polyhedra, was not handled by this method and deserves a complete characterization to address the general inverse optimality problem. This paper has as main objective to overcome the unboundedness limitation of the given polyhedral partition and to extend the constructive solution put forward in [START_REF] Nguyen | Inverse parametric convex programming problems via convex liftings[END_REF] for this omitted case.

I. INTRODUCTION

Inverse parametric convex programming was previously investigated in [START_REF] Baes | Every continuous nonlinear control system can be obtained by parametric convex programming[END_REF] where it was proved that every continuous nonlinear function can be obtained via parametric convex programming without a guideline for the construction of such convex programming problems. The first constructive results have recently been presented via different approaches in [START_REF] Hempel | Every continuous piecewise affine function can be obtained by solving a parametric linear program[END_REF], [START_REF] Nguyen | Inverse parametric convex programming problems via convex liftings[END_REF], [START_REF]On the lifting problems and their connections with piecewise affine control law design[END_REF]. These developments focus on continuous piecewise affine functions, a particular but important class of nonlinear functions which receives great attention in control theory as attested by the references in different topics [START_REF] Bemporad | The explicit linear quadratic regulator for constrained systems[END_REF], [START_REF] Johansen | On multi-parametric nonlinear programming and explicit nonlinear model predictive control[END_REF], [START_REF] Seron | Characterisation of receding horizon control for constrained linear systems[END_REF], [START_REF]Approximate explicit receding horizon control of constrained nonlinear systems[END_REF], [START_REF] Pistikopoulos | Multi-parametric programming[END_REF], [START_REF] Bemporad | An algorithm for approximate multiparametric convex programming[END_REF], [START_REF] Olaru | A parameterized polyhedra approach for explicit constrained predictive control[END_REF], [START_REF] Pistikopoulos | Perspectives in multiparametric programming and explicit model predictive control[END_REF], [START_REF] Grancharova | Explicit Nonlinear Model Predictive Control[END_REF].

It is well known that optimal solution to a parametric linear/quadratic programming problem is a piecewise affine (PWA) function defined over a polyhedral partition. Note that the continuity of optimal solution to parametric linear programming problems, is not guaranteed in many cases. However, it is proved in [START_REF]On the continuity and complexity of control laws based on multiparametric linear programs[END_REF] that a continuous optimal solution can always be selected. Conversely, inverse parametric linear/quadratic programming (IPL/QP) aims to recover an appropriate optimization problem, described by a constraint set and a cost function, having as the optimal solution a given continuous PWA function defined over a polyhedral partition.

This paper completes and generalizes the result in [START_REF] Nguyen | Inverse parametric convex programming problems via convex liftings[END_REF], [START_REF]On the lifting problems and their connections with piecewise affine control law design[END_REF] wherein IPL/QP problems are solved via convex liftings. In the respective works, this solution covers polytopic partitions (i.e. bounded polyhedral partitions) of the parameter space, since the convex lifting construction is based on continuity and convexity conditions on vertices of the polytopes composing the given polytopic partition. Therefore, if the given polyhedral partition contains unbounded polyhedra, N. A. Nguyen, S. Olaru, P. Rodriguez-Ayerbe are with the Laboratory of Signals and Systems (L2S, UMR CNRS 8506), CentraleSupélec-CNRS-Université Paris Sud, 3 rue Joliot Curie, Plateau de Moulon, 91192, Gif-sur-Yvette, France. Ngocanh.Nguyen, Sorin.Olaru, Pedro.Rodriguez-Ayerbe @supelec.fr this algorithm cannot be directly employed. This paper is motivated by this limitation to solve IPL/QP problems for more general class of continuous PWA functions, namely continuous PWA functions defined over polyhedral partitions of polyhedra. This result is useful to reduce implementation complexity of PWA control laws as shown in [START_REF]On the complexity of the convex liftings-based solution to inverse parametric convex programming problems[END_REF], [START_REF] Gulan | Implications of inverse parametric optimization in model predictive control[END_REF].

II. PROBLEM FORMULATION A. Generalities and basic notions

Throughout the paper, R, R + , R >0 , N, N >0 denote the field of real numbers, the field of non-negative real numbers, the set of strictly positive real numbers, the set of nonnegative integers and the positive integer set, respectively. The following index set is also defined for ease of presentation with respect to a given N ∈ N >0 :

I N = {i ∈ N >0 | i ≤ N }.
Given a d ∈ N >0 , by 1 d , we denote a vector of dimension d whose elements are equal to 1; i.e.

1 d ∈ R d .
Given a finite set S := {s 1 , . . . , s L }, then Card(S) denotes the cardinal number of the set S, i.e. Card(S) = L. conv(S) denotes the convex hull of S. Moreover, if R is a set of vectors, by cone(R), we denote the cone which has elements of R as its extreme rays.

A polyhedron is defined as the intersection of a finite number of halfspaces. A polytope is defined as a bounded polyhedron. Given a full dimensional polyhedron S ⊂ R d , then V(S) denotes the set of its vertices, and R(S) denotes the set of its extreme rays. We use k-face to denote a face of dimension k of S. A 0-face is also called a vertex, an 1-face is alternatively called an edge, a (d -1)-face amounts to a facet. Furthermore, by int(S), we denote the interior of S. If S is a vector space, and S is an arbitrary set, then Proj S S represents the orthogonal projection of set S onto space S. Also, we use dim(S) to denote the dimension of the affine hull of S.

Finally, given two sets P 1 , P 2 ⊂ R d , by P 1 ⊕P 2 , we denote the Minkowski addition defined as follows:

P 1 ⊕ P 2 = y ∈ R d | ∃x 1 ∈ P 1 , x 2 ∈ P 2 s.t. y = x 1 + x 2 .
The following definitions are extended in comparison with their counterparts presented and employed in [START_REF]On the lifting problems and their connections with piecewise affine control law design[END_REF], [START_REF] Nguyen | Inverse parametric convex programming problems via convex liftings[END_REF], [START_REF]On the complexity of the convex liftings-based solution to inverse parametric convex programming problems[END_REF].

Definition 1: A collection of N ∈ N >0 full-dimensional polyhedra X i ⊂ R d is called a polyhedral partition of a polyhedron X in 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 , Also, (X i , X j ) are called neighbours if (i, j) ∈ I 2 N , i = j and dim(X i ∩ X j ) = d -1.
If set X is compact, then this partition is called polytopic partition.

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 understood as a polyhedral partition whose facet-to-facet property is fulfilled; i.e. any pair of neighboring regions share a common facet.

In the remainder of this paper, a slight abuse of notation is used: X implies simultaneously a polyhedral partition/cell complex of a polyhedron and this polyhedron itself. Its meaning will be clarified from the context.

Definition 2: For a given polyhedral partition X = i∈I N X i ⊆ R d , a picewise affine lifting is described by a real-valued function z : X → R with:

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

a i ∈ R d , b i ∈ R, ∀i ∈ I N . Definition 3: Given a polyhedral partition X = i∈I N X i ⊆ R d , a piecewise affine lifting z(x) = a T i x + b i ∀x ∈ X i , is called 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 .
For ease of presentation, a convex piecewise affine lifting is called, throughout the rest of this paper, convex lifting. It is shown in [START_REF] Rybnikov | Polyhedral partitions and stresses[END_REF], [START_REF]Recognition of additively weighted voronoi diagrams and weighted delaunay decompositions[END_REF] that a polyhedral partition which admits a convex lifting, is a cell complex. Therefore, a convex lifting is always defined over a cell complex instead of a polyhedral partition.

For a given polyhedral partition, some conditions have to be fulfilled for the existence of a convex lifting. A summary of these conditions can be found in [START_REF] Rybnikov | Polyhedral partitions and stresses[END_REF]. We extract here only the necessary notation in connection with the present developments. Interested readers can find details in [START_REF] Rybnikov | Polyhedral partitions and stresses[END_REF], [START_REF]On the lifting problems and their connections with piecewise affine control law design[END_REF].

Given a polyhedron C and its facet F , we use n(F, C) to denote the inward unit normal vector at F to C, meaning the unit vector normal to F at F and inward to C. The definition of stress is recalled here for completeness.

Definition 4:

(Rybnikov [20]) A real-valued function s(•) defined on the (d -1)-faces of a cell complex X ⊆ R d is called a d-stress if at each internal (d -2)-face F of X : F ⊂C s(C)n(F, C) = 0, (2)
where this sum ranges over all (d-1)-faces in the star of F (the (d -1)-faces such that F is their common facet). The quantities s(C) are the coefficients of d-stresses, and are called tension if the sign is strictly positive, and compression if the sign is strictly negative. Such a (d -2)-face F of cell complex X satisfying ( 2) is also called in equilibrium. Note also that a necessary and sufficient condition for such a cell complex X to be convexly liftable is the existence of a strictly positive d-stress defined over all (d -1)-faces of cell complex X .

B. Problem formulation

The solution to inverse parametric linear/quadratic programming problems is shown in [START_REF]On the lifting problems and their connections with piecewise affine control law design[END_REF], [START_REF] Nguyen | Inverse parametric convex programming problems via convex liftings[END_REF] via convex liftings. This solution restricts the parameter space to a polytope and lets aside the important case of unbounded parameter space. This omission is tackled in this paper and the problem can be formally stated as follows: Problem statement: Given a polyhedral partition of a polyhedron X = i∈I N X i ⊆ R dx , we use f pwa (•) to denote a continuous PWA function: f pwa (x) : X → R du , defined over partition X . The objective is to determine

J(x, z, u), H x , H u , H z , K such that:    f pwa (x) = Proj R du arg min [z u T ] T J(x, z, u), s.t: H x x + H z z + H u u ≤ K. (3)
Some assumptions need to be stated for guaranteeing the validity of the proposal. Assumption 1: Polyhedral partition X is a cell complex. Assumption 2: Polyhedral partition X is convexly liftable. As discussed before, a polyhedral partition, admitting a convex lifting, is a cell complex, therefore, if a given partition satisfies Assumption 2, then it also fulfills Assumption 1.

Note that Assumption 2 is not restrictive, since, as shown in [START_REF]On the lifting problems and their connections with piecewise affine control law design[END_REF], any polyhedral partition can be subdivided into a convexly liftable cell complex such that the internal boundaries are maintained. This inclusion can be easily extended to unbounded polyhedral partitions by following the same methodology of the proof (Theorem IV.2 in [START_REF]On the lifting problems and their connections with piecewise affine control law design[END_REF]).

III. CONSTRUCTIVE SOLUTION

It is shown in [START_REF]On the lifting problems and their connections with piecewise affine control law design[END_REF], [START_REF] Nguyen | Inverse parametric convex programming problems via convex liftings[END_REF] that constructive solution to such an inverse parametric linear/quadratic programming problem can be built upon convex lifting principle. However, the algorithm to construct convex liftings of the given cell complex put forward therein, is only applicable for cell complexes of polytopes. Therefore, for the cell complexes of polyhedra, this algorithm cannot be directly applicable. To adapt to unbounded parameter space, two intuitive approaches can be proposed:

• either to modify this algorithm subject to cell complexes of polyhedra, • or to adjust the given cell complex of polyhedra in such a manner that this algorithm can be directly of use. The latter approach will be of interest via a simply intermediate step in the sequel. More precisely, we restrict the given parameter space partition to an appropriate bounded region such that the convex liftability of this new partition and the initial one is treated in a similar manner. Accordingly, we propose here the use of a hyperbox large enough to contain in its interior all vertices of the initial partition. The existence of such a hyperbox is guaranteed by the fact that a polyhedral partition is the collection of a finite number of polyhedra, as a consequence the number of vertices is finite. By B dx ( ), we denote a hyperbox for a given scalar ∈ R >0 , defined as

B dx ( ) := x ∈ R dx | x ∞ ≤ .
The hyperbox used for our purpose needs to meet the following assumption: Assumption 3: Given a polyhedral partition X = i∈I N X i ⊆ R dx , the scalar is restricted to the values that ensure x ∈ int(B dx ( )) for every x ∈ i∈I N V(X i ).

The following observation guarantees the correspondence of their convex liftability property.

Proposition 1: If a given partition X of a polyhedron satisfies Assumption 1, then partition X is convexly liftable if and only if there exists a hyperbox B dx ( ), satisfying Assumption 3 such that the partition X ∩B dx ( ) = i∈I N (X i ∩ B dx ( )) is convexly liftable.

Proof: -→ It is already known ( [START_REF] Rybnikov | Polyhedral partitions and stresses[END_REF], [START_REF]On the lifting problems and their connections with piecewise affine control law design[END_REF]) that the convex liftability of partition X leads to the existence of a strictly positive function s(•) defined over the (d x -1)-faces of partition X such that every internal (d x -2)-face is in equilibrium. Consider an internal (d x -2)-face of partition X denoted by F , we write F dx-1 (F ) to denote the set of (d x -1)-faces of partition X , sharing a common facet F , then the following inclusion holds true:

Ci∈F dx -1 (F ) s(C i ) n(F, C i ) = 0.
By the construction of B dx ( ), if F is an internal (d x -2)-face of partition X , then F ∩ B dx ( ) is also an internal (d x -2)-face of partition X ∩ B dx ( ). Furthermore, F ∩ B dx ( ) also satisfies the following property:

Ci∈F dx -1 (F ) s(C i )n(F ∩ B dx ( ), C i ∩ B dx ( )) = 0, due to the fact that n(F ∩ B dx ( ), C i ∩ B dx ( )) = n(F, C i ).
Therefore any internal face F ∩B dx ( ) is in equilibrium with strictly positive d x -stress: s(C i ∩ B dx ( )) = s(C i ) > 0, meaning the cell complex X ∩ B dx ( ) is convexly liftable. ←-The sufficient condition can be similarly proved. The goal is to present a construction of convex liftings for the given cell complex X of a polyhedron, based on an intermediate polytopic partition X ∩ B dx ( ). The following observation shows this close relation.

Proposition 2: Given a cell complex X of a polyhedron satisfying Assumption 2 and a hyperbox

B dx ( ) satisfying Assumption 3, if f : X ∩ B dx ( ) → R i.e. f (x) = a i x + b i for x ∈ X i ∩ B dx ( ),
is a convex lifting of the cell complex X ∩ B dx ( ), then the function g : X → R, defined as follows:

g(x) = a i x + b i for x ∈ X i ,
is also a convex lifting of partition X .

Proof: First, we observe that due to Assumption 3, the constraints characterized by B dx ( ) do not contribute to the division of the partition X ∩ B dx ( ).

From the hypothesis, f (x) is a convex lifting of partition X ∩ B dx ( ), then it can be deduced from two neighboring regions (X i ∩ B dx ( ), X j ∩ B dx ( )) that:

a i x + b i = a j x + b j ∀x ∈ X i ∩ X j ∩ B dx ( ), a i x + b i > a j x + b j ∀x ∈ (X i ∩ B dx ( ))\(X j ∩ B dx ( )).
Note also that the constraint a i x + b i = a j x + b j describes the set of points which lie on the hyperplane separating X i ∩B dx ( ) and X j ∩B dx ( ), then it also separates X i and X j . Therefore, the following inclusions hold true:

a i x + b i = a j x + b j ∀x ∈ X i ∩ X j , a i x + b i > a j x + b j ∀x ∈ X i \X j .
The same argument holds true for all pairs of neighboring regions in partition X ∩ B dx ( ), leading to:

g(x) = a i x + b i > a j x + b j , ∀x ∈ X i \X j , ∀j = i.
In other words, as per Definition 3, g(x) is a convex lifting of the cell complex X . The above results are meaningful to construct a convex lifting for the cell complex X of a polyhedron, based on a bounded one X ∩ B dx ( ). The structure of the latter partition is compatible with the algorithms presented in [START_REF]On the lifting problems and their connections with piecewise affine control law design[END_REF].

As previously shown, the construction of a convex lifting for partition X of a polyhedron can be carried out via the restriction of X into a large enough hyperbox in the same dimensional space. A natural question arises how this hyperbox can be chosen. This choice must clearly satisfy Assumption 3, and can be found through Algorithm 1.

Algorithm 1 Computation of a hyperbox B dx ( ) Input: A cell complex X of a polyhedron in R dx and a scalar a > 0. Output: .

1: V = i∈I N V(X i ). 2: Solve the following problem min s.t. ≥ 0, -( -a)1 dx ≤ x ≤ ( -a)1 dx , ∀x ∈ V. (4)
Note that such a constant a > 0 needs to be inserted in the set of constraints for guaranteeing Assumption 3 i.e. all vertices v ∈ i∈I N V(X i ) lie in the interior of B dx ( ). This constant can be freely chosen as long as it is strictly positive.

Based on these results, to state a solution to inverse parametric linear/quadratic programming problem via convex liftings for unbounded partition, we need to define some supplementary notation.

First, given a cell complex of a polyhedron X = i∈I N X i ⊆ R dx satisfying Assumption 2, a continuous PWA function f pwa (•) : X → R du is defined as

f pwa (x) = f i x + g i for x ∈ X i .
(5)

By (x), we denote a convex lifting of the cell complex X i.e. (x) = a i x+b i for x ∈ X i . Based on the above elements, the following sets are also defined:

V x = i∈I N V(X i ), R x = i∈I N R(X i ), V [x T z u T ] T = x T (x) f T pwa (x) T | x ∈ V x , R [x T z u T ] T =        r (r) f (r)   r ∈ R x , (r) = a i r f (r) = f i r if r ∈ R(X i )      , Π v = conv(V [x T z u T ] T ), Π r = cone(R [x T z u T ] T ), Π = Π v ⊕ Π r . (6)
With these notation, the following theorem presents a solution to IPL/QP problems via convex liftings for polyhedral partitions of a polyhedron. Theorem 3.1: Given any continuous PWA function f pwa (x) (5) defined over a cell complex of a polyhedron satisfying Assumption 2 and the sets defined in (6), then f pwa (x) is the image via the orthogonal projection of the optimal solution to the following optimization problem:

min [z u T ] T z s.t. x T z u T T ∈ Π. (7)
Proof: Consider x ∈ X i , for a region X i of the given partition X , according to the Minkowski-Weyl theorem for polyhedra (Corollary 7.1b in [START_REF] Schrijver | Theory of linear and integer programming[END_REF]), x can be described as follows:

x = v∈V(Xi) α(v)v + r∈R(Xi) β(r)r,
where α(v), β(r) ∈ R + and v∈V(Xi) α(v) = 1. As a consequence, the convex lifting at x, i.e. (x) can be described by:

(x) = a i x + b i = a i ( v∈V(Xi) α(v)v + r∈R(Xi) β(r)r) + b i , = v∈V(Xi) α(v)(a i v + b i ) + r∈R(Xi) β(r)(a i r).
Similarly,

f pwa (x) = f i x + g i = f i ( v∈V(Xi) α(v)v + r∈R(Xi) β(r)r) + g i , = v∈V(Xi) α(v)(f i v + g i ) + r∈R(Xi) β(r)(f i r).
It can be observed that if r is an extreme ray of X i , then r T a i r T is also an extreme ray of the affinely equivalent polyhedron Π [x T z] T of cell complex X defined as follows:

Π [x T z] T = conv(V [x T z] T ) ⊕ cone(R [x T z] T ),
where

V [x T z] T = x (x) | x ∈ V x , R [x T z] T = r (r) | r ∈ R x , (r) = a i r if r ∈ R(X i ) .
According to the definition of an affinely equivalent polyhedron, the optimal solution to the following problem:

min z z s.t. x T z T ∈ Π [x T z] T
falls in the lower facets of Π [x T z] T described by the convex lifting (x) of partition X . Now, consider a region X i , by

F (i) [x T z] T we denote the lower facet of Π [x T z] T such that Proj R dx F (i) [x T z] T = X i .
According to Proposition 5.1 in [START_REF] Nguyen | Inverse parametric convex programming problems via convex liftings[END_REF], every augmented point in V [x T z u T ] T corresponds to the vertices of Π v after lifting onto R dx+du+1 . Therefore, by preserving lifting onto R dx+du+1 , we guarantee the existence of a d x -face of Π, denoted by

F (i) [x T z u T ] T such that: Proj R dx+1 F (i) [x T z u T ] T = F (i) [x T z] T .
Note that such a d x -face is defined as follows:

F (i) [x T z u T ] T = F (i) 1 ⊕ F (i) 2 F (i) 1 = conv v T (v) f T pwa (v) T | v ∈ V(X i ) F (i) 2 = cone      r (r) f (r)   r ∈ R(X i ), (r) = a i r f (r) = f i r    .
It can be observed that at a point x ∈ X i , the minimal value of z can be obtained when x T z u T T lies in

F (i) [x T z u T ] T since Proj R dx +1 F (i) [x T z u T ] T = F (i) [x T z]
T and the optimal solution to:

min z z s.t. x T z T ∈ Π [x T z] T , falls at the point x T (x) T ∈ F (i) [x T z] T .
Therefore, optimal solution to (7) at x can be described by:

  x z * (x) u * (x)   = v∈V(Xi) α(v)   v a i v + b i f i v + g i   + r∈R(Xi) β(r)   r a i r f i r   , where α(v), β(r) ∈ R + and v∈V(Xi) α(v) = 1. It is clear that z * (x) u * (x) = a i x + b i f i x + g i = (x) f pwa (x)
, for x ∈ X i .

To complete the proof, we now need to show that the optimal solution to (7) is unique. In fact, at a point x ∈ X i , suppose there exist two different d x -faces denoted by F 1 , F 2 to which optimal solutions to (7) belong. Let

x T z 1 (x) u T 1 (x) T ∈ F 1 and x T z 2 (x) u T 2 (x) T ∈ F 2 , then it can be observed that z 1 (x) = z 2 (x), leading to Proj R dx +1 F 1 = Proj R dx +1 F 2 = F (i) [x T z] T . If u 1 (x) = u 2 (x), then F 1 , F 2 lie in a hyperplane of dimension d x + 1 which is orthogonal to the space of x T z
T . In this case, either f pwa (v) or f (r) or both are not uniquely defined for some vertices v ∈ V(X i ), some extreme rays r ∈ R(X i ). This contradicts the construction in [START_REF] Gulan | Implications of inverse parametric optimization in model predictive control[END_REF]. Therefore, F 1 = F 2 leading to the uniqueness of the optimal solution to [START_REF] Hempel | Every continuous piecewise affine function can be obtained by solving a parametric linear program[END_REF].

Based on the above result, Algorithm 2 summarizes a procedure to solve the inverse optimality problem to recover a continuous PWA function defined over a convexly liftable cell complex of a polyhedron.

Algorithm 2 Solution to IPL/QP problem via convex lifting. Input: A continuous PWA function f pwa (x) [START_REF] Grünbaum | Convex polytopes[END_REF]. Output: H x , H u , H z , K, J(x, z, u).

1: Call Algorithm 1 to find an appropriate B dx ( ). 2: Construct a convex lifting denoted as (x) of the cell complex X ∩ B dx ( ). 1 3: Compute (x) for the cell complex X . 4: Construct constraint set Π as in (6). 5: Solve the following optimization problem:

z * u * = arg min [z u T ] T z s.t. x T z u T T ∈ Π.
6: Project the optimal solution onto R du i.e.

u * = Proj R du z * u * .
Note that this result can be trivially extended for removal of redundant constraints as shown in [START_REF]On the complexity of the convex liftings-based solution to inverse parametric convex programming problems[END_REF]. Similarly, extensions of inverse optimality with quadratic cost functions and discontinuous PWA functions are referred to [START_REF] Nguyen | Any discontinuous pwa function is optimal solution to a parametric linear programming problem[END_REF].

IV. NUMERICAL EXAMPLES This section considers some numerical examples to illustrate the above results. All numerical examples in this paper are carried out in the environment of MPT 3.0 [START_REF] Herceg | Multi-Parametric Toolbox 3.0[END_REF].

Example 1

This subsection considers a continuous PWA function defined over the whole space R, as shown in Fig. 1. This partition is the union of several segments:

X 1 = {x ∈ R | x ≤ -0.5} , X i = {x ∈ R | 0.1(i -7) ≤ x ≤ 0.1(i -6)} , i = 2...11, X 12 = {x ∈ R | x ≥ 0.5} .
A convex lifting of this partition is presented in Fig. 2. A set of constraints for the formulation of inverse optimality problem, is shown in Fig. 3 as the shaded pink polyhedron. It is shown therein that the line along the x-axis, represents the given partition X , while the green curve represents the given PWA function associated with this partition. It can be observed that the solid pink line depicts the optimal solution to (7) whose image via the orthogonal projection onto R du coincides with the given PWA function. 1 An algorithm to construct a convex lifting of a bounded cell complex is presented in [START_REF]On the lifting problems and their connections with piecewise affine control law design[END_REF].

Example 2

The present subsection aims to illustrate the constructive solution with another continuous PWA function defined over a convexly liftable partition covering the whole space R 2 as seen in Fig. 4. This continuous PWA function is depicted in Fig. 5. A convex lifting of the given partition can be found in Fig. 6. Finally, the recovered PWA function is shown in Fig. 7, and can be seen to be similar to the original one.

V. CONCLUSIONS

The present paper shows a procedure to recover a continuous PWA function defined over a polyhedral partition of unbounded polyhedra. This solution is a simple extension of the constructive solution based on convex liftings put forward in previous results. Two numerical examples are presented to illustrate the constructive procedure proposed above.

Fig. 1 .Fig. 2 .Fig. 3 .

 123 Fig. 1. Given PWA function defined over a partition of R.

Fig. 4 .

 4 Fig. 4. A partition covering the whole space R 2 .

Fig. 6 .Fig. 7 .

 67 Fig. 6. A convex lifting of the partition in Fig.4.


Qiang Li

Yunbo Zhong

Huai Wang

Yipeng Fang

Zuosheng Lei

Jianbo Yu

Zhongming Ren

Evolvement of solidified morphology in GCr15 bearing steel ingots remelted by magneticcontrolled ESR process

Keywords: solidified morphology, bearing steel, ESR, magnetic-controlled

The GCr15 bearing steel ingots were remelted by Electro-Slag Remelting (ESR) process with superimposing of 0T, 0.08T and 0.16T transverse static magnetic field, which was named as MC-ESR. The solidification morphology and secondary dendrite arm spacing (SDAS) of MC-ESR ingots were analyzed. The results showed that the solidification structure of ESR ingots without static magnetic field was oversized, and that of MC-ESR ingots was refined obviously. With 400A melting current, SDAS reduced from 71.6μm to 52.9μm by superimposing of 0.16T steady magnetic field. The electromagnetic vibration effect due to the interaction between static magnetic field and alternating electric current for remelting is thought to be the main reason to even the temperature field in slag pool and molten steel pool and to refine the solidification morphology.

Introduction

Electroslag Remelting process has been widely used in modern metallurgy for its advanced characters such as purifying metal, solidification structure control and nearly net shape. The products of ESR are widely found in everywhere of the national economy [1][2]. With the development of society, the demand of large, super large ESR ingots become more and more urgent, so it put forward higher requirements of the ESR process. However, while producing high-alloy steel, there are still coarse solidification structure, serious problems of macrosegregation, porosity and shrinkage cavity [3][START_REF] Yoshiko | Tetsu-to-Hagane[END_REF]. Therefore improving slag ingot quality has an important significance to the development of China's industrial economy. How to control the melting and solidification process of ESR process, reinforcement refining process and the transmission behavior of slag and metal in the weld pool, become the key problem to solve. In modern metallurgical production process, electromagnetic technology has been rapid development with its unique superiority [START_REF] Zhong Yun-Bo | [END_REF][6]. Researches on the ESR of high speed steel under 0.1T magnetic field reveal that outer magnetic field can change the remelting mechanism of self-consuming electrode and refine the solidification structure and even the phase-change thermodynamics during the cooling of high speed steel [6]. In this paper, the steady magnetic field was applied during the ESR process of bearing steel according the features of ESR. The effects of the electrical field on the solidification process, the influence of magnetic field on the solidification and the transmission process were integrated. The theoretical analysis and experimental results show that the main influence factors of ESR Ingot quality include power supply system, speed of melting, solidification velocity and magnetic induction intensity. A appropriately parameters of power supply mechanism , magnetic flux density and so on were decided by the analysis of solidification structure refined by electromagnetic oscillation.

Experimental Apparatus and Method

The GCr15 consutrodes used for ESR process is bearing steel prepared by BaoSteel special steel factory, with size 20 mm x 650 mm, and the chemical components are listed in Table 1. The GCr15 Φ20mm×650mm consumable electrodes were melted under the 0T, 0.08T and 0.16T transverse static magnetic field by using the micro-ESR system (Fig. 1). The steady magnetic field was provided by NdFeB magnets. By changing the number of NdFeB magnets, the range of the steady magnetic field is from 0T to 0.16T. The mold is made by the copper and water-cool. The inner diameter and height is 50 and 130 mm. The effect of different configurations of the applied magnetic fields on the technological features of the electro-slag process and properties of melted ingots were tested.

Fig. 1 Experimental ESR device of of bearing steal magnetic pole

Triplet Fluorine-free slag of CaO-Al2O3-SiO2 are applied in ESR process [7], which is used to compare with the traditional CaF2 slag series. Fluorine-free slag has lower electric conductivity and better effect of desulfurization, and remelting speed is increased by 20%-40%, thus it can improve the productivity and reduce current wattage [8].

In ESR experiment, an access industry frequency alternating current is applied from bearing steel through consutrode and water-cooled copper plate to bottom electrode. Current of 400A, 500A, 600A, and 700A is chosen for remelting under magnetic field of 0T, 0.08T and 0.16T respectively. To keep ESR process stable, we try to keep the depth of slag pool constant and stability of component through continuous addition of covering slag.

Experimental result and discussion

The remelted ingots are divided into two parts along the axial direction, and one of them was grind and polished, then the upper, middle and bottom area are remarked. By means of measuring the secondary dendrite arm spacing in 30 visual fields randomly in microscope, each part's average secondary dendrite arm spacing of remelted ingots under different magnetic field intensity is shown in Fig. 2.

Fig. 2 Average secondary dendrite arm spacing From Fig. 2, we can easily find that by imposing a static magnetic field during ESR process, the secondary dendrite arm spacing is changed dramatically. Without magnetic field, the ingot microstructure is well-developed coarse dendrite whose average dendrite arm spacing is over 70μm under a 400A current. While being remelted under magnetic flux density of 0.08T, the dendrite grain is greatly refined to about 60μm. When magnetic flux density reaches 0.16T, dendrite arm spacing reduce to 52.9μm, which is nearly 25% lower than that by typical ESR. The above phenomena indicate that magnetic field plays an important role in refining the ingot microstructure. Microstructure is one of the most factor to determine properties of ingots. The effect of different configurations of the applied steady magnetic fields on the properties of ESR ingots were verified in Fig. 3. For the classical ESR process, the main feature of the melting mechanism is the high superheating of metal by the molten slag, whose temperature is usually 423-473K higher than the temperature of electrode metal melting [9], resulting in the relatively low cooling speed during solidification [10][11]. For this reason, a strong and oversize coarse dendrites occurred (Fig 3a). At the same time, the oversized dendrites grow with the direction toward axial.

The steady magnetic field applied during the conventional ESR remelting caused significant positive changes in the microstructure of the ingots (Fig. 3b and3c). With a 0.08T steady magnetic field, the structure and grain size are of remelting ingots got obviously refined (Fig. 3b). At the same time, the included angle between axial and the dendrites decreased. The refining of the ingot structure was stimulated by intensification of heat/mass exchange at the liquid-solid phase interface. However, both of these phenomenons can prove the effectiveness that electromagnetic vibration caused by the interaction between the alternating current and the steady magnetic field. In this experiment, steady magnet field, which is vertical to the current direction, is employed from the top of consutrode to liquid metal, by which an alternate Lorentz force will be induced in the whole ESR system. This kind of alternating Lorentz force will accelerate the drops off of melt droplet, causing the size of melt droplet to become smaller. With the increasing of the magnetic flux density and current intensity, the electromagnetic oscillating force will be stronger then tiny melt droplets will be obtained. In general, the decreasing of the melt droplet size will reduce the migrating distance and duration for inclusions and impure element migrating from inner area of melting droplets to the surface of the droplet. The ratio surface area of the molten drops will be increased too, and the molten droplets will stayed in molten for longer time due to its reduced sinking rate. All of the above factors will promote inclusions and impurity element in the drops to be removed more thoroughly.

In addition, the effect of the electromagnetic vibration also occurs in the molten slag and the melt pool. The electromagnetic oscillating force in molten slag pool will promote the uniformity distribution of temperature, which will make the solid/liquid interface planer. Also the vibration due to the alternative electromagnetic force will strengthen transport process of gases and impurity elements which is beneficial to dephosphorization and desulfbrization process. Electromagnetic oscillating force will stabilize the temperature gradient in front of solid/liquid interface, and break down the branch crystal tips, which leads to refine the grain size and reduce dendrite arm spacing. As we know, the decrease of inclusions, the refined grain size and reduced dendrite arm spacing will be helpful to homogenize the elements and elevate the mechanics performance of ESR ingots.

Conclusions

With increasing the magnetic flux density and the current intensity, the dendrite spacing of the ESR ingot will be decreased and the structure will be refined. The superimposing of static magnetic field obviously made the metal molten pool tend to become planer than that without magnetic field, which is thought that the pool temperature uniformity can be prompted through the electromagnetic oscillating due to the interaction between AC current and static magnetic field. The planer interface is beneficial to remove inclusion, restrain composition segregation evolved over time and the formation of small columnar crystal.

Fig. 3

 3 Fig. 3 microstructural evolution under different steady magnetic field: (a) 0T, (b) 0.08T and (c) 0.16T

Table 1

 1

			Chemical compositions of consumable eIectrode (mass fraction, %)
	C	Si	Mn	S	P	Cr	Al
	0.82~0.85	0.201~0.205 0.367~0.368 0.010~0.012 0.031~0.035 1.39	0.022~0.025

Acknowledgment

The authors gratefully acknowledged the financial support of Nature Science Foundation of China (Key Project No. 51034010), Science and Technology Commission of Shanghai Municipality (Key Project No. 13JC1402500), Natural Science Foundation of Jiangsu Province (BK2011501) and Innovation Fund for Technology Based Firms (12C26213202452).


V Bojarevics
email: v.bojarevics@gre.ac.uk

K Pericleous

Particle tracking during melting and solidification in the presence of AC magnetic field of various configurations

Keywords: particle tracking, electromagnetic mixing, melting, solidification

The AC electromagnetic field effects in molten metal are investigated to account for the mixing of particles (grain refiners, micro/nano additives, impurities, broken metal dendrite agglomerates, bubbles) during the full melting/solidification cycle. The particles travel due to the hydrodynamic drag, buoyancy, turbulent fluctuations and the electromagnetic force action via the local pressure distribution around the particle. The time average effects are investigated previously using approximation derived for a uniform electric and magnetic fields. In the presence of AC field the force distribution is non-uniform, confined to an exponential skin-layer near the outer surface of liquid. This typically results in high mixing rates and an intense turbulence in the bulk of molten metal, additionally contributing to the particle dispersion. The paper attempts to demonstrate the importance of each of the mentioned effects to the organized particle 'swarm' like transport and the eventual distribution. Three different examples of the mixing flows generated by AC fields are presented: a travelling field stirring during directional solidification, the semi-levitation dynamic melting and the contactless top coil 'immersion' mixing involving the dynamic AC field adjustment. The Lagrangian particle tracking in the presence of strong AC electromagnetic force field gives new perspectives to the understanding of the melting and casting processes.

Introduction

Aluminium, magnesium and titanium alloys are the light structural metals attractive for aerospace and automotive applications. Research efforts are aimed at developing new casting techniques and practices to ease inherent processing difficulties of these alloys to achieve more desirable mechanical properties for critical automotive structural and kinetic components. One major barrier to casting these components is melting and subsequently casting homogeneous alloys free of contamination and severe segregation, or alternatively adding uniformly dispersed micro to nano particles to create a composite alloy of enhanced mechanical properties. A finer microstructure usually improves the mechanical properties of the solidified alloy. Finer microstructure can be achieved by increasing the cooling rate, adding dispersed micro to nano size particles of other materials or distributing broken dendrite fragments of the same material as grain refiners. The additional stirring eases the restrictions on the cooling rate during the casting process. It is well known that forced stirring of the melt by electromagnetic forces can significantly promote the detachment of dendrite arms and transporting the crystal fragments in a disperse fashion due to the presence of high turbulence [1]. However, unidirectional stirring in laminar conditions could induce undesirable channel segregation in the solidifying material [2]. Therefore the electromagnetic stirring [3] must be applied in an optimized way designed for a particular process. The large scale electromagnetically driven flow circulation exerts a drag force which contributes to the particle transport. The particles travel due to the hydrodynamic drag, buoyancy, turbulent fluctuations [4] and the electromagnetic force action via the local pressure distribution around the particle. A significant contribution to the force balance arises from the so called electro-magnetophoretic forces [5], which are well known for a variety of MHD applications, such as removal of inclusions from steel melt [6,7], concentrating electrically insulating bubbles [8,9] or insulating particles collected near the surface [START_REF] Taniguchi | Proc. 3rd Int. Symp. Electromagn. Proc. Materials[END_REF], and for many other purposes of separation or mixing [START_REF] Zhang | [END_REF]. The electromagnetic force acts directly onto electrically conducting inclusions, however the electromagnetic force in the surrounding fluid creates the pressure distribution gradient leading to the integral force on the non-conducting inclusions. Often the electromagnetic force expression is used as derived by Leenov & Kolin [5] in the case of particles positioned in a constant crossed electric and magnetic fields. Experimental observations of the particles of various shapes and electrical conductivities in the liquid metal carrying electrical current are described in [START_REF] Bojarevics | Electrically Induced Vortical Flows[END_REF], where the expression similar to Leenov, Kolin's was derived, but for the conditions of gradient magnetic field, which results in the increase of the effective force on the particles. In the AC magnetic field the time average force effects are often treated using the same formulae as for the constant uniform fields. The latter contradicts the skin-layer distribution of the exponential force distribution in the AC field [START_REF] Etay | [END_REF]. Moreover, the total force in AC field contains also the pulsating part contributing to the particle drag by the 'history' and 'added mass' contributions. The high mixing rates ensure the intense turbulence in the bulk of molten metal, additionally affecting the particle dispersion. This paper attempts to demonstrate the importance of each of the mentioned effects to the organized particle 'swarm' like transport and the eventual distribution when the melt solidifies to final ingot of modified impurity distribution. The pseudo-spectral numerical method is extended to account for the presence of particles during the melting/mixing/solidification cycle in presence of single and multiphase AC magnetic fields. Three different examples of the mixing flows generated by AC fields are presented: a travelling field stirring during directional solidification, the semi-levitation dynamic melting and the contactless top coil 'immersion' mixing involving the transient AC field adjustment.

Mathematical modelling

The mathematical modelling of the complex time dependent problem describing initially a solid body heating, the melting process and subsequent liquid metal confinement dynamics, internal fluid flow and the temperature evolution is accomplished using the SPHINX code developed at the University of Greenwich [START_REF] Bojarevics | [END_REF]15]. While in the temperature limit below melting the solid body heating is solved in the continuously adjusted electromagnetic field from the (possibly moving) source coils. The time dependent Joule heating eventually leads to melting of the solid. When the solidus temperature is reached, the model accounts for the phase transition and the following liquid material shape change due to the action of the EM force distribution adjusted to the moving interface. The fluid flow is solved using the Reynolds averaged turbulent flow model for an incompressible fluid with the effective viscosity ν e and the turbulent diffusivity α e modified heat transfer equations given in detail elsewhere [START_REF] Bojarevics | [END_REF]15]. The boundary conditions are prescribed dynamically on the moving liquid interface. The free surface boundary conditions are determined by the tangential and normal stress components accounting for the temperature dependent surface tension γ(T). The method is based on the continuous coordinate transformation adapting to the free surface and the containing vessel shape. The present implementation adds the Lagrangian passive particle tracking algorithm. The position R(x,y,z,t) of an individual particle can be determined following its path and the variable total force F(x,y,z,t) acting on the particle by solving the set of two equations [4,[START_REF] Clift | Bubbles, Drops, and Particles[END_REF]:

, , t p p t p m     R u u F (1), ( 2
)
where u p is the particle velocity and m p its mass. The force F acting locally on the spherical particle can be decomposed into the fluid drag force F d , the buoyancy force F g and the effective electromagnetic force F e . The drag force depends on the Reynolds number

/ p p R e r    u
, where r p is the particle radius, Δu = uu p is the (slip) velocity relative to the fluid velocity u, νthe kinematic viscosity. For small particles (1nm -100 µm) the Reynolds number Re p is rather small, of the order 0.1 -10, therefore the drag force can be approximated as instantaneous modified Stokes formula [START_REF] Clift | Bubbles, Drops, and Particles[END_REF]. The buoyancy force due to the gravity g action on the particle and the surrounding fluid is ( )

g p p V     F
g , ρ is the fluid density, ρ pthe particle density, V pthe particle volume. The electromagnetic force acts on the induced electric current in the particle [3] and due to the fluid pressure redistribution on the surface of the particle. For the case of electrically non-conducting particles (oxides, carbides, dendrite fragments, bubbles etc.) the electromagnetic force in the AC skin-layer can be derived as V  F f gives two times smaller force acting on a non-conducting particle. The presence of the oscillating force component requires the modified drag expression for an oscillating spherical particle [START_REF] Landau | Fluid Mechanics[END_REF]:

2 2 6 [ (1 ) (1 )
] , 9 2

p p r d r dt                  d u F u , (3)
where the Stokes number ε can reach an order 1 in an AC field oscillating at typical frequencies ω ~10 3 -10 4 Hz. The equation (3) contains the instantaneous Stokes drag, the memory term (Basset force) and the added mass force. The typical mixing flow is turbulent (Re ~ 10 3 -10 4 ), which further requires a modification due to the stochastic part of velocity in accordance to the resolved turbulent kinetic energy k and the local eddy life time (or the particle transit time in that eddy, whichever is the shortest) [4]. The use of k-ω turbulence model in the SPHINX code facilitates to obtain these quantities, which are locally interpolated to the particle position at each time step. The numerical integration of equations ( 1) and ( 2) is done for each individual particle of various properties depending on the initial seeding locations. The time dependent forces F are sensitive to the location and the instantaneous update of local slip velocity Δu (including the stochastic contribution). Therefore, the stability of long term integration along the particle tracks can be adversely affected by the choice of numerical integration scheme. The classical explicit integration schemes are limited to extremely small time steps, which could make the numerical solution difficult for the dynamic flow conditions. The exponential numerical scheme, proposed in [15], permits stable time integration of the particle tracks with the time steps of the order 0.1 -1ms (adjustable) used for the unsteady fluid flow solution in the examples considered below.

Numerical solution examples

In a typical induction melting crucible of cylindrical shape the coil is coaxially surrounding the liquid zone, for instance as in the Figs. 4,5. The computed force distribution is shown in the Fig. 1 comparing the 1 kHz and 11 kHz cases. The relatively large particle of 1mm is shown in the skin-layer to demonstrate the steep force change over the size of particle. The full AC force variation in the Fig. 2 is computed for several AC periods using 100 time steps per period for the top coil immersed mixing application (see the Fig. 3). The force amplitude is very large under the top coil due to the extreme proximity effect achieved in this application [START_REF] Bojarevics | [END_REF]. This helps to produce a strong jet and the turbulent mixing required to disperse the particles initially added on the top surface, Fig. 3. The second example shows two different SiC particle distribution types achieved when using the travelling magnetic field type of mixing during the silicon material solidification. The upward travelling field produces fast engulfment of the particles in the bottom zone (Fig. 4), while the downward travelling field creates conditions to collect the particles at the side wall (Fig. 5), though at much slower rate. The third example is for a containerless semi-levitation melting process [19,[START_REF] Bojarevics | [END_REF]. The electromagnetic field induces a strong turbulent flow in the molten pool, which is beneficial for producing a homogeneous melt with uniform temperature. The process combines induction melting and casting into a single self-controlling operation. The charge is melted from top to bottom through movement of the induction coil as illustrated in Fig. 6. Pouring of the charge through the hole in the chill block into the mold below occurs when the liquid melting front reaches the base of the metal charge. Fig. 7 compares the particle instantaneous positions after the random seeding in the initial solid cylinder, melting and mixing for 340 s, then pouring while the magnetic confinement and mixing is maintained. The mixing patterns in organized particle 'loops' are created when neglecting the turbulent fluctuations and the oscillating force, while the full AC force contribution creates more realistic particle distribution.

  the time average and the oscillating components in the fluid at the location of the particle. Note, the Leenov, Kolin[5] expression derived for DC constant fields

Fig. 1 :

 1 Fig. 1: Time average force and the electric current radial distribution in the cylindrical crucible, showing a small sphere for a scale comparison.

Fig. 2 :Fig. 3 :Fig. 4 :

 234 Fig. 2: Oscillating force distribution for the top coil (1700 A, 10 kHz) and the side coil (1600 A, 2 kHz) joint action.

Fig. 5 :

 5 Fig. 5: The effect of downward travelling field at 500 Hz on particles in directionally solidified Si.

Fig. 6 :Fig. 7 :

 67 Fig. 6: Semi-levitation melting at the final stage when liquid pouring starts.

Acknowledgment

The authors acknowledge financial support from the ExoMet Project (co-funded by the European Commission (contract FP7-NMP3-LA-2012-280421), by the European Space Agency and by the individual partner organizations). This project has received funding from the European Union's Seventh Framework Programme for research, technological development and demonstration under grant agreement No. 603-718.