Anicet Kouomou Choupo

Laure Berti-Équille

Visual Feature Mining for Adapting Query-by-Example over Large Image Databases

This paper proposes a strategy for automatic selection and scheduling of visual features as search criteria that are relevant to the query-by-example on a large still-image database. This method is composed of the two main steps: the indexing and the retrieval processes. The indexing step uses K-mean clustering and association rule discovery as dimensionality reduction techniques on the descriptor values. The retrieval step is designed to order the query execution plans for speeding up the content-based retrieval over the image database. At this step, query-by-example processing is adapted in order to propose instantaneous and intermediate results that are progressively merged together with the advantage, for the users, on one hand, not to wait until the whole database has been processed by similarity search and, on the other hand, to allow them to stop the current execution of the query without losing the first partial results. We evaluate our method by comparing query execution time and result quality with the sequential search on all the low-level descriptors available in the image database. Our experiments show that we can get a result similar to the final one in less than half the time of the sequential search, which is a promising result for optimizing content-based retrieval.

Introduction

Content-based retrieval in very large multimedia databases exploits the indexation of various intermediate descriptions of the contents whose computing costs can be considerable. For each media type (video, text, audio, image), the set of potentially relevant descriptors is often very large. Many descriptors are proposed in the literature and standardized (e.g., MPEG-7, MPEG-21 [START_REF] Kosch | Distributed Multimedia Database Technologies Supported by MPEG-7 and MPEG-21[END_REF], TV AnyTime). A still-image database can be represented at the pixel level in various ways [START_REF] Smeulders | Content-based image retrieval at the end of the e arly years[END_REF]: by local visual features or global descriptors of color, texture, layout or shape. However, for answering a query-by-example, it is sometimes useless to search the entire database by computing similarity distances over every available low-level feature, because the discrimination power of the features (and their filtering capacities) often depends on the size of the database (i.e., some features may be very discriminative for small databases and they may be advantageously used for filtering the results, but they lose their property when they are flushed in millions of images).

Another major drawbacks of content-based retrieval based on sequential similarity search is that the query must be carried out in an exhaustive way over the whole database, because of the poor efficiency of indexation scheme of very large databases of images described by high-dimensional features. The consequence is an unacceptable waiting time for the user, until all the images of the database are compared to the image-query with a similarity distance. Moreover, any stop during the query execution has, as a consequence, the loss of all the retrieval information due to the lack of recovery strategies, forcing the user to restart the query again.

Contrary to traditional databases where many works have been carried out on query optimization and more recently on adaptive query processing [START_REF] Gounaris | Adaptive query processing[END_REF][START_REF] Manolescu | Adaptive and self-tuning query processing[END_REF], very few works have been proposed on multimedia content-based retrieval optimization. In our paper, we propose a strategy for automatic selection and scheduling of the search criteria (i.e., the visual features) that are relevant to a given query-byexample on a large still-image database. We use techniques of clustering and discovery of association rules on low-level descriptor values as dimensionality reduction techniques specifically applied to query-byexample optimization. We also present how the queryby-example processing can be adapted to propose instantaneous and intermediate results which are progressively merged, with the advantage, for users, on one hand, not to wait until the whole database has been processed for finding the most similar images to the submitted image-query and, on the other hand, to allow them to stop the current execution of the query. We evaluate our method on a still-image database by comparison with the query performance and result quality obtained by the sequential search over the whole set of available features.

The rest of the paper is organized as follows: in section 2, we present the related works using discovery of association rules for indexing and searching images. We present then, in section 3, our method of automatic selection of the search criteria, and then we formalize, in section 4, the progressive adaptation of query-by-example execution plans. In section 5, we describe the experiments that validate our approach. Section 6 offers concluding remarks.

Related works

Content-based retrieval of images consists in searching the nearest neighbors of a query-by-example among all the available images indexed by multidimensional descriptors in the database (e.g., by MPEG-7 image descriptors that are vectors with 7 to 84 dimensions). Indexation techniques that are either based on data partitioning (such as R-Tree [START_REF] Guttman | R-trees: A dynamic Index Structure for Spatial Searching[END_REF]) or on space partitioning (such as k-d-Tree [START_REF] Bentley | Multidimensional binary search in database applications[END_REF] or GridFile [START_REF] Nievergelt | The GridFile: An adaptable, symmetric multikey file structure[END_REF]) remain adapted to low-dimensional vectors. The performances are very quickly deteriorating when the dimension of features increases. New indexation scheme have to be defined and adapted to the vectors of high dimension as well as approximate searching methods to improve the query performance.

In this context, several methods exploit, among the data mining techniques [START_REF] Zhang | Image mining: issues, frameworks and techniques[END_REF], the discovery of association rules in the context of multimedia contentbased retrieval [START_REF] Djeraba | Association and content-based retrieval[END_REF][START_REF] Ordonez | Discovering association rules based on image content[END_REF][START_REF] Zaïane | Mining recurrent items in multimedia with progressive resolution re?nement[END_REF][START_REF] Kouomou-Choupo | Multimedia Indexing and Retrieval with Features Association Rules Mining[END_REF]. Djeraba [START_REF] Djeraba | Association and content-based retrieval[END_REF] uses an indexing technique that combines the construction of clusters and the determination of association rules. Several subgroups of images (clusters) are thematically classified with labels (such as "animal", "plant"...). The aim is to characterize and labellize these image groups by association rules. At the query time, an analysis of the query starting from the association rules drives the choice of the images subgroups for the sequential search. The work of Djeraba [START_REF] Djeraba | Association and content-based retrieval[END_REF] aims at the improvement of the quality of results from a semantic perspective without merging the results from several visual descriptors and without considering the query performance. Moreover, the approach imposes the creation of a thesaurus for the semantic labellisation of the clusters.

In our approach, the number and the type of descriptors are not limited and no labelling is required, because our objective is clearly to technically improve the query performance at the pixel level with no ambition on the semantic level. At the indexing step, our strategy combines cluster computation and extraction of association rules. Thus, it is entirely nonsupervised and is appropriate for very large image databases.

Since Apriori [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF], many algorithms for discovery of association rules have been proposed in the literature, they are very effective for classical transactional and relational databases whose structure is well defined. But their application to the images requires some adaptations. An idea consists in transforming the image descriptions and in applying the traditional techniques of association rule discovery. An image can be identified as a transaction and the various regions that compose it as objects [START_REF] Ordonez | Discovering association rules based on image content[END_REF]. Under certain conditions, the repetition of objects may carry information. Zaïane et al. [START_REF] Zaïane | Mining recurrent items in multimedia with progressive resolution re?nement[END_REF] proposed a definition of association rules with recurrent objects as the following implication:

α 1 P 1 ∧ α 2 P 2 ∧ ... ∧ α n P n → β 1 Q 1 ∧ β 2 Q 2 ∧ ... ∧ β m Q m
where P i and Q j (with i ∈ [1..n] and j ∈ [1..m]) are image descriptors and α i , β j are integers indicating the number of occurrences of the descriptors. The MaxOccur algorithm described in [START_REF] Zaïane | Mining recurrent items in multimedia with progressive resolution re?nement[END_REF] is an adaptation of Apriori for the extraction of association rules with recurrent objects.

In our approach, we propose an application of the association rules for indexing and querying by example still-image databases. Our approach lies within the scope of the transformation of multimedia data and the application of the traditional techniques of discovery of association rules. We use several MPEG-7 image descriptors and the images are gathered into clusters for each descriptor. We consider an image as a transaction and a cluster identifier of each descriptor as an attribute. The problem of recurrent objects does not arise since the clusters are identified in a single way for each descriptor. The main contribution of this paper compared to our previous work [START_REF] Kouomou-Choupo | Multimedia Indexing and Retrieval with Features Association Rules Mining[END_REF] is the introduction of progressive query-by-example in order to propose intermediate results that are progressively merged together until the end of the query execution over the whole database. This extends the recent work of Kiranyaz and Gabbouj [START_REF] Kiranyaz | A novel multimedia retrieval techique: progressive query (why wait?)[END_REF] on progressive query which was limited to the periodic execution of the same sub-query on portions of multimedia databases (images or videos) with no emphasis neither on scheduling the data subsets to process, nor on merging results from heterogeneous descriptors. The scalability and the computational complexity of the approach were not studied in [START_REF] Kiranyaz | A novel multimedia retrieval techique: progressive query (why wait?)[END_REF] and the size of the databases or of the database portions targeted by the sub-queries were not mentioned. Our study focuses on theses aspects for improving the query-by-example performance without deteriorating the quality of results compared to the sequential search.

Features mining and scheduling

Let us now present the principle of our method of automatic selection of the search criteria for the queryby-example on large still image databases. It includes: 1) the indexing step, based on clustering and discovery of association rules between the visual descriptors, 2) the retrieval step, based on selection and use of rules in order to choose the first-rank descriptors as search criteria (i.e., the most relevant for the query in terms of result quality and the most efficient for the query performance).

Indexing process

Off-line indexing process is based on the organization of the still-image database by computing the set of descriptor values for the characterization of the images. The image database is then gathered into several clusters using a K-means-like algorithm for each type of computed descriptors. The principle of the algorithm is as follows: data are partitionned into k clusters. We determine the number of clusters (k) empirically (see section 5.1). Each cluster centroid is firstly initialized by one image chosen randomly. The algorithm assigns each image to the cluster which the centroid is the nearest. It calculates new centroids and repeats the operations until no image are re-assigned (convergence).

Consider the image database B with N images, noted I 1 , I 2 , ..., I N . Let D = {d 1 , d 2 , ..., d m } be the whole set of m available descriptors. We note (n j (I i ), d j ) the cluster of the descriptor d j which the image I i belongs to and we note B, the image database such as:

B ={I|I={(n 1 (I),d 1 ),(n 2 (I),d 2 ),..

.,(n m (I),d m )}}

We apply the Apriori algorithm [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF] for discovering association rules on the image database B and for obtaining the implications between the clusters of descriptors. We worked with a database of 30411 still images coming from a photo agency and described by the following MPEG-7 descriptors: ColorLayout (CLD), ScalableColor (SCD), HomogeneousTexture (HTD), EdgeHistogram (EHD) and RegionShape (RSD).

At the end of the indexing process, we obtain a set of clusters for each descriptor d i and a set of association rules computed by the Apriori algorithm which identifies the relations between different clusters of the database B such as the rules r1 and r2 as examples: where <0.1,66.1> are respectively the support and the confidence values of the rule r1, expressed as percentages (idem with the support and confidence <0.1,55.2> of r2). Intuitively, semantics of a rule r selected for the q uery-by-example is: the nearest neighbors of the image-query that belong to all the clusters that are on the left-hand side of r, probably belong to the clusters that are on the right-hand side of r too.

We then use the most relevant association rules to schedule the sequential search on the ordered list of clusters, starting first with clusters that have the best selectivity (defined in section 4.1.) and that are on the left-hand side of selected association rules.

Content-based retrieval process

When the user submits a query-by-example to the system, his goal is to find all the images similar to the image-query according to several visual criteria. The user may know how to choose the visual descriptors as search criteria. But generally, he does not have any idea of what are the most discriminative descriptors for his query. In many cases, it is useless to search images on all the features already computed in the database. Our goal is to determine the priority order on the descriptors (and on their clusters) that are the most relevant, especially in the context of progressive queries that can provide intermediate and instantaneous results during the query execution and before the end of the exhaustive processing of the database by similarity search.

Given an image-query Iq, the system computes, for each descriptor d j , a measure of selectivity of each cluster. The selectivity measure of a cluster depends on the size and the density of the cluster, and on its closeness to the description of the image-query relative to a given descriptor. The end of what we call a searching phase corresponds to the presentation of an intermediate result. The system determines, for the given searching phase, the Top M clusters to start with the similarity search and retrieves the nearest neighbors of I q .

For the query processing using the association rules, the strategy is to first ignore the clusters present on the right-hand side of the selected rules and their corresponding descriptors. In the previous example, consider that the rules r1 and r2 are selected, then the query execution will first ignore clusters #29 and #8 of the descriptor CLD because they are in the righthand side of the rules.

Adaptating query-by-example processing

Content-based retrieval generally requires the exhaustive processing of the whole image database before providing a result to users. Our goal is to improve the query processing while proposing: 1) a strategy of query-by-example execution plans which defines an optimal scheduling of the clusters to process with the similarity search, 2) the possibility to provide to users instantaneous results which are progressively refreshed and merged during the query execution, 3) the possibility for users to stop t he current query execution if they are satisfied with the last intermediate result retrieved by the system.

The general principle is presented in the Figure 1. The indexing process is represented by the two first steps consisting in (1) the computation of the descriptor values and the clustering and (2) the generation of association rules (such as the rule R1: C33 ∧ C23 ->C12). The retrieval process starts at the step (3), a query-by-example I q is submitted at the initial time T o , and it is decomposed into several subqueries targetting specific portions of the database (i.e., the Top M clusters) selected by the selectivity measure, and the priorities given by the association rules extracted beforehand at the indexing step (4). In Figure 1, the cluster C 33 is the nearest to D 3 (I q ), the description of the image-query relative to the D 3 descriptor and it belongs to the first association rule R1 previously generated. In this example, considering that the clusters C33 and C23 have a good selectivity, they will be selected as the first-rank clusters to process by the first subquery. At step (5), t he intermediate results are progressively merged, updated and refined during the total query execution time over the whole image database and sent to the user (at T 1, T 2, T 3 ). The advantage is to provide instantaneous results to the user during the query execution. Moreover, the user will be able to stop the current execution (at T stop ) keeping the previous intermediate results. When the whole database has been processed, the last instantaneous result is merged with previous instantaneous results and is sent as the final result to the user at T f .

k j D card 1 i D, d C B j i ij .. 1 ), ( .. = = ∈ ∀ = U
An image belongs to the database if its description for each descriptor present in the database belongs to a cluster.

C I ( d , C D d f i B I ij i ij i ∈ ∃ ∈ ∀ ∈
) ,

Query-by-example.

A query-by-example I q = (n q , O q , W q , D q ) for the multidimensional space S consists of the following information:

-The number n q of points in I q -A set of n q points { }

) ( ) 1 ( , , q n q q q O O K = Ο in the d S - dimensional feature space S -A set of n q weights { } ) ( ) 1 ( , , q n q q q w w K = W
, the i th weight ) (i q w being associated with the i th point

) (i q O ( 1 , 0 1 1 ) ( ) ( = ≥ ≥ ∑ = q n i i q j q w w ) -A distance function D q , which, given a point O
in the space S, returns the distance between the query and the point. We assume D q to be a weighted L p metric, i.e., for a given value of p, the distance between two points T 1 and T 2 in S is given by:1

( ) ( ) [ ] [ ] ( ) p d j p j q q s j T j T T T D 1 1 2 1 2 1 ,       - = ∑ = µ
where ) (j q µ denotes the weight associated with the i th dimension of S (

1 , 0 1 1 ) ( ) ( = µ ≥ µ ≥ ∑ = S d j j q j q
). D q specifies which L p metric to use (i.e., the value of p) and the values of the dimension weights. We use the point distance function D q to construct the aggregate distance function D q (I q ,O) between the multiple query points O q and the point O (in S). D q (I q ,O) is the aggregate of the distances between O and the individual points

q i q O Ο ∈ ) ( : ( ) O O D w O I i q q n i i q q q q , ) , ( ) ( 1
) ( ∑ = = D
We use an equally weighted sum as the aggregation function but any other function can be used as long as it is weighted and monotonic.

Searching phase. The i th searching phase corresponds to the similarity search processing over the set of i th rank clusters for each descriptor.

Selectivity of clusters.

The selectivity of the cluster C for a given query-by-example I q is a function combining the closeness of the cluster to the imagequery (previously defined as the distance function D q ), the size and the local density of the cluster. Selectivity measure of a cluster C depending on the query-byexample I q is noted Selectivity(C, I q ) and defined as follows:

( ) ( )

(C) . ) ( max ) ( 1
)) , ( ( max )
, ( 1 , density C size C size C I dist C I dist I C y Selectivit j j j q j q q γ β α +           - + +           - = 1 0 , 0 , 0 = γ + β + α ≥ γ ≥ β ≥ α and with
. size(C) is the size of cluster C, dist(I q ,C) is the distance of I q to the centroid of cluster C and density(C) is the density of cluster C at its centroid. We evaluate the density using an index defined such as:

( ) chosen such as 0 ≤ Selectivity(C, I q ) ≤ 1. The priority for processing a cluster C is high for a given query-byexample I q if Selectivity(C, I q ) is close to 1.

C I I C I dist C size C I dist C I dist C density j i C size i i C size i C size j j i ∈ × - × - = ∑ ∑ ∑ = = = , with ) , ( 1 ) ( 2 ) , ( ) , ( ) ( ) ( 1 ) ( 1 )

Association rule between clusters.

An association rule r between several clusters of descriptors, noted C ij , C i'j' , C i"j" , is defined as follows:

> < → ∧ ∧ conf supp, C C C r j i j i ij " " ' ' : K with i,i',i"=1..card(D), i" i' i ≠ ≠
and j,j',j"=1..k Semantics of the rule r is: an image whose description relative to the descriptors d i and d i' belongs respectively to the clusters C ij and C i'j' on the left-hand side of the rule r, probably belongs to the cluster C i"j" (on the right-hand side of the rule r) , with supp and conf as support and confidence values of the rule r.

(

) (3) (4) (5) (6) (1) 2
Selection of association rules between clusters. For a given query-by-example I q , the clusters are selected depending on their selectivity measure at the i th searching phase. For the i th searching phase of I q , the set of the Top M clusters is noted:

) ( q i M I TopC .
The corresponding set of selected descriptors is noted: ) ( q i M I TopD after the rule selection. An association rule is selected for query-by-example I q , at searching phase k if its support and confidence are higher than given thresholds and if the set of clusters composing the rule, noted Cr, is such as:

U k i q i M r I TopC C .. 1 ) ( = ⊆
When a rule is selected, the query processing will first ignore the clusters that are on the right-hand side of the rule.

Query-by-example execution plan.

A logical query execution plan P for the query-by-example I q is composed of the list of clusters C ij to process for retrieving the most similar image according to all the descriptors D of the database. A query execution plan P for I q is composed of several subplans whose results are merged with the fusion function noted "o " as follows: after the subquery execution depending on a frequency, noted freq. We suppose a partial order on the initial, intermediate and final times during the execution time of the query such as:

K o o ) d (I P ) d (I P D I P q, q, q 2 2 1 1 ) , ( ←
) m q, m i q, i d (I P ) d (I P o K o o P i (I q ,d i )
} { } K o K o K ) ,C , C (I P ) ,C , C (I P D I P k q, k q, q 2 21 2 1 11 1 ) , ( ← { }) , , ( 1
T 0 < T 1 < T 2 <…<T f.
Frequency of a progressive query. The frequency of a progressive query is the ratio of the required number of intermediate results and the number of minimal subqueries (i.e., the number of clusters). A minimal subquery corresponds to the similarity search over one cluster of descriptor. Frequency is defined by:

Nc Ni freq 1 + =
with Nc : the number of minimal subqueries (i.e., the total number of clusters) and Ni : the number of required intermediate results (0 ≤ Ni ≤ Nc-1). For the default frequency freq = 1, the intermediate results are sent to the user after the merging of the results of each minimal subquery. The corresponding progressive query on n clusters is:

) ( ) ( ) ( ) , ( f n 2 2 1 1 0 T Q T Q T Q 1 T Q o K o o =
In Figure 1, the frequency is freq = 4/9, with 3 intermediate results and 9 minimal subqueries (i.e., 9 clusters).

Instantaneous result. An instantaneous result of a

progressive query Q , is the result of a subquery on a portion of the database (i.e., one or a list of clusters of descriptor). It is obtained by the fusion of the previous intermediate results.

Final Result. The final result of a query is obtained:

when the whole image database has been processed to answer to the initial query-byexample (i.e., when all the clusters have been processed by similarity search), -when the query execution has been volontarily stopped by the user.

Generation and selection of query plans

Among all the possible query execution plans, query processing selects an optimal query execution plan that is executed by the query engine, which implements an execution model and produce the query result. Bushy plans offer the best opportunities to minimize the size of intermediate results. Hence, we represent query-by-example execution plan as an operator bushy tree. Nodes of the tree represent atomic physical operators and edges represent dataflow. A blocking edge indicates that the data is entirely produced before it can be consumed and an operator with a blocking input must wait for the entire operand to be computed and materialized before it can start. A pipelinable edge indicates that data can be consumed "one vector of descriptor values at a time". Therefore,

a pipelinable input (represented as a dotted line) can be consumed as soon as it has been produced. Figures 2a and2b show the two cases of query execution plan corresponding to the query-by-example over the nine clusters of three descriptors given as example in Figure 1: the case of a traditional sequential search (Figure 2a) and the case of progressive query including cluster selection and association rules (Figure 2b). Two main classes of operators are considered in these plans: 1) binary symmetric operators that have one blocking inputs and one pipelinable input ( such as rank for the same descriptor) or two blocking inputs (such as fusion for heterogeneous descriptors), and produce a pipelinable output, 2) unary operators (such as scan, mat). We introduce the unary operator mat in the query plan before each blocking edge to indicate that the materialization of intermediate results can occur at that point (in memory or on disk). The first plan (Figure 2a) takes sequentially all the clusters of each descriptor before returning the result. It's written such as:

P1(d1,d2,d3) <-(C11oC12oC13oC21oC22oC23oC31 oC32oC33)(Tf)
The second plan (Figure 2b and also represented in Figure 1) is driven by cluster selectivity and discovered association rules and it returns three intermediate materialized results before the end of the query execution over the whole database.

It's written such as:

P2(d1,d2,d3) <-(C33oC23)(T1) o (C13oC21)(T2) o(C32oC31)(T3)o(C11oC22oC12)(T4=Tf)
Our goal concerning the execution strategy is to interleave the processing or the (partial) materialization of data from several clusters by selecting, scheduling and executing several query fragments concurrently in order to minimize the response time. Consider the query-by-example I q submitted to the image database and P Q the set of all possible plans for the query-by-example, the search space for retrieving the N top plans is the set of size N of all the subsets of

P Q . S(Q) = { P' ⊆ P Q | |P'| = N }
To retrieve the top N plans including the cluster selection step, we are currently adapting the Branch & Bound algorithm [START_REF] Narendra | A branch and bound algorithm for feature subset selection[END_REF]. And we introduce the notion of upper bound limit for the plan P defined by the function upperbound(P) such as :

)] ' ( [ max ) ( ' P y selectivit P upperbound P P ⊇ ≥

Fusion of intermediate results

For a given searching phase, the similarity search is first done over a selected subset of descriptors {d 1 ,d 2 ,…,d m1 } ⊆ D with m 1 ≤ card(D). Consider l j , the list of query results for the descriptor d j ranked in the decreasing order of similarity distance (1 ≤ j ≤ m 1 ). For computing the final result by merging the different ranked lists of results per descriptor, we define a merging score for the image I such as:

( ) ( ) ( ) ( )         + = ∑ = 1 1 1 2 1 m j d d f I S I f m I S j j with ( ) [ ] 1 , 0 ∈ I S j d and ( )    ∉ ∈ = j l I if 0 1 j d l I if I f j ( ) I S j d
is the score of I for the descriptor d j . It is proportional to the similarity distance between the query-by-example I q and I . Similarity between two images is the distance between the respective multidimensional vectors of the descriptors. We use the distances proposed by MPEG-7 in the definition of the descriptors. Merging Top N lists from heterogeneous descriptors (with different vector dimensions) is a difficult problem and we study other fusion functions [START_REF] Berretti | Ischia, Merging results for distributed content-based image retrieval[END_REF][START_REF] Fagin | Efficient similarity search and classification via rank aggregation[END_REF]

Experimental results

The method of automatic selection and ranking of the visual descriptors as search criteria for the queryby-example processing presented above is implemented in C++ on Linux. We're currently working with a database of 30411 heterogeneous still images coming from a photo agency. We will soon consider the processing of several hundreds of thousands of images.

At the indexation step, we exploit several MPEG-7 descriptors for color ( ColorLayout, ScalableColor), for texture ( HomogeneousTexture, EdgeHistogram) and for shape ( RegionShape). For each MPEG-7 descriptor, we gather the images into clusters with a K-means-like algorithm. In this work, we observed that very large clusters (containing many images) mostly appear on the right-hand side of the association rules in order to keep the level of confidence high. The determination of the number k of clusters is difficult. Compared t o other works [START_REF] Fernandez | Intelligent Image Clustering[END_REF], we adopt an experimental approach in which the homogeneity of the size of the clusters determines the choice of the number of clusters to consider. That is, we do not fix arbitrarily the number of clusters but we determine it depending on the image database population and on the number of robust association rules we want to consider (see Experiment 1).

At the retrieval step, we study the contribution of association rules (see Experiment 2) and the selection of clusters based on the selectivity measure (see Experiment 3). In these experiments, we use 100 images as queries-by-examples, each belonging to the database and we search for the Top 15 nearest neighbors. We measure the average time and the average result quality. In our approach, the result quality at each searching phase for a given progressive query-by-example is defined as the number of common images, present both in the intermediate result and in the result obtained at the end of the sequential and exhaustive search over the whole set of descriptors of the image database. In other words, the quality of result is optimal when the quality is the same as obtained by sequential search (i.e., retrieving the same images). In this measurement of quality, we are not focused on the order of the retrieved images belonging to the result list but only on their presence/absence that could be satisfactory enough for the end-user at each searching phase.

Experiment 1: choosing indexing parameters

The goal is to study the parameters of indexing such as the number of clusters to fix, the thresholds of the support and of the confidence. First, we calculate, for a given value of the number of clusters, a quantity characterizing the distribution of the size of clusters around the average size. The higher this quantity is, the more the size of clusters is far from the average. Figure 3 shows the variations of the computed distribution against the number of clusters for each of the five descriptors: ColorLayout, ScalableColor, HomogeneousTexture, E dgeHistogram and RegionShape (respectively noted CLD, SCD, HTD, EHD, and RSD).

Figure 3. Indexing parameters: the number of clusters

We observe that, when the number of clusters is less than 10, the clusters are very disparate. For more than 20 clusters, the size of clusters significantly approaches the average. Hence, the number of cluster must be sufficiently large so that the size does not deviate significantly from the average. This is true for all the descriptors since they have the same distribution of the images in the clusters. For this reason, we can choose the same number of clusters for all the descriptors and, for this database, we fixed the number of clusters for each descriptor to 30 clusters per descriptor (Figure 3). The homogeneity of the size of the clusters is an important parameter that has an impact on query time over the whole set of clusters. The association rules are computed over the clusters of descriptors with the algorithm Apriori [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF]. The threshold of confidence is fixed at 50 % to guarantee the robustness of the rules. The threshold of the support is chosen experimentally. We obtain rules with very weak support in general. A high number of clusters involves the reduction of the support of the rules. Suppose that all the 30 clusters contain exactly the same number of images (i.e. 30 30411 ), then, under the assumption that the right and left-hand sides of the rules contain the same images, the support of a rule will be, in the best case, about The rules give nevertheless information about the number of images that are found in the same cluster for several descriptors. In the following, a rule will be selected if its confidence is at least 50 % and if the left and right hand sides of the rule have at least 10 common images. Our goal is then to manage a big number of rules with a fixed threshold of the support of 0,033 %. Under these conditions, 30 clusters numbered from 0 to 29 are computed for all the descriptors and 279 rules are produced at the end of the indexing process.

Experiment 2: using association rules for progressive query

The similarity search is first made on clusters of descriptors ranked according to the closeness of their centroid to the given image-query I q . At the first searching phase, the query processing of I q is done on the first-rank clusters (i.e., ) (

M I TopC

). At the next searching phase, the query processing is done on the second-rank clusters and the query results are merged with the ones of the previous searching phase and updated.

The database is organized into 30 clusters for each descriptor, and the query processing will thus have 30 searching phases. A progressive query means that intermediairy results can be sent at the end of each phase. We propose in this experiment to explore the strategy of the dynamic use of association rules: the rules are selected while the query is executed.

This approach requires the browsing of the whole set of association rules every time a query is submitted to the system. At the 12 th searching phase, the quality of the intermediate result obtained by the dynamic use of association rules is almost the same as the final result obtained by sequential search. Figure 4 shows that, when we dynamically use association rules, the relative loss of quality is about

Figure 4. Dynamical use of association rules

The main advantage of progressive query execution planning is to retrieve the final result (with approximatively the same quality) after the half of the global query time necessary to a sequential search.

Experiment 3: selecting and ordering clusters

We study the measure of selectivity to show the importance of the order of clusters in the context of a progressive query. This measure combines the distance of the cluster centroid to the image-query, the size of the cluster and the density of a cluster at its centroid. It privileges the smallest, the nearest, and the most concentrated clusters at their centroid.

Based on the definition of the selectivity measure (previously given in section 4.1, formula (4)), for α = 1, β = 0 and 0 = γ , clusters are ranked according to the closeness of their centroid to the query image and we have the same results shown in Figure 4.

Curves of result quality and query time for different values of α, β, γ are respectively shown in Figure 5 and Figure 6.

The values α = 0, β = 1, 0 = γ imply the clusters selection exclusively on the size criterion (Figure 5). In this case, the time grows slowly, but convergence of the result is slowed compared to the case (α = 1, β = 0, 0 = γ ) of selection on closeness. We observe on We can then say that cluster selection on the size criterion is good for reducing time but the closeness criterion contributes to keep partial result convergence high (i.e., with relatively good quality compared to sequential search). Partial result convergence is faster with 5), corresponding times varying similarly (Figure 6). This observation confirms that additional density-based criterion can speed up result convergence keeping retrieval time relatively low.

(α = 1/3, β = 1/3, 3 / 1 = γ ) than with (α = 1/4, β = 3/4, 0 = γ ) (Figure

Discussion

The previous experimental section presented the work done for the test and the validation of our method. The goal of the first experiment was to study the main indexation parameters that are: the number of clusters, the thresholds of the support and the confidence. The number of clusters was chosen to be the same for all features. The discovery of association rules can however be done, each feature having a different number of clusters, with no effect on the retrieval process. The method is then easily usable in the general case where the number of clusters may be different for each descriptor. We show in this experiment that thresholds of the support and the confidence essentially depend on the number o f association rules to manage. Confidence threshold can be arbitrarily chosen but the more support threshold is reduced, the more we have rules and the less these rules are statistically significant.

The focus of the second experiment is set on using association rules in the scope of progressive queries. We show on one hand that, given a query-by-example, it is not necessary to process all the image database before retrieving results and, on the other hand, that the retrieval process is sped up using association rules. In this experiment, all queries-by-example are randomly taken in the image database and the results are compared to the results obtained by sequential search. The next step of validation of the result quality will involve users in the relevance feedback.

Efficient processing of progressive queries-byexample implies to know by which cluster to start. For this reason, i t is then important to design several criteria leading to the definition of the priority order for processing the clusters for answering to a given query-by-example. The third experiment shows how the order of cluster processing plays an important role on the quality of intermediate results and on the response time. We work on a family of query plans in which we assume, at each searching phase, that one cluster is processed for each descriptor. We then consider implicitly that all features have the same number of clusters. It is completely possible to make the retrieval process more flexible by giving an order on clusters all together (whatever descriptor) with the advantage to start by clusters of the most interesting features for the query.

Conclusion

In this paper, we present an automatic strategy for selecting the search criteria for content-based retrieval over still-image databases. This strategy is based on the use of clustering and discovery of association rules techniques in order to set the priority on the relevant descriptors for a query-by-example and also to schedule the first-rank clusters to process. We introduce the measure of selectivity of clusters that we use to reduce the query time while keeping a suitable speed of convergence of the intermediate results close to the quality of results obtained by sequential search. All our experimental results are compared on the quality and the search time obtained with a sequential and exhaustive search on a database of 30411 still images described by five MPEG-7 descriptors. Our experimental results show that, on one h and, a strategy of progressive query execution plan makes it possible to have almost the totality of the final result (with the same quality) after half of the total query time of a sequential search and, on the other hand, clustering and discovery of association rules over clusters of images accelerates the retrieval process. The use of association rules is thus a promising technique for the cluster selection and the improvement of the query performance.

The perspectives of our work are now to prove the scalabitlity of our approach for indexing and querying very large images databases with several hundreds of thousands of images. In this context, we may have to refine our measurement of selectivity and add other measures for evaluating the retrieval cost. The size of clusters should be fixed to better manage I/O problems in the case of very large image databases (not only stored in main memory). The complexity of determination of clusters with K-means algorithm is quadratic with the size of the database, so we will have to look for more efficient methods of clustering.

  r1:(19,HTD)∧(0,SCD)->(29,CLD)<0.1,66.1> r2:(23,RSD)∧(1,HTD)∧(23,EHD) ->(8,CLD)<0.1,55.2>

°Figure 1 .

 1 Figure 1. Example of a progressive query execution plan

( 1 dist

 1 (I i ,C) is the distance of I i to the centroid of cluster C for I i ∈ C. Parameters α, β, γ are positive and

  corresponds to the processing of the clusters for the descriptor d i . There are n c (d i ), the number of clusters of the descriptor d i . P(I q , D) can be rewritten with the list of clusters to process such as: {

Figures 5 and 6

 6 Figures 5 and 6 that at equal time duration, partial result convergence speed is better for (α = 1/4, β = 3/4, 0 = γ ).

Figure 5 .

 5 Figure 5. Average result quality with differents parameters α, β, γ of selectivity

Figure 6 .

 6 Figure 6. Average query time with differents parameters α, β, γ of selectivity

  to implement in our experiments.

								Blocking edge
					Fusion		Pipelinable edge
			Fusion
		Rank			Rank			Rank
		Rank		Rank			Rank
	Scan	Scan	Scan	Scan	Scan	Scan	Scan	Scan	Scan
	C11	C12	C13	C21	C22	C23	C31	C32	C33
		Descriptor D1		Descriptor D2		Descriptor D3
			Figure 2a. Query plan tree for sequential search
						Fusion
				Mat
			Fusion
			Mat
		Fusion
		Mat						Fusion
		Fusion	Fusion		Rank	Rank
	Scan	Scan	Scan	Scan	Scan	Scan	Scan	Scan	Scan
	C33	C23	C13	C21	C32	C31	C11	C12	C22
			Figure 2b. Query plan tree for progressive query

Note that this assumption is general since most commonly used distance functions (e.g., Manhattan distance, Euclidean distance, Bounding Box distance) are special cases of the Lp metric.


J M Gomes Da Silva

M Z Oliveira

D Coutinho
email: daniel.coutinho@ufsc.br

S Tarbouriech

Static Anti-windup Design for a Class of Nonlinear Systems

This paper focuses on the problem of static anti-windup design for a class of multivariable nonlinear systems subject to actuator saturation. The considered class regards all systems that are rational on the states or that can be conveniently represented by a rational system with algebraic constraints considering some variable changes. More precisely, a method is proposed to compute a static anti-windup gain which ensures regional stability for the closed-loop system assuming that a dynamic output feedback controller is previously designed to stabilize the nonlinear system. The results are based on a differential-algebraic representation of rational systems. The control saturation effects are taken into account by the application of a generalized sector bound condition. From these elements, LMI-based conditions are devised to compute an anti-windup gain with the aim of enlarging the closed-loop region of attraction. Several numerical examples are provided to illustrate the application of the proposed method.

Introduction

The general principle of the anti-windup technique is the introduction of an extra feedback loop in a predesigned control system to mitigate the effects caused by saturation. Although there exist many different strategies and design approaches, the majority of the results regards the synthesis of anti-windup compensators for linear systems (see [START_REF] Tarbouriech | Anti-windup Design: An Overview of Some Recent Advances and Open Problems[END_REF][START_REF] Teel | The L 2 Anti-windup Problem: Its Definition and Solution[END_REF][START_REF] Galeani | A Tutorial on Modern Anti-windup Design[END_REF][START_REF] Zaccarian | Modern Anti-windup Synthesis: Control Augmentation for Actuator Saturation[END_REF][START_REF] Cao | An Antiwindup Approach to Enlarging Domain of Attraction for Linear Systems Subject to Actuator Saturation[END_REF][START_REF] Gomes Da | Anti-windup Design with Guaranteed Regions of Stability: An LMI-based Approach[END_REF] and references therein). However, if the anti-windup compensator is designed based on the linear approximation of the nonlinear dynamics, it can lead to a poor behavior when implemented on the original nonlinear control system. Moreover, the computed region of attraction of the closed-loop system considering the linear approximation may be highly modified by the nonlinear dynamics.

In general, one cannot ensure that a region of stability computed considering the linear approximation will be valid for the actual nonlinear system. In spite of these facts, only few works have addressed the antiwindup synthesis problem for nonlinear systems subject to saturating actuators. We can cite, for instance, the references [START_REF] Prempain | Coprime Factor Based Anti-windup Synthesis for Parameter-dependent Systems[END_REF][START_REF] Wu | Anti-windup Controller Design Using Linear Parametervarying Control Methods[END_REF][START_REF] Wu | Extended anti-windup control schemes for LTI and LFT systems with actuator saturations[END_REF] which consider anti-windup synthesis for linear-parameter varying systems, [START_REF] Morabito | Nonlinear Anti-windup Applied to Euler-Lagrange Systems[END_REF] which proposes anti-windup methods for Euler-Lagrange systems, and [START_REF] Kahveci | A Robust Adaptive Control Design for Gliders Subject to Actuator Saturation Nonlinearities[END_REF] which considers an adaptive control design. We can also cite some works dealing with the anti-windup synthesis for systems with nonlinear dynamic inversion (NDI) controllers, such as the references [START_REF] Herrmann | Anti-windup Synthesis for Nonlinear Dynamic Inversion Control Schemes[END_REF][START_REF] Kendi | An Anti-windup Scheme for Multivariable Nonlinear Systems[END_REF][START_REF] Kapoor | An Observer-based Anti-windup Scheme for Non-linear Systems with Input Constraints[END_REF][START_REF] Doyle | An Anti-windup Input-output Linearization Scheme for SISO Systems[END_REF][START_REF] Menon | General Anti-windup Synthesis for Input Constrained Nonlinear Systems Controlled Using Nonlinear Dynamic Inversion[END_REF].

On the other hand, a key problem to characterize the stability of nonlinear systems is the determination of a non conservative estimate of the system region of attraction. In general, the estimates are obtained from Lyapunov level sets (see, for instance, the references [START_REF] Khalil | Nonlinear Systems[END_REF][START_REF] Barreiro | Detection of Attraction Domains of Nonlinear Systems Using the Bifurcation Analysis and Lyapunov Functions[END_REF][START_REF] Coutinho | Computing Estimates of the Region of Attraction for Rational Control Systems with Saturating Actuators[END_REF][START_REF] Chesi | Estimating the domain of attraction for uncertain polynomial systems[END_REF][START_REF]Domain of Attraction -Analysis and Control via SOS Programming[END_REF]). In this context, considering an NDI-based controller, the synthesis of a dynamic anti-windup compensator aiming at the enlargement of an estimate of the region of attraction of the closed-loop system in the subspace of the plant variables has been proposed in [START_REF] Valmorbida | Anti-windup for NDI Quadratic Systems[END_REF] for the class of quadratic systems. The considered architecture in this case, as in [START_REF] Herrmann | Anti-windup Synthesis for Nonlinear Dynamic Inversion Control Schemes[END_REF], can be seen as a generalization of the coprime-factorization approach (or the model recovery anti-windup) used in linear anti-windup [START_REF] Teel | The L 2 Anti-windup Problem: Its Definition and Solution[END_REF][START_REF] Weston | Analysis and Design of Linear Conditioning Schemes for Systems Containing Saturating Actuators[END_REF]. This same problem has been tackled in [START_REF] Oliveira | Anti-windup Design for a Class of Nonlinear Control Systems[END_REF], but considering rational systems and static anti-windup compensation. In particular, the multivariable case is not addressed and the method is based on a non-convex condition, although the problem solution is obtained from LMI relaxations. These drawbacks have been in part overcome in [START_REF]Anti-windup Design for a Class of Multivariable Nonlinear Control Systems: an LMI-based Approach[END_REF], where convex stabilizing conditions are proposed. However, it should be pointed out that in [START_REF] Oliveira | Anti-windup Design for a Class of Nonlinear Control Systems[END_REF] and [START_REF]Anti-windup Design for a Class of Multivariable Nonlinear Control Systems: an LMI-based Approach[END_REF], only systems and controllers with linear outputs can be considered. It turns out that these approaches cannot be applied in the case of NDI controllers, for instance.

In light of the above scenario, this paper aims at devising a numerical and tractable technique to design static anti-windup compensators for a class of nonlinear systems subject to actuator saturation. The class of systems considered in this paper covers all systems modeled by rational differential equations. The motivation to investigate rational systems is their use to model several phenomena in real life applications, in particular in systems biology, engineering, physics, and economics, and also in nonlinear system identification and realization theory [START_REF] Aguirre | Modeling Nonlinear Dynamics and Chaos: A Review[END_REF][START_REF] Nemcova | Realization theory for rational systems: the existence of rational realizations[END_REF], which has given rise to a large number of works on the stability analysis, control and filter design for rational nonlinear systems [START_REF] Coutinho | Computing Estimates of the Region of Attraction for Rational Control Systems with Saturating Actuators[END_REF][START_REF] Ghaoui | Control of Rational Systems Using Linear-Fractional Representations and LMIs[END_REF][START_REF] Dussy | Multiobjective robust control toolbox for linear-matrix-inequality-based control[END_REF][START_REF] Coutinho | Guaranteed cost control of uncertain nonlinear systems via polynomial Lyapunov functions[END_REF][START_REF] Wang | Improved stability analysis and gain-scheduled controller synthesis for parameter-dependent systems[END_REF][START_REF] Coutinho | Stability Analysis and Control of a Class of Differential-Algebraic Nonlinear Systems[END_REF][START_REF] Papachristodoulou | Analysis of non-polynomial systems using the sum of squares decomposition[END_REF][START_REF] Coutinho | L 2 -Gain Analysis and Control of Uncertain Nonlinear Systems with Bounded Disturbance Inputs[END_REF][START_REF] Acikmese | Stability analysis with quadratic Lyapunov functions: Some necessary and sufficient multiplier conditions[END_REF]. We emphasize that a large class of systems can be embedded in this setup such as quadratic and polynomial systems. Furthermore, the proposed technique can deal with more complex nonlinearities by means of additional algebraic constraints and/or change of variables (see, e.g., [START_REF] Coutinho | Stability Analysis and Control of a Class of Differential-Algebraic Nonlinear Systems[END_REF][START_REF] Papachristodoulou | Analysis of non-polynomial systems using the sum of squares decomposition[END_REF][START_REF] Coutinho | L 2 -Gain Analysis and Control of Uncertain Nonlinear Systems with Bounded Disturbance Inputs[END_REF]). In particular, the method to be presented in the paper applies a differential algebraic representation (DAR) of nonlinear systems letting to cast Lyapunov based stability conditions in terms of a finite set of state-dependent linear matrix inequalities, which can be numerically solved at the vertices of a given polytope of admissible states. To deal with the saturation nonlinearity, a modified version of the generalized sector bound condition proposed in [START_REF] Gomes Da | Anti-windup Design with Guaranteed Regions of Stability: An LMI-based Approach[END_REF] is also considered. From these elements, we derive regional stabilizing conditions directly in LMI form. In addition, an LMI-based optimization problem is devised to compute an anti-windup gain in order to obtain a maximized region of asymptotic stability, which implicitly leads to the maximization of the basin of attraction of the closed-loop system. This work is a further development of our previous result proposed in [START_REF] Oliveira | Anti-windup Design for a Class of Nonlinear Control Systems[END_REF], where the main differences and advantages are:

(a) the conditions are directly cast in terms of LMIs avoiding iterative relaxation schemes, and (b) it allows to consider multivariable nonlinear control systems in a straightforward way. The paper can also be seen as a generalization of our recent conference work [START_REF]Anti-windup Design for a Class of Multivariable Nonlinear Control Systems: an LMI-based Approach[END_REF], in the sense that systems and controllers with rational outputs can now be treated, which allows to cope with the important case of NDI controllers, among others.

The paper is organized as follows. Section 2 introduces the problem to be addressed in the paper.

Section 3 provides preliminary results concerning the system representation, the Lyapunov theory, and the generalized sector bound condition. The main result is presented in Section 4, where the computation of the anti-windup gain is obtained by means of an optimization problem in Section 4.1. Several illustrative examples are provided in Section 5 in order to demonstrate the potentialities of the proposed approach. Section 6 ends the paper with some concluding remarks.

Notation: I n is the n × n identity matrix and 0 may either denote the scalar zero or a matrix of zeros with appropriate dimensions. For a real matrix H, H ′ denotes its transpose and H > 0 means that H is symmetric and positive definite.H (i) and x (i) denotes the i th line of matrix H and the i th element of vector x, respectively. For a block matrix, the symbol ⋆ represents symmetric blocks outside the main diagonal block. For a given polytope Φ, V(Φ) is the set of vertices of Φ. blockdiag(• • • ) is a block diagonal matrix whose diagonal blocks are the ordered arguments. Matrix and vector dimensions are omitted whenever they can be inferred from the context.

Problem Statement

Consider the following class of nonlinear control systems:

ẋ(t) = f x (x(t)) + g(x(t))sat(v c (t)) y(t) = h y (x(t)) (1)
where x ∈ B x ⊂ R n denotes the state vector; y ∈ R ny is the measured output; v c ∈ R nv is the control input; sat(•) is a classical saturation function, defined as follows:

sat(v c(i) (t)) = sign(v c(i) (t)) min{|v c(i) (t)|, u 0(i) }, i = 1, . . . , n v
with u 0(i) > 0, i = 1, . . . , n v denoting the symmetric saturation level of the i th actuator. It is assumed that

f x : R n → R n , g : R n → R n × R nv ,
h y : R n → R ny are rational functions of x satisfying the conditions for the existence and uniqueness of solution for all x ∈ B x .

In addition, we assume that a dynamic output stabilizing controller

η(t) = f η (η(t), y(t)) v c (t) = h η (η(t), y(t)) (2)
has been designed to guarantee some performance requirements (such as exponential decay rate and damping of the state time-response) and the stability of the closed-loop system (1)-( 2) in the absence of control saturation, where: η ∈ B η ⊂ R nc denotes the controller state; y(t) is the controller input; v c (t) is the controller output; f η : R nc × R ny → R nc and h η : R nc × R ny → R nv are rational functions of η and y satisfying the conditions for existence and solutions for all η ∈ B η and x ∈ B x .

In view of the undesirable effects of windup caused by input saturation, an anti-windup gain is added to the controller. Thus, considering the dynamic controller and the anti-windup strategy, the closed-loop system reads:

ẋ(t) = f x (x(t)) + g(x(t))sat(v c (t)) y(t) = h y (x(t)) η(t) = f η (η(t), y(t)) + E c (sat(v c (t)) -v c (t)) v c (t) = h η (η(t), y(t)) (3)
where E c ∈ R nc×nv is a constant matrix representing the anti-windup gain to be determined.

Considering the above setup, we aim at determining the anti-windup gain E c such that the region of attraction of the closed-loop system (3) is enlarged.

Preliminaries

This section presents some basic results needed to derive an LMI-based method to address the anti-windup computation as stated in Section 2. Firstly, we present the Differential Algebraic Representation (DAR) of nonlinear systems. Then we briefly recall some results of the Lyapunov Theory. Finally, we present an extension of the generalized sector condition proposed in [START_REF] Gomes Da | Anti-windup Design with Guaranteed Regions of Stability: An LMI-based Approach[END_REF] to cope with the case where the actuator input is computed as a rational function of both the plant and controller states. This condition will be useful for dealing with the saturation nonlinearity in the sequel.

Differential Algebraic Representation -DAR

Firstly, define a decentralized deadzone nonlinearity

ψ(v c (t)) △ = v c (t) -sat(v c (t)) , (4)
and rewrite system (3) as follows:

ẋ(t) = f x (x(t)) + g(x(t))v c (t) -g(x(t))ψ(v c (t)) y(t) = h y (x(t)) η(t) = f η (η(t), y(t)) -E c ψ(v c (t)) v c (t) = h η (η(t), y(t)) . (5)
It is worth noticing that, since h y and h η are rational functions, the resulting closed-loop system (5) is indeed rational in the state variables x and η. Hence, defining an augmented state vector

ξ(t) = [x(t) ′ η(t) ′ ] ′ ∈ B ξ ⊂ R n ξ , B ξ = {ξ ∈ R n ξ ; x ∈ B x and η ∈ B η }, with n ξ = n + n c
, it is always possible to find a Differential Algebraic Representation (DAR) for ( 5), as follows:

ξ(t) = A a ξ(t) + A b z(t) + (A c -WE c )ψ(v c (t)) 0 = Ω a ξ(t) + Ω b z(t) + Ω c ψ(v c (t)) (6)
where

W =   0 n×nc I nc   ; z ∈ R nz
is an auxiliary nonlinear vector function with respect to (w.r.t.) ξ and linear w.r.t. ψ, containing rational and polynomial terms (having terms of order equal or larger than two);

A a ∈ R n ξ ×n ξ , A b ∈ R n ξ ×nz , A c ∈ R n ξ ×nv , Ω a ∈ R nz×n ξ , Ω b ∈ R nz×nz and Ω c ∈ R nz×nv , are affine matrix functions of ξ.
Similarly, it is always possible to re-write v c (t) in the following form since h η is a rational function of ξ:

v c (t) = K 1 ξ(t) + K 2 ρ(t) 0 = Ξ 1 ξ(t) + Ξ 2 ρ(t) (7)
where ρ ∈ R nρ is an auxiliary nonlinear vector function of (x, η) containing rational and polynomial terms (having terms of order equal or larger than two) of h η , and

K 1 ∈ R nv×n ξ , K 2 ∈ R nv ×nρ , Ξ 1 ∈ R nρ×n ξ and Ξ 2 ∈ R nρ×nρ are affine matrix functions of ξ.
Regarding the closed-loop system (5) (or ( 6)-( 7)), we assume that:

(A1) the origin (ξ = 0) is a (locally) asymptotically stable equilibrium point; and

(A2) the domain B ξ is a given polytope containing the origin in its interior.

Hence, the polytope B ξ can be described by a set of scalar inequalities as follows:

B ξ = {ξ ∈ R n ξ : q ′ r ξ ≤ 1, r = 1, . . . , n e } , (8)
where q r ∈ R n ξ , r = 1, . . . , n e , are given vectors defining the n e faces of B ξ . For convenience, B ξ can be alternatively described by the convex hull of its vertices, where the notation V(B ξ ) denotes the set of vertices of B ξ . Indeed, suppose that B ξ has N v vertices, i.e. V(B ξ ) = {v 1 , v 2 , . . . , v Nv }, it follows that any ξ ∈ B ξ can be computed as a convex combination of these vertices, that is:

∀ξ ∈ B ξ , ξ = Nv i=1 λ i v i
with λ i ≥ 0 and Nv i=1 λ i = 1. To guarantee that the DAR ( 6)-( 7) is well posed (i.e., the uniqueness of the solution ξ(t) is ensured), we further consider that: (A3) the matrix functions Ω b and Ξ 2 , affine on ξ, have full rank for all ξ ∈ B ξ .

Notice from A3 that the auxiliary vectors z(t) and ρ(t) can be eliminated, respectively, from ( 6) and [START_REF] Prempain | Coprime Factor Based Anti-windup Synthesis for Parameter-dependent Systems[END_REF] leading to the original system representation in ( 5) by means of

z(t) = -Ω -1 b (Ω a ξ(t) + Ω c ψ(v c (t))) and ρ(t) = -Ξ -1 2 Ξ 1 ξ(t) (9)
It turns out that a broad class of nonlinear systems can be embedded in the DAR as defined in ( 6) and ( 7), such as the whole class of (nonsingular) rational control systems which are linear w.r.t. the control input u = sat v c (t) . Moreover, more complex nonlinearities can be dealt with by applying some change of variables or by adding algebraic conditions. See, for instance, some examples in references [START_REF] Coutinho | Computing Estimates of the Region of Attraction for Rational Control Systems with Saturating Actuators[END_REF][START_REF] Coutinho | Stability Analysis and Control of a Class of Differential-Algebraic Nonlinear Systems[END_REF][START_REF] Papachristodoulou | Analysis of non-polynomial systems using the sum of squares decomposition[END_REF][START_REF] Coutinho | L 2 -Gain Analysis and Control of Uncertain Nonlinear Systems with Bounded Disturbance Inputs[END_REF].

Moreover, it has has been shown in [START_REF] Coutinho | L 2 -Gain Analysis and Control of Uncertain Nonlinear Systems with Bounded Disturbance Inputs[END_REF] that the DAR includes the linear fractional representation (LFR) of nonlinear systems introduced in [START_REF] Ghaoui | Control of Rational Systems Using Linear-Fractional Representations and LMIs[END_REF] and thus we may apply the LFR modeling tools (see, e.g., [START_REF] Dussy | Multiobjective robust control toolbox for linear-matrix-inequality-based control[END_REF]) to derive a DAR model for (nonsingular) rational control systems.

Remark 1 Although the DAR representation presents some similarity to quasi-LPV models (see, for instance, [START_REF] Amato | Robust Control of Linear Systems Subject to Uncertain Time-Varying Parameters[END_REF] and references therein) some key differences should be highlighted. In the quasi-LPV approach the nonlinearities are seen as bounded time-varying parameters. However, once the representation is obtained, these parameters are treated as completely independent of the state dynamics, which is potentially conservative for assessing the stability of nonlinear systems. On the other hand, in the DAR approach, the variables z (and ρ), which concentrate the nonlinearities, are directly coupled with the true state through an algebraic equation. Moreover, the set B ξ , is considered directly to check stability by convexity arguments, while in the LPV approach, this set should be re-defined according to the definition of the varying parameter.

In order to illustrate these differences, consider the following simple polynomial system:

ξ(t) = ξ(t) 2 -10 ξ(t) , ξ(t) ∈ B ξ := {ξ : |ξ| ≤ α} ( 10
)
If we consider the quasi-LPV framework, the above system may be represented in terms of a parameter varying function

θ(t) = ξ(t) 2 , θ(t) ∈ B θ := {θ : 0 ≤ θ ≤ α 2 }
yielding the following representation for the system in ( 10)

ξ(t) = θ(t) -10 ξ(t) , θ(t) ∈ B θ . ( 11
)
On the other hand, a DAR for the system in ( 10) can be obtained by defining z(t) = ξ(t) 2 leading to the following representation:

   ξ(t) = -10ξ(t) + z(t) 0 = Ω a ξ(t) + Ω b z(t) , ξ(t) ∈ B ξ (12)
where Ω a = ξ and Ω b = -1. Notice, for large values of α, that the representation in ( 11) is likely to be more conservative than the DAR in (12).

Lyapunov Theory Results

In this section, we recall a basic result from the Lyapunov theory [START_REF] Khalil | Nonlinear Systems[END_REF].

Lemma 1 Consider a nonlinear system ξ = a(ξ) where a :

B ξ → B ξ , B ξ ⊂ R n ξ , is a locally Lipschitz function
such that a(0) = 0. Suppose there exist positive scalars ǫ 1 , ǫ 2 and ǫ 3 , and a continuously differentiable function V : B ξ → R satisfying the following conditions:

ǫ 1 ξ ′ ξ ≤ V (ξ) ≤ ǫ 2 ξ ′ ξ, ∀ ξ ∈ B ξ , (13)
V (ξ) ≤ -ǫ 3 ξ ′ ξ, ∀ ξ ∈ B ξ , (14)
R {ξ ∈ R n ξ : V (ξ) ≤ c} ⊂ B ξ , (15)
then, V (ξ) is a Lyapunov function in B ξ . Moreover, for all ξ(0) ∈ R the trajectory ξ(t) belongs to R and approaches the origin as t → ∞.

To assess the local stability of system [START_REF] Gomes Da | Anti-windup Design with Guaranteed Regions of Stability: An LMI-based Approach[END_REF], in this work we consider a quadratic Lyapunov function:

V (ξ) = ξ ′ P ξ , P = P ′ > 0 ( 16
)
with P ∈ R n ξ ×n ξ , and the following normalized level set

R = {ξ ∈ R n : ξ ′ P ξ ≤ 1} . (17)
In view of Lemma 1, if V (ξ) as above defined satisfies the conditions ( 13)-( 15), for all x ∈ B ξ and R ⊂ B ξ , then R is an invariant and contractive set contained in the region of attraction of the nonlinear system and can be seen as an estimate of it [START_REF] Khalil | Nonlinear Systems[END_REF].

Generalized Sector Bound Condition

Let G 1 ∈ R nv ×n ξ and G 2 ∈ R nv ×nρ be affine matrix functions of ξ. Define now the following set

S △ = {ξ ∈ R n ξ : |(K 1(i) -G 1(i) )ξ + (K 2(i) -G 2(i) )ρ| ≤ u 0(i) , i = 1, . . . , n v } (18)
Note that ρ is a function of ξ and thus S defines a set of vectors in the ξ domain.

From the deadzone nonlinearity ψ(v c ) defined in (4) and the set S as above defined, the following Lemma can be stated as a generalization of the Lemma 1 presented in [START_REF] Gomes Da | Anti-windup Design with Guaranteed Regions of Stability: An LMI-based Approach[END_REF] (see also [START_REF] Tarbouriech | Stability and Stabilization of Linear Systems with Saturating Actuators[END_REF]).

Lemma 2 If ξ ∈ S then the relation

ψ(v c ) ′ T [ψ(v c ) -G 1 ξ -G 2 ρ] ≤ 0 (19)
is verified for any diagonal and positive definite matrix T ∈ R nv ×nv .

Proof.

Recall that v c = K 1 ξ +K 2 ρ and define r = G 1 ξ +G 2 ρ. Considering ξ ∈ S, it follows that (v c(i) -r (i) - u 0(i) ) < 0 and (v c(i) -r (i) + u 0(i) ) > 0, i = 1 . . . , n v . If v c(i) > u 0(i) , it follows that ψ(v c ) (i) = v c(i) -u 0(i) > 0 and then ψ(v c ) (i) (v c(i) -r (i) -u 0(i) ) < 0. If v c(i) < -u 0(i) , it follows that ψ(v c ) (i) = v c(i) + u 0(i) < 0 and then ψ(v c ) (i) (v c(i) -r (i) + u 0(i) ) < 0. Finally, if -u 0(i) ≤ v c(i) ≤ u 0(i) , it follows that ψ(v c ) (i) = 0. From all
this cases, we can conclude that ( 19) is verified for any diagonal and positive definite matrix T ∈ R nv ×nv .

For deadzone nonlinearities, the relation ( 19) can be viewed as a generalized sector condition which encompasses the classical one used, for instance, in [START_REF] Hindi | Analysis of Linear Systems with Saturation Using Convex Optimization[END_REF] and [START_REF] Kiyama | On the Use of Multi-loop Circle Criterion for Saturating Control Synthesis[END_REF]. The generalized sector condition is known to be less conservative than the classical one when assessing the stability of systems subject to actuator saturation [START_REF] Gomes Da | Anti-windup Design with Guaranteed Regions of Stability: An LMI-based Approach[END_REF]. Furthermore, it allows to convexify the problem of synthesizing local stabilizing anti-windup compensators (see [START_REF] Tarbouriech | Stability and Stabilization of Linear Systems with Saturating Actuators[END_REF]). In the present form, it should be noticed that matrices G 1 and G 2 can be affine in ξ. As it will be seen further, these matrices will be considered as free variables in the synthesis optimization problem.

Main Result

In this section, an LMI framework to address the anti-windup synthesis problem stated in Section 2 is presented.

In this case, by considering the quadratic Lyapunov function defined in [START_REF] Menon | General Anti-windup Synthesis for Input Constrained Nonlinear Systems Controlled Using Nonlinear Dynamic Inversion[END_REF], it follows that:

V (ξ) = ξ(t) ′ P ξ(t) + ξ(t) ′ P ξ(t) . (20)
Considering the auxiliary vector

ζ 0 = [ ξ(t) ′ ξ(t) ′ ] ′ , we can rewrite (20) as V (ξ) = ζ ′ 0 Λ 1 ζ 0 with Λ 1 =   0 P P 0   .
In view of Lemma 2, if ξ ∈ S, then the relation

ψ(v c ) ′ T [ψ(v c ) -G 1 ξ -G 2 ρ] ≤ 0 is verified for any matrix
T diagonal and positive definite. Hence, if

ζ ′ 0 Λ 1 ζ 0 -2ψ(v c ) ′ T [ψ(v c ) -G 1 ξ -G 2 ρ] < 0, ∀ξ ∈ B ξ ∩ S (21)
is verified, then V (ξ) < 0 for all ξ ∈ S ∩ B ξ .

Considering the auxiliary vector

ζ = [ ξ(t) ′ ξ(t) ′ z(t) ′ ρ(t) ′ ψ(v c (t)) ′ ] ′ we can rewrite (21) as ζ ′ Λ 2 ζ < 0 ( 22
)
with

Λ 2 =             0 P 0 0 0 P 0 0 0 G ′ 1 T 0 0 0 0 0 0 0 0 0 G ′ 2 T 0 T G 1 0 T G 2 -2T             .
Define now the following scalars:

β 1 = ξ(t) ′ M 1 (-ξ(t) + A a ξ(t) + A b z(t) + (A c -WE c )ψ(v c (t))) β 2 = ξ(t) ′ M 2 (-ξ(t) + A a ξ(t) + A b z(t) + (A c -WE c )ψ(v c (t))) β 3 = z(t) ′ M 3 (Ω a ξ(t) + Ω b z(t) + Ω c ψ(v c (t))) β 4 = ρ(t) ′ M 4 (Ξ 1 ξ(t) + Ξ 2 ρ(t)) (23)
In view of ( 6) and [START_REF] Prempain | Coprime Factor Based Anti-windup Synthesis for Parameter-dependent Systems[END_REF], it follows that the equations

0 = β 1 + β ′ 1 , 0 = β 2 + β ′ 2 , 0 = β 3 + β ′ 3 , 0 = β 4 + β ′ 4 ( 24
)
are satisfied, for any matrices

M 1 ∈ R n ξ ×n ξ , M 2 ∈ R n ξ ×n ξ , M 3 ∈ R nz ×nz and M 4 ∈ R nρ×nρ .
From [START_REF] Oliveira | Anti-windup Design for a Class of Nonlinear Control Systems[END_REF], if

ζ ′ Λ 2 ζ + β 1 + β ′ 1 + β 2 + β ′ 2 + β 3 + β ′ 3 -β 4 -β ′ 4 < 0 (25)
holds, then ( 22) is satisfied. Observe that we can rewrite [START_REF]Anti-windup Design for a Class of Multivariable Nonlinear Control Systems: an LMI-based Approach[END_REF] as follows

ζ ′ Λ 3 (ξ)ζ < 0 (26)
where

Λ 3 (ξ) =             -M 1 -M ′ 1 P -M ′ 2 + M 1 A a M 1 A b 0 M 1 A c -M 1 WE c ⋆ M 2 A a + A ′ a M ′ 2 M 2 A b + Ω ′ a M ′ 3 -Ξ ′ 1 M ′ ⋆ -2T             .
Let us assume that M 1 , M 3 and M 4 are nonsingular and that M 2 = M ′ 2 > 0. Define now the following matrices

Q 1 = M -1 1 , Q 2 = M -1 2 , Q 3 = M -1 3 , Q 4 = M -1 4 , F = T -1 and Π 0 = blockdiag{Q 1 , Q 2 , Q 3 , Q 4 , F } (27)
Pre-and post-multiplying the condition Λ 3 (ξ) < 0 by Π 0 and Π ′ 0 , we have

            -Q 1 -Q ′ 1 Q 1 P Q 2 -Q 1 + A a Q 2 A b Q ′ 3 0 A c F -WE c F ⋆ A a Q 2 + Q 2 A ′ a A b Q ′ 3 + Q 2 Ω ′ a -Q 2 Ξ ′ ⋆ -2F             < 0 .
Observe that the above inequality is not an LMI due to the term Q 1 P Q 2 . However, in this case, we can consider P = M 2 and it follows that P Q 2 = I n ξ . Besides, for the terms Q 2 G ′ and E c F , we consider the following change of variables:

V ′ 1 = Q 2 G ′ 1 , V ′ 2 = Q 4 G ′ 2 and E F = E c F . In this case, if Λ 4 (ξ) < 0 , (28)
with

Λ 4 (ξ) =             -Q 1 -Q ′ 1 A a Q 2 A b Q ′ 3 0 A c F -WE F ⋆ A a Q 2 + Q 2 A ′ a A b Q ′ 3 + Q 2 Ω ′ a -Q 2 Ξ ′ 1 A c F -WE F + V ′ 1 ⋆ ⋆ Ω b Q ′ 3 + Q 3 Ω ′ b 0 Ω c F ⋆ ⋆ ⋆ -Ξ 2 Q ′ 4 -Q 4 Ξ ′ 2 V ′ 2 ⋆ ⋆ ⋆ ⋆ -2F            
, holds, then ( 22) is satisfied.

In light of the above, we state the following result.

Theorem 1 Consider system (5) satisfying A1-A2 and its DAR representation ( 6)-( 7) satisfying A3. If

there exist constant matrices Q 1 , Q 2 = Q ′ 2 > 0, Q 3 , Q 4 , E F , V 1
and V 2 of appropriate dimensions and a positive diagonal matrix F , satisfying the following matrix inequalities for all ξ ∈ V(B ξ ):

Λ 4 (ξ) < 0 , (29)
  Q 2 Q 2 q r q ′ r Q 2 1   > 0, r = 1, . . . , n e (30)
     Q 2 Q 2 Ξ ′ 1 Q 2 K ′ 1(i) -V ′ 1(i) ⋆ Ξ 2 Q ′ 4 + Q 4 Ξ ′ 2 Q 4 K ′ 2(i) -V ′ 2(i) ⋆ ⋆ u 2 0(i)      > 0, i = 1, . . . , n v (31)
then the anti-windup gain E c = E F F -1 is such that for all ξ(0) ∈ R, with P = Q -1 2 , the respective closed-loop trajectories ξ(t) belong to R, and approach the origin as t → ∞, where R is as given in [START_REF] Khalil | Nonlinear Systems[END_REF]. 29)-( 31) are feasible for each ξ ∈ V(B ξ ), then they are also satisfied for all ξ ∈ B ξ from similar convexity arguments of parameter-dependent LMIs [START_REF] Amato | Robust Control of Linear Systems Subject to Uncertain Time-Varying Parameters[END_REF].

Proof. First recall that matrices

A a , A b , A c , Ω a , Ω b , Ω c , K 1 , K 2 , Ξ 1 and Ξ 2 are affine in ξ. If the inequalities (
Note that, since Ω b and Ξ 2 are supposed to be nonsingular (from A3), the terms 31)) ensure that Q 3 and Q 4 are nonsingular. Moreover, since (from ( 29))

Ω b Q ′ 3 + Q 3 Ω ′ b < 0 (from (29)) and Ξ 2 Q ′ 4 + Q 4 Ξ 2 > 0 (from (
Q 1 + Q ′
1 > 0 and (by hypothesis) Q 2 > 0, it follows that matrix Π 0 defined in ( 27) is invertible. Hence if Λ 4 (ξ) < 0, it follows that Λ 3 (ξ) < 0. Hence, in view of [START_REF] Oliveira | Anti-windup Design for a Class of Nonlinear Control Systems[END_REF] we conclude that (21) holds with Q -1 2 = P > 0. Hence, if R ⊂ S ∩ B ξ and considering V (ξ) = ξ ′ P ξ, it follows that V (ξ) < 0, ∀ξ ∈ R, which ensures that for all ξ(0) ∈ R the result closed-loop trajectories ξ(t) belong to R and approach the origin as t → ∞.

On the other hand, pre-and post-multiplying [START_REF] Coutinho | Guaranteed cost control of uncertain nonlinear systems via polynomial Lyapunov functions[END_REF] by Π 1 = blockdiag{Q -1 2 , 1} and Π ′ 1 , respectively, we obtain:

  P q r q ′ r 1   ≥ 0, ∀r = 1, . . . , n e . ( 32
)
which ensures that R is included in the region B ξ defined in (8) [START_REF] Boyd | Linear Matrix Inequalities in Systems and Control Theory[END_REF].

Moreover, pre-and post-multiplying (31) by Π 2 = blockdiag{Q -1 2 , Q -1 4 , 1} and Π ′ 2 , respectively, we obtain:

     P Ξ ′ 1 M ′ 4 K ′ 1(i) -G ′ 1(i) ⋆ M 4 Ξ 2 + Ξ ′ 2 M ′ 4 K ′ 2(i) -G ′ 2(i) ⋆ ⋆ u 0(i) 2      ≥ 0 , ∀i = 1, . . . , n v . ( 33
)
Applying now the Schur's complement to [START_REF] Papachristodoulou | Analysis of non-polynomial systems using the sum of squares decomposition[END_REF] and in the sequel pre-and post-multiplying the obtained matrix inequality respectively by the vector [ ξ ′ ρ ′ ] and its transpose, it follows that:

(K 1(i) -G 1(i) )ξ + (K 2(i) -G 2(i) )ρ 2 u 0(i) 2 ≤ ξ ′ P ξ + 2ρ ′ M 4 (Ξ 1 ξ + Ξ 2 ρ), ∀i = 1, . . . , n v
Hence, taking into account that Ξ 1 ξ + Ξ 2 ρ = 0 and if ξ ′ P ξ ≤ 1, it follows that:

|(K 1(i) -G 1(i) )ξ + (K 2(i) -G 2(i) )ρ| ≤ u 0(i) , ∀i = 1, . . . , n v which ensures that R ⊂ S.
Hence we conclude that ( 30) and ( 31) ensure that R ⊂ B ξ ∩ S, which concludes the proof.

Remark 2 In the particular case where v c depends linearly or bilinearly (quadratically) on x and η, it follows that ρ = 0 in ( 7) and thus we can consider K 2 = 0, G 2 = 0, Ξ 1 = 0 and Ξ 2 = 0.

In this case, relation [START_REF] Coutinho | Guaranteed cost control of uncertain nonlinear systems via polynomial Lyapunov functions[END_REF] should be replaced by

  Q 2 Q 2 K ′ 1(i) -V ′ 1(i) ⋆ u 0(i) 2   ≥ 0 , ∀i = 1, . . . , n v . ( 34
)
Moreover, the 4 th line and the 4 th column in (29) should be eliminated.

Optimization Problems

The result given in Theorem 1 can be applied for computing an anti-windup gain in order to attempt a maximization of the region of attraction of the closed-loop system. In fact, this goal is implicitly achieved if we maximize the region R associated to the gain to be computed.

To this end, since R is an ellipsoidal domain, the following optimization problem can be considered: 29), ( 30), [START_REF] Wang | Improved stability analysis and gain-scheduled controller synthesis for parameter-dependent systems[END_REF], ∀ξ ∈ V(B ξ ) [START_REF] Acikmese | Stability analysis with quadratic Lyapunov functions: Some necessary and sufficient multiplier conditions[END_REF] Note that the minimization of trace(H) is a criterion that leads to the minimization of trace(Q -1 2 ) = trace(P ) an thus an implicit maximization of the size of R. Other classical size criteria of ellipsoidal sets such as volume maximization, minor axis maximization and the maximization in certain directions (see, e.g., Chapter 2 in [START_REF] Tarbouriech | Stability and Stabilization of Linear Systems with Saturating Actuators[END_REF] and references therein) can also be applied. It should be noticed that ( 29), [START_REF] Coutinho | Guaranteed cost control of uncertain nonlinear systems via polynomial Lyapunov functions[END_REF] and [START_REF] Wang | Improved stability analysis and gain-scheduled controller synthesis for parameter-dependent systems[END_REF] are LMIs for ξ ∈ V(B ξ ). Hence, problem [START_REF] Acikmese | Stability analysis with quadratic Lyapunov functions: Some necessary and sufficient multiplier conditions[END_REF] is convex and can be solved by standard LMI solvers.

min trace(H) :   H I I Q 2   > 0, (

Remark 3

The region B ξ corresponds to a region where the feasibility of the state dependent LMIs of Theorem 1 should be verified. It is a priori fixed by the designer. In practice, it can be chosen as an hyperrectangle, which allows a straightforward description as [START_REF] Wu | Anti-windup Controller Design Using Linear Parametervarying Control Methods[END_REF] and the vertices characterization. Of course, the assumption regarding the existence and uniqueness of the solutions in B ξ must be respected.

On the other hand, the size of the estimate R is highly dependent on the size of the polytope B ξ . In consequence, if B ξ is small then the estimate R, which is contained in B ξ , can be conservative. The combined maximization of R and B ξ is a nonconvex problem, which is hard to be solved. A simple solution is to parameterize B ξ as a hypercube, i.e.,

B ξ = {ξ : |ξ (i) | ≤ α, i = 1, . . . , n ξ }
and then starting from a sufficiently small α we can increase the value of α until the LMI conditions of Theorem 1 are not feasible. Alternatively, we may apply an iterative procedure consisting of two optimization steps. More precisely, if we parameterize B ξ as below:

B ξ := {ξ : |ξ (i) | ≤ α i , i = 1, . . . , n ξ } ,
we solve [START_REF] Acikmese | Stability analysis with quadratic Lyapunov functions: Some necessary and sufficient multiplier conditions[END_REF] for given (sufficiently small) α 1 , . . . , α n ξ . Then, for given matrices Q 2 , Q 3 , Q 4 and F , we maximize B ξ over α 1 , . . . , α n ξ and free matrices Q 1 , E F , V 1 and V 2 . Hence, we iterate between these two steps until there is no significant change in the size of R.

Remark 4 The computational effort (number of decision variables and number of LMIs) for solving Theorem 1 or the optimization problem in [START_REF] Acikmese | Stability analysis with quadratic Lyapunov functions: Some necessary and sufficient multiplier conditions[END_REF] depends on the number of states n, the number of control states n c , the number of control inputs n v , the size n z of the auxiliary vector z(t), the size n ρ of the auxiliary vector ρ(t) and the polytope geometry (number of vertices and edges of B ξ ). For a hyper-rectangle B ξ , the number of LMIs is given by n LMI = 2 n ξ (1 + 2n ξ + n v ) and the number of decision variables is

n dv = n 2 ξ + n ξ (n ξ + 1)/2 + n 2 ρ + n 2 z + n v (n ξ + n ρ + n c + 1)
, where n ξ = n + n c .

Numerical Examples

Example 1 Consider the nonlinear closed-loop system treated in [START_REF] Oliveira | Anti-windup Design for a Class of Nonlinear Control Systems[END_REF]:

ẋ(t) = (x 2 (t) -1)x(t) + sat(v c (t)) y(t) = x(t), (36)
with u 0 = 1, and the controller

η(t) = -x(t) v c (t) = η(t) -2y(t). (37)
Considering the DAR given in ( 6) with z = x 2 , we get for ( 36)-(37) the following:

A a =   -3 1 -1 0   , A b =   x 0   , A c =   -1 0   , Ω a = x 0 , Ω b = -1 , Ω c = 0 , K 1 = -2 1 .
Note that in this case (see Remark 2), ρ = 0 and thus K 2 = 0, Ξ 1 = 0 and Ξ 2 = 0. Figure 2 shows the new estimate of the region of attraction for the above value of E c , which is denoted by

Consider B ξ := ξ ∈ R 2 : |ξ 1 | ≤ α 1 , |ξ 2 | ≤ α 2 ,
R 2 .
The resulting region of attraction in this case can also be observed in the figure. Note that the introduction of the anti-windup compensation makes the limit cycle disappear and now the region of attraction is clearly bigger and unbounded in some directions. For comparison purposes, we present both estimates of the region of attraction in Figure 3, where R 1 is in dashed line and R 2 is in solid line. The region where the control does not saturate is denoted by R ns . Considering now the initial condition ξ(0) = [-0.6 1.16] ′ , Figure 4 shows the time evolution of the output (y) and the control signal (sat(v c )) in 3 cases, namely: present approach, approach from [START_REF] Oliveira | Anti-windup Design for a Class of Nonlinear Control Systems[END_REF] and without the anti-windup strategy. Note that, with anti-windup strategy the control signal remains less time saturated and the transient performance is improved. Although the performance optimization is not the focus neither in [START_REF] Oliveira | Anti-windup Design for a Class of Nonlinear Control Systems[END_REF] nor in the present work, we can note that a better performance is obtained with the anti-windup computed from the present approach.

It should also be pointed out that conditions in [START_REF] Oliveira | Anti-windup Design for a Class of Nonlinear Control Systems[END_REF] are BMIs and an iterative algorithm is proposed to obtain the estimate of the region of attraction, which leads to a greater computational burden. Moreover, this algorithm is strongly dependent on the initialization and in general only suboptimal solutions can be achieved. (solid), the approach in [START_REF] Oliveira | Anti-windup Design for a Class of Nonlinear Control Systems[END_REF] (dotted) and without AW (dashed).

Example 2 Consider the closed-loop system borrowed from [START_REF] Valmorbida | Anti-windup for NDI Quadratic Systems[END_REF]:

ẋ1 (t) = x 1 (t) + 2x 1 (t) 2 + x 1 (t)x 2 (t) + sat(v c (t)) ẋ2 (t) = x 1 (t) y(t) = x 1 (t) + 0.5x 2 (t) (38)
with u 0 = 0.6 and the NDI controller η1 (t) = x 1 (t) + 0.5x 2 (t) -1.480η

) 39
Considering the DAR given in (6), we get for ( 38)- [START_REF] Kiyama | On the Use of Multi-loop Circle Criterion for Saturating Control Synthesis[END_REF] the following:

A a =         -3.4 -
        , A c =         -1 0 0 0         , and
K 1 = -4.4 -2x 1 -2.2 -x 1 -15.148 -21.449 .
Since the open-loop system and the output of the controller are quadratic in x and η, in this case A b , Ω a , Ω b , Ω c , K 2 , Ξ 1 and Ξ 2 are equal to zero matrices of appropriate dimensions.

Consider B ξ := ξ ∈ R 4 : |ξ 1 | ≤ α 1 , |ξ 2 | ≤ α 2 , |ξ 3 | ≤ α 3 , |ξ 4 | ≤ α 4 ,
, where α 1 = 0.35 and α 2 = α 3 = α 4 = 0.6. Based on optimization problem stated in [START_REF] Acikmese | Stability analysis with quadratic Lyapunov functions: Some necessary and sufficient multiplier conditions[END_REF], we have first determined the estimate R 1 of the region of attraction of the closed-loop system without anti-windup compensation, i.e. forcing E c = 0. In this case the matrix P is given by: Applying now the optimization problem [START_REF] Acikmese | Stability analysis with quadratic Lyapunov functions: Some necessary and sufficient multiplier conditions[END_REF] and considering E c = 0, we obtain a region R 2 , defined from

P =        
P =         20
       
.

with trace(P ) = 660.17 It can be seen that without anti-windup compensation the closed-loop trajectory diverges. Let us now discuss our results with respect to those proposed in [START_REF] Valmorbida | Anti-windup for NDI Quadratic Systems[END_REF], which concerns the design of norder dynamic anti-windup controllers (with an additional state x a ), and aims at providing an estimate of the domain of attraction in the subspace of the plant state x. In the current paper, we are concerned with a static anti-windup, and we consider the whole augmented state for the estimation of the region of attraction. Then, in order to compare both approaches, we plot in Figure 6 the cut of the estimates of the region of attraction in the subespace defined by the state x (i.e considering x c = 0 and, for the dynamic anti-windup case, also

x a = 0). Although the Lyapunov function used in [START_REF] Valmorbida | Anti-windup for NDI Quadratic Systems[END_REF] is more complex (i.e. it presents bi-quadratic terms in

x, x c and x a ), it can be shown that the cut of the obtained estimate of the region of attraction is included in the ellipoidal set plotted in dashed line. It can be observed that the region associated to our approach clearly includes the dashed ellipsoid, which shows that the set of plant initial conditions for which the stability is guaranteed ensured is larger than the one provided by [START_REF] Valmorbida | Anti-windup for NDI Quadratic Systems[END_REF]. Although the performance optimization is not the focus neither in [START_REF] Valmorbida | Anti-windup for NDI Quadratic Systems[END_REF] nor in our paper, in Figure 7 a comparison between the time-responses considering an initial condition ξ(0) = 0.2235 0 0 0 ′ is depicted. For the dynamic anti-windup compensator computed in [START_REF] Valmorbida | Anti-windup for NDI Quadratic Systems[END_REF] we considered x a (0) = 0. We can note that the response with our approach is slightly better. Moreover, it should be pointed out that in our case the anti-windup structure (i.e. a simple gain) is much simpler than the n-order dynamic nonlinear structure proposed in [START_REF] Valmorbida | Anti-windup for NDI Quadratic Systems[END_REF].

Example 3 Consider the following multivariable nonlinear system and assume that the inputs are subject to saturation, with

u 0 = [1 1] ′ : ẋ1 (t) = (x 1 (t) + 2)x 1 2 (t) + 10x 2 (t) + 10sat(v c2 (t)) ẋ2 (t) = -100x 1 (t) -30x 2 (t) + 10sat(v c1 (t)) y 1 (t) = 20x 1 (t) y 2 (t) = 20x 2 (t). ( 40
)
Figure 7: Example 2 -Time evolution of the output y: present approach (solid) and approach from [START_REF] Valmorbida | Anti-windup for NDI Quadratic Systems[END_REF] (dashed).

From the linearized model of system (40), we designed a locally stabilizing multivariable proportionalintegral (PI) controller given by:

η(t) = A η x(t) + B η y(t) v c (t) = C η η(t) + D η η(t) , (41)
where For α 1 = 3.0, Table 1 shows the results of the optimization problem [START_REF] Acikmese | Stability analysis with quadratic Lyapunov functions: Some necessary and sufficient multiplier conditions[END_REF], considering the case without and with anti-windup compensation. From the matrices P and the respective traces, we can conclude that the estimate R of the region of attraction is significantly enlarged with the application of the anti-windup compensation.

η(t) = [η 1 (t) ′ η 2 (t) ′ ] ′ , v c (t) = [v c1 (t) ′ v c2 (t) ′ ] ′ , A η = 0 2 , B η = I 2 , C η =   - 0

Concluding Remarks

This paper has proposed an approach to compute anti-windup gains for a class of multivariable nonlinear systems subject to actuator saturation. The proposed design conditions relies on a differential algebraic representation of rational systems, which can model a broad class of nonlinear systems. To deal with the saturation, we have considered a modified version of the generalized sector bound condition. From these elements, an LMI-based method has been devised to compute anti-windup gains aiming at the maximization of the estimates of the region of attraction of the closed-loop system. Several numerical examples have illustrated the application of the proposed approach and the effective improvement on the size of the region of attraction of the closed-loop system achieved by means of an appropriate anti-windup compensation.

where α 1 = 1 .3 and α 2 = 2 . 4 .

 11224 Based on optimization problem stated in[START_REF] Acikmese | Stability analysis with quadratic Lyapunov functions: Some necessary and sufficient multiplier conditions[END_REF], we have first determined the estimate R 1 of the region of attraction of the closed-loop system without anti-windup compensation, i.e. forcing E c = 0. Figure1shows the obtained estimate R 1 and the actual region of attraction, which is clearly bounded by a limit cycle. In this case the matrix P is given by:

Figure 1 :

 1 Figure 1: Example 1 -Estimate of the region of attraction R 1 without anti-windup.

Figure 2 :

 2 Figure 2: Example 1 -Estimate of the region of attraction R 2 with anti-windup.

Figure 3 :

 3 Figure 3: Example 1 -Comparison of R 1 and R 2 .

Figure 4 :

 4 Figure 4: Example 1 -Time evolution of the output y and the control signal with the present approach

′.

  that the trace of P is significantly reduced by using the anti-windup technique, which implicitly means that the region of attraction is enlarged with the anti-windup compensation.Consider now the initial condition ξ(0) = 0.2235 0 0 0 It should be noticed that ξ(0) ∈ R 2 , but ξ(0) does not belong to R 1 . Figure5shows the response of the output y and the control signal sat(v c ) for this initial condition considering the cases with (solid line) and without anti-windup strategy (dashed line).

Figure 5 :

 5 Figure 5: Example 2 -Time evolution of the output y and the control signal v c with AW (solid) and without AW (dashed).

Figure 6 :

 6 Figure 6: Example 2 -Cut of the stability regions on the subspace defined by the plant states: present approach (solid) and approach from [22] (dashed).

Considering z = x 1 2 ,

 2 the following DAR for (40)-(41) can be obtained: In this case, ρ = 0 and thus K 2 = 0, Ξ 1 = 0 and Ξ 2 = 0. Moreover, since the matrices of the DAR depend only on the state x 1 , we can consider B ξ := ξ ∈ R 5 : |x 1 | ≤ α 1 .

Table 1 :

 1 Example 3 -Results of the optimization problem for E c = 0 and E c = 0.

Figure 8

 8 Figure 8 shows the time evolution of the outputs and the control signals obtained from the initial condition ξ(0) = -0.1548 -1.0109 -3.2397 13.0463

Figure 8 :

 8 Figure 8: Example 3 -Time evolution of the outputs y and the control signals v c with AW (solid) and without AW (dashed).

M 2 A c -M 2 WE c + G ′ 1 T ⋆ ⋆ M 3 Ω b + Ω ′ b M ′ 3 0 M 3 Ω c ⋆ ⋆ ⋆ -M 4 Ξ 2 -Ξ 2 M ′ 4 G ′ 2 T ⋆ ⋆ ⋆

A c F -WE c F + Q

G ′ 1 ⋆ ⋆ Ω b Q ′

+ Q 3 Ω ′ b 0 Ω c F ⋆ ⋆ ⋆ -Ξ 2 Q ′

-Q 4 Ξ ′ 2 Q 4 G ′ 2 ⋆ ⋆ ⋆

Acknowledgements J.M. Gomes da Silva Jr. was partially supported by CAPES (BEX 3594-10-6) and CNPq (grant 306210/2009-6/PQ). M. Z. Oliveira received a CAPES PhD scholarship. D. Coutinho was partially supported by CNPq (grants 477390/2010-2 and 302136/2011-8/PQ).