Định lí sau cho ta điều kiện cần và đủ của tính tựa Lipschitz đối với ánh xạ nghiệm S.
Định lí 2.4.1. Ánh xạ S là tựa Lipschitz địa phương xung quanh điểm ( ¯w,x)¯ nếu và chỉ nếu
(kerA¯T)∩ N(¯v;K) ={0}, (2.9) trong đó v¯= ¯Ax¯+ ¯b và kerA¯T := {v0 ∈ Rm|A¯Tv0 = 0}.
Chứng minh. Trước hết ta tính đối đạo hàm của S. Chú ý rằng F là đồ thị đóng bởi G là một ánh xạ đơn trị liên tục và K là tập đóng. Ngoài ra,
∇wG(¯x,w)¯ là toán tử toàn ánh. Theo định lí 2.1,[3], ta có D∗S( ¯w,x)(x¯ 0) = [
v0∈Rm
{(−x0, w0) ∈ ∇G(¯x,w)v¯ 0+D∗M( ¯w)(v0)}
(2.10) với bất kì x0 ∈ Rn. Theo định lí (2.3.2) và (2.3.3), ta có
D∗S( ¯w,x)(x¯ 0) = {{−(vi0x¯j)} × {−v0}|v0 ∈ −N(¯v;K), với x0 = ATv0}.
(2.11) Dễ thấy gph S là đóng. Do đó, theo [5], định lí 4.10,[2] và định lí 9.40,[6], S là Lipschitz địa phương quanh ( ¯w,x)¯ nếu và chỉ nếu
D∗S( ¯w,x)(0) =¯ {0} (2.12) Điều này tương đương với
{{−(vi0x¯j)} × {−v0}|v0 ∈ −N(¯v;K) với 0 = ATv0} = {0}
Rõ ràng {{−(v0ix¯j)} × {−v0}} = {0} nếu và chỉ nếu v0 = 0. Do đó, S là Lipschitz địa phương quanh ( ¯w,x)¯ nếu và chỉ nếu
kerA¯T ∩ −N(¯v;K) = {0}.
Do kerA¯T là không gian con tuyến tính của Rm nên đẳng thức cuối tương đương với (2.9).
Đẳng thức (2.9) là điều kiện cần và đủ để S là Lipschitz địa phương quanh ( ¯w,x)¯ . Nếu có kerA¯T = {0} hoặc N(¯v;K) ={0} thì (2.9) thoả mãn.
Tiếp theo ta chỉ ra tính tựa Lipschitz địa phương tương đương với tính chính qui mêtric. Ta cần hai bổ đề sau.
Bổ đề 2.4.1. Nếu S là chính qui mêtric theo nghĩa Robinson tại w0 = ( ¯w,x,¯ 0) thì S là tựa Lipschitz địa phương xung quanh ( ¯w,x)¯ .
Chứng minh. Giả sử S là chính qui mêtric theo nghĩa Robinson tại w0. Khi đó ánh xạ đa trị F(x, w) = −Ax−b+K, với w = (A, b) là nửa liên tục trong tại w0 = ( ¯w,x,¯ 0). Theo định nghĩa tính chính qui mêtric tồn tại r > 0, lân cận bị chặn U của w¯, V của x¯ sao cho
d(x, S(w)) ≤ rd(0;F(x, w)),∀w ∈ U, x ∈ V. (2.13) và S(w) 6= ∅,∀w ∈ U.
Từ V là bị chặn nên tồn tại α > 0 sao cho kxk ≤ α,∀x ∈ V. Bây giờ ta chỉ ra S là tựa Lipschitz địa phương với lân cận U, V như trên.
Thật vậy lấy w1 = (A1, b1);w2 = (A2, b2) ∈ U;x1 ∈ S(w1) ∩ V. Từ kx1k ≤ α và A1x1 +b1 ∈ K và (2.13) ta có
d(x1;S(w2)) ≤ rd(0;F(x1, w2)) =rd(0;−A2x1 −b2 +K)
= rd(A2x1 + b2;K)
≤ rk(A2x1 +b2)−(A1x1 +b1)k
≤ r(k(A2 −A1kkx1k+ kb2 −b1k)
≤ r(α(A2 −A1kkx1k+kb2 −b1k).
Đặt ` = max{r, rα}, ta được
d(x1;S(w2)) ≤ `kw2 −w1k;∀x1 ∈ S(w1)∩V.
TừS(w2)là tập đóng, khác rỗng nên tồn tạix2 ∈ S(w2)sao chod(x1;S(w2)) = d(x1, x2). Do đó
d(x1, x2) ≤ `kw2 −w1k.
Vì x1 tùy ý thuộc S(w1)∩V nên x1 ∈ S(w2) +`kw2 −w1k×B¯
Rn. Điều này kéo theo
S(w1)∩V ⊂ S(w2) + `kw2 −w1k×B¯
Rn.
Vậy S là tựa chính qui mêtric địa phương xung quanh ( ¯w,x)¯ . Bổ đề được chứng minh.
Bổ đề 2.4.2. Nếu điều kiện (2.9) thỏa mãn thì S là mêtric chính qui theo nghĩa Robinson tại w0 = ( ¯w,x,¯ 0).
Chứng minh. Sử dụng định lí 3.1,[4], ta cần chỉ ra một trong 2 điều kiện sau được thỏa mãn, thứ nhất là
kerD∗F(w0) = {0}, (2.14)
trong đó F(x, w) =G(x, w) +M(x, w). Thứ hai là
{w0 ∈ W∗ | ∃v0 ∈ Rm,(0, w0) ∈ D∗F(w0)(v0)} = {0}. (2.15) Sử dụng định lí 1.62,[2], cho v0 bất kì, ta có
D∗F(w0)(v0) =∇G(¯x,w)¯ ∗v0+D∗M( ¯w)(v0).
Do đó, điều kiện (2.14) trở thành
(0 ∈ ∇G(¯x,w)¯ ∗v0 +D∗M( ¯w)(v0)) ⇒ v0 = 0.
Từ định lí 2.3.2 và 2.3.3 , điều kiện (2.14) trở thành
[v0 ∈ −N(¯v;K) và {−A¯Tv0} × {−(vi0x¯j)} × {−v0} = 0]⇒ v0 = 0.
Do (2.10), điều kiện (2.15) nghĩa là (2.12) được thỏa mãn. Trong chứng minh định lí 2.4.1 đẳng thức trên tương đương với điều kiện (2.9). Vậy bổ đề được chứng minh.
Định lí 2.4.2. Tính tựa Lipschitz địa phương xung quanh ( ¯w,x)¯ và tính chính qui metric theo nghĩa Robinson tại w0 = ( ¯w,x,¯ 0) của S là tương đương.
Chứng minh. Sử dụng định lí 2.4.1, bổ đề 2.4.1 và 2.4.2.
Định lí 2.4.3. Nếu K là nón lồi đóng thì các tính chất sau là tương đương:
(a) S là tựa Lipschitz địa phương quanh ( ¯w,x)¯ ;
(b) S là chính qui mêtric theo nghĩa Robinson tại w0 = ( ¯w,x,¯ 0);
(c) (kerA¯T)∩N(¯v;K) ={0};
(d) (kerA¯T)∩ K∗ ∩(¯v)⊥ = {0}, K∗ = {v0 ∈ Rm | hv0,vi ≤¯ 0,∀v ∈ K},
¯
v = ¯A¯x+ ¯b,(¯v)⊥ := {v0 ∈ Rm | hv0,¯vi ≤ 0};
(e) 0∈ int(rgeA¯ = K−¯v), ở đó rgeA¯:= ¯A(Rn) là ảnh của A¯ và intΩ là phần trong của Ω;
(f) rgeA¯+ cone(K −v) =¯ Rm, ở đó coneC là nón được tạo ra bởi C. Do đó, một trong các điều kiện sau là đủ để (a) và (b) thỏa mãn:
(kerA¯T)∩K∗ = {0};
(kerA¯T)∩(¯v)⊥ = {0};
K∗ ∩(¯v)⊥ = {0}.
(a) ⇔ (b) ⇔ (c) được suy ra từ định lý 2.4.2
Để chứng minh (c) ⇔(d), ta cần chứng minh N(¯v;K) = K∗ ∩(¯v)⊥. Do v0 ∈ K∗ và v0 ∈ (¯v)⊥ nên dễ dàng suy ra v0 ∈ N(¯v;K).
Nếu v0 ∈ N(¯v;K), thì hv0, v−vi ≤¯ 0, ∀v ∈ K. v = 0 ⇒ hv0,vi ≥¯ 0.
v = 2¯v ⇒ hv0,vi ≤¯ 0.
Do đó hv0,vi¯ = 0 hay v0 ∈ (¯v)⊥. Với bất kì v ∈ K, thay v bởi v + ¯v vào bất đẳng thức trên, ta có hv0, vi ≤ 0, do đó v0 ∈ K∗.
Để chứng minh(c) ⇒ (e), giả sử trái lại (c) là đúng, nhưng 0∈ Rm là một điểm biên của tập lồiC := rgeA¯+K−v¯. Theo định lý phân tách, ta có thể tìm được véctơ khác không x∗ ∈ Rm sao cho hx∗, yi ≤ 0, ∀y ∈ C. Thay y = ¯Ax vào bất đẳng thức cuối ta được
hA¯Tx∗, xi = hx∗,Axi ≤¯ 0, ∀x∈ Rn.
do đó x∗ ∈ ker ¯AT. Bây giờ, cho y = v −v, v¯ ∈ K, ta được hx∗, v−vi ≤¯ 0, ∀v ∈ K. Điều này nghĩa là x∗ ∈ N(¯v;K). Do đó, tính chất x∗ 6= 0 trái với (c).
Do cone(rgeA¯+ (K −¯v)) =rgeA¯+cone(K −v)¯ , do đó (e) ⇒ (f). Để kết thúc chứng minh, ta cần chứng minh(f) ⇒(c). Nếux∗ ∈ (ker ¯AT)∩
N(¯v;K) thì hx∗,Axi¯ = 0 ∀x ∈ Rn và hx∗, v−¯vi ≤ 0, ∀v ∈ K. Do đó:
hx∗,Ax¯ + λ(v −v)i ≤¯ 0, ∀x ∈ Rn, v ∈ K, λ ≥0.
Theo (f), ta có x∗ = 0. Do đó, (c) đúng.
Chương 3
Bài toán bù tuyến tính