Convergence of the Sequential Alternating Subspace Minimization

(u^(ℓ)₁ K^∗(g− Ku2− Ku^(ℓ)₁ ))

− PαK(u^(ℓ)₁ + K^∗(g− Ku2− Ku^(ℓ)1 + u₂− η)) .

The computation ofη^(ℓ)can be implemented by the algorithm (3.173).

Proposition 3.31 Assume u₂ ∈ V2 and kKk < 1. Then the iteration (3.174) con-verges to a solutionu^∗₁ ∈ V1of (3.163) for any initial choice ofu⁽⁰⁾₁ ∈ V1.

The proof of this proposition is similar to the one of Theorem 3.7 and it is omitted.

Let us conclude this section mentioning that all the results presented here hold sym-metrically for the minimization onV₂, and that the notations should be just adjusted accordingly.

3.4.3 Convergence of the Sequential Alternating Subspace Minimization In this section we want to prove the convergence of the algorithm (3.162) to minimizers ofJ . In order to do that, we need a characterization of solutions of the minimization problem (2.80) as the one provided in [77, Proposition 4.1] for the continuous set-ting. We specify the arguments in [77, Proposition 4.1] for our discrete setting and we highlight the significant differences with respect to the continuous one.

Characterization of solutions We make the following assumptions:

(A_ϕ) ϕ : R→ R is a convex function, nondecreasing in R⁺such that (i) ϕ(0) = 0.

(ii) There exist c > 0 and b ≥ 0 such that cz − b ≤ ϕ(z) ≤ cz + b, for all z∈ R⁺.

The particular example we have in mind is simplyϕ(s) = s, but we keep a more gen-eral notation for uniformity with respect to the continuous version in [77, Proposition 4.1]. In this section we are concerned with the following more general minimization problem

argmin_u∈H{Jϕ(u) :=kKu − gk²2+ 2αϕ(|∇u|)(Ω)} (3.175) whereg∈ H is a datum, α > 0 is a fixed constant (in particular for ϕ(s) = s).

To characterize the solution of the minimization problem (3.175) we use duality results from [36]. Therefore we recall the definition of the conjugate (or Legendre transform) of a function (for example see [36, Def. 4.1, pag. 17]):

Definition 3.32 LetV and V^∗be two vector spaces placed in the duality by a bilinear pairing denoted byh·, ·i and φ : V → R be a convex function. The conjugate function (or Legendre transform)φ^∗ : V^∗ → R is defined by

φ^∗(u^∗) = sup

u∈V{hu, u^∗i − φ(u)}.

Proposition 3.33 Let ζ, u∈ H. If the assumption (Aϕ) is fulfilled, then ζ ∈ ∂Jϕ(u) if and only if there existsM = (M₀, ¯M ) ∈ H × H^d, ^{| ¯M(x)}_2α ^| ≤ c1 ∈ [0, +∞) for all x∈ Ω such that

h ¯M (x), (∇u)(x)i^Rd+ 2αϕ(|(∇u)(x)|) + 2αϕ^∗1

| ¯M (x)| 2α



= 0 for all x∈ Ω (3.176) K^∗M₀− div ¯M + ζ = 0 (3.177)

−M0 = 2(Ku− g), (3.178)

whereϕ^∗₁is the conjugate function ofϕ1defined byϕ1(s) = ϕ(|s|), for s ∈ R.

If additionally ϕ is differentiable and |(∇u)(x)| 6= 0 for x ∈ Ω, then we can compute ¯M as

M (x) =¯ −2αϕ^′(|(∇u)(x)|)

|(∇u)(x)| (∇u)(x). (3.179) Remark 3.34 (i) Forϕ(s) = s the function ϕ₁from Proposition 3.33 turns out to

beϕ₁(s) =|s|. Its conjugate function ϕ^∗1 is then given by

ϕ^∗₁(s^∗) = sup

s∈R{hs^∗, si − |s|} = (

0 for|s^∗| ≤ 1

∞ else .

Hence condition (3.176) specifies as follows

h ¯M (x), (∇u)(x)i^Rd+ 2α|(∇u)(x)| = 0

and, directly from the proof of Proposition 3.33 in the Appendix,| ¯M (x)| ≤ 2α for allx∈ Ω.

(ii) We want to highlight a few important differences with respect to the continuous case. Due to our definition of the gradient and its relationship with the divergence operator − div = ∇^∗ no boundary conditions are needed. Therefore condition (10) of [77, Proposition 4.1] has no discrete correspondent in our setting. The continuous total variation of a function can be decomposed into an absolute con-tinuous part with respect to the Lebesgue measure and a singular part, whereas no singular part appears in the discrete setting. Therefore condition (6) and (7) of [77, Proposition 4.1] have not a discrete correspondent either.

(iii) An interesting consequence of Proposition 3.33 is that the mapS_α= (I− PαK) is bounded, i.e.,kSα(z^k)k2 → ∞ if and only if kz^kk2 → ∞, for k → ∞. In fact, since

S_α(z) = arg min

u∈Hku − zk²2+ 2α|∇u|(Ω), from (3.177) and (3.178), we immediately obtain

S_α(z) = z−1

2div ¯M , and ¯M is uniformly bounded.

Proof. (Proposition 3.33.) It is clear thatζ ∈ ∂Jϕ(u) if and only if u = argmin_v∈H{Jϕ(v)− hζ, viH}, and let us consider the following variational problem:

v∈Hinf{Jϕ(v)− hζ, viH} = inf

v∈H{kKv − gk²2+ 2αϕ(|∇v|)(Ω) − hζ, viH} (P) We denote such an infimum byinf(P). Now we compute (P^∗) the dual of (P). Let F : H → R, G : H × H^d→ R, G1:H → R, G2 :H^d→ R, such that

F(v) = −hζ, viH

G1(w₀) = kw0− gk²2

G2( ¯w) = 2αϕ(| ¯w|)(Ω) G(w) = G1(w0) +G2( ¯w)

withw = (w0, ¯w) ∈ H × H^d. Then the dual problem of (P) is given by (cf. [36, p 60])

sup

p^∗∈H×H^d{−F^∗(M^∗p^∗)− G^∗(−p^∗)} (P^∗) where M :H → H × H^dis defined by

Mv = (Kv, (∇v)¹, . . . , (∇v)^d)

and M^∗ is its adjoint. We denote the supremum in (P^∗) by sup(P^∗). Using the definition of the conjugate function we computeF^∗andG^∗. In particular

F^∗(M^∗p^∗) = sup

v∈H{hM^∗p^∗, viH−F(v)} = sup

v∈HhM^∗p^∗+ζ, viH=

(0 M^∗p^∗+ ζ = 0

∞ otherwise wherep^∗ = (p^∗₀, ¯p^∗) and

G^∗(p^∗) = sup

w∈H×H^d{hp^∗, wi_H×H^d − G(w)}

= sup

w=(w0, ¯w)∈H×H^d{hp^∗0, w₀iH+h¯p^∗, ¯wi_H^d− G1(w₀)− G2( ¯w)}

= sup

w0∈H{hp^∗0, w0iH− G1(w0)} + sup

¯

w∈H^d{h¯p^∗, ¯wi_H^d− G2( ¯w)}

=G1^∗(p^∗₀) +G2^∗(¯p^∗)

We have that

For ease we include in below the explicit computation of these conjugate functions.

So we can write (P^∗) in the following way

Hence we can writeK in the following way K = We now apply the duality results from [36, Theorem III.4.1], since the functional in (P) is convex, continuous with respect to M v in H × H^d, andinf(P) is finite. Then inf(P)= sup(P^∗)∈ R and (P^∗) has a solutionM = (M0, ¯M )∈ K.

Let us assume thatu is a solution of (P) and M is a solution of (P^∗). Frominf(P)= verifies the direct implication of (3.177). In particular

−hζ, uiH=hK^∗M0, uiH− hdiv ¯M , uiH =hM0, KuiH+h ¯M ,∇ui_H^d,

Let us write (4.183) again in the following form X

Conversely, if such anM = (M0, ¯M )∈ H × H^dwith^{| ¯M(x)|}_2α ≤ c1exists which ful-fills conditions (3.176)-(3.178), it is clear from previous considerations that equation (4.182) holds. Let us denote the functional on the left side of (4.182) by

P (u) :=kKu − gk²2+ 2αϕ(|∇u|)(Ω) − hζ, uiH

and the functional on the right side of (4.182) by P^∗(M ) :=−

We know that the functional P is the functional of (P) and P^∗ is the functional of (P^∗). Henceinf P = inf(P) and sup P^∗ = sup(P^∗). SinceP is convex, continuous

If additionally ϕ is differentiable and|(∇u)(x)| 6= 0 for x ∈ Ω, we show that we can compute ¯M (x) explicitly. From equation (3.176) (resp. (4.185)) we have

2αϕ^∗₁

| − ¯M (x)| 2α



=−h ¯M (x), (∇u)(x)i^Rd− 2αϕ(|(∇u)(x)|). (4.187) From the definition of conjugate function we have

2αϕ^∗₁

which implies

M¯^j(x) =−2αϕ^′(|(∇u)(x)|)

|(∇u)(x)| (∇u)^j(x) j = 1, . . . , d, and verifies (3.179). This finishes the proof.

Computation of conjugate functions. Let us compute the conjugate function of the convex functionG1(w0) =kw0− gk²₂. From Definition 3.32 we have

G1^∗(p^∗₀) = sup

w0∈H{hw0, p^∗₀iH− G1(w₀)} = sup

w0∈H{hw0, p^∗₀iH− hw0− g, w0− giH}.

We setH(w₀) := hw0, p^∗₀iH − hw0− g, w0− giH. To get the maximum ofH we compute the Gˆateaux-differential atw0ofH,

H^′(w0) = p^∗₀− 2(w0− g) = 0

Ifϕ were an even function then sup whereϕ^∗ is the conjugate function ofϕ.

Unfortunately ϕ is not even in general. To overcome this difficulty we have to choose a function which is equal toϕ(s) for s≥ 0 and does not change the supremum fors < 0. For instance, one can choose ϕ1(s) = ϕ(|s|) for s ∈ R. Then we have

We return to the sequential algorithm (3.162). Let us explicitly express the algorithm as follows:

Note that we do prescribe a finite numberL and M of inner iterations for each sub-space respectively and thatu⁽ⁿ⁺¹⁾ = ˜u⁽ⁿ⁺¹⁾₁ + ˜u⁽ⁿ⁺¹⁾₂ , withu⁽ⁿ⁺¹⁾_i 6= ˜u⁽ⁿ⁺¹⁾_i ,i = 1, 2, in general. In this section we want to prove its convergence for any choice ofL and M .

Observe that, fora∈ Vi andkKk < 1,

kui− ak²2− kKui− Kak²2 ≥ Ckui− ak²2, (3.190)

forC = (1− kKk²) > 0. Hence

J (u) = Ji^s(u, u_i)≤ Ji^s(u, a), (3.191) and

Ji^s(u, a)− Ji^s(u, u_i)≥ Ckui− ak²2. (3.192) Proposition 3.35 (Convergence properties) Let us assume thatkKk < 1. The algo-rithm in (3.210) produces a sequence(u⁽ⁿ⁾)_n∈NinH with the following properties:

(i) J (u⁽ⁿ⁾) >J (u⁽ⁿ⁺¹⁾) for all n∈ N (unless u⁽ⁿ⁾= u⁽ⁿ⁺¹⁾);

(ii) lim_n→∞ku⁽ⁿ⁺¹⁾− u⁽ⁿ⁾k2 = 0;

(iii) the sequence(u⁽ⁿ⁾)_n∈Nhas subsequences which converge inH.

Proof. Let us first observe that

J (u⁽ⁿ⁾) =J1^s(˜u⁽ⁿ⁾₁ + ˜u⁽ⁿ⁾₂ , ˜u⁽ⁿ⁾₁ ) = J1^s(˜u⁽ⁿ⁾₁ + ˜u⁽ⁿ⁾₂ , u^(n+1,0)₁ ).

By definition ofu^(n+1,1)₁ and the minimal properties ofu^(n+1,1)₁ in (3.210) we have J1^s(˜u⁽ⁿ⁾₁ + ˜u⁽ⁿ⁾₂ , u^(n+1,0)₁ )≥ J1^s(u^(n+1,1)₁ + ˜u⁽ⁿ⁾₂ , u^(n+1,0)₁ ).

From (3.191) we have

J1^s(u^(n+1,1)₁ + ˜u⁽ⁿ⁾₂ , u^(n+1,0)₁ )≥ J1^s(u^(n+1,1)₁ + ˜u⁽ⁿ⁾₂ , u^(n+1,1)₁ ) =J (u^(n+1,1)1 + ˜u⁽ⁿ⁾₂ ).

Putting in line these inequalities we obtain

J (u⁽ⁿ⁾)≥ J (u^(n+1,1)₁ + ˜u⁽ⁿ⁾₂ ).

In particular, from (3.192) we have

J (u⁽ⁿ⁾)− J (u^(n+1,1)₁ + ˜u⁽ⁿ⁾₂ )≥ Cku^(n+1,1)₁ − u^(n+1,0)₁ k²2. AfterL steps we conclude the estimate

J (u⁽ⁿ⁾) ≥ J (u^(n+1,L)1 + ˜u⁽ⁿ⁾₂ ), and

J (u⁽ⁿ⁾)− J (u^(n+1,L)1 + ˜u⁽ⁿ⁾₂ )≥ C

L−1

X

ℓ=0

ku^(n+1,ℓ+1)1 − u^(n+1,ℓ)1 k²2.

By definition ofu^(n+1,1)₂ and its minimal properties we have

J (u^(n+1,L)₁ + ˜u⁽ⁿ⁾₂ )≥ J2^s(u^(n+1,L)₁ + u^(n+1,1)₂ , u^(n+1,0)₂ ).

By similar arguments as above we finally find the decreasing estimate

J (u⁽ⁿ⁾)≥ J (u^(n+1,L)₁ + u^{(n+1,M )}₂ ) =J (u⁽ⁿ⁺¹⁾) =J (˜u⁽ⁿ⁺¹⁾₁ + ˜u⁽ⁿ⁺¹⁾₂ ), (3.193) and

J (u⁽ⁿ⁾)− J (u⁽ⁿ⁺¹⁾)

≥ C

L−1X

ℓ=0

ku^(n+1,ℓ+1)₁ − u^(n+1,ℓ)₁ k²2+

M−1X

m=0

ku^(n+1,m+1)₂ − u^(n+1,m)₂ k²2

!

, (3.194) which verifies(i).

From (3.193) we haveJ (u⁽⁰⁾)≥ J (u⁽ⁿ⁾). By the coerciveness condition (C) (u⁽ⁿ⁾)_n∈N is uniformly bounded inH, hence there exists a convergent subsequence (u^(nk))_k∈N and hence (iii) holds. Let us denote u^(∞) the limit of the subsequence. For sim-plicity, we rename such a subsequence by(u⁽ⁿ⁾)_n∈N. Moreover, since the sequence (J (u⁽ⁿ⁾))n∈N is monotonically decreasing and bounded from below by 0, it is also convergent. From (3.194) and the latter convergence we deduce

L−1X

ℓ=0

ku^(n+1,ℓ+1)₁ − u^(n+1,ℓ)₁ k²2+

MX−1 m=0

ku^(n+1,m+1)₂ − u^(n+1,m)₂ k²2

!

→ 0, n → ∞.

(3.195) In particular, by the standard inequality(a²+ b²) ≥ ¹₂(a + b)² fora, b > 0 and the triangle inequality, we have also

ku⁽ⁿ⁾− u⁽ⁿ⁺¹⁾k2→ 0, n → ∞. (3.196) This gives(ii) and completes the proof.

The use of the partition of unity{χ1, χ2} allows not only to guarantee the boundedness of(u⁽ⁿ⁾)_n∈N, but also of the sequences(˜u⁽ⁿ⁾₁ )_n∈Nand(˜u⁽ⁿ⁾₂ )_n∈N.

Lemma 3.36 The sequences(˜u⁽ⁿ⁾₁ )_n∈Nand(˜u⁽ⁿ⁾₂ )_n∈Nproduced by the algorithm (3.210) are bounded, i.e., there exists a constant ˜C > 0 such thatk˜u⁽ⁿ⁾_i k2≤ ˜C for i = 1, 2.

Proof. From the boundedness of(u⁽ⁿ⁾)_n∈Nwe have

k˜u⁽ⁿ⁾_i k2=kχiu⁽ⁿ⁾k2≤ κku⁽ⁿ⁾k2≤ ˜C fori = 1, 2.

From Remark 3.34 (iii) we can also show the following auxiliary lemma.

Lemma 3.37 The sequences (η₁^(n,L))nand⁽η₂^{(n,M )})nare bounded.

Proof. From previous considerations we know that

u^(n,L)₁ = Sα(z^(n,L₁ ⁻¹⁾+ ˜u⁽ⁿ₂ ⁻¹⁾− η₁^(n,L))− ˜u⁽ⁿ₂ ⁻¹⁾ u^{(n,M )}₂ = S_α(z^(n,M₂ ⁻¹⁾+ u^(n,L)₁ − η2^{(n,M )})− u^(n,L)1 .

Assume(η^(n,L)₁ )_n were unbounded, then by Remark 3.34 (iii), also S_α(z₁^(n,L−1) +

˜

u⁽ⁿ₂ ⁻¹⁾− η^(n,L)₁ ) would be unbounded. Since (˜u⁽ⁿ⁾₂ )_n and (u^(n,L)₁ )_n are bounded by Lemma 3.36 and formula (3.195), we have a contradiction. Thus(η₁^(n,L))nhas to be bounded. With the same argument we can show that(η^{(n,M )}₂ )_nis bounded.

We can eventually show the convergence of the algorithm to minimizers ofJ . Theorem 3.38 (Convergence to minimizers) AssumekKk < 1. Then accumulation points of the sequence(u⁽ⁿ⁾)_n∈Nproduced by algorithm (3.210) are minimizers ofJ . IfJ has a unique minimizer then the sequence (u⁽ⁿ⁾)n∈Nconverges to it.

Proof. Let us denoteu^(∞)the limit of a subsequence. For simplicity, we rename such a subsequence by(u⁽ⁿ⁾)_n∈N. From Lemma 3.36 we know that(˜u⁽ⁿ⁾₁ )_n∈N,(˜u⁽ⁿ⁾₂ )_n∈N and consequently (u^(n,L)₁ )_n∈N,(u^{(n,M )}₂ )_n∈N are bounded. So the limit u^(∞) can be written as

u^(∞)= u⁽₁^∞)+ u⁽₂^∞)= ˜u⁽₁^∞)+ ˜u⁽₂^∞) (3.197) whereu⁽₁^∞)is the limit of(u^(n,L)₁ )_n∈N,u⁽₂^∞)is the limit of(u^{(n,M )}₂ )_n∈N, andu˜⁽_i^∞)is the limit of(˜u⁽ⁿ⁾_i )_n∈N fori = 1, 2. Now we show that ˜u^(∞)₂ = u^(∞)₂ . By using the triangle inequality, from (3.195) it directly follows that

ku^{(n+1,M )}₂ − ˜u⁽ⁿ⁾₂ k2 → 0, n → ∞. (3.198) Moreover, sinceχ2 ∈ V2is a fixed vector which is independent ofn, we obtain from Proposition 3.35(ii) that

kχ2(u⁽ⁿ⁾− u⁽ⁿ⁺¹⁾)k2→ 0, n → ∞, and hence

k˜u⁽ⁿ⁾₂ − ˜u⁽ⁿ⁺¹⁾₂ k2→ 0, n → ∞. (3.199) Putting (3.198) and (3.199) together and noting that

ku^{(n+1,M )}₂ − ˜u⁽ⁿ⁾₂ k2+k˜u⁽ⁿ⁾₂ − ˜u⁽ⁿ⁺¹⁾₂ k2≥ ku^{(n+1,M )}₂ − ˜u⁽ⁿ⁺¹⁾₂ k2

we have

ku^{(n+1,M )}₂ − ˜u⁽ⁿ⁺¹⁾₂ k2 → 0, n → ∞, (3.200)

which means that the sequences(u^{(n,M )}₂ )_n∈Nand(˜u⁽ⁿ⁾₂ )_n∈Nhave the same limit, i.e.,

˜

u⁽₂^∞) = u⁽₂^∞), which we denote by u⁽₂^∞). Then from (3.200) and (3.197) it directly follows thatu˜⁽₁^∞)= u⁽₁^∞).

As in the proof of the oblique thresholding theorem we set

F₁(u^(n+1,L)₁ ) :=ku^(n+1,L)1 − z1^(n+1,L)k²2+ 2α|∇(u^(n+1,L)1 + ˜u⁽ⁿ⁾₂  

Ω1

)|(Ω1) where

z₁^(n+1,L):= u^(n+1,L−1)₁ + (K^∗(g− K ˜u⁽ⁿ⁾₂ − Ku^(n+1,L−1)₁ )) Ω1

.

The optimality condition foru^(n+1,L)₁ is

0∈ ∂V1F₁(u^(n+1,L)₁ ) + 2η₁^(n+1,L) where

η^(n+1,L)₁ = (Tr|Γ1)^∗Tr|Γ1



(z₁^(n+1,L)) + P_αK(η₁^(n+1,L)− z^(n+1,L)1 − ˜u⁽ⁿ⁾2 ) . In order to use the characterization of elements in the subdifferential of|∇u|(Ω), i.e., Proposition 3.33, we have to rewrite the minimization problem for F1. More precisely, we define

Fˆ₁(ξ₁^(n+1,L)) :=kξ1^(n+1,L)− ˜u⁽ⁿ⁾2

 Ω1

− z1^(n+1,L)k²2+ 2α|∇(ξ1^(n+1,L))|(Ω1) for ξ₁^(n+1,L) ∈ V1 with Tr |Γ1 ξ^(n+1,L)₁ = ˜u⁽ⁿ⁾₂ . Then the optimality condition for ξ₁^(n+1,L)is

0∈ ∂ ˆF₁(ξ₁^(n+1,L)) + 2η₁^(n+1,L) (3.201) Note that indeedξ^(n+1,L)₁ is optimal if and only ifu^(n+1,L)₁ = ξ₁^(n+1,L)− ˜u⁽ⁿ⁾₂ 



Ω1

is optimal.

Analogously we define

Fˆ₂(ξ^{(n+1,M )}₂ ) :=kξ^{(n+1,M )}2 − u^(n+1,L)1

 Ω2

− z2⁽ⁿ⁺¹⁾k²2+ 2α|∇(ξ^{(n+1,M )}2 )|(Ω2) forξ^{(n+1,M )}₂ ∈ V2withTr |Γ2 ξ^{(n+1,M )}₂ = u^(n+1,L)₁ , and the optimality condition for ξ₂^{(n+1,M )}is

0∈ ∂ ˆF₂(ξ^{(n+1,M )}₂ ) + 2η₂^{(n+1,M )} (3.202) where

η^{(n+1,M )}₂ = (Tr|Γ2)^∗Tr|Γ2

(z₂^{(n+1,M )}) + P_αK(η^{(n+1,M )}₂ − z2^{(n+1,M )}− u^(n+1,L)1 ) .

Let us recall that now we are considering functionals as in Proposition 3.33 with ϕ(s) = s, K = I, and Ω = Ωi, i = 1, 2. From Proposition 3.33 and Remark 3.34 we get thatξ₁^(n+1,L), and consequentlyu^(n+1,L)₁ is optimal, i.e., −2η^(n+1,L)₁ ∈

∂ ˆF1(ξ₁^(n+1,L)), if and only if there exists an M₁⁽ⁿ⁺¹⁾ = (M_0,1⁽ⁿ⁺¹⁾, ¯M₁⁽ⁿ⁺¹⁾)∈ V1× V₁^d with| ¯M₁⁽ⁿ⁺¹⁾(x)| ≤ 2α for all x ∈ Ω1such that

h ¯M₁⁽ⁿ⁺¹⁾(x), (∇(u^(n+1,L)₁ + ˜u⁽ⁿ⁾₂ ))(x)i^Rd+ 2αϕ(|(∇(u^(n+1,L)₁ + ˜u⁽ⁿ⁾₂ ))(x)|) = 0 (3.203)

−2(u^(n+1,L)₁ (x)− z₁^(n+1,L)(x))− div ¯M₁⁽ⁿ⁺¹⁾(x)− 2η^(n+1,L)₁ (x) = 0.

(3.204) for allx ∈ Ω1. Analogously we get that ξ₂^{(n+1,M )}, and consequently u^{(n+1,M )}₂ is optimal, i.e., −2η^{(n+1,M )}₂ ∈ ∂ ˆF₂(ξ₂^{(n+1,M )}), if and only if there exists an M₂⁽ⁿ⁺¹⁾ = (M_0,2⁽ⁿ⁺¹⁾, ¯M₂⁽ⁿ⁺¹⁾)∈ V2× V₂^dwith| ¯M₂⁽ⁿ⁺¹⁾(x)| ≤ 2α for all x ∈ Ω2such that

h ¯M₂⁽ⁿ⁺¹⁾(x), (∇(u^(n+1,L)₁ + u^{(n+1,M )}₂ ))(x)i^Rd+ 2αϕ(|(∇(u^(n+1,L)₁ + ˜u^{(n+1,M )}₂ ))(x)|) = 0 (3.205)

−2(u^{(n+1,M )}2 (x)− z2^{(n+1,M )}(x))− div ¯M₂⁽ⁿ⁺¹⁾(x)− 2η^{(n+1,M )}2 (x) = 0, (3.206) for allx ∈ Ω2. Since( ¯M₁⁽ⁿ⁾(x))_n∈N is bounded for allx ∈ Ω1and ( ¯M₂⁽ⁿ⁾(x))_n∈N is bounded for all x ∈ Ω2, there exist convergent subsequences ( ¯M₁^(nk)(x))_k∈N and ( ¯M₂^(nk)(x))_k∈N. Let us denote ¯M₁^(∞)(x) and ¯M₂^(∞)(x) the respective limits of the sequences. For simplicity we rename such sequences by ( ¯M₁⁽ⁿ⁾(x))_n∈N and ( ¯M₂⁽ⁿ⁾(x))_n∈N.

Note that, by Lemma 3.37 (or simply from (3.204) and (3.206)) the sequences (η₁^(n,L))n∈N and (η^{(n,M )}₂ )n∈N are also bounded. Hence there exist convergent sub-sequences which we denote, for simplicity, again by (η₁^(n,L))_n∈N and (η₂^{(n,M )})_n∈N with limitsη_i^(∞), i = 1, 2. By taking in (3.203)-(3.206) the limits for n → ∞ we obtain

h ¯M₁^(∞)(x), (∇(u^(∞)1 + u^(∞)₂ ))(x)i^Rd+ 2αϕ(|(∇(u^(∞)1 + u^(∞)₂ ))(x)|) = 0 for all x ∈ Ω1

−2(u⁽₁^∞)(x)− z⁽₁^∞)(x))− div ¯M₁^(∞)(x)− 2η⁽₁^∞)(x) = 0 for allx∈ Ω1

h ¯M₂^(∞)(x), (∇(u^(∞)1 + u^(∞)₂ ))(x)i^Rd+ 2αϕ(|(∇(u^(∞)1 + u^(∞)₂ ))(x)|) = 0 for all x ∈ Ω2

−2(u⁽₂^∞)(x)− z⁽₂^∞)(x))− div ¯M₂^(∞)(x)− 2η⁽₂^∞)(x) = 0 for allx∈ Ω2

Sincesupp η⁽₁^∞)= Γ₁andsupp η⁽₂^∞)= Γ₂we have

h ¯M₁^(∞)(x), (∇(u^(∞))(x)i^Rd+ 2αϕ(|(∇(u^(∞))(x)|) = 0 for all x ∈ Ω1

−2K^∗((Ku^(∞))(x)− g^(∞)(x))− div ¯M₁^(∞)(x) = 0 for allx∈ Ω1\ Γ1

(3.207) h ¯M₂^(∞)(x), (∇(u^(∞))(x)i^Rd + 2αϕ(|(∇(u^(∞))(x)|) = 0 for all x ∈ Ω2

−2K^∗((Ku^(∞))(x)− g^(∞)(x))− div ¯M₂^(∞)(x) = 0 for all x∈ Ω2\ Γ2. (3.208) Observe now that from Proposition 3.33 we also have that 0∈ J (u^(∞)) if and only if there existsM^(∞)= (M₀^(∞), ¯M^(∞)) with| ¯M₀^(∞)(x)| ≤ 2α for all x ∈ Ω such that

h ¯M^(∞)(x), (∇(u^(∞))(x)i^Rd+ 2αϕ(|(∇(u^(∞))(x)|) = 0 for all x ∈ Ω

−2K^∗((Ku^(∞))(x)− g^(∞)(x))− div ¯M^(∞)(x) = 0 for all x∈ Ω. (3.209) Note that ¯M_j^(∞)(x), j = 1, 2, for x ∈ Ω1∩ Ω2satisfies both (3.207) and (3.208).

Hence let us choose

M^(∞)(x) =

(M₁^(∞)(x) if x∈ Ω1\ Γ1

M₂^(∞)(x) if x∈ (Ω2\ Ω1)∪ Γ1

.

With this choice of M^(∞) equations (3.207) - (3.209) are valid and hence u^(∞) is optimal inΩ.

Remark 3.39 (i) If∇u^(∞)(x)6= 0 for x ∈ Ωj,j = 1, 2, then ¯M_j^(∞)is given as in equation (3.179) by

M¯_j^(∞)(x) =−2α (∇u^(∞)|Ωj)(x)

|(∇u^(∞) |Ωj)(x)|.

(ii) The boundedness of the sequences(˜u⁽ⁿ⁾₁ )_n∈Nand(˜u⁽ⁿ⁾₂ )_n∈Nhas been technically used for showing the existence of an optimal decompositionu^(∞)= u^(∞)₁ +u^(∞)₂ in the proof of Theorem 3.38. Their boundedness is guaranteed as in Lemma 3.36 by the use of the partition of the unity{χ1, χ2}. Let us emphasize that there is no way of obtaining the boundedness of the local sequences (u^(n,L)₁ )_n∈N and (u^{(n,M )}₂ )_n∈N otherwise. In Figure 3.12 we show that the local sequences can become unbounded in case we do not modify them by means of the partition of the unity.

(iii) Note that for deriving the optimality condition (3.209) foru^(∞)we combined the respective conditions (3.207) and (3.208) foru^(∞)₁ andu^(∞)₂ . In doing that, we strongly took advantage of the overlapping property of the subdomains, hence avoiding a fine analysis ofη₁^(∞)and η₂^(∞) on the interfacesΓ1 and Γ2. This is the major advantage of this analysis with respect to the one provided in [44] for nonoverlapping domain decompositions.

Nel documento Numerical methods for sparse recovery (pagine 93-107)