Arnaud M Ünch

Keywords: Arnaud AMS Classifications: 35K58, 93B05, 93E24 Control of semilinear PDEs, Fixed point theorem, Numerical approximation, Space-time discretization

Approximation of exact controls for semilinear wave and heat equations through space-time methods

Introduction

Approximation of null controllability problems for partial differential equations is a delicate issue. In contrast with optimal control problems, the occurrence of a terminal constraint for the state of the equation makes the analysis non trivial, both at the theoretical but also at the numerical level. Thus, it is by now wellknown since the pioneering works of Roland Glowinski in the nineties collected in [START_REF] Glowinski | Exact and approximate controllability for distributed parameter systems[END_REF] that the use of standard numerical schemes for hyperbolic equations may lead to divergent sequences of control as the discretization parameter goes to zero. This is due to spurious discrete high frequencies generated by the finite dimensional approximation. Similarly, for parabolic equations, the regularization phenomenon makes the approximation of controls badly conditioned and leads to highly oscillating behaviors. On the other hand, exact controllability results for semilinear equations, since the pioneering works of Enrique Zuazua [START_REF] Zuazua | Exact controllability for semilinear wave equations in one space dimension[END_REF] in the nineties, are usually based on non constructive fixed point arguments and therefore do not lead to method of approximations.

We focus here on the approximation of null distributed controls for semilinear wave and heat equation.

We first review some recent techniques that lead to robust numerical solution of null controllability problems associated with linear wave and heat equations. The methods are characterized by the fact that we approximate in finite dimension in space and time simultaneously. This is made possible by introducing an appropriate reformulation as an equation in a space of functions depending on the spatial and time variables which is then discretized and solved. In particular, we do not employ usual time-marching methods for the evolution equations. The well-posedness of these reformulations relies on so-called generalized observability inequalities, also refereed to as global Carleman estimates. The methods developed here to solve the optimality system associated with each controllability problem fall into the emergent strategy "control-thendiscretize". In contrast with the classical reverse strategy "discretize-then-control", we emphasize that it * Université Clermont Auvergne, CNRS, LMBP, F-63000 Clermont-Ferrand, France. e-mail: arnaud.munch@uca.fr.

1 leads to robust and strong convergent approximation with respect to the parameters of discretization. It is also notably appropriate for mesh adaptivity.

We also design, both for the wave and the heat case, a least-squares algorithm yielding sequences converging strongly and at least linearly to a controlled solution for the semilinear equation. Each element of the sequence is solution of a linearized controllability problem and therefore can be approximated numerically though a robust space-time formulation. Section 2 is devoted to the wave equation and Section 3 is devoted to the heat equation. In both cases, we illustrate our results with numerical experiments performed with the software Freefem++ (see [START_REF] Hecht | New development in Freefem++[END_REF]). Section 4 concludes with some perspectives.

Notations

In the text, Ω is a bounded domain of R d (d ≥ 1) with C 1,1 boundary and ω ⊂⊂ Ω is a non-empty open set. For any T > 0, we set Q T := Ω × (0, T ), q T := ω × (0, T ) and Σ T := ∂Ω × (0, T ).

The variable y is used for the state of the equation while the control is defined in term of the variable v.

Moreover, f is the function defining the nonlinearity of the equation. Last, the variable C denotes a generic constant depending only on T , Ω, ω but not on any state variable.

The wave equation

This section is devoted to the linear and semilinear wave equations. We first recall some classical controllability results (Section 2.1 and Section 2.2), then explain how one may construct a sequence (y k , v k ) k∈N converging strongly to a controlled pair for the semilinear equation, based on a suitable linearization (Section 2.3). In Section 2.4, we discuss some methods of numerical approximation and we conclude with some numerical experiments in Section 2.5. We mainly focus on distributed controls although similar results are available for boundary controls.

Controllability results for the linear wave equation

The linear wave equation, completed with Dirichlet and initial conditions, reads as follows:

∂ tt y -∆y + Ay = v1 ω + F in Q T , y = 0 on Σ T , (y(• , 0), ∂ t y(• , 0)) = (u 0 , u 1 ) in Ω.

(1)

Here, y is the state and v ∈ L 2 (q T ) is the control. We assume that the initial data (u 0 , u 1 ) belongs to V := H 1 0 (Ω) × L 2 (Ω), F ∈ L 2 (Q T ) and A ∈ L ∞ (0, T ; L d (Ω)). Under these assumptions, (1) possesses a unique weak solution in C 0 ([0, T ]; H 1 0 (Ω)) ∩ C 1 ([0, T ]; L 2 (Ω)), see [START_REF] Lions | Contrôlabilité exacte, perturbations et stabilisation de systèmes distribués[END_REF][START_REF] Fu | Exact controllability for multidimensional semilinear hyperbolic equations[END_REF].

The exact controllability problem for (1) in time T is formulated as follows:

given (u 0 , u 1 ), (z 0 , z 1 ) ∈ V , find a control v ∈ L 2 (q T ) such that the weak solution to [START_REF] Antonietti | A space-time discontinuous Galerkin method for the elastic wave equation[END_REF] satisfies (y(• , T ), ∂ t y(• , T )) = (z 0 , z 1 ).

In other terms, through the action on the open subset ω of Ω, we want to steer the solution from the state (u 0 , u 1 ) to the state (z 0 , z 1 ). In view of the linearity of the system (1), it is equivalent to reach the zero target, i.e. take (z 0 , z 1 ) = (0, 0) leading the so-called null controllability problem.

Using multiplier techniques, this controllability problem was solved in the eighties in [START_REF] Lions | Contrôlabilité exacte, perturbations et stabilisation de systèmes distribués[END_REF] in the case A ≡ 0, later generalized in [START_REF] Fu | Exact controllability for multidimensional semilinear hyperbolic equations[END_REF] as follows.

Theorem 1. [40, Theorem 2.2] For any

x 0 ∈ R d \Ω, let Γ 0 := {x ∈ ∂Ω : (x -x 0 ) • ν(x) > 0} and let O (Γ 0 ) := {y ∈ R d : dist (y, Γ 0 ) ≤ } for any > 0. Assume (H 0 ) T > 2 max x∈Ω |x -x 0 | and ω ⊇ O (Γ 0 ) ∩ Ω for some > 0.
Then (1) is exactly controllable in time T .

In Theorem 1, Γ 0 is the usual star-shaped part of Ω introduced in [START_REF] Lions | Contrôlabilité exacte, perturbations et stabilisation de systèmes distribués[END_REF]. Using microlocal analysis, we recall that C. Bardos, G. Lebeau and J. Rauch proved in [START_REF] Bardos | Sharp sufficient conditions for the observation, control, and stabilization of waves from the boundary[END_REF] that, in the class of C ∞ domains and for A ≡ 0, controllability holds if and only if (ω, T ) satisfies the following geometric control condition: "every ray of geometric optics that propagates in Ω and is reflected on Γ enters ω at a time t < T ".

Using duality arguments, Theorem 1 can be deduced from an observability estimate for the adjoint system. Thus, let us recall the following result, proved in [START_REF] Li | Exact controllability for semilinear wave equations[END_REF].

Proposition 1. [62, Theorem 2.1] Assume (H 0 ). For any A ∈ L ∞ (0, T ; L d (Ω)) and any (φ 0 , φ 1 ) ∈ H := L 2 (Ω) × H -1 (Ω), the weak solution φ to

∂ tt φ -∆φ + Aφ = 0 in Q T , φ = 0 on Σ T , (φ(• , 0), ∂ t φ(• , 0)) = (φ 0 , φ 1 ) in Ω, (2)
satisfies the following observability inequality, for some C > 0 only depending on Ω and T :

(φ 0 , φ 1 ) H ≤ Ce C A 2 L ∞ (0,T ;L d (Ω)) φ L 2 (q T ) . (3)
The inequality ( 3) is refereed as an observability inequality as the knowledge of φ on the subset q T of Q T allows to observe the full system. Among all admissible controls, we usually consider the control of minimal L 2 (q T ) norm which is unique and depends continuously on the data as follows.

Proposition 2. Let A ∈ L ∞ (0, T ; L d (Ω)), F ∈ L 2 (Q T ) and (u 0 , u 1 ), (z 0 , z 1 ) ∈ V be given. Assume (H 0 ).
Then the control of minimal L 2 (q T ) norm v together with the corresponding controlled weak solution y of (1)satisfy the following estimate, for some constant C > 0 only depending on Ω and T :

v L 2 (q T ) + (y, ∂ t y) L ∞ (0,T ;V ) ≤ C F L 2 (Q T ) + (u 0 , u 1 ) V + (z 0 , z 1 ) V e C A 2 L ∞ (0,T ;L d (Ω)) . (4)

Controllability results for a semilinear wave equation

We consider now the following system for the semilinear wave equation:

∂ tt y -∆y + f (y) = v1 ω in Q T , y = 0 on Σ T , (y(• , 0), ∂ t y(• , 0)) = (u 0 , u 1 ) in Ω. (5)
Here, f : R → R is a C 1 function such that |f (r)| ≤ C(1 + |r|) ln(2 + |r|) for all r ∈ R and some C > 0. There exists a unique global weak solution to [START_REF] Helio | The finite element method with Lagrange multipliers on the boundary: circumventing the Babuška-Brezzi condition[END_REF] [START_REF] Cazenave | Équations d'évolution avec non linéarité logarithmique[END_REF]).

in C 0 ([0, T ]; H 1 0 (Ω)) ∩ C 1 ([0, T ]; L 2 (Ω)) (see
Furthermore, imposing an adequate growth condition on f at infinity, the exact controllability problem has been solved in [START_REF] Li | Exact controllability for semilinear wave equations[END_REF] and generalized in [START_REF] Fu | Exact controllability for multidimensional semilinear hyperbolic equations[END_REF] to more general hyperbolic equations. |r| ln 2 |r| = 0, later relaxed in [START_REF] Cannarsa | One-sided and internal controllability of semilinear wave equations with infinitely iterated logarithms[END_REF] and [START_REF] Martinez | Exact controllability in "arbitrarily short time" of the semilinear wave equation[END_REF]. The exact controllability for subcritical nonlinearities is obtained in [START_REF] Dehman | Analysis of the HUM control operator and exact controllability for semilinear waves in uniform time[END_REF] under the sign condition rf (r) ≥ 0 for all r ∈ R. This last assumption has been weakened in [START_REF] Joly | A note on the semiglobal controllability of the semilinear wave equation[END_REF] to an asymptotic sign condition leading to a semi-global controllability result, in the sense that the final data (z 0 , z 1 ) must be prescribed in a precise subset of V .

The proof of Theorem 2 given in [START_REF] Li | Exact controllability for semilinear wave equations[END_REF] is based on the fixed-point argument introduced in [START_REF] Zuazua | Exact controllability for the semilinear wave equation[END_REF][START_REF] Zuazua | Exact controllability for semilinear wave equations in one space dimension[END_REF] and the a priori estimate (4) for the linear wave equation [START_REF] Antonietti | A space-time discontinuous Galerkin method for the elastic wave equation[END_REF]. More precisely, it is shown that the operator

Λ : L ∞ (0, T ; L d (Ω)) → L ∞ (0, T ; L d (Ω))
, where y ξ := Λ(ξ) is the solution to the linear problem

     ∂ tt y ξ -∆y ξ + f (ξ) y ξ = -f (0) + v ξ 1 ω in Q T , y ξ = 0 on Σ T , (y ξ (• , 0), ∂ t y ξ (• , 0)) = (u 0 , u 1 ) in Ω, f (r) :=    f (r) -f (0) r r = 0, f (0) r = 0 , (6)
and v ξ is the minimal L 2 (q T ) norm control for which (y ξ (• , T ), y ξ,t (• , T )) = (z 0 , z 1 ) has a fixed-point. The existence is obtained by using the Leray-Schauder's Theorem; in particular, under the growth assumption (H 1 ), it is shown that there exists a positive constant

M = M ( u 0 , u 1 V , z 0 , z 1 V ) such that Λ maps the ball B L ∞ (0,T ;L d (Ω)) (0, M ) into itself.
2.3 Construction of a convergent sequence of state-control pairs for the semilinear system (5): a least-squares approach

We now discuss the explicit construction of a sequence (v k ) k∈N that converges strongly to an exact control for [START_REF] Helio | The finite element method with Lagrange multipliers on the boundary: circumventing the Babuška-Brezzi condition[END_REF]. The controllability of nonlinear PDEs has attracted a large number of works in the last decades (see [START_REF] Coron | Control and nonlinearity[END_REF]). However, few are concerned with the computation of exact controls and the explicit construction of convergent approximations remains a challenge.

A first idea that comes to mind is to consider the Picard iterates (y k ) k∈N associated with the operator Λ, defined by y k+1 = Λ(y k ) for k ≥ 0, starting from some y 0 ∈ L ∞ (0, T ; L d (Ω)). The resulting sequence of controls (v k ) k∈N fulfills the following property: v k+1 ∈ L 2 (q T ) is the control of minimal L 2 (q T ) norm for which the associated solution to

∂ tt y k+1 -∆y k+1 + f (y k ) y k+1 = -f (0) + v k+1 1 ω in Q T , y k+1 = 0 on Σ T , (y k+1 (• , 0), ∂ t y k+1 (• , 0)) = (y 0 , y 1 ) in Ω (7)
satisfies (y k+1 (• , T ), ∂ t y k+1 (• , T )) = (z 0 , z 1 ). Such a strategy fails frequently, since the operator Λ is not in general a contraction, even if f is globally Lipschitz-continuous. We refer to [START_REF] Bottois | Constructive exact control of semilinear multi-dimensional wave equations[END_REF] for a numerical evidence of the lack of convergence (see also [START_REF] Fernández | Numerical null controllability of semi-linear 1-D heat equations: fixed point, least squares and Newton methods[END_REF] in a similar parabolic context).

A second idea is to use a method of the Newton kind to find a zero of the C 1 mapping F : Y → W , defined by

F(y, v) := ∂ tt y -∆y + f (y) -v1 ω , y(• , 0) -u 0 , ∂ t y(• , 0) -u 1 , y(• , T ) -z 0 , ∂ t y(• , T ) -z 1 (8)
for some appropriates Hilbert spaces Y and W . Thus, starting from (y 0 , v 0 ) ∈ Y , for each k ≥ 0 we set

(y k+1 , v k+1 ) = (y k , v k ) -(Y k , V k ) where V k is the control of minimal L 2 (q T ) norm such that the solution to ∂ tt Y k -∆Y k + f (y k ) Y k = V k 1 ω + ∂ tt y k -∆y k + f (y k ) -v k 1 ω in Q T , Y k = 0 on Σ T , Y k (• , 0) = u 0 -y k (• , 0), ∂ t Y k (• , 0) = u 1 -∂ t y k (• , 0) in Ω (9) satisfies Y k (• , T ) = z 0 -y k (• , T ) and ∂ t Y k (• , T ) = z 1 -∂ t y k (• , T ).
As is well-known, the resulting sequence may fail to converge if the initial guess (y 0 , v 0 ) is not close enough to a zero of F.

Given any initial data (u 0 , u 1 ) ∈ V , under assumptions on f that are slightly stronger than (H 1 ) and d ≤ 3, we can design an algorithm providing a sequence (y k , v k ) k∈N that converges to a controlled pair.

Moreover, after a finite number of iterates, the convergence is super-linear. This is achieved by introducing a least-squares functional that measures how much a pair (y, v) is close to a controlled solution for (5) and, then by determining a particular convergent minimizing sequence. Following [START_REF] Bottois | Constructive exact control of semilinear multi-dimensional wave equations[END_REF][START_REF] Münch | Constructive exact control of semilinear 1d wave equations by a leastsquares approach[END_REF], we define the Hilbert space

H := {(y, v) ∈ L 2 (Q T ) × L 2 (q T ) : y ∈ C 0 ([0, T ]; H 1 0 (Ω)) ∩ C 1 ([0, T ]; L 2 (Ω)), ∂ tt y -∆y ∈ L 2 (Q T )},
which is endowed with the scalar product (y, v), (y, v) H := (y, y)

L 2 (Q T ) + (y(• , 0),∂ t y(• , 0)), (y(• , 0), ∂ t y(• , 0)) V + (∂ tt y -∆y, ∂ tt y -∆y) L 2 (Q T ) + (v, v) L 2 (q T ) .
We then define the non-empty linear manifold

A := {(y, v) ∈ H : (y(• , 0), ∂ t y(• , 0)) = (u 0 , u 1 ), (y(• , T ), ∂ t y(• , T )) = (z 0 , z 1 )}
and the associated space A 0 := {(y, v) ∈ H : (y(• , 0), ∂ t y(• , 0)) = (0, 0), (y(• , T ), ∂ t y(• , T )) = (0, 0)} and consider the following non-convex extremal problem of the least-squares kind inf

(y,v)∈A E(y, v), E(y, v) := 1 2 ∂ tt y -∆y + f (y) -v 1 ω 2 L 2 (Q T ) . (10)
The functional E is well-defined in A: we check that there exists

C > 0 such that E(y, v) ≤ C(1 + (y, v) 3 H ) for all (y, v) ∈ A.
Main properties of the functional E The functional E is Gâteaux-differentiable over A. Moreover, it is shown in [START_REF] Bottois | Constructive exact control of semilinear multi-dimensional wave equations[END_REF] the following inequality.

E(y, v) ≤ C 1 + f (y) L ∞ (0,T ;L 3 (Ω)) e C f (y) 2 L ∞ (0,T ;L d (Ω)) E (y, v) A 0 , ∀(y, v) ∈ A. (11)
Consequently, any critical point (y, v)

∈ A of E such that f (y) L ∞ (0,T ;L 3 (Ω)) is finite is a zero for E,
i.e. a solution to the controllability problem and any sequence (

y k , v k ) k>0 satisfying E (y k , v k ) A 0 → 0 as k → ∞ for which f (y k ) L ∞ (0,T ;L 3 (Ω)) is uniformly bounded is such that E(y k , v k ) → 0 as k → ∞.
This property does not imply the convexity of the functional E (and a fortiori the strict convexity of E, which actually cannot hold in view of the multiple zeros for E). However, it shows that a minimizing sequence for E cannot be stuck in a local minimum. In order to construct a minimizing sequence for E, we formally look, for any (y, v) ∈ A, for a pair (Y 1 , V 1 ) ∈ A 0 solving the following linear wave equation

∂ tt Y 1 -∆Y 1 + f (y) • Y 1 = V 1 1 ω + ∂ tt y -∆y + f (y) -v 1 ω in Q T , Y 1 = 0 on Σ T , (Y 1 (• , 0), ∂ t Y 1 (• , 0)) = (0, 0) in Ω. (12)
Since (Y 1 , V 1 ) belongs to A 0 , V 1 is a null control for Y 1 . Among all the controls of this linear equation, we select the control of minimal L 2 (q T ) norm. In the sequel, we call the corresponding solution (Y

1 , V 1 ) ∈ A 0 the solution of minimal control norm. Then the derivative of E at (y, v) ∈ A in the direction (Y 1 , V 1 ) satisfies E (y, v) • (Y 1 , V 1 ) = 2E(y, v)
which allows to define a minimizing sequence for E.

Given f ∈ C 1 (R) and p ∈ (0, 1], we introduce the following hypothesis: Then, for any initial and final data (u 0 , u 1 ) and (z 0 , z 1 ) in V and any starting (y 0 , v 0 ) ∈ A, the sequence

(H p ) [f ] p := sup a,b∈R a =b |f (a) -f (b)| |a -
(y k , v k ) k∈N defined by (y k+1 , v k+1 ) = (y k , v k ) -λ k (Y 1 k , V 1 k ), k ∈ N, λ k := argmin λ∈[0,1] E (y k , v k ) -λ(Y 1 k , V 1 k ) , (13)
where

(Y 1 k , V 1 k ) ∈ A 0 is the solution of minimal control norm of ∂ tt Y 1 k -∆Y 1 k + f (y k ) • Y 1 k = V 1 k 1 ω + (∂ tt y k -∆y k + f (y k ) -v k 1 ω ) in Q T , Y 1 k = 0 on Σ T , (Y 1 k (• , 0), ∂ t Y 1 k (• , 0)) = (0, 0) in Ω ( 14
)
strongly converges to a pair (y, v) ∈ A satisfying (5) and the condition (y(• , T ), ∂ t y(• , T )) = (z 0 , z 1 ), for all (u 0 , u 1 ), (z 0 , z 1 ) ∈ V . Moreover, the convergence is at least linear and at least of order p + 1 after a finite number of iterations.

Theorem 3 provides a new proof of the exact controllability of semilinear multi-dimensional wave equations which is moreover constructive, with an algorithm that converges unconditionally at least with order p + 1.

Remark 1. The asymptotic condition (H 2 ) on f is slightly stronger than the assumption (H 1 ) made in [START_REF] Fu | Exact controllability for multidimensional semilinear hyperbolic equations[END_REF]: this is due to our linearization of ( 5), which concerns f , while the linearization [START_REF] Ervedoza | Numerical approximation of exact controls for waves[END_REF] in [START_REF] Fu | Exact controllability for multidimensional semilinear hyperbolic equations[END_REF] involves

r → (f (r) -f (0))/r. Remark however that the particular example f (r) = a + br + cr ln 1/2 (1 + |r|) with
a, b ∈ R and c > 0 small enough (which is somehow the limit case in Theorem 2) satisfies (H 2 ) as well as

(H p ) for any p ∈ (0, 1]. Remark 2. Defining F : A → L 2 (Q T ) by F(y, v) := (∂ tt y-∆y+f (y)-v 1 ω ), we have E(y, v) = 1 2 F(y, v) 2 2
and we observe that, for λ k = 1, the algorithm (13) coincides with the Newton algorithm associated with the mapping F (see [START_REF] Bottois | Constructive exact control of semilinear multi-dimensional wave equations[END_REF]). This explains the super-linear convergence property in Theorem 3, in particular the quadratic convergence when p = 1. The optimization of the parameter λ k allows a global convergence property of the algorithm and leads to the so-called damped Newton method applied to F (we refer to [28, Chapter 8])). As far as we know, the analysis of damped type Newton methods for PDEs has deserved very few attention in the literature (we mention [START_REF] Lemoine | A fully space-time least-squares method for the unsteady Navier-Stokes system[END_REF][START_REF] Saramito | A damped Newton algorithm for computing viscoplastic fluid flows[END_REF] in the context of fluids mechanics.)

Remark 3. Instead of the control of minimal L 2 -norm, we may consider weighted costs involving both the state and the control. In the framework of boundary controllability, it is shown in [START_REF] Bhandari | Exact boundary controllability of 1d semilinear wave equation through a constructive approach[END_REF] using global Carleman estimates (see [START_REF] Bellassoued | Carleman estimates and applications to inverse problems for hyperbolic systems[END_REF]) that appropriate choices of the weights lead to convergent result with linear rate assuming only (H 2 ). We also refer to Section 3, in particular Theorem 8 and 9, devoted to the heat equation where this is discussed with more details.

Numerical approximation of exact controls for the wave equation

We now discuss the approximation of exact controls for the wave equation. For brevity, we employ the notation L A φ := ∂ tt φ -∆φ + Aφ. According to the previous section and Theorem 3, a convergent numerical approximation of controls for the linear wave equation allows to construct a convergent numerical approximation of controls in the semilinear case as well. We therefore focus on the linear situation.

Without loss of generality, we assume that the target (z 0 , z 1 ) vanishes and look for an approximation of the control of minimal L 2 (q T )-norm solution of inf v∈C(u0,u1,T )

J(v), J(v) := v 2 L 2 (q T )
where C(u 0 , u 1 , T ) denotes the non empty convex set of controls. Applying the Fenchel-Rockafellar duality theory (see [START_REF] Ekeland | Convex analysis and variational problems[END_REF]), the control of minimal L 2 (q T ) norm is expressed by v = φ1 ω where φ solves (2) with initial data (φ 0 , φ 1 ) ∈ H and (φ 0 , φ 1 ) solves the following extremal problem inf

(φ0,φ1)∈H J (φ 0 , φ 1 ), J (φ 0 , φ 1 ) := 1 2 q T |φ| 2 + Q T F φ + φ 1 , u 0 H -1 (Ω),H 1 0 (Ω) -φ 0 , u 1 L 2 (Ω) . (15)
Here, J is the so-called conjugate functional associated with J. The observability inequality (3) for the variable φ leads to the well-posedness of this extremal problem. Compared with the initial minimization of J over exact null controls for (1), this equivalent problem does not make appear any terminal constraint and therefore can be solved through an iterative descent method: the conjugate gradient algorithm is usually employed (see [START_REF] Glowinski | Exact and approximate controllability for distributed parameter systems[END_REF]) since the so-called HUM operator related to J is coercive.

However, at the finite dimensional level (induced by the numerical approximation in time and space), [START_REF] Aranda | A variational method for the numerical simulation of a boundary controllability problem for the linear and semilinear 1D wave equations[END_REF] can not be in general solved exactly: in other words, the constraint

L A φ = 0 in Q T is not exactly satisfied
what makes irrelevant the observability inequality (3). For some specific geometries, let us mention however spectral methods initially developed by F. Bourquin in [START_REF] Bourquin | Approximation theory for the problem of exact controllability of the wave equation with boundary control[END_REF] (then used in [START_REF] Lebeau | Experimental study of the HUM control operator for linear waves[END_REF]) leading to precise convergence results. At least two possibilities appear in order to bypass this difficulty. The first one is to first reformulate the controllability problem at the finite dimensional level leading to so-called discretize-then-control strategy.

The discretize-then-control strategy A possible strategy is to first discretize ( 5) and then determine a discrete control of minimal L 2 (q T ) norm by minimizing the associated discrete functional J h , where h stands for the discretization parameter. This has been the subject of numerous works and extended to many others PDEs, starting from the seminal contribution of R. Glowinski and J.-L. Lions [START_REF] Glowinski | Exact and approximate controllability for distributed parameter systems[END_REF] (see also [START_REF] Glowinski | Exact and approximate controllability for distributed parameter systems[END_REF]). The experiments there reveal that the convergence of the approach is very sensitive to the chosen approximation. Thus, if standard time marching convergent schemes are coupled with standard finite element approximations, the associated observability constant may not be uniformly bounded with respect to h, leading to a divergence of the discrete family of controls (v h ) h>0 as h tends to zero. In practice, the conjugate gradient algorithm fails to converge as the discretization becomes finer. As conjectured in [START_REF] Glowinski | Exact and approximate controllability for distributed parameter systems[END_REF] and later analyzed (see [START_REF] Zuazua | Propagation, observation, and control of waves approximated by finite difference methods[END_REF] for a review), this is due to spurious high frequencies discrete modes which are not exactly controllable uniformly in h. This pathology can easily be avoided in practice by adding to the conjugate functional a regularized Tikhonov parameter; this leads to so called approximate controls, solving the control problem only up to a small remainder term:

y h (•, T ), ∂ t y h (•, T ) H 1 0 (Ω)×L 2 (Ω) ≤ O(h α ), ∀h > 0
where the real α is related to the order of the numerical scheme. This is sufficient for the applications but not fully satisfactory from a theoretical viewpoint. That is why several cures aiming to filter out the high frequencies have been proposed and analyzed, mainly for simple geometries (1d interval, unit square in 2d, etc) with finite differences schemes. The simplest but artificial approach is to eliminate the highest eigenmodes of a discrete approximation of the initial condition as discussed in one space dimension in [START_REF] Micu | Uniform boundary controllability of a semi-discrete 1-D wave equation[END_REF], and extended in [START_REF] Lissy | Optimal filtration for the approximation of boundary controls for the onedimensional wave equation using a finite-difference method[END_REF]. We also mention so called bi-grid methods (based on the projection of the discrete gradient of J on a coarse grid) proposed in [START_REF] Glowinski | A numerical approach to the exact boundary controllability of the wave equation. I. Dirichlet controls: description of the numerical methods[END_REF] and analyzed in [START_REF] Liviu | Convergence of a two-grid algorithm for the control of the wave equation[END_REF][START_REF] Loreti | An Ingham type proof for a two-grid observability theorem[END_REF] leading to convergence results. One may also design more elaborated discrete schemes avoiding spurious modes: we mention [START_REF] Glowinski | A mixed finite element formulation for the boundary controllability of the wave equation[END_REF] based on a mixed reformulation of the wave equation analyzed later with finite difference schemes in [START_REF] Castro | Boundary controllability of a linear semi-discrete 1-D wave equation derived from a mixed finite element method[END_REF][START_REF] Castro | Numerical approximation of the boundary control for the wave equation with mixed finite elements in a square[END_REF][START_REF] Asch | Uniformly controllable schemes for the wave equation on the unit square[END_REF] at the semi-discrete level and then extended in [START_REF] Münch | A uniformly controllable and implicit scheme for the 1-D wave equation[END_REF] to a full space-time discrete setting, leading to strong convergent results. For instance, in [START_REF] Münch | A uniformly controllable and implicit scheme for the 1-D wave equation[END_REF], the following scheme

D ∆t (y ∆t,∆x ) -D ∆x (y ∆t,∆x ) + 1 4 (∆ 2 t -∆ 2 x )D ∆x (D ∆t (y ∆t,∆x )) = 0
is proved to be uniformly controllable with respect to the discretization h = (∆ t , ∆ x ) as it leads to a discrete family of controls converging strongly to a control for the wave equation as soon as the controllability T is large enough such that T > 2 max(1, ∆ 2 t /∆ 2 x ) (see [START_REF] Münch | A uniformly controllable and implicit scheme for the 1-D wave equation[END_REF]Theorem 2.8]). Here, D η (z) stands for the standard operator

D η (z)(r) = z(r + η) -2z(r) + z(r -η) η 2
, ∀r ∈ R, ∀η > 0 associated with the centered approximation of order two of the second derivative of any smooth function z.

The previous works, notably reviewed in [START_REF] Zuazua | Propagation, observation, and control of waves approximated by finite difference methods[END_REF][START_REF] Ervedoza | Numerical approximation of exact controls for waves[END_REF], fall within an approach that can be called "discretize then control " as they aim to control exactly to zero a finite dimensional approximation of the wave equation.

A relaxed controllability approach is analyzed in [START_REF] Burman | A fully discrete numerical control method for the wave equation[END_REF] using a stabilized finite element method in space and leading for smooth two and three dimensional geometries to a strong convergent approximations (we refer to [14, Theorem 2.1]). The controllability requirement is imposed via appropriate penalty terms. We also mention [START_REF] Pedregal | A numerical method of local energy decay for the boundary controllability of time-reversible distributed parameter systems[END_REF] based on the Russel's stabilization implies control principle, extended in [START_REF] Cîndea | An approximation method for exact controls of vibrating systems[END_REF] and [START_REF] Gunzburger | A numerical method for exact boundary controllability problems for the wave equation[END_REF][START_REF] Aranda | A variational method for the numerical simulation of a boundary controllability problem for the linear and semilinear 1D wave equations[END_REF] for least-squares based method.

The control-then-discretize strategy A second strategy allowing to bypass the issue of approximating the constraint L A φ = 0 is somehow to relax it by keeping the variable φ as the main variable into a space-time formulation. This leads to a "control-then-discretize" procedure, where the optimality system associated with problem (15) mixing the boundary condition in time and space and involving the primal and adjoint state is discretized within a priori a space-time approximation. The well-posedness of such system is achieved by using so called global or generalized observability inequalities (usually refereed to global Carleman inequality, see [START_REF] Bellassoued | Carleman estimates and applications to inverse problems for hyperbolic systems[END_REF]).

To this purpose, we keep φ as the main variable and introduce the Hilbert space

Φ := φ ∈ L 2 (Q T ); φ ∈ C([0, T ]; L 2 (Ω)) ∩ C 1 ([0, T ]; H -1 (Ω), L A φ ∈ L 2 (0, T ; H -1 (Ω)) , endowed with the inner product < φ, φ > Φ :=< φ, φ > L 2 (q T ) + < L A φ, L A φ > L 2 (0,T ;H -1 (Ω))
. We also introduce the subspace W := {φ ∈ Φ, L A φ = 0} and remark that ( 15) is equivalent to the extremal problem min φ∈W J (φ) (using that φ is uniquely determined from (φ 0 , φ 1 ) ∈ L 2 (Ω) × H -1 (Ω)). Since φ is now the main variable, we may address the linear constraint L A φ = 0 through a Lagrange multiplier λ ∈ M := L 2 (0, T ; H 1 0 (Ω)), leading to the following equivalent saddle point problem sup

λ∈L 2 (0,T,H 1 0 (Ω)) inf φ∈Φ L r (φ, λ), L r (φ, λ) := J (φ)+ T 0 λ, L A φ H 1 0 (Ω),H -1 (Ω) + r 2 L A φ 2 L 2 (0,T ;H -1 (Ω)) (16)
for any augmentation parameter r ≥ 0 and the following mixed formulation: for any r ≥ 0, find (φ, λ)

∈ Φ × L 2 (0, T ; H 1 0 (Ω)) such that a r (φ, φ) + b(λ, φ) = l(φ), ∀φ ∈ Φ, b(λ, φ) = 0, ∀λ ∈ L 2 (H 1 0 (Ω)), with              a r : Φ × Φ → R, a r (φ, φ) :=< φ, φ > L 2 (q T ) + Q T F φ + r < L A φ, L A φ > L 2 (0,T ;H -1 (Ω))) , b : M × Φ → R, b(λ, φ) := T 0 < λ, L A φ > H 1 0 (Ω),H -1 (Ω) , l : Φ → R, l(φ) :=< φ 1 , u 0 > H -1 (Ω),H 1 0 (Ω) -< φ 0 , u 1 > L 2 (Ω) . (17)
It turns out that the Lagrange multiplier coincides with the controlled solution of the wave equation. 1. The mixed problem (17) is well-posed and its unique solution (φ, λ) ∈ Φ × L 2 (0, T ; H 1 0 (Ω)) is the unique saddle-point of the Lagrangian L r defined in [START_REF] Carthel | On exact and approximate boundary controllabilities for the heat equation: a numerical approach[END_REF].

2. The optimal φ is the minimizer of J over Φ, while the optimal multiplier λ is the state of the controlled wave equation (1) in the weak sense (associated with the control φ1 ω ).

The fundamental tool used to prove the well-posedness and notably the continuity of the linear form l is the following generalized observability inequality:

φ(• , 0, ), ∂ t φ(• , 0) 2 H ≤ C(Ω, T, A L ∞ (0,T ;L d (Ω)) ) φ L 2 (q T ) + L A φ L 2 (0,T ;H -1 (Ω)) ∀φ ∈ Φ, (18)
which can be easily deduced from the inequality (3) using the linearity of the equation (we refer for instance to [START_REF] Castro | Controllability of the linear one-dimensional wave equation with inner moving forces[END_REF]). With respect to (3), the main interest of ( 18) is that it remains true for any finite dimensional subspace Φ h ⊂ Φ parametrized with h > 0 (with a constant independent of h). In other words, there is no need to prove any uniform property for some discrete observability constant.

The well-posedness of ( 17) is based on two properties (that should be preserved uniformly at the finite

∃δ > 0 s.t. inf λ∈M sup φ∈Φ b(λ, φ) λ M φ Φ ≥ δ.
Let T := {T h , h > 0} be family of regular triangulations of the space-time domain

Q T such that Q T = ∪ K∈T h K.
The family is indexed by h = max K∈τ h |K|. The coercivity property of the bilinear form a remains true over Φ h × Φ h for any finite dimensional subspace Φ h ⊂ Φ as soon as the augmentation parameter r is strictly positive.

On the other hand, a discrete inf-sup property, uniformly with respect to the parameter h, is in general more delicate to obtain as it depends strongly on the discrete spaces M h ⊂ M and Φ h used. For instance, if we define

M h := {p h ∈ C(Q T ); (p h ) |K ∈ P 1 (K) ∀K ∈ T h } where P k (K) denotes the space of polynomials of degree k and Φ h := {p h ∈ C 1 (Q T ); (p h ) |K ∈ HCT (K) ∀K ∈ T h }
where HCT denotes the Hsieh-Clough-Tocher composite finite element (see [START_REF] Ciarlet | Interpolation error estimates for the reduced Hsieh-Clough-Tocher triangle[END_REF]), we numerically observe (by the inf-sup test, see [START_REF] Chapelle | The inf-sup test[END_REF]) that a discrete inf-sup property holds true when the parameter r is of order of h 2 . This leads in practice to a convergent approximation of the control of minimal L 2 (q T ) norm. Remark that a C 1 finite element is used in order to ensure that L A φ h belongs to L 2 (Q T ) for any φ h ∈ Φ h . The theoretical study of the behavior with respect to h of inf λ∈M h sup φ∈Φ h b(λ,φ) λ M φ Φ is in general a difficult question. This is a fortiori true here since the constraint L A φ ∈ L 2 (Q T ) implies second derivates in time and space and involves C 1 finite element.

Hopefully, one may avoid it by stabilizing the mixed formulation with respect to the variable λ (see the seminal work [START_REF] Helio | The finite element method with Lagrange multipliers on the boundary: circumventing the Babuška-Brezzi condition[END_REF]): this consists in adding to the Lagrangian some terms so as to get a coercivity property for the variable λ as well. This is notably employed in [START_REF] Montaner | Approximation of controls for linear wave equations: a first order mixed formulation[END_REF] devoted to the approximation of boundary controls for the wave equation, preliminary reformulated as a first order system. This reformulation as a first order system requires, within a conformal approximation, only C 0 finite element (but needs to be stabilized whatever be the value of the augmentation parameter).

Stabilization methods may also be employed in the context of non-conformal approximations. In this respect, let us introduce

V q h = {p h ∈ C(Q T ); (p h ) |K ∈ P q (K) ∀K ∈ T h } and consider the discrete Lagrangian L h : V p h × V q h → R, given by L h (φ h , λ h ) := J (φ h ) + h 2 2 L A φ h 2 L 2 (Q T ) + h 2 K∈T h ∂K [[∂ ν φ h ]] 2 + h -1 Σ T φ 2 h -h -1 Σ T λ 2 h + Q T (-∂ t φ h ∂ t λ h + ∇φ h • ∇λ h + Aφ h λ h ) - h 2 K∈T h ∂K [[∂ ν λ h ]] 2 - h 2 2 L A λ h -φ h 1 ω 2 L 2 (Q T ) ,
where [[∂ ν φ h ]] denotes the jump of the normal derivative of φ h across the internal edges of the triangulation.

The terms

h 2 Lφ h L 2 (Q T ) and -h 2 Lλ h -φ h 1 ω 2 L 2 (Q T )
play a symmetric role. Both vanish at the continuous level. On the other hand, the jump terms somehow aim to control the regularity of the approximation.

The discrete Lagrangian L h admits a unique saddle-point. The well-posedness is based on a variant of the generalized observability inequality [START_REF] Castro | Boundary controllability of a linear semi-discrete 1-D wave equation derived from a mixed finite element method[END_REF], where the L 2 (0, T ; H -1 (Ω)) norm of L A φ is replaced by the

H -1 (Q T ) norm.
Moreover, if the saddle-point (φ, λ) of L r is smooth enough, the following approximation result holds true (we refer to [13, section 2] and also [START_REF] Burman | Space time stabilized finite element methods for a unique continuation problem subject to the wave equation[END_REF] in the closed context of data assimilation problems):

Theorem 5. [13, Theorem 2.5] Assume (H 0 ). Let p, q ≥ 1, h > 0 and r ≥ 0. Let (φ h , λ h ) ∈ V q h × V p h be the saddle point of L h and assume that the saddle point (φ, λ) of L r (see [START_REF] Carthel | On exact and approximate boundary controllabilities for the heat equation: a numerical approach[END_REF]) belongs to H q+1 (Q T )×H p+1 (Q T ). Then, there exists a positive constant C independent of h such that

χ(φ -φ h ) L 2 (Q T ) ≤ C(h p λ H p+1 (Q T ) + h q φ H q+1 (Q T ) ), ( 19
)
where χ is a cut-off function of the form χ(x, t) = χ 0 (x)χ 1 (t), with χ 0 ∈ C ∞ 0 (ω) and χ 1 ∈ C ∞ 0 (0, T ).

The regularity assumption on the optimal pair (φ, λ) notably holds true if the initial data (u 0 , u 1 ) to be controlled are smooth and satisfy compatibility conditions at ∂Ω × {0} (we refer to [START_REF] Ervedoza | A systematic method for building smooth controls for smooth data[END_REF]).

To end this brief review on the control-then-discretize approach, we emphasize that, in order to avoid the delicate issue of the inf-sup condition, we can alternatively consider a cost that involves both the control and the state. Note that the minimizer of the functional (y, v) → J(y, v)

:= y 2 L 2 (Q T ) + v 2 L 2 (q T )
over the control-state pair for ( 1) is given by (y, v) = (-L A φ, φ 1 ω ), where φ ∈ Φ solves

a r=1 (φ, φ) =< ∂ t φ(• , 0), u 0 > H -1 (Ω),H 1 0 (Ω) -< φ(• , 0), u 1 > L 2 (Ω) , ∀φ ∈ Φ, (20)
a well-posed problem in view of the generalized inequality [START_REF] Castro | Boundary controllability of a linear semi-discrete 1-D wave equation derived from a mixed finite element method[END_REF]. When a conformal and dense finite element approximation space Φ h ⊂ Φ is employed, Cea's Lemma yields a r=1 (φ h -φ, φ h -φ) → 0 as h → 0 and a strong convergent approximation φ h 1 ω of a control for (1) is obtained. Once φ h is computed from the fourth-order in time and space elliptic problem [START_REF] Cazenave | Équations d'évolution avec non linéarité logarithmique[END_REF], an approximation of the controlled solution is defined by y h := -L A φ h . We refer to [START_REF] Cîndea | Numerical controllability of the wave equation through primal methods and Carleman estimates[END_REF] where this method is fully analyzed for the one-dimensional wave equation with C 1 (Q T ) coefficients. We also refer to the recent work [START_REF] Bhandari | Exact boundary controllability of 1d semilinear wave equation through a constructive approach[END_REF].

It is also interesting to point out that the control-then-discretize approaches is notably well-suited for mesh adaptivity. We mention a growing interest for space-time (finite element) methods of approximation for the wave equation, initially advocated in [START_REF] Hulbert | Space-time finite element methods for second-order hyperbolic equations[END_REF] and more recently in [START_REF] Langer | Space-Time Methods[END_REF], [START_REF] Antonietti | A space-time discontinuous Galerkin method for the elastic wave equation[END_REF], [START_REF] Dumont | 4D remeshing using a space-time finite element method for elastodynamics problems[END_REF], [START_REF] Dörfler | Space-time discontinuous galerkin discretizations for linear first-order hyperbolic evolution systems[END_REF], [START_REF] Steinbach | A Stabilized Space-Time Finite Element Method for the Wave Equation[END_REF].

Numerical illustrations

We first illustrate Theorem 5 in the one dimensional case. For simplicity, we take A ≡ 0 and F ≡ 0 in [START_REF] Antonietti | A space-time discontinuous Galerkin method for the elastic wave equation[END_REF]. The initial condition to be controlled is (u 0 , u 1 ) = (sin(πx), 0) ∈ H k+1 (Ω)×H k (Ω) for all k ∈ N leading to regular

(φ -φ h ) L 2 (Q T ) / χφ L 2 (Q T ) associated with T = 2
with respect to the parameter h for various pairs of (p, q). Remark that explicit solutions are not available in the distributed case: we define as "exact" solution (y, φ) the one of ( 16) from a fine and structured mesh (composed of 409 000 triangles and 205 261 vertices) corresponding to h ≈ 4.41×10 -3 and (u h , φ h ) ∈ V p h ×V q h with (p, q) = (3, 3). We observe rates close to 0.5, 2 and 3 for (p, q) = (1, 1), (p, q) = (2, 2) and (p, q) = (3, 3) respectively, in agreement with Theorem 5. For comparison, Figure 1-right depicts the evolution of the relative error for χ 0 (t) = 1 and χ 1 (x) = 1 (a,b) (x), i.e. when no regularization of the control support is introduced. We still observe the convergence with respect to the parameter h but with a reduced rate. For instance, for (p, q) = (2, 2), the rate is close to 1.5. This highlights the influence of the cut off functions, including for very smooth initial conditions. We refer to [13, Section 5.1] for more details.

In order to enhance the robustness of the method, we also consider in the boundary case a stiff situation with discontinuous initial condition: (u 0 , u 1 ) = (4x1 (0,1/2) , 0), x ∈ (0, 1). We refer to [START_REF] Burman | Spacetime finite element methods for control problems subject to the wave equation[END_REF]Theorem 4.6] for convergent results in the boundary cases. The corresponding control of minimal L 2 (0, T ) with T = 2 acting at x = 1 is given by the trace of the corresponding solution : explicit computations using d'Alembert formula

χ(φ -φ h ) L 2 (Q T ) / χφ L 2 (Q T )
vs. h with (left) and without (right) regularization of the control support q T . leads to v(t) = 2(1 -t)1 (1/2,3/2) (t). The corresponding controlled solution is

y(x, t) =    4x 0 ≤ x + t < 1 2 , 2(x -t) -1 2 < t -x < 1 2 , x + t ≥ 1 2 , 0 elsewhere.
The initial condition of the corresponding adjoint solution is (φ 0 , φ 1 ) = (0, -2x

1 (0,1/2) (x)) ∈ H 1 (Ω) × L 2 (Ω)
Both the variable φ and y develop singularities (where y and ∇φ are discontinuous). Figure 2 depicts the

evolution of ∂ x φ h (1, •) -v L 2 (0,T ) / v L 2 (0,T )
with respect to the discretization parameter h, leading to a rate of convergence close to 1/2. We also emphasize that the space-time discretization formulation is appropriated for mesh adaptivity: using the space of approximation V 1 h × V 2 h , Figure 4-left (resp. right) depicts the mesh obtained after seven adaptative refinements based on the local values of the gradient of φ h (resp. λ h ). Starting with a coarse mesh composed of 288 triangles and 166 vertices, the final mesh is composed with 13068 triangles and 6700 vertices. We refer to [13, Section 5] for numerical illustrations of Theorem 5 with smooth initial data.

The second experiment illustrates Theorem 3 devoted to a semilinear situation in the two dimensional case with Ω = (0, 1) 2 (we refer to [START_REF] Bottois | Constructive exact control of semilinear multi-dimensional wave equations[END_REF] for more details). The final time is taken equal to T = 3 and the control domain ω is depicted in Figure 3. As for the initial and final conditions, we take (u 0 , u 1 ) ≡ (100 sin(πx 1 ) sin(πx 2 ), 0) and (z 0 , z 1 ) ≡ (0, 0), respectively. We refer to [START_REF] Asch | Uniformly controllable schemes for the wave equation on the unit square[END_REF][START_REF] Münch | Optimal design of the support of the control for the 2-D wave equation: a numerical method[END_REF] for numerical experiments in the two dimensional case. Moreover, for any real constant c f , we consider the nonlinear function f (r) = -c f r ln 1/2 (2 + |r|), for all r ∈ R. Note that f satisfies (H p ) for p = 1 and (H 2 ) for |c f | small enough.

Remark that the unfavorable situation (for which the norm of the uncontrolled corresponding solution grows) corresponds to strictly positives values of c f . Table 1, Figures 5 and6 show the results obtained for c f = 10. The convergence is observed after 4 iterations. The optimal steps λ k are very close to one. The main difference with lower values of c f (for instance c f = 5) is the behavior of the uncontrolled solution, which grows exponentially with respect to the time variable, as shown in Figure 5. As expected, this large value of c f induces a large gap between the nonlinear and the linear controls.

We observe that the nonlinear control v -the limit of the sequence (v k ) k∈N -acts stronger from the beginning, precisely in order to compensate the initial exponential growth of the solution outside the set ω. We also observe that the control reduces the oscillations of the corresponding controlled solution (in comparison with the solution to the linear equation). The effect of the nonlinear control on the system is measured through the relative error E T := (y,∂ty)(• ,T ;v ) V (y,∂ty)(• ,T ;0) V where y(• , T, v ) (resp. y(• , T, 0)) is the solution iterate k 1: c f = 10; Norms of (y k , v k ) with respect to k defined by the algorithm [START_REF] Fernández | The cost of approximate controllability for heat equations: the linear case[END_REF].

2E(y k , v k ) y k -y k-1 L 2 (Q T ) y k-1 L 2 (Q T ) v k -v k-1 L 2 χ (q T ) v k-1 L 2 χ (q T ) y k L 2 (Q T ) v k L 2 χ (q T ) λ k 0 7.
Figure 5:

c f = 10 -y 4 (• , t) L 2 (Ω) ( ), y 0 (• , t) L 2 (Ω) ( ) and y(• , t; 0) L 2 (Ω) ( ) w.r.t. t. Figure 6: c f = 10 -v 4 (• , t) L 2 χ (ω) ( ), and v 0 (• , t) L 2 χ (ω) ( ) w.r.t. t.

The heat equation

In this section, we consider the heat equation, both in linear and semilinear regime and highlight that spacetime approaches also lead to robust numerical approximation of exact controls. The approach is similar with the notable exception that it involves singular in time Carleman weights, in the framework proposed by Fursikov and Imanuvilov in [START_REF] Fursikov | Controllability of evolution equations[END_REF]. This third section follows the same outline than the previous one.

Controllability results for the linear heat equation

As a preliminary step for a semilinear situation, we recall some controllability results for the linear heat equation with potential A ∈ L ∞ (Q T ) and right hand side F ∈ L 2 (ρ 0,s , Q T ) for a precise weight ρ 0,s parametrized by s ∈ R + , that is defined in the sequel. More precisely, we are interested in the existence of a control v such that the solution z of

∂ t z -∆z + Az = v1 ω + F in Q T , z = 0 on Σ T , z(• , 0) = z 0 in Ω (21) satisfies z(• , T ) = 0 in Ω. ( 22
)
We follow the usual strategy of [START_REF] Fursikov | Controllability of evolution equations[END_REF] to construct a solution of the null controllability problem, using Carleman type estimates. Instead of using the classical estimates of [START_REF] Fursikov | Controllability of evolution equations[END_REF], we use the one in [START_REF] Badra | Local controllability to trajectories for non-homogeneous incompressible Navier-Stokes equations[END_REF] for which it is easier to deal with non zero initial data as the weight function does not blow up as t → 0. For any s ≥ 0, we consider the weight functions ρ s = ρ s (x, t), ρ 0,s = ρ 0,s (x, t) and ρ 1,s = ρ 1,s (x, t) which are continuous, strictly positive and belong to L ∞ (Q T -δ ) for any δ > 0. Precisely, we use the weights introduced in [4]:

(ρ 0,s , ρ 1,s , ρ 2,s , ρ 3,s ) = (ξ -3/2 , ξ -1 , ξ -1/2 , ξ 1/2 )ρ s where ρ s and ξ are defined, for all s ≥ 1 and λ ≥ 1, as follows:

ρ s (x, t) = e sϕ(x,t) , ξ(x, t) = θ(t)e λ ψ(x) , (23)
with θ ∈ C 2 ([0, T )) such that θ(0) = 1 and θ(t) = (T -t) -1 for all t ∈ [T -T 1 , T ] with 0 < T 1 < min( 1 4 , 3T 8 )
and ϕ ∈ C 1 ([0, T )) is defined by ϕ(x, t) = θ(t) λe 12λ -e λ ψ(x) with ψ = ψ + 6, where ψ ∈ C 1 (Ω) satisfies ψ ∈ (0, 1) in Ω, ψ = 0 on ∂Ω and |∇ ψ(x)| > 0 in Ω\ω. We emphasize that the weights blow up as t → T - but not at t = 0 and that ρ 0,s (x, t) = ξ -3/2 (x, t)ρ s (x, t) ≥ e 3/2s for all (x, t) ∈ Q T .

Carleman estimates

The controllability property for the linear system ( 21) is a consequence of the following Carleman estimate, written to simplify in the one dimensional case :

Lemma 1. [60, Lemma 2.1] Let P 0 := {q ∈ C 2 (Q T ) : q = 0 on Σ T }.
There exist λ 0 ≥ 1 and s 0 ≥ 1 such that for all λ ≥ λ 0 and for all s ≥ max(

A 2/3 L ∞ (Q T ) , s 0 ), the following Carleman estimate holds Ω ρ -2 s (0)|∂ x p(0)| 2 + s 2 λ 3 e 14λ Ω ρ -2 s (0)|p(0)| 2 + sλ 2 Q T ρ -2 2,s |∂ x p| 2 + s 3 λ 4 Q T ρ -2 0,s |p| 2 ≤ C Q T ρ -2 s | -∂ t p -∂ xx p + Ap| 2 + Cs 3 λ 4 q T ρ -2 0,s |p| 2 , ∀p ∈ P 0 . ( 24
)
This estimate is deduced from the one obtained in [4, Theorem 2.5] devoted to the case A ≡ 0. In the sequel we assume that λ = λ 0 . We then define and check that the bilinear form (p, q) P :=

Q T ρ -2 s L A p L A q + s 3 λ 4 0 q T ρ -2 0,s p q
where L A q := -∂ t q -∂ xx q + Aq for all q ∈ P 0 is a scalar product on P 0 (see [START_REF] Fernández | Strong convergent approximations of null controls for the 1D heat equation[END_REF]). The completion P of P 0 for the norm • P associated with this scalar product is a Hilbert space. By density arguments, [START_REF] Cîndea | Numerical controllability of the wave equation through primal methods and Carleman estimates[END_REF] remains true for all p ∈ P , that is, for

λ = λ 0 , Ω ρ -2 s (0)|∂ x p(0)| 2 + s 2 λ 3 0 e 14λ0 Ω ρ -2 s (0)|p(0)| 2 + sλ 2 0 Q T ρ -2 2,s |∂ x p| 2 + s 3 λ 4 0 Q T ρ -2 0,s |p| 2 ≤ C p 2 P ( 25
)
for all s ≥ max(

A 2/3 L ∞ (Q T )
, s 0 ). This inequality leads to the following result.

Lemma 2. [60, Lemma 2.2] Let s ≥ max( A 2/3 L ∞ (Q T ) , s 0 ).
There exists a unique solution p ∈ P of (p, q) P = Ω z 0 q(0)

+ Q T F q, ∀q ∈ P. ( 26
)
This solution satisfies the following estimate (with

c := ϕ(•, 0) L ∞ (Ω) ) p P ≤ Cs -3/2 ρ 0,s F L 2 (Q T ) + e cs z 0 L 2 (Ω) . (27)

Application to controllability

Following closely [START_REF] Fursikov | Controllability of evolution equations[END_REF], the previous lemma implies a controllability result for the linear system [START_REF] Cazenave | An introduction to semilinear evolution equations[END_REF].

Theorem 6. [60, Theorem 2.3] Assume A ∈ L ∞ (Q T ), s ≥ max( A 2/3 L ∞ (Q T ) , s 0 ), F ∈ L 2 (ρ 0,s , Q T ) and z 0 ∈ L 2 (Ω).
Let p the solution of [START_REF] Coron | Control and nonlinearity[END_REF]. Then, the pair (z, v) defined by

z = ρ -2 s L A p and v = -s 3 λ 4 0 ρ -2 0,s p| q T ( 28
)
is a controlled pair and satisfies the following estimates

ρ s z L 2 (Q T ) + s -3/2 λ -2 0 ρ 0,s v L 2 (q T ) ≤ Cs -3/2 ρ 0,s F L 2 (Q T ) + e cs z 0 L 2 (Ω) (29)
with c := ϕ(•, 0) L ∞ (Ω) .
We refer to [START_REF] Fernández | The cost of approximate controllability for heat equations: the linear case[END_REF] for an estimate of the null control of minimal L 2 (q T ) norm (corresponding to ρ 0 ≡ 1 and ρ = 0) in the case F ≡ 0. Thus, the resolution of ( 26) leads in practice to a control for the linear problem.

Moreover, following [START_REF] Fursikov | Controllability of evolution equations[END_REF], we check that the pair (z, v) defined in [START_REF] Deuflhard | Newton methods for nonlinear problems[END_REF] is the unique minimizer of the functional J defined as

J(z, v) := s 3 λ 4 0 2 Q T ρ 2 s |z| 2 + 1 2 q T ρ 2 0,s |v| 2 (30)
over the set (z, v) : 21)-( 22) in the transposition sense .

ρ s z ∈ L 2 (Q T ), ρ 0,s v ∈ L 2 (q T ), (z, v1 ω ) solves (
Before to discuss the numerical approximation of controls, we explain in the next section how we can construct, using the estimate of Theorem ( 6), convergence sequence of controlled pair in semilinear situation.

Controllability results for the semilinear heat equation

We now consider the null controllability problem for the following system for the semilinear heat equation:

∂ t y -∆y + f (y) = v1 ω in Q T y = 0 on Σ T , y(•, 0) = u 0 in Ω , (31)
with for all r ∈ R and some C > 0, the solutions to [START_REF] Ekeland | Convex analysis and variational problems[END_REF] are globally defined in [0, T ] and one has

u 0 ∈ L 2 (Ω), v ∈ L 2 (Q T )
y ∈ C 0 ([0, T ]; L 2 (Ω)) ∩ L 2 (0, T ; H 1 0 (Ω)). (32)
Without the above growth condition, the solutions to (31) can blow up before t = T ; in general, the blow-up time depends on f and the size of u 0 L 2 (Ω) . We refer to [START_REF] Lacey | Global blow-up of a nonlinear heat equation[END_REF] and to [42, Section 2 and Section 5] for a survey on this issue.

System ( 31) is said to be exactly controllable to trajectories at time T if, for any u 0 ∈ L 2 (Ω) and any globally defined bounded trajectory y ∈ C 0 ([0, T ]; L 2 (Ω)) (corresponding to data u 0 ∈ L 2 (Ω) and f ∈ L 2 (q T )), there exist controls f ∈ L 2 (q T ) and associated states y that are again globally defined in [0, T ] and satisfy [START_REF] Sylvain Ervedoza | Constructive exact control of semilinear heat equation[END_REF] and

y(x, T ) = y (x, T ), ∀x ∈ Ω. ( 33
)
As for the wave equation, the uniform controllability strongly depends on the growth properties of the nonlinear function f at infinity. The following has been proven by Fernández-Cara and Zuazua in [START_REF] Fernández | Null and approximate controllability for weakly blowing up semilinear heat equations[END_REF]:

Theorem 7.
[39, Theorem 1.2] Let T > 0 be given and d ≥ 1. Assume that (31) admits at least one solution y , globally defined in [0, T ] and bounded in

Q T . Assume that f : R → R is C 1 and satisfies |f (r)| ≤ C(1 + |r| 4+d ) for every r ∈ R. If (H 4 ) lim sup |r|→∞ |f (r)| |r| ln 3/2 |r| = 0, then (31)
is exactly controllable to y in time T .

Therefore, if |f (r)| does not grow at infinity faster than |r| ln p (1 + |r|) for some p < 3/2, then (31) is controllable. On the contrary, if f is too "super-linear" at infinity (specifically if p > 2), then for some initial data the control cannot compensate the blow-up phenomenon occurring in Ω\ω (see [START_REF] Fernández | Null and approximate controllability for weakly blowing up semilinear heat equations[END_REF]Theorem 1.1]). The problem remains open when f behaves at infinity like |r| ln p (1 + |r|) with 3/2 ≤ p ≤ 2. In [START_REF] Le Balc'h | Global null-controllability and nonnegative-controllability of slightly superlinear heat equations[END_REF],

Le Balc'h has proved the uniform controllability for p ≤ 2 assuming that T is large enough and imposing sign conditions on f , notably that f (r) > 0 for r > 0 or f (r) < 0 for r < 0 (a condition not satisfied for f (r) = -r ln p (1 + |r|)).

Theorem 7 is deduced in [START_REF] Fernández | Null and approximate controllability for weakly blowing up semilinear heat equations[END_REF] from a null controllability result corresponding to the null trajectory, i.e.

y ≡ 0 corresponding to v ≡ 0, u 0 ≡ 0 and assuming f (0) = 0. The proof is based on a fixed-point method, initially introduced in [START_REF] Zuazua | Exact controllability for semilinear wave equations in one space dimension[END_REF] for a one-dimensional wave equation. Precisely, a stability result is shown for the operator Λ :

L ∞ (Q T ) → L ∞ (Q T )
, where y := Λ(z) is a null controlled solution of the linear boundary value problem

∂ t y -∆y + y f (z) = v1 ω in Q T y = 0 on Σ T , y(• , 0) = u 0 in Ω , f (r)
:= f (r)/r r = 0 f (0) r = 0 . (34)
Then, Kakutani's Theorem provides the existence of at least one fixed-point for the operator Λ, which is also a controlled solution for [START_REF] Ekeland | Convex analysis and variational problems[END_REF]. The control of minimal L ∞ (q T ) norm is considered in [START_REF] Fernández | Null and approximate controllability for weakly blowing up semilinear heat equations[END_REF] leading to controlled solution in L ∞ (Q T ).

Construction of two sequences converging to a controlled pair for (31)

We now discuss how we can design sequences (y k , v k ) k∈I N converging to a controlled pair for [START_REF] Ekeland | Convex analysis and variational problems[END_REF]. The motivation, difficulties and ideas are very similar to the ones explained in Section 2.3 dedicated to the wave equation. The arguments for the heat equation are however a bit more technical since singular Carleman weights appear in the various estimates.

As for the wave equation, one may consider for any initial guess in L ∞ (Q T ) the Picard iterates associated with the operator Λ. Numerical experiments reported in [START_REF] Fernández | Numerical null controllability of semi-linear 1-D heat equations: fixed point, least squares and Newton methods[END_REF]Section 4] exhibit the non convergence of the sequence (y k ) k∈N for some initial conditions large enough, related to the fact that the operator Λ is not contracting.

In the one-dimensional case, a least-squares type approach, based on the minimization over

Z := L 2 ((T - t) -1 , Q T ) = {z : (T -t) -1 z ∈ L 2 (Q T )} of the functional R : Z → R + defined by R(z) := z -Λ(z) 2 Z
has been introduced in [START_REF] Fernández | Numerical null controllability of semi-linear 1-D heat equations: fixed point, least squares and Newton methods[END_REF]. Assuming u 0 ∈ L ∞ (Ω), f ∈ C 1 (R) and ( f ) ∈ L ∞ (R), it is proved (see [START_REF] Fernández | Numerical null controllability of semi-linear 1-D heat equations: fixed point, least squares and Newton methods[END_REF]Proposition 3.2]) that R ∈ C 1 (Z; R + ) and that, for some constant C > 0

1 -C ( f ) L ∞ (R) u 0 L ∞ (Ω) R(z) ≤ R (z) L 2 (Q T ) ∀z ∈ Z implying that if ( f ) L ∞ (R) u 0 L ∞ (Ω)
is small enough, then any critical point for R is a fixed point for Λ (see [START_REF] Fernández | Numerical null controllability of semi-linear 1-D heat equations: fixed point, least squares and Newton methods[END_REF]Proposition 3.2]). In particular, taking u 0 small in L ∞ makes of no relevance the behavior of f at infinity, as it enters in the framework of local controllability results. Under such smallness assumption on the data, numerical experiments (see [START_REF] Fernández | Numerical null controllability of semi-linear 1-D heat equations: fixed point, least squares and Newton methods[END_REF]Section 4]) display the convergence of gradient based minimizing sequences for R and a better behavior than the ones associated with the Picard iterates for Λ.

Similarly, we can employ a Newton type method to find a zero of the mapping F : Y → W defined by

F(y, v) = (∂ t y -∆y + f (y) -v1 ω , y(• , 0) -u 0 ) ∀(y, v) ∈ Y, (35)
where the Hilbert space Y and W are defined as follows

Y := (y, v) : ρ s y ∈ L 2 (Q T ), ρ 0,s (∂ t y -∆y) ∈ L 2 (Q T ), y = 0 on Σ T , ρ 0,s v ∈ L 2 (q T )
and W := L 2 (ρ 0,s , Q T ) × L 2 (Ω) for some appropriates weights. Here, L 2 (ρ 0,s , Q T ) stands for the space

{z : ρ 0,s z ∈ L 2 (Q T )}. It is shown in [35, Section 3.3] that, if f ∈ C 1 (R) and f ∈ L ∞ (R), then F ∈ C 1 (Y ; W ).
This enables to derive the Newton iterative sequence. Starting from (y 0 , v 0 ) in Y , we set, for each k ≥ 0,

(y k+1 , v k+1 ) = (y k , v k ) -(Y k , V k )
, where V k is a null control for the system

∂ t Y k -∆Y k + f (y k ) Y k = V k 1 ω + ∂ t y k -∆y k + f (y k ) -v k 1 ω in Q T , Y k = 0 on Σ T , Y k (• , 0) = u 0 -y k (• , 0) in Ω (36)
and Y k (•, T ) = -y k (•, T ). Numerical experiments in [START_REF] Fernández | Numerical null controllability of semi-linear 1-D heat equations: fixed point, least squares and Newton methods[END_REF]Section 4] exhibit however the lack of convergence of the Newton method for large values of u 0 L 2 (Ω) .

A least-squares approach related to a Newton type linearization

Let us introduce, for each s ≥ s 0 , the vector space

A 0,s :={(y, v) : ρ s y ∈ L 2 (Q T ), ρ 0,s v ∈ L 2 (q T ), ρ 0,s (∂ t y -∆y) ∈ L 2 (Q T ), y(• , 0) = 0 in Ω, y = 0 on Σ T },
where ρ s , ρ 1,s and ρ 0,s are defined in [START_REF] Ciarlet | Interpolation error estimates for the reduced Hsieh-Clough-Tocher triangle[END_REF]. Endowed with the scalar product

(y, v), (y, v) A0,s := ρ s y, ρ s y L 2 (Q T ) + ρ 0,s v, ρ 0,s v L 2 (q T ) + ρ 0,s (∂ t y -∆y), ρ 0,s (∂ t y -∆y) L 2 (Q T ) ,
A 0,s is a Hilbert space. Let us also consider the linear manifold

A s := {(y, v) : ρ s y ∈ L 2 (Q T ), ρ 0,s v ∈ L 2 (q T ), ρ 0,s (∂ t y -∆y) ∈ L 2 (Q T ), y(• , 0) = u 0 in Ω, y = 0 on Σ T }.
We endow A s with the same scalar product. If (y, v) ∈ A s , then y ∈ C 0 ([0, T ]; L 2 (Ω)). Moreover, the property ρ s y ∈ L 2 (Q T ) implies that y(• , T ) = 0 so that the null controllability requirement is incorporated in the spaces A 0,s and A s . For any fixed s ≥ 0, we consider the following non-convex extremal problem:

inf (y,v)∈A0,s E s (y, v), E s (y, v) := 1 2 ρ 0,s ∂ t y -∆y + f (y) -v 1 ω 2 L 2 (Q T ) . (37)
We check that ρ 0,s f (y) ∈ L 2 (Q T ) for any (y, f ) ∈ A s , so that E s is well-defined. Assuming slightly stronger assumption on f than in Theorem 7, a strong convergent approximation of a controlled pair is obtained:

Theorem 8. [60, Theorem 4.3] Let T > 0 be given. Let d = 1. Assume that (31) admits at least one solution y , globally defined in [0, T ] and bounded in Q T associated with v ∈ L 2 (ρ 0,s , q T ) and s large enough. Assume that f ∈ C 1 (R) satisfies (H p ) from some p ∈ [0, 1] (introduced in page 5) and the growth condition

(H 1 ) ∃α > 0, s.t. |f (r)| ≤ (α + β ln(1 + |r|)) 3/2 , ∀r ∈ R
for some β = β (y ) > 0 small enough. Then, for any u 0 ∈ H 1 0 (Ω) and any starting (y 0 , v 0 ) ∈ A s , the sequence (y k , v k ) k∈N ∈ A s defined as follows:

(y 0 , v 0 ) ∈ A s , (y k+1 , v k+1 ) = (y k , v k ) -λ k (Y 1 k , V 1 k ), k ≥ 0, λ k = argmin λ∈[0,1] E s (y k , v k ) -λ(Y 1 k , V 1 k ) , (38)
where (Y 1 k , F 1 k ) ∈ A 0,s is the minimal controlled pair solution (with respect to the cost J, see (30) ) of

∂ t Y 1 k -∆Y 1 k + f (y k )Y 1 k = V 1 k 1 ω + ∂ t y k -∆y k + f (y k ) -v k 1 ω in Q T , Y 1 k = 0 on Σ T , Y 1 k (• , 0) = 0 in Ω, (39)
converges strongly to a controlled pair for (31) satisfying [START_REF] Ervedoza | A systematic method for building smooth controls for smooth data[END_REF]. Moreover, after a finite number of iterations, the convergence is of order at least 1 + p.

The hypothesis on f are stronger here than in Theorem 7: it should be noted however that the function f (r) = a + br + βr ln(1 + |r|) 3/2 , a, b ∈ R which is somehow the limit case in (H 4 ) satisfies (H 1 ) and (H 1 ).

On the other hand, Theorem 8 devoted to the one dimensional case is constructive, contrary to Theorem 7.

A similar construction is performed in a multi-dimensional case with d ≤ 3 in [START_REF] Lemoine | Approximation of null controls for semilinear heat equations using a least-squares approach[END_REF] assuming that f is globally Lipschitz. The minimizing sequence for E s constructed in [START_REF] Lemoine | Approximation of null controls for semilinear heat equations using a least-squares approach[END_REF][START_REF] Lemoine | Constructive exact control of semilinear 1d heat equation[END_REF] are related to the operator Λ N : A → A defined by y = Λ N (z) controlled solution of

∂ t y -∆y + f (z)y = v1 ω + f (z)z -f (z) in Q T y = 0 on Σ T , y(•, 0) = u 0 in Ω , (40)
through the control v of minimal L 2 (ρ 0 (s), q T ) norm. The analysis in [START_REF] Lemoine | Constructive exact control of semilinear 1d heat equation[END_REF] makes use of global L 2 Carleman estimates as initially introduced in this context in [START_REF] Fursikov | Controllability of evolution equations[END_REF]. The arguments used in the proof take their roots in the works [START_REF] Lemoine | A fully space-time least-squares method for the unsteady Navier-Stokes system[END_REF][START_REF] Lemoine | Resolution of the implicit Euler scheme for the Navier-Stokes equation through a least-squares method[END_REF], concerned with the approximation of the solution to Navier-Stokes-like problems through least-square methods; see also [START_REF] Lemoine | Analysis of continuous H -1 -least-squares approaches for the steady Navier-Stokes system[END_REF][START_REF] Münch | A least-squares formulation for the approximation of controls for the Stokes system[END_REF], inspired in the seminal contribution [START_REF] Bristeau | On the numerical solution of nonlinear problems in fluid dynamics by least squares and finite element methods. I. Least square formulations and conjugate gradient[END_REF].

We also emphasize that the L 2 (Q T ) norm in E s indicates that we are looking for regular weak solutions to the parabolic equation [START_REF] Ekeland | Convex analysis and variational problems[END_REF]. We refer to [START_REF] Lemoine | Approximation of null controls for semilinear heat equations using a least-squares approach[END_REF], devoted to the case f ∈ L ∞ (R) and d ≤ 3, where the L 2 (0, T ; H -1 (Ω)) norm is considered leading to weaker solutions.

The analysis in [START_REF] Lemoine | Constructive exact control of semilinear 1d heat equation[END_REF] indicates that the parameter s plays a crucial role: a large value of this parameter ensures convergence properties. This is the also the case in the following section where a different method based on a simpler linearization is discussed.

Influence of the parameter s on a simpler linearization

The following extension is proved in [START_REF] Sylvain Ervedoza | Constructive exact control of semilinear heat equation[END_REF] based on simpler linearization.

Theorem 9. [32, Theorem 8] Let T > 0 be given. Let d ≤ 5 and u 0 ∈ L ∞ (Ω). Assume that f is locally Lipschitz-continuous and satisfies (H 1 ) for β small enough. There exist s and R large enough such that, for any

y 0 ∈ C R (s) := {y ∈ L ∞ (Q T ) : y L ∞ (Q T ) ≤ R, ρ 0,s y L 2 (Q T ) ≤ R 1/2 }, the sequence (y k ) k∈N given by ∂ t y k -∆y k = v k 1 ω -f (y k-1 ) in Q T , y k = 0 on Σ T , y k (• , 0) = u 0 in Ω, (41)
where v k ∈ L 2 (ρ 0,s , q T ) is such that (y k , v k ) minimizes J (see [START_REF] Dumont | 4D remeshing using a space-time finite element method for elastodynamics problems[END_REF]), remain in C R (s) and converge strongly to a controlled solution for [START_REF] Ekeland | Convex analysis and variational problems[END_REF].

To prove this result, we proceed as follows:

• First, we introduce, for each y ∈ L 2 (ρ 0,s , Q T ) ∩ L ∞ (Q T ), the following corresponding linear null controllability problem: find v such that the solution to

∂ t y -∆y = v1 ω -f ( y), in Q T , y = 0, on Σ T , y(• , 0) = u 0 , in Ω (42)
satisfies y(• , T ) = 0.

• Then, we consider the mapping Λ s that associates to each y the solution to [START_REF] Victor | The problem of blow-up in nonlinear parabolic equations[END_REF] with the control v1 ω furnished by Theorem 6 (for A ≡ 0 and F = -f ( y)) and prove that for s large enough, the operator Λ s is a contraction.

Numerical approximation of exact controls for the heat equation

Approximations of null controls for the linear heat equation is a delicate issue: we mention the seminal work [START_REF] Carthel | On exact and approximate boundary controllabilities for the heat equation: a numerical approach[END_REF] dealing with the control of minimal L 2 -norm which is very oscillatory near the final time t = T and therefore difficult to construct and implement for real life applications (see also [START_REF] Labbé | Uniform controllability of semidiscrete approximations of parabolic control systems[END_REF][START_REF] Münch | Numerical approximation of null controls for the heat equation: illposedness and remedies[END_REF] where this is discussed at length). On the other hand, as discussed in [START_REF] Fernández | Strong convergent approximations of null controls for the 1D heat equation[END_REF][START_REF] Fernández | Numerical exact controllability of the 1D heat equation: duality and Carleman weights[END_REF], introduction of Carleman weights in the cost functional J leads -within the control-then-discretize strategy -to a robust method and strong convergent approximations with respect to the discretization parameter. Precisely, in view of Theorem 6, one have to approximate the solution p ∈ P of the second order in time and fourth order in space variational formulation [START_REF] Coron | Control and nonlinearity[END_REF]. A conformal parametrized approximation, say P h of P , leads to the finite dimensional problem : find

p h ∈ P h solution of (p h , p h ) P = Q T F p h + Ω u 0 p h (0) ∀p h ∈ P h . (43)
If the family (P h ) h>0 is dense in P , Cea type lemma implies the convergence p h -p P → 0 as h → 0. From p h , an approximation of the controlled state is then given by (y h , v h ) := (ρ -2 s L p h , -s 3 ρ -2 0,s p h 1 ω ). In order to solve [START_REF] Glowinski | A mixed finite element formulation for the boundary controllability of the wave equation[END_REF], it is very convenient to preliminary perform the change of variable m = ρ -1 0,s p, z = ρ -1 s L p so that z = ρ -1 s L (ρ 0,s m) and y = ρ -1 s z and then replace the formulation (43) by the equivalent and well-posed following mixed formulation: find (z, m, η)

∈ L 2 (Q T ) × ρ -1 0,s P × L 2 (Q T ) solution of                  Q T zz + s 3 q T m m + Q T (T -t) 1/2 η z -ρ -1 s L (ρ 0,s m) = - Q T ρ 0,s F m + Ω ρ 0,s (0)u 0 m(0), ∀(m, z) ∈ ρ -1 s P × L 2 (Q T ), Q T (T -t) 1/2 η z -ρ -1 s L (ρ 0,s m) = 0, ∀η ∈ L 2 (Q T ). (44)
η k stands as a Lagrange multiplier for the constraint z

-ρ -1 s L (ρ 0,s m) = 0 in Q T . For every m ∈ ρ -1 s P , we check that -ρ -1 s L (ρ 0,s m) = (g 1 (θ, ϕ) + g 2 (θ, ϕ))m + θ -3/2 (∂ t m + ∆m) + g 3 (θ, ϕ) • ∇m with g 1 (θ, ϕ) := ρ -1 s ∂ t ρ 0,s = ∂ t (θ -3/2 ) + θ -3/2 s(∂ t ϕ), g 2 (θ, ϕ) := θ -3/2 (s∆ϕ + s 2 (∇ϕ) 2 ), g 3 (θ, ϕ) := ρ -1 s ∇ρ 0,s = θ -3/2 s∇ϕ.
We observe that g 2 is singular like (T -t) -1/2 for t ≥ T -T 1 and therefore introduce the function (T -t) 1/2 in (44). The equivalent formulation (44) instead of (43) allows, first to eliminate the exponential singularity of the coefficients for t close to T and second to obtain simultaneously the control and the controlled solution. We refer to [START_REF] Fernández | Strong convergent approximations of null controls for the 1D heat equation[END_REF][START_REF] Fernández | Numerical exact controllability of the 1D heat equation: duality and Carleman weights[END_REF] where experiments are discussed in detail and emphasize the robustness of the approximation. We also refer to [START_REF] Münch | A mixed formulation for the direct approximation of L 2 -weighted controls for the linear heat equation[END_REF] for some numerical evidences of the robustness of the method with respect to the parameter h associated with the cost J(v) = ρ 0,s v 2 L 2 (q T ) .

Numerical illustrations

We illustrate the convergence stated in Theorem 9 by computing the sequence (y k , v k ) k∈I N solution of (41) and minimizing for each k the functional J s defined in [START_REF] Dumont | 4D remeshing using a space-time finite element method for elastodynamics problems[END_REF] with s large enough. We consider the one dimensional setting with Ω = (0, 1). We take T = 1/2 and consider data for which the uncontrolled solution of (31) blows up before T . Moreover, in order to reduce the decay of the solution of (31) when f ≡ 0, we replace the term -∆y in (31) by -ν∆y with ν = 10 -1 . We consider the nonlinear even function f (r) = c f α + β ln(1 + |r|) 3/2 r with α = β = 1 and c f < 0. As for the initial condition to be controlled, we consider u 0 (x) = c u0 sin(πx) parametrized by c u0 > 0. We use a mesh composed of 29132 vertices and 14807 triangles corresponding to h ≈ 1.17 × 10 -2 . The sequence (y k , v k ) k∈N is initialized with the state-control pair (y 0 , v 0 ) corresponding to the controlled trajectory of the linear heat equation with initial datum u 0 and zero source term) and is computed until the following criterion is satisfied with respect to the parameter of iteration k for s ∈ {1, 2, 3, 4}. In agreement with the theoretical results, the convergence is observed for s large enough, here s ≥ 2. Moreover, the rate increases with s: the convergence is observed after k iterations equal to 48, 17, 13 for s = 2, 3 and 4 respectively. highlighting the lack of contracting property of Λ s for s = 1. Figure 8 depicts the evolution of the L 2 (Ω) norm of the control and corresponding controlled solution with respect to the time variable for s = 2, 3, 4. In view of the behavior of the weights, large values of s concentrate the action of the control close to the initial time and leads to large L ∞ (q T ) norm of the control (see Table 2). Figure 9 and Figure 10 depict the control and corresponding controlled solution in Q T for these values of s. Table 3 provides some norms of the solution for s = 3 with respect to the fineness h of the triangular mesh used and highlights the stability of the approximation. The large degree equal to 3 of the approximation space induced by the composite finite element HCT makes the convergence fast with respect to h. We also observe that the number of iterations to reach the convergence of the sequence (y k ) k≥0 is independent of h.

s y k L 2 (Q T ) ρ s y k L 2 (Q T ) v k L 2 (q T ) ρ 0,s v k L 2 (q T ) v k L ∞ (q T ) k 2
h y k L 2 (Q T ) ρ s y k L 2 (Q T ) v k L 2 (q T ) ρ 0,s v k L 2 (q T ) v k L ∞ (q T ) k 0.

Perspectives

Within the approach control-then-discretize strategy, we have emphasized, both for the wave and heat equation, the ability of variational space-time formulations to get robust finite dimensional approximation of exact controls. The space-time framework makes easier both the numerical analysis and the numerical implementation than classical methods within the approach discretize-then-control. Moreover, it is very appropriate for (space-time) mesh adaptivity, allowing a notable reduction of the computational cost. Then, we have defined strongly convergent sequences to control-state pairs for semilinear wave and heat equation.

In both cases, the convergence is ensured assuming an asymptotic growth condition on the first derivative of the nonlinear function. Numerical experiments, within the space-time methods introduced in the first part, confirm the theoretical results. In both parts, the main tool is a parametrized global Carleman inequality allowing precise estimates of the state-control pair in term of the data. As emphasized for the heat equation in sections 3.3.1 and 3.3.2 an appropriate choice of the Carleman parameters guarantees contracting properties for some fixed point application. This is also true for wave type equations; we refer to the recent work [START_REF] Bhandari | Exact boundary controllability of 1d semilinear wave equation through a constructive approach[END_REF] where a constructive convergent sequence to boundary controls for semilinear wave equation is designed.

Actually, since global Carleman inequalities are now available for many equations and systems, the methods presented here can very likely be extended to other situations involving notably nonlinearity with gradient terms and arising in fluid and solid mechanics. We mention the Burgers equation and the Navier-Stokes equation in incompressible regime which are now under investigation.

Theorem 2 .

 2 [62, Theorem 2.1] Let x 0 , Γ 0 and O (Γ 0 ) be as in Theorem 1. Assume that (H 0 ) holds. If f satisfies (H 1 ) lim sup |r|→∞ |f (r)| |r| ln 1/2 |r| = 0, then (5) is exactly controllable in time T . Theorem 2 extends to the multi-dimensional case the result of [79] devoted to the one-dimensional case under the condition lim sup |r|→∞ |f (r)|

Proposition 3 .

 3 [START_REF] Bottois | Constructive exact control of semilinear multi-dimensional wave equations[END_REF] Proposition 3] Assume (H 0 ) and let d ≤ 3. There exists C = C(ω, Ω, T ) > 0 such that

Theorem 4 .

 4 [START_REF] Castro | Controllability of the linear one-dimensional wave equation with inner moving forces[END_REF] Theorem 3.1] Assume (H 0 ) and let r ≥ 0.

  dimensional level): (i) The coercivity of the bilinear form a over the kernel Ker (b) = {φ ∈ Φ, b(λ, φ) = 0 ∀λ ∈ M} of b and (ii) The inf-sup property for b:

1 T e - 1 T 1 51

 111 controlled and adjoint solutions. The distributed control acts in ω×(0, T ) with ω = (a, b) = (0.1, 0.4) and T = 2. Precisely, the cut off functions are defined as χ 0 (t) = e -and χ 1 (x) = e -[a,b] (x).

Figure 1 -

 1 Figure 1-left depicts the evolution of the relative error χ(φ -φ h ) L 2 (Q T ) / χφ L 2 (Q T ) associated with T = 2

Figure 1 :

 1 Figure 1:χ(φ -φ h ) L 2 (Q T ) / χφ L 2 (Q T )vs. h with (left) and without (right) regularization of the control support q T .

Figure 2 :

 2 Figure 2: ∂ x φ h (1, •) -v L 2 (0,T ) / v L 2 (0,T ) with respect to h for different approximations.Figure 3: Control domain ω ⊂ Ω = (0, 1) 2 .

Figure 3 :Figure 4 :

 34 Figure 2: ∂ x φ h (1, •) -v L 2 (0,T ) / v L 2 (0,T ) with respect to h for different approximations.Figure 3: Control domain ω ⊂ Ω = (0, 1) 2 .

  and f : R → R. Recall that if f is locally Lipschitz-continuous and satisfies the condition |f (r)| ≤ C(1+|r| 4+d ) for all r ∈ R, then (31) possesses exactly one local in time solution. Moreover, in accordance with the results in [21, Section 5], under the growth condition |f (r)| ≤ C(1 + |r| ln(1 + |r|))

  ρ0,s(y k+1 -y k ) L 2 (Q T ) ρ0,sy k L 2 (Q T )≤ 10 -6 . We shall denote by k the lowest integer k for which it holds true.For ω = (0.2, 0.8), c u0 = 10 and c f = -5, Figure7-left depicts the evolution of the relative error ρ0,s(y k+1 -y k ) L 2 (Q T ) ρ0,sy k L 2 (Q T )

Figure 7 -

 7 Figure 7-right depicts the ratio ρ0,s(Λs(yk )-Λs(y k-1 )) L 2 (Q T ) ρ0,s(y k -y k ) L 2 (Q T )

Figure 7 :

 7 Figure 7:ρ0,s(y k+1 -y k ) L 2 (Q T ) ρ0,sy k L 2 (Q T )

Figure 8 :

 8 Figure 8: v k (•, t) L 2 (Ω) and y k (•, t) L 2 (Ω) w.r.t. t ∈ [0, T ] for c u0 = 10, c f = -5 and s ∈ {2, 3, 4}.

Figure 9 :

 9 Figure 9: The control v k in Q T for c u0 = 10, c f = -5 and s ∈ {2, 3, 4}.

Figure 10 :

 10 Figure 10: The controlled solution y k in Q T for c u0 = 10, c f = -5 and s ∈ {2, 3, 4}.

  There exists α ≥ 0 and β ∈ [0, β (p)) such that |f (r)| ≤ α + β ln 1/2 (1 + |r|) for every r in R.

	Theorem 3. [9, Theorem 2] Assume (H 0 ) and let d ≤ 3. Also, assume that f satisfies (H p ) for some
	p ∈ (0, 1] and
	(H 2 )
		b| p	< +∞
	and set β (p) :=	p 2C(2p+1) where C > 0 (only depending on Ω and T ) is the constant appearing in
	Proposition 2. The following result from [9] provides a constructive way to approximate a control for the
	semilinear wave equation (5).

Table

		44 × 10 2	-	-	38.116	732.22	1
	1	1.63 × 10 2	1.79 × 10 0	9.30 × 10 -1	58.691	667.602	1
	2	1.62 × 10 0	8.42 × 10 -2	1.41 × 10 -1	60.781	642.643	1
	3	1.97 × 10 -3	1.21 × 10 -3	4.66 × 10 -3	60.745	643.784	1
	4	5.11 × 10 -10	6.43 × 10 -7	2.63 × 10 -6	60.745	643.785	-

Table 2 :

 2 c u0 = 10 ; c f = -5; Norms of (y k , v k ) w.r.t. s.

		2.43	80.50	58.24	208.52	297.56	48
	3	1.415	86.53	51.30	463.69	414.93	17
	4	1.108	173.17	52.83	1366.08	605.20	13
	5	0.931	429.07	57.04	4328.61	889.05	11

Table 3 :

 3

	1562	1.47841	90.9285	51.4646	469.008	420.345	18
	0.0760	1.46148	87.9869	51.2379	465.822	419.42	17
	0.0441	1.45521	87.0578	51.0243	464.527	416.886	17
	0.0208	1.45056	86.2678	51.0448	463.253	414.223	17
	0.0117	1.45203	86.5628	51.1068	463.723	415.114	17

c u0 = 10 ; c f = -5 ; s = 3; Norms of (y k , v k ) w.r.t. h.


Majid Zohrehbandian
email: zohrebandian@yahoo.com

New insight into introducing a -approximation ratio for minimum vertex cover problem

Keywords: Discrete Optimization, Vertex Cover Problem, Complexity Theory, NP-Complete Problems. MSC 2010: 90C35, 90C60

Vertex cover problem is a famous combinatorial problem, which its complexity has been heavily studied over the years and we know that there is not any mathematical formulation that approximates it better than 2 -𝑜(1). In other words, it is known that it is hard to approximate to within any constant factor better than 2, while a 2-approximation for it can be trivially obtained. In this paper, by a combination of a well-known semidefinite programming formulation and a rounding procedure, along with satisfying new properties, we introduce an approximation algorithm for the vertex cover problem with a performance ratio of 1.999999 on arbitrary graphs, en route answering an open question about the unique games conjecture.

Introduction

In complexity theory, the abbreviation 𝑁𝑃 refers to "nondeterministic polynomial", where a problem is in 𝑁𝑃 if we can quickly (in polynomial time) test whether a solution is correct. 𝑃 and 𝑁𝑃-complete problems are subsets of 𝑁𝑃 Problems. We can solve 𝑃 problems in polynomial time while determining whether or not it is possible to solve 𝑁𝑃-complete problems quickly (called the 𝑃 vs 𝑁𝑃 problem) is one of the principal unsolved problems in Mathematics and Computer science.

Here, we consider the vertex cover problem which is a famous 𝑁𝑃-complete problem. It cannot be approximated within a factor of 1.36 [START_REF] Dinur | On the hardness of approximating minimum vertex cover[END_REF], unless 𝑃 = 𝑁𝑃, while a 2-approximation factor for it can be trivially obtained by taking all the vertices of a maximal matching in the graph. However, improving this simple 2-approximation algorithm has been a quite hard task [START_REF] Khot | On the power of unique 2-Prover 1-Round games[END_REF][START_REF] Khot | Vertex cover might be hard to approximate to within 2-ℇ[END_REF].

In this paper, we show that there is a (2 -ℇ)-approximation ratio for the vertex cover problem, based on any feasible solution of it. Then, we fix the ℇ value equal to ℇ = 0.000001 and we show that on arbitrary graphs a 1.999999-approximation ratio can be obtained by a combination of a well-known semidefinite programming (SDP) formulation and a rounding procedure.

The rest of the paper is structured as follows. Section 2 is about the vertex cover problem and introduces new properties about it. In section 3, we propose a rounding procedure along with using the satisfying properties to propose an algorithm with a performance ratio of 1.999999 on arbitrary graphs.

Finally, Section 4 concludes the paper.

Performance ratio for a feasible solution of vertex cover problem

In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. The problem of finding a minimum vertex cover is a typical example of an 𝑁𝑃-complete optimization problem. In this section, we calculate the performance ratios of vertex cover feasible solutions which lead to an approximation ratio of 2 -ℇ, where the value of ℇ is not constant and depends on the produced feasible solution. Then, in the next section, we fix the value of ℇ equal to ℇ = 0.000001 to produce a 1.999999-approximation ratio for the vertex cover problem on arbitrary graphs.

Let 𝐺 = (𝑉, 𝐸) be an undirected graph on vertex set 𝑉 and edge set 𝐸, where |𝑉| = 𝑛. Throughout this paper, suppose that the vertex cover problem on 𝐺 is hard and we have produced an arbitrary feasible solution for the problem, with vertex partitioning 𝑉 = 𝑉 ∪ 𝑉 (𝑉 is a vertex cover solution of the graph 𝐺) and objective value |𝑉 |, and for solving the problem, we use the well-known semidefinite programming (SDP) formulation as follows:

(

. 𝑧 = 1 + 𝑣 𝑣 2 ∈ +𝑣 𝑣 + 𝑣 𝑣 -𝑣 𝑣 = 1 𝑖𝑗 ∈ 𝐸 +𝑣 𝑣 + 𝑣 𝑣 + 𝑣 𝑣 ≥ -1 𝑖, 𝑗, 𝑘 ∈ 𝑉 ∪ {𝑜} +𝑣 𝑣 -𝑣 𝑣 -𝑣 𝑣 ≥ -1 𝑖, 𝑗, 𝑘 ∈ 𝑉 ∪ {𝑜} -𝑣 𝑣 + 𝑣 𝑣 -𝑣 𝑣 ≥ -1 𝑖, 𝑗, 𝑘 ∈ 𝑉 ∪ {𝑜} -𝑣 𝑣 -𝑣 𝑣 + 𝑣 𝑣 ≥ -1 𝑖, 𝑗, 𝑘 ∈ 𝑉 ∪ {𝑜} 𝑣 𝑣 = 1 𝑖 ∈ 𝑉 ∪ {𝑜} 𝑣 𝑣 ∈ {-1, +1} 𝑖, 𝑗 ∈ 𝑉 ∪ {𝑜} 1) min .
Note that, we know for sure that just by solving this SDP formulation or the other SDP formulations with additional constraints, we cannot approximate the vertex cover problem with a performance ratio better than 2 -𝑜(1). In other words, in section 3, we are going to propose a randomized algorithm to classify the solution vectors of the SDP (1) relaxation to produce a suitable solution for the vertex cover problem with a performance ratio of 1.999999.

Theorem 1. Suppose that in SDP formulation [START_REF] Dinur | On the hardness of approximating minimum vertex cover[END_REF] we have 𝑧 * ≥ + = ( ) . Then, for all vertex cover feasible solutions, = 𝑉 ∪ 𝑉 , we have the approximation ratio

A (𝟏. 𝟗𝟗𝟗𝟗𝟗𝟗)-approximation algorithm for the vertex cover problem

In section 2 and based on the produced feasible solution, we could introduce a (2 -𝜀)-approximation ratio where ℇ value was not a constant value. In this section, we fix the value of ℇ equal to ℇ = 0.000001 to produce a 1.999999-approximation ratio for the vertex cover problem on arbitrary graphs. To do this, we assume the following assumption about the solution of the SDP (1) relaxation. Note that, the induced subgraph on G is a triangle-free graph and we know that almost all trianglefree graphs are bipartite. However, if the solution of the SDP (1) relaxation meets the Assumption (1), it is necessary to introduce a suitable feasible solution based on G to produce a performance ratio of 1.999999. In other words, to produce a performance ratio of 1.999999, we should solve the SDP (1) relaxation.

Then, if the solution of the SDP (1) relaxation does not meet the Assumption (1), we have a performance ratio of 1.999999 and if the solution of the SDP (1) relaxation meets the Assumption (1), it is sufficient to produce a normalized random vector 𝑤, where |𝐻 | ≥ .

Theorem 4. Let 𝑢, 𝑤 be two normalized random vectors, then for any normalized vector 𝑣 * , we have Pr 𝑢𝑣 * ≤ 0.5003 & 𝑤𝑣 * ≤ 0.5003 < 0.60933.

Proof. Let 𝑣 * = 𝑣 + 𝑣 , where 𝑣 is the projection of vector 𝑣 * onto the 𝑢 -𝑤 plane (suppose that the vector 𝑢 is on the 𝑜𝑥 axis) and 𝑣 is the projection of 𝑣 * onto the normal vector of that plane. Then, (0 ≤ 𝜃 ≤ cos (0.5003)), and the gray region is symmetric concerning the ox axis, the oy axis, and the origin.

Note that, the maximum area of the region 𝑆, where 𝑆 is the area of the common gray region between two vectors 𝑢 and 𝑤, is produced based on the |𝑢𝑤| ≅ 1 condition (and the minimum value is produced when |𝑢𝑤| ≅ 0). Now, we can introduce our algorithm to produce an approximation ratio 𝜌 ≤ 1.999999.

Zohrehbandian Algorithm (To produce a vertex cover solution with a factor 𝝆 ≤ 𝟏. 𝟗𝟗𝟗𝟗𝟗𝟗)

Step 1. Solve the SDP (1) relaxation.

Step

Assumption 1 .Definition 1 .

 11 By solving the SDP (1) relaxation, a) For less than 𝑛 of vertices 𝑗 ∈ 𝑉 and corresponding vectors we have 𝑣 * 𝑣 * < 0. Otherwise, we can produce 𝑉 = 𝑗 ∈ 𝑉 𝑣 * 𝑣 * < 0 and 𝑉 = 𝑉 -𝑉 , to have a feasible solution with |𝑉 | ≥ 𝑛 and |𝑉 | ≤ 𝑛 ≤ 999999|𝑉 |. Then, based on Theorem (2) we have an approximation ratio less than 𝑛 of vertices 𝑗 ∈ 𝑉 and corresponding vectors we have 𝑣 * 𝑣 * > 0.0004. Otherwise, 𝑧 * ≥ ( ) × Then, based on Theorem (1) and for all feasible solutions 𝑉 = 𝑉 ∪ 𝑉 , we have the Let ε = 0.0004 and G = 𝑗 ∈ V 0 ≤ 𝑣 * 𝑣 * ≤ +ε . Based on Assumption (1), after solving the SDP (1) relaxation, we have a performance ratio of 𝑚𝑎𝑥{1.999994, 1.999998} < 1.999999 (if the solution of the SDP (1) relaxation does not meet the Assumption (1)) or for more than 𝑛 of vertices j ∈ V and corresponding vectors we have 0 ≤ 𝑣 * 𝑣 * ≤ +ε; i.e. |G | ≥ 0.989999n (if the solution of the SDP (1) relaxation meets the Assumption (1)).

Theorem 3 .Corollary 1 .

 31 For any normalized vector 𝑤, the induced subgraph on 𝐻 = 𝑗 ∈ 𝐺 ; 𝑤𝑣 * > 0.5003 is a bipartite graph. Proof. Let us divide the vertex set 𝐻 as follows: 𝑆 = 𝑗 ∈ 𝐻 𝑤𝑣 * < -0.5003 and 𝑇 = 𝑗 ∈ 𝐻 𝑤𝑣 * > +0.5003 Then, it is sufficient to show that the sets 𝑆 and 𝑇 are null subgraphs. For each edge 𝑖𝑗 ∈ 𝐸(𝐺) and based on the first constraint of the SDP model (1), if 𝑖, 𝑗 ∈ 𝐻 ⊆ 𝐺 then we have 𝑣 * 𝑣 * ≤ -1 + 2𝜀. + 𝑣 𝑣 * * + 𝑣 𝑣 * * -𝑣 𝑣 = 1 𝑖𝑗 ∈ 𝐸, 𝑖, 𝑗 ∈ 𝐻 ⊆ 𝐺 Moreover, the triangle inequality could not be violated between vectors 𝑣 * -𝑣 * , 𝑤 -𝑣 * and 𝑤 -𝑣 * . But, if 𝑖𝑗 ∈ 𝐸(𝑇) then the triangle inequality between these vectors is violated; i.e. 𝑣 * -𝑣 * ≤ ‖𝑤 -𝑣 * ‖ + 𝑤 -𝑣 * 2 -2𝑣 * 𝑣 * ≤ 2 -2𝑤𝑣 * + 2 -2𝑤𝑣 * 2 -2(-1 + 2(0.0004)) ≤ 2 -2𝑣 * 𝑣 * ≤ 2 -2𝑤𝑣 * + 2 -2𝑤𝑣 * ≤ 2 2 -2(0.5003) Therefore, we have 1.9995999 ≤ √3.9984 ≤ 2√0.9994 ≤ 1.9994, which is a contradiction. Likewise, if 𝑖𝑗 ∈ 𝐸(𝑆) then the triangle inequality between vectors 𝑣 * -𝑣 * , 𝑢 -𝑣 * and 𝑢 -𝑣 * is violated, where 𝑢 = -𝑤 ■ By introducing a normalized random vector 𝑤, where |𝐻 | ≥ , we can produce a feasible solution 𝑉 ∪ 𝑉 , correspondingly, where |𝑉 | = 𝑚𝑎𝑥{|𝑆|, |𝑇|} ≥ . Hence, based on Theorem (2), we have |𝑉 |

Figure 1 .

 1 Figure 1. 𝑢 -𝑤 plane, where the radius of the smaller circle is 0.5003, 𝑢𝑢 = 0, 𝑢𝑢 " = 0.5003 , 𝑢𝑜𝑢 " = cos (0.5003) , f(θ) = .

2 .Step 3 .

 23 If for more than of vertices 𝑗 ∈ 𝑉 and corresponding vectors we have 𝑣 * 𝑣 * < 0, then produce the suitable solution V ∪ V , correspondingly, where V = j|𝑣 * 𝑣 * < 0 . Therefore, based on the Assumption (1. a) we have | | * ≤ 1.999999. Otherwise, go to Step 3. If for more than 𝑛 of vertices 𝑗 ∈ 𝑉 and corresponding vectors we have 𝑣 * 𝑣 * > 0.0004, then 𝑧 * ≥ + 0.0000015𝑛 and it is sufficient to produce an arbitrary feasible solution. Therefore, based on Assumption (1. b) for all feasible solutions 𝑉 = 𝑉 ∪ 𝑉 we have | |

  Therefore, Pr 𝑢𝑣 * ≤ 0.5003 & 𝑤𝑣 * ≤ 0.5003 = , where Note that, if |𝑢𝑤| < 1 then we have smaller values for this probability. Therefore, by introducing two normalized random vectors 𝑢, 𝑤, we have 𝑢𝑣 * ≤ 0.5003 and 𝑤𝑣 * ≤ 0.5003 for at most 0.60933𝑛 of the vectors 𝑣 * , the optimal solution of the SDP (1) relaxation. Hence, for at least 0.39067𝑛 of the vectors 𝑣 * we have 𝑢𝑣 * > 0.5003 or 𝑤𝑣 * > 0.5003.

	𝑆 ≤ 4	cos -1 ( .	)	1 2	(	0.5003 cos 𝜃	) 𝑑𝜃	+	cos -1 ( .	)	1 2	𝑑𝜃
	= 2 (0.5003) tan cos -1 (0.5003) + -cos -1 (0.5003) < 2(0.957132).
	Hence, Pr 𝑢𝑣 * ≤ 0.5003 & 𝑤𝑣 * ≤ 0.5003 <	( .	) < 0.60933 ■
	Corollary 2. If the solution of the SDP (1) relaxation meets the Assumption (1), then we have
	|G | 0.989999n and one of the bipartite graphs 𝐻	or 𝐻	has more than
	.	| | =	.	× .			>		of vertices which produces a null subgraph 𝑉	with more than
	.	× .

>

of the vertices and based on the Corollary (1) we have an approximation ratio

| | * ≤ 1.999999 < 2.


Majid Zohrehbandian
email: zohrebandian@yahoo.com

A randomized -approximation algorithm for the minimum vertex cover problem

Keywords: Discrete Optimization, Vertex Cover Problem, Complexity Theory, NP-Complete Problems. MSC 2010: 90C35, 90C60

Vertex cover problem is a famous combinatorial problem, which its complexity has been heavily studied over the years and we know that there is not any mathematical formulation that approximates it better than . In other words, it is known that it is hard to approximate to within any constant factor better than , while a -approximation for it can be trivially obtained. In this paper, by a combination of a well-known semidefinite programming formulation and a rounding procedure, along with satisfying new properties, we introduce an approximation algorithm for the vertex cover problem with a performance ratio of on arbitrary graphs, en route answering an open question about the unique games conjecture.

Introduction

In complexity theory, the abbreviation refers to "nondeterministic polynomial", where a problem is in if we can quickly (in polynomial time) test whether a solution is correct. and -complete problems are subsets of Problems. We can solve problems in polynomial time while determining whether or not it is possible to solve -complete problems quickly (called the vs problem) is one of the principal unsolved problems in Mathematics and Computer science.

Here, we consider the vertex cover problem which is a famous -complete problem. It cannot be approximated within a factor of 1.36 [START_REF] Dinur | On the hardness of approximating minimum vertex cover[END_REF], unless , while a -approximation factor for it can be trivially obtained by taking all the vertices of a maximal matching in the graph. However, improving this simple -approximation algorithm has been a quite hard task [START_REF] Khot | On the power of unique 2-Prover 1-Round games[END_REF][START_REF] Khot | Vertex cover might be hard to approximate to within 2-ℇ[END_REF].

In this paper, we show that there is a -approximation ratio for the vertex cover problem, based on any feasible solution of it. Then, we fix the value equal to and we show that on arbitrary graphs a -approximation ratio can be obtained by a combination of a well-known semidefinite programming (SDP) formulation and a rounding procedure.

The rest of the paper is structured as follows. Section 2 is about the vertex cover problem and introduces new properties about it. In section 3, we propose a rounding procedure along with using the satisfying properties to propose an algorithm with a performance ratio of on arbitrary graphs.

Finally, Section 4 concludes the paper.

Performance ratio for a feasible solution of vertex cover problem

In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. The problem of finding a minimum vertex cover is a typical example of an -complete optimization problem. In this section, we calculate the performance ratios of vertex cover feasible solutions which lead to an approximation ratio ,

where the value of is not constant and depends on the produced feasible solution. Then, in the next section, we fix the value of equal to to produce a -approximation ratio for the vertex cover problem on arbitrary graphs.

Let be an undirected graph on vertex set and edge set , where . Throughout this paper, suppose that the vertex cover problem on is hard and we have produced an arbitrary feasible solution for the problem, with vertex partitioning ( is a vertex cover solution of the graph ) and objective value , and for solving the problem, we use the well-known semidefinite programming (SDP) formulation as follows:

Note that, we know for sure that just by solving this SDP formulation or the other SDP formulations with additional constraints, we cannot approximate the vertex cover problem with a performance ratio better than . In other words, in section 3, we are going to propose a randomized algorithm to classify the solution vectors of the SDP (1) relaxation to produce a suitable solution for the vertex cover problem with a performance ratio of .

Theorem 1. Suppose that in SDP formulation (1) we have . Then, for all vertex cover feasible solutions, , we have the approximation ratio .

Proof. and . Then, ■

Theorem 2. Suppose that the vertex cover problem on is hard ( ) and we have produced a feasible solution for which we have . Then, we have an approximation ratio .

Proof. and . Hence, , and

. Then, which concludes that ■

A -approximation algorithm for the vertex cover problem

In section 2 and based on the produced feasible solution, we could introduce a -approximation ratio where value was not a constant value. In this section, we fix the value of equal to to produce a -approximation ratio for the vertex cover problem on arbitrary graphs. To do this, we assume the following assumption about the solution of the SDP (1) relaxation. In other words, to produce a performance ratio of , we should solve the SDP (1) relaxation.

Then, if the solution of the SDP (1) relaxation does not meet the Assumption (1), we have a performance ratio of and if the solution of the SDP (1) relaxation meets the Assumption (1), it is sufficient to produce a normalized random vector , where .

Theorem 4. Let be two normalized random vectors that are perpendicular to each other, then for any normalized vector , we have .

Proof. Let

, where is the projection of vector onto the plane (suppose that the vector is on the axis and the vector is on the axis) and is the projection of onto the normal vector of that plane. Then, , and we have and if and only if the vector is projected on the gray region in Figure [START_REF] Dinur | On the hardness of approximating minimum vertex cover[END_REF]. In other words, suppose that the vector is projected onto the white region on the first quadrant and with an angle of concerning the vector . Then, we have: Now, we can introduce our algorithm to produce an approximation ratio .

Zohrehbandian Algorithm (To produce a vertex cover solution with a factor )

Step 1. Solve the SDP (1) relaxation.

Step 2. If for more than of vertices and corresponding vectors we have , then produce the suitable solution , correspondingly, where . Therefore, based on the Assumption (1. a) we have . Otherwise, go to Step 3.

Step 3. If for more than of vertices and corresponding vectors we have , then and it is sufficient to produce an arbitrary feasible solution. Therefore, based on the Assumption (1. b) for all feasible solutions we have . Otherwise, go to

Step 4.

Step 4. We have . Then, introduce two normalized random perpendicular vectors and , and produce and . Based on the Corollary (2), one of these bipartite graphs has more than vertices and we can produce a suitable solution , correspondingly, where . Therefore, based on the Corollary (2) we have .

Corollary 3.

Based on the proposed -approximation algorithm for the vertex cover problem, the unique games conjecture is not true.

Figure 1 .Corollary 2 .

 12 Figure 1. plane, where the radius of the smaller circle is 0.700001, , , and ( ) are symmetric concerning the line , and the gray region is symmetric concerning the axis, the axis, and the origin.

Conclusions

One of the open problems about the vertex cover problem is the possibility of introducing an approximation algorithm within any constant factor better than 2. Here, we proposed a new algorithm to introduce a -approximation algorithm for the vertex cover problem on arbitrary graphs, and this may lead to the conclusion that .