Samia Ben Ismail
email: samia_benismail@yahoo.fr

Hajer Maraoui
email: hajer.maraoui@gmail.com

Kais Haddar
email: kais.haddar@yahoo.fr

Laurent Romary
email: laurent.romary@inria.fr

Samia Ben

ALIF editor for generating Arabic normalized lexicons

Keywords: LMF, TEI, Lexicon Editor, Interoperable formats

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

I. INTRODUCTION

The standardization of lexical information becomes an obvious necessity, especially for linguistic communities to cover the compatibility and the interchangeability between NLP applications. In fact, the Arabic-speaking community that deals with lexica adapts this idea to create standardized lexical databases favouring the integration, the evaluation and the interoperability of lexical resources. However, creating such lexical databases is not an easy task for a linguist user. In fact, a linguist has no computing development knowledge to create standardized lexical resources based on existing norms. Moreover, even if he/she is familiar with the standards structures, the creation of lexica can only be processed manually and this task takes a long time. Therefore, the existence of a lexicon editor based on standards models and formats can simplify the description of the lexical databases and comply with certain constraints especially when it endowed with a constraints checker. Besides, the lexical editor can be the basis for computer based training activities and support non-expert users. The realisation of such an editor raises a number of serious problems. The first major difficulty was encountered in the preparatory phase. in fact, it relates with the selection and identification of data categories from standards registers used by the processing levels (i.e., morphological, syntactical, etc.) and the language specification. The second difficulty occurs when looking for a generic approach to generate a variety of types of normalized lexicons such as LMF (Lexical Mark-up Framework) and TEI (Text Encoding Initiative) simultaneously. Another serious problem lies in the identification of lexical constraints (for example inflectional ambiguity may appear in several conjugation rules for verbs with the same scheme).

Our main objective is to create an LMF/TEI editor dedicated to the generation of Arabic lexica covered from the morphological, syntactic and semantic levels. To realise this objective, we made an in-depth study of Arabic words (verbs, nouns and particles) on two levels: lexical and syntactic.

Besides, to reach lexical standardization, we based our work on the ISO standard 24613 LMF and the TEI guidelines (http://www.tei-c.org/). We have worked with LMF for the following reasons: First, LMF allows the specification of monolingual and multilingual lexica. In addition, it insures a stretchable and modular modelling covering all the levels of linguistic description (morphological, syntactic and semantic). Furthermore, its flexibility of modelling favours the representation of the characteristics of Arabic language in particular the derivational and inflectional aspects. We also choose to work with TEI because it has clear, simple and concrete structure. Further, the encoding of textual and lexical content with TEI is based upon a well-maintained schema and offers a large spectrum of possible elements. Moreover, it is easy to identify a subset of the TEI which is compatible with LMF [START_REF] Romary | TEI and LMF crosswalks[END_REF].

In the present paper, we begin with an overview of the LMF and TEI standards. These two standards are necessary for the encoding of the Arabic lexica for Modern Standard Arabic (MSA). Then, we present the specificities of the MSA in the perspective of the modelling of a lexicon. After that, we present the experiment of the approach by a prototype and its evaluation.

II. OVERVIEW ON LMF

ISO 24613 LMF [START_REF] Francopoulo | LMF Lexical Markup Framework[END_REF] is a standard whose scope is the standardization and the representation of monolingual, bilingual and multilingual lexical databases. The LMF standard allows the management of the data exchange between these resources. It also allows the merging of a large number of lexical resources.

LMF conforms to the specifications and main modelling of UML defined by OMG. In fact, it is a meta-model represented by UML classes and the associations between them.

According to ISO 42613, LMF is decorated by data categories selected from a register (DCR). It consists of a core and eight extensions. Meta-model core (see Figure 1) is a lexical entry backbone. It specifies the notions of lexicon, word, form and sense. It admits extensions describing the various descriptions levels of the monolingual and multilingual lexical resources. All these extensions cannot be represented independently of the core.

In the NLP domain, several works have focussed on the lexicon standardization. Among the works dealing with Arabic lexica on the basis of the LMF standard, we can mention for example the development of ArabicLDB [START_REF] Khemakhem | ISO Standard Modeling of a large Arabic Dictionary[END_REF]. The ArabicLDB aims at the construction of a conjugation system of the Arabic verbs and nouns. The problem of this system is that it is not endowed with a constraints checker and it does not handle all the descriptions levels such as syntactic level.

We can also point to an approach for projecting one or more syntactic lexicons existing HPSG to LMF [START_REF] Haddar | A prototype for projecting HPSG syntactic lexica towards LMF[END_REF]. This prototype can produce either lexica corresponding to LMF without any loss of information, or lexica corresponding to LMF with loss of information and also can produce lexicons not corresponding to LMF with loss of information. Also, there exists another approach for projecting LMF lexicon of Arabic verbs to TDL lexicon [START_REF] Loukil | A Syntactic Lexicon for Arabic Verbs[END_REF]. This prototype can add as much transformation rules in the rule file as necessary, without changing the code. But the major complexity lies in the number of rules used and the size of the XML file given as input.

After our study of the existing systems, we find that these systems are complicated to use and also are not free. Besides, they do not take the specificities of Arabic language such as LEXUS [START_REF] Kemps-Snijders | LEXUS, a webbased tool for manipulating lexical resources[END_REF] and Marphalou [START_REF] Romary | Standards going concrete: from LMF to Morphalou[END_REF]. Furthermore, they work only with LMF norm. However, these inconveniences did not prevent that these works are the source of inspiration to realise our prototype.

III. OVERVIEW ON TEI

The TEI is an international consortium whose goals are the development of a set of standards for the preparation and the exchange of electronic texts. This initiative was established in 1987 by a set of researchers working on archiving, structuring and of analysis of the electronic texts [START_REF] Burnard | TEI P5: Guidelines for Electronic Text Encoding and Interchange[END_REF].

The publication of the works of the various committees' research was in the form of "Guidelines" [START_REF] Ide | Une application de la TEI aux industries de la langue: le Corpus Encoding Standard[END_REF]. Indeed, the TEI recommendations present conventions of usable coding in several domains. They can be applied as well to create new information that to exchange existing information. A TEI document has to comply with XML coding rules. The fundamental structure of a TEI document bases itself on a structure which can be, according to the project BVH, a printed text or another a manuscript [START_REF] Dufournau | Manuel d'encodage XML-TEI Renaissance et temps modernes Imprimés-manuscrits[END_REF]. This structure describes the textual part of the document. The notion of structure is essential to edit exchange and analyze texts thanks to the TEI guidelines. In what follows, we give overviews onto the structure and documents in TEI representations.

Several works are made throughout the process of development and improvement of the TEI from its first recommendations until the last publications. However, these works have not dealt strictly the lexica. Besides, there is an absence of Arabic language treatment although the TEI has been the basis for many projects on documents with various natural languages. One of the TEI projects works on dictionary structures. Dictionaries appear among the complex document types the most handled by the TEI. The workgroup of the TEI on dictionaries had occupied the production of a set of conventions at the level of dictionary entries. Every entry of a dictionary is a strongly structured object, in which the numerous mechanisms of abbreviation and typographic organization allow a presentation condensed by the information [START_REF] Romary | Consistent modeling of heterogeneous lexical structures[END_REF] [START_REF] Romary | TEI and LMF crosswalks[END_REF].

Dictionary entries contain several clearly recognizable types of information: information on the form of the word (spelling, pronunciation, caesura, etc.), grammatical information (word class, morphology, etc.), definitions or translations, etc. To normalize lexica with TEI, we started from the idea of considering lexica as a dictionary with a high level of details where each entry can get morphological, syntactical and semantic descriptions. We inspired from the TEI dictionary structure to customize a lexicon structure dedicate for Arabic lexicons [START_REF] Maraoui | Automatisation de l'encodage des lexiques arabes en TEI[END_REF].

IV. PROPOSED METHOD FOR LEXICAL ENCODING

In this section, we explain the various operations for the word transformation in the inflected forms. These operations can be an addition of a letter, a deletion or a replacement of consonant or brief vowel. The employment of these operations defers according to schema and category [START_REF] Dahdeh | األفعال" تصريف في الوسيط [END_REF]. Fig. 1 Fig. 1 explains the operations to generate an inflected form for the sound hamzated verb )أمر( (to order) of schema [

َ َل َع ف - ُ َفع ي ُ ل ].
The extraction of the inflected forms for nouns (as the dual and plural forms) is made by the same operations of the inflection paradigms for verbs [START_REF] Dahdeh | لوحات" و جداول في ّة العربي اللغة قواعد [END_REF]. Inflection paradigms are the necessary operations to generate the inflected / derived forms and to introduce the conjugation paradigms [START_REF] Ammar | ّة" العربي األفعال تصريف في [END_REF]. To reach the determination of the inflected/derived forms for a verb, it is necessary to pass by a process of operations. The appearance of these operations depends on the category of the handled word. The structure of the rule files used by this prototype postponed from a standard to another one. Files appropriate to LMF standard are built by an XML model however files appropriate to TEI standard are built by TEI model.

V. IMPLEMENTATION

To implement our prototype, we used some tools. First, we designed our system with UML. Then, we used Oxygen XML Editor to create the rule files and to propose a TEI structure to describe Arabic lexicons. After that, we developed the editor interfaces using JAVA language and the API JDOM Library.

A. Lexicon creation

The module of lexicon creation consists of two sub-modules: one is to describe generally the lexicon and the other one is for adding lexical entries. In the following part, we are going to explain the mechanism of this module.

The first stage of creation of new lexicon is the choice of the lexicon entry type (verbs, nouns or particles) and the lexicon output file type (TEI, LMF or both of them). In the second stage, the user is going to select the properties of his lexicon. These properties are the authentication properties (workspace and password) and lexicon properties (lexicon name and corresponding package). The second sub-module is for the adding of the lexical entry description in the lexicon file. In this part, ALIF editor connects to the rules and constraints files to generate a morphological description (derived and inflected forms) for each entry given by the user and according to its properties (scheme and category). Besides, ALIF editor offers the choice for the user to create lexicon by adding the canonical entries one by one or all of them in an external text file. For the example of a verb lexicon, Fig. 3 illustrates the interface to create new verb lexicon. To generate derived and inflected forms for each verb, ALIF editor selects the specific rules matches with the verb properties from the rule files. Then, the system applies the derivational and inflectional rules one by one on the canonical form of the verb.

ALIF editor generates a list of TEI/LMF output files for the created lexicon and save them in the user workspace. The number of the output files depends on the number of canonical forms given by the user. ALIF editor starts with creating an output LMF/TEI file containing the first morphological description for all the canonical forms (category of the word, schema, root, pronunciation, etc.). For each canonical form, the editor creates another LMF/TEI file containing all the derived and inflected forms. Every canonical form gets an attribute to mention the reference of the correspondent inflectional and derivational file. For example, for 500 verbs the ALIF editor generates 1002 output files for each lexicon type. All these files are saved in one package in the user workspace.

B. Lexicon management

In this module, the user can update his lexicons. This module includes an authentication step. After choosing the lexicon and entry type, the system passes to the authentication step to verify the properties of the user. After that, the system launches an interface named "Open Lexicon" which permits three services. The first one allows consulting the created lexicon. The second permits to look for a lexical entry in the chosen lexicon. The third allows adapting the selected lexicon. The first service allows the consultation of the selected lexicon file. That will be by opening one of the created TEI or LMF lexicon files. Fig. 4 presents a fragment from TEI lexicon for the derived and inflected forms of the verb [ َ م ﱠ َل ]ع / ʕˤallama / (to teach). <LexicalEntry name=" َ م ﱠ َل "ع morphologiquePatterns=" تام فعل بمفعولين ّي "متعد id="م ّ >"عل <Stem> <feat att="writtenForm" val=" َ م ﱠ َل >/"ع <formRepresentation> <feat att="writtenForm" val="ʕˤallama" /> <feat att="writtenForm" val="latn" /> </formRepresentation> … </Stem> <syntacticBehaviour> <subcategorizationFrame> <feat att="description" أداة"=val بدون >/"فعل+اسم+مفعولين </syntacticBehaviour> <feat att="partOfSpeech" val="verb" /> <feat att="root" val=""ع_ل_م /> <feat att="scheme" val=" ﱠلَ َع "ف />…. <Relatedform> <feat att="writtenForm" val=" ٌ م ﱠ َل ُع "م /> <feat att="catGram" مفعول"=val "اسم /> <feat att="sheme" val=" ُ م ٌ ﱠل َع ف " /> … </Relatedform> … </LexicalEntry> <morphologicalPatterns بمفعولين"=target ّي متعد تام "فعل id="م ّ >"عل <feat att="patternType" val="flexionnalPattern" /> <feat att="example" val=" َ م ﱠ َل "ع /> <feat att="partOfSpeech" val="verb" /> … <TransformSet val=" تُ ْ م ﱠ َل >"ع <feat att="comment" الماضي"=val في أنا مع الفعل >/"تصريف <grammaticalFeatures val=">"أنا <feat att="grammaticalTense" >/"ماضي"=val <feat att="grammaticalGender" val="neutral"/> <feat att="person" val="1"/> <feat att="grammaticalNumber" val="singular"/> <feat att="grammaticalVoice" "معلوم"=val /> </grammaticalFeatures> </TransformSet> … </morphologicalPatterns> <LexicalEntry name="ٌ د َ ل َ "و >"ولد"=id … <feat att="partOfSpeech" val="noun" /> <feat att="scheme" val=" ٌ َل َع "ف /> <Lemma> <feat att="type" سالم"=val صحيح ھو و مجرد ثالثي "إسم /> … </Lemma> </LexicalEntry> <morphologicalPatterns >"ولد"=id <feat att="patternType" val="flexionnalPattern" /> <feat att="example" val=" ٌ د َ ل َ "و /> <feat att="partOfSpeech" مشترك"=val "اسم /> … <TransformSet val=" ٌ د َ ال وْ َ >"أ <feat att="comment" val=" ج تكسير مع " /> <grammaticalFeatures> <feat att="grammaticalGender" "مذكر"=val /> <feat att="grammaticalNumber" val=""جمع /> </grammaticalFeatures> </TransformSet> </morphologicalPatterns> Fig. 6. Fragment from the LMF noun lexicon.

From the lexicons generated by the editor, the user has the option of exposing the inflected forms of the lexicon in table form or in normalized XML file with TEI or LMF like the examples of the figures 5 and 6. The second step allows the user to look for a lexical entry in the selected lexicon. The editor extracts the selected entry descriptions from the lexicon and shows them to the user.

In this section, we present the main interfaces of ALIF editor. These interfaces are shared between the creation of a lexicon or lexical entries and the management of the existing lexicons. In the following part, we are going to evaluate our ALIF system.

VI. EVALUATION AND DISCUSSION

To evaluate our editor prototype, we created and tested a normalized syntactical lexicon containing 10000 Arabic verbs and 500 nouns. Consequently, for the verb lexicon, the prototype generates respectively 20002 TEI and LMF files representing the 10000 canonical forms. From these canonical forms ALIF editor's system generates 1 130 000 inflected and derived forms (113 forms per verb). Table 1 illustrates the obtained results. For the nouns lexicon, ALIF creates 1002 TEI and LMF files representing 4500 inflected forms for the 500 nouns (9 forms per noun). For the noun lexicon, the total number of the obtained forms is 4500. The editor succeeded to create 4350 correct forms and 150 erroneous. Failure cases are (in most of the cases) due to the non-detection of the inflectional rules for plural nouns of some nouns that are irregular in inflection. For example, the nouns (

) ِبٌ َات ك - ابٌ ﱠ ت ُ ك and ( ٌ ِر َاع ش - ٌ َاء َر ع ُ ش
) are in the same category and have the same scheme but they did not have same inflectional rule for plural. Indeed, we estimate the quality of our work manually. Table 2 illustrates the obtained values of precision, recall and F-score. According to the value of precision, we conclude that the value of precision for the verb lexicon is worth 0.99. For the noun lexicon, the precision is equal to 0.96. Also, the recall value for the verb lexicon is 0.99 and for the noun lexicon 0.96. These values provide an F-measure equal to 0.49 for verb lexicon and 0.48 for noun lexicon. Consequently, we conclude that the obtained results are encouraging. Besides, we can say that this prototype is flexible and easy to maintain because it is based on an object-oriented programming language. However, we handled some problems. Some of them are related with the irregular verbs and nouns which need to integrate heuristics solving this kind of problems.

Other kind of problems was related with the optimization of response time. We experience the creation of a verb lexicon by adding entries one by one. Then we found that the execution time augmented with the number of entries and it takes much time to create a lexicon with more than 500 entries. So, we tried to run the system with other method and start with a text file contains the entries. This solution makes the execution faster and much easier for the user.

VII. CONCLUSION

In this paper, we have elaborated a lexicon editor supporting two standards: LMF and TEI. We have also integrated a module for constraint checker. In this editor, we have proposed a type hierarchy for Arabic words according to a done study on Arabic word specificities. As mentioned, the elaborated editor allowed us to generate two normalized lexicons with large coverage for Arabic words: one for LMF and the other for TEI. This editor can be considered also as a good tool for linguists dealing with normalization. The obtained values of measures show that the results obtained from our editor are encouraging. These results can be used in others levels of analyses. Moreover, the execution time is correct. Indeed, the lexicon files need only few minutes to be generated.

As perspectives, we want to improve the proposed models. This improvement consists on incorporating new elements describing more deeply the various levels of description. Besides, we want to develop more our TEI model to incorporate a syntactical description and to get to a deep morphological level. Moreover, we want elaborate a tool allowing the transformation from LMF lexicons to TEI ones and vice versa. To increase the visibility of our lexicon editor, we want to post it open source.

  specifies the operations for the conjugation of a sound hamzated [ صحيح ]مھموز verb with the singular third person [ ھ و ] (he) in the inaccomplished aspect with the passive voice.

Fig. 1 .

 1 Fig. 1. Generation of inflectional form ( ُ ر َ م ُؤْ )ي /yɁmaru/.

Fig. 2

 2 Fig. 2 illustrates the essential operations to produce the broken plural of the singular noun ( ٌ م َ َل )ق (pencil).

Fig. 2 .

 2 Fig. 2. Calculation of inflected form ( ٌ م َ ال ْ ق َ )أ /Ɂqlamun/.

Fig. 3 .

 3 Fig. 3. New verb lexicon interface.

Fig. 4 .

 4 Fig. 4. Fragment from the TEI verb lexicon.

Fig. 5

 5 Fig.5presents a fragment from LMF lexicon for morphological and syntactic level of the verb [ َ م ﱠ َل ]ع /ʕˤallama/ (to teach).

Fig. 5 .

 5 Fig. 5. Fragment from the LMF verb lexicon.

Fig. 6

 6 Fig. 6 presents a fragment from the LMF noun lexicon of the noun [ ٌ د َ ل َ ]و /waladun/ (a boy).

TABLE I .

 I SUMMARYTABLE OF THE SYSTEM RESULTS.

	examples (1) and (2) illustrate a case of irregularity of verb
	conjugation.
	َ ذ خَ َ أ ْ ذ ُ خ (1)	َ جَر َ أ  ُرْ وج ُ ا (2)
	/Ɂa/xa/δa/  /xu/δ/	/Ɂa/dᵹ/ra/  /Ɂu/Ɂ/dᵹ/r/
	The verb [ َ ذ خَ َ ]أ (to take) how has the schema [ irregular verb in the imperative with the personal pronoun [ ]أنتَ َ َل َع ف -ُل ع ْ َف ي ] is an ُ
	(you).
	Table 1 shows that sometimes for irregular verbs, we can obtain
	erroneous generated forms. For the verbs lexicon, the total
	number of obtained forms is 1 130 000. The program succeeded
	to produce 1 129 700 correct forms. However, we found 300
	erroneous forms requiring rectification. This problem of
	erroneous forms is related with some irregular verbs. The

TABLE II .

 II SUMMARY TABLE OF THE PRECISION, RECALL AND F-

SCORE.


Paul Armand

Bounds on the number of vertices of perturbed polyhedra

Keywords: Convex polytopes, degeneracy, linear programming, simplex method. l

Finding the incident edges to a degenerate vertex of a polyhedron is a non-trivial problem. So pivoting methods generally involve a perturbation argument to overcome the degeneracy problem. But the perturbation entails a bursting of each degenerate vertex into a cluster of nondegenerate vertices. The aim of this paper is to give some bounds on the number of these perturbed vertices.

Introduction

Degeneracy of a polyhedron is a source of difficulties for both theory and computation in mathematical programming. This phenomenon may be avoided by considering slight perturbations of degenerate polyhedra, that is, by approximating the degenerate polyhedron by a nondegenerate one. This method was applied to a well-known proof of finiteness of the simplex algorithm [START_REF] Chames | Optimality and degeneracy in linear programming[END_REF][START_REF] Dantzig | The generalized simplex algorithm for minimizing a linear form under linear inequality restraints[END_REF]. Another application is a connectedness result of Gal [START_REF]Determination of all neighbors of a degenerate extreme point in po1ytopes[END_REF][START_REF]On the structure of the set bases of a degenerate point[END_REF][START_REF]Degeneracy graphs-Theory and application. A state-of-the-art survey[END_REF][START_REF] Gal | Survey of solved and open problems in the degeneracy phenomenon[END_REF] concerning graphs of bases associated to the degenerate vertices of a polyhedron, which had induced an algorithm for finding all incident edges to a degenerate vertex [START_REF] Kruse | Degeneracy Graphs and the Neighbourhood Problem[END_REF]. So the pivoting methods which require the search of all or part of the incident edges to a given vertex, for example the vertex enumeration methods (see for example [START_REF] Balinski | An algorithm for finding all vertices of convex polyhedral sets[END_REF][START_REF] Mattheiss | An algorithm for determining irrelevant constraints and all vertices in systems of linear inequalities[END_REF] and a survey in [START_REF] Dyer | The complexity of vertex enumeration methods[END_REF]), the linear multiobjective methods (see for example [START_REF] Armand | Determination of the efficient set in multiobjective linear programming[END_REF] and references . given therein), frequently need a perturbation argument such that the polyhedron is simple. But the perturbed polyhedron has generally many more vertices than the initial polyhedron. Here we give one lower and two upper bounds on the number of vertices of perturbed polyhedra. In our study, we resolutely adopt a geometric viewpoint. This permits the use of some basic facts in the field of convex polytopes as well as a strong result of Klee [START_REF] Klee | Polytopes pairs and their relationship to linear programming[END_REF] concerning the number of vertices of unbounded polyhedra (see also [START_REF] Bamette | An upper bound theorem for polytope pairs[END_REF]).

This paper is organized as follows. In section 2 we extend the right hand side perturbation principle by introducting a perturbation function of a polyhedron and we define the corresponding perturbed polyhedron. We show that, for a given function, the family of perturbed polyhedra belongs to an equivalence class under the combinatorial polyhedral equivalence relation. The perturbation entails a "bursting" of each degenerate vertex into several nondegenerate vertices, called the broken-vertices. From an algorithmic viewpoint, a perturbation corresponds to a choice of lexicographic order on the set of bases that selects certain bases associated with a degenerate vertex.

In section 3 we establish a connection between the redundant constraints in a representation of a polyhedron and the facets of the perturbed polyhedron. We show that for any representation of a full-dimensional polyhedron, there exist perturbation functions which preserve redundancy. In this case, the initial polyhedron and the perturbed polyhedron have the same number of facets.

Section 4 is devoted to the minimum and maximum number of brokenvertices. We show that this number can be equal to the number of vertices of some particular unbounded polyhedra.

2.

Perturbed polyhedra

Here we call a polyhedron a convex subset of Rn defined by the intersection of a finite number of closed halfspaces. We shall say that a polyhedron is fulldimensional if it is n-dimensional. A face of a polyhedron P is the empty set 0, P itself, or the intersection of P with a supporting hyperplane. The faces 0 and P are called improper faces, while the others are called proper. Vertices and edges of a polyhedron are respectively 0-and !-dimensional faces. A facet is a maximal proper face. The recession cone of a polyhedron Pis the polyhedral cone defined by rec P = {y: x +yE P, for all x E P}.

A pointed polyhedron is a polyhedron with a line-free recession cone (i.e., rec P n -rec P = {0} ). A polyhedron is pointed if and only if its vertex set is nonempty. Throughout this paper the polyhedra are implicitly assumed to be pointed. A bounded polyhedron (i.e., rec P = {0}) is called a polytope and it is the convex hull of its vertices. A d-dimensional polyhedron is said to be simple if it is pointed and if its vertices are incident to precisely d edges, or equivalently, to precisely d facets. Two pointed polyhedra P and Q are said to be equivalent if there exists a one-to-one correspondence 4> between the set of all faces of P and the set of all faces of Q such that 4> preserves the inclusion. Equivalently, P and Q are equivalent if their face-lattices are isomorphic. For background material on the theory of polyhedra see [START_REF] Brondsted | An Introduction to Convex Polytopes[END_REF][START_REF] Griinbaum | Convex Polytopes[END_REF].

Any nonempty pointed polyhedron in Rn, defined by a set of n +m linear inequalities, can be transformed to an equivalent polyhedron described in the standard form of the feasible region of a linear program, namely

P = {x ERn: Ax < b,x > 0}, (2.1)
where A IS an m x n-matrix and b is an m-column vector with nonnegative components. Such a transformation can be achieved by exactly n pivots of the Gaussian elimination method and by a Phase I linear programming (see for example [START_REF] Dyer | The complexity of vertex enumeration methods[END_REF]). Adding slack variables, the above representation can be transformed to the canonical form, (2.2) with A= (A,/), I being the m x m identity matrix. A basis B is a regular m x m- submatrix of A. Using the basic-nonbasic partition, A becomes (B, N), so if Ay= b then y 8 = B-1 b-B-1 NYN• With a basis B we associated the following set It is a full-dimensional polyhedral cone, thus it is a closed convex cone with a nonempty interior defined by

int K(B) = {z E lRm: B-1 z > 0}.
The basis B is feasible (with respect toP) if bE K(B). In this case, the vector y such that (y 8 ,yN) = (B-1 b, 0) is a vertex of P, and the vector x such that y = (x, b-Ax) is a vertex of P. The basis B is said to be degenerate if b lies on the boundary of K(B). In this case we denote by (J the number of null components of B-1 band say that the associated vertex is (]-degenerate [10, 20]. Equivalently, a vertex xis (]-degenerate if and only if precisely n + (J constraints are tight at x. Recall that a vertex is non- degenerate if and only if a unique basis is associated with it, on the other hand, at least 2 and at most (n!<7) bases may define the same (]-degenerate vertex. A poly- hedron is said to be degenerate if at least one vertex is degenerate. Denote by 11 the set of feasible bases (B-1 b > 0) and by 11' the one of infeasible bases (B-1 b i 0). We define the stability cone of polyhedron P by

S(A,b) = n K(B)\ U K(B), (2.3) BE91 BE91 1
so it is the intersection of all the "feasible cones" with all the complements of "infeasible cones". Since bE S(A, b), it is a nonempty cone but not necessarily convex. The following two conditions are equivalent.

• P (or P) is a nondegenerate polyhedron.

• bE int S(A, b).

LEMMA 2.1

If the polyhedron P defined by (2.1) is nondegenerate, then for all c E int S(A, b), the polyhedron {x: Ax < c, x > 0} is equivalent toP.

Proof

Let Q = {x: Ax < c, x > 0}. For convenience we use the canonical represen- tation of P and Q and prove that P and Q are equivalent polyhedra. Let B be any basis. If B-1 b > 0 thencE K(B), which implies B-1 c > 0. Conversely, if B-1 bi.O then c~ K(B), which implies B-c i 0. Therefore a basis is feasible with respect toP if and only if it is feasible with respect to Q, whence S(A, b) = S(A, c). As c is an interior point of S(A, c), the polyhedron Q is nondegenerate. Now, let F be a non- enlpty face of P and let B be a basis associated with a vertex of F. By the non- degeneracy assumption, there exists a unique index subset I of the non basic index set such that F ={yE P : Y; = 0, for all i E /}, (see for example [START_REF] Murty | Faces of a polyhedron[END_REF]). The basis B is also associated with a vertex of polyhedron Q and the set {y E Q : Y; = 0, for all i E /}determines a unique face of Q. Obviously, this correspondence between the faces of P and Q preserves the inclusion and because of symmetry of c and b, it is one-to-one. D

The perturbation principle consists in moving the vector b such that it never lies on the boundary of any cone K( B). Denote by x T the transpose vector of x. Let hT = (h 1 , ••• , hm), where each h; is a continuous function from [0, + oo) to R, such that h(O) = 0 and, for any hyperplane H of lRm, there is at most a finite number oft > 0 such that h(t) E H. Such a function will be called a perturbation June tion.

LEMMA2.2

Let z be a nonzero vector of lRm. Then there exists E > 0 such that for all t E (0, E], the scalar product (z, h(t)) has constant sign.

Proof

Suppose that the continuous function t ~ (z, h(t)), defined fort> 0, changes sign in any neighborhood oft= 0. Then there exists a nonfinite number oft> 0 such that h(t) E {x: (z, x) = 0}, which contradicts the definition of a perturbation function.

D

From the standard form (2.1) of polyhedron P we define the family of perturbed polyhedra

P(h(t)) = {x ERn : Ax < b + h(t), x > 0}. (2.4)
Throughout the sequel it will be implicitly assumed that the perturbed polyhedra are nonempty. Usually the perturbation function is defined by h(t) = (t, t 2 , ... , tm)T, see [6,16,[START_REF] Hadley | Linear Programming[END_REF]. (Other perturbation functions are used in the literature, see [START_REF] Chames | Optimality and degeneracy in linear programming[END_REF][START_REF] Os | On the solution of highly degenerate linear programmes[END_REF][START_REF] Wolfe | A technique for resolving degeneracy in linear programming[END_REF]). PROPOSITION 2.3 There exists E > 0 such that [P(h(t))]o<t$f is a family of equivalent nondegenerate polyhedra.

Proof

It suffices to show that there exists E > 0 such that any basis is either feasible and nondegenerate with respect to P(h(t)) for all t E (o, €], or infeasible for all t E (0, €]. Indeed, for all t E (0, €], the vector b + h(t) will be an interior point of the stability cone S(A, b + h(e)), from which the conclusion will follow, cf. lemma 2.1.

Let B be a basis. Every component of B-1 (b + h(t)) is the scalar product of h(t) with a row vector of B-1 • By lemma 2.2, there exists €(B) > 0 such that the basis B is either feasible and nondegenerate or infeasible. Then we take f equal to the smallest E(B) over all of the bases B. D

Throughout the sequel we shall denote by P(h) the perturbed polyhedron. It will indicate an element of this equivalence class. This result shows that the combinatorial structure of a perturbed polyhedron is independent of the value oft > 0 in a neighborhood of 0. This fact appears in the proof of the equivalence of the perturbation method with the lexicographic pivoting rule of the simplex algorithm, see for example [6, chap. 10; 18, chap. 6], where it is shown that it is never necessary to compute the perturbation explicitly.

Another well-known geometrical interpretation of the perturbation is the following. A vertex of Pis degenerate if more than n bounding hyperplanes pass through the vertex. Perturbing P consists in translating each hyperplane parallel to itself, such that there is no degeneracy. This entails a "bursting" of a degenerate vertex into a cluster of nondegenerate vertices. If x(h) is a vertex of the perturbed polyhedron then the basis associated with x(h) is also associated with a vertex x of the initial polyhedron. In this case x(h) will be called a broken-vertex of x.

Note that when h(t) = (t, t 2 , ... , tm)T the broken-vertices correspond one-to-one to the lexicographic bases. PROPOSITION 2.4 For any vertex x, the set of broken-vertices of xis nonempty.

Proof Let x 0 be a vertex of P (2.1) and let c be a normal vector to a supporting hyperplane of P such that, for all x E Px 0 }, (c,x) > (c,x 0 ). Since the polyhedra P and P(h) have the same recession cone, namely the set {x: Ax < O,x > 0}, the problem min { (c, x), x E P(h)} has at least one minimal solution. Therefore, there exists a basis B associated with a vertex of P(h) which satisfies the dual-optimality condition, namely eN-cBB-1 N > 0, where c = (c, 0) E JR.n+m. Note that this condition does not depend on the perturbation, thus the basis B is also dual-optimal with respect to the problem min { (c, x), x E P}. But x 0 is the unique solution of the problem, therefore the basis B is necessarily associated with x 0 .

D

The following result is fundamental for establishing the bounds of theorem 4.4. Given a nondegenerate polyhedron P, it allows us to produce a polyhedron Q with a degenerate vertex such that the perturbed polyhedron Q(h) is equivalent toP.

THEOREM 2.5

Let P = { x : Ax < b, x > 0} be a nondegenerate polyhedron and let Q = {x: Ax < 0, x > 0} be the recession cone of P. Then there exists a perturbation function h such that Q(h) and Pare equivalent polyhedra.

Proof

Without loss of generality we may suppose that P = { x : Ax < e, x > 0}, where e = (1, ... , l)T. Let K = S(A,e) be the stability cone (2.3) associated with P. By the nondegeneracy assumption, e is an interior point of K. Denote by (e;) the canonical basis of JR. m. Let us choose ' rJ > 0 sufficiently small such that the vectors c; = e + rJe;, i E {I, ... , m}, are interior points of K. Consider the perturbation function h(t) = 2:~1 t;c;. Clearly h(t) E int K for all t > 0, and therefore the perturbed polyhedron Q(h) is equivalent to P (cf. lemma 2.1). D

Stability of redundancy

Let Q be a polyhedron in JRn with the following representation, where each Ki is a closed halfspace (also named constraint) with bounding hyperplane H;. Throughout the sequel it will be assumed that no two constraints of a representation of a polyhedron are identical. The constraint K, is said to be redundant if

The redundancy is said to be weak if Q n H, #0, in the other case it is strong. It is well-known that if K, is weakly redundant, then all the vertices of Q contained in H, are degenerate (see for example [13]). Given a vector y and a scalar number a, we shall denote by {(y) <a} the closed halfspace {x: (y,x) <a}. Given a pertur- bation function h, the standard representation (2.1) of polyhedron P and the representation (2.4) of perturbed polyhedron P(h) may be rewritten in the following form,

m n p = n{(ai) < b;} n n{(e;) > 0} (3.1)
i=l i=l and

m n P(h) = n{ (a;) < b; + h;} n n{ (et) > 0}, (3.2)
i=l i=l where (a;) are the row vectors of the matrix A and (e;) is the canonical basis ofiRn.

Note that redundancy is always strong for the representation (3.2) since the perturbed polyhedron is nondegenerate.

Proof

Denote by K; the halfspaces in representation (3.1) and by K;(h) those in (3.2). Suppose that K,(h) is redundant, then

P(h) = n Kt(h) c K,(h). i :f: r
But when h tends to zero we have, whence the redundancy of K,.

P= nK; c K,, i ::f:. r 0 We shall say that a perturbation function preserves redundancy if for any redundant constraint in (3.1) the corresponding perturbed constraint remains redundant in (3.2). Such a perturbation function will be called stable. PROPOSITION 3.2 Any perturbation function preserves strong redundancy.

Proof

Let K be a constraint of a representation of polyhedron P, and let H be its bounding hyperplane. Suppose that the perturbed constraint is not strongly redundant. Then its bounding hyperplane H(h) is a supporting hyperplane of P(h). Therefore there exists a vertex x(h) of P(h) contained in H(h). When h tends to zero, x(h) tends to a vertex x(O) of P contained in H, then K is not strongly redundant for the re~~~~~~ 0 On the other hand, a weakly redundant constraint can be transformed into a nonredundant one for the perturbed polyhedron. Before establishing the next result, note that the deletion of one weakly redundant constraint can make other redundant constraints nonredundant. However, if a polyhedron is full-dimensional and no two constraints of its representation are identical, then all the redundant constraints can be deleted at the same time, without changing the polyhedron. Indeed, under the above assumptions there exists a one-to-one correspondence between the facets and the nonredundant constraints defining P (3.1) (see for example [4, theorem 8.2]). THEOREM 3.3 For any standard representation of a full-dimensional polyhedron, there exists a stable perturbation function. In this case, the polyhedron and the perturbed polyhedron have the same number of facets.

Proof

It follows from the above remark that for a stable perturbation function the two polyhedra have the same number of facets.

We may assume that then nonnegativity constraints { (e;) > 0} in (3.1) are nonredundant. Indeed, since P is n-dimensional, there exist at least n facets containing any vertex x of P. From among these facets, let us choose n of them such that their normal vectors are linearly independent (such a choice exists, otherwise the dimension of P would be smaller than n ). All these facets are defined by the intersection of P with the bounding hyperplanes of n nonredundant constraints. This choice corresponds to the choise of a basis associated with the vertex x. Denote by B this basis. Using the canonical form of P and the basic-nonbasic partition, we can write P in the following equivalent form,

P(B) = {x E IRn: B-1 Nx < B-1 b,x > 0}.
The transformation from P to P(B) maps the vertex x onto the origin ofiRn, and the n preceding constraints are mapped onto the nonnegativity constraints of P(B). Since the redundancy is invariant under a change of basis, we then have a polyhedron equivalent toP with nonredundant nonnegativity constraints. Now, assume that the constraints {(a;) < b;}, i = 1, ... , r, are weakly redundant. Define the perturbation function as follows: h;(t) = t' (t to the ith power). Note that h has only positive components, so the constraints are moved away from any interior point of polyhedron P. Let

m n Q(h) = n {(a;) < b; + h;} n n{ (e;) > 0}. i=r+l i=l
By assumption and from the above mentioned remark, all the redundant constraints can be deleted at the same time in (3.1), hence P = Q(O). Now it suffices to show that Actually, we shall show that the vertices x(h} of Q(h) verify (3.4) which implies (3.3). let x be a vertex of P and let x(h) E Q(h) be a broken-vertex of x. As Q(h) is nondegenerate and son-dimensional, there are exactly n constraints of Q(h) which are tight at x(h), say { (x(h), e;) = 0, i E / 0 , (x(h), aj) = bj + h 1 , j E Jo, with j/ 0 1 + IJol = n. If J 0 = 0, then x(h) = 0 which implies x = 0. Now suppose that J 0 is nonempty. The system above can be written Gx(h) = g(h), where G is then x nmatrix with row vectors e; and a 1 , and g(h) is the corresponding column vector.

Q(h) is included
Since x(h) is a vertex, the matrix G is invertible, hence x(h) = G-1 g(h). Since x(h) is a broken-vertex of x it follows that x = G-1 g(O). We then have

llx(h)-xll = IIG-1 (g(h)-g(O))II < IIG-1 1lllg(h) -g(O)II < allg(h)-g(O)JI,
where a is an upper bound of IIG-1 11 for all matrices G corresponding to the vertices of Q(h). Since the constraints which are tight at x(h) are among those which are tight at x, and since lim 1 -+ 0 (h;(t)/h,+ 1 (t)) = 0, for all i = r + 2, ... , m, it follows that llx-x(h) 11 < ah,+ 1 , which implies (3.4). D

Bounds on the number of broken-vertices

Using a result of K.lee about the number of vertices of a class of unbounded polyhedra [19, theorem 1], we derive some bounds for the number of broken-vertices of a degenerate vertex.

This study is motivated by an algorithm of Kruse [20, p. 97] which finds all adjacent vertices of a degenerate vertex of a polytope ("N-tree method"). Starting from a basic B 0 associated to a a-degenerate vertex x 0 and using the lexicographic pivoting rule of Dantzig, Orden and Wolfe, the N-tree algorithm enumerates the whole set of lexicographic bases associated to x 0 (that is, the bases which can be found from B 0 by means of a finite sequence of "lexicographic pivoting operations"). Kruse emphasizes that the number of lexicographic bases depends on the starting basis B 0 and on the arrangement of rows in the corresponding initial simplex tableau. He conjectures that there exists a starting basi~ B 0 and an arrangement of rows such that this number is not greater than r J a, where r is the number of feasible bases associated to the a-degenerate vertex x 0 • Since the lexicographic variant is formally equivalent to the right hand side perturbation method, the conjecture can be rephrased as follows. There exists a perturbation function such that the number of broken vertices of x 0 is not greater than rja. The following example invalidates the conjecture in the particular case of a polytope which is not full-dimensional.

P = {x ERn : Ix < b, x > 0}, n > 3,
where I is the identity matrix ofRn and bT = (1, 0, ... , 0). Let x be a point of P, then X; < 0, i = 2, ... , n, X; > 0, i = 1, ... , n. Thus Pis the line segment [x 0 ,x 1 ), where x 0 = 0 and x 1 =b. These two vertices are both (n -1 )-degenerate since (2n-1) constraints are tight at x 0 or x 1 • By means of slack variables, the above system is transformed onto

(I,I]y = b, y > 0,
where yT = (xh ... , x 2 n)• There are precisely 2n regular n x n-submatrices of [I,/], each of them corresponding to a feasible basis. Moreover, a variable xz, i E {1, ... ,n}, is basic if and only if Xn+i is nonbasic. Therefore 2n-I bases are associated with x 0 (resp. x 1 ). For any perturbation function (such that the perturbed polytope is nonempty), the perturbed polytope will be defined by lx < b(h), x > 0, where b(h) is an n-column vector with only positive components. Therefore the perturbed polytope is equivalent to the n-dimensional cube. Since the latter has 2n vertices, the number of vertices of P(h) is equal to the number of feasible bases. In particular, for any starting basis B 0 associated to x 0 and for any arrangement of rows in the initial simplex tableau, the number of bases enumerated by Kruse's N-tree algorithm is equal to the number of feasible bases associated to x 0 • 0 Following Klee [19] (see also [2]), for 3 < d < u < p, a pair (Q, G) is called a polytope pair of class (d,p, u) provided Q is a simple polytope of dimension dwithp facets and G is a facet intersecting precisely u other facets of Q. Klee has shown that the minimal and maximal numbers of vertices of Q\G are respectively equal to

cp(d,p, u) = (p-u-2)(d-1) + u, fjJ(d,p, u) = +d-u-1,
where [a) stands for the greatest integer less than a, and (:) denotes the binomial coefficient.

LEMMA4.2 Proof For 3 < d < u < p, fiJ(d,p, u) < fjJ(d,p, u-1), fjJ(d,p, u) < fjJ(d,p + 1, u), <!J(d,p,p-1) < <!J(d,p + l,p).
fjJ(d,p, u) = <jJ(d,p, u-1)-1, implying (4.1). To show (4.2), consider

1/;(d,p) = <jJ(d,p, u)-(d-u-1). Thus <jJ(d,p +I, u)-fjJ(d,p, u) = 1/;(d,p + 1) -1/;(d,p), with 1
/;(d,p + 1) = Since ( n) = n (n -1) , k n -k k it follows that 1/;(d,p + 1) = q (4.1) (4.2) (4.3) with and
For every integer n we have:

Whence [ d+2] and r = p- 2 .

p-d

As q > r, we deduce '1/J(d,p + 1) > r'ljJ(d,p), (4.4) and finally,

-[d+2] d+2 p 2 p-2 d-2 r= > =1+ . p-d -p-d 2(p -d) But d > 3 and p > d, therefore r > 1.
To show (4. We shall say that a constraint is weakly redundant at a vertex, provided the latter is contained in its bounding hyperplane. THEOREM 4.4 Let x 0 be a a-degenerate vertex of a full-dimensional polyhedron of1Rn, n > 3.

Let 0 < r < a be the number of weakly redundant constraints at x 0 . Then for any perturbation function, the minimum and maximum number of broken-vertices of x 0 are respectively equal to: r.p(n, n +a-r + I, n +a-r) =a+ 1 -r, If the perturbation function is stable, then the maximum is equal to

( [n] ) -+a-r cf>(n, n + e1-r + 1, n +a-r) = 2 a-r Proof
The proof is divided into two parts. Firstly, we establish the bounds; then we prove the existence of degenerate vertices for which the bounds are attained. Throughout the proof we denote by v the number of broken-vertices of x 0 • Establishing the bounds. Since x 0 is a vertex of P, there exists a supporting hyperplane { (y) = a} of P such that P n { (y) =a} = {x 0 } and P\{x 0 } c { (y) <a}.

There exists (3 <a such that all vertices of P except x 0 are contained in the open halfspace { (y) < ,B}. Given a perturbation function h(t), when t tends to 0, the broken-vertices of a vertex x of P tend to x, thus we can choose the perturbed poly- hedron such that the hyperplane { (y) = ,B} separates the broken-vertices of x 0 from the remaining vertices of P(h) . The set Q = P(h) n { (y) > (3} is a polytope, indeed if z is a recession direction of Q then (y, z) > 0. But z is also a recession direction of P, then (y, x 0 + z) < a, whence z = 0. Moreover, Q is of dimension n, the set F = P(h) n {y = (3} is a facet of Q and any vertex of Q is either a broken-vertex of x 0 or a vertex of the facet F [4, theorem 11.11]. By proposition 3.1, a nonredundant constraint is also nonredundant for the perturbed polyhedron, so each facet of P incident to x 0 corresponds to a facet of Q. Moreover, such a facet intersects the facet F. Therefore, (Q, F) is a polytope pair of class (n,p, u) with p > p 1 = n + a -r + 1 and u > p 1 -1.

If the perturbation function preserves redundancy, it follows from theorem 3.3 that p = p 1 and u = p 1 -1. So vis bounded from above by cjJ(n,p 11 p 1 -1 ), which gives the supremum for a stable perturbation function. Now for any perturbation function, a weakly redundant constraint at x 0 may define a facet of Q and such a facet may or may not intersect the facet F. Thus p < P2 = n + a + 1 and u < p -1.

Therefore vis bounded from below by min{<p(n,p,u) :pi <p <p2,Pt-1 < u <p-1}.

By virtue of lemma 4.3 we have x 0 will be equal to r = p -1 -u. The facet Fj is bounded if and only if its recession cone is equal to {0}, namely rec Fj = { (yj) = 0} n n{ (y;) < 0} = {0}.

i#j

This implies { (yj) = 0} n ni#j{ (y;) < 0} = 0, which is just a rephrasing of the redundancy of { (yj) < 0} [4, theorem 8.1]. Conversely, suppose that { (yj) < 0} is redundant, namely n{ (y;) < o} c { (yj) < o}.

i #j

Using polarity of cones [25, chap. 14], the above inclusion is equivalent to yj E C, where C is the cone generated by the vectors y;, i E {1, .. . ,p-1}\{j}. The cone C is the polar cone of the pointed and full-dimensional cone rec U, so it is also pointed and full-dimensional. Let us show that Yj is an interior point of C. Since C is pointed, it is the conical hull of its extremal directions [25, theorem 18.5] and each of them is among the vectors Y;, i =I= j. Suppose that Yj is on the boundary of C. Then there exists a facet D of C which contains Yj• Since C is full-dimensional, the facet D has dimension ( n -1) and so has at least ( n -1) extremal directions. Therefore the hyperplane defined by D contains at least n vectors y;, which contra- dicts the general position of Y;• Using again polarity, to say that Yj is an interior point of C is equivalent to Vx =I= 0, (x,y;) < 0, i E {1, . . . ,p-1}\{j} =} (x,yj) < 0. This implies rec Fj = { (yj) = 0} n ni#j{ (Yi) < 0} = {0}, therefore Fj is bounded. Finally the vertex x 0 = 0 of rec U is a-degenerate and precisely r constraints are weakly redundant at x 0 • Now its suffices to find a standard representation of rec U and apply theorem 3.3, which implies the existence of a perturbation function h such that the perturbed polyhedron (rec U)(h) is equivalent to U. Now for the situation with a stable perturbation function (lower bound and second upper bound), it suffices to restart the above procedure with a polytope pair (Q, F) of class (n,p,p-1), withp = n +a -r + 1, for which the number of vertices of Q\F is equal to <p(n,p,p-1) (resp. f/>(n,p,p-1)). Then we choose a represen- tation of the unbounded polyhedron U and add r strongly redundant constraints. Obviously, the latter correspond to weakly redundant constraints for the recession cone of U.

D

Using the notation of the proof above, by lemma 2.2 we can easily derive the following formula, 4>(n,phPI-1) = min{f/>(n,p, u): Pt < p < P2,Pt-1 < u < p-1}.

Therefore we might think that a stable perturbation function generates fewer vertices than any other. This is true for the dimensions 2 and 3 (see below), but the following example shows that this is false for the dimension 4. Consider P = {x E 1R 4 : Ax < b, x > 0} with Pis a 4-dimensional polytope and is the convex hull of the vertex x 0 = (I, 0, 0, 0) T with a 3-dimensional polytope contained in the hyperplane { (e 1 ) = 0}. There are 8 facets of P containing x 0 . The first constraint {((I, 0, 0, 0)) < 1} is redundant at x 0 . Hence 9 constraints are tight for x 0 , thus x 0 is 5-degenerate. For the stable pertur- bation function h(t) = (t, t 2 , ... , t 6 )T there are 15 broken-vertices of x 0 , although for the non-stable perturbation function g(t) = (t 6 , t 5 , . . • t)T, this number is only equal to 8. D Before dimension 3, consider full polytopes of lR 2 • If x 0 is a-degenerate, then its degeneracy is only due to redundancy. Therefore a stable perturbation function generates only one broken-vertex. If it is not stable the number of broken-vertices is bounded from above by (a+ 1). Now we consider the three-dimensional case. PROPOSITION 4.6 Let x 0 be a a-degenerate vertex of a full-dimensional polyhedron of JR 3 • Let r be the number of weakly redundant constraints at x 0 • For any stable perturbation function the number of broken-vertices of x 0 is equal to v = a-r + I. Moreover, for any perturbation function this number is always greater than v.

Proof

Suppose the perturbation function stable, then the upper and lower bounds of theorem 4.4 are both equal to v = 1 +a-r. Now suppose that among the redundant constraints, there are 1 < k < r nonredundant constraints for the perturbed polyhedron. Let (Q, F) be the polytope pair as in the proof of theorem 4.4. Then (Q, F) is of class (3,p, u) with p = 4 + u-r + k and 3 + u -r < u < p -1. Since <p decreases with respect to u, cf. lemma 4.3, then the number of broken-vertices of x 0 1s lowered by cp(3, 4 + u-r + k, 3 + u-r + k) = u-r + k + 1 > v.

D

The case of higher dimensions contradicts somewhat our intuition. For if a redundant constraint for the perturbed polyhedron becomes nonredundant (by a change of perturbation function), the perturbed polyhedron is in a way truncated such that the new polyhedron has one additional facet. Now, if a simple d-dimensional polytope Pis truncated to obtain a polytope P' such that P' is simple and has one more facet than P, then • if d = 2 or 3, P' has more vertices than P,

• if d > 4, P' may have fewer vertices than P.

For a polyhedron P we denote by Pk the number of k-dimensional faces. The above remark is trivial for d = 2 and for dimension 3 follows from the Dehn-Sommerville relations (see for example [4, § 17]), p 0 = 2p 2 -4 and p 1 = 3p 2 -6. Let F be a facet of P. Translate the hyperplane determined by F onto a hyperplane H, such that F is one one side of Hand the vertices of P\F are on the other side, H containing no vertex. Let Q = H' n P, where H' is the closed halfspace bounded by Hand including F. Since any facet of P intersects the others, Hinter- sects every facet different from F, and G = H n Pis a facet of Q. Hence Q is a simple polytope with one additional facet. Vertices of Q are the union of those of F and those G. The latter result from the intersection of the hyperplane H with external edges of F. Since F is simple, there is precisely one external edge per vertex, therefore q 0 = 2/ 0 . The facet F is a 3-dimensional simple polytope with k-1 facets, therefore by (4.5) we have q 0 = 4(k-3). At last we have p 0 > q 0 as soon as k > 9. 0 This example is based on a counterexample of Mattheiss and Schmidt [START_REF] Mattheiss | Computational results on an algorithm for finding all vertices of a polytope[END_REF] invalidating a conjecture of Mattheiss [START_REF] Mattheiss | An algorithm for determining irrelevant constraints and all vertices in systems of linear inequalities[END_REF] about a vertex enumeration algorithm. A similar construction can be found in [8, p. 388].

PROPOSITION 3. 1

 1 If a constraint is nonredundant for the representation (3.1) of P, then the corresponding perturbed constraint is nonredundant for the representation (3.2) of P(h).

. 3 For 3

 33 3) consider 4>(d,p + 1,p) = 'ljJ(d,p +I)+ d-p-1 > r'ljJ(d,p) + d-p-1, the inequality be derived from (4.4). As 'ljJ(d,p) = 4>(d,p,p-1)-(d-p), we have 4>(d,p + l,p) > r4J(d,p,p-1) + k, with k = (d-p)(1 -r)-1. Replace r by its value, we have k = [(d + 1)/2)-2. Since d > 3, then r > 1 and k > 0, which implies ( 4.3). D LEMMA4< d < u < p, Proof r.p(d,p, u) < r.p(d,p, u-1), r.p(d,p, u) < r.p(d,p + 1, u), r.p(d,p,p-I)< r.p(d,p + l,p). r.p(d,p, u) = (d-1 )(p-2) -u(d-2), thus r.p decreases with respect to u and increases with respect top. A simple calculation shows that r.p(d,p,p-1) = p-d andr.p(d,p+1,p)=p-d+I. 0

EXAMPLE 4. 5

 5

(4. 5 )

 5 Now suppose that d = 4. Let P be a simple dual neighbourly polytope with k facets (for example the dual of a cyclic polytope with k vertices), see[4, § §13-14]. Then P3 = k and Po = !k(k-3).

Acknowledgements

The author is grateful to the referees for their helpful comments and suggestions concerning the presentation of the paper.

and It follows that the infimum is equal to cp(n,p 1 ,p 1 -1 ). Note that this case corresponds to a stable perturbation function.

In the same way, v is bounded from above by max { <P( n, p, u) :

As (,b increases with respect top and decreases with respect to u, cf. lemma 4.2, the maximum is attained for p = p 2 and u = p 1 -1 which gives the supremum.

Attaining the bounds. First we shall show that the first upper bound is attained. We have to produce a full-dimensional polyhedron, with a a-degenerate vertex x 0 and with 0 < r < C1' weakly redundant constraints at

for which the number of vertices of Q\F is equal to <,h(n,p, u). Then we shall prove that there exists a perturbation function such that v = <,h(n,p, u) .

Let U be the unbounded simple polyhedron obtained from Q by applying a projective transformation that sends the facet F into the hyperplane at infinity [START_REF] Griinbaum | Convex Polytopes[END_REF][START_REF] Klee | Polytopes pairs and their relationship to linear programming[END_REF]. Then U has precisely u unbounded facets and its recession cone is fulldimensional [START_REF] Bamette | An upper bound theorem for polytope pairs[END_REF], moreover U and Q\F have the same number of vertices. Let p-1 u = n { (y;) < a;} i=1 be a representation of U such that each set F; = { (y;) =a;} nU is a facet of U. We may assume that each n of the hyperplanes { (y;) =a;} have a unique common point; if not, the vectors Yi can be slightly perturbed such that each n of them are linearly independent (the vectors Y; are said to be in general position). The recession cone of U is defined by p-1 rec u = n{(y;) < 0}. i=l Clearly, the unique vertex x 0 = 0 of rec U is a-degenerate. Now we shall show that a facet Fj of U is bounded if and only if the constraint { (yj) < 0} is redundant for the representation of rec U. Therefore the number of weakly redundant constraints at


Samir Adly

Daniel Goeleven

Michel Thera

Existence Results for a Class of Periodic Evolution Variational Inequalities

Keywords: Variational inequalities, Differential inclusions, Topological degree, Guiding functions, Periodic solutions 2000 MR Subject Classification 49J40, 49J20, 35K85

In this paper, using the Brouwer topological degree, the authors prove an existence result for finite variational inequalities. This approach is also used to obtain the existence of periodic solutions for a class of evolution variational inequalities.

Introduction

It has been well recognized that variational inequalities offer the right framework to consider numerous applied problems in various areas such as economics and engineering. Throughout this paper, we consider R n equipped with the usual euclidean scalar product • , • . We start by considering a variational inequality VI(Λ, ϕ), that is, the problem of finding x ∈ R n such that Λ(x), vx + ϕ(v)ϕ(x) ≥ 0, ∀ v ∈ R n .

In this formulation, Λ : R n → R n is a continuous map, ϕ : R n → R is a convex function. When the operator Λ under consideration is coercive, existence results for the problem VI(Λ, ϕ) are well known in the setting of reflexive Banach spaces. This study was initiated by G. Stampacchia in the 60's, and we refer to the contributions of J. L. Lions [START_REF] Lions | Quelques Méthodes de Résolution des Problèmes aux Limites Non-linéaires[END_REF], Brézis [START_REF] Brézis | Problèmes unilatéraux[END_REF] and Kinderlehrer and Stampacchia [START_REF] Kinderlehrer | An Introduction to Variational Inequalities and Their Applications[END_REF] for various results and references therein.

In the first part of this paper, we develop an original approach essentially based on the use of the Brouwer topological degree to prove results related to the existence of a solution to problem VI(Λ, ϕ).

Then, we study a first order evolution variational inequality, that is, a differential inclusion of the form: find a T -periodic function u ∈ C 0 ([0, T ]; R n ) such that du dt (t) + F (u(t))f (t) ∈ -∂ϕ(u(t)), a.e. t ∈ [0, T ],

where F : R n → R n is a continuous map, ϕ : R n → R is a convex function, f ∈ C 0 ([0, +∞[; R n ) is such that df dt ∈ L 1 loc (0, +∞; R n ), T > 0 is a prescribed period and ∂ϕ is the convex subdifferential operator. This problem is studied by means of a continuation method. It is well known that the Brouwer topological degree plays a fundamental role in the theory of ordinary differential equations (ODE). M. A. Krasnosel'skii [START_REF] Krasonel'skii | The Operator of Translation along the Trajectories of Differential Equations[END_REF][START_REF] Krasonel'skii | Geometrical Methods of Nonlinear Analysis[END_REF] and H. Amann [START_REF] Amann | A note on degree theory for gradient mappings[END_REF], developed a continuation method to compute this Brouwer topological degree associated to some gradient mapping (called the method of guiding function). This approach was useful for the study of the existence of periodic solutions for ODE's. Roughly speaking, if on some balls of R n the Brouwer topological degree of the Poincaré translation operator (see e.g. [START_REF] Mawhin | Continuation theorems and periodic solutions of ordinary differential equations[END_REF]) associated to the ODE is different from zero, then the problem has at least one periodic solution (for more details, references and possible extensions to the Leray-Schauder degree, we refer to the monograph of J. Mawhin [START_REF] Mawhin | Continuation theorems and periodic solutions of ordinary differential equations[END_REF]). With the emergence of many engineering disciplines and due to the lack of smoothness in many applications, it is not surprising that these classical mathematical tools require natural extensions (for both analytical and numerical methods) to the class of unilateral dynamical systems. It is well known that the mathematical formulation of unilateral dynamical systems involves inequality constraints and hence contains natural non-smoothness. In mechanical systems, this non-smoothness could have its origin in the environment of the system studied (e.g. case of contact) in the dry friction, or in the discontinuous control term. Recently, new analytical tools have been developed for the study of unilateral evolution problems (see e.g. [START_REF] Adly | Attractivity theory for second order dynamical systems with application to dry friction[END_REF][START_REF] Adly | A stability theory for second order non-smooth dynamical systems with application to friction problems[END_REF][START_REF] Goeleven | Necessary conditions of asymptotic stability for unilateral dynamical systems[END_REF][START_REF] Goeleven | On the stability of stationary solutions of first order evolution variational inequalities[END_REF][START_REF] Goeleven | Stability and unstability matrices for linear evolution variational inequalities[END_REF] and the references therein).

The study of periodic solutions of evolution variational inequalities is also important. The Krasnol'skii's original approach for ODE, has known some extensions in order to obtain continuation methods for differential inclusions (see [START_REF] Górniewicz | Topological approach to differential inclusions, Topological Methods in Differential Equations and Inclusions[END_REF] and the references therein for more details).

In Section 4, we will be concerned with the existence of a T -periodic solution u ∈ C 0 ([0, T ];

R n ) such that du dt ∈ L ∞ (0, T ; R n ), u is right-differentiable on [0, T ), u(0) = u(T ), du dt (t) + F (u(t)) -f (t), v -u(t) + ϕ(v) -ϕ(u(t)) ≥ 0, ∀ v ∈ R n , a.e., t ∈ [0, T ]. (1.1)
In this formulation,

F : R n → R n is a continuous map, ϕ : R n → R is a convex function, f ∈ C 0 ([0, +∞[; R n ) is such that df dt ∈ L 1 loc (0, +∞; R n )
and T > 0 is a prescribed period. We prove (see Corollary 5.1) that if F and ϕ satisfy some growth condition (see (5.17)), then problem (1.1) has at least one periodic solution.

This approach is also used to obtain the existence of a T -periodic solution of a second order dynamical system of the form:

M q(t) + C q(t) + Kq(t) -F (t) ∈ -H 1 ∂Φ(H T 1 q(t)), (1.2)
where q ∈ R m is the vector of generalized coordinate, Φ : R l → R is a convex function, M ∈ R m×m is a symmetric and positive definite matrix, C ∈ R m×m , K ∈ R m×m are given matrices and H 1 ∈ R m×l is a given matrix whose coefficients are determined by the directions of friction forces. The function

F ∈ C 0 ([0, +∞); R m ) is such that dF dt ∈ L 1 loc ([0, +∞); R m ). The term H 1 ∂Φ(H T 1 •
) is used to modelise the convex unilateral contact induced by friction forces. The paper is organized as follows: Section 2 contains some background materials on properties of the Brouwer topological degree and the concept of resolvent operator associated to a subdifferential operator. In Section 3, using an equivalent fixed point formulation as well as the Brouwer topological degree, we give some existence results for finite variational inequalities. In Section 4, we introduce the Poincaré operator associated to problem (1.1). Section 5 is devoted to the existence of a periodic solution of problem (1.1). In Section 6, we show that our approach could be applied to a special second order problem (1.2).

Brouwer Topological Degree and the Resolvent Operator P λ,ϕ

It is well known that the degree theory is one of the most powerful tool in nonlinear analysis for the study of zeros of a continuous operator. Let Ω ⊂ R n be an open and bounded subset with boundary ∂Ω and

f ∈ C 1 (Ω; R n ) ∩ C 0 (Ω, R n ). The Jacobian matrix of f at x ∈ Ω is defined by f (x) = (∂ x i f j (x))
1≤i,j≤n and the Jacobian determinant of f at x ∈ Ω is defined by

J f (x) = det(f (x)).
We set

A f (Ω) = {x ∈ Ω : J f (x) = 0}. Observe that if f -1 (0) ∩ A f (Ω) = ∅ and 0 ∈ f (∂Ω), then the set f -1 (0) is finite. The quantity x∈f -1 (0)
sign (J f (x)) is therefore defined and is called the Brouwer topological degree of f with respect to Ω and 0 and is denoted by deg(f, Ω, 0). More generally, if f ∈ C 0 (Ω; R n ) and 0 ∈ f (∂Ω), then the Brouwer topological degree of f with respect to Ω and 0, denoted by deg(f, Ω, 0), is well defined (see [START_REF] Lloyd | Degree Theory[END_REF] for more details).

In the sequel, we use standard notations. We denote by • , • the scalar product on R n and by • the associated norm. For r > 0, we set B r := {x ∈ R n : x < r}, and respectively B r = {x ∈ R n : x ≤ r}, for the open (respectively closed) unit ball with radius r > 0. We use the notation ∂B r to denote the boundary B r \

• Br of B r , that is, {x ∈ R n : x = r}. If f : B r → R n is continuous and 0 / ∈ f (∂B r )
, then the Brouwer topological degree of f with respect to B r and 0 is well-defined (see e.g. [START_REF] Lloyd | Degree Theory[END_REF]) and denoted by deg(f, B r , 0).

Let us now recall some properties of the topological degree that we will use later.

P1 If 0 / ∈ f (∂B r ) and deg(f, B r , 0) = 0, then there exists x ∈ B r such that f (x) = 0. P2 Let ϕ : [0, 1] × B r → R n ; (λ, x) → ϕ(λ, x) be continuous such that, for each λ ∈ [0, 1], one has 0 / ∈ ϕ(λ, ∂B r ), then the map λ → deg(ϕ(λ, • ), B r , 0) is constant on [0, 1].
P3 Let us denote by id R n the identity mapping on R n . We have

deg(id R n , B r , 0) = 1. P4 If 0 / ∈ f (∂B r ) and α > 0, then deg(αf, B r , 0) = deg(f, B r , 0), deg(-αf, B r , 0) = (-1) n deg(f, B r , 0). P5 If 0 / ∈ f (∂B r ) and f is odd on B r (i.e., f (-x) = -f (x), ∀ x ∈ B r ), then deg(f, B r , 0) is odd. P6 Let f (x) = Ax -b, with A ∈ R n×n a nonsingular matrix and b ∈ R n . Then deg(f, A -1 b+B r , 0) = sign(det A) = ±1.
Let V ∈ C 1 (R n ; R) and suppose that there exists r 0 > 0 such that for every r ≥ r 0 , 0 / ∈ ∇V (∂B r ). Then deg(∇V, B r , 0) is constant for r ≥ r 0 and one defines the index of

V at infinity "ind(V, ∞)" by ind(V, ∞) := deg(∇V, B r , 0), ∀ r ≥ r 0 . Let ϕ : R n → R be a convex mapping. It is well known that (a) ϕ is continuous on R n ;
(b) For all x ∈ R n , the convex subdifferential of ϕ at x is a nonempty compact and convex subset of R n and defined by

∂ϕ(x) = {w ∈ R n : ϕ(v) -ϕ(x) ≥ w, v -u , ∀ v ∈ R n }; (c) For all x ∈ R n , the directional derivative of ϕ at x ∈ R n in the direction ξ ∈ R n , i.e., ϕ (x; ξ) = lim α↓0 ϕ(x + αξ) -ϕ(x) α
exists (see e.g. [11, p. 164]).

Since the subdifferential operator ∂ϕ associated to ϕ, is maximal monotone (see [START_REF] Brézis | Opérateurs Maximaux Monotones et Semi-groupes de Contractions dans les Espaces de Hilbert[END_REF]), the operator (I + λ∂ϕ) -1 denoted by P λ,ϕ is a contraction everywhere defined on R n , that is,

P λ,ϕ (x) -P λ,ϕ (y) ≤ x -y , ∀ x, y ∈ R n .
This operator P λ,ϕ is called the resolvent of order λ > 0 associated to ∂ϕ and for simplicity, we denote it by P ϕ instead of P 1,ϕ when the parameter λ = 1.

Let Λ : R n → R n be a continuous mapping and consider the inequality problem: Find

x ∈ R n such that Λ(x), v -x + ϕ(v) -ϕ(x) ≥ 0, ∀ v ∈ R n . (2.1)
Clearly problem (2.1) is equivalent to the nonlinear equation: Find x ∈ R n such that

x -P ϕ (x -Λ(x)) = 0. (2.2)
In view of property P1 recalled earlier, it is important to compute the degree of the operator id

R n -P ϕ • (id R n -Λ). Remark 2.1 If x is a solution of problem (2.1), then Λ(x), ξ + ϕ (x; ξ) ≥ 0, ∀ ξ ∈ R n .
Indeed, let x be a solution of (2.1). Let ξ ∈ R n and α > 0 be given. Setting v = x + αξ in (2.1), we get Λ(x), αξ + ϕ(x + αξ)ϕ(x) ≥ 0.

Thus, for all α > 0, we have

Λ(x), ξ + ϕ(x + αξ) -ϕ(x) α ≥ 0.
Taking the limit as α ↓ 0 we obtain

Λ(x), ξ + ϕ (x; ξ) ≥ 0.
Example 2.1 Let ϕ : R → R be the function defined by

ϕ(x) = |x|, ∀ x ∈ R.
We have

∂ϕ(x) = ⎧ ⎪ ⎨ ⎪ ⎩ 1, if x > 0, [-1, 1], if x = 0, -1, if x < 0,
and

P ϕ (x) = (I + ∂ϕ) -1 (x) = ⎧ ⎪ ⎨ ⎪ ⎩ x -1, if x ≥ 1, 0, if x ∈ [-1, 1], x + 1, if x ≤ -1. ∂ϕ(x) P ϕ I -P ϕ • (I -Λ) (I + ∂ϕ) ¢ ¢ ¢ ¢ ¢ ¢ ¢ Figure 1 Example 2.1 Setting Λ(x) = 2x, we get x -P ϕ (x -Λ(x)) = ⎧ ⎪ ⎨ ⎪ ⎩ x, if |x| ≤ 1, 2x -1, if x ≥ 1, 2x + 1, if x ≤ -1.
We see that the operator id R -P ϕ • (id R -Λ) has a unique zero on R. Proposition 2.1 Let L > 0 be given and assume that the mapping G :

[0, L] × R n → R n defined by (λ, y) → G(λ, y) is continuous on [0, L] × R n . Then, the mapping (λ, y) → P λ,ϕ (G(λ, y)) is continuous on [0, L] × R n .
Proof Let {y n } ⊂ R n and {λ n } ⊂ [0, L] be given sequences converging respectively to y * ∈ R n and λ n → λ * ∈ R as n → +∞. We claim that the sequence {P λ n ,ϕ (G(λ n , y n ))} tends to P λ * ,ϕ (G(λ * , y * )) as n → +∞. Indeed, setting x n := P λ n ,ϕ (G(λ n , y n )) and x * := P λ * ,ϕ (G(λ * , y * )), we have

x n -G(λ n , y n ), v -x n + λ n ϕ(v) -λ n ϕ(x n ) ≥ 0, ∀ v ∈ R n , (2.3) x * -G(λ * , y * ), v -x * + λ * ϕ(v) -λ * ϕ(x * ) ≥ 0, ∀ v ∈ R n . (2.4)
Let us first check that the sequence {x n } is bounded. Indeed, suppose on the contrary that the sequence { x n } is unbounded. Setting v := 0 in (2.3), we obtain

-x n -G(λ n , y n ), x n + λ n [ϕ(0) -ϕ(x n )] ≥ 0,
and thus

x n 2 ≤ G(λ n , y n ) x n + λ n [ϕ(0) -ϕ(x n )].
It results that for n large enough, x n = 0 and

1 ≤ G(λ n , y n ) x n + λ n x n 2 [ϕ(0) -ϕ(x n )]. (2.5)
As for n large enough, 1

x n ∈ (0, 1], we use the convexity of ϕ to obtain

ϕ x n x n ≤ 1 x n ϕ(x n ) + 1 - 1 x n ϕ(0). Thus ϕ(0) -ϕ(x n ) x n ≤ ϕ(0) -ϕ x n x n .
From (2.5), we get

1 ≤ G(λ n , y n ) x n + λ n ϕ(0) -ϕ( x n x n ) x n . (2.6)
The sequence { x n x n } remains in the compact set ∂B 1 and from the continuity of ϕ, we derive that the sequence {ϕ(

x n x n )} is bounded in R. Hence lim n→+∞ ϕ x n
x n

x n = 0.

Taking now the limit as n → +∞ in (2.6), we obtain the contradiction 1 ≤ 0. The sequence {x n } is thus bounded.

Setting v := x * in (2.3) and v := x n in (2.4), we obtain the relations

x n -G(λ n , y n ), x n -x * -λ n ϕ(x * ) + λ n ϕ(x n ) ≤ 0, (2.7) -x * -G(λ * , y * ), x n -x * -λ * ϕ(x n ) + λ * ϕ(x * ) ≤ 0. (2.8) Thus x n -x * 2 ≤ G(λ n , y n ) -G(λ * , y * ) x n -x * + (λ n -λ * )ϕ(x * ) + (λ * -λ n )ϕ(x n ).
(2.9)

Using the continuity of ϕ and the boundeness of {x n }, we get that the sequence {ϕ(

x n )} n is bounded in R. Moreover G(λ n , y n ) -G(λ * , y * ) → 0 and (λ n -λ * ) → 0 in R as n → +∞.
Relation (2.9) yields that x n → x * in R n as n → +∞. Hence the operator (λ, y) → P λ,ϕ (G(λ, y)) is continuous, which completes the proof.

Proposition 2.2 Suppose that Λ : R n → R n is continuous and ϕ : R n → R is a convex function. If there exists a continuous mapping H : R n → R n and r > 0 such that

Λ(x), H(x) + ϕ (x; H(x)) < 0, ∀ x ∈ ∂B r , (2.10
)

then deg(H, B r , 0) = (-1) n deg(id R n -P ϕ (id R n -Λ), B r , 0). Proof Let h : [0, 1] × B r → R n ;
(λ, y) → h(λ, y) := y -P λ,ϕ (y -λΛ(y) + (1λ)H(y)). Proposition 2.1 ensures that h is continuous. Let us now check that h(λ, x) = 0, ∀x ∈ ∂B r . Indeed, suppose on the contrary that there exists x ∈ ∂B r and λ ∈ [0, 1] such that h(λ, x) = 0, that is

x = P λ,ϕ (x -λΛ(x) + (1 -λ)H(x)).
We first remark that λ = 0. Indeed, if we suppose, on the contrary, that λ = 0, then x = P 0 (x + H(x)) = x + H(x). This yields H(x) = 0 which contradicts assumption (2.10).

Thus λ > 0 and

λΛ(x) -(1 -λ)H(x), v -x + λϕ(v) -λϕ(x) ≥ 0, ∀ v ∈ R n .
It results that (see Remark 2.1)

λΛ(x) -(1 -λ)H(x), ξ + λϕ (x; ξ) ≥ 0, ∀ ξ ∈ R n .
Setting ξ := H(x), we obtain

λ[ Λ(x), H(x) + ϕ (x; H(x))] ≥ (1 -λ) H(x) 2 ≥ 0,
which contradicts assumption (2.10).

Therefore,

deg(id R n -P ϕ (id R n -Λ), B r , 0) = deg(h(1, • ), B r , 0) = deg(h(0, • ), B r , 0) = deg(id R n -P 0 (id R n + H), B r , 0) = deg(-H, B r , 0) = (-1) n deg(H, B r , 0),
which completes the proof.

Some Existence Results for Finite Variational Inequalities

As a direct consequence of Proposition 2.2, we have the following existence results for finite dimensional variational inequalities. Theorem 3.1 Suppose that (1) Λ : R n → R n is a continuous operator;

(2) ϕ : R n → R is a convex function;

(3) there exists r > 0 such that

Λ(x), x -ϕ (x; -x) > 0, ∀ x ∈ ∂B r .
Then there exists x ∈ B r such that

Λ(x), v -x + ϕ(v) -ϕ(x) ≥ 0, ∀ v ∈ R n .
Proof Just apply Proposition 2.2 with H := -id R n . Indeed, here we have

Λ(x), H(x) + ϕ (x; H(x)) = -Λ(x), x + ϕ (x; -x).
Theorem 3.2 Suppose that (1) Λ : R n → R n is continuous;

(2) ϕ : R n → R is convex and Lipschitz continuous with Lipschitz constant K > 0, i.e.,

| ϕ(x) -ϕ(y) |≤ K x -y , ∀ x, y ∈ R n ;
(3) there exists r > 0 such that

Λ(x) > K, ∀ x ∈ ∂B r and deg(Λ, B r , 0) = 0.
Then there exists x ∈ B r such that

Λ(x), v -x + ϕ(v) -ϕ(x) ≥ 0, ∀ v ∈ R n .
Proof Just apply Proposition 2.2 with H := -Λ. Indeed, we have

Λ(x), H(x) + ϕ (x; H(x)) = -Λ(x) 2 + ϕ (x; -Λ(x)) ≤ -Λ(x) 2 + K Λ(x) = Λ(x) (K -Λ(x) ). Therefore Λ(x), H(x) + ϕ (x; H(x)) < 0, ∀ x ∈ ∂B r . Proposition 2.2 ensures that deg(id R n -P ϕ (id R n -Λ), B r , 0) = (-1) n deg(H, B r , 0) = deg(Λ, B r , 0) = 0.
Hence, there exists x ∈ B r such that x = P ϕ (x -Λ(x)). The conclusion follows.

Theorem 3.3 Suppose that

(1) Λ : R n → R n is continuous and that there exists r > 0 such that Λx, x > 0, ∀ x ∈ ∂B r and deg(id R n + Λ, B r , 0) = 0;

(2) ϕ : R n → R is a convex function satisfying

ϕ (x; -x -Λx) ≤ 0, ∀ x ∈ ∂B r .
Then there exists x ∈ B r such that

Λ(x), v -x + ϕ(v) -ϕ(x) ≥ 0, ∀ v ∈ R n .
Proof Just take H := -id R n -Λ in Proposition 2.2. Indeed, we have

Λ(x), H(x) + ϕ (x; H(x)) = -Λ(x) 2 -Λ(x), x + ϕ (x; -x -Λ(x)) < 0, ∀x ∈ ∂B r .
According to Proposition 2.2, we have

deg(id R n -P ϕ (id R n -Λ), B r , 0) = (-1) n deg(H, B r , 0) = deg(id R n + Λ, B r , 0) = 0.
Hence, there exists x ∈ B r such that x = P ϕ (x -Λ(x)). The conclusion follows.

Corollary 3.1 Let f ∈ R n be given. Suppose that (1) A ∈ R n×n is a real nonsingular matrix;

(2) ϕ : R n → R is convex and Lipschitz continuous with Lipschitz constant K > 0.

Then there exists x ∈ R n such that

Ax -f, v -x + ϕ(v) -ϕ(x) ≥ 0, ∀ v ∈ R n .
Proof The result is a consequence of Theorem 3.2 with Λ defined by

Λ(x) = Ax -f, ∀ x ∈ R n .
The matrix A is nonsingular and thus there exists c > 0 such that

Ax ≥ c x , ∀ x ∈ R n . Let us choose r > max K + f c , A -1 f . We see that if x = r, then Λ(x) ≥ Ax -f ≥ c x -f > K.
On the other hand, we remark that

h(λ, x) := Ax -λf = 0, ∀ λ ∈ [0, 1], x ∈ ∂B r .
Indeed, suppose on the contrary that there exists λ ∈ [0, 1] and x ∈ ∂B r such that Ax = λf . Then

x = λ A -1 f ≤ A -1 f ,
and we obtain the contradiction r ≤ A -1 f . Thus

deg(A. -f, B r , 0) = deg(h(1, • ), B r , 0) = deg(h(0, • ), B r , 0) = deg(A., B r , 0) = sign (det A) = 0,
which completes the proof.

The Poincaré Operator

Let us first recall some general existence and uniqueness results (see e.g. [START_REF] Showalter | Monotone Operators in Banach Spaces and Nonlinear Partial Differential Equations[END_REF]).

Theorem 4.1 Let ϕ : R n → R be a convex function. Let F : R n → R n be a continuous operator such that for some ω ∈ R, F + ωI is monotone, i.e.,

F (x) -F (y), x -y ≥ -ω x -y 2 , ∀ x, y ∈ R n . Suppose that f : [0, +∞) → R n satisfies f ∈ C 0 ([0, +∞); R n ), df dt ∈ L 1 loc (0, +∞; R n ).
Let u 0 ∈ R n and 0 < T < +∞ be given. There exists a unique u

∈ C 0 ([0, T ]; R n ) such that du dt ∈ L ∞ (0, T ; R n ); (4.1) u is right-differentiable on [0, T ); (4.2) u(0) = u 0 ; (4.3) du dt (t) + F (u(t)) -f (t), v -u(t) + ϕ(v) -ϕ(u(t)) ≥ 0, ∀ v ∈ R n , a.e., t ∈ [0, T ]. (4.4)
Remark 4.1 Suppose that F : R n → R n is of the type

F (x) = Ax + Ψ (x) + F 1 (x), ∀ x ∈ R n , where A ∈ R n×n is a real matrix, Ψ ∈ C 1 (R n ; R) is convex and F 1 is Lipschitz continuous, i.e., F 1 (x) -F 1 (y) ≤ k x -y , ∀ x, y ∈ R n
for some constant k > 0. Then F is continuous and F + ωI is monotone provided that

ω ≥ sup x =1 -Ax, x + k.
We note that if F is k-Lipschitz, then F + kI is monotone.

du dt (t) + F (u(t)) -f (t), ξ + ϕ (u(t); ξ) ≥ 0, ∀ ξ ∈ R n , a.e., t ∈ [0, T ].
Let T > 0 be given. Theorem 4.1 enables us to define the one parameter family {S(t) : 0 ≤ t ≤ T } of operators from R n into R n , as follows:

∀ y ∈ R n , S(t)y = u(t), (4.6)
u being the unique solution on [0, T ] of the evolution problem (4.1)-(4.4). Note that ∀ y ∈ R n , S(0)y = y.

Lemma 4.1 (See e.g. [START_REF] Showalter | Monotone Operators in Banach Spaces and Nonlinear Partial Differential Equations[END_REF]) Let T > 0 be given and let a, b ∈ L 1 (0, T ; R) with b(t) ≥ 0 a.e., t ∈ [0, T ]. Let the absolutely continuous function w : [0, T ] → R + satisfy

(1 -α) dw dt (t) ≤ a(t)w(t) + b(t)w α (t), a.e., t ∈ [0, T ],
where 0 ≤ α < 1. Then

w 1-α (t) ≤ w 1-α (0)e Ê t 0 a(s)ds + t 0 e Ê t s a(q)dq b(s)ds, ∀ t ∈ [0, T ].
Theorem 4.2 Suppose that the assumptions of Theorem 4.1 hold. Then

S(t)y -S(t)z ≤ e ωt y -z , ∀ y, z ∈ R n , t ∈ [0, T ].
Proof Let y, z ∈ R n be given. We have

- d dt S(t)y + F (S(t)y) -f (t), S(t)z -S(t)y -ϕ(S(t)z) + ϕ(S(t)y) ≤ 0, a.e., t ∈ [0, T ], d dt S(t)z + F (S(t)z) -f (t), S(t)z -S(t)y -ϕ(S(t)y) + ϕ(S(t)z) ≤ 0, a.e., t ∈ [0, T ].
It results that for almost every t ∈ [0, T ] we have

d dt (S(t)z -S(t)y), S(t)z -S(t)y ≤ ω S(t)z -S(t)y -[F + ωI](S(t)z) -[F + ωI](S(t)y), S(t)z -S(t)y .2
Since by assumption, F + ωI is monotone, it results that

d dt S(t)z -S(t)y 2 ≤ 2ω S(t)z -S(t)y 2 , a.e., t ∈ [0, T ]. (4.7)
Using Lemma 4.1 with w(

• ) := S( • )z -S( • )y 2 , a( • ) := 2ω, b( • ) = 0, α = 0, we get S(t)z -S(t)y 2 ≤ z -y 2 e 2ωt , ∀ t ∈ [0, T ].
The conclusion follows.

Let us now consider the Poincaré operator S(T ) : R n → R n given by y → S(T )y. Theorem 4.2 ensures that S(T ) is Lipschitz continuous, i.e., S(T )y -S(T )z ≤ e ωT yz , ∀ y, z ∈ R n . Remark 4.3 ( i ) Note that if F is continuous and monotone, then Theorem 4.2 holds with ω = 0. In this case, the Poincaré operator S(T ) is nonexpansive, i.e., S(T )y -S(T )z ≤ yz , ∀ y, z ∈ R n .

(ii) If F is continuous and strongly monotone, i.e., there exists α > 0 such that

F (x) -F (y), x -y ≥ α x -y 2 , ∀ x, y ∈ R n ,
then Theorem 4.2 holds with ω = -α < 0 and the Poincaré operator S(T ) is a contraction.

According to (4.6), the unique solution of the problem (4.1)-(4.4) satisfies, in addition, the periodicity condition

u(0) = u(T )
if and only if y is a fixed point of S(T ), that is,

S(T )y = y.
Thus the problem of the existence of a periodic solution for the evolution problem (4.1)-(4.2), (4.4) reduces to the existence of a fixed point for S(T ).

Periodic Solutions

Definition 5.1 Let Ω ⊂ R n be a given subset of R n . We say that V ∈ C 1 (R n ; R) is a guiding function for (4.5) on Ω provided that

F (x) -f (t), ∇V (x) + ϕ (x; ∇V (x)) < 0, ∀ x ∈ Ω, t ∈ [0, T ].
(5.1) Remark 5.1 ( i ) Suppose that there exists a guiding function V ∈ C 1 (R n ; R) for (4.5) on ∂B r (r > 0), i.e.,

F (x) -f (t), ∇V (x) + ϕ (x; ∇V (x)) < 0, ∀ x ∈ ∂B r , t ∈ [0, T ].
Then for any τ ∈ [0, T ], we have

deg(∇V, B r , 0) = (-1) n deg(id R n -P ϕ (id R n -F + f (τ )), B r , 0). (5.2)
Relation in (5.2) is a consequence of Proposition 2.2.

(ii) Suppose that there exists a guiding function V ∈ C 1 (R n ; R) for (4.5) on

Ω R := {x ∈ R n : x ≥ R}, R > 0.
Then for r ≥ R and any τ ∈ [0, T ], we have

ind(V, ∞) = (-1) n deg(id R n -P ϕ (id R n -F + f (τ )), B r , 0).
Proposition 5.1 Suppose that there exists R > 0 such that

F (x) -f (t), ∇V (x) < 0, ∀ x ∈ R n , x ≥ R, t ∈ [0, T ]. (5.3)
Then for r ≥ R and any τ ∈ [0, T ], we have

ind(V, ∞) = deg(f (τ ) -F, B r , 0).
Proof Let r ≥ R be given and let h : [0, 1] × B r → R n be the mapping defined by (λ, y) → h(λ, y) := λ∇V (y) + (1λ)(f (0) -F (y)). We claim that h(λ, y) = 0, ∀ y ∈ ∂B r , λ ∈ [0, 1]. Indeed, suppose by contradiction that

λ∇V (y) + (1 -λ)(f (τ ) -F (y)) = 0 for some y ∈ ∂B r and λ ∈ [0, 1]. Then λ ∇V (y), f(τ ) -F (y) = -(1 -λ) f (τ ) -F (y) 2 .
(5.4)

If λ = 0, relation (5.4) implies that f (τ )-F (y) = 0, and since y ∈ ∂B r and r ≥ R, we derive from relation (5.3) a contradiction. Hence, λ = 0 and relation (5.4) yields ∇V (y), f(τ ) -F (y) < 0 and a contradiction to (5.3). Thus,

deg(∇V, B r , 0) = deg(h(1, • ), B r , 0) = deg(h(0, • ), B r , 0) = deg(f (τ ) -F, B r , 0). Theorem 5.1 Suppose that f ∈ C 0 ([0, +∞); R n ) and df dt ∈ L 1 loc (0, +∞; R n ).
Let ϕ : R n → R be a convex function. Let F : R n → R n be a mapping satisfying the conditions of Theorem 4.1. Suppose that there exist constants

c 1 > 0, c 2 > 0, c 3 > 0, C 1 ≥ 0, C 2 ≥ 0 and a function W ∈ C 1 (R n ; R) such that c 1 x 2 ≤ W (x) ≤ c 3 x 2 , ∀ x ∈ R n ,
(5.5)

c 2 ∇W (x) 2 ≤ W (x), ∀ x ∈ R n , (5.6)
F (x), ∇W (x) + ϕ (x; ∇W (x)) ≤ C 1 ∇W (x) 2 + C 2 ∇W (x) , ∀ x ∈ R n . (5.7)
Let T > 0 be given. Assume that there exists a (guiding

) function V ∈ C 1 (R n ; R) and R > 0 such that F (x) -f (t), ∇V (x) + ϕ (x; ∇V (x)) < 0, ∀ x ∈ R n , x ≥ R, t ∈ [0, T ].
(5.8)

Then there exists r 0 > R such that for any τ ∈ [0, T ], we have

deg(id R n -S(T )( • ), B r , 0) = deg(id R n -P ϕ (id R n -F + f (τ )), B r , 0) = (-1) n ind(V, ∞), ∀ r ≥ r 0 .
Proof Let us first remark that without any loss of generality, we may assume that C 1 > 0. We set

r 0 := R √ c 3 √ c 1 e C 1 2c 2 T + √ c 2 C 2 √ c 1 C 1 (e C 1 2c 2 T -1) + 1 2 √ c 1 c 2 T 0 f (s) e C 1 2c 2
s ds.

(1) We claim that if y ∈ R n , y = r with r ≥ r 0 , then

S(t)y ≥ R, ∀ t ∈ [0, T ].
Suppose by contradiction that there exists t * ∈ [0, T ] such that S(t * )y < R. We know that u(

ϕ(v) -ϕ(Y (t)) + - dY dt (t), v -Y (t) ≥ -F (Y (t)) + f (t * -t), v -Y (t) . Hence dY dt (t), ξ ≤ F (Y (t)) -f (t * -t), ξ + ϕ (Y (t); ξ), ∀ ξ ∈ R n , a.e., t ∈ [0, t * ]. Set v = ∇W (Y (t)) to obtain dY dt (t), ∇W (Y (t)) ≤ F (Y (t)) -f (t * -t), ∇W (Y (t)) + ϕ (Y (t); ∇W (Y (t))) ≤ C 1 ∇W (Y (t)) 2 + C 2 ∇W (Y (t)) + f (t * -t) ∇W (Y (t)) ≤ C 1 c 2 W (Y (t)) + C 2 √ c 2 W (Y (t)) + 1 √ c 2 f (t * -t) W (Y (t)) , a.e., t ∈ [0, t * ]. Thus 1 2 d dt W (Y (t)) ≤ C 1 2c 2 W (Y (t)) + C 2 2 √ c 2 W (Y (t)) + 1 2 √ c 2 f (t * -t) W (Y (t)), a.e., t ∈ [0, t * ]. Using Lemma 4.1 with w( • ) := W (Y ( • )), a( • ) := C 1 2c 2 , b( • ) := 1 2 √ c 2 (C 2 + f (t * -• ) ) and α := 1 2 , we obtain for every t ∈ [0, t * ], W (Y (t)) ≤ W (Y (0)) e C 1 2c 2 t + t 0 C 2 2 √ c 2 e C 1 2c 2 (t-s) ds + t 0 1 2 √ c 2 f (t * -s) e C 1 2c 2
(t-s) ds.

Thus, for every t ∈ [0, t * ], s ds = r 0 .

Y (t) ≤ 1 √ c 1 √ c 3 Y (0)
Hence, y < r 0 , a contradiction.

Let r ≥ r 0 be given.

(2) We claim that there exists ε > 0 and T * ∈ (0, T ] such that F (x)-f (t), ∇V (y) + ϕ (x; ∇V (y)) < 0, ∀ x ∈ R n , y ∈ R n , y = r, x-y ≤ ε, t ∈ [0, T * ].

Indeed, recalling that the mapping (z, ξ) → ϕ (z; ξ) is upper semicontinuous (see e.g. [START_REF] Hiriart-Urruty | Fundamentals of Convex Analysis[END_REF]), we note that the mapping (t, x, y) → F (x)f (t), ∇V (y) + ϕ (x; ∇V (y)) is upper semicontinuous on [0, T ] × R n × R n , and if y ∈ R n , y = r ≥ r 0 ≥ R, then (by condition (5.8))

F (y)f (0), ∇V (y) + ϕ (y; ∇V (y)) < 0.

Thus, for t > 0 close to 0, say t ≤ T * , and x closed to y, say xy ≤ ε, ε > 0 small enough, we have F (x)f (0), ∇V (y) + ϕ (x; ∇V (y)) < 0.

(3) We claim that there exists T ∈ (0, T * ] such that

S(t)y -y ≤ ε, ∀ y ∈ ∂B r , ∀ t ∈ [0, T ].
Indeed, by contradiction suppose that there exists sequences {t n } and {y n } with t n ∈ [0, T * n ] (n ∈ N, n ≥ 1), y n = r and such that S(t n )y ny n > ε. Taking a subsequence, y, if necessary, we may assume that t n → 0+ and y n → y * ∈ ∂B r . On the other hand, we have S(t n )y ny n = S(t n )y n -S(t n )y * + S(t n )y *y n ≤ S(t n )y n -S(t n )y * + S(t n )y *y n .

Then, using Theorem 4.2, we obtain S(t n )y ny n ≤ √ e 2wt n y ny * + S(t n )y *y n .

Using the continuity of the map t → S(t)y, we see that S(t n )y ny n → 0, a contradiction.

Remark 4 . 2

 42 (i) The variational inequality in (4.4) can also be written as the differential inclusion du dt(t) + F (u(t))f (t) ∈ -∂ϕ(u(t)), a.e., t ∈ [0, T ],(4.5)(ii) Let u : [0, T ] → R be the unique solution of (4.1)-(4.4). Then

( 4 )

 4 Let H T : [0, 1] × C r → R n ; (λ, y) → H T (λ, y) := y -(1λ)∇V (y) -S(λT )y. We claim that the homotopy H T is such that 0 = H T (λ, y), ∀ y ∈ ∂B r , λ ∈ [0, 1]. By contradiction, suppose that there exists y ∈ R n , y = r and λ ∈ [0, 1] such that y -(1λ)∇V (y) -S(λT )y = 0. Then S(λT )yy = -(1λ)∇V (y)

  • ) ≡ S( • )y satisfies (4.5), i.e.,

			du dt	(t) + F (u(t)) -f (t) ∈ -∂ϕ(u(t)), a.e., t ∈ [0, T ],	(5.9)
	and thus
	du dt	(t ].	(5.10)
	Setting
					Y (t) = u(t * -t), t ∈ [0, t * ],
	we derive	-	dY dt	(t) + F (Y (t)) -f (t * -t) ∈ -∂ϕ(Y (t)), a.e., t ∈ [0, t * ].	(5.11)

*t) + F (u(t *t))f (t *t) ∈ -∂ϕ(u(t *t)), a.e., t ∈ [0, t *

Thus, for every v ∈ R n and almost every t ∈ [0, t * ], we have

  e Since Y (t * ) = u(0) = S(0)y = y and Y (0) = u(t * ) = S(t * )y, we get

	C 1 2c 2 f (t y ≤ t + t 0 C 2 2 √ c 2 e C 1 2c 2 (t-s) ds + t 0 1 2 √ c 2 1 √ c 1 √ c 3 S(t * )y e C 1 2c 2 t * + t * 0 C 2 2 √ c 2 e C 1 2c 2 (t t * 0 1 2 √ f (t C 1 2c 2 c 2 < R √ c 3 √ c 1 e C 1 2c 2 T + √ c 2 C 2 √ c 1 C 1 (e C 1 2c 2 T -1) + 1 2 √ 0 c 1 c 2 T f (s) e C 1 2c 2	(t * -s) ds

*s) e * -s) ds + *s) e

and thus S(λT )yy, ∇V (y) = -(1λ) ∇V (y) 2 ≤ 0.

(5.12)

On the other hand, we know that d dt S(t)y, v -S(t)y + ϕ(v)ϕ(S(t)y) ≥ -F (S(t)y) + f (t), v -S(t)y , This contradicts relation (5.12).

(5) Thanks to part (4) of this proof, we may use the invariance by homotopy property of the topological degree and observe that

Thus

V (y) = V (S(h)y).

(5.14)

On the other hand, This contradicts (5.14).

(7) Thanks to part [START_REF] De Blasi | Topological degree and periodic solutions of differential inclusions[END_REF] of this proof, we may use the invariance by homotopy property of the topological degree and see that

In conclusion, for all r ≥ r 0 , we have

Finally, for any τ ∈ [0, T ], we have also (see Proposition 2.2 and Remark 5.1)

Let ϕ : R n → R be a convex function. Let F : R n → R n be a mapping satisfying the conditions of Theorem 4.1. Suppose in addition that there exist constants

(5.17)

Let T > 0 be given. Assume that there exists

and ind(V, ∞) = 0.

Then there exists at least one

)

Proof We may apply Theorem 5.1 with W (x) = 1 2 x 2 . It results that for r > 0 large enough, we have deg(id R n -S(T )., B r , 0) = 0 and the existence of a fixed point for the Poincaré operator follows from the existence property of the topological degree.

Let ϕ : R n → R be a convex and Lipschitz continuous function. Let F : R n → R n be a mapping satisfying the conditions of Theorem 4.1. Suppose in addition that there exists

for some constants c 1 > 0, c 2 > 0 and c 3 > 0.

Let T > 0 be given. There exists at least one

Proof We may apply Theorem 5.1 with W = Φ and V = -Φ. Indeed, let K > 0 denote the Lipschitz constant of ϕ. We have

Let ϕ : R n → R be a convex and Lipschitz continuous function and let T > 0 be given. Let A ∈ R n×n be a real matrix and denote by σ(A) the set of eigenvalues of A. If

Proof Our assumption Re(σ(A)) ⊂]0, +∞[ together with Lyapunov's Theorem ensures the existence of a positive definite matrix G such that

Then

Thus, for R > 0 large enough, condition (5.18) is satisfied. It is also clear that condition (5.17

then condition (5.17

We have

Hence Condition (5.17) of Corollary 5.1 is satisfied with

Example 5.2 If we take F (x) = -x and ϕ(x) = x , then

Hence Condition (5.17) of Corollary 5.1 is satisfied with C 1 = 0 and C 2 = 1.

Second Order Periodic Dynamical System with Friction

Let us consider the following second order dynamical system with periodic conditions: For (q 0 , q0 ) ∈ R m × R m , we consider the problem P (q 0 , q0 ) of finding a function t → q(t)

q(0) = q(T ) and q(0) = q(T ), (

In this problem Φ : R l → R is a convex function, M ∈ R m×m is a symmetric and positive definite matrix, C ∈ R m×m and K ∈ R m×m are given matrices and H 1 ∈ R m×l is a given matrix whose coefficients are related to the directions of friction forces. The function

The second order dynamical system (6.4) is useful for the study of many problems in unilateral mechanics. Indeed, the motion of various mechanical systems with frictional contact can be studied within the framework of equation (6.4). For such problems m is the number of degrees of freedom, M is the mass matrix, C is the viscous damping matrix and K is the stiffness matrix. The vector q ∈ R m is the vector of generalised coordinates. The term

) is used to model the unilaterality of the contact induced by the friction forces.

Since the matrix M is symmetric and positive definite, then problem (6.4) is equivalent to the first order variational inclusion: ẋ(t) + A(x(t))f (t) ∈ -∂ϕ(x(t)),

x(0) = x(T ), where the vector x =

x 1 x 2 ∈ R n (n = 2m) and the matrix A ∈ R n×n is defined by

)

and the convex function ϕ : R n → R is defined by

In this case, let us observe that the subdifferential of ϕ is given by

It is clear that A is continuous and A + ωI n×n is monotone provided that ω ≥ sup

x =1

-Ax, x .

As a direct consequence of Corollary 5.3, we obtain an existence result for second order periodic systems.

Theorem 6.1 If the function Φ is convex and Lipschitz continuous and Re(σ(A)) ⊂]0, +∞[, then there exists at least one q ∈ C 1 (0, T ; R n ) such that d 2 q dt 2 ∈ L ∞ (0, T ; R n ) satisfying (6.3)-(6.4). Remark 6.1 We note that the conclusions of Theorem 6.1 hold under the key assumption that Φ is convex and Lipschitz continuous. Let us now give a counterexample when Φ is convex but not Lipschitz. Let us take m = 1, Φ : R →

0) = q(1), q(0) = q(1).

(6.10)

We let the reader check that problem (6.10) has no solutions. We consider the following problem ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ mq(t) + c q(t) + kq(t) -F (t) ∈ -Sign( q(t)), t ∈ [0, T ], q(0) = q(T ), q(0) = q(T ) (6.11) with F ∈ C 0 ([0, +∞[; R) such that dF dt ∈ L 1 loc ([0, +∞[; R). The matrix A in (6.5) is given by

.

We suppose that m, c, k > 0 and set Δ = c 2 m 2 -4 k m . Then we have

We note that in both cases Re(σ(A)) ⊂]0, +∞[ and hence by Theorem 6.1, problem (6.11) has at least a solution.