Numerical approximation of a one-dimensional elliptic optimal design problem

NUMERICAL APPROXIMATION OF A ONE-DIMENSIONAL ELLIPTIC OPTIMAL DESIGN PROBLEM* J. CASADO-DÍAZ†, C. CASTRO‡, M. LUNA-LAYNEZ†,AND E. ZUAZUA§ Abstract. We address the numerical approximation by finite-element methods of an optimal design problem for a two phase material in one space dimension. This problem, in the continuous setting, due to high frequency oscillations, often does not have a classical solution, and a relaxed formulation is needed to ensure existence. On the contrary, the discrete versions obtained by numerical approximation have a solution. In this article we prove the convergence of the discretizations and obtain convergence rates. We also show a faster convergence when the relaxed version of the continuous problem is taken into account when building the discretization strategy. In particular it is worth emphasizing that, even when the original problem has a classical solution so that relaxation is not necessary, numerical algorithms converge faster when implemented on the relaxed version. Key words. control in the coefficients, composite optimal design, relaxation, numerical approximation, finite elements AMS subject classifications. 49M25, 49J20 DOI. 10.1137/10081928X 1. Introduction. This paper is devoted to the finite-element numerical analysis of a problem of optimal mixture of two (thermal or electrical) materials in order to minimize a given functional in one space dimension. Let Ωbe a bounded open set of RN,N≥1(although our analysis is limited to the case N¼1, the problem makes sense in any space dimension), and consider the following optimization problem: Find ω0∈Usuch that Jðω0Þ¼min ω∈U JðωÞ: ð1:1Þ Here ω, the control, is a measurable subset of Ω,JðωÞ, the cost functional, is of the form JðωÞ¼Zω F1ðx; u; ∇uÞdxþZΩ\ω F2ðx; u; ∇uÞdx;ð1:2Þ where F1;F2∶Ω×R×RN→Rare given functions, and u, the state, is the solution of *Received by the editors December 23, 2010; accepted for publication (in revised form) May 26, 2011; published electronically September 15, 2011. http://www.siam.org/journals/mms/9-3/81928.html †Dpto. de Ecuaciones Diferenciales y Análisis Numérico, Facultad de Matemáticas, Universidad de Sevilla, C. Tarfía s/n, 41012 Sevilla, Spain ([email protected], [email protected]). The work of the first and third authors was partially supported by project MTM2008-00306 of the MICINN (Spain) and the research group FQM-309 of the CICE (Andalusia). ‡Dpto. de Matemáticas e Informática, ETSI caminos, canales y puertos, Universidad Politécnica de Madrid, Ciudad Universitaria, 28040 Madrid, Spain ([email protected]). The work of the second author was partially supported by grant MTM2008-03541 of the MICINN (Spain). §Basque Center for Applied Mathematics, Bizkaia Technology Park, Building 500. E-48160 Derio, Basque Country, Spain ([email protected]); IKERBASQUE, Basque Foundation for Science, E-48011 Bilbao, Basque Country, Spain. The work of the last author was partially supported by ERC advanced grant FP7-246775 NUMERIWAVES, grant PI2010-04 of the Basque Government, ESF Research Networking Programme OPTPDE, and grant MTM2008-03541 of the MICINN (Spain). 1181 MULTISCALE MODEL.SIMUL. Vol. 9, No. 3, pp. 1181–1216 © 2011 Society for Industrial and Applied Mathematics Copyright ©by SIAM. Unauthorized reproduction of this article is prohibited. −divððαχωþβð1−χωÞÞ∇uÞ¼fin Ω; u¼0on∂Ω ð1:3Þ for some given source term f∶Ω→R. The positive constants α,βrepresent the two materials, determining the coefficients of the corresponding diffusion matrices. Some restrictions can and must be imposed to the control ωdepending on the problem. For example, an interesting case is when the material αis more efficient than the material βbut it is also more expensive. Then, it is usual to consider a restriction of the form jωj≤κ, limiting the use of the material α. We include this restriction in the admissible set of controls U, U¼fω⊂Ω∶ωmeasurable;jωj≤κg:ð1:4Þ The existence of an optimal set ωfulfilling these constraints, for which the function usolution of (1.3) minimizes J, does not hold in general (see [15], [16]). In these cases, it is natural to look for minimizing sequences, i.e., sequences fωlg∞ l¼1⊂Usuch that lim l→∞ JðωlÞ¼inf ω∈U JðωÞ since they provide near optimal designs. A usual procedure to find such sequences is to introduce a relaxed version of the problem for which a minimizer exists. Then, a suitable approximation of the minimizers provides minimizing sequences of the original problem. For a sequentially continuous functional J, in the weak topology of the Sobolev space H1ðΩÞ(see [1], [13], [20]), this relaxation can be obtained by replacing in (1.3) the function χωwith a measurable function θtaking its values in the closed interval ½0;1and the function ðαχωþβð1−χωÞÞ with a matrix function Ain the set KðθÞof matrices constructed by homogenization (see, e.g., [17], [19], [21]) mixing the materials α and βwith respective proportions θand 1−θ. Remark that the set KðθÞis known in the case described above, corresponding to the mixture of two isotropic materials (see [14], [22]), but not in other interesting cases such as the mixture of more than two materials, anisotropic materials, etc. Henceforth we denote by ^ Uthe set of relaxed controls ðθ;AÞ. Note that functionals of the form (1.2) are not sequentially continuous in the weak topology of H1ðΩÞ, in general. In those cases, to obtain the relaxed version (see [6]) we must replace the set of controls χωand coefficients ðαχωþβð1−χωÞÞ with the pairs ðθ;AÞ∈^ Uas above, and the functional Jwith another one of the form ^ Jðθ;AÞ¼ZΩ Hðx; u; ∇u; A∇u; θÞdx;ð1:5Þ where uis solution of the homogenized problem 8 < : −divA∇u¼fin Ω; u¼0on∂Ω: ð1:6Þ An explicit expression of the function His only known in some particular cases (see the references [2], [6], [7], [8], [11], [12], [18], [23]). It satisfies Hðx; u; ∇u; A∇u; θÞ¼F1ðx; u; ∇uÞχωþF2ðx; u; ∇uÞχΩ\ω;if θ¼χω; 1182 CASADO-DÍAZ, CASTRO, LUNA-LAYNEZ, ZUAZUA Copyright ©by SIAM. Unauthorized reproduction of this article is prohibited. and A¼ðαχωþβð1−χωÞÞIand, so, the relaxed functional is in fact an extension of the original one to the larger set of relaxed controls. The relaxed control problem reads Find ðθ0;A 0Þ∈^ Usuch that ^ Jðθ0;A 0Þ¼ min ðθ;AÞ∈^ U ^ Jðθ;AÞ: ð1:7Þ In practical applications, in order to solve numerically the above control problem (1.1), it is necessary to introduce a discretization of both the control set and the functional. In the present context, we have at least two approaches to this numerical approximation issue. One based on the discretization of the original problem and one relying on the discretization of the relaxed version. Recently, in [8] and [9], both discretization procedures have been shown to converge. In these articles, some partially relaxed versions have also been studied in which the class of controls under consideration is enlarged but not to the extent of exhausting the class of the relaxed version of the problem; we refer to [12] for a related result. We also refer to [26] for the numerical study of the relaxed formulation of a particular case of problem (1.1). In this paper we compare and get convergence rates for the sequences of discrete minimizers obtained with both approximation methods. These issues are addressed in the simplest one-dimensional setting, where the partial differential equation (1.3) is reduced to an ordinary differential equation, the set KðθÞis well known to be reduced to the harmonic mean of αand βwith respective proportions θand 1−θ, and the function His explicitly known. Note that in this case we can write ^ Jðθ;AÞ¼ ^ JðθÞin (1.5), since Ais completely determined by θ, and ^ Uis just the set of measurable functions θ∶Ω→½0;1with integral less or equal than κ. To make our results precise, we first consider the discretization of the set of controls but not of the state equation (1.3). In the context of finite-element approximation methods, we can consider a decomposition of Ωin elements with maximum size rand subsets ωconstituted by unions of a subset of such elements. If we denote by Urthe set of such subsets, the discrete problem reads Find ωr 0∈Ursuch that Jðωr 0Þ¼min ω∈UrJðωÞ: ð1:8Þ The discrete space of controls obtained in this way Uris compact in the strong topology of L1ðΩÞ, and the corresponding state functions are compact in H1ðΩÞ. Therefore, the discretized problem has a solution without the need for a relaxed version. In this way we obtain a sequence of discrete minimizers fωr 0grthat are likely to constitute a minimizing sequence of Jin U,asr→0. We show that this is the case, and we give convergence rates for Jðωr 0Þ−inf ω∈U JðωÞas r→0:ð1:9Þ On the other hand, instead of discretizing the original control problem, we can discretize the relaxed version. After introducing a decomposition of Ωin elements, with maximal size r, we can consider the set ^ Urof functions θ∈^ Uwhich are constant on each element. The discrete relaxed problem reads Find ^ θr 0∈^ Ursuch that ^ Jð^ θr 0Þ¼min θ∈^ Ur ^ JðθÞ. ð1:10Þ APPROXIMATION OF AN OPTIMAL DESIGN PROBLEM 1183 Copyright ©by SIAM. Unauthorized reproduction of this article is prohibited. As above, we show that ^ Jð^ θr 0Þ−inf ω∈^ U∇ JðuÞ→0asr→0;ð1:11Þ and we give convergence rates. Once a discrete relaxed minimizer is known ^ θr 0we can construct a sequence fωk;rg∞ k¼1⊂Usuch that lim k→∞ Jðωk;rÞ¼ ^ Jð^ θr 0Þ: This provides a minimizing sequence of the original problem. As we show, the sequence fωk;rg∞ k¼1can be constructed explicitly from ^ θr 0with almost no computational cost. Our results show that it is better to discretize the relaxed problem, in the sense that we get a faster convergence rate, as r→0, for (1.11) than the one obtained for (1.9). This is true even in the case where the original problem has a solution, and so the relaxation is unnecessary from a theoretical point of view. Despite this, the relaxed version of the original minimization problem can always be formulated, and our results show that it is indeed better to approximate the optimal design problem numerically in these cases as well. From a computational point of view, besides discretizing the set of controls, we must also discretize the state equation (1.3) or (1.6). This requires a second decomposition of Ωconstituted by elements of maximum size h. A natural assumption is to consider this new decomposition as a refinement of the one used for the control set, or vice versa. In the context of the original unrelaxed control problem, denoting by uhthe P1-finite-element approximation of the solution of (1.3), and defining Jhas JhðωÞ¼Zω F1ðx; uh;∇uhÞdxþZΩ\ω F2ðx; uh;∇uhÞdx; the full discrete control problem reads Find ωr;h 0∈Ursuch that Jhðωr;h 0Þ¼min ω∈UrJhðωÞ: ð1:12Þ Analogously, we can define a full discretization of the relaxed problem by considering ^ JhðθÞ¼ZΩ Hðx; uh;∇uh;A∇uh;θÞdx;ð1:13Þ where uhis the P1-finite-element approximation of (1.6). The fully discrete relaxed problem in this case is Find ^ θr;h 0∈^ Ursuch that ^ Jhð^ θr;h 0Þ¼min θ∈^ Ur ^ JhðθÞ: ð1:14Þ We focus on the convergence rates for the sequences fωr;h 0gr;h and f^ θr;h 0gr;h obtained with the two approaches above, respectively. More precisely, we compare the sequences 1184 CASADO-DÍAZ, CASTRO, LUNA-LAYNEZ, ZUAZUA Copyright ©by SIAM. Unauthorized reproduction of this article is prohibited. Jðωr;h 0Þ−inf ω∈U JðωÞand ^ Jð^ θr;h 0Þ−inf ω∈U JðωÞ; as r; h →0. The following results are proven: •Discretizing the relaxed formulation, we show that, solving the state equation with the P1-finite-element method in a mesh of size hand taking the control θto be piecewise constant on elements of a coarser mesh of size ffiffiffi h p, the error is of order h. This constitutes a bigrid or multiscale strategy, implemented on the relaxed version, in the sense that the discretization of the PDE and that of the control are performed on two different grids. The PDE is discretized in the fine grid of size h, while the control is discretized in the coarse one of size ffiffiffi h p. •Discretizing the original unrelaxed problem, solving the state equation with a P1-finite-element method in a mesh of size h, and taking the control χωpiecewise constant in the elements of such mesh, we show that the error is of order h1−εwith εarbitrarily small if the functions Fiin (1.2) do not depend on the variable uand ε¼1∕2otherwise. A bigrid strategy consisting in discretizing the PDE in the coarser grid (instead of the finer one) can produce lack of convergence for both the unrelaxed and relaxed problems. In particular, the minimizers for the discrete problem will possibly give a nonminimizing sequence of the continuous control problem, as r; h →0. We also give an explicit example in which the functional is independent of u, showing our estimates are nearly sharp. To be more precise, our example shows the optimality of the estimates in the case in which the relaxed version of the problem is discretized, while an order hof convergence is obtained when the original problem is discretized, thus showing that our estimates are nearly optimal. Therefore the approach based on the discretization of the relaxed formulation provides a better approximation and a faster convergence rate with a lower computational cost. The computational cost and the complexity of this approach is lower since the controls are discretized in a mesh or order ffiffiffi h pinstead of h. Furthermore, the minimizers for the corresponding discrete optimization problems are easier to find numerically. Indeed, thanks to the convexity of the relaxed control set, gradient-like algorithms can be implemented. This is in contrast to the unrelaxed problem, where the control set is not convex and we cannot compute variations. Instead, much less efficient methods such as Monte Carlo or genetic algorithms should be used. On the contrary, the advantages of discretizing the original problem directly are that, on one hand, one does not need to know the relaxed formulation and, on the other hand, it provides a physical control (i.e., a characteristic function) instead of a relaxed one. However, this latter drawback can be overcome by approximating the relaxed controls by physical ones, with almost no computational cost. This paper provides a complete analysis of the rate of convergence of the finiteelement approximation of the optimal design problem under consideration. Whether this classical engineering practice leads to convergent algorithms is unknown in many other optimal design problems, except in some other particular examples as it occurs when dealing with the optimal shape design of the domain for Dirichlet Laplacian in two space dimensions (see [10]). Note, however, that, in the later, there is no result about the convergence rate. Although the present article is devoted to the study of the 1−doptimal design problem, some remarks about the N-dimensional case are given in the last section of the paper. As above these remarks are devoted to the case of diffusion coefficients that APPROXIMATION OF AN OPTIMAL DESIGN PROBLEM 1185 Copyright ©by SIAM. Unauthorized reproduction of this article is prohibited. are uniformly elliptic and bounded; the case where we consider matrix diffusions such that their smaller and/or larger eigenvalues can approximate to zero or infinity, respectively, is more involved. Indeed, even the definition of solution of the state equation is not clear in this case, where in particular Lavrentiev’s phenomenon can occur; i.e., smooth functions cannot be dense in the space of functions with bounded energy (see, e.g., [25] and the references therein). In this sense, we remark that in order to prove the convergence of the finite-element method, it is necessary to have the density of the Lipschitz functions in the space where we are looking for the solution of the state equation. A reciprocate of this result has been obtained in [5] for a calculus of variations problem without restrictions. As we have already remarked, control problem (1.1) does not have a solution in general. To have a well-posed problem, such as we do in the present paper, an approach consists of obtaining a relaxation of (1.1) by using homogenization techniques. However, there exist other approaches, for instance, the filtering technique. Loosely speaking, the idea of the filtering technique consists of replacing the set of controls in (1.1) with a smoother class, defined by mean of a convolution operator. More precisely, in (1.3) the characteristic functions χω, with ω∈U, are replaced by the smooth functions ρRθ, with θ∈L∞ðΩ;½0;1Þ satisfying the volume restriction, where ρRis the typical mollifier function ρRðxÞ¼ρðx∕RÞ∕RNwith ρa fixed C∞nonnegative function with support in the ball of center 0 and radius 1, and integral equals 1. Thus, we obtain a new problem (filtered problem) with a compact set of controls in C∞ð¯ ΩÞ, which guarantees the existence of a solution when the cost functional Jis sequentially lower continuous in the weak topology of H1ðΩÞ. The filtered problems are then smooth approximations of (1.1) when R>0is small, at least formally. Given Rfixed, the finite-element approximation of the filtered problem has been studied in [4], in the framework of a control problem in the coefficients in elasticity—namely the compliance problem. In [4], the convergence of the finite-element approximation, as the mesh size tends to zero, is proved but without explicit rates. Some definitions and notations: •For a number r∈R, we denote by ½rthe integer part of r. •For a (Lebesgue) measurable subset Eof ð0;1Þ, with positive measure, and a function win L1ð0;1Þ, we denote the mean value of win Eby ⨍E wdx¼1 jEjZE wdx: •The set of functions of bounded variation in ð0;1Þis denoted by BVð0;1Þ.Ifψis in BVð0;1Þand Iis a subinterval of ½0;1, then VIðψÞrepresents the total variation of ψin I. •Throughout the paper, αand βare two positive constants. •For p∈½0;1, we denote by MðpÞ∈Rthe harmonic mean of αand βwith proportions pand 1−p, respectively, given by MðpÞ¼p αþ1−p β−1 ¼αβ ð1−pÞαþpβ: Note that Mð1Þ¼α,Mð0Þ¼β, and α≤MðpÞ≤β∀p∈½0;1:ð1:15Þ 1186 CASADO-DÍAZ, CASTRO, LUNA-LAYNEZ, ZUAZUA Copyright ©by SIAM. Unauthorized reproduction of this article is prohibited. For every θ∈L∞ð0;1; ½0;1Þ we define Mθ∈L∞ðΩÞby MθðxÞ¼MðθðxÞÞ for a:e:x∈ð0;1Þ: •For a matrix A∈RN×N, we denote by EigðAÞthe set of its eigenvalues. •Let Φbe a function defined in the interval ð0;δÞfor some δ>0. The equality Φ¼oðhÞ(Landau symbol) means lim h→0 ΦðhÞ h¼0: •We denote by Ca generic positive constant that can change from line to line. 2. Discretization and error estimates. 2.1. The main results. In this section we state the main results of the paper. They are referred to the numerical analysis of a control problem for the 1−delliptic state equation in Ω¼ð0;1Þbelow, the control being the space-dependent coefficient (−d dx ðαχωþβð1−χωÞÞdu dx¼finð0;1Þ; uð0Þ¼uð1Þ¼0; ð2:1Þ where αand βare two fixed positive constants and fa given function in (at least) L1ð0;1Þ. Defining, for a fixed constant κ>0, the set of admissible controls as (1.4), our aim is to choose ω∈Usuch that the unique solution uω∈H1 0ð0;1Þof problem (2.1) minimizes the functional J∶UR !defined as the 1−dversion of (1.2); i.e., JðωÞ¼Zω F1x; uω;duω dx dxþZð0;1Þ\ω F2x; uω;duω dx dx∀ω∈U:ð2:2Þ Here F1;F2∶ð0;1Þ×R×R→Rsatisfy Fi∈W1;∞ðð0;1Þ×ð−R; RÞ×ð−R; RÞÞ ∀i∈f1;2g∀R>0:ð2:3Þ As we said in the introduction, αand βrepresent two materials that we want to mix in order to minimize J. The constant κis the maximum quantity of material αthat can be used in the mixture. Note that taking κ≥1would be equivalent to not imposing any restriction in the set of admissible sets ω. Remark 1. In (2.1), we consider homogeneous Dirichlet conditions to fix ideas, but our results also hold for nonhomogeneous Dirichlet conditions or other boundary conditions, such as Fourier or Neumann ones. We can also consider the functions Fi satisfying weaker assumptions than (2.3), but then the error estimates we find for the numerical approximations defined below are worse. It is well known that the original minimization problem (1.1) does not have a solution in general (see [15], [16]). Therefore, it is necessary to introduce a relaxation. However, as we have mentioned in the introduction, for numerical purposes it is often convenient to work in the relaxed version of the problem even when the original formulation has a minimizer. The relaxed version thus plays a key role in the numerical analysis we develop in this article. The following result provides a characterization of the relaxation. APPROXIMATION OF AN OPTIMAL DESIGN PROBLEM 1187 Copyright ©by SIAM. Unauthorized reproduction of this article is prohibited. THEOREM 2.1. A relaxation of problem (1.1) is given by Find θ0∈^ Usuch that ^ Jðθ0Þ¼min θ∈^ U ^ JðθÞ; ð2:4Þ where ^ U¼θ∈L∞ð0;1; ½0;1Þ∶Z1 0 θdx≤κ;ð2:5Þ and ^ J∶^ U→Ris defined by ^ JðθÞ¼Z1 0θF1x; uθ;Mθ α duθ dx þð1−θÞF2x; uθ;Mθ β duθ dx dxð2:6Þ for every θ∈^ Uwith u¼uθthe solution of (−d dx Mθdu dx¼fin ð0;1Þ; uð0Þ¼uð1Þ¼0: ð2:7Þ Remark 2. Theorem 2.1 also holds true for every f∈H−1ð0;1Þand more general nonlinearities F1,F2. Indeed, it is enough to assume that F1,F2are two Carathéodory functions (measurable with respect to xand continuous with respect to ðs; ξÞ) such that for every R>0, the functions φ1;R,φ2;R defined as φi;RðxÞ¼ sup jsjþjξj≤RjFiðx; s; ξÞj for a:e:x∈ð0;1Þ∀i∈f1;2g belong to L1ð0;1Þ. Remark 3. For every ω⊂ð0;1Þmeasurable, we have JðωÞ¼ ^ JðχωÞ: Therefore, ^ Jis in fact an extension of the functional χω↦JðωÞdefined on the space L∞ð0;1; f0;1gÞ to the relaxed control set L∞ð0;1; ½0;1Þ. Remark 4. Theorem 2.1 is a generalization of Proposition 4.1 and Theorem 4.3 in [6], where the multidimensional case is also considered. In the present paper, we are interested mainly in the numerical analysis of problem (1.1). For this purpose, thanks to Theorem 2.1, two choices are possible: to discretize directly problem (1.1) or to discretize the relaxed problem (2.4). Our goal is to compare these two possibilities. To this aim, given r>0, we take a partition Pr¼fykgmr k¼0of ½0;1, with mr∈N, such that r¼max 1≤k≤mrðyk−yk−1Þ:ð2:8Þ Then, we define ^ Urand Uras the subsets of ^ Ugiven by ^ Ur¼θ∈^ U∶θ¼X mr k¼1 tkχðyk−1;ykÞa:e:inð0;1Þwith tk∈½0;1;1≤k≤mr;ð2:9Þ 1188 CASADO-DÍAZ, CASTRO, LUNA-LAYNEZ, ZUAZUA Copyright ©by SIAM. Unauthorized reproduction of this article is prohibited. Ur¼fω⊂ð0;1Þ∶χω∈^ Urg:ð2:10Þ Associated to these subsets we can consider the two discretizations of the control problem given by (1.10) and (1.8). Note that problem (1.8) is a discretization of the original minimization problem (1.1), while (1.10) is a discretization of the relaxed problem (2.4). The following theorems provide estimates on the difference between these problems and (2.4). Some versions of Theorem 2.2 can also be obtained in the N-dimensional case; see section 8. THEOREM 2.2. Assuming f∈L1ð0;1Þ, problem (1.10) has a solution for every r>0, and we have 0≤min θ∈^ Ur ^ JðθÞ−min θ∈^ U ^ JðθÞ¼oðrÞ:ð2:11Þ Moreover, if f∈L∞ð0;1Þand problem (2.4) has a solution θ0in BVð0;1Þ, then 0≤min θ∈^ Ur ^ JðθÞ−min θ∈^ U ^ JðθÞ≤Cr2:ð2:12Þ THEOREM 2.3. Assuming f∈L1ð0;1Þ, problem (1.8) has a solution for every r>0, and we have 0≤min ω∈UrJðωÞ−inf ω∈U JðωÞ≤Cr1 2:ð2:13Þ Moreover, if for some integer l≥1, we have that fbelongs to the space Wl;1ð0;1Þand F1ðx; s; ξÞ,F2ðx; s; ξÞare independent of sand belong to Cl;1 locð½0;1×RÞ; then we have 0≤min ω∈UrJðωÞ−inf ω∈U JðωÞ≤Crlþ1 lþ2:ð2:14Þ 2.2. Optimality. We now give an example showing that the previous results are nearly optimal. Example 1. We consider problem (1.1) with α<β,f¼1,κ¼2∕3, and Jgiven by JðωÞ¼−αZω duω dx  2 dx−βZð0;1Þ\ω duω dx  2 dx:ð2:15Þ For every n∈N, we define Pnas the partition of ½0;1given by Pn¼fk10−n∶0≤k≤10ng: We define ^ Un¼θ∈^ U∶θ¼X 10n k¼1 rkχððk−1Þ10−n;k10−nÞwith rk∈½0;1∀k∈f1; :::;10ng;ð2:16Þ Un¼fω∈U∶χω∈^ Ung:ð2:17Þ We will prove in section 6 the following result. APPROXIMATION OF AN OPTIMAL DESIGN PROBLEM 1189 Copyright ©by SIAM. Unauthorized reproduction of this article is prohibited. Remark 7. In Example 3 we are discretizing the state equation (2.1) or (2.7) using a partition of ½0;1of size hbigger than the size r¼h∕2employed in discretizing the set of controls. Statement (2.38) shows that in this case the minimum of the discretized problem does not tend to the infimum of (1.1). Thus, this type of discretization is not convergent in general. 3. Proof of the relaxation result. This section is devoted to proving Theorem 2.1, which characterizes the relaxation of problem (1.1). To do it, we use the following lemma. LEMMA 3.1. The functional ^ J∶^ U⊂L∞ð0;1Þ→Ris sequentially continuous for the -weak topology of L∞ð0;1Þ. Proof. Given a sequence θn∈^ Uwhich converges weakly-in L∞ð0;1Þto a function θ∈^ U, we have to see that ^ JðθnÞconverges to ^ JðθÞ. For a such sequence θn, we observe that the corresponding solution uθnof (2.7) is given by uθnðxÞ¼−Zx 0 FðtÞ−cn Mθn dt¼−Zx 0ðFðtÞ−cnÞαð1−θnðtÞÞþβθnðtÞ αβ dt with Fa primitive of fin ð0;1Þand cn¼Z1 0 dt MθnðtÞ−1Z1 0 FðtÞ MθnðtÞdt: Therefore, it is immediate to show that kuθnkW1;∞ð0;1Þ≤C; uθn→uθin C0ð½0;1Þ;M θn dun dx −Mθ duθ dx →0inC0ð½0;1Þ with uθthe unique solution of (2.7). Then, by (2.3) we obtain lim n→∞ ^ JðθnÞ ¼limn→∞Z1 0θnF1x; uθn;Mθn α duθn dx þð1−θnÞF2x; uθn;Mθn β duθn dx dx ¼Z1 0θF1x; uθ;Mθ α duθ dx þð1−θÞF2x; uθ;Mθ β duθ dx dx¼^ JðθÞ:▯ Proof of Theorem 2.1. Taking into account that the space of controls ^ Ugiven by (2.5) is sequentially compact in the -weak topology of L∞ð0;1Þ, from Lemma 3.1 we deduce that problem (2.4) has at least a solution. On the other hand, by Remark 3 it is clear that inf ω∈U JðωÞ¼ inf χω∈^ U ^ JðχωÞ≥min θ∈^ U ^ JðθÞ: Therefore, in order to check that problem (2.4) is a relaxation of (1.1), it is enough to prove that for every θ∈^ U, there exists a sequence ωnin Usuch that 1196 CASADO-DÍAZ, CASTRO, LUNA-LAYNEZ, ZUAZUA Copyright ©by SIAM. Unauthorized reproduction of this article is prohibited. χωn⇀ θin L∞ð0;1Þ;ð3:1Þ JðωnÞ→^ JðθÞ:ð3:2Þ The existence of this sequence ωnis well known (for example, it is a consequence of Lemma 5.1 below), while by the continuity property of ^ Jproved in step 1, (3.2) is a consequence of (3.1). So, the proof of Theorem 2.1 is complete. ▯ 4. Proof of the convergence estimates for the discretized relaxed control problem. In this section we prove Theorem 2.2 referred to the convergence of the discretization of problem (2.4) given by (1.10). Note that we are discretizing the controls but not the state equation. We also give the proof of Proposition 2.5, which permits us to obtain a physical control from a relaxed one. Along this section, we consider a partition Pr¼fykgmr k¼0, with mr∈N, satisfying (2.8). The space ^ Uris defined by (2.9). In order to show Theorem 2.2, we will use the operator Πrdefined by the following. DEFINITION 4.1. We define the projection operator Πr∶L1ð0;1Þ→^ Urby Πrψ¼X mr k¼1⨍yk yk−1 ψdsχðyk−1;ykÞ∀ψ∈L1ð0;1Þ:ð4:1Þ The following lemma estimates the difference Πrθ−θwhen rtends to zero. LEMMA 4.2. Let θbe in L∞ð0;1; ½0;1Þ. Then, for every φ∈W1;1ð0;1Þ, it holds that Z1 0ðθ−ΠrθÞφdx¼oðrÞ;ð4:2Þ Z1 0Zx 0ðθðtÞ−ΠrθðtÞÞφðtÞdt dx¼oðrÞ:ð4:3Þ Moreover, if θis in BVð0;1Þ, and φis in W1;∞ð0;1Þ, we have the following improvement of the previous estimates: Z1 0ðθ−ΠrθÞφdx ≤C    dφ dx   L∞ð0;1Þ r2;ð4:4Þ Z1 0Zx 0ðθðtÞ−ΠrθðtÞÞφðtÞdt dx≤CkφkW1;∞ð0;1Þr2:ð4:5Þ Proof. We take φ∈W1;1ð0;1Þ; for a given x∈½0;1, we consider yjdefined by yj¼supfyk∶yk≤x; 0≤k≤mrg: Then, using the inequality  φðtÞ−⨍yk yk−1 φds ≤    dφ dt    L1ðyk−1;ykÞ ∀t∈½yk−1;y k we have APPROXIMATION OF AN OPTIMAL DESIGN PROBLEM 1197 Copyright ©by SIAM. Unauthorized reproduction of this article is prohibited. Zx 0ðθ−ΠrθÞφdt ¼X j k¼1Zyk yk−1θ−⨍yk yk−1 θdsφdtþZx yjθ−⨍yk yk−1 θdsφdt ¼X j k¼1Zyk yk−1ðθ−⨍yk yk−1 θdsÞðφ−⨍yk yk−1 φdsÞdt þZx yjθ−⨍yk yk−1 θdsφdt ≤X j k¼1    dφ dx   L1ðyk−1;ykÞkθ−ΠrθkL1ðyk−1;ykÞþkφkL∞ð0;1Þkθ−ΠrθkL1ðyj;xÞ:ð4:6Þ Integrating this inequality in ð0;1Þ,weget Z1 0Zx 0ðθðtÞ−ΠrθðtÞÞφðtÞdt dx ≤X mr k¼1    dφ dx   L1ðyk−1;ykÞkθ−ΠrθkL1ðyk−1;ykÞ þkφkL∞ð0;1ÞX mr−1 j¼0Zyjþ1 yjkθ−ΠrθkL1ðyj;xÞdx ≤X mr k¼1    dφ dx   L1ðyk−1;ykÞkθ−ΠrθkL1ðyk−1;ykÞþkφkL∞ð0;1Þkθ−ΠrθkL1ð0;1Þr:ð4:7Þ If φbelongs to W1;∞ð0;1Þand θbelongs to BVð0;1Þ, using in (4.7)     dφ dx   L1ðyk−1;ykÞ ≤    dφ dx   L∞ð0;1Þ r; kθ−ΠrθkL1ð0;1Þ≤Vð0;1ÞðθÞr;ð4:8Þ we deduce (4.5). Inequality (4.4) is a consequence of (4.6) with x¼1¼yjand (4.8). In order to show (4.2) and (4.3) we now take a sequence φnin W1;∞ð0;1Þwhich converges to φin W1;1ð0;1Þand a sequence θnin BVð0;1Þ, with 0≤θn≤1in ð0;1Þ, which converges to θin L1ð0;1Þ. Then, we estimate the right-hand side of (4.7) as follows: X mr k¼1    dφ dx   L1ðyk−1;ykÞkθ−ΠrθkL1ðyk−1;ykÞþkφkL∞ð0;1Þkθ−ΠrθkL1ð0;1Þr ≤2    dðφ−φnÞ dx    L1ð0;1Þ rþkφkL∞ð0;1Þkθ−θn−Πrðθ−θnÞkL1ð0;1Þr þX mr k¼1    dφn dx    L1ðyk−1;ykÞkθ−ΠrθkL1ðyk−1;ykÞþkφkL∞ð0;1Þkθn−ΠrθnkL1ð0;1Þr ≤2    dðφ−φnÞ dx    L1ð0;1Þ rþkφkL∞ð0;1Þkθ−θn−Πrðθ−θnÞkL1ð0;1Þr þ    dφn dx    L∞ð0;1Þ Vð0;1ÞðθÞþkφkL∞ð0;1ÞVð0;1ÞðθnÞr2: 1198 CASADO-DÍAZ, CASTRO, LUNA-LAYNEZ, ZUAZUA Copyright ©by SIAM. Unauthorized reproduction of this article is prohibited. Dividing this inequality by rand passing to the limit first when rtends to zero and then when ntends to infinity, we deduce (4.3). The proof of (4.2) can be obtained reasoning in a similar way with (4.6). ▯ For θ∈L∞ð0;1; ½0;1Þ, the following lemma estimates the difference between the solution of (2.7) and the solution of the analogous problem when θis replaced by Πrθ. LEMMA 4.3. Assume f∈L1ð0;1Þ. For θ∈L∞ð0;1; ½0;1Þ, we consider θr¼Πrθ. Then, the solutions uθand uθrof (2.7) for θand θr, respectively, satisfy kuθ−uθrkL1ð0;1Þ≤oðrÞ;ð4:9Þ     Mθ duθ dx −Mθr duθr dx    L∞ð0;1Þ ≤oðrÞ:ð4:10Þ If fis in L∞ð0;1Þand θis in BVð0;1Þ, then in (4.9) and (4.10) we can take oðrÞ¼CVð0;1ÞðθÞr2: Proof. The functions uθand uθrare given by uθðxÞ¼−Zx 0 g Mθ dsþcZx 0 1 Mθ dsfor a:e:x∈ð0;1Þ;ð4:11Þ uθrðxÞ¼−Zx 0 g Mθr dsþcrZx 0 1 Mθr dsfor a:e:x∈ð0;1Þð4:12Þ with ga primitive of fand c; cr∈Rdefined by c¼Z1 0 1 Mθ dx−1Z1 0 g Mθ dx; cr¼Z1 0 1 Mθr dx−1Z1 0 g Mθr dx:ð4:13Þ Using these expressions and taking into account that minfα;βg≤Mθ;Mθr≤maxfα;βg; we easily deduce kuθ−uθrkL1ð0;1Þ≤CZ1 0ðθ−θrÞgdxþZ1 0ðθ−θrÞdx : þZ1 0Zx 0ðθðtÞ−θrðtÞÞgðtÞdt dxþZ1 0Zx 0ðθðtÞ−θrðtÞÞdt dx and     Mθ duθ dx −Mθr duθr dx    L∞ð0;1Þ ≤CZ1 0ðθ−θrÞgdxþZ1 0ðθ−θrÞdx: Lemma 4.3 is then a simple consequence of Lemma 4.2. ▯ We are now in position to prove the following. Proof of Theorem 2.2. The existence of solution for problem (1.10) is a simple consequence of the compactness of (2.9) in L1ð0;1Þ. On the other hand, using that F1and F2are locally Lipschitz, and that the functions uθ,uθrdefined as in Lemma 4.2 are bounded in W1;∞ð0;1Þindependently of r, we have APPROXIMATION OF AN OPTIMAL DESIGN PROBLEM 1199 Copyright ©by SIAM. Unauthorized reproduction of this article is prohibited. j^ JðθÞ−^ JðθrÞj ≤Z1 0 F1x; uθ;Mθ α duθ dx ðθ−θrÞdxþZ1 0 F2x; uθ;Mθ α duθ dx ðθ−θrÞdx þCZ1 0juθ−uθrjþMθ duθ dx −Mθr duθr dx dx: Thanks to Lemma 4.3, we then deduce (2.11) and (2.12). ▯ To finish this section, we now give the proof of Proposition 2.5. Proof of Proposition 2.5. Reasoning as in the proof of Theorem 2.2, we have that the result is an immediate consequence of the following lemma, which is similar to Lemma 4.2. ▯ LEMMA 4.4. Assume θand ωas in the statement of Proposition 2.5; then for every φ∈W1;∞ð0;1Þ, it holds that Z1 0ðθ−χωÞφdx ≤    dφ dx   L∞ð0;1Þ r2;ð4:14Þ Z1 0Zx 0ðθðtÞ−χωðtÞÞφðtÞdt dx≤kφkW1;∞ð0;1Þr2:ð4:15Þ Proof. Since in each interval ½yk−1þði−1Þsk;y kþisk, with 1≤k≤mr, 1≤i≤jk, the functions θand χωhave the same integral, we can reason as in the proof of (4.6) to deduce that for every x∈½0;1, we have Zx 0ðθ−χωÞφdt ≤    dφ dx   L∞ð0;1Þkθ−χωkL1ð0;1Þr2þkφkL∞ð0;1Þkθ−χωkL1ðIÞr;ð4:16Þ where Iis an interval of the form ½yk−1þði−1Þsk;y kþiskcontaining x. Taking x¼1 we get (4.14). On the other hand, since θand χωbelong to L∞ð0;1; ½0;1Þ, inequality (4.16) implies Zx 0ðθ−χωÞφdt ≤r2kφkW1;∞ð0;1Þ for every x∈½0;1. This inequality immediately proves (4.15). ▯ 5. Proof of the convergence estimates for the discretized unrelaxed control problem. Let us now prove Theorem 2.3. As for Theorem 2.2, we will need some preliminary lemmas. LEMMA 5.1. We consider θ∈L∞ð0;1Þand l∈N; then, there exists ω⊂ð0;1Þmeasurable such that Z1 0 tjθðtÞdt¼Zω tjdt∀j∈f0; :::;lg:ð5:1Þ Moreover ωcan be chosen in the following way: 1200 CASADO-DÍAZ, CASTRO, LUNA-LAYNEZ, ZUAZUA Copyright ©by SIAM. Unauthorized reproduction of this article is prohibited. If l¼2n, with n∈N, ω¼ð0;b 0Þ[[ m i¼1ðai;b iÞ; where m≤nand 0≤b0<a1<b1<···<am<bm≤1. If l¼2nþ1, with n∈N, ω¼[ m i¼1ðai;b iÞ; where m≤nþ1and 0≤a1<b1<···<am<bm≤1. Proof. Let us prove the result in the case l¼2nþ1, the other one being similar. We define D⊂L1ð0;1Þas D¼ϕ¼X m i¼1 χðai;biÞwith m≤nþ1;0≤a1<b1<···<am<bm≤1 and Ψ∶D→Rby ΨðϕÞ¼X 2nþ1 j¼0Z1 0 tjðθðtÞ−ϕðtÞÞdt2 ∀ϕ∈D: Since Dis compact in L1ð0;1Þand Ψis continuous, we know that Ψattains its minimum in some function ϕ¼X m i¼1 χðai;biÞ∈D: Then, we define the polynomial Pas PðλÞ¼X 2nþ1 j¼0Z1 0 tjðθðtÞ−ϕðtÞÞdtλj. We fix k, with 1≤k≤m. For ε∈R, with jεjsmall (εmust also be positive if k¼1, a1¼0), the function ϕε¼χ∪i≠kðai;biÞþχðakþε;bkÞ belongs to D. Taking into account that ΨðϕεÞ¼X 2nþ1 j¼0Z1 0 tjðθðtÞ−ϕðtÞÞdtþZakþε ak tjdt2 ; and that ϕis a minimum point of Ψ, the derivative of ΨðϕεÞwith respect to εyields PðakÞ¼0ifak≠0;Pða1Þ≥0ifa1¼0: Analogously, we can prove APPROXIMATION OF AN OPTIMAL DESIGN PROBLEM 1201 Copyright ©by SIAM. Unauthorized reproduction of this article is prohibited. PðbkÞ¼0ifbk≠1;PðbmÞ≥0ifbm¼1: If Phas 2nþ2zeros, then it is the zero polynomial and we obtain the conclusion of the lemma. So, we assume in the following that Phas at most 2nþ1zeros. By the above proved we deduce that m¼nþ1;a 1¼0;and∕or bnþ1¼1; or m<nþ1: Let us prove that in all these cases Psatisfies PðλÞ≥0in [ m i¼1ðai;b iÞ;PðλÞ≤0inð0;1Þ\[ m i¼1ðai;b iÞ.ð5:2Þ (i) Case m¼nþ1,a1¼0,bnþ1¼1. Since we are supposing that the number of zeros of Pis strictly less than 2nþ2and Pvanishes in the 2npoints akwith k¼2; :::;nþ1,bkwith k¼1; :::;n, we have that Phas 2nor 2nþ1zeros in ½0;1. If the number of zeros is 2nþ1, then using that Pð0Þ;Pð1Þ≥0,we deduce that the other zero of Pis in 0 or 1 and that Psatisfies (5.2). If the number of zeros is 2n, then we have Pð0Þ;Pð1Þ>0and (5.2) is satisfied. (ii) Case m¼nþ1,a1¼0,bnþ1<1. In this case we have that the 2nþ1zeros of Pare given by the points akwith k¼2; :::;nþ1,bkwith k¼1; :::;nþ1. Since Pð0Þ≥0, we deduce (5.2). (iii) Case m¼nþ1,a1>0,bnþ1¼1. It is similar to the case (ii). (iv) Case m<nþ1. In this case, we take a point c∈ðai;b iÞfor some i∈f1; :::mg. Then for ε>0, small enough, the function ϕε¼ϕ−χðc−ε;cþεÞ belongs to D. Using that ΨðϕεÞ¼X 2nþ1 j¼0Z1 0 tjðθðtÞ−ϕðtÞÞdtþZcþε c−ε tjdt2 ; and deriving with respect to ε, we deduce that PðcÞ≥0∀c∈[ m i¼1ðai;b iÞ: Analogously, if c∈ð0;1Þ\Sm i¼1½ai;b i, taking ϕε¼ϕþχðc−ε;cþεÞ; we deduce that 1202 CASADO-DÍAZ, CASTRO, LUNA-LAYNEZ, ZUAZUA Copyright ©by SIAM. Unauthorized reproduction of this article is prohibited. PðcÞ≤0∀c∈ð0;1Þ\[ m i¼1½ai;b i: Thus, (5.2) is also proven in this case. To finish, let us prove that (5.2) implies the conclusion of the lemma. For this purpose, we just write X 2nþ1 j¼0Z1 0 tjðθðtÞ−ϕðtÞÞdt2 ¼Z1 0X 2nþ1 j¼0Z1 0 tjðθðtÞ−ϕðtÞÞdtsjðθðsÞ−ϕðsÞÞds ¼Z1 0 PðsÞðθðsÞ−ϕðsÞÞds.ð5:3Þ If s∈Sm i¼1ðai;b iÞ(i.e., ϕðsÞ¼1), then by (5.2), PðsÞ≥0and since θðsÞ≤1, we have PðsÞθðsÞ≤PðsÞϕðsÞ: If s∈=Sm i¼1ðai;b iÞ(i.e., ϕðsÞ¼0), then by (5.2), PðsÞ≤0and since θðsÞ≥0, we also have PðsÞθðsÞ≤PðsÞϕðsÞ: Therefore the last integral in (5.3) is nonpositive, which proves X 2nþ1 j¼0Z1 0 tjðθðtÞ−ϕðtÞÞdt2 ¼0: This proves Lemma 5.1. ▯ As a consequence, we deduce the following. LEMMA 5.2. Let a,bbe in Rwith a<band let fykgm k¼0be a partition of ½a; bof size δ¼max 1≤k≤mðyk−yk−1Þ: Let also θbe in L∞ða; b;½0;1Þ. Then for every l∈N, there exists I⊂f1; :::;mgsuch that ~ ω¼[ k∈Iðyk−1;y kÞð5:4Þ satisfies j~ ωj≤Zb a θdx;ð5:5Þ Zb aðθ−χ~ ωÞφdx ≤Cðb−aÞlþ1kDlþ1φkL1ða;bÞþCδkφkL∞ða;bÞ∀φ∈Wlþ1;1ð0;1Þ; ð5:6Þ where Cis a positive constant that depends on l, but it is independent of θ,δ,a, and b. APPROXIMATION OF AN OPTIMAL DESIGN PROBLEM 1203 Copyright ©by SIAM. Unauthorized reproduction of this article is prohibited. Proof. It is enough to show the case a¼0,b¼1. The general one follows using a translation and a dilatation which transforms ða; bÞin ð0;1Þ. For a given l∈N, by Lemma 5.1 we know there exists ω⊂ð0;1Þsatisfying (5.1) and such that the number of discontinuity points of χωin ½0;1is at most lþ1. We then define I¼fk∈f1; :::;mg∶ðyk−1;y kÞ⊂ωg and ~ ωby (5.4). By the definition of ~ ω, we have ~ ω⊂ω, and then using (5.1) when j¼0, we obtain (5.5). Moreover, using that χωhas at most lþ1discontinuity points in ½0;1, we have jω\~ ωj≤ðlþ1Þδ:ð5:7Þ We now fix φ∈Wlþ1;1ð0;1Þ. Taking a polynomial pof degree lsuch that Z1 0jφ−pjdx≤CkDlþ1φkL1ð0;1Þ with Cindependent of φ(take, for example, the Taylor polynomial of degree lof φ∈ Wlþ1;1ð0;1Þ⊂Clð½0;1Þ in some point of ½0;1), we get Z1 0ðθ−χ~ ωÞφdx ≤Z1 0ðθ−χωÞðφ−pÞdxþZ1 0ðχω−χ~ ωÞφdx ≤CkDlþ1φkL1ð0;1Þþðlþ1ÞδkφkL∞ð0;1Þ:ð5:8Þ This proves (5.6) for a¼0,b¼1.▯ LEMMA 5.3. For r>0small we take a partition Pr¼fykgmr k¼0with mr∈Nsuch that (2.8) is satisfied. We define ^ Uby (2.5) and Urby (2.10). (a) For every θ∈^ U, there exists ω∈Ursuch that Zx 0ðθ−χωÞφds ≤Cr1 2kφkW1;1ð0;1Þ∀x∈½0;1;∀φ∈W1;1ð0;1Þ;ð5:9Þ where Cis a positive constant independent of θand r. (b) For every θ∈^ Uand every l∈N, there exists ω∈Ursuch that Z1 0ðθ−χωÞφds ≤Crlþ1 lþ2kφkWlþ1;1ð0;1Þ∀φ∈Wlþ1;1ð0;1Þ;ð5:10Þ where Cis a positive constant that depends on l, but it is independent of θand r. Proof. We take l∈N,γ∈ð2r; 1Þ, and a subpartition Pγ¼fzigmγ i¼0⊂Prof Pr which satisfies γ−r≤zi−zi−1≤γ∀i∈f1; :::;m γ−1g;r≤zmγ−zmγ−1≤γ: This implies in particular mγ≤1 γ−rþ1≤3 γ:ð5:11Þ 1204 CASADO-DÍAZ, CASTRO, LUNA-LAYNEZ, ZUAZUA Copyright ©by SIAM. Unauthorized reproduction of this article is prohibited. Using that for every i∈f1; :::;m γ−1gthe points ykwith zi−1≤yk≤ziare a partition of ½zi−1;z iwith mesh r, we can apply Lemma 5.2 in each interval ½zi−1;z ito construct a set ω∈Usuch that for every i∈f1; :::;m γ−1g, we have Zzi zi−1ðθ−χωÞφdx ≤Cðγlþ1kDlþ1φkL1ðzi−1;ziÞþkφkL∞ðzi−1;ziÞrÞð5:12Þ for every φ∈Wlþ1;1ð0;1Þ. For x∈½0;1, we take the larger jsuch that zj≤x; then, thanks to (5.12) and (5.11), we have Zx 0ðθ−χωÞφds¼Zzj 0ðθ−χωÞφdsþZx zjðθ−χωÞφds ≤Cγlþ1kDlþ1φkL1ð0;1ÞþkφkL∞ð0;1Þ3r γþðx−zjÞ:ð5:13Þ For l¼0, the above inequality and x−zj<γprove Zx 0ðθ−χωÞφds ≤CγkD1φkL1ð0;1ÞþCkφkL∞ð0;1Þr γþγ: Minimizing in γthis quantity, we deduce (5.9). On the other hand, for x¼1¼zjinequality (5.13) gives Z1 0ðθ−χωÞφds ≤Cγlþ1kDlþ1φkL1ð0;1ÞþCkφkL∞ð0;1Þ r γ; which minimizing in γproves (5.10). ▯ Using Lemma 5.3 and reasoning similarly to Lemma 4.3, we easily deduce the following. LEMMA 5.4. Let θbe in ^ Uand f∈L1ð0;1Þ. Then, for every r>0, there exists ω∈Ur such that, defining uθ,uras the solutions of (2.7) for θand χω, respectively, we have the following: (a) kuθ−urkL1ð0;1Þ≤Cð1þkfkL1ð0;1ÞÞr1 2:ð5:14Þ (b) If fbelongs to Wl;1ð0;1Þ, then     Mθ duθ dx −Mχω dur dx    L∞ð0;1Þ ≤Cð1þkfkWl;1ð0;1ÞÞrlþ1 lþ2:ð5:15Þ LEMMA 5.5. Let f∈L1ð0;1Þand θbe in ^ U; then for every r>0, there exists ω∈Ur such that j^ JðθÞ−JðωÞj ≤Cr1 2ð1þkfkL1ð0;1ÞÞ:ð5:16Þ If for some l∈Nwe have that fbelongs to Wl;1ð0;1Þ,F1ðx; s; ξÞ,F2ðx; s; ξÞare independent of sand belong to Cl;1 locð½0;1×RÞ; then APPROXIMATION OF AN OPTIMAL DESIGN PROBLEM 1205 Copyright ©by SIAM. Unauthorized reproduction of this article is prohibited. This permits us, for example, to substitute in the definition of the relaxed control set ^ U the set KðpÞby the (more simple) set of symmetric matrices whose eigenvalues are compressed between λðpÞand ΛðpÞ. Remark 9. Defining E¼fðξ;η;pÞ∈RN×RN×½0;1∶ðη−λðpÞξÞ·ðη−ΛðpÞξÞ≤0g; the function Hthat appears in (8.5) is a Carathéodory function with domain Ω×R×E. An explicit expression of Hin the whole of its domain is not known in general. In the particular case where F1ðx; s; ξÞ,F2ðx; s; ξÞare affine functions in the variable ξ, we have Hðx; s; ξ;η;pÞ¼pF1ðx; s; ξÞþð1−pÞF2ðx; s; ξÞ∀ðs; ξ;η;pÞ∈R×Ea:e:x∈Ω; while for nonlinear functions Fiin the variable ξ, an expression of His only known in some particular cases (which essentially are concerned with the nonlinear function jξj2); see [3], [6], [8], [11], and [18]. However, an explicit representation is always known in the boundary of its domain fðx; s; ξ;η;pÞ∶∈Ω×R×R×½0;1∶ðη−λðpÞξÞ·ðη−ΛðpÞξÞ¼0g; where Hðx; s; ξ;η;pÞis given by 8 > > < > > : F1ðx; s; ξÞif p¼1; F2ðx; s; ξÞif p¼0; pF1x; s; βξ−η pðβ−αÞþð1−pÞF2x; s; η−αξ ð1−pÞðβ−αÞif p≠0;1: ð8:7Þ Observe that the last line can be taken as the general expression for H, taking the values for p¼0and p¼1by continuity. Analogously as we did in the one-dimensional case, in order to numerically solve problem (8.5), for r>0we decompose Ωas Ω¼[ mr i¼1 Ki;K idisjoint;measurable;diamðKiÞ<r; i ∈f1; :::;m rg:ð8:8Þ Then, we discretize problem (8.5) as min ZΩ Hðx; u; ∇u; M∇u; θÞdx −div M∇u¼fin Ω;u¼0on∂Ω; ðθ;MÞ∈^ U;ðθ;MÞconstant in Ki;1≤i≤mr;RΩθdx≤κ: ð8:9Þ As we said in Remark 9 in the case where the functions Fiðx; s; ξÞare nonlinear in the variable ξ, one of the main difficulties to solve problem (8.9) is that His not known. To solve this difficulty we can replace Hwith another function. The following result is proved in [8] in the particular case F1ðx; s; ξÞ¼F2ðx; s; ξÞ¼FðξÞ. The general case follows similarly. 1212 CASADO-DÍAZ, CASTRO, LUNA-LAYNEZ, ZUAZUA Copyright ©by SIAM. Unauthorized reproduction of this article is prohibited. THEOREM 8.1. We consider a function ^ H∶Ω×R×E→R∪fþ∞gsuch that ^ Hð:; s; ξ;η;pÞis measurable in Ω∀ðs; ξ;η;pÞ∈R×E;ð8:10Þ ^ Hðx; :; :; :; :Þis lower semicontinuous in R×E for a:e: x ∈Ω;ð8:11Þ ^ Hðx; s; ξ;αξ;1Þ¼F1ðx; s; ξÞ;^ Hðx; s; ξ;βξ;0Þ¼F2ðx; s; ξÞ;ð8:12Þ ^ Hðx; s; ξ;η;pÞ≥Hðx; s; ξ;η;pÞ∀ðs; ξ;η;pÞ∈R×E a:e: x ∈Ω:ð8:13Þ For every r>0, we decompose Ωby (8.9). Then, the problem min ZΩ ^ Hðx; u; ∇u; M∇u; θÞdx −div M∇u¼fin Ω;u¼0on∂Ω; ðθ;MÞ∈^ U;ðθ;MÞconstant in Ki;1≤i≤mr;RΩθdx≤κ ð8:14Þ has a solution (not unique in general) ðθr;MrÞ. Taking uras the solution of −div Mr∇ur¼finΩ;u r¼0on ∂Ω; we have ∃lim r→0ZΩ ^ Hðx; ur;∇ur;Mr∇ur;θrÞdx¼I with Ithe minimum value of problem defined by (8.5). The sequence ðθr;Mr;u rÞis bounded in L∞ðΩÞ×L∞ðΩ;RN×NÞ×H1 0ðΩÞ. Every function ðθ;M;uÞ∈L∞ðΩÞ× L∞ðΩ;RN×NÞ×H1 0ðΩÞsuch that there exists a subsequence of r, still denoted by r, satisfying θr⇀ θin L∞ðΩÞ;M r⇀ MinL ∞ðΩ;RN×NÞ;u r⇀uinH 1 0ðΩÞ is such that the function ðθ;σ;uÞwith σ¼M∇uis a solution of (8.6). Remark 10. A first choice of function ^ His to take ^ Hðx; s; ξ;η;pÞ¼8 < : F1ðx; s; ξÞif p¼1;η¼αξ; F2ðx; s; ξÞif p¼0;η¼βξ; þ∞otherwise: In this case, taking into account that ^ Hðx; u; ∇u; M∇u; θÞ<þ∞a.e. in Ωimplies that θ is a characteristic function we get that problem (8.14) can be written as min Zω F1ðx; u; ∇uÞdxþZΩ\ω F2ðx; u; ∇uÞdx −divðαχωþβχΩ\ωÞ∇u¼fin Ω;u¼0on∂Ω; ∃I⊂f1; :::;m rgsuch that ω¼S i∈I Ki;jωj≤κ: Therefore, with this choice of function ^ H, Theorem 8.1 gives the convergence of the numerical method consisting in discretizing directly the original (unrelaxed) problem (8.1). APPROXIMATION OF AN OPTIMAL DESIGN PROBLEM 1213 Copyright ©by SIAM. Unauthorized reproduction of this article is prohibited. Thanks to (8.7), another possibility for ^ His to take ^ H¼Hin ∂DðHÞ, and ^ H¼þ∞, otherwise. For this choice of function ^ H, taking into account that for p≠0;1a matrix M∈KðpÞsatisfies ðMξ−λðpÞξÞ·ðMξ−ΛðpÞξÞ¼ξfor some ξ≠0 ⇔Mis a lamination of αI; βIwith proportions pand 1 −p ⇔EigðMÞ¼ðλðpÞ;ΛðpÞ; :::;ΛðpÞÞ: We can write problem (8.14) as min ZΩpF1x; u; β∇u−M∇u pðβ−αÞþð1−pÞF2x; u; M∇u−α∇u ð1−pÞðβ−αÞdx 8 < : −div M∇u¼fin Ω;u¼0on∂Ω; θ∈L∞ðΩ;½0;1Þ;Msymmetric;EigðMÞ¼ðλðθÞ;ΛðθÞ; :::;ΛðθÞÞa:e:in Ω; θ;Mconstants in Ki;i¼1; :::;m r;RΩθdx≤κ: In this case, problem (8.14) consists in discretizing a partial relaxation of problem (8.1) consisting in considering not only the original controls but also the ones obtained by a simple lamination. Clearly, when His known, another possibility is to take directly ^ H¼H. In this case we are discretizing the relaxed control problem (8.9). Remark 11. Although Theorem 8.1 gives the convergence of the discretized problem (8.14), it does not provide any error estimate. In particular, it does not show which choice of the functions ^ Hmentioned in Remark 10 is better. As we saw in the proof of the estimates for the one-dimensional problem, in order to obtain an estimate for the convergence rate of the numerical method, one idea is to construct from a relaxed control ðθ;MÞanother control ðθr;MrÞin the set of discretized controls such that the solutions of the state equations relative to ðθ;MÞand ðθr;MrÞare close. In the case where ^ H¼H(which can only be used if His known), one idea is to take ðθr;MrÞas the mean value of ðθ;MÞin each element of the triangulation. Denoting by uand urthe solutions of −div M∇u¼fin Ω; u¼0on∂Ω;−div Mr∇ur¼fin Ω; u¼0on∂Ω with fin H−1ðΩÞand taking into account that −div Mr∇ðu−urÞ¼−div ðMr−MÞ∇uin Ω; we deduce that ZΩj∇ðu−urÞj2dx≤CZΩjðMr−MÞ∇uj2dx; which permits to estimate the difference of u−urdepending on the smoothness properties of Mand uand then to estimate the error for the discretized method. When His not known and therefore we need to discretize directly the original problem or to consider some partial relaxation, the choice of ðθr;MrÞis not clear. 1214 CASADO-DÍAZ, CASTRO, LUNA-LAYNEZ, ZUAZUA Copyright ©by SIAM. Unauthorized reproduction of this article is prohibited. Remark 12. In Theorem 8.1, we have discretized the set of controls, but the state equation is directly solved. It will be interesting to study the convergence when we also discretize this equation, and in particular to study what the relation is that we must use between the triangulation chosen for the controls and the one chosen for the resolution of the state equation. A result in this sense can be found in [8], showing that in some cases the method converges using the same triangulation to discretize the controls and the state equation. Acknowledgment. The authors are grateful to the Basque Center for Applied Mathematics for its hospitality and support in several visits. REFERENCES [1] G. ALLAIRE,Shape Optimization by the Homogenization Method, Appl. Math. Sci. 146, Springer-Verlag, New York, 2002. [2] G. ALLAIRE AND S. GUTIÉRREZ,Optimal design in small amplitude homogenization, ESAIM Math. Model. Numer. Anal., 41 (2007), pp. 543–574. [3] J. C. BELLIDO AND P. PEDREGAL,Explicit quasiconvexification for some cost functionals depending on derivatives of the state in optimal designing, Discrete Contin. Dyn. Syst., 8 (2002), pp. 967–982. [4] B. BOURDIN,Filters in topology optimization, Internat. J. Numer. Methods Engrg., 50 (2001), pp. 2143–2158. [5] C. CARSTENSEN AND C. ORTHNER,Analysis of a class of penalty methods for computing singular minimizers, Comput. Methods Appl. Math., 10 (2010), pp. 137–163. [6] J. CASADO-DÍAZ,J.COUCE-CALVO,AND J. D. MARTÍN-GÓMEZ,Relaxation of a control problem in the coefficients with a functional of quadratic growth in the gradient, SIAM J. Control Optim., 47 (2008), pp. 1428–1459. [7] J. CASADO-DÍAZ,J.COUCE-CALVO,AND J. D. MARTÍN-GÓMEZ,Relaxation of optimal design problems with nonlinear functionals in the gradient, to appear. [8] J. CASADO-DÍAZ,J.COUCE-CALVO,M.LUNA-LAYNEZ,AND J. D. MARTÍN-GÓMEZ,Optimal design problems for a non-linear cost in the gradient: Numerical results, Appl. Anal., 87 (2008), pp. 1461–1487. [9] J. CASADO-DÍAZ,J.COUCE-CALVO,M.LUNA-LAYNEZ,AND J. D. MARTÍN-GÓMEZ,Discretization of coefficient control problems with a nonlinear cost in the gradient, in Integral Methods in Science and Engineering, Computational Methods 2, C. Constanda and M. E. Pérez, eds., Birkhäuser, Boston, 2010, pp. 55–63. [10] D. CHENAIS AND E. ZUAZUA,Finite element approximation of 2D elliptic optimal design, J. Math. Pures Appl. (9), 85 (2006), pp. 225–249. [11] Y. GRABOVSKY,Optimal design for two-phase conducting composites with weakly discontinuous objective functionals, Adv. in Appl. Math., 27 (2001), pp. 683–704. [12] R. LIPTON AND A. P. VELO,Optimal design of gradient fields with applications to electrostatics,in Nonlinear Partial Differential Equations and Their Applications, Collège de France Seminar XIV, D. Cioranescu and J. L. Lions, eds., Stud. Math. Appl. 31, North-Holland, Amsterdam, 2002, pp. 509–532. [13] K. A. LURIE,Applied Optimal Control Theory of Distributed Systems, Plenum Press, New York, 1993. [14] K. A. LURIE AND A. V. CHERKAEV,Exact estimates of the conductivity of a binary mixture of isotropic materials, Proc. Roy. Soc. Edinburgh Sect. A, 104 (1986), pp. 21–38. [15] F. MURAT,Un contre-example pour le problème du contrôle dans les coefficients, C. R. Math. Acad. Sci. Paris, 273 (1971), pp. 708–711. [16] F. MURAT,Théorèmes de non existence pour des problèmes de contrôle dans les coefficients, C. R. Math. Acad. Sci. Paris, 274 (1972), pp. 395–398. [17] F. MURAT AND L. TARTAR,H-convergence, in Topics in the Mathematical Modelling of Composite Materials, Progr. Nonlinear Differential Equations Appl. 31, L. Cherkaev and R. V. Kohn, eds., Birkhäuser, Boston, 1998, pp. 21–43. [18] P. PEDREGAL,Optimal design in two-dimensional conductivity for a general cost depending on the field, Arch. Ration. Mech. Anal., 182 (2006), pp. 367–385. APPROXIMATION OF AN OPTIMAL DESIGN PROBLEM 1215 Copyright ©by SIAM. Unauthorized reproduction of this article is prohibited. [19] S. SPAGNOLO,Sulla convergenza di soluzioni di equazioni paraboliche ed ellittiche, Ann. Sc. Norm. Super. Pisa Cl. Sci. (5), 22 (1968), pp. 571–597. [20] L. TARTAR,Problèmes de contrôle des coefficients dan des équations aux dérivées partielles, in Control Theory, Numerical Methods and Computer Systems Modelling, Lectures Notes in Econ. and Math. Systems 10, Springer-Verlag, Berlin, 1975. English translation: F. MURAT AND L. TARTAR,On the control of coefficients in partial differential equations, in Topics in the Mathematical Modelling of Composite Materials, Progr. Nonlinear Differential Equations Appl. 31, L. Cherkaev and R. V. Kohn, eds., Birkhäuser, Boston, 1998, pp. 1–8. [21] L. TARTAR,Cours Peccot, Collège de France, 1977, partly written in [17]. [22] L. TARTAR,Estimations fines de coefficients homogénéisés, in Ennio de Giorgi Colloquium (Paris 1983), Res. Notes Math. 125, P. Kree, ed., Pitman, London, 1985, pp. 168–187. [23] L. TARTAR,Remarks on optimal design problems, in Calculus of Variations, Homogenization and Continuum Mechanics, Ser. Adv. Math. Appl. Sci. 18, G. Buttazzo, G. Bouchitte, and P. Suquet, eds., World Scientific, Hackensack, NJ, 1994, pp. 279–296. [24] L. TARTAR,An introduction to the homogenization method in optimal design, in Optimal Shape Design, Lecture Notes in Math. 1740, A. Cellina and A. Ornelas, eds., Springer-Verlag, Berlin, 2000, pp. 47–156. [25] V. V. ZHIKOV,Weighted Sobolev spaces, Sb. Math., 189 (1998), pp. 1139–1170. [26] J. GOODMAN,R.V.KOHN,AND L. REYNA,Numerical study of a relaxed variational problem from optimal design, Comput. Methods Appl. Mech. Engrg., 57 (1986), pp. 107–127. 1216 CASADO-DÍAZ, CASTRO, LUNA-LAYNEZ, ZUAZUA Copyright ©by SIAM. Unauthorized reproduction of this article is prohibited. Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.