WANG Jianhong

School of Engineering and Sciences,Tecnologico de Monterrey,Monterrey 64849,Mexico

Abstract:The problem of how to identify the piecewise affin system is studied in this paper,where this considered piecewise affin system is a special nonlinear system.The reason why it is not easy to identify this piecewise affin system is that each separated region and each unknown parameter vector are all needed to be determined simultaneously.Then,firstl,in order to achieve the identificatio goal,a multi-class classificatio process is proposed to determine each separated region.As the proposed multi-class classificatio process is the same with the classical data clustering strategy,the multi-class classificatio process can combine the firs order algorithm of convex optimization,while achieving the goal of the classificatio process.Secondly,a zonotope parameter identificatio algorithm is used to construct a set,which contains the unknown parameter vector.In this zonotope parameter identificatio algorithm,the strict probabilistic description about the external noise is relaxed,and each unknown parameter vector is also identified Furthermore,this constructed set is consistent with the measured output and the given bound corresponding to the noise.Thirdly,a sufficien condition about guaranteeing our derived zonotope not growing unbounded with iterations is formulated as an explicit linear matrix inequality.Finally,the effectiveness of this zonotope parameter identificatio algorithm is proven through a simulation example.

Keywords:piecewise affin system,zonotope parameter identification,linear matrix inequality.

1.Introduction

In this paper,our considered piecewise affine system can be regarded as a special hybrid dynamical system,as the piecewise affine system denotes the switching principle by using a collection of linear differential or difference equations,whose state space is partitioned by a finite number of linear hyperplanes.Generally hybrid dynamical systems belong to a class of complex dynamic systems,which include interacting discrete events and continuous variable dynamical systems.All above mentioned hybrid dynamical systems are important in lots of application fields,such as embedded systems,cyber physical systems,robotics,manufacturing systems and biomolecular networks,and they have recently been at the center of intense research activities in the control theory and artificial intelligence communities. However, in order to control a dynamical system,generally after modeling the considered plant by using the system identification theory,the process of system identification is finished and the process of control design is started.Moreover,the control performance depends on the mathematical model for the considered plant closely,i.e.,the accuracy of the mathematical model will affect the latter control performance.It means the goal of system identification is to provide a mathematical basis for the next controller design,and this is the reason of the name for“identification for control”.Because the considered plant and controller exist in the original closed loop system simultaneously,before identifying that unknown plant,the controller needs to be considered whether it is known or not in priori.

According to[1],the process of system identification consists of designing and conducting the identification experiment in order to collect the measurement data,selecting the structure of the model,specifying the parameters to be identified,and eventually fitting the model parameters to the obtained data.A large number of nonlinear model structures have been constructed to investigate their properties[2],where some real time fast convex algorithms are proposed to identify model parameters.Identification of the hybrid systems is an area that is related to many other research fields within nonlinear system identification,as such hybrid systems are sufficiently expressive to model many physical processes[3].The identification of the piecewise affine system is a challenging problem,as it involves the estimation of both the parameters of the affine sub-models,and the coefficients of the hyper-planes[4].Lauer et al.proposed to exploit the combined use of clustering,linear identification,and pattern recognition techniques[5].In[6],the sub-model parameters were described through probability density functions.The sum of the norms regularization strategy in[7]can be computationally heavy in case of appropriate step size.The piecewise affine system identification problem amounts to learning from a set of training data[8].This piecewise affine system identification problem is a nondeterministic polynomial(NP)hard problem in general[9].For the sake of simplicity, the sparse property is imposed in piecewise affine systems[10].The strengths of the piecewise affine system identification problem of[11]are the computational efficiency and the ability to be run both in a batch and in a recursive way.A three-stage procedure of a bounded error approach for parametric identification of piecewise affine autoregressive exogenous models was proposed in[12].The conversion of piecewise affine models from the state space input-output form was addressed by deriving necessary and sufficient conditions[13].A convex relaxation based on L1 regulation was proposed in[14]to approximate the underlying combinatorial problem.The statistical clustering technique in[15]computed the parameters of the affine local models,then partitioned the regressor space.

It is well known that in the piecewise affine system,the space is partitioned into many separated regions and a local linear form is used for each separated region.Thus the first step in identifying the piecewise affine system is to determine these separated regions.After the separate regions are given,the second identification problem is reduced to identify the linear submodels for each region.To deal with the above mentioned steps,we reformulate the problem of determining the separated regions as a multiclass classification problem,which can be solved by the classical first order algorithm from the convex optimization theory.A multi-class classification problem coincides with a data clustering process into the separated regions.When we identify the unknown parameter in each separated region,many classical identification algorithms can be used directly.However,all the classical identification algorithms hold in case that the considered noise may be a zero mean random signal.To relax this strict probabilistic description on noise,a zonotope parameter identification algorithm is investigated in the presence of bounded noise.Generally the zonotope parameter identification algorithm computes a set that contains the parameters,and this set is consistent with the measured output and the given bound of the disturbance.To keep our derived zonotope not growing unbounded with the iteration steps,some contracting properties must be imposed.

The rest of this paper is organized as follows.In Section 2,the problem setting and the piecewise affine system are presented.In Section 3,a multi-class classification problem based on the first order algorithm from the convex optimization theory is introduced to determine the separate regions.In Section 4,a zonotope parameter identification algorithm is proposed to identify the unknown parameters in the presence of bounded noise for each separated region.In Section 5,a very simple numerical example is used to illustrate the proposed algorithm.Finally,conclusions and comments about future research are presented in Section 6.

2.Piecewise affine system

Consider the following affine model as

whereu(t)andy(t)are input and output signals respectively,ai(i=1,...,na)andbj(j=1,...,nb)are the unknown models or system parameters,ande(t)is an external noise or disturbance.Two numbersnaandnbare priori known.

Rewrite(1)as a linear regression form,and define a regression vectorφ(t)as

where the unknown parameter vector is stacked as

For large enough ordersnaandnb,the affine model can be used to approximate any linear system,but it cannot capture any nonlinear properties,so to extend the affine model into the nonlinear system,our considered piecewise affine system is obtained.At this time,the unknown parameter vectorθis dependent of the region in the regression space,where the regression vectorφ(t)lies.Thus the regression space can be divided intonseparated regionsR1···Rn.Let us define the piecewise affine system as

where the parameter vectorθidepends on its corresponding separated regionRi.The identification problem for the piecewise affine system is reformulated as that,after the output and input observed data point{u(t),y(t)}is collected by using some sensors,how to identify those unknown parameter vectorsθi(i=1,...,n)Due to the fact that the regression vectorφ(t)is constituted by the output and input observed data point{u(t),y(t)},the first step is to determine which region the regression vector belongs to.

3.Multi-class classification process

Becausenseparated regionsR1···Rnexist,the determi-nation about which region the regression vector lies is in conjunction with a multi-class classification process.

ObservingNinput-output data pointsz(t)(t=1,...,N)as follows:

whereNdenotes the number of observed input-output data points,and each data pointz(t)is included in one ofnnonoverlapping classes, along with labelsλt∈Rn,whereRnis the real number set with dimensionn,and basic quadrants inRn,and the index of the only nonzero entry inλtis the number of class to whichz(t)belongs.

A multi-class analogy of the standard linear classifier is built as follows:a multi-class classifier is specified by a matrixAand a vectora∈Rn.Given the input-output observed data pointz(t),compute thendimensional vectorAz(t)+a,identify its maximal component,and treat the index of this component as our guess for the serial number of the class to whichz(t)belongs.

Set=1?λtas the component ofλt.Given a data pointzand the corresponding labelλ,let us set

Ifi?is the index of the only nonzero entry inλ,then thei?th entry inhis zero.his nonpositive if and only if the classifier,given byA,aand evaluated atz,recovers the classi?ofzwith a margin 1,i.e.,we have On the other hand,if the classifier fails to classifyzcorrectly,that is,

A nonnegative function is obtained,and it always vanishes for the pairs(z,λ).The pairs are quite reliably(with margin1)classified by(A,a),and equal to or larger than 1 for the pairs(z,λ)withznot classified correctly.Thus,the following function is simplified as

This expectation being taken over the whole distribution of the pairs(z,λ)is an upper bound on the probability for the classifier(A,a)to misclassify a data point.What we would do is to minimizeF(A,a)overAanda.To achieve this mission,sinceF(A,a)is not observable,we replace the expectation by its empirical counterpart

For the sake of simplicity,imposing an upper bound on some normAofA,an optimization problem is obtained.

A natural choice of the normAis the maximum of theA2norm.Once optimization variablesAandaare obtained,then the linear classifierAz(t)+ais get.From the above multi-class classification process,after a data point is collected,we cluster it with a linear classifier.Thus based on the above linear classifier,all data points can be clustered together,then those data points clustering together as a class can be used in the second identification problem for an unknown parameter.

4.Zonotope parameter identification algorithm

After all collected input-output data points are clustered as thesenclasses,then these data points belonging to the same class can be used to identify an unknown parameter.Here we only rewrite the following piecewise affine system in theith separate region.

The goal of this section is to identify the unknown parameter vectorθiin case of the unknown but bounded noise.Based on this unknown but bounded noise,one of the new identification approaches,the zonotope parameter identification algorithm,is chosen to identify the unknown parameter vectorθi.This identification algorithm obtains a set iteratively that includes the parameters consistent with the measured output signal and the given bound of the disturbance or noise.The zonotope is used to represent this obtained set.The reason of using the zonotope is that a zonotope is an affine map of a unitary hypercube.

Observing(13)again,ase(t)represents the considered disturbance or external noise,and assume this external noise belongs to a bounded set,i.e.,

whereσ∈R is an upper bound and external noisee(t)is unknown,but it has a known bound in priori.

From the set membership identification theory,given a set of measured outputs,the feasible solution set(FSS)for the unknown parameter is defined as the set of parameters that are consistent with measured outputs and the given bounds of the considered external noise.More precisely,the following definitions are given through this whole zonotope parameter identification algorithm.

Definition 1FSS

Suppose the observed input-output pairs{y(t),φ(t)}(t=1,2,...,N)are given.The unknown parameter vectorθiis regarded to belong to the FSS if there existsθi,such that

Definition 2Information set

Given the observed input-output pairs{y(t),φ(t)}(t=1,2,...,N)at time instantt,the information setItis deemed as a set of all feasible parameters,which are consistent with the linear regression model(13),the measured outputy(t)and the known bound at time instantt,namely,

Geometrically,Itrepresents a strip,which is consistent with the observed input-output pairs{y(t),φ(t)}(t=1,2,...,N).

The FSS at the next time instantt+1,denoted as FSSt+1,can be computed exactly from the one corresponding to time instanttby the following iterative recursion:

Because it is difficult to compute the FSS,an outer bound of the FSS can be defined again.

Definition 3Approximated FSS(AFSS)

An AFSS is a set that satisfies FSS.The intersection FSSt∩Itis approximated by means of the intersection between a zonotope and a strip at time instantt.

Definition 4Zonotope of orderm

Given a vectorp∈Rna+nband a matrixH∈R(na+nb)×m,a zonotope of ordermis a set withn1=na+nbdimensional vectors.

whereHBmis a linear projection ofBminton1=na+nbdimensional parameter space,Bmis a unit hypercube of the orderm,and⊕denotes the Miniowski sum.

Using the above definitions and the AFSS on the intersection(17),then we have

If in(19),FSStis denoted by a defined zonotope,and the information setItis a strip,then a family of zonotopes,bounding the intersection between a zonotope and a strip,are derived as the following obtained Theorem 1.

Theorem 1Suppose a zonotope is used to denote an FSS at time instantt.

and the information set or a strip is given as

and a scalarγdefines the following variables as

whereIis an identity matrix.Thus we have

A scalarγ∈R is chosen by an optimization based method,through minimizing the volume of the obtained zonotope.Now the minimization of the P-radius of a zonotope is applied,as the P-radius criterion allows to guarantee the non-increasing property of the guaranteed zonotope at each time instant.It tells us that to guarantee the AFSS not growing unbounded with iteration steps,the following inequality relation between two neighboring zonotopes is imposed to guarantee that property.

whereβ∈(0,1]is a contraction rate,andltis a chosen parameter or the P-radius of the zonotope parameter estimation set at time instantt,which is defined by

wherePis ann1-dimensional positive definite matrix.

After substituting(25)into(24),we have

Expanding(26)to obtain the following inequity:

Due to the recursion property of(γ)in(22),we continue to compute

where we set two new defined variables

Applying(28)in(27),we get

Formulating the above inequality to simplify it as

A sufficient condition for(31)to hold can be rewritten as the following linear matrix inequality:

Using the definition and the property of the positive definite matrix,we rewrite it as

The linear matrix inequality in(33)defines the feasible solution for scalarγ,i.e.,γcan be computed by solving the following eigenvalue problem:

After solving the above convex optimization algorithm,then based on this optimal scalarγ∈R,a zonotopic outer approximation of the intersection between a zonotope and a strip is obtained by using the matrix inequality optimization strategy.

Finally,our zonotope parameter identification algorithm is formulated as follows.

Algorithm 1Zonotope parameter identification algorithm

Step 1Obtain measured input-output data points and construct the regressor vectorφ(t)according to(5).

Step 2Build a strip that bounds the consistent parameters,i.e.,it is similar to the following information set:

Step 3Construct a zonotope

to denote the FSS at time instantt.

Step 4Compute the intersection between a zonotope and a strip at time instanttand obtain a new zonotope at the next time instantt+1:

to denote the AFSS at time instantt+1.

Step 5Choose an optimal scalarγthrough solving a matrix inequality optimization strategy according to(34).

Step 6Repeat the above steps and terminate the recursive algorithm when the P-radiusltis zero,then denoteas the vector in the last zonotope,so the unknown parameter vectorθiis given by

It is similar to applying the above six steps to identify another unknown parameter vector.

Based on the linear matrix inequality(33),it corresponds to the contracting properties between two neighboring zonotopes,then this linear matrix inequality can be regarded as a sufficient condition to guarantee that the volume of the obtained zonotope will be decreased as the iteration steps increase.It means that after the above six steps are stopped,the volume of the final zonotope will be sufficiently small,then the center of the final zonotope can be chosen as the parameter estimation.Therefore,the convergence consistency of the proposed zonotope parameter identification algorithm can be guaranteed by the added contracting properties.

5.Numerical example

In this numerical example section,a special piecewise affine system is used to prove our ideas,such as the two class classification process and the zonotope parameter identification algorithm.This simple piecewise affine system is given as follows:

where the condition that the regression vectorφ(t)satisfiesφ(t)>0 means all the elements in the regression vectorφ(t)are positive.Furthermore,similarly the condition that the regression vectorφ(t)satisfiesφ(t)0 means all the elements in the regression vectorφ(t)are negative or zreo.

In(36),the regression vectorφ(t)and two unknown parameter vectorsθ1andθ2are described as

The input signalu(t)is used to excite the piecewise affine system(36),then the actual input signal is plotted in Fig.1(a).We use its approximated input signal to replace the actual input signal in our simulation,because it is not useful in practice,where the approximated input signal is similar to the sinusoidal signal in Fig. 1(b). Then we collect the output signaly(t)by using some sensors,the observed output signal is plotted in Fig.2.

Fig.1 Applied input signal

Fig.2 Observed output signal

Firstly,our mentioned multi-class classification process is reduced to two class classification problems.After collecting one input-output data point(y(t),φ(t)),the region,which this data input-output point belongs to,is determined.In the whole simulation process,the number of given input-output data points is set to beN=500,i.e.,these 500 data points belong to one of the two classes.The detailed clustering process can be seen in Fig.3,where the data points are clustered around two ellipsoids.As from three points deviate away these two ellipsoids,then they are regarded as outliers and they are deleted in our simulation.From Fig.3,all data points are classified correctly,except those three data points.

Fig.3 Whole clustering process for estimated collected data

Secondly,in the presence of unknown but bounded external noise,choose its upper bound as

and all initial parameter values are chosen as

The introduced zonotope parameter identification algorithm is used to identify those two unknown parameter vectors.Using the above six steps to construct a sequence of candidate zonotopes iteratively,we see that after 20 iterations,these candidate zonotopes are given in Fig.4 and Fig.5.

Fig.4 Candidate zonotopes iteratively for the first optimal parameter vector

Fig.5 Candidate zonotopes iteratively for the second optimal parameter vector

In Fig.4,the black star denotes the optimal parameter vector to beθ1=[7 2]T,and a sequence of candidate zonotopes are generated by the zonotope parameter identification algorithm,which includeθ1=[7 2]Tas their interior points.The volumes of these candidate zonotopes decrease with iterations,i.e.,certain contracting properties are guaranteed.Generally,the other unknown parameter vector corresponding toθ1=[7 2]Tcan be chosen as the center of the smallest zonotope.Furthermore,the black star is the optimal parameter vector asθ2=[2 0.5]Tin Fig.5,and the results are similar to those in Fig.4.

From Fig.3,all data points are classified correctly,so Fig.3can be used to measure the performance of the multiclass classification process.

Fig.4 and Fig.5 are used to measure the performance of the zonotope parameter identification algorithm,and the black star is the optimal parameter vector.After running the zonotope parameter identification algorithm,a sequence of zonotopes are obtained.Moreover,the optimal parameter vector is an interior point or a center of the smallest zonotope.

6.Conclusions

In this paper,we study the problem of identifying a special nonlinear system,the piecewise affine system,which combines linear and nonlinear properties.As this piecewise affine system is piecewise affine in the regression space,the parameter vector depends on the region in the whole considered regression space.The separated regions are determinedas a multi-class classification problem,which can be solved by the classical first order algorithm from the convex optimization theory.In the presence of unknown but bounded external noise,the zonotope parameter identification algorithm is introduced to identify the unknown parameter vector in each separated region.Generally,the finite sample property of the zonotope parameter identification algorithm is our ongoing work.