ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC TRẦN VŨ MINH HOÀNG ĐẶC TRƯNG CHO TẬP NGHIỆM CỦA BÀI TOÁN QUY HOẠCH LỒI VÀ BÀI TOÁN BẤT ĐẲNG THỨC BIẾN PHÂN LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên – 2015 Mục lục Mở đầu 1 Kiến thức chuẩn bị 1.1 Một số kiến thức giải tích lồi 1.2 Bài toán tối ưu toán bất đẳng thức biến phân 11 Đặc trưng cho tập nghiệm toán quy hoạch lồi toán bất đẳng thức biến phân 14 2.1 Đặc trưng cho tập nghiệm trường hợp f khả vi Gâteaux 14 2.2 Đặc trưng tập nghiệm qua vi phân 21 2.3 Đặc trưng tập nghiệm toán bất đẳng thức biến phân Kết luận 28 36 Tài liệu tham khảo 37 i Mở đầu Lý chọn đề tài O L Mangasarian (1988) chứng minh tập nghiệm toán lồi: (P ) M in {f (x) : x ∈ C} , C ⊂ Rn , f : Rn → R Có thể đặc trưng gradient f f khả vi liên tục hai lần tập mở chứa C đặc trưng vi phân f f liên tục phần tương đối tập nghiệm khác rỗng Z L Wu S Y Wu (2006) chứng minh với toán lồi (P) không gian định chuẩn với hàm mục tiêu khả vi Gâteaux nghiệm tối ưu tập nghiệm bao gồm điểm chấp nhận nằm siêu phẳng mà véctơ pháp tuyến đạo hàm Gâteaux Với tốn quy hoạch lồi liên tục, điểm chấp nhận nghiệm nằm siêu phẳng với vectơ pháp tuyến thuộc vi phân hàm mục tiêu điểm Đồng thời đặc trưng tập nghiệm toán bất đẳng thức biến phân Đây đề tài nhiều tác giả quan tâm nghiên cứu Chính em chọn đề tài "Đặc trưng cho tập nghiệm toán quy hoạch lồi bất đẳng thức biến phân" Mục đích luận văn Luận văn trình bày kết đặc trưng cho tập nghiệm toán quy hoạch lồi toán bất đẳng thức biến phân Z L Wu S Y Wu đăng J Optim Theory Appl (2006) Nội dung luận văn Luận văn bao gồm phần mở đầu, hai chương, kết luận danh mục tài liệu tham khảo Chương Kiến thức chuẩn bị Trình bày số kiến thức giải tích lồi như: Phần tương đối, vi phân hàm lồi, phép tính vi phân hàm lồi Chương trình bày tốn quy hoạch lồi, toán bất đẳng thức biến phân, toán bất đẳng thức biến phân đối ngẫu hàm sai khác đối ngẫu toán bất đẳng thức biến phân xét chương Chương 2.Đặc trưng cho tập nghiệm toán quy hoạch lồi tốn bất đẳng thức biến phân Trình bày tính chất đặc trưng cho tập nghiệm toán quy hoạch lồi trường hợp hàm mục tiêu khả vi Gâteaux, trường hợp toán quy hoạch lồi liên tục toán bất đẳng thức biến phân Z L Wu S Y Wu ([13], 2006) Trong trường hợp hàm mục tiêu toán quy hoạch lồi khả vi Gâteaux, tập nghiệm nằm siêu phẳng mà vectơ pháp tuyến đạo hàm Gâteaux hàm mục tiêu Trong trường hợp quy hoạch lồi liên tục, điểm chấp nhận nghiệm tối ưu nằm siêu phẳng mà vectơ pháp tuyến thuộc vi phân hàm mục tiêu điểm Trong số trường hợp tập nghiệm toán bất đẳng thức biến phân trùng với tập nghiệm toán quy hoạch lồi với hàm sai khác đối ngẫu hàm mục tiêu Nhân dịp xin chân thành cảm ơn PGS.TS Đỗ Văn Lưu, người hướng dẫn tận tình, giúp đỡ tơi hồn thành luận văn Tôi xin chân thành cảm ơn Ban chủ nhiệm Khoa Toán-Tin Trường Đại học Khoa học - Đại học Thái Nguyên thầy cô giáo tham gia giảng dạy khóa học Xin chân thành cảm ơn gia đình, bạn bè đồng nghiệp thành viên lớp Cao học Tốn K7A ln quan tâm động viên giúp đỡ tơi suốt q trình làm luận văn Thái Nguyên, ngày 20 tháng 05 năm 2015 Tác giả Trần Vũ Minh Hoàng Chương Kiến thức chuẩn bị Chương trình bày số kiến thức giải tích lồi như: Phần tương đối, vi phân hàm lồi, phép toán vi phân hàm lồi, hàm khả vi Gâteaux Chương trình bày tốn quy hoạch lồi, toán bất đẳng thức biến phân, toán bất đẳng thức biến phân đối ngẫu hàm sai khác đối ngẫu xét chương Các kiến thức trình bày chương tham khảo [1], [13] 1.1 Một số kiến thức giải tích lồi Giả sử X khơng gian tuyến tính trường số thực Định nghĩa 1.1.1 Tập A ⊂ X gọi lồi nếu: ∀x1 , x2 ∈ A, ∀λ ∈ R : ≤ λ ≤ ⇒ λx1 + (1 − λ) x2 ∈ A, R tập số thực Định nghĩa 1.1.2 a) Tập K ⊂ X gọi nón có đỉnh 0, nếu: ∀x ∈ K, ∀λ > ⇒ λx ∈ K K gọi nón có đỉnh x0 , K − x0 nón có đỉnh b) Nón K có đỉnh gọi nón lồi, K tập lồi có nghĩa là: ∀x, y ∈ K, ∀λ, µ > ⇒ λx + µy ∈ K Định nghĩa 1.1.3 Phần tương đối tập A ⊂ Rn phần A affA; Kí hiệu riA, affA bao affine tập A Như riA = {x ∈ affA :∃ε > 0, (x + εB) ∩ affA ⊂ A}, B hình cầu đơn vị Rn Định nghĩa 1.1.4 Trên đồ thị hàm f : D ⊂ X → R, ký hiệu epif, định nghĩa sau: epif = {(x, r) ∈ D × R : f (x) ≤ r} Định nghĩa 1.1.5 Hàm f : D ⊂ X → R gọi thường nếu: domf = ∅ f (x) > −∞ (∀x ∈ D) , domf = {x ∈ D : f(x) < +∞} Định nghĩa 1.1.6 Hàm f gọi lồi D epif tập lồi X × R Hàm f gọi lõm D −f hàm lồi D Giải sử f hàm xác định không gian lồi địa phương HausdorffX, f X < +∞ Định nghĩa 1.1.7 Đạo hàm hàm f theo phương d x , ký hiệu f (x; d) định nghĩa giới hạn sau: f (x; d) = lim λ↓0 f (x + λd) − f (x) λ Nếu giới hạn tồn (có thể hữu hạn ±∞) Định lí 1.1.1 Giả sử f hàm lồi thường X Khi f có đạo hàm theo phương điểm x ∈ domf Đồng thời, f (x + λd) − f (x) f (x; d) = inf λ λ>0 Nhận xét 1.1.1 Nếu f lồi thường X , x ∈ domf f (x, ) hàm lồi Giả sử f hàm lồi X Định nghĩa 1.1.8 Phiếm hàm x∗ ∈ X ∗ gọi gradient (subgradient) f x ∈ X nếu: f (x) − f (x) ≥ x∗ , x − x (∀x ∈ X) Định nghĩa 1.1.9 Tập tất gradient f x gọi vi phân (subdifferential) f x, ký hiệu ∂f (x), tức là: ∂f (x) = {x∗ ∈ X ∗ : f (x) − f (x) ≥ x∗ , x − x , ∀x ∈ X} Định lí 1.1.2 Giả sử f hàm lồi thường X x ∈ domf Khi đó, x∗ ∈ ∂f (x) ⇔ f (x; d) ≥ x∗ , d (∀d ∈ X) Chứng minh Nếu x∗ ∈ ∂f (x) ∀d ∈ X, λ > 0, ta có: f (x + λd) − f (x) ≥ λ x∗ , d Theo Định lý 1.1.1, f có đạo hàm x theo phương d, cho nên: f (x; d) ≥ x∗ , d (1.1) Ngược lại, (1.1) đúng, ta lấy x ∈ X, d = x − x, từ Định lý 1.1.1, ta nhận được: x∗ , x − x ≤ f (x; x − x) ≤ f (x + (x − x)) − f (x) Do đó, x∗ ∈ ∂f (x) Định lí 1.1.3 Giả sử f hàm lồi thường X x ∈ domf Khi đó, x∗ ∈ ∂f (x) ⇔ f (x) + f ∗ (x∗ ) = x∗ , x Chứng minh Giả sử x∗ ∈ ∂f (x) Khi đó, f (x) − f (x) ≥ x∗ , x − x (∀x ∈ X) ⇒ x∗ , x − f (x) ≥ x∗ , x − f (x)(∀x ∈ X) ⇒ x∗ , x − f (x) ≥ sup{ x∗ , x − f (x)}(∀x ∈ X) = f ∗ (x∗ ) (1.2) Mặt khác, theo bất đẳng thức Young-Fenchel x∗ , x − f (x) ≤ f ∗ (x∗ ) (1.3) Từ (1.2) (1.3) suy ra: f (x) + f ∗ (x∗ ) = x∗ , x (1.4) Giả sử (1.4)đúng Từ bất đẳng thức Young-Fenchel với λ > 0, d ∈ X , ta có: f (x + λd) ≥ x∗ , x + λd − ( x∗ , x − f (x)) x∗ , λd f (x + λd) − f (x) ≥ = x∗ , d ⇒ λ λ ∗ ⇒ f (x; d) ≥ x , d (∀d ∈ X) ⇒ x∗ ∈ ∂f (x) Ví dụ 1.1.1 Cho hàm affine f (x) = x∗ , x + α (x∗ ∈ X ∗ , α ∈ R) Khi đó, ∂f (x) = {x∗ } (∀x ∈ X) Ví dụ 1.1.2 Cho hàm f (x) = δ (.| A), A tập lồi khác ∅ Khi đó, với x ∈ A, x∗ ∈ ∂δ (x| A) ⇔ δ (x| A) ≥ δ (x| A) + x∗ , x − x (∀x ∈ X) ⇔ x∗ , x − x ≤ (∀x ∈ A) Điều có nghĩa x∗ véctơ pháp tuyến A x Như vậy, ∂δ (x| A) nón pháp tuyến A x, ∂δ (x| A) = N (x| A) / A, ∂δ (x| A) = ∅ Chú ý: Với x ∈ Ví dụ 1.1.3 X = R, f (x) = |x| Với x = 0: f hàm khả vi, : ∂f (x) = |x|−1 x Với x = 0: ∂f (0) = {ξ ∈ R : |z| ≥ ξ, z , ∀z ∈ R} = {ξ ∈ R : |ξ| ≤ 1} = [−1, 1] Định nghĩa 1.1.10 Hàm f gọi khả vi Gâteaux x ∈ X , ∃x∗ ∈ X ∗ cho với d ∈ X , f (x + td) = f (x) + t x∗ , d + o (t) (1.5) Khi đó, ta gọi x∗ đạo hàm Gâteaux f x: f G (x) = x∗ Định lí 1.1.4 Giả sử f hàm lồi X Khi đó, a)Nếu f khả vi Gâteaux x với đạo hàm Gâteaux x x∗ Định lí 2.2.1 Giả sử C tập lồi không gian Banach X , f lồi liên tục C , C nghiệm toán {f (x) : x ∈ C} Nếu x∗ ∈ C C = C1 = C2 = C3 = C4 = C5 = C , C1 := x ∈ C : ξ, x − x∗ = 0, với ξ ∈ ∂f (x) ∩ ∂f (x∗ ) , C2 := x ∈ C : ξ, x − x∗ ≤ 0, với ξ ∈ ∂f (x) ∩ ∂f (x∗ ) , C3 := {x ∈ C : ξ, x − x∗ = η, x − x∗ = 0, với ξ ∈ ∂f (x), η thuộc ∂f (x∗ )}, C4 := {x ∈ C : ξ, x − x∗ = η, x − x∗ ≤ 0, với ξ ∈ ∂f (x), η thuộc ∂f (x∗ )}, C5 := x ∈ C : ξ, x − x∗ = 0, với ξ ∈ ∂f (x) , C6 := x ∈ C : ξ, x − x∗ ≤ 0, với ξ ∈ ∂f (x) Chứng minh Bởi C1 ⊆ C2 ⊆ C4 ⊆ C6 C1 ⊆ C3 ⊆ C5 ⊆ C6 hiển nhiên C6 ⊆ C suy f (x∗ ) ≥ f (x) + ξ, x∗ − x ≥ f (x) ≥ f (x∗ ) , với x ∈ C6 ξ thuộc ∂f (x), ta cần C¯ ⊆ C1 Giả sử x ∈ C x = x∗ Khi đó, xt := tx∗ + (1 − t) x ∈ C, với t ∈ (0, 1) , f (x∗ ) ≤ f (xt ) ≤ tf (x∗ ) + (1 − t) f (x) = f (x∗ ) Từ ta có f (xt , x − x∗ ) = Bây giờ, với y := xt với t = 1/2, hàm lồi f liên tục y , ta có ∂f (y) = ∅ Theo Bổ đề 2.2.1, ta có ∂f (y) = ∂f (x∗ ) ∩ ∂f (x) 24 Hơn nữa, Mệnh đề 2.1.2 2.2.7 [4], tồn ξ ∈ ∂f (y) cho f (y, y − x∗ ) = ξ, y − x∗ = ξ, x − x∗ Bởi f (y, y − x∗ ) = 0, ta có ξ, x − x∗ = 0, với ξ ∈ ∂f (x∗ ) ∩ ∂f (x) Vì vậy, x ∈ C1 Nhận xét 2.2.1 Ta biết hàm lồi giá trị thực f Rn liên tục Khi áp dụng Định lý 2.2.1 ta nhận Định lý 1a [9] Do Định lý 2.2.1 mở rộng Định lý 1a [9] cho không gian Banach X Tương tự, Định lý 4.1 [14] phát biểu C = C1 = C5 khơng gian tuyến tính định chuẩn X ∈ int (C − domf ), domf := {x ∈ X : f (x) < +∞} Không giống Định lý 1a [9], ta không giả thiết phần tương đối C khác rỗng Định lý 2.2.1 Điều có ý nghĩa, Định lý 1a [9] khơng áp dụng cho tốn có hàm mục tiêu liên tục lồi chặt C Chẳng hạn, C = [0, 1] f (x) = x2 , với x ∈ [−1, +∞) , +∞, với x ∈ (−∞, −1) Ta thấy x = nghiệm tối ưu toán tương ứng Tuy nhiên, Định lý 1a [9] khơng cho tốn này, Định lý 2.2.1 lại Để bổ sung cho Định lý 1a [9], Burke Ferris [3] đặc trưng C cách mơ tả xác gradient f Rn Với điều kiện giống Định lý 2.2.1, kết luận Hệ 2.2.1 Giả sử C, f, C,x∗ Định lý 2.2.1 Khi đó, C = {x ∈ C : ∂f (x) ∩ [−Nc (x)] = ∂f (x∗ ) ∩ [−Nc (x∗ )]} Chứng minh 25 Giả sử C1 Định lý 2.2.1 Bởi hàm lồi f liên tục C , theo Mệnh đề 5.6 [5],ta có ∈ ∂f (x∗ ) + Nc (x∗ ) , tức , ∂f (x∗ ) ∩ [−Nc (x∗ )] = ∅ Như vậy, ta cần bao hàm thức đầu C ⊆ {x ∈ C : ∂f (x) ∩ [−Nc (x)] = ∂f (x∗ ) ∩ [−Nc (x∗ )]} ⊆ C1 , C = C1 bao hàm thức thứ hai Thật vậy, ta chứng minh điều sau đủ, ∂f (x) ∩ [−Nc (x)] ⊆ ∂f (x∗ ) ∩ [−Nc (x∗ )] , với x ∈ C Giả sử x ∈ C ξ ∈ ∂f (x) ∩ [−Nc (x)] Khi đó, f (y) − f (x) ≥ ξ, y − x , ∀y ∈ X, ξ, c − x ≥ 0, ∀c ∈ C Bằng cách lấy y = x∗ c = x∗ , ta ξ, x∗ − x = Từ ta có f (y) − f (x∗ ) = f (y) − f (x) ≥ ξ, y − x = ξ, y − x∗ , ∀y ∈ X, ξ, c − x∗ ≥ 0,∀c ∈ C, nghĩa ξ ∈ ∂f (x∗ ) ∩ [−Nc (x∗ )] Nhắc lại rằng, với y ∈ X , tập xấp xỉ tốt cho y từ C Bc (y) := {x ∈ C : x − y = inf { c − y : c ∈ C}} 26 Áp dụng Định lý 2.2.1 cho f (y) = x − y , ta nhận đặc trưng sau Bc (y) mà kết khơng thể dẫn từ Định lý 1a [9] chí Rn Hệ 2.2.2 Giả sử C tập lồi đóng khác rỗng không gian Banach X , y ∈ X\C x∗ ∈ Bc (y) Khi đó, Bc (y) = C1 = C2 = C3 = C4 = C5 = C6 , C1 , C2 , C3 , C4 , C5 , C6 Định lý 2.2.1 với f (x) = x − y với x ∈ X ∂f (c) = {ξ ∈ X ∗ : ξ = 1, ξ, c − y = c − y } , ∀c ∈ C Nếu X không gian Hilbert Bc (y) = {x∗ } Chứng minh Ta cần Bc (y) = {x∗ } khơng gian Hilbert X Bởi vì: BC (y) = C1 = {x ∈ C : ξ, x − x∗ = 0, với ξ ∈ X ∗ , ξ = 1, ξ, x − y = x − y , ξ, x∗ − y = x∗ − y }, bất đẳng thức Cauchy-Schwarz, (x − y)/ x − y = ξ = (x∗ − y)/ x∗ − y , ∀x ∈ Bc (y) , Từ suy x = x∗ , f (x) = f (x∗ ) , ∀x ∈ Bc (y) Nhận xét 2.2.2 Biểu diễn Bc (y) = C5 = C6 Hệ 2.2.2 trình bày Jeyakumar [7] Các biểu diễn khác Bc (y) hệ hữu ích Chẳng hạn, Bc (y) = {x∗ } không gian Hilbert X suy từ Bc (y) = C1 27 2.3 Đặc trưng tập nghiệm toán bất đẳng thức biến phân Nhắc lại C∗ tập nghiệm toán {G (x) : x ∈ C} mà Định lý 2.1.1 áp dụng hàm sai khác đối ngẫu G VIP(C,F) khả vi Gâteaux x∗ ∈ C∗ Để biểu diễn C∗ đặc biệt trường hợp này, ta cần sử dụng dạng kết sau: Mệnh đề 2.3.1 Với x ∈ X , ta có (i) Nếu G (x) < +∞ {F (y) : y ∈ Λ (x)} ⊆ ∂G (x) Nói riêng, {F (y) : y ∈ C ∗ ∪ {x}} ⊆ ∂G (x) , với x ∈ C∗ (ii) Nếu Λ (x) khác rỗng G khả vi Gâteaux x F không đổi Λ (x) G (x; v) = sup { F (y) , v : y ∈ Λ (x)} , ∀v ∈ X (2.4) Nói riêng, với x ∈ C∗ , G khả vi Gâteaux x C ∗ = Λ (x), F không đổi C ∗ G (x; v) = sup { F (y) , v : y ∈ C ∗ } , ∀v ∈ X Chứng minh (i) Với y ∈ Λ (x), G (x) = (F (y) , x − y) , ta có G (z)−G (x) ≥ F (y) , z − y − F (y) , x − y = F (y) , z − x , ∀z ∈ X Như vậy, F (y) ∈ ∂G (x) Bởi x ∈ C∗ , ta có x ∈ Λ (x) ≤ F (x∗ ) , x − x∗ ≤ G (x) = 0,∀x∗ ∈ C ∗ , tức là, C ∗ ⊆ Λ (x), ta có {F (y) : y ∈ C ∗ ∪ {x}} ⊆ ∂G (x) , với x ∈ G∗ (ii) Bởi Λ (x) khác rỗng, (i), ∂G (x) = ∅ Nếu ∇G (x) đạo hàm Gâteaux G x ∂G (x) = {∇G (x)}và lại theo (i) ta có F (y) = ∇G (x) ,∀y ∈ Λ (x) 28 Điều kéo theo (2.4) Ngược lại, F số Λ (x) thỏa mãn (2.4) từ (i) ta suy với y ∈ Λ (x), G (x, v) = F (y) , v , với v ∈ X Vì vậy, G khả vi Gâteaux x Ta phải chứng minh C ∗ = Λ (x) G khả vi Gâteaux x ∈ C∗ Bao ham thức C ∗ ⊆ Λ (x) chứng minh Vì vậy, ta cần Λ (x) ⊆ C ∗ Lấy y ∈ Λ (x) Khi đó, F (y) = F (x) Vì C lồi x nghiệm toán {G (c) : c ∈ C}, với c ∈ C , ta có F (y) , c − y = F (x) , c − x + F (y) , x − y = G (x; c − x) = lim+ [G (x + t (c − x)) − G (x)] /t ≥ t→0 Như vậy, y ∈ C ∗ Điều kết thúc chứng minh Nhận xét 2.3.1 Như Mệnh đề 2.3.1, Λ (x) khác rỗng x ∈ C G (x) = 0, với x ∈ C , G (x) = x ∈ Λ (x), nghĩa là, x ∈ C∗ Điều kiện đủ khác cho Λ (x) , x ∈ X khác rỗng C compăc F liên tục C Chú ý tính khác rỗng Λ (x) kéo theo tính khác rỗng ∂G (x) Ta ln có C ∗ ⊆ Λ (x∗ ) với x∗ ∈ C∗ Mệnh đề phát biểu C ∗ trùng với Λ (x∗ ) G khả vi Gâteaux x∗ ∈ C∗ , có nghĩa tập nghiệm VIP(C,F) khác rỗng đặc trưng C ∗ = {x ∈ C : F (x) , x − x∗ = 0} = {x ∈ C : F (x) , x − x∗ ≤ 0} Sử dụng Định lý 2.1.1, Mệnh đề 2.1.2 Mệnh đề 2.3.1, ta nhận biểu diễn sau cho C ∗ C∗ Định lí 2.3.1 29 Giả sử G khả vi Gâteaux x∗ ∈ C∗ Ký hiệu: C (x∗ ) : = x ∈ C : {v ∈ X : ξ, v ≥ 0} , với ξ thuộc ∂G (x) = v ∈ X : F (x∗ ) , v ≥ 0, với ξ thuộc ∂G (x) Khi đó, C∗ = C0 = C1 = C2 = C3 = C4 = C5 , C0 := x ∈ C : ξ, y − x ≥ 0, với ξ ∈ ∂G (x) y ∈ C , C1 := {x ∈ C : F (x∗ ) , x − x∗ = 0, F (x∗ ) ∈ ∂G (x)}, C2 := {x ∈ C (x∗ ) : F (x∗ ) , x − x∗ = 0} , C3 := x ∈ C : ξ, x − x∗ = F (x∗ ) , x − x∗ = 0, với ξ ∈ ∂G (x) , C4 := x ∈ C : ξ, x − x∗ = 0, với ξ ∈ ∂G (x) , C5 := x ∈ C : ξ, x − x∗ ≤ 0, với ξ ∈ ∂G (x) Hơn nữa, C ∗ = C∗ , C∗ = D0 = C1 = D2 = D3 = D4 = D5 = Λ (x∗ ) , D0 , D2 , D3 , D4 , D5 kí hiệu C0 , C2 , C3 , C4 , C5 với ξ thay F (x) Chứng minh Các đẳng thức C∗ = Ci ,i = 0, , 5, suy trực tiếp từ Định lý 2.1.1 Tiếp theo, ta có D2 ⊆ D3 ⊆ D4 = D5 ⊆ Λ (x∗ ) = C ∗ , đẳng thức sau suy từ Mệnh đề 2.3.1 Bây giờ, C∗ = C ∗ C ∗ = D0 Do đó, ta cần C ∗ ⊆ D2 Lấy x ∈ C ∗ Bởi C∗ = C ∗ , F (x) ∈ ∂G (x) ≥ F (x) , x − x∗ ≥ F (x∗ ) , x − x∗ ≥ ta suy ra, F (x) − F (x∗ ) , x − x∗ = 30 Theo Nhận xét 2.1.2, {F (x) , F (x∗ )} ⊆ ∂G (x) ∩ ∂G (x∗ ) ⊆ ∂G (x∗ ) = {F (x∗ )} Điều kéo theo F (x) = F (x∗ ) Như vậy, x ∈ D2 Nhận xét 2.3.2 Như phát biểu Nhận xét 2.1.3, đẳng thức (=0) C1 , C2 , C3 Định lý 2.3.1 thay bất đẳng thức (≤ 0) Điều nhận xét thích hợp cho kết sau mà từ ta nhận D3 = D4 Định lý 2.3.1 với G khả vi Gâteaux x∗ ∈ C∗ Định lí 2.3.2 Giả sử G khả vi Gâteaux x∗ ∈ C∗ Khi đó, C ∗ ∩ C∗ = C1 = C2 = C3 , C1 = {x ∈ C : F (x) , x − x∗ = F (x∗ ) , x − x∗ = 0, F (x) ∈ ∂G (x)} , C2 = {x ∈ C : F (x) , x − x∗ = 0,F (x) ∈ ∂G (x) ∩ ∂G (x∗ )} , C3 = {x ∈ C : F (x) , x − x∗ = 0,F (x) ∈ ∂G (x)} Vì vậy, C ∗ ⊆ C∗ C ∗ = C1 = C2 = C3 Nếu C∗ ⊆ C ∗ C∗ = C1 = C2 = C3 Chứng minh Ta có bao hàm thức C1 ⊆ C2 theo Nhận xét 2.1.2 ta có F (x) = F (x∗ ) ∈ ∂G (x∗ ) ;C2 ⊆ C3 hiển nhiên; C3 ⊆ C1 suy từ = F (x) , x − x∗ ≥ F (x∗ ) , x − x∗ ≥ 0,∀x ∈ C3 Vì vậy, ta phải C ∗ ∩ C∗ = C1 Lấy x ∈ C ∗ ∩ C∗ Khi đó, x ∈ C1 x ∈ C ∗ ⊆ Λ (x∗ ) , x ∈ Λ (x) , x∗ ∈ Λ (x∗ ) = C ∗ ⊆ Λ (x) , đẳng thức suy từ tính khả vi Gâteaux G x∗ ∈ C∗ Ngược lại, x ∈ C1 x ∈ Λ (x∗ ) = C ∗ x ∈ C∗ , G (x∗ ) ≥ G (x) + F (x) , x∗ − x = G (x) 31 Theo Định lý 2.2.1, với điều kiện G liên tục C , ta chứng minh biểu diễn cho C∗ Khơng có giả thiết liên tục tính khả vi Gâteaux tập C ∗ , C∗ đặc trưng Định lý 2.3.2 cho trường hợp C ∗ = C∗ dựa kết sau Định lí 2.3.3 Giả sử C ∗ ⊆ C∗ x∗ ∈ C∗ Khi đó, C ∗ ⊆ {x ∈ C : F (x) , x − x∗ = 0,F (x) ∈ ∂G (x) ∩ ∂G (x∗ )} = {x ∈ C : F (x) , x − x∗ ≤ 0,F (x) ∈ ∂G (x) ∩ ∂G (x∗ )} ⊆ {x ∈ C : F (x) , x − x∗ = 0,F (x) ∈ ∂G (x)} = {x ∈ C : F (x) , x − x∗ ≤ 0,F (x) ∈ ∂G (x)} ⊆ C∗ Nếu G khả vi Gâteaux F liên tục theo phương C∗ tập trùng Chứng minh Vì x∗ ∈ C∗ , ta có F (x) , x − x∗ ≥ 0,∀x ∈ C Từ đó, với x ∈ C , F (x) , x − x∗ = ⇔ F (x) , x − x∗ ≤ Điều kéo theo hai đẳng thức kết mong muốn Hơn nữa, bao hàm thức x∗ ∈ C ∗ ⊆ C∗ kéo theo C ∗ ⊆ Λ (x∗ ) Như vậy, x∗ ∈ C ∗ ⊆ C∗ x∗ ∈ Λ (x∗ ) ∩ Λ (x∗ ) Do đó, F (x∗ ) , x∗ − x∗ = −G (x∗ ) = Theo Mệnh đề 2.3.1 ta có, F (x∗ ) ∈ ∂G (x∗ ) ∩ ∂G (x∗ ) Do đó, C ∗ ⊆ {x ∈ C : F (x) , x − x∗ = 0,F (x) ∈ ∂G (x) ∩ ∂G (x∗ )} 32 Rõ ràng, phần tử x vế phải bao hàm thức thỏa mãn x ∈ C , F (x) , x − x∗ = F (x) ∈ ∂G (x) Hơn nữa, phần tử x có tính chất thuộc C∗ , = G (x∗ ) ≥ G (x) + F (x) , x∗ − x = G (x) ≥ Do đó, sáu tập thỏa mãn quan hệ bao hàm thức Tiếp theo, G khả vi Gâteaux F liên tục theo phương điểm thuộc C∗ theo Mệnh đề 2.1.1 2.1.2, C∗ ⊆ C ∗ Vì tập nói trùng Hệ 2.3.1 Giả sử F : X → X ∗ ánh xạ thỏa F (x) ∈ ∂G (x) với x ∈ C Khi đó, với x∗ ∈ C∗ , bao hàm thức Định lý 2.3.3 Chứng minh Theo giả thiết, với x ∈ C , ta có F (x) ∈ ∂G (x) Nói riêng, F (x∗ ) ∈ ∂G (x∗ ) , ∀x∗ ∈ C ∗ Bởi ∂G đơn điệu, ta có F (x) , x − x∗ ≥ F (x∗ ) , x − x∗ ≥ 0, ∀x ∈ C Điều kéo theo C ∗ ⊆ C∗ Do đó, bao hàm thức Định lý 2.2.3 chứng minh Nhận xét 2.3.3 Bao hàm thức C ∗ ⊆ {x ∈ C : F (x) , x − x∗ = 0,F (x) ∈ ∂G (x) ∩ ∂G (x∗ )} Định lý 2.3.3 kéo theo với cặp điểm x∗ y ∗ C ∗ , ta có F (x∗ ) , x∗ − y ∗ = 0, F (y ∗ ) , x∗ − y ∗ = 0, mà C ∗ ⊆ C∗ Chú ý tính giả đơn điệu F kéo theo C ∗ ⊆ C∗ Vì thế, F giả đơn điệu∗ C tập nghiệm tốn VIP(C,F) có biểu diễn đặc biệt 33 Định lí 2.3.4 Giả sử x∗ ∈ C ∗ F giả đơn điệu∗ C Khi đó, C = C1 = C2 , C1 = {x ∈ C : F (x) , x − x∗ = 0, F (x∗ ) , x − x∗ = 0} , C2 = x ∈ C : F (x) , x − x∗ = 0, F (x) = kF (x∗ ) , k > Chứng minh Vì F giả đơn điệu∗ C , x∗ ∈ C ∗ ⊆ C∗ C ⊆ C2 Hơn nữa, theo Định lý 2.3.3 Nhận xét 2.3.2, C ∗ ⊆ C1 Vì vậy, ta cần C2 ⊆ C ∗ Nhưng điều có bở với x ∈ C2 y ∈ C tồn k > cho F (x) , y − x = k F (x∗ ) , y − x∗ + F (x) , x∗ − x ≥ Định lí chứng minh Khi F giả đơn điệu+ , Định lý 2.3.4 kéo theo C ∗ = {x ∈ C : F (x) , x − x∗ = 0,F (x) = F (x∗ )} Chú ý tập vế phải nằm Λ (x∗ ) Do Λ (x∗ ) ⊆ {x ∈ C : F (x) , x − x∗ = 0, F (x∗ ) , x − x∗ = 0} , với x ∈ Λ (x∗ ), ta có F (x) , x∗ − x = Do giả thiết giả đơn điệu F C F (x∗ ) , x − x∗ ≥ kéo theo F (x∗ ) , x − x∗ = Vì vậy, theo Định lý 2.3.4, ta nhận đặc trưng C ∗ mà không sử dụng tính khả vi Gâteaux hàm sai khác đối ngẫu 34 Hệ 2.3.2 Giả sử x∗ ∈ C ∗ F : X → X ∗ giả đơn điệu+ C Khi đó, C ∗ = {x ∈ C : F (x) , x − x∗ = 0, F (x∗ ) , x − x∗ = 0} = {x ∈ C : F (x) , x − x∗ = 0,F (x) = F (x∗ )} = Λ (x∗ ) Vì vậy, G khả vi Gâteaux x∗ G (x∗ ; v) = sup { F (x) , v : x ∈ C ∗ } , ∀v ∈ X Nhận xét 2.3.4 Với điều kiện phát biểu Hệ 2.3.2, Λ (x∗ ) = C ∗ F số C ∗ Λ (x∗ ) 35 Kết luận Luận văn trình bày kết tính chất đặc trưng tập nghiệm tốn quy hoạch lồi toán bất đẳng thức biến phân Z L Wu S Y Wu (2006), bao gồm: - Một số kiến thức giải tích lồi; - Phát biểu tốn quy hoạch lồi toán bất đẳng thức biến phân; - Các tính chất đặc trưng cho tập nghiệm toán quy hoạch lồi với hàm mục tiêu khả vi Gâteaux; - Các tính chất đặc trưng cho tập nghiệm toán quy hoạch lồi liên tục; - Kết tập nghiệm toán bất đẳng thức biến phân trùng với tập nghiệm toán quy hoạch lồi với hàm mục tiêu hàm sai khác đối ngẫu Các tính chất đặc trưng tập nghiệm toán quy hoạch lồi toán bất đẳng thức biến phân đề tài nhiều tác giả quan tâm nghiên cứu 36 Tài liệu tham khảo Tài liệu Tiếng Việt [1] Đỗ Văn Lưu, Phan Huy Khải (2000), Giải tích lồi, NXB Khoa học Kỹ thuật, Hà Nội Tài liệu Tiếng Anh [2] Bazaraa, M S., Sherali, H D., and Shetty, C M.(1993), Nonlinear Programming Theory and Algorithms, John Wiley and Sons, Singapore, Republic of Singapore [3] Burker, J V., and Ferris, M C.(1991), Charaterization of solution sets of convex programs, Operations Research Letters, vol 10, pp 57-60 [4] Clarke, F H.(1983), Optimization and Nonsmooth Analysis, Wiley-Interscience, New York, NY, 1983; see also Classics in Applied Mathematics, SIAM, Philadelphia, Pennsylvania, vol [5] Ekeland, I., and Temam, R.(1976), Convex Analysis and Variational Problems, North-Holland, Amsterdam, Holland [6] Giannessi, F.(1998), On Minty variationnal principle, New Trends in Mathematical Programming, Edited by F Giannessi, S Komlósi, and T Rapcsák, Kluwer Academic Publishers, Dordrecht, Holland, pp 93-99 [7] Jeyakumar, V.(1992), Infinite-dimensional convex programming with application to constrained approximation, Journal of Optimization Theory and Applications, vol 75, pp 569-586 37 [8] Komlósi, S.(1999), On the Stampacchia and Minty variational inequalities, Generalized Convexity and Optimization for Economic and Financial Decisions, Edited by G Giorgi and F Rossi, Pitagora Editrice, Bologna, Italy, pp 231-260 [9] Mangasarian, O L.(1988), A Simple characterization of solution sets of convex programs, Operations Research Letters, vol 7, pp 21-26 [10] Minty, G.(1962), Monotone (nonlinear) operators in Hilbert space, Duke Mathematical Journal, vol 29, pp 341-346 [11] Shih, M H., and Tan, K K.(1988), Browder-HartmannStampacchia variational inequalities for multivalued monotone operators, Journal of Mathematical Analysis and Applications, vol 134, pp 431-440 [12] Wu, Z L.(2003), Equivalent formulations of Ekeland’s variational principle, Nonlinear Analysis, Vol 55, pp 609-615 [13] Wu, Z L., and Wu, S Y.(2006), Characterizations of the solution sets of convex programs and variational inequality problems [14] Yao, J C.(1994), Multivalued variational inequalitities with Kpseudomonotone operators, Journal of Optimization Theory and Applications, vol 83, pp 391-403 38 ... đề tài "Đặc trưng cho tập nghiệm toán quy hoạch lồi bất đẳng thức biến phân" Mục đích luận văn Luận văn trình bày kết đặc trưng cho tập nghiệm toán quy hoạch lồi toán bất đẳng thức biến phân Z... Kiến thức chuẩn bị 1.1 Một số kiến thức giải tích lồi 1.2 Bài toán tối ưu toán bất đẳng thức biến phân 11 Đặc trưng cho tập nghiệm toán quy hoạch lồi toán bất đẳng thức biến phân. .. đẳng thức biến phân đối ngẫu hàm sai khác đối ngẫu toán bất đẳng thức biến phân xét chương Chương 2 .Đặc trưng cho tập nghiệm toán quy hoạch lồi tốn bất đẳng thức biến phân Trình bày tính chất đặc