Yannick Benezeth

Grégoire Bachman

Guylaine Le Jan

Nathan Souviraà-Labastie

Frédéric Bimbot

BL-Database: A French audiovisual database for speech driven lip animation systems

Keywords: and Language Processing Perception, Cognition, Interaction 3D audiovisual speech database, speech-driven lip animation

The lack of publicly available annotated databases is a major limitation to research advances in speech processing. We describe in this paper an audiovisual speech database which is being made available to the research community. Our database, called BL-database (Blue Lips-database), consists of 238 utterances spoken by 17 speakers. The recordings have been performed during two sessions. The data of the rst session can be used to analyze the 2D movements of the mouth while the data collected by the second session is dedicated to 3D analysis. The audio signal has been phonetically segmented and labeled.

Such data is expected to be of great interest to all research groups working on multimodal automatic speech recognition, audio/visual synchronization or speech-driven lip animation.

BL-Database : Une base de données audiovisuelle en Français pour l'animation labiale à partir de ux de parole Résumé : Le manque de bases de données annotées et librement accessibles est une limitation importante aux avancées de la recherche sur le traitement de la parole. Nous décrivons dans cet article une base de données audiovisuelle mise à la disposition de la communauté scientique. Notre base de données audiovisuelle, appelée BL-database, est composée de 238 phrases prononcées par 17 locuteurs. Les enregistrements se sont déroulés lors de deux sessions. Les données de la première session peuvent être utilisées pour l'étude des mouvements 2D de la bouche d'un locuteur alors que les données de la deuxième session permettent une analyse des mouvements 3D de la bouche. Nous fournissons également, en plus des données audiovisuelles, la transcription phonétique de la base. Ces données peuvent être utilisées pour des travaux de recherche portant sur la reconnaissance de la parole multimodale, la synchronisation audiovisuelle ou sur l'animation labiale à partir de la parole.

Mots-clés : base de données audiovisuelle 3D, animation labiale. and for linguistic research. Most are in English (e.g. [START_REF] Godfrey | SWITCHBOARD: Telephone speech corpus for research and development[END_REF][START_REF] Garofolo | TIMIT Acoustic-Phonetic Continuous Speech Corpus[END_REF]) but some are also in French [START_REF] Galliano | Corpus description of the ESTER Evaluation Campaign for the Rich Transcription of French Broadcast News[END_REF][START_REF] Avanzi | An annotated corpus for french prominence studies[END_REF].

It is important to note that human perception of speech is multimodal. The acoustic signal is the primary choice for recognizing speech but visual information (mainly lips, tongue and jaw movements) also contribute to the perception of speech. The multimodality of speech has been demonstrated with the wellknown McGurk eect [START_REF] Mcgurk | Hearing lips and seeing voices[END_REF]. Consequently, multimodal speech corpora have been collected. These corpora are usually composed of audio and visual modalities [START_REF] Patterson | CUAVE: A new audio-visual database for multimodal human-computer interface research[END_REF][START_REF] Lee | AVICAR: Audio-Visual Speech Corpus in a Car Environment[END_REF] whereas the Mocha corpus [START_REF] Wrench | A multichannel articulatory speech database and its application for automatic speech recognition[END_REF] is constituted by audio and sensor signals describing the movement of lips and tongue. These multimodal corpora are used to develop multimodal speech recognition or speech-driven lip animation algorithms.

We are interested in this latter category of method. Our objective is to study the correspondence between acoustic signals of speech and mouth movements in order to synthetically reproduce these movements on virtual characters. The work presented in this paper is within the context of the project Rev-TV which aims to create a new category of TV programs in which viewers have the opportunity to interact with the content of a TV program through an immersive and user friendly environment. Viewers will have their virtual representation in a synthetic environment. This avatar will be controlled by several methods (motion and video analysis, speech processing, etc.). In order to obtain natural looking and realistic animation of virtual characters, the lip movements shall be consistent with the speech. It is possible to make such an animation manually, by adjusting frame after frame, the control parameters of the avatar lips. The obtained results are then very realistic, but this method requires a substantial workload and does not allow real time avatar animations. Hence, methods to automatically generate lip movements from speech have been proposed. These methods can be divided into two classes, namely (1) the low-level mapping between acoustic features and mouth positions control parameters and (2) the mouth shape recognition techniques.

Methods in (1) establish the direct correspondence between audio descriptors, e.g. Mel Frequency Cepstral Coecients (MFCC) or Linear Predictive Coding (LPC) and parameters controlling the shape of the mouth (aperture, protrusion, etc.). This correspondence can be learned by neural networks, Gaussian mixture models or vector quantization (e.g. [START_REF] Frank | Automated Lip-Sync for 3D-Character Animation[END_REF][START_REF] Nakamura | Statistical multimodal integration for audio-visual speech processing[END_REF]). Then, methods in (2), are based on the mouth shape recognition from the speech signal. The mouth movements are then monitored with a discrete set of positions: the visemes. A viseme is a shape of the mouth associated with particular sounds. Observation vectors provided by a spectral and/or a temporal analysis are used to estimate the parameters of the mouth shape recognition system. Well-known techniques in automatic speech recognition, such as Hidden Markov models (HMM) [START_REF] Rabiner | A tutorial on hidden Markov models and selected applications in speech recognition[END_REF],

RR n°7711 can be used. The recognized acoustic unit can be the phoneme [START_REF] Park | Real-Time Continuous Phoneme Recognition System Using Class-Dependent Tied-Mixture HMM With HBT Structure for Speech-Driven Lip-Sync[END_REF] or the viseme [START_REF] Foo | Recognition of Visual Speech Elements Using Hidden Markov Models[END_REF]. If the recognition system is based on the phoneme recognition, a correspondence between each detected phoneme and its corresponding viseme is performed.

Unlike methods in (2) which only use an unimodal corpus with audio and phonetic transcription, methods in (1) necessitate audiovisual corpora for the supervised learning of the mouth control parameters. In this work, we are interested in speech-driven animation systems based on continuous and 3D mouth control parameters (horizontal and vertical aperture, and protrusion). Consequently, we have collected the BL-database in which we have recorded the 3D movements of the mouth of several speakers uttering specic sentences. The experimental protocol is made so that it is possible to recover 3D information of the mouth. Two spatially calibrated cameras and one depth camera are used.

The utterances have been selected in order to represent a wide variety of the diphones in the French language. Audio data have been recorded with 2 microphones. In order to easily extract the lips position in the image sequences, people were wearing blue lipstick.

This material diers from most other audio-visual databases mainly in the following aspects:

1. Specic recording materials allow to recover 3D information of the movements of the mouth, 2. The language of the database is French, 3. The speech material is composed of most the diphones of the French Language.

In the following, we present the experimental protocol and the composition of the dataset.

BL-Database

The BL-database is an audio-visual speech corpus composed of 238 sentences uttered by 17 speakers. The actual speech length by speaker is around 20 minutes. The recordings have been performed during two sessions. For the rst recording session, data have been recorded with a front view color camera and two microphones. For the second session, we have used two calibrated cameras, one depth camera and two microphones. The language of the corpus is French.

In the following, we present the database content, the recording equipment, the speakers and the speech material.

Database content

As explained previously, the recordings have been performed during two sessions.

The data of the rst session can be used to analyze the 2D movements of the mouth while the data collected by the second session have been performed for 3D analysis. It is possible to use the data of session 2 in addition to the data of session 1 for 2D analysis. Finally, depending on your application, the BL-Database is composed of:

17 speakers (about 340 minutes) for 2D analysis, 9 speakers (about 180 minutes) for 3D analysis.

Recording equipment

For each session, audio channels are sampled at 44.1 kHz with 16 bits per sample.

We have used one AKG microphone, which is composed of a CK91 capsule with a AKG SE300K preamp, and an omnidirectional Labtec microphone. AKG CK91 is a cardioid condenser capsule. For A/D conversion, a Mackie ONYX 1200F soundcard has been employed. The recordings have been realized in a specic recording room which is reasonably sound-proof and with a low reverberation.

For the rst session, video data have been recorded with a front view color camera (a Canon MVX3i) which records 25 interlaced frames per second and has a resolution of 576x720. For the second session, video data has been recorded

with the front view color camera spatially calibrated with another color side-view camera and one depth camera. The side view color camera records at 30 frames per second and has a resolution of 640x480. The depth camera, a Microsoft Kinect, records 30 depth images per second at a resolution of 640x480. In order to ensure comparable lightning conditions, the room was shaded and illuminated only by an articial light.

RR n°7711

Cameras and microphones have been arranged on a table near the speaker in order to achieve a high resolution close-up view of the speaker's face and a sufcient signal-to-noise ratio of audio signals. A standard PC display was placed in front of the speaker indicating the sentences to pronounce. The recording setup is illustrated in the Figure 1.

Figure 1: Illustration of the recording setup.

Speakers

Using only one speaker greatly simplies the recordings as well as the extraction and interpretation of the data but, in this case, it is not possible to determine general properties that hold for all speakers. Consequently, we design a corpus that contains the spoken utterances of 17 native-French speakers. The speakers was aged from 23 to 48 years-old. Table 1, presents the number of speakers in the database in each session.

Table 1: Content of the Database.

X

X X X X X X X X X Gender Session #1 #2 Male 4 5 Female 4 4
Figure 2 presents two speakers of the database recorded with the front and side-view cameras.

Speech material

The speech materials is composed of continuous spoken words. The material was developed by G. Gibert at ICP (Grenoble, France). More details about the content of the speech material can be found in [START_REF] Gibert | Analysis and synthesis of the three-dimensional movements of the head, face and hand of a speaker using Cued Speech[END_REF] (or in French with more details in [START_REF] Gibert | Conception et évaluation d'un système de synthèse 3D de Langue française Parlée Complétée (LPC) à partir du texte[END_REF]). The corpus is composed of 238 sentences, containing all diphones of the French langage.

Table 2 presents the 33 phonemes of our dataset. It is possible to observe that the frequency of occurrence of phonemes in the BL-database is closely related to the frequency of occurrence of phonemes in the French language (calculated with the ESTER dataset [START_REF] Galliano | Corpus description of the ESTER Evaluation Campaign for the Rich Transcription of French Broadcast News[END_REF]).

RR n°7711

Figure 2: Sample speakers from the database (front and side view).

Specic instructions

Each recording begins with some explanations on the objectives of the experiment. The speaker is made-up with blue lipstick and is asked to stand in front of the camera. Then, the operator explains to the speaker that he has to pronounce each sentence uently but without exagerating. In case of mistake, the speaker can repeat the sentence. Before beginning the recording, each speaker is invited to practice his elocution on 10 sample sentences. Even if an operator was present in the room, the speaker control the slides scrolling by himself.

Post-processing and annotation

The audio signal is rst manually segmented into sentences and is then segmented into phonemes with a semi-automatic annotation process. We have used forced alignment, using HTK 1 , and have then manually adjusted the phoneme borders.

Each movie is compressed with MPEG4 codec.

Conclusion

In this paper, we have presented a new French audiovisual database. This database is expected to be useful for research concerning multimodal automatic speech recognition, audio/visual synchronization or speech-driven lip animation.

The dataset has been recorded using specic recording materials (two color calibrated cameras and one depth camera) in order to study 3D information of the movements of the mouth. The corpus is balanced between men and women speakers to determine general audio properties that hold for various speakers.

Finally, the corpus has been annotated at the sentence and the phoneme level.

The dataset is freely available upon request available at http://bl-database.inria. fr/.

1 http://www.voxforge.org/home/dev/autoaudioseg RR n°7711

1

 1 IntroductionOver the past decade, speech databases have been collected, annotated and shared to the research community. Such data are very important to speed-up the development of innovative speech-related algorithms and are also necessary in order to fairly compare new algorithms over the same data. Most of these speech databases are composed of audio les associated with the corresponding phonetic transcription. These databases are primarily designed for the development of automatic speech recognition and speaker authentication systems,

  Data and information collected and generated during the 2 recording sessions are: RR n°7711 Session 1 (dedicated to the 2D analysis): 238 utterances spoken by 4 men and 4 women Audio data from 2 microphones (each audio le corresponds to one sentence uttered by one speaker), Video data recorded by 1 front-view camera (each video le corresponds to one sentence uttered by one speaker), Time-aligned phonetic transcription associated to the audio and video data, Non-nominative speaker information (age, gender). Session 2 (dedicated to the 3D analysis): 238 utterances enunciated by 5 men and 4 women Audio data from 2 microphones (each audio le corresponds to one sentence uttered by one speaker), Video data recorded by 2 spatially calibrated cameras and 1 depth camera (each video le corresponds to one sentence uttered by one speaker and recorded by one camera), Time-aligned phonetic transcription associated to the audio and video data, Calibration data (23 images of a planar checkerboard), Non-nominative speaker information (age, gender).

Table 2 :

 2 A list of the 33 phonemes in the corpus with their occurrence frequency.

	IPA symbol	Occurrence	Occurrence frequency BL-Database ESTER
	a	464	7,97	8,12
	l	388	6,66	6,35
	K	370	6,35	8,20
	i	326	5,60	5,74
	ø	296	5,08	4,49
	t	280	4,81	5,29
	e	240	4,12	5,47
	s	232	3,98	6,08
	E	222	3,81	4,77
	d	206	3,54	5,13
	y	196	3,37	2.08
	Ẽ	171	2,94	1,58
	ã	165	2,83	3,28
	o	164	2,82	1,11
	p	163	2,80	3,52
	n	162	2,78	3,00
	k	162	2,78	4,04
	u	154	2,64	1,73
	b	154	2,64	1,17
	m	147	2,52	3,01
	j	132	2,27	2,07
	g	126	2,16	0,62
	Z	120	2,06	1,12
	v	119	2,04	1,83
	Õ	98	1,68	2,10
	f	95	1,63	1,38
	z	93	1,60	1,62
	S	81	1,39	0,50
	O	69	1,18	2,56
	w	67	1,15	0,81
	oe	55	0,94	0,51
	ï	39	0,67	0,11
	4	38	0,65	0,43

http://www.inria.fr ISSN 0249-6399


Stéphane Ducasse

Manuel Oriol
email: manuel@cs.york.ac.uk

Alexandre Bergel

Challenges to support automated random testing for dynamically typed languages

Automated random testing is a proven way to identify bugs and precondition violations, and this even in well tested libraries. In the context of statically typed languages, current automated random testing tools heavily take advantage of static method declaration (argument types, thrown exceptions) to constrain input domains while testing and to identify errors. For such reason, automated random testing has not been investigated in the context of dynamically typed languages. In this paper we present the key challenges that have to be addressed to support automated testing in dynamic languages.

Introduction

Random testing is a form of automatic testing that randomly generates data input and test cases. Random testing shines in its effectiveness to identify software faults against manual testing [CPO + 11]. Random tests are appealing because they are relatively easy and cheap to obtain.

Autotest [CPL + 08, COMP08] and Yeti [START_REF] Oriol | Testing .net code with yeti[END_REF] 1 have proven that automated random testing is an effective way to identify bugs and generate test cases which reproduce them. Autotest typically finds more bugs than any kind of manual testing in very small amounts of time [START_REF] Ciupa | Finding faults: Manual testing vs. random+ testing vs. user reports[END_REF]. While all types of testing find different kinds of bugs, there is an overlap between bugs found by random testing and bugs found by other techniques.

Dynamically typed languages, including Pharo, [BDN + 09] should be able to take advantages of the benefits of au-tomated random testing. Unfortunately, current automated random testing tools heavily rely on of static type annotation: method signatures, including argument types, return types and thrown exceptions, constrain input domains used by a random test. In addition, static types qualify the software faults found by random tests (e.g., whether a fault is effectively a bug or a false positive). In this paper we present the key challenges and paths that further researchers may follow to support automated testing in dynamic languages.

First we present the principles of random automated testing in Java (Section 2) by explaining the strategies of YETI, one of the best automated random testing tools. We subsequently identify the challenges that dynamic languages pose and we sketch some possible tracks of solutions (Section 3). The focus of this article is not to propose a solution but to stress the challenges that have to be addressed to support automated random testing for dynamically typed languages.

Random Automated Testing in Java:

The Facts

Random Automated Testing Principles

To explain how random testing tools for statically typed languages work, we present how the York Extensible Testing Infrastructure (YETI) -a language agnostic automated random testing tool -works. YETI is an application coded in Java. It tests programs at random in a fully automated manner. It is designed to support various programming languages -for example, functional, procedural and object-oriented languages can easily be bound to YETI. YETI is a lightweight platform with around 10,000 lines of code for the core, the strategies and the Java binding and is available under BSD license.

Figure 1 shows the general process of an automated random testing tool. An instance database is created with some seeds (for example, 0, 1, -1 for numbers). Such database is used during the instance generation period. The instance generation step requires instances for both the receiver and arguments of a message. It uses class type profiles (types method declaration) which are stored in another database.

Then tests are created by calling methods, the tests may check the returns values and the thrown exceptions. During tests execution, when a new instance is created it may be added to the instance database. To determine whether a fault is actually found, the declared exceptions and precondition (argument types are used) are key to determine whether a fault is a bug in the analyzed software or whether it is a false positive. By default YETI uses a strategy that generates calls and selects values at random. Two main probabilities can be adjusted: the percentage of null values p null , and the percentage of newly created objects to use when testing p new . Figure 3 shows the overall process followed when YETI needs an instance for a test and calls getInstanceOfType. By default, YETI uses 10% as a default value for both p new and p null .

In the Java binding, YETI uses class loaders to find definitions of classes to tests, reflection to make calls, and a separate thread to run them. Any undeclared RuntimeException or Error is interpreted as a failure and failures are grouped into unique failures by comparing their call stack trace beyond the first line. Receiver and arguments are discarded: to avoid the fact that if we would reuse sets of arguments/receiver we could trigger the same bug.

To understand how strong typing impacts the testing process, we identify 4 main areas where the typing information is used extensively. For each of these areas, we indicate whether a dynamically typed language has an easy way of supporting it:

Type description and pool of objects. Types are necessary to construct message arguments. In YETI, a type is mainly made of a list of supertypes, a list of subtypes, a list of "constructors" (by constructors we mean method returning an instance of the class), and a list of instances. Constructors are all routines that return a value of the type, and the list of instances is a pool of objects of that type.

Many dynamically typed languages offer support for listing existing instances for a given class, which can be used as example for feeding the testing tool. Supertypes and subtypes are easily and efficiently accessible via reflec-tion. It is however more difficult to know the return type of a routine because 1) it is not declared and 2) it may vary over multiple executions.

Instance generation. In YETI, generating an instance is done through a "constructor" for such an instance. If the routine to call needs arguments, these are typed and it is easy to reuse instances of such types already present in the system through their type or create new ones through their own constructors.

Test generation and execution. To generate and execute a test, YETI either uses or generates instances of the needed types and makes a call. Without restriction to given types for the arguments, calling a method with random instances is very unlikely to produce a meaningful test.

Feedback and bug identification. In YETI, because the type is supposedly valid due to the typing information, collecting runtime exception is meaningful as only a superficial check on the APIs is needed to make sure that unique failures are in fact bugs. As mentioned previously, testing an untyped routine leads to calls that have a high risk of failing. It is also not useful to know that a routine fails when using arguments of types which were not foreseen to be usable there.

As we can see in the previous description, typing information is used at every single step of the process.

YETI Facts

By using such typing information YETI is able to run a million tests per minute -this represents a barely noticeable overhead over reflexive invocation. So far, YETI found thousands of bugs and was able to test many programs such as the Java core libraries, GWT2 , and all programs in the Qualitas Corpus [TAD + 10]. YETI also has a graphical user interface which allows the test engineers to monitor how a testing session performed so far.

Challenges for Dynamic Languages

We now explore the challenges and possible solutions posed by the absence of static types to support automated random testing.

Instance generation and execution

Obtaining instances to execute the tests is key in automated random testing. Instances are necessary to feed random tests. Constructing messages (which received objects as argument) intended to be sent to object receivers are used as input of a test.

In Smalltalk, the fact that no constructor is natively supported by the language makes the generation of well formed instance challenging. One way to circumvent this lack of constructor is to use existing instances (and thus well formed) as an input for random testing. An approach is to use heuristics based on method categories and some patterns for methods. The fact that in Pharo and Squeak the method new automatically invokes the method initialize is a good step to obtain more systematically well initialized instances.

Getting instances is easily done through exploring the instances currently in the system. In Smalltalk, it is possible to get access to all the instances of a class using messages allInstances. Reflection is simple and efficient to use. Accessing existing instances can provide specific information that generated instances could not present.

However, using existing instances as input in random tests presents two issues:

1. Partially initialization -Since Smalltalk does not offer any guarantee on whether an object is properly initialized or not, the standard Pharo distribution contains uninitialized or partially initialized instances. Those objects have their invariant broken. As an example we have found an instance of the class Point which contains the nil value as x and y and totally unused by the system. A properly initialized point contains numerical values instead.

2. Fragile objects -Randomly modifying existing objects may lead to situation where the system is put in a dangerous state. Such objects may either be discarded for not being used as a random test input or be copied. Copying objects may be an option, however it may lead to an overhead in case of a deep copy, if ever possible at all.

In addition, since we do not know the supposed type of the arguments, it is not clear what instances to pass.

Using type inference. To know the argument type, one possibility is to use type inference. Different approaches are possible: lightweight with low precision [START_REF] Pluquet | Fast type reconstruction for dynamically typed programming languages[END_REF] or heavy computation (and with the problem of the availability of the approach) [START_REF] Spoon | Demand-driven type inference with subgoal pruning: Trading precision for scalability[END_REF]. We believe that a lightweight approach is a first step to be used. As an example, RoelTyper only considers single method body to identify argument type of the method, therefore the precision of the type information is low. Another heavy approach could be to annotate methods with type information but this clearly does not scale.

Using libraries like MethodWrappers or other techniques to monitor method execution [BFJR98, Duc99] could be a possible way to collect type information. However, this is not the panacea because (1) we face a bootstrap problemwe need to use some pre-existing information (existing tests could be used to run but again the results would be driven by test quality and in absence of large coverage we may get incomplete type information). In statically type languages, the process does not require existing tests to run. ( 2) not all the methods should be executed randomly.

Executing destructive methods. Once we get access to instances to which messages can be sent, we should consider which methods to invoke. There again care is important because it is not trivial to identify potentially destructive methods. Smalltalk offers powerful features such as pointer swapping, class changing, quitting the VM, unloading classes.... Not invoking these methods is important. The Finder tool manually specifies a list of problematic methods. Another approach can be to ask programmers to tag the methods with meta information. As a general point, we believe that knowing methods which may endanger the system when run randomly is a valuable information that can make the system more robust in presence of tools such as the Finder in Pharo or Squeak [BDN + 09].

How to identify errors?

While the other problems can be fixed with the (tedious) addition of meta-data, identifying that a bug is found is a difficult question. Indeed raised exceptions are not part of method declaration in Smalltalk as this is the case in Java. Therefore we cannot simply identify a bug by looking if the exception raised was part of the declared raised exception. In addition, since there are no contracts, they cannot be used to filter wrongly passed arguments. In addition, since a wide range of objects can be passed as arguments (and could be invalid) we cannot use the fact that the arguments are valid when analyzing an exception. The combination of the absence of argument type, contracts and declared exception is clearly what makes the real error identification a challenge.

As a first way to distinguish between various situations we can consider the object receiver contained in the top frame of the method stack and to identify different errors.

Receiver on top of stack and message not understood. The idea here is how do we make sure that one sends messages that are understood by the receiver. Such situation should not happen because the tools should enumerate the methods from the receiver class. However, even such simple assumption is not always true: a message can be cancelled in superclasses using "should not implement" exception and superclass methods are banned from subclasses.

Receiver not on the top of the stack and error. This is the regular case when we get an error is because you send a message and this method sends another one and along the road there is an error. The question then is what to do? Such a situation can arise due to different causes: Badly initialized objects. For example, executing methods on an object that is not well initialized or whose invariant is broken can happen. The automatic detection of such case is difficult. Such object can either be created by a bogus initialization or the result of inadequate method execution. It is thus important to know that instances in the instance database are in a valid state.

Breaking precondition. It may happen that messages not respecting non explicit invariant lead to errors. For example sending the message reciprocal to 0@0 leads to a problem because x reciprocal does not work on number zero.

(0@0) reciprocal -> x reciprocal @ y reciprocal.

-> x reciprocal

Probably the receiver being different of 0 should be a precondition on Number»reciprocal and similarly, x != 0 and y != 0 should be the precondition of Point»reciprocal.

Another example is #() first (accessing the first element of an empty array). Here clearly a precondition would help to capture that this behavior is not an error but just a normal behavior. In addition considering specific error raised by the class can be a good starting help.

#() first -> errorSubscriptBounds:

The definition of the at: method (which leads to the previous error) shows that some errors could be used to build up a list of raised errors. Such errors could then be used to define preconditions.

Object>>at: index "Primitive. Assumes receiver is indexable. Answer the value of an indexable element in the receiver. Fail if the argument index is not an Integer or is out of bounds. Read the class comment for a discussion about that the fact that the index can be a float Since there is no contract declared, software bugs cannot be distinguished from contract violation. This clearly shows that preconditions could be useful for automated random testing in addition to the other properties they bring to software quality.

Understanding results

While performing some preliminary experiments with automated random testing in Smalltalk, we identified also the following challenge: How can we identify the impact of a bogus instances on the resulting generated errors?

For example we got an instance of Point, the point nil@nil as an available instance and it generated a lot of false positives by generating errors when executing methods that were totally correct when we picked any other instances available in the system. We identified this instance in a ad-hoc way and we believe that tools to support the understanding of the results are needed. Notice that this problem does not happen in YETI because YETI uses types and contracts as specifications for valid input. In Smalltalk, this is obviously not possible so the nil@nil example is a good one.

If somebody had specified formally Point, then nil@nil would have been illegal. In the case of Pharo, this instance lives in the system, so it was taken as possible input, and polluted your output. We analyzed why such instance was there and it was unused. Since Pharo 1.3 this instance was removed, still this is an interesting case for understanding the impact of an instance of the resulting method that are raising errors.

To illustrate this challenge, here are the data we got when performing our experiments. The existing instance nil@nil broke a lot of messages: in our experiments we obtained 3695 problematic messages. While checking the problematic messages we found that we obtained 371 buggy receivers (points with at least one zero) and a number of buggy methods r, reciprocal, guarded, negated, degrees, max, theta, as-FloatPoint, abs, isZero, truncated, rightRotated, eightNeighbors, ceiling, leftRotated, asIntegerPoint, min, normal, transposed, normalized, sign, floor, fourNeighbors, deepCopy, fourDirections, angle, rounded.

When filtering the buggy selectors by removing the bogus instance (nil@nil) from the instance database, we reduced the number of problematic methods to two: normalized and reciprocal. Such methods raised errors because of points with one zero. We identified the problems with nil@nil because we looked at all the instances that generated errors and noticed it. In this case this was simple: we got points with nil, or at least one zero. We tried to see how a tool could have help us and report a problem but we did not found a simple approach based on a correlation or statistics. In our dataset, sorting the number of problematic methods according to the receiver was not a great help.

Being able to represent results and the influence of receiver/arguments on the generated problems is thus of importance to reduce noise.

Paths towards random testing

To enable automated random testing for dynamic languages, we propose to follow these milestones:

• Dynamic Type Inference using Random Testing. One of the first actions to be done is to use type inference to get some type information. The minimum is to use a simple static analysis as proposed by RoelTyper [START_REF] Pluquet | Fast type reconstruction for dynamically typed programming languages[END_REF].

Combining an approach like the one of RoelTyper with the type collected by MethodWrapper is an interesting track to follow. However, using MethodWrapper or any execution based appraoch requires both tests availability and

• Random testing for dynamically typed languages using existing instances. Once type inference is available, it becomes possible to use instances in an image and perform either random testing or exhaustive testing of programs in an automated way. The performance associated to the testing is then dependent on the quality of the existing instances. It seems thus likely that such a technique should be applied while the program to test is stalled after being run for a while.

In parallel, identifying classes defining an initialize method (or inheriting one) should be considered to identify classes where creating instances using the method new may provide well initialized instances.

• Automated random testing for dynamically typed languages. The next step is to be create meaningful instances at random. As of now, creating random instances is easy. Making sure these are meaningful is quite difficult without additional support. It might be useful in this case to add support for contracts (pre-, postconditions, and class invariants) and to let programmers specify such contracts to decide whether instances are valid for testing. This might, for example, allow the filtering for testing of instances such as nil@nil.

• Sandboxing for testing. As a more long-term goal it might also be interesting to consider how to restrain testing so that it does not corrupt the tested images and external resources.

Figure 3 .

 3 Figure 3. Generation of values.

for(T in R0.getArgumentTypes()){ arguments.addLast(strategy.getInstanceOfType(T));

				(call) and how to interpret the results (representsFailure) are
				both defined in the language binding.
				reuse value from object pool	1-Pnew	pick value from the object pool
				Pnew
		Class type profile database	Bugs	generate value at random
	Instance	Test	on error template profile is improved	Pnull	1-Pnull
	Generation	Generation	and bugs are registered
				return null	generate value at random
		Test Execution	Error
						return value
	Instance
	database	on success instances
		created during tests
		may be added to the data
	Figure 1. Automated random testing process
	YETI contains three parts: the core infrastructure, the
	strategies, and the language-specific bindings. The core in-
	frastructure contains the code to represent routines (methods
	or functions), a graph of types (class profile database), and a
	pool of typed objects (instance database). Routines use argu-
	ments of certain types and return an object of a certain type
	(if any) for which they are considered constructors.
	// Input: Program/Strategy
	// Output: found bugs
	foundBugs = new Vector<Bug>();
	M0 = strategy.getModuleToTest();
	while (not endReached){
	R0=strategy.getRandomRoutineFromModule(M0);
	Vector<Variables> arguments =
	new Vector<Variable>();
	}
	try {
	new Variable(languageBinding.call(R0,arguments));
	} catch (Exception e) {
	if (languageBinding.representsFailure(e)){
	foundBugs.add(e);
	}
	}
	}
	Figure 2. Algorithm of automated random testing. Bolded
	source lines show where a dynamic language cannot provide
	the necessary typing information.
	Similarly to other automated random testing tools, YETI
	follows the algorithm in Figure 2. In this algorithm, getMod-
	uleToTest, getRandomRoutineFromModule, and getInstance-
	OfType are defined within the strategies. How to make a call

http://www.yetitest.org [Preprint of International Workshop on Smalltalk Technologies

2011.]

2011/8/16

http://code.google.com/webtoolkit/

2011/8/16

2011/8/16

2011/8/16

2011/8/16

Acknowledgements

This work was supported by Ministry of Higher Education and Research, Nord-Pas de Calais Regional Council and FEDER through the 'Contrat de Projets Etat Region (CPER) 2007-2013' and the Royal Academy of Engineering.


Samuel Amstutz
email: samuel.amstutz@univ-avignon.fr

Nicolas Van Goethem
email: vangoeth@ptmat.fc.ul.pt

TOPOLOGY OPTIMIZATION METHODS WITH GRADIENT-FREE PERIMETER APPROXIMATION

In this paper we introduce a family of smooth perimeter approximating functionals designed to be incorporated within topology optimization algorithms. The required mathematical properties, namely the Γ-convergence and the compactness of sequences of minimizers, are first established. Then we propose several methods for the solution of topology optimization problems with perimeter penalization showing different features. We conclude by some numerical illustrations in the contexts of least square problems and compliance minimization.

Introduction

In several areas of applied sciences, models where the perimeter of an unknown set plays a crucial role may be considered. Such problems include multiphase problems where the interface between two liquid phases is assumed to minimize a free energy while keeping its area bounded [START_REF] Gurtin | On a theory of phase transitions with interfacial energy[END_REF][START_REF] Solci | Variational models for phase separation[END_REF], or image segmentation models with Mumford-Shah type functionals [START_REF] Ambrosio | Functions of bounded variation and free discontinuity problems[END_REF]. Another important field where the perimeter comes into play is the optimal design of shapes [START_REF] Ambrosio | An optimal design problem with perimeter penalization[END_REF], such as load bearing structures or electromagnetic devices, where it aims at rendering the problem well-posed in the sense of the existence of optimal domains. However it is known that the major difficulty of standard perimeter penalization is that the sensitivity of the perimeter to topology changes is of lower order compared to usual cost functionals, like the volume (see e.g. [START_REF] Garreau | The topological asymptotic for PDE systems: the elasticity case[END_REF][START_REF] Soko | On the topological derivative in shape optimization[END_REF][START_REF] Amstutz | Sensitivity analysis with respect to a local perturbation of the material property[END_REF] for the topological sensitivity of other functionals) and thus prohibits successful numerical solution. In this paper we propose a regularization of the perimeter that overcomes this drawback and show simple applications in topology optimization and source identification. Since we believe that applications of our method could show useful in other areas of applied sciences, a brief overview of the physical motivation of our approach is first proposed.

The Ericksen-Timoshenko bar [START_REF] Rogers | Discretization and hysteresis[END_REF] was designed as an alternative to strain-gradient models to simulate microstructures of finite scale ξ, where an energy functional

G ξ (u, v) = 1 0 αξ 2 2 (v ′ ) 2 + α 2 (u -v) 2 dx
depending on two variables u, the longitudinal strain, and v, an internal variable assumed to measure all deviations from 1D deformations, is minimized in (u, v). Seeking a minumum in the second variable amounts to finding v ξ solution of the Euler-Lagrange equation -ξ 2 v ′′ ξ + v ξ = u with v ′ ξ (0) = v ′ ξ (1) = 0. Hence the problem can be restated as

u ξ ∈ argmin F ξ (u) := 1 ξ G ξ (u, v ξ ) = α 2ξ u -v ξ , u , (1.1)
where the brackets denote the L 2 scalar product. Moreover, it is observed that v ξ also minimizes Gξ (u, v) :=1 ξ G ξ (u, v) + α 2ξ u, 1 -u which, in two papers of Gurtin and Fried [START_REF] Fried | Continuum theory of thermally induced phase transitions based on an order parameter[END_REF][START_REF] Fried | Dynamic solid-solid transitions with phase characterized by an order parameter[END_REF], is identified with the free energy of (a particular choice of 1 ) some thermally induced phase transition models where u stands for the scaled temperature variation and v represents a scalar "order parameter". In [START_REF] Fried | Dynamic solid-solid transitions with phase characterized by an order parameter[END_REF], the authors consider a dimensional analysis where ξ = ε is allowed to tend to 0.

In this paper we show that for any space dimension N ,

Fε (u) := α 2ε 1 -v ε , u (1.2)
for u ∈ [0, 1] is the relaxation of F ε (u) for u ∈ {0, 1} in the weak- * topology, and converges as ε → 0 in a suitable sense and for a particular value of α independent of N to the perimeter P er(A) of A ⊂ Ω as soon as u is the characteristic function of A. As a consequence we can address topology optimization problems where the perimeter is approximated by Fε (χ A ) with A in some admissible class of shapes, which is thereby continuous for the weak- * topology of characteristic functions and obviously free of any gradient term. Let us emphasize that while the addition of the perimeter in several shape and topology optimization problems is by now quite standard, it is usually done in an ad-hoc manner to penalize an optimization algorithm, see [START_REF] Bendsøe | Topology optimization[END_REF] and the references therein. To our knowledge a proper mathematical justification is still missing and we believe that the contribution of this paper is also to propose a theoretical response to this important issue.

Here, by observing that Fε (u) = F ε (u) as soon as u takes binary values (usually 1 or 0 in topology optimization), homogenization (i.e., intermediate values of u) can be considered in the converging optimization process. Moreover, since we intend to analyze the convergence of minimizers as ε → 0, a more general notion of convergence of functionals, namely the Γ-convergence [START_REF] Maso | An introduction to Γ-convergence[END_REF][START_REF] Braides | Γ-convergence for beginners[END_REF], must be considered. In this setting, the Modica-Mortola approach to approximate the perimeter is wellknown and widely used. In image segmentation [START_REF] Ambrosio | Functions of bounded variation and free discontinuity problems[END_REF] or fracture mechanics [START_REF] Bourdin | The variational approach to fracture[END_REF], the length of the jump set of the unknown u is added to quadratic terms integrated over the smooth regions, whose joint regularization is provided by the Ambrosio-Tortorelli functional [START_REF] Ambrosio | Approximation of functionals depending on jumps by elliptic functionals via Γ-convergence[END_REF]. Let us emphasize that, as they involve a gradient term ∇u 2 L 2 , none of these two functionals are well-suited to approximate optimal solutions in topology optimization. Indeed, they are defined for H 1 functions and not for characteristic functions, hence they would require to extend the cost function to the intermediate values, typically by a relaxation which is not always doable. In addition, they are not compatible with a discretization of u by piecewise constant finite elements, which are yet the most frequently used in topology optimization.

In a previous paper [START_REF] Amstutz | Regularized perimeter for topology optimization[END_REF] the pointwise convergence of a variant of F ε (χ A ) to P er(A) for A with suitable regularity has been studied. Moreover, the topological sensitivity (or derivative) of the approximating functionals has been explicitly computed. With our approximating functionals Fε or F ε we are able to nucleate holes, in particular, we can compute the corresponding topological derivatives at the only additional cost of computing an adjoint state solution to a well-posed elliptic PDE similar to the aforementioned Euler-Lagrange equation with appropriate right hand-side. Moreover, if topology optimization is intended without using the concept of topological derivative, our formulation allows one to relax the cost function, while the perimeter term might be approximated and relaxed by Fε (u), allowing for minimizing sequences showing intermediate "homogenized" values, but nevertheless converging to a characteristic function. From a numerical point of view another direct benefit of our approach, besides the absence of lower order terms in the topological sensitivity which has been mentioned already, is that the solutions of topology optimization problems is explicitely written as a multiple infima problem, which is easy to handle (e.g., by gradient or alternated directions algorithms), as shown in three basic examples at the end of our paper.

Moreover, it is rather remarkable that Fε (u) seems not only to be arbitrarily proposed to get better numerical algorithms, but also has an intrinsic meaning in terms of physical modelling, i.e., as a free-energy type functional depending on a small parameter and where v is interpreted as a slow internal variable which tracks the fast variable u. Our approach can therefore be a tool to study limit models as ε → 0. In mechanics one may think for instance of fracture models approximated by damage models, where the damage variable is the scalar v, ε is the "thickness" of the crack, and u the displacement field, while the cost function is a Griffith-type energy [START_REF] Allaire | Damage and fracture evolution in brittle materials by shape optimization methods[END_REF][START_REF] Bourdin | The variational approach to fracture[END_REF]. Let us remark that it is a general limitation of our method that the numerical solutions to optimal structures have at least a thickness of the order of ε, itself limited by the mesh stepsize. Coming back to our first motivation example, the Eriksen-Timoshenko bar, there is an interest to replace strain-gradient models by models with internal variables and free energy functionals reading as our F ε . We believe that several other problems in physics where the perimeter enters the model could also find appropriate intepretations and/or extension in the light of our functional.

Description of the approximating functionals

Let Ω be a bounded domain of R N with Lipschitz boundary. For all u ∈ L 2 (Ω) we define

F ε (u) = inf v∈H 1 (Ω) ε 2 ∇v 2 L 2 (Ω) + 1 2ε v -u 2 L 2 (Ω) , (2.1)
i.e., F ε is equal to ε/2 times the Moreau-Yosida regularization with constant 1/ε 2 of the function v ∈ H 1 (Ω) → ∇v 2 L 2 (Ω) . For later purposes we also introduce the relaxation of F ε for the weak- * topology of L ∞ (Ω) (see Proposition 2.3), given by

Fε (u) = F ε (u) + 1 2ε u, 1 -u , (2.2)
or equivalently,

Fε (u) = inf v∈H 1 (Ω) ε 2 ∇v 2 L 2 (Ω) + 1 2ε v 2 L 2 (Ω) + u, 1 -2v . (2.3)
Throughout we use the notation u, v := Ω uvdx for every pair of functions u, v having suitable regularity. Practical expressions of F ε (u) and Fε (u) are provided below.

Proposition 2.1. Let u ∈ L 2 (Ω) be given and v ε ∈ H 1 (Ω) be the (weak) solution of

-ε 2 ∆v ε + v ε = u in Ω ∂ n v ε = 0 on ∂Ω. (2.4)
Then we have

F ε (u) = 1 2ε u -v ε , u , (2.5)
Fε (u) = 1 2ε 1 -v ε , u . (2.6)
Moreover, Fε (u) is differentiable with respect to ε with derivative

d dε Fε (u) = 1 2ε 2 3 u, v ε -2 v ε 2 L 2 (Ω) -1, u . (2.7)
Proof. The Euler-Lagrange equations of the minimization problems (2.1) and (2.3) are identical and read for the solution v ε

ε 2 ∇v ε , ∇ϕ + v ε -u, ϕ = 0 ∀ϕ ∈ H 1 (Ω), (2.8)
which is the weak formulation of (2.4). It holds in particular

ε 2 ∇v ε 2 L 2 (Ω) + v ε 2 L 2 (Ω) = v ε , u . ( 2
(u) = - 1 2ε 2 1 -v ε , u - 1 2ε vε , u .
Using (2.8) we obtain

d dε Fε (u) = - 1 2ε 2 1 -v ε , u - 1 2ε ε 2 ∇v ε , ∇ vε + v ε , vε . (2.10) Now differentiating (2.8) provides 2ε ∇v ε , ∇ϕ + ε 2 ∇ vε , ∇ϕ + vε , ϕ = 0 ∀ϕ ∈ H 1 (Ω). Choosing ϕ = v ε yields ε 2 ∇ vε , ∇v ε + vε , v ε = -2ε ∇v ε 2 L 2 (Ω) . It follows from (2.10) that d dε Fε (u) = - 1 2ε 2 1 -v ε , u + ∇v ε 2 L 2 (Ω)
. Using (2.9) and rearranging yields (2.7).

We define the sets

E = L ∞ (Ω, {0, 1}), Ẽ = L ∞ (Ω, [0, 1]),
remarking that Ẽ is obviously the convex hull of E. Let us now prove that Fε is the relaxation, i.e. the lower semicontinuous envelope, of

F ε : Fε (u) = inf{lim inf n→∞ F ε (u n ) : (u n ) s.t. u = lim n→∞ u n }.
Lemma 2.2. The functional Fε is continuous on Ẽ for the weak- * topology of L ∞ (Ω).

Proof. We first note that Ẽ, endowed with the weak- * topology of L ∞ (Ω), is metrizable. Thus continuity is equivalent to sequential continuity. Assume that u n , u ∈ Ẽ satisfy

u n ⇀ u weakly- * in L ∞ (Ω). Set v n = (-ε 2 ∆ + I) -1 u n and v = (-ε 2 ∆ + I) -1 u, so that by Proposition 2.1 Fε (u n ) = 1 2ε 1 -v n , u n , Fε (u) = 1 2ε 1 -v, u .
For all test function ϕ ∈ L 2 (Ω) we have

v n , ϕ = u n , (-ε 2 ∆ + I) -1 ϕ → u, (-ε 2 ∆ + I) -1 ϕ = v, ϕ , hence v n ⇀ v weakly- * in L 2 (Ω)
. By standard elliptic operator theory, v n H 1 (Ω) is uniformly bounded. By the Rellich theorem, one can extract a non-relabeled subsequence such that v n → w strongly in L 2 (Ω), for some w ∈ L 2 (Ω). By uniqueness of the weak limit, we have w = v and convergence of the whole sequence (v n ). Finally, as product of strongly and weakly convergent sequences, we get Fε (u n ) → Fε (u).

Proposition 2.3. The function Fε : Ẽ → R is the relaxation of the function

u ∈ Ẽ → F ε (u) if u ∈ E +∞ if u / ∈ E (2.11)
for the weak- * topology of L ∞ (Ω).

Proof. Denote by G ε the function defined by (2.11). According to Proposition 11.1.1 of [START_REF] Attouch | Variational analysis in Sobolev and BV spaces[END_REF], the problem amounts to establishing the two following assertions:

∀(u n ) ∈ Ẽ, u n ⇀ u ⇒ Fε (u) ≤ lim inf n→∞ G ε (u n ), ∀u ∈ Ẽ ∃(u n ) ∈ Ẽ s.t. u n ⇀ u, Fε (u) = lim n→∞ G ε (u n ).
Using that G ε (u) ≥ Fε (u) for all u ∈ Ẽ, the first assertion is a straightforward consequence of Lemma 2.2. Let now u ∈ Ẽ be arbitrary. A standard construction (see e.g. [START_REF] Henrot | Variation et optimisation de formes[END_REF] proposition 7.2.14) enables to define a sequence (u n ) ∈ E such that u n ⇀ u. By Lemma 2.2 there holds

Fε (u) = lim n→∞ Fε (u n ) = lim n→∞ G ε (u n ).

Γ-convergence of the approximating functionals

This section addresses the Γ-convergence of the sequence of functionals ( Fε ) when ε → 0. Note that, when a sequence is indexed by the letter ε, we actually mean any sequence of indices (ε k ) of positive numbers going to zero.

3.1. Definition and basic properties of Γ-convergence. The notion of Γ-convergence (see, e.g., [START_REF] Maso | An introduction to Γ-convergence[END_REF][START_REF] Braides | Γ-convergence for beginners[END_REF][START_REF] Attouch | Variational analysis in Sobolev and BV spaces[END_REF]) is a powerful tool of calculus of variations in function spaces. Given a metrizable space (X, d) (in our case X = Ẽ endowed with distance induced by the L 1 -norm) one would like the maps

F → inf X F and F → argmin X F
to be sequentially continuous on the space of extended real-valued functions F : X → R ∪ {+∞}. Definition 3.1. Let ( Fε ) be a sequence of functions Fε : X → R ∪ {+∞} and F : X → R ∪ {+∞}. We say that Fε Γ-converges to F iff for all u ∈ X the two following conditions hold:

(1) for all sequences (u ε )

∈ X such that d(u ε , u) → 0 it holds F (u) ≤ lim inf ε→0 Fε (u ε ), (2) there exists a sequence (ū ε ) ∈ X such that d(ū ε , u) → 0 and F (u) ≥ lim sup ε→0 Fε (ū ε ).
The key theorem we shall use in this paper reads ([10] Theorem 12.1.1):

Theorem 3.2. Let Fε : X → R ∪ {+∞} Γ-converge to F : X → R ∪ {+∞}. (1) If u ε is an approximate minimizer of Fε , i.e. Fε (u ε ) ≤ inf u∈X Fε (u) + λ ε , with λ ε → 0, then inf u∈X Fε (u) → inf u∈X F (u)
and every cluster point of (u ε ) is a minimizer of F .

(2)

If J : X → R is continuous, then J + Fε Γ-converge to J + F .
Let us emphasize that the consideration of approximate minimizers is of major importance as soon as numerical approximations are made.

Preliminary results.

It turns out that the Γ-convergence can be straightforwardly deduced from the pointwise convergence if the sequence of functionals under consideration is nondecreasing and lower semicontinuous (see, e.g., [START_REF] Maso | An introduction to Γ-convergence[END_REF] Proposition 5.4). The subsequent Lemma 3.6 as well as several numerical tests based on the expression (2.7) of the derivative lead us to conjecture that Fε is indeed nondecreasing when ε decreases. In addition, the pointwise convergence can be established, at least under some regularity assumptions, by harmonic analysis techniques, similarly to [START_REF] Amstutz | Regularized perimeter for topology optimization[END_REF]. However, the motonicity being unproven, we will proceed more directly.

We define the potential function W : R → R + by

W (s) =    s(1 -s) if 0 ≤ s ≤ 1, -s if s ≤ 0, s -1 if s ≥ 1.
We set for all u, v

∈ L 1 (Ω) × L 1 (Ω) Gε (u, v) =    ε 2 ∇v 2 L 2 (Ω) + 1 2ε v -u 2 L 2 (Ω) + 1 2ε Ω W (u) if (u, v) ∈ L 2 (Ω) × H 1 (Ω), +∞ otherwise. Note that, if (u, v) ∈ Ẽ × H 1 (Ω), then Gε (u, v) = ε 2 ∇v 2 L 2 (Ω) + 1 2ε v -u 2 L 2 (Ω) + 1 2ε u, 1 -u = ε 2 ∇v 2 L 2 (Ω) + 1 2ε v 2 L 2 (Ω) + u, 1 -2v .
Therefore we have for all u ∈ Ẽ Fε (u) = inf

v∈H 1 (Ω) Gε (u, v).
The following theorem, taken from [START_REF] Solci | Variational models for phase separation[END_REF], will play a central role in our proof. We recall (see e.g. [START_REF] Attouch | Variational analysis in Sobolev and BV spaces[END_REF]) that, when u belongs to the space BV (Ω) of functions of bounded variations on Ω, its distributional derivative Du is a Borel measure whose total mass is denoted by |Du|(Ω). If u is the characteristic function of some subset A of Ω with finite perimeter, then |Du|(Ω) corresponds to the relative perimeter of A in Ω, namely, the N -1 dimensional Hausdorff measure of ∂A \ ∂Ω.

Theorem 3.3. When ε → 0, the functionals Gε Γ-converge in L 1 (Ω) × L 1 (Ω) to the functional G(u, v) = κ|Du|(Ω) if u = v ∈ BV (Ω, {0, 1}), +∞ otherwise.
The constant κ is given by

κ = 1 2 inf R W (ϕ)dx + 1 4 R 2 e -|x-y| (ϕ(x) -ϕ(y)) 2 dxdy, ϕ(-∞) = 0, ϕ(+∞) = 1 .
Before stating our Γ-convergence result for Fε , we shall prove three technical lemmas.

Lemma 3.4. Let Φ ε be the fundamental solution of the operator

-ε 2 ∆ + I on R N . For all u ∈ L 1 (R N , [0, 1]) we have lim ε→0 Φ ε * u -u L 1 (R N ) = 0.
Proof. Let λ > 0 be arbitrary. A classical density result gives the existence of

v ∈ C(R N , [0, 1]) with compact support such that u -v L 1 (R N ) ≤ λ. We have Φ ε * u -u L 1 (R N ) ≤ Φ ε * v -v L 1 (R N ) + Φ ε * (u -v) L 1 (R N ) + u -v L 1 (R N ) .
Using that Φ ε ≥ 0 (from the maximum principle) and

R N Φ ε = 1 (from -ε 2 ∆Φ ε + Φ ε = δ), we obtain Φ ε * u -u L 1 (R N ) ≤ Φ ε * v -v L 1 (R N ) + 2 u -v L 1 (R N ) . (3.1)
Now let µ > 0. By uniform continuity of v (Heine's theorem) there exists η > 0 such that

|x -y| ≤ η ⇒ |v(x) -v(y)| ≤ µ.
We have for any

x ∈ R N |(Φ ε * v -v)(x)| = R N Φ ε (x -y)(v(y) -v(x))dy ≤ [|y-x|≤η] Φ ε (x -y)|v(y) -v(x)|dy + [|y-x|>η] Φ ε (x -y)|v(y) -v(x)|dy ≤ µ + 2 [|y-x|>η] Φ ε (x -y)dy.

By change of variable we have Φ

ε (z) = 1 ε N Φ 1 ( z ε )
. Due to the exponential decay of Φ 1 at infinity, we get for ε small enough

[|y-x|>η] Φ ε (x -y)dy ≤ µ. This shows that |(Φ ε * v -v)(x)| → 0 uniformly on R N . This entails Φ ε * v -v L 1 (R N ) → 0. Consequently, we have for ε small enough Φ ε * v -v L 1 (R N ) ≤ λ. Going back to (3.1) we arrive at Φ ε * u -u L 1 (R N ) ≤ 3λ.
As λ is arbitrary this proves the desired convergence.

We define the projection (or truncation) operator P [0,1] : R → [0, 1] by

P [0,1] (s) = max(0, min(1, s)). (3.2)
Lemma 3.5. Let (u, v) ∈ L 2 (Ω) × H 1 (Ω) and set ũ = P [0,1] (u), ṽ = P [0,1] (v). Then Gε (ũ, ṽ) ≤ Gε (u, v).

Proof. We shall show that each term in the definition of Gε is decreased by truncation. Suppose that (u, v) ∈ L 2 (Ω) × H 1 (Ω). For the first one we have ∇ṽ = χ [0<v<1] ∇v. Hence ∇ṽ 2 L 2 (Ω) ≤ ∇v 2 L 2 (Ω) . For the second term we use that the pojection P [0,1] is 1-Lipschitz, which yields

|ṽ(x) -ũ(x)| ≤ |v(x) -u(x)| ∀x ∈ Ω.
This obviously implies that ṽ -

ũ 2 L 2 (Ω) ≤ v -u 2 L 2 (Ω) .
As to the last term we notice that, by construction of W , we have 0

≤ W (P [0,1] (s)) ≤ W (s) ∀s ∈ R.
Although the third lemma holds only in dimension N = 1, it will have useful consequences in arbitrary space dimension.

Lemma 3.6. Let a < 0 < b, Ω =]a, b[ and u = χ ]0,b[ . We have lim ε→0 F ε (u) = 1 4 , d dε F ε (u) ≤ 0 ∀ε > 0.
Proof. We make the splitting

u ε = v ε + w ε with -ε 2 v ′′ ε + v ε = χ R+ on R, v ′ ε (-∞) = v ′ ε (+∞) = 0, -ε 2 w ′′ ε + w ε = 0 on [a, b], w ′ ε (a) = -v ′ ε (a), w ′ ε (b) = -v ′ ε (b),
and we find the solutions

v ε (x) = 1 2 e x/ε if x ≤ 0, 1 -1 2 e -x/ε if x ≥ 0, w ε (x) = - 1 2 e -2a/ε -1 e 2(b-a)/ε -1 e x/ε + 1 2 e 2b/ε -1 e 2(b-a)/ε -1 e -x/ε ∀x ∈ R.
After some algebra we arrive at

F ε (u) = 1 4
(e -2a/ε -1)(e 2b/ε -1) e 2(b-a)/ε -1 .

Setting t = 2/ε, we obtain

F ε (u) = 1 4 (e -ta -1)(e tb -1) e t(b-a) -1 = 1 4 (1 -e ta )(1 -e -tb ) 1 -e -t(b-a) .
Clearly,

F ε (u) → 1/4 as t → +∞. Set now h = b -a > 0, r = -a/(b -a) ∈ [0, 1], so that a = -rh, b = (1 -r)h, and
F ε (u) = 1 4 (1 -e -trh )(1 -e -t(1-r)h ) 1 -e -th .
The change of variable s = e -th leads to

F ε (u) = 1 4 (1 -s r )(1 -s 1-r ) 1 -s .
Now differentiating with respect to s yields

d ds F ε (u) = 1 4(1 -s) 2 2 -r(s r-1 + s 1-r ) -(1 -r)(s -r + s r ) . Set f (s, r) = 1 2 r(s r-1 + s 1-r ) + (1 -r)(s -r + s r ) .
We have f (e τ , r) = r cosh((1 -r)τ ) + (1 -r) cosh(rτ ) =: g r (τ ).

For fixed r ∈ [0, 1], the function g r is clearly even and nondecreasing on R + . Hence g r (τ ) ≥ g r (0) = 1 for all τ ∈ R. This implies that f (s, r) ≥ 1 for all (s, r

) ∈ R * + × [0, 1], therefore d ds F ε (u) ≤ 0 ∀(s, r) ∈ R * + × [0, 1].
Recalling that s = e -2h/ε , we derive

d dε F ε (u) ≤ 0 ∀ε > 0.
3.3. Main result. With Theorem 3.3 and the three above lemmas at hand we are now able to state and prove our Γ-convergence result.

Theorem 3.7. When ε → 0, the functionals Fε Γ-converge in Ẽ endowed with the strong topology of L 1 (Ω) to the functional

F (u) = 1 4 |Du|(Ω) if u ∈ BV (Ω, {0, 1}) +∞ otherwise.
Proof.

(1) Let (u ε ), u ∈ Ẽ be such that u ε → u in L 1 (Ω). For each ε > 0 there exists a (unique)

function v ε ∈ H 1 (Ω) such that Fε (u ε ) = Gε (u ε , v ε ). This is the solution of -ε 2 ∆v ε + v ε = u ε in Ω, ∂ n v ε = 0 on ∂Ω.
Set w ε = Φ ε * u ε , where u ε is here extended by zero outside Ω. By the Lax-Milgram theorem we have 1 2

ε 2 ∇v ε 2 L 2 (Ω) + v ε 2 L 2 (Ω) -u ε , v ε ≤ 1 2 ε 2 ∇w ε 2 L 2 (Ω) + w ε 2 L 2 (Ω) -u ε , w ε . Adding to both sides 1 2 u ε 2 L 2 (Ω) results in ε 2 ∇v ε 2 L 2 (Ω) + v ε -u ε 2 L 2 (Ω) ≤ ε 2 ∇w ε 2 L 2 (Ω) + w ε -u ε 2 L 2 (Ω) .
Yet the right hand side is bounded from above by

ε 2 ∇w ε 2 L 2 (R N ) + w ε -u ε 2 L 2 (R N ) = R N -ε 2 ∆w ε + w ε w ε -2u ε w ε + u 2 ε = R N u ε w ε -2u ε w ε + u 2 ε = R N (u ε -w ε )u ε . We obtain v ε -u ε 2 L 2 (Ω) ≤ u ε -w ε L 1 (Ω) ≤ u -Φ ε * u L 1 (Ω) + u -u ε L 1 (Ω) + Φ ε * (u ε -u) L 1 (Ω) .
By virtue of Lemma 3.4 and the Young inequality for convolutions the right hand side goes to zero, hence v ε -u ε L 2 (Ω) → 0. Next we have

v ε -u L 1 (Ω) ≤ v ε -u ε L 1 (Ω) + u ε -u L 1 (Ω) ≤ |Ω| 1/2 v ε -u ε L 2 (Ω) + u ε -u L 1 (Ω) .
It follows that v ε -u L 1 (Ω) → 0. We infer using Theorem 3.3:

lim inf ε→0 Fε (u ε ) = lim inf ε→0 Gε (u ε , v ε ) ≥ G(u, u) = 4κ F (u).
(2) Suppose that u ∈ Ẽ. By Theorem 3.3 there exists

(u ε , v ε ) ∈ L 2 (Ω) × H 1 (Ω) such that u ε → u, v ε → u in L 1 (Ω), and lim sup ε→0 Gε (u ε , v ε ) ≤ G(u, u).
By truncation (see Lemma 3.5), one may assume that u ε , v ε ∈ Ẽ. Yet Fε (u ε ) ≤ Gε (u ε , v ε ), which entails lim sup ε→0 Fε (u ε ) ≤ 4κ F (u).

(3) Finally, observing that κ is independent of Ω and the dimension N , we deduce by identification from Lemma 3.6 that κ = 1/4.

Solution of topology optimization problems with perimeter penalization

In this section we propose solution methods for the optimization of shape functionals involving the perimeter. The functionals under consideration will be of the form j α (A) = J α (χ A ), with J α (u) = J(u) + 4α|Du|(Ω). Through a continuation procedure, J α will be approximated by a sequence of auxiliary functionals of the form Jα,ε (u) = J(u) + 4α Fε (u). The issue is then to study the convergence (up to a subsequence) of sequences of minimizers of Jα,ε (u). As is well-known, the Γ-convergence of the functionals is not sufficient to guarantee this property, which is yet essential.

Preliminary results.

Lemma 4.1. Let (u ε ) be a sequence of Ẽ such that ( Fε (u ε )) is bounded. For each ε > 0 let v ε ∈ H 1 (Ω) be the solution of (2.4) with right hand side u ε . Then (v ε ) admits a subsequence which converges strongly in L 1 (Ω).

Proof. We have by definition

Fε (u ε ) = ε 2 ∇v ε 2 L 2 (Ω) + 1 2ε v ε 2 L 2 (Ω) + u ε , 1 -2v ε , and, as 0 ≤ u ε ≤ 1, u ε , 1 -2v ε ≥ Ω min(0, 1 -2v ε )dx. Setting W(s) = s 2 + min(0, 1 -2s) we obtain Fε (u ε ) ≥ Ω ε 2 |∇v ε | 2 + 1 2ε W(v ε ) dx. (4.1)
Straightforward calculations show that the function W is nonnegative, symmetric with respect to 1/2, and vanishes only in 0 and 1 (see Figure 1). We now use a classical argument due to Modica [START_REF] Modica | The gradient theory of phase transitions and the minimal interface criterion[END_REF], which consists in applying successively to the right hand side of (4.1) the elementary Young inequality and the chain rule. This entails

Fε (u ε ) ≥ Ω |∇v ε | W(v ε )dx = Ω |∇w ε |dx,
where ψ is an arbitrary primitive of √ W and w ε = ψ • v ε . The weak maximum principle implies that 0 ≤ v ε ≤ 1, hence ψ(0) ≤ w ε ≤ ψ(1). It follows that (w ε ) is bounded in L 1 (Ω). By the compact embedding of BV (Ω) into L 1 (Ω), (w ε ) admits a subsequence which converges strongly in L 1 (Ω) to some function w. By construction, ψ is an increasing homeomorphism of R into itself. Denoting by ψ -1 the inverse function, we have v ε = ψ -1 • w ε . Up to a subsequence, we have w ε → w almost everywhere, thus v ε → ψ -1 • w =: v almost everywhere. The Lebesgue dominated convergence theorem yields that v ε → v in L 1 (Ω). Lemma 4.2. Let (u ε ) be a sequence of Ẽ which converges weakly- * in L ∞ (Ω) to u ∈ Ẽ. For each ε > 0 let v ε ∈ H 1 (Ω) be the solution of (2.4) with right hand side u ε . Then v ε ⇀ u weakly in L 2 (Ω).

Proof. The variational formulation for

v ε reads Ω ε 2 ∇v ε .∇ϕ + v ε ϕ dx = Ω u ε ϕdx ∀ϕ ∈ H 1 (Ω). (4.2)
Choosing ϕ = v ε and using the Cauchy-Schwarz inequality yields

ε 2 ∇v ε 2 L 2 (Ω) + v ε 2 L 2 (Ω) ≤ u ε L 2 (Ω) v ε L 2 (Ω) ≤ u ε L 2 (Ω) ε 2 ∇v ε 2 L 2 (Ω) + v ε 2 L 2 (Ω) ,
which results in

ε 2 ∇v ε 2 L 2 (Ω) + v ε 2 L 2 (Ω) ≤ u ε 2 L 2 (Ω) ≤ |Ω|. In particular we infer that v ε L 2 (Ω) ≤ |Ω|, ∇v ε L 2 (Ω) ≤ |Ω| ε . (4.3)
Coming back to (4.2) we derive that, for every ϕ ∈ H 1 (Ω),

Ω v ε ϕdx = Ω u ε ϕdx -ε 2 Ω ∇v ε .∇ϕdx.
Passing to the limit, we get with the help of (4.3)

Ω v ε ϕdx → Ω uϕdx. (4.4)
Choose now an arbitrary test function ψ ∈ L 2 (Ω), and fix ρ > 0. By density of H 1 (Ω) in L 2 (Ω), there exists ϕ ∈ H 1 (Ω) such that ϕ -ψ L 2 (Ω) ≤ ρ. From (4.4), there exists η > 0 such that

Ω (v ε -u)ϕdx ≤ ρ ∀ε < η.
We obtain for any ε < η

Ω (v ε -u)ψdx ≤ Ω (v ε -u)ϕdx + Ω v ε (ψ -ϕ)dx + Ω u(ψ -ϕ)dx ≤ ρ(1 + 2 |Ω|). Hence v ε ⇀ u weakly in L 2 (Ω). Lemma 4.3. Let (u ε ) ∈ Ẽ be a sequence such that u ε ⇀ u weakly- * in L ∞ (Ω). If u ∈ E, then u ε → u strongly in L 1 (Ω).
Proof. We have by definition

Ω (u ε -u)ϕdx → 0 ∀ϕ ∈ L 1 (Ω). (4.5)
Since u ∈ E and u ε ∈ Ẽ, we have

Ω |u ε -u|dx = [u=0] u ε dx + [u=1]
(1 -u ε )dx.

From (4.5) with ϕ = χ [u=0] we get

[u=0] u ε dx → 0. Choosing now ϕ = χ [u=1] results in [u=1]
(1 -u ε )dx → 0, which completes the proof.

The three above lemmas can be summarized in the following Proposition.

Proposition 4.4. Let (u ε ) be a sequence of Ẽ such that ( Fε (u ε )) is bounded. For each ε > 0 let v ε ∈ H 1 (Ω) be the solution of (2.4) with right hand side u ε . If u ε ⇀ u weakly- * in L ∞ (Ω) then, for some subsequence, there holds:

(1) v ε → u strongly in L 1 (Ω), ( 2
) u ∈ E, (3) u ε → u strongly in L 1 (Ω).
Proof. By Lemma 4.2, we have v ε ⇀ u weakly in L 2 (Ω), thus also weakly in L 1 (Ω) since Ω is bounded. By Lemma 4.1, we have for a subsequence v ε → v ∈ Ẽ strongly in L 1 (Ω), and subsequently by uniqueness of the weak limit we have v = u.

Next, we have in view of (2.6)

Fε (u ε ) = 1 2ε Ω (1 -v ε )u ε dx ≥ 0.
Therefore, the boundedness of ( Fε (u ε )) entails

Ω (1 -v ε )u ε dx → 0.
Yet, there holds

Ω (1 -v ε )u ε dx - Ω (1 -u)udx = Ω (u ε -u)(1 -u)dx - Ω u ε (v ε -u)dx.
Since, on one hand, u ε ⇀ u weakly- * in L ∞ (Ω) and, on the other hand, v ε → u strongly in L 1 (Ω) and u ε ∈ Ẽ, both integrals at the right hand side of the above equality tend to zero. We arrive at

Ω (1 -u)udx = 0.
In addition, due to the closedness of Ẽ in the weak- * topology of L ∞ (Ω), we have u ∈ Ẽ. We infer that u(x) ∈ {0, 1} for almost every x ∈ Ω. Finally, Lemma 4.3 implies that u ε → u strongly in L 1 (Ω).

4.2.

Existence and convergence of minimizers. Let a functional J : E → R + and a parameter α > 0 be given. We want to solve the minimization problem

I := inf u∈BV (Ω,{0,1}) {J(u) + 4α|Du|(Ω)} . (4.6)
Proposition 4.5. Assume that J is lower semi-continuous on E for the strong topology of L 1 (Ω).

Then the infimum in (4.6) is attained.

Proof. Let (u n ) ∈ BV (Ω, {0, 1}) be a minimizing sequence. By boundedness of Ω and definition of the objective functional, u n L 1 (Ω) + |Du n |(Ω) is uniformly bounded. Therefore, due to the compact embedding of BV (Ω) into L 1 (Ω), one can extract a subsequence (not relabeled) such that u n → u in L 1 (Ω), for some u ∈ L 1 (Ω). In addition, for a further subsequence, u n → u almost everywhere in Ω, thus u ∈ E. Using the sequential lower semi-continuity of J and u → |Du|(Ω), we obtain

J(u) + 4α|Du|(Ω) ≤ lim inf n→∞ J(u n ) + 4α|Du n |(Ω) = I.
It follows that u is a minimizer.

Let J : Ẽ → R + be an extension of J, i.e., a function such that J(u) = J(u) for all u ∈ E. By Theorem 3.7 we have

I = inf u∈ Ẽ J(u) + α F (u) . (4.7)
Given ε > 0 we introduce the approximate problem:

I ε := inf u∈ Ẽ J(u) + α Fε (u) . (4.8)
It turns out (cf. Proposition 4.8), that the approximate subproblem (4.8) needs to be solved only approximately. However, the existence of exact minimizers is an information of interest regarding the design and analysis of a solution method.

Proposition 4.6. Assume that J : Ẽ → R + is lower semi-continuous for the weak- * topology of L ∞ (Ω). Then the infimum in (4.8) is attained.

Proof. By Lemma 2.2, the functional u ∈ Ẽ → J(u) + α Fε (u) is lower semi-continuous for the weak- * topology of L ∞ (Ω). In addition, the set Ẽ is compact for the same topology. The claim results from standard arguments.

Thanks to Proposition 4.4 the so-called equicoercivity property might be formulated as follows.

Proposition 4.7. Let J : Ẽ → B be a given cost function, where B is a bounded subset of R. Consider a sequence

(u ε ) ∈ Ẽ such that J(u ε ) + α Fε (u ε ) ≤ I ε + λ ε ,
with (λ ε ) bounded. There exists u ∈ E and a subsequence of indices such that u ε → u strongly in L 1 (Ω).

Proof. By the limsup inequality of the Γ-convergence, there exists a sequence (z ε ) ∈ Ẽ such that z ε → 0 in L 1 (Ω) and Fε (z ε ) → F (0) = 0. For this particular sequence we have

J(u ε ) + α Fε (u ε ) ≤ J(z ε ) + α Fε (z ε ) + λ ε ,
which entails that ( Fε (u ε )) is bounded. Now, since Ẽ is weakly- * compact in L ∞ (Ω), there exists u ∈ Ẽ and a non-relabeled subsequence such that u ε ⇀ u weakly- * in L ∞ (Ω). Using Proposition 4.4, we infer that u ∈ E as well as u ε → u strongly in L 1 (Ω).

Combining Theorem 3.2, Theorem 3.7 and Proposition 4.7 leads to the following result. Theorem 4.8. Let u ε be an approximate minimizer of (4.8), i.e.

J (u

ε ) + α Fε (u ε ) ≤ I ε + λ ε ,
with lim ε→0 λ ε = 0. Assume that J is continuous on Ẽ for the strong topology of L 1 (Ω). Then we have J(u ε ) + α Fε (u ε ) → I. Moreover, (u ε ) admits cluster points, and each of these cluster points is a minimizer of (4.7). Theorem 4.8 shows in particular that, when (4.7) admits a unique minimizer u * , then the whole sequence (u ε ) converges in L 1 (Ω) to u * . We have now a solid background to address the algorithmic issue.

4.3.

Algorithms for topology optimization with perimeter penalization. As already said, we propose to use a continuation method with respect to ε. Namely, we construct a sequence (ε k ) going to zero and solve at each iteration k the minimization problem (4.8) using the previous solution as initial guess.

Several methods may be used to solve (4.8). The specific features of the functional J may guide the choice.

(1) The most direct approach consists in using methods dedicated to the solution of optimization problem with box constraints, for instance the projected gradient method. (2) When J is continuous for the weak- * topology of L ∞ (Ω) one can restrict the feasible set to E and use topology optimization methods to find an approximate minimizer. (3) Another alternative is to come back to the definition of Fε by (2.3), and write

I ε = inf u∈ Ẽ inf v∈H 1 (Ω) J(u) + α ε 2 ∇v 2 L 2 (Ω) + 1 2ε v 2 L 2 (Ω) + u, 1 -2v .
Then one can use an alternating minimization algorithm with respect to the pair of variables (u, v). In the subsequent sections we present three examples of application. The first one illustrates the method (1) in the context of least square problems. The last two ones deal with self-adjoint problems for which, as we shall see, the method (3) is particularly relevant. We refer to [START_REF] Amstutz | Regularized perimeter for topology optimization[END_REF] for some examples of application of the approach (2).

For the discretization of all the PDEs involved, we use piecewise linear finite elements on a structured triangular mesh. For each example different values of the penalization parameter α are considered. Note that choosing α too small requires, in order to eventually obtain a binary solution (i.e. u ∈ E), to drive ε towards very small values, which in turn necessitates the use of a very fine mesh to solve (2.4) with a good accuracy. This is why, to enable comparisons of solutions obtained with identical meshes and a wide range of values of α, we always use relatively fine meshes. Proposition 5.1. The functional J is continuous on Ẽ strongly in L 1 (Ω) and also weakly- * in L ∞ (Ω).

Proof. First we remark that if (u n ) is a sequence of Ẽ such that u n → u strongly in L 1 (Ω), then u n → u almost everywhere (for a subsequence), which implies that u n ⇀ u weakly- * in L ∞ (Ω) by dominated convergence. Thus, let us assume that u n ⇀ u weakly- * in L ∞ (Ω). As ( y un H 1 (Ω) ) is bounded, we can extract a subsequence such that y un ⇀ y ∈ H 1 0 (Ω) weakly in H 1 0 (Ω) and strongly in L 2 (Ω). This implies, on one hand, that y = y u , thus by uniqueness of this cluster point the whole sequence (y un ) converges to y for the aforementioned topologies, and, on the other hand, that J(u n ) → J(u). Using (2.3) and ( 6.3), this can be rewritten as inf

(u,v,τ )∈ Ẽ×H 1 (Ω)×Σ Ω γ -1 u |τ | 2 dx + ℓ Ω udx + α ε 2 ∇v 2 L 2 (Ω) + 1 2ε v 2 L 2 (Ω) + u, 1 -2v . (6.6)
Proposition 6.2. The infima (6.5) and (6.6) are attained.

Proof. Since the infima (2.3) and (6.3) are both attained, it suffices to consider (6.5). Let therefore (u n ) be a minimizing sequence for (6.5), whose corresponding solutions of (6.2) are denoted by (y n ). We extract a subsequence, still denoted (u n ), such that u n ⇀ u ∈ Ẽ weakly- * in L ∞ (Ω). By the so-called compactness property of the G-convergence (see, e.g., [START_REF] Allaire | Shape optimization by the homogenization method[END_REF] Theorem 1.2.16), we can extract a further subsequence such that the matrix-valued conductivity γ un I, where I is the identity matrix of order N , G-converges to some A, where, at each x ∈ Ω, A(x) is a symmetric positive definite N × N where y solves -div(A∇ s y) = 0 in Ω, y = 0 on ∂Ω,

with ∇ s the symmetrized gradient, or with the help of the complementary energy [START_REF] Allaire | Conception optimale de structures[END_REF],

C(A) = inf σ∈Σ Ω A -1 σ : σdx , (7.2)
with Σ = {σ ∈ L 2 (Ω) N ×N , -div σ = f in Ω}.

Given ℓ, α > 0, we want to solve inf u∈E {J(u) + 4α|Du|(Ω)} ,

with

J(u) = C(A(u)) + ℓ Ω udx, A(u)(x) = A 0 if u(x) = 0, A 1 if u(x) = 1.
Here, A 0 , A 1 are given Hooke tensors. Typically, A 1 corresponds to a physical material, while A 0 represents a weak phase of small Young modulus meant to mimick void. The problem can be reformulated as inf

u∈ Ẽ J(u) + α F (u) , where J(u) = inf A∈Gu C(A) + ℓ Ω udx, (7.4)
the convention A ∈ G u ⇐⇒ A(x) ∈ G u(x) for almost every x ∈ Ω is used, and, for each x ∈ Ω, G u(x) is a set of fourth order tensors such that

G u(x) = {A 0 } if u(x) = 0, {A 1 } if u(x) = 1.
Henceforth we choose, for all x ∈ Ω, G u(x) as the set of all Hooke tensors obtained by homogenization of tensors A 0 and A 1 in proportion 1 -u(x) and u(x), respectively (see e.g. [START_REF] Allaire | Shape optimization by the homogenization method[END_REF] for details on homogenization).

Proposition 7.1. The functional J is continuous on Ẽ strongly in L 1 (Ω).

Proof. Suppose that (u n ) ∈ Ẽ converges to u ∈ Ẽ strongly in L 1 (Ω). Thus u n → u almost everywhere for a non-relabeled subsequence. Thanks to the density of E in Ẽ for the weak- * topology of L ∞ (Ω), we may assume that (u n ) ∈ E. By compactness of the G-convergence and stability of G un with respect to this convergence (see [START_REF] Allaire | Shape optimization by the homogenization method[END_REF] Lemma 2.1.5), there exists A * n ∈ G un such that

C(A * n ) = inf A∈Gu n C(A).
Using again the compactness of the G-convergence, there exists a subsequence such that A * n Gconverges to some A * , thus C(A * n ) → C(A * ). By [START_REF] Allaire | Shape optimization by the homogenization method[END_REF] Lemma 2.1.7, there exists c, δ > 0 such that

d(G un(x) , G u(x) ) ≤ c|u n (x) -u(x)| δ (7.5)
for every x ∈ Ω, where d denotes the Hausdorff distance between sets. Hence there exists

A ♯ n ∈ G u such that |A * n -A ♯ n | ≤ c|u n -u| δ almost everywhere. By the dominated convergence theorem we get A * n -A ♯ n L 1 (Ω) → 0. Once more by compactness of the G-convergence, A ♯ n G-converges to some A ♯ ∈ G u , up to a subsequence. It follows from [1] Proposition 1.3.44 that A * = A ♯ ∈ G u .
Let now A ∈ G u be arbitrary, and denote by A n (x) the projection of A(x) onto G un(x) . Using again (7.5), we get A n (x) → A(x) almost everywhere, therefore, by [START_REF] Allaire | Shape optimization by the homogenization method[END_REF]

Lemma 1.2.22, C(A n ) → C(A). By definition we have C(A n ) ≥ C(A *
n ) for all n. Passing to the limit yields C(A) ≥ C(A * ). This means that

C(A * ) = inf A∈Gu C(A).
Eventually we have obtained

J(u n ) = C(A * n ) + ℓ Ω u n dx → C(A * ) + ℓ Ω udx = J(u).
For ε > 0 fixed we solve the approximate problem inf u∈ Ẽ J(u) + α Fε (u) . Let (u n , A n ) be a minimizing sequence. Thanks to the density of E in Ẽ for the weak- * topology of L ∞ (Ω) and the continuity of E ε (., A) for the same topology (see Lemma 2.2), we may assume that (u n ) ∈ E. We extract a subsequence, still denoted (u n ), such that u n ⇀ u ∈ Ẽ weakly- * in L ∞ (Ω). Further, by compactness of the G convergence, we can extract a subsequence such that (A n ) G-converges to some tensor field A. By construction, we have A ∈ G u . By definition of the G-convergence, the sequence of the states (y n ), solutions of (7.1) with Hooke's tensor (A n ), converges weakly in H 1 0 (Ω) to the state y associated to A. This implies that C(A n ) → C(A), and subsequently, using again Lemma 2.2, that E ε (u n , A n ) → E ε (u, A). 7.2. Description of the algorithm. We use again an alternating minimization algorithm, by performing successively a full minimization with respect to each of the variables (u, A), v, σ. The minimization with respect to σ is equivalent to solving the linear elasticity problem (7.1) and setting σ = A∇ s y. The minimization with respect to v is again done by solving (2.4). The minimization with respect to A for a given u reduces to the standard problem inf A∈Gu Ω

A -1 σ : σdx =: f (u, σ).

When A 1 and A 0 are isotropic and A 0 → 0, the minimization is achieved by using well-known lamination formulas, see [START_REF] Allaire | Shape optimization by the homogenization method[END_REF]. We have Next we address the bridge problem, where Ω is a rectangle of size 2×1.2. The structure is clamped on two segments of lengths 0.1 located at the tips of the bottom edge, and submitted to a unitary pointwise vertical force exerted at the middle of the bottom edge. The chosen Lagrange multiplier is ℓ = 30, and the mesh contains 123393 nodes. Our results are depicted on Figure 6.

f (u, σ) = A -1 1 σ : σ + 1 -u u f * (σ),

Figure 1 .

 1 Figure 1. Plot of the function W.

5 . 1 .

 51 First application: source identification for the Poisson equation 5.Problem formulation. For all u ∈ L 2 (Ω) we denote by y u ∈ H 1 0 (Ω) the solution of -∆y u = u in Ω, y u = 0 on ∂Ω,

Figure 2 .

 2 Figure 2. Source identification. Top: true sources. Then reconstructed sources for α = 10 -8 (first line), α = 10 -7 (second line) and α = 10 -6 (third line), with R = 0 (first column), R = 33% (second column) and R = 58% (third column).

Figure 4 .

 4 Figure 4. Optimized V-shaped conductor for α = 0.1, 0.5, 1, 3, respectively.

(7. 6 )v 2 L 2 ( 7 ) 7 . 2 .

 622772 Using (2.3),(7.4) and(7.2), this can be rewritten asinf u ∈ Ẽ, A ∈ G u , (v, σ) ∈ H 1 (Ω) × Σ Ω A -1 σ : σdx + ℓ Ω) + u, 1 -2v . (7.Proposition The infima (7.6) and (7.7) are attained.Proof. First, we remark that both problems (7.6) and (7.7) amount to solving inf u∈ Ẽ,A∈Gu E ε (u, A) := C(A) + ℓ Ω udx + α Fε (u) .

with, in dimension N = 2 , 3 .

 23 f * (σ) = 2µ + λ 4µ(µ + λ) (|σ 1 | + |σ 2 |) 2 .Above, λ, µ are the Lamé coefficients of the phase A 1 , and σ 1 , σ 2 are the principal stresses. Let us finally focus on the minimization with respect to We have to solveinf u∈ Ẽ Ω Φ ε,v,σ (u(x))dx , with Φ ε,v,σ (u) = f (u, σ) + ℓu + α 2ε u(1 -2v).This means that, at every point x ∈ Ω, we have to minimize the function s∈ [0, 1] → Φ ε,v,σ (s). From Φ ε,v,σ (s) = A -1 1 σ : σ + 1 -Numerical examples.We first consider the classical cantilever problem, where Ω is a rectangle of size 2 × 1. The left edge is clamped, and a unitary pointwise vertical force is applied at the middle of the right edge. We choose the Lagrange multiplier ℓ = 100, and use a mesh containing 160601 nodes. Our findings are displayed on Figure5.

Figure 5 .

 5 Figure 5. Cantilever for α = 0.1, 2, 20, 50, respectively.

Figure 6 .

 6 Figure 6. Bridge for α = 0.2, 1, 3, 10, respectively.

In particular a model with dissipationless kinetics and vanishing specific heat. 1

Acknowledgements. We thank M. Ciligot-Travain for useful remarks.

Algorithm and examples.

In our simulations y † is defined by

where y ♯ solves -∆y ♯ = u ♯ in Ω, y ♯ = 0 on ∂Ω, for some given u ♯ ∈ L 2 (D) and n ∈ L 2 (D). More precisely, n is of the form β n, with β > 0 and n a random Gaussian noise with zero mean. The function u ♯ is chosen as the characteristic function of a subdomain Ω ♯ ⊂⊂ Ω. The domain Ω is the unit square ]0, 1[×]0, 1[. We initialize ε to 1 and divide it by 2 until it becomes less that 10 -6 . The initial guess is u ≡ 1. In order to solve the approximate problems we use a projected gradient method with line search. Here the mesh contains 80401 nodes. The results of computations performed with different values of the coefficients α and β are depicted on Figure 2. Rather than β, we indicate the noise to signal ratio, viz.,

We observe, as expected, that the higher the noise level is, the larger the penalization parameter α must be chosen in order to achieve a proper reconstruction. The price to pay, of course, is that the reconstructed shapes are smoothed.

6. Second application: conductivity optimization 6.1. Problem formulation. We consider a two-phase conductor Ω with source term f ∈ L 2 (Ω). For all u ∈ Ẽ we define the conductivity

where γ 1 > γ 0 > 0 are given constants. Our objective functional is the power dissipated by the conductor augmented by a volume term, i.e.,

where ℓ is a fixed positive multiplier and y solves

Note that the Dirichlet boundary condition has been chosen merely for simplicity of the presentation. Alternatively, this functional can be expressed in terms of the complementary energy (see, e.g., [START_REF] Allaire | Conception optimale de structures[END_REF])

When it occurs that u ∈ E we set J(u) := J(u). Given α > 0, we want to solve

which amounts to solving inf u∈ Ẽ J(u) + α F (u) .

Proposition 6.1. The functional J defined by (6.1) is continuous on Ẽ strongly in L 1 (Ω).

Proof. Assume that u n → u strongly in L 1 (Ω), and denote by y n , y the corresponding states. Obviously, γ un → γ u strongly in L 1 (Ω). Then y n ⇀ y weakly in H 1 0 (Ω), see [START_REF] Attouch | Variational analysis in Sobolev and BV spaces[END_REF] Theorem 16.4.1 or [1] Lemma 1.2.22. It follows straightforwardly that J (u n ) → J(u). matrix. This means that y n ⇀ y weakly in H 1 0 (Ω), where y solves -div(A∇y) = f in Ω, y = 0 on ∂Ω.

By virtue of [1] Theorem 3.2.6, we have at each point x ∈ Ω A∇y = γ u ∇y. Therefore, by uniqueness, y is the state associated to u. By (6.1), J(u n ) → J(u) while we know by Lemma 2.2 that Fε (u n ) → Fε (u), which completes the proof.

6.2. Description of the algorithm. In the spirit of [START_REF] Allaire | Shape optimization by the homogenization method[END_REF], we use an alternating minimization algorithm, by performing successively a full minimization of (6.6) with respect to each of the variables u, v, τ . The minimization with respect to τ is equivalent to solving (6.2) and setting τ = γ u ∇y. The minimization with respect to v is done by solving (2.4). Let us focus on the minimization with respect to u. We have to solve

This means that, at every point x ∈ Ω, we have to minimize the function s

we readily find the minimizer

where we recall that P [0,1] is the projection operator defined by (3.2).

Numerical examples.

Our example is a conductor with one inlet and two outlets, see Figure 3. The domain Ω is the square ]0, 1.5[×]0, 1.5[. The conductivities of the two phases are γ 0 = 10 -3 and γ 1 = 1. The Lagrange multiplier is ℓ = 2. We initialize ε to 1 and divide it by two each time a (local) minimizer of (6.6) has been found. The procedure is stopped when ε becomes less that h/10, with h the mesh stepsize. We use a mesh with 65161 nodes. The results of computations performed with different values of α are shown on Figure 4. We assume now that Ω is occupied by a linear elastic material subject to a volume force f ∈ L 2 (Ω) N . We denote by A(x) the Hooke tensor at point x. We assume for simplicity, bu without loss of generality, that the medium is clamped on ∂Ω. The compliance can be defined either by