Tài liệu Bất đẳng thức biến phân affine và ứng dụng

LỜI CAM ĐOAN Tôi xin cam đoan luận văn là công trình nghiên cứu của riêng tôi được thực hiện dưới sự hướng dẫn của PGS. TS Nguyễn Năng Tâm. Hà Nội, tháng 9 năm 2009 Tác giả Nguyễn Tấn Hòa Mục lục Lời giới thiệu 4 Chương 1. BẤT ĐẲNG THỨC BIẾN PHÂN AFFINE 6 1.1. Bất đẳng thức biến phân . . . . . . . . . . . . . . . . . . . 6 1.2. Bài toán bù . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3. Bất đẳng thức biến phân affine . . . . . . . . . . . . . . . 13 1.4. Bài toán bù tuyến tính . . . . . . . . . . . . . . . . . . . . 21 Chương 2. SỰ TỒN TẠI NGHIỆM CHO BÀI TOÁN BẤT ĐẲNG THỨC BIẾN PHÂN AFFINE 25 2.1. Sự tồn tại nghiệm dưới điều kiện đơn điệu . . . . . . . . . 25 2.2. Sự tồn tại nghiệm dưới điều kiện đơn điệu nón . . . . . . . 32 Chương 3. ỨNG DỤNG CỦA BẤT ĐẲNG THỨC BIẾN PHÂN AFFINE VÀO BÀI TOÁN CÂN BẰNG GIAO THÔNG 43 3.1. Mạng lưới cân bằng giao thông . . . . . . . . . . . . . . . 43 3.2. Đưa bài toán cân bằng mạng giao thông về bài toán bù . . 46 3.3. Đưa bài toán cân bằng mạng giao thông về bài toán bất đẳng thức biến phân . . . . . . . . . . . . . . . . . . . . . 47 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . 53 MỘT SỐ KÍ HIỆU Trong luận văn sử dụng các kí hiệu cho trong bảng sau h, ·, i Rn Rn×n + tích vô hướng trong không gian Hilbert không gian thực n−chiều không gian các ma trận cấp n với các thành phần không âm n×n Rs không gian các ma trận đối xứng cấp n n×m R không gian các ma trận cỡ n × m + O ∆ nón lùi xa ∅ tập rỗng V I(φ, ∆) bài toán bất đẳng thức biến phân xác định bởi tập ∆ và ánh xạ φ N CP (φ, ∆) bài toán bù xác định bởi nón lồi ∆ và ánh xạ φ GLCP (M, q, ∆) bài toán bù tuyến tính tổng quát AV I (M, q, ∆) bài toán bất đẳng thức biến phân affine xác định bởi tập lồi ∆, ma trận M và véc tơ q SOL (AV I (M, q, ∆)) tập nghiệm của bài toán bất đẳng thức biến phân affine int∆ phần trong của ∆ ∂f (x) dưới vi phân của f tại x MỞ ĐẦU 1. Lý do chọn đề tài Bài toán bất đẳng thức biến phân ra đời và phát triển góp phần cho toán học ứng dụng phát triển mạnh mẽ. Nó được hình thành từ điều kiện cần cực trị của bài toán tối ưu. Lớp những bài toán bất đẳng thức biến phân trong không gian Hilbert có vai trò quan trọng và có nhiều ứng dụng rộng rãi. Nhưng với toán học ứng dụng càng đi sâu vào một phân ngành thì tính ứng dụng càng rộng rãi. Bất đẳng thức biến phân affine là trường hợp đặc biệt của bài toán bất đẳng thức biến phân. Sau khi học và nghiên cứu các môn Giải tích hàm, Giải tích lồi, lí thuyết tối ưu,... với mong muốn hiểu sâu hơn về phần lí thuyết và ứng dụng của bất đẳng thức biến phân affine tôi đã lựa chọn đề tài: "Bất đẳng thức biến phân affine và ứng dụng" 2. Mục đích nghiên cứu Mục đích của luận văn là tìm hiểu sâu về lí thuyết bất đẳng thức biến phân affine, nghiên cứu về sự tồn tại nghiệm của bài toán này, nghiên cứu bài toán bù và ứng dụng của nó trong thực tế. 3. Nhiệm vụ nghiên cứu Nội dung nghiên cứu của luận văn gồm 03 chương: Chương 1: Bất đẳng thức biến phân affine Trong chương này, chúng ta tìm hiểu các khái niệm bất đẳng thức biến phân, bất đẳng thức biến phân affine, khái niệm bài toán bù và các tính chất của chúng. Chương 2: Sự tồn tại nghiệm cho bài toán bất đẳng thức biến phân affine Trong chương này, chúng ta tìm hiểu những định lí cơ bản về sự tồn tại nghiệm của bài toán bất đẳng thức biến phân affine. 5 Chương 3: Ứng dụng của bất đẳng thức biến phân affine vào bài toán cân bằng mạng giao thông. Trong chương này, chúng ta tìm hiểu các khái niệm lưới giao thông. Sự tương ứng của bài toán bất đẳng thức biến phân và sự cân bằng mạng lưới giao thông. 4. Đối tượng và phạm vi nghiên cứu Luận văn tập trung nghiên cứu sự đặc biệt hóa từ bất đẳng thức biến phân thành bất đẳng thức biến phân affine, nghiên cứu tính chất của bài toán bất đẳng thức biến phân affine, sự tồn tại nghiệm của nó và một phần ứng dụng của nó vào cân bằng mạng lưới giao thông. 5. Phương pháp nghiên cứu Phân tích, tổng hợp,... 6. Giả thuyết khoa học Dựa trên giả thuyết khoa học của các nhà Toán học đi trước. Chương 1 BẤT ĐẲNG THỨC BIẾN PHÂN AFFINE Khái niệm bất đẳng thức biên phân affine và bài toán bù được đưa ra nhờ sự thu hẹp khái niệm bất đẳng thức biến phân. 1.1. Bất đẳng thức biến phân Bài toán bất đẳng thức biến phân bắt nguồn từ bài toán tối ưu hóa. Cho φ : Rn → Rn là hàm C 1 và ∆ ⊂ Rn là một tập lồi, đóng, khác rỗng. Mệnh đề 1.1. Nếu x̄ là một nghiệm địa phương của bài toán tối ưu min {f (x) : x ∈ ∆} , (1.1) h∇f (x) , y − xi ≥ 0, ∀y ∈ ∆. (1.2) thì Chứng minh. Gọi x ∈ ∆ là một nghiệm địa phương của (1.1). Chọn µ sao cho f (y) ≥ f (x) , y ∈ ∆ ∩ B (x, µ). Lấy bất kỳ x ∈ ∆\{x}, ta thấy rằng tồn tại ∃δ > 0 sao cho x + t (x − x) ∈ ∆ ∩ B (x, µ). Ở đó t ∈ (0, δ). Hơn thế nữa f (x + t (x − x)) − f (x) = f , (x, x − x) = h∇f (x) , x − xi t→0 t = hDx + c, x − xi . 0 ≤ lim Đặt     φ (x) = ∇f (x) =    ∂f (x) ∂x1 . . . ∂f (x) ∂xn      , ∀x ∈ Rn .   (1.3) 7 Chúng ta thấy rằng (1.2) có thể viết lại hφ (x) , y − xi > 0, ∀y ∈ R. (1.4) Định nghĩa 1.1. Cho ∆ ⊂ Rn là một tập con lồi, đóng và φ : ∆ → Rn là một ánh xạ đã cho thì bài toán tìm x ∈ ∆ thỏa mãn (1.4) được gọi là bài toán bất đẳng thức biến phân, hoặc đơn giản là bất đẳng thức biến phân (kí hiệu V I). Nó được kí hiệu bởi V I(φ, ∆). Tập nghiệm Sol(V I(φ, ∆)) của bài toán V I(φ, ∆) là tập tất cả các x ∈ ∆ thỏa mãn (1.4). Chúng ta dễ dàng kiểm tra rằng x ∈ (V I(φ, ∆)) nếu và chỉ nếu 0 ∈ φ (x) + N∆ (x) . Ở đó N∆ (x) := {ω : hω, y − xi ≤ 0, ∀y ∈ ∆} , gọi là nón pháp tuyến ngoài của ∆ tại x. Mệnh đề 1.1 chứng tỏ rằng bài toán tối ưu trơn có thể dẫn đến bất đẳng thức biến phân. Một câu hỏi nảy sinh một cách tự nhiên: Đưa ra một bất đẳng thức biến phân V I(φ, ∆) với một hàm liên tục φ : Rn → Rn có thể tìm được một hàm f : Rn → R, f ∈ C 1 sao cho bài toán V I(φ, ∆) có thể thu được từ bài toán tối ưu (1.1) bởi phương pháp mô tả nào đó hay không? Nếu tồn tại f , chúng ta chắc chắn có φ (x) = ∇f (x) ∀x ∈ ∆. (1.5) Ta lưu ý rằng, nếu f là một hàm C 2 thì toán tử tuyến tính φ : Rn → Rn định nghĩa bởi (1.3) có ma trận Jacobi đối xứng. Giả sử rằng nếu φ : Rn → Rn là một hàm véc tơ có các thành phần φ1 , ..., φn trơn thì ma trận Jacobi của φ tại x định nghĩa bởi công thức  ∂φ (x) ∂φ (x) 1 1 ... ∂φ∂x1 (x) ∂x1 ∂x2 n  : :  : Jφ (x) =  . .  . ∂φn (x) ∂φn (x) ... ∂φ∂xn (x) ∂x1 ∂x2 n      8 Vì f được giả sử là hàm C 2 , nên từ (1.3) chúng ta kết luận rằng ∂φi (x) ∂ 2 f (x) ∂ 2 f (x) ∂φj (x) = = = , ∂xj ∂xj xi ∂xi xj ∂xi với mọi i, j. Điều đó chứng tỏ rằng Jφ (x) là ma trận đối xứng. Mệnh đề 1.2. [6] Cho ∆ ⊂ Rn là một tập lồi, đóng, khác rỗng. Nếu φ : Rn → Rn là một hàm véc tơ trơn từng khúc đồng thời ∂φi (x) ∂xj = ∂φj (x) ∂xi , với tất cả các i, j (một toán tử đối xứng trơn), khi đó tồn tại một hàm f : Rn → Rn , f ∈ C 2 sao cho hệ thức (1.5) được thỏa mãn. Vì vậy, chúng ta thấy rằng bài toán tối ưu trơn C 2 tương ứng với bài toán bất đẳng thức biến phân với toán tử trơn và đối xứng. Hơn thế nữa, khi nghiên cứu bài toán V I, chúng ta có thể gặp trường hợp bài toán V I với toán tử không đối xứng gián đoạn. Mệnh đề sau đây chứng tỏ rằng, các nghiệm của các bài toán tối ưu và bài toán V I là không tương đương, nghiệm của bài toán V I chỉ là nghiệm địa phương đặc trưng của bài toán tối ưu. _ Mệnh đề 1.3. Cho x ∈ ∆. Nếu _ _ ∃ε > 0 : φ(x), y − x > 0, _ _ ∀y ∈ ∆ ∩ B (x, ε), (1.6) _ thì x ∈ Sol(V I(φ, ∆)). Chứng minh. Giả sử  > 0 thỏa mãn (1.6). Hiển nhiên, với y ∈ ∆, ∃t = _ _ _ _ t (y) ∈ (0, 1) sao cho y(t) := x +t(y − x) ∈ ∆ ∩ B (x, ε). _ _ _ _ Theo (1.6), 0 6 φ(x), y(t) − x = t φ(x), y − x . Điều đó suy ra rằng _ _ _ φ(x), y − x > 0 ∀y ∈ ∆. Do đó x ∈ Sol(V I(φ, ∆))  Bài toán V I(φ, ∆) phụ thuộc hai điều kiện: Tập ∆ và ánh xạ φ. Cấu trúc của tập nghiệm Sol(V I(φ, ∆)) được quyết định bởi tập ∆ và ánh xạ φ. Trong lý thuyết bất đẳng thức biến phân, vấn đề sau đây là cơ bản: Sự tồn tại và duy nhất của nghiệm, tính ổn định và sự phụ thuộc (độ nhạy) 9 của tập nghiệm vào sự thay đổi (nhiễu) của điều kiện bài toán, thuật toán tìm tất cả các nghiệm hoặc một phần của tập nghiệm. Định lí Hartman - Stampacchia sau đây là định lí cơ bản cho sự tồn tại bài toán V I. Nó được chứng minh nhờ việc công nhận định lí Brouwer. Định lý 1.1. [11], [22] Nếu ∆ ⊂ Rn là một tập lồi, compact, khác rỗng và φ : ∆ → Rn là liên tục, khi đó bài toán V I(φ, ∆) có nghiệm. Dưới điều kiện bức thích hợp chúng ta có thể có định lí cho bài toán trên tập lồi không compact. Định lý 1.2. [11] Cho ∆ ⊂ Rn là một tập lồi, đóng, khác rỗng và φ : ∆ → Rn là ánh xạ tuyến tính. Nếu ∃x0 ∈ ∆  φ(y) − φ(x0 ), y − x0 → +∞, y ∈ ∆, ||y − x0 || (1.7) thì bài toán V I(φ, ∆) có nghiệm. Ta có (1.7) tương đương với điều kiện sau đây  φ(y) − φ(x0 ), y − x0 > γ, ∀y ∈ ∆ :k y k> ρ. ∀γ > 0, ∃ρ > 0 : k y − x0 k Điều đó chứng tỏ rằng nếu ∆ là tập compact thì bất kỳ x0 ∈ ∆, (1.7) là đúng. Nếu ∃x0 ∈ ∆ sao cho (1.7) vẫn còn đúng khi đó ta nói rằng điều kiện bức thoả mãn. Điều kiện bức giữ một vai trò khá quan trọng trong việc nghiên cứu bất đẳng thức biên phân trên tập ràng buộc không compact. Chú ý rằng (1.7) là một trường hợp quan trọng của các điều kiện bức. Nếu ∃x0 ∈ ∆ và α ∈ R+  φ(y) − φ(x0 ), y − x0 > α k y − x0 k2 , ∀y ∈ ∆, (1.8) thì chắc chắn (1.7) vẫn còn đúng. Điều đó rõ ràng rằng ∃α > 0 sao cho hφ(y) − φ(x), y − xi > α k y − x0 k2 , ∀x ∈ ∆, ∀y ∈ ∆, thì (1.8) thoả mãn. (1.9) 10 Định nghĩa 1.2. Nếu ∃α > 0 sao cho (1.9) đúng thì φ gọi là đơn điệu mạnh trên ∆. Nếu những điều kiện yếu hơn sau đây hφ(y) − φ(x), y − xi > 0, ∀x ∈ ∆, ∀y ∈ ∆, x 6= y, (1.10) hφ(y) − φ(x), y − xi > 0, ∀x ∈ ∆, ∀y ∈ ∆, (1.11) thoả mãn, thì φ gọi là đơn điệu ngặt trên ∆ và đơn điệu trên ∆ tương ứng. Ví dụ 1.1. Cho ∆ ⊂ Rn là một tập lồi, đóng, khác rỗng. Cho D ∈ Rn×m và c ∈ Rn . Nếu ma trận D xác định dương thì toán tử tuyến tính φ : ∆ → Rn xác định bởi φ(x) = Dx + c là đơn điệu mạnh trên ∆. Trong trường hợp này, chúng ta dễ dàng thử lại rằng α cần tìm ở công thức (1.9) có thể xác  định bởi α = inf v T F v : v ∈ Rn , k v k= 1 . Hơn nữa, Nếu D là nửa xác định dương thì công thức φ(x) = Dx + c xác định một toán tử đơn điệu. Mệnh đề 1.4. Các điều kiện sau đây là đúng i, Nếu φ đơn điệu ngặt trên ∆ thì bài toán V I(φ, ∆) có 1 nghiệm. ii, Nếu φ là đơn điệu và liên tục trên ∆ thì tập nghiệm của bài toán V I(φ, ∆) là tập lồi đóng. Để chứng minh điều kiện thứ hai ở mệnh đề trên chúng ta cần sử dụng các điều kiện về đơn điệu sau đây của bài toán V I. Bổ đề 1.1. [11] Nếu ∆ ⊂ Rn là một tập lồi, đóng và φ : ∆ → Rn là một _ toán tử tuyến tính, đơn điệu thì x ∈ Sol(V I(φ, ∆)) khi và chỉ khi x ∈ ∆ và hφ (y) , y − xi > 0, ∀y ∈ ∆. (1.12) Chứng minh. _ Điều kiện cần. Cho x ∈ Sol(V I(φ, ∆)). Vì tính đơn điệu của φ, chúng ta có hφ(y) − φ(x), y − xi > 0, ∀y ∈ ∆. 11 Kết hợp với điều kiện (1.4) suy ra hφ(y), y − xi > hφ(x), y − xi > 0, ∀y ∈ ∆. Tính chất (1.12) được chứng minh. Điều kiện đủ. Giả sử rằng x ∈ ∆ và (1.12) thoả mãn. Cố định y ∈ ∆ bất kỳ. Vì ∆ lồi, y(t) := x + t(y − x) ∈ ∆, ∀ =∈ (0; 1). Thế y(t) vào (1.12) ta thu được 0 ≤ hφ (y (t)) , y (t) − xi = hφ (x + t (y − x)) , t (y − x)i . Điều đó chứng tỏ rằng hφ (x + t (y − x)) , y − xi ≥ 0, ∀t ∈ (0; 1) . Cho t → 0, vì tính liên tục của φ ta thu được hφ (x) , y − xi ≥ 0. Vì bất đẳng thức trên đúng ∀y ∈ ∆, chúng ta kết luận rằng x ∈ Sol (V I (φ, ∆)).  Chứng minh mệnh đề 1.4 Chứng minh. i, Giả sử ngược lại rằng φ đơn điệu ngặt trên ∆, nhưng bài toán V I (φ, ∆) có hai nghiệm khác nhau x và y . Khi đó hφ (x) , y − xi ≥ 0 và hφ (y) , x − yi ≥ 0. Kết hợp hai bất đẳng thức đó ta có hφ (x) − φ (y) , y − xi ≥ 0. Bất đẳng thức này mâu thuẫn với bất đẳng thức hφ (y) − φ (x) , y − xi > 0. ii, Giả thiết rằng φ đơn điệu và liên tục trên ∆, ∀y ∈ ∆ kí hiệu Ω(y) là tập tất cả những x ∈ ∆ thoả mãn bất đẳng thức hφ (y) , y − xi ≥ 0. Từ đó chúng ta suy ra rằng Ω(y) là một tập lồi đóng. Từ bổ đề 1.1 suy ra rằng \ Sol (V I (φ, ∆)) = Ω (y). y∈∆ 12 Do đó Sol (V I (φ, ∆)) là tập lồi đóng.  Từ định lí 1.2 và bổ đề 1.4(i) suy ra rằng, nếu ∆ 6= ∅ và φ : ∆ → Rn đơn điệu mạnh và liên tục thì bài toán V I (φ, ∆) có nghiệm duy nhất. Trong phần tiếp theo, chúng ta xét bài toán bất đẳng thức biến phân trong trường hợp ràng buộc của ∆ là nón. 1.2. Bài toán bù Những điều kiện dẫn đến bài toán bù. Mệnh đề 1.5. Nếu ∆ là một nón lồi đóng, thì bài toán V I (φ, ∆) có thể viết lại tương đương như sau x ∈ ∆, φ(x) ∈ ∆+ , hφ(x), xi = 0. (1.13) Ở đó ∆+ = {ξ ∈ Rn : hξ, vi > 0, ∀v ∈ ∆} kí hiệu cho nón đối ngẫu dương của ∆. Chứng minh. Cho x là một nghiệm của (1.4) Với bất kỳ v ∈ ∆ vì ∆ là một nón lồi, chúng ta có x + v ∈ ∆. Từ (1.4) chúng ta kết luận rằng 0 6 hφ (x) , (x + v) − xi = hφ (x) , vi . Vậy φ (x) ∈ ∆+ . Hơn nữa, vì 12 x ∈ ∆ và 2x ∈ ∆, theo (1.4) chúng ta có   1 1 0 ≤ φ (x) , x − x = − hφ (x) , xi , 2 2 và 1 hφ (x) , xi . 2 ⇒ hφ(x), xi = 0. 0 6 hφ (x) , 2x − xi = Bây giờ, lấy x sao cho (1.13) đúng. Với bất kỳ y ∈ ∆, vì hφ (x) , xi = 0 và φ (x) ∈ ∆+ , chúng ta có hφ (x) , y − xi = hφ (x) , yi > 0. Điều đó suy ra rằng x ∈ Sol (V I (φ, ∆)).  13 Định nghĩa 1.3. Bài toán (1.13), ở đó ∆ ⊂ Rn là một nón lồi, đóng và φ : Rn → Rn được kí hiệu bởi N CP (φ, ∆) và gọi là bài toán bù xác định bởi φ và ∆. 1.3. Bất đẳng thức biến phân affine Nếu x là một nghiệm địa phương của bài toán toàn phương   1 T min f (x) = x M x + q T x : x ∈ ∆ , 2 (1.14) là ma trận đối xứng cấp n, q ∈ Rn và ∆ ⊂ Rn là một đa ở đó M ∈ Rn×n s diện lồi, thì hM x + q, y − xi > 0, ∀y ∈ ∆. Điều đó suy ra rằng x là một nghiệm của bài toán V I(φ, ∆). Ở đó φ (x) = M x + q là một toán tử affine với M là ma trận Jacobian đối xứng cố định. Định nghĩa 1.4. Cho M ∈ Rn×n , q ∈ Rn , ∆ ⊂ Rn là một đa diện lồi. Bài toán bất đẳng thức biến phân Tìm x ∈ ∆ sao cho hM x + q, y − xi > 0, ∀y ∈ ∆, (1.15) được gọi là bất đẳng thức biến phân affine xác định bởi các dữ kiện {M, q, ∆} và kí hiệu bởi AV I (M, q, ∆). Tập nghiệm của bài toán này được viết ngắn gọn là Sol (AV I (M, q, ∆)). Định lí sau đây chứng tỏ rằng nghiệm của bài toán AV I(M, q, ∆) có thể biểu thị bởi nhân tử Lagrange. Bổ đề 1.2. (Bổ đề Farkas) Cho A ∈ Rm×n , b ∈ Rm . Khi đó trong hai hệ dưới đây có một và chỉ một hệ có nghiệm Ax > 0, bT x < 0, x ∈ Rm , AT = b, y > 0, y ∈ Rm . 14
Đặt λi = 0, ∀i ∈ I1 và λ = λ1 , λ2 , ..., λm ∈ Rm . Vì ai = ATi , ∀i = 1, 2, ...m. Từ (1.18) ta thu được bất đẳng thức thứ nhất trong (1.17). Vì x ∈ ∆ (A, b) và λi (Ai x − bi ) = 0 với một i ∈ I điều kiện còn lại trong (1.17) cũng được thoả mãn. Định lý 1.3. [14] Cho ∆ = {x ∈ Rn : Ax > b} , (1.16) với A ∈ Rm×n , b ∈ Rm . Khi đó x ∈ Rn là một nghiệm của (1.15) khi và chỉ
khi tồn tại λ = λ1 , λ2 , ..., λm ∈ Rm sao cho  T   Mx − A λ + q = 0 Ax > b, λ > 0 (1.17)  T  λ (Ax − b) = 0 Chứng minh. Chúng ta kí hiệu Ai là cột thứ i của ma trận A và bi là tọa độ thứ i của véc tơ b. Ta đặt ai = ATi , ∀i = 1, 2, ...m. Giả sử x ∈ Sol (AV I (M, q, ∆)). Ta đặt I = {1, 2, ..., m} , I0 = {i ∈ ∆ : hai , xi = bi } , và I1 = {i ∈ I : hai , xi > bi } . Giả sử bất kỳ v ∈ Rn thoả mãn hai , vi > 0, ∀i ∈ I0 . Chúng ta dễ dàng thấy rằng tồn tại δ1 > 0 sao cho hai , x + tvi > bi , ∀i ∈ I và t ∈ (0; δ1 ). Thay y = x + tv, ở đó t ∈ (0; δ1 ), vào (1.15) dẫn đến hM x + q, vi > 0. Thật vậy,h−M x − q, vi 6 0. Cho bất kỳ v ∈ Rn thoả mãn h−ai , vi 6 0, ∀i ∈ I0 . Theo bổ đề Farakas, tồn tại số thực không âm λi , (i ∈ I0 ) sao 15 cho X λi (−ai ) = −M x − q. (1.18) i∈I Trong phần tiếp theo ta chứng minh điều kiện đủ, giả sử rằng tồn
tại λ = λ1 , λ2 , ..., λm ∈ Rm sao cho (1.17) đúng. Khi đó, cho y ∈ ∆ chúng ta cũng có  hM x + q, y − xi = AT λ, y − x  = λ, (Ay − b) − (Ax − b)  = λ, (Ay − b) − (Ax − b) T T = λ (Ay − b) − λ (Ax − b) T = λ (Ay − b) > 0. Điều đó chứng tỏ rằng x là một nghiệm của (1.15). Đó là điều phải chứng minh.  Từ định lí 1.3 chúng ta có thể suy ra hai hệ quả sau đây. Một trong hai hệ quả đó là ứng dụng cho trường hợp mà ở đó ∆ biểu diễn dạng ∆ = {x ∈ Rn : Ax ≥ b, x ≥ 0} , (1.19) và hệ quả còn lại ứng dụng trường hợp mà ở đó ∆ biểu diễn dạng ∆ = {x ∈ Rn : Ax > b, Cx = d} . (1.20) Hệ quả 1.1. Cho ∆ được xác định bởi công thức (1.19). Khi đó x ∈ Rn
là một nghiệm của (1.15) khi và chỉ khi tồn tại λ = λ1 , λ2 , ..., λm ∈ Rm sao cho      xT M x − AT λ + q > 0 Ax > b, x > 0, λ > 0
T M x − AT λ + q + λ (Ax − b) = 0 (1.21) (m×n)×n e Chứng minh. Định ma và véc tơ eb ∈ Rm×n xác  nghĩa   trận  A∈R e = A , eb = b . Khi đó, bài toán (1.15), ở đó ∆ được định bởi A E 0 16 e xác n định bởi côngothức (1.19) thì tương đương với bài toán: Tìm x ∈ ∆ := e e > eb sao cho hM x + q, y − xi > 0, ∀y ∈ ∆. x ∈ Rn : Ax Ứng dụng định lí 1.3 vào bài toán AV I này chúng ta kết luận rằng x e = (λ1 , λ2 , ..., λm+2s ) ∈ Rm+2s là một nghiệm của bài toán khi và chỉ khi λ sao cho   T e e e e e e e M x − A λ + q = 0, Ax > b, λ > 0, λ Ax − b = 0, T
với λ = λ1 , λ2 , ..., λm ∈ Rm . Ở đó, λi = λi , ∀i ∈ {1, 2, ..., m}. Chúng ta có thể thu được các tính chất trong (1.21) từ những điều trên. Hệ quả 1.2. Cho ∆ được xác định bởi công thức (1.20). Khi đó x ∈ Rn
là một nghiệm của (1.15) khi và chỉ khi tồn tại λ = λ1 , λ2 , ..., λm ∈ Rm và µ = (µ1 , µ2 , ..., µs ) ∈ Rs sao cho  T T   Mx − A λ − C µ + q = 0 Ax > b, Cx = d, λ > 0  T  λ (Ax − b) = 0 (1.22) e ∈ R(m+2s)×n và eb ∈ Rm×2s . Khi đó, bài toán Chứng minh. Định nghĩa A (1.15) ở đó, ∆ xác định bởi (1.20) là tương đương với bài toán n o n e e e e Tìm x ∈ ∆ := x ∈ R : Ax > b sao cho hM x + q, y − xi > 0, ∀y ∈ ∆. Ứng dụng định lí 1.3 vào bài toán AV I này chúng ta kết luận rằng x e = (λ1 , λ2 , ..., λm+2s ) ∈ Rm+2s là một nghiệm của bài toán khi và chỉ khi λ sao cho   Te T e e e e e e e M x − A λ + q = 0, Ax > b, λ > 0, λ Ax − b = 0
với λ = λ1 , λ2 , ..., λm ∈ Rm và µ = (µ1 , µ2 , ..., µs ) ∈ Rs Ở đó, λi = λi , ∀i ∈ {1, 2, ..., m} và µj = λm+j − λm+s+j , ∀j ∈ {1, 2, ..., s} . 17 Chúng ta có thể thu được các tính chất trong (1.22) từ những điều trên. Định lý 1.4. Tập nghiệm của bài toán bất đẳng thức biên phân affine là hợp hữu hạn những tập đa diện lồi. Chứng minh. Xét bài toán AV I tổng quát từ (1.15). Vì ∆ là một tập đa diện lồi, nên tồn tại m ∈ N, A ∈ Rm×n , b ∈ Rm sao cho ∆ = {x ∈ Rn : Ax > b}. Theo định lí 1.3 x ∈ Sol (AV I (M, q, ∆)) khi và chi khi   M x − AT λ + q = 0 Ax > b, λ > 0  λT (Ax − b) = 0 (1.23) Cho I (1, 2, ..., m) lấy một điểm x ∈ Sol (AV I (M, q, ∆)), chúng ta gọi I0 = {i ∈ I : Ai x = bi } , I1 = I\I0 = {i ∈ I : Ai x > bi }. Từ bất đẳng thức trên trong (1.23) chúng ta có được λi = 0, ∀i ∈ I1 . Do đó (x, λ) thoả mãn hệ thức   M x − AT λ + q = 0 A x = bI0 , λI0 > 0  I0 AI1 x > bI1 , λI1 = 0 (1.24) Cố định tập I0 ⊂ I và tập QI0 xác định bởi tất cả (x, λ) thoả mãn (1.24). Từ đó suy ra rằng QI0 là tập đa diện lồi. Từ đó, ta có điều sau đây Sol (AV I (M, q, ∆)) = ∪ {PrRn (QI0 ) : I0 ⊂ I} . (1.25) Ở đó, PrRn (x, λ) := x. Vì PrRn (.) : Rn × Rn → Rn là một toán tử tuyến tính, cho bất kỳ I0 ⊂ I, PrRn (QI0 ) là một tập đa diện lồi. Từ (1.25) chúng ta có điều sau đây Sol (AV I (M, q, ∆)) là hợp hữu hạn các tập đa diện lồi.  Định nghĩa 1.5. Một nửa đường thẳng ωδ = {x + tv : t > 0}, ở đó v ∈ Rn \ {0} và δ > 0, mà là một tập con của Sol (AV I (M, q, ∆)) thì được gọi là một tia nghiệm của bài toán (1.15). 18 Định nghĩa 1.6. Một đoạn thẳng ωδ = {x + tv : t ∈ [0; δ)}, ở đó v ∈ Rn \ {0} và δ > 0, mà là một tập con của Sol (AV I (M, q, ∆)) thì được gọi là một khoảng nghiệm của bài toán (1.15). Mệnh đề 1.6. [13]Các điều kiện sau đây là đúng i, Tập nghiệm của một bất đẳng thức biến phân affine là một tập đóng có thể rỗng. ii, Nếu tập nghiệm của một bài toán bất đẳng thức biến phân affine là không bị chặn thì bài toán này có một tia nghiệm. iii, Nếu tập nghiệm của một bài toán bất đẳng thức biến phân affine là hữu hạn thì bài toán này có một khoảng nghiệm. Chứng minh. Phát biểu i, tương ứng từ công thức (1.25) bởi vì, cho I0 ⊂ I, tập PrRn (QI0 ) là đa diện lồi thì nó đóng. Nếu Sol (AV I (M, q, ∆)) là không bị chặn thì từ (1.25) chúng ta có điều sau đây: Tồn tại một tập chỉ số I0 ⊂ I sao cho ΩI0 := PrRn (QI0 ) , (1.26) là một tập không bị chặn. Vì ΩI0 là một tập đa diện lồi, nó là một tập lồi đóng không bị chặn. [23], ΩI0 là một phương suy thoái. Điều đó có nghĩa là tồn tại v ∈ Rn \ {0} sao cho x + tv ∈ ΩI0 , x ∈ ΩI0 , ∀t > 0. (1.27) Lấy bất kỳ x ∈ ΩI0 từ (1.25) và (1.27) chúng ta kết luận rằng x + tv ∈ Sol (AV I (M, q, ∆)) , ∀t > 0. Vì vậy, chúng ta kết luận rằng bài toán (1.15) có tia nghiệm. Nếu Sol (AV I (M, q, ∆)) là hữu hạn thì từ (1,25) chúng ta kết luận rằng có một tập chỉ số I0 ⊂ I sao cho ΩI0 là tập đa diện lồi biểu diễn bởi (1.26) là hữu hạn. Khi đó, có chắc chắn hai điểm khác nhau x ∈ ΩI0 , y ∈ ΩI0 . Chúng ta có thể kết luận rằng tập [x; y) := {x + t (y − x) : t ∈ [0; 1)} là một khoảng nghiệm của (1.15).  19 Sử dụng định lí 1.4, chúng ta có thể thu được một mở rộng mô tả cho tính không đóng tập nghiệm của một bài toán AV I. Tiếp theo chúng ta xét bài toán (1.15), ở đó ∆ cho bởi (1.16) và đưa vào các kí hiệu sau đây δ (A) = {v ∈ Rn : Av > 0}  δ (A)+ = z ∈ Rn : z T v > 0, ∀v ∈ δ (A)  Chú ý rằng δ (A) và v ∈ Rn : Av ∈ δ (A)+ là những nón đa diện lồi; Trong đó, l (M ) là một nón đóng, không lồi trong trường hợp tổng quát. Chú ý
+ δ (A) = 0+ ∆ và δ (A)+ = 0+ ∆ . Định lý 1.5. [14] Tập nghiệm của (1.15) là không bị chặn khi và chỉ khi
tồn tại một cặp v; u0 ∈ Rn × Rn , v 6= 0, u0 ∈ Sol (AV I (M, q, ∆)) sao cho i, v ∈ δ (A) , M v ∈ δ (A)+ , v ∈ l (M )
T ii, M u0 + q v = 0  iii, M v, y − u0 > 0, ∀y ∈ ∆ Chứng minh.
Điều kiện cần. Giả sử rằng có một cặp v; u0 ∈ Rn × Rn , v 6= 0, u0 ∈ Sol (AV I (M, q, ∆)), sao cho i, ii, iii, được thoả mãn. Lấy xt = u0 +tv, t > 0. Lấy bất kỳ y ∈ ∆, từ i, ii, iii, chúng ta kết luận rằng xt ∈ Sol (AV I (M, q, ∆)) , ∀t > 0. Do đó, tập nghiệm của nó là không bị chặn. Điều kiện đủ. Giả sử tập Sol (AV I (M, q, ∆)) là không bị chặn. Theo (1.25) tồn tại I0 ⊂ I sao cho ΩI0 biểu diễn bởi (1.26) là không bị chặn. Từ định lí 8.4 [23], chúng ta có thể suy ra rằng tồn tại v ∈ Rn , v 6= 0 và u0 ∈ ΩI0 sao cho u0 + tv ∈ ΩI0 ⊂ Sol (AV I (M, q, ∆)) , ∀t > 0. (1.28)
Vì A u0 + tv > b, ∀t > 0, chúng ta có thể kết luận rằng Av > 0. Điều đó có nghĩa rằng v ∈ δ (A). Theo (1.28) chúng ta có

 M u0 + tv + q, y − u0 + tv > 0, ∀y ∈ ∆. (1.29) 20 Cố định bất kỳ y ∈ ∆, từ (1.29) chúng ta kết luận rằng   1 1 1 0 1 0 M u + M v + q, y − u − v > 0, ∀t > 0. t t t t Bởi vậy hM v, −vi > 0. (1.30) Thay y = u0 + t2 v, ở đây t > 1, vào (1.29) và chia bất đẳng thức cho
t t2 − t chúng ta thu được   1 1 M u0 + M v + q, v > 0, ∀t > 1 t t Cho t → +∞ suy ra hM v, vi > 0. Kết hợp với (1.30) chúng ta có hM v, −vi = 0. (1.31) Điều đó chứng tỏ rằng v ∈ l (M ). Thay y = u0 vào (1.29) và thay  tiếp vào (1.31) chúng ta được M u0 + q, v 6 0. Thay y = u0 + t2 v, ở đó t > 1 vào (1.29) và sử dụng (1.31) chúng ta có thể kết luận rằng  M u0 + q, v > 0. Từ đó và từ bất đẳng thức ở trước suy ra rằng ii, thoả mãn. Theo (1.29), ( 1.31) và ii, ∀y ∈ ∆ chúng ta có   0 6 M u0 + q + tM v, y − u0 − tv = M u0 + q, y − u0 +  + t M v, y − u0 , ∀t > 0.  Từ đó suy rằng bất đẳng thức M v, y − u0 < 0, ∀y ∈ ∆ là sai. Vì vậy chúng ta có  M v, y − u0 > 0, ∀y ∈ ∆. (1.32) Thay y = u0 + ω ở đó ω ∈ δ (A). Điều đó có nghĩa là M v ∈ δ (A)+ . Vì vậy, chúng ta kết luận rằng cả ba kết luận trong i, đều đúng.  Một vài điều kiện đủ cho (1.15) về tính compact của tập nghiệm có thể thu trực tiếp từ định lí trên.