Luận văn Thạc sĩ Toán học: Đặc trưng cho tập nghiệm của bài toán quy hoạch lồi và bất đẳng thức biến phân

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:40

Thêm vào BST

Báo xấu

25
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn trình bày các kết quả về đặ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 của Z. L. Wu và S. Y. Wu đăng trong J. Optim. Theory Appl (2006). Mời các bạn tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Đặc trưng cho tập nghiệm của bài toán quy hoạch lồi và bất đẳng thức biến phân

ĐẠ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 1 Kiến thức chuẩn bị 4 1.1 Một số kiến thức giải tích lồi . . . . . . . . . . . . . . . 4 1.2 Bài toán tối ưu và bài toán bất đẳng thức biến phân . . 11 2 Đặ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 14 2.1 Đặc trưng cho tập nghiệm trong trường hợp f khả vi Gâteaux . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2 Đặc trưng tập nghiệm qua dưới vi phân . . . . . . . . . 21 2.3 Đặc trưng tập nghiệm của bài toán bất đẳng thức biến phân . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Kết luận 36 Tài liệu tham khảo 37 i
Mở đầu 1. Lý do chọn đề tài O. L. Mangasarian (1988) đã chứng minh rằng tập nghiệm của bài toán lồi: (P ) M in {f (x) : x ∈ C} , C ⊂ Rn , f : Rn → R Có thể đặc trưng bởi gradient của f khi f khả vi liên tục hai lần trên một tập mở chứa C và có thể đặc trưng bởi dưới vi phân của f khi f liên tục và phần trong tương đối của tập nghiệm khác rỗng. Z. L. Wu và S. Y. Wu (2006) đã chứng minh rằng với bài toán lồi (P) trong không gian định chuẩn với hàm mục tiêu khả vi Gâteaux tại một nghiệm tối ưu thì tập nghiệm bao gồm các điểm chấp nhận được nằm trong siêu phẳng mà véctơ pháp tuyến của nó bằng đạo hàm Gâteaux đó. Với bài toán quy hoạch lồi liên tục, điểm chấp nhận được là nghiệm khi và chỉ khi nó nằm trong siêu phẳng với vectơ pháp tuyến thuộc dưới vi phân của hàm mục tiêu tại điểm đó. Đồng thời có thể đặc trưng tập nghiệm của bài toán bất đẳng thức biến phân. Đây là đề tài được nhiều tác giả quan tâm nghiên cứu. Chính vì thế em chọn đề tài "Đặc trưng cho tập nghiệm của bài toán quy hoạch lồi và bất đẳng thức biến phân". 2. Mục đích của luận văn Luận văn trình bày các kết quả về đặ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 của Z. L. Wu 1
và S. Y. Wu đăng trong J. Optim. Theory Appl (2006). 3. Nội dung của luận văn Luận văn bao gồm phần mở đầu, hai chương, kết luận và danh mục các tài liệu tham khảo. Chương 1. Kiến thức chuẩn bị Trình bày một số kiến thức cơ bản của giải tích lồi như: Phần trong tương đối, dưới vi phân hàm lồi, các phép tính về dưới vi phân hàm lồi. Chương 1 cũng trình bày bài toán quy hoạch lồi, bài toán bất đẳng thức biến phân, bài toán bất đẳng thức biến phân đối ngẫu và hàm sai khác đối ngẫu của bài toán bất đẳng thức biến phân sẽ được xét trong chương 2. Chương 2.Đặ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. Trình bày các tính chất đặc trưng cho tập nghiệm của bài toán quy hoạch lồi trong trường hợp hàm mục tiêu khả vi Gâteaux, trường hợp bài toán quy hoạch lồi liên tục và bài toán bất đẳng thức biến phân của Z. L. Wu và S. Y. Wu ([13], 2006). Trong trường hợp hàm mục tiêu của bài toán quy hoạch lồi khả vi Gâteaux, tập nghiệm sẽ nằm trong siêu phẳng mà vectơ pháp tuyến của nó bằng đạo hàm Gâteaux của hàm mục tiêu. Trong trường hợp quy hoạch lồi liên tục, một điểm chấp nhận được là nghiệm của tối ưu khi và chỉ khi nó nằm trong siêu phẳng mà vectơ pháp tuyến thuộc dưới vi phân của hàm mục tiêu tại điểm này. Trong một số trường hợp tập nghiệm của bài toán bất đẳng thức biến phân trùng với tập nghiệm của bài toán quy hoạch lồi với hàm sai khác đối ngẫu là hàm mục tiêu. Nhân dịp này tôi 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 hoàn thành bản luận văn này. 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 cùng các 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 2
bè đồng nghiệp và các thành viên lớp Cao học Toán K7A đã luôn quan tâm động viên giúp đỡ tôi trong suốt quá 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 3
Chương 1 Kiến thức chuẩn bị Chương 1 trình bày một số kiến thức cơ bản của giải tích lồi như: Phần trong tương đối, dưới vi phân hàm lồi, các phép toán về dưới vi phân các hàm lồi, hàm khả vi Gâteaux. Chương này cũng trình bày bài toán quy hoạch lồi, bài toán bất đẳng thức biến phân, bài toán bất đẳng thức biến phân đối ngẫu và hàm sai khác đối ngẫu sẽ được xét trong chương 2. Các kiến thức trình bày trong chương này được tham khảo trong [1], [13]. 1.1 Một số kiến thức giải tích lồi Giả sử X là không gian tuyến tính trên trường số thực. Định nghĩa 1.1.1. Tập A ⊂ X được gọi là lồi nếu: ∀x1 , x2 ∈ A, ∀λ ∈ R : 0 ≤ λ ≤ 1 ⇒ λx1 + (1 − λ) x2 ∈ A, trong đó R là tập các số thực. Định nghĩa 1.1.2. a) Tập K ⊂ X được gọi là nón có đỉnh tại 0, nếu: ∀x ∈ K, ∀λ > 0 ⇒ λx ∈ K. K được gọi là nón có đỉnh tại x0 , nếu K − x0 là nón có đỉnh tại 0. 4
b) Nón K có đỉnh tại 0 được gọi là nón lồi, nếu K là một tập lồi có nghĩa là: ∀x, y ∈ K, ∀λ, µ > 0 ⇒ λx + µy ∈ K. Định nghĩa 1.1.3. Phần trong tương đối của tập A ⊂ Rn là phần trong của A trong affA; Kí hiệu là riA, trong đó affA là bao affine của tập A. Như vậy riA = {x ∈ affA :∃ε > 0, (x + εB) ∩ affA ⊂ A}, trong đó B là hình cầu đơn vị trong Rn . Định nghĩa 1.1.4. Trên đồ thị của hàm f : D ⊂ X → R, ký hiệu là epif, được định nghĩa như sau: epif = {(x, r) ∈ D × R : f (x) ≤ r} . Định nghĩa 1.1.5. Hàm f : D ⊂ X → R được gọi là chính thường nếu: domf 6= ∅ và f (x) > −∞ (∀x ∈ D) , trong đó domf = {x ∈ D : f(x) < +∞}. Định nghĩa 1.1.6. Hàm f được gọi là lồi trên D nếu epif là tập lồi trong X × R. Hàm f được gọi là lõm trên D nếu −f là hàm lồi trên D. Giải sử f là hàm xác định trên không gian lồi địa phương Haus-
dorffX,
f X
< +∞. Định nghĩa 1.1.7. Đạo hàm của hàm f theo phương d tại x , ký hiệu là f 0 (x; d) được định nghĩa là giới hạn sau: f (x + λd) − f (x) f 0 (x; d) = lim λ↓0 λ Nếu giới hạn này tồn tại (có thể hữu hạn hoặc ±∞). 5
Định lí 1.1.1. Giả sử f là hàm lồi chính thường trên X . Khi đó f có đạo hàm theo phương tại mọi điểm x ∈ domf . Đồng thời, f (x + λd) − f (x) f 0 (x; d) = inf . λ>0 λ Nhận xét 1.1.1. Nếu f là lồi chính thường trên X , x ∈ domf thì f 0 (x, .) là hàm lồi. Giả sử f là hàm lồi trên X . Định nghĩa 1.1.8. Phiếm hàm x∗ ∈ X ∗ được gọi là dưới gradient (subgradient) của f tại x ∈ X nếu: f (x) − f (x) ≥ hx∗ , x − xi (∀x ∈ X) . Định nghĩa 1.1.9. Tập tất cả dưới gradient của f tại x được gọi là dưới vi phân (subdifferential) của f tại x, ký hiệu là ∂f (x), tức là: ∂f (x) = {x∗ ∈ X ∗ : f (x) − f (x) ≥ hx∗ , x − xi , ∀x ∈ X} . Định lí 1.1.2. Giả sử f là hàm lồi chính thường trên X và x ∈ domf . Khi đó, x∗ ∈ ∂f (x) ⇔ f 0 (x; d) ≥ hx∗ , di (∀d ∈ X) . Chứng minh. Nếu x∗ ∈ ∂f (x) thì ∀d ∈ X, λ > 0, ta có: f (x + λd) − f (x) ≥ λ hx∗ , di . Theo Định lý 1.1.1, f có đạo hàm tại x theo phương d, cho nên: f 0 (x; d) ≥ hx∗ , di (1.1) Ngược lại, nếu (1.1) đúng, ta lấy x ∈ X, d = x − x, từ Định lý 1.1.1, ta nhận được: hx∗ , x − xi ≤ f 0 (x; x − x) ≤ f (x + (x − x)) − f (x) . Do đó, x∗ ∈ ∂f (x). 6
Định lí 1.1.3. Giả sử f là hàm lồi chính thường trên X và x ∈ domf . Khi đó, x∗ ∈ ∂f (x) ⇔ f (x) + f ∗ (x∗ ) = hx∗ , xi . Chứng minh. Giả sử x∗ ∈ ∂f (x). Khi đó, f (x) − f (x) ≥ hx∗ , x − xi(∀x ∈ X) ⇒ hx∗ , xi − f (x) ≥ hx∗ , xi − f (x)(∀x ∈ X) ⇒ hx∗ , xi − f (x) ≥ sup{hx∗ , xi − f (x)}(∀x ∈ X) = f ∗ (x∗ ) . (1.2) Mặt khác, theo bất đẳng thức Young-Fenchel hx∗ , xi − f (x) ≤ f ∗ (x∗ ) . (1.3) Từ (1.2) và (1.3) suy ra: f (x) + f ∗ (x∗ ) = hx∗ , xi . (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) ≥ hx∗ , x + λdi − (hx∗ , xi − f (x)) f (x + λd) − f (x) hx∗ , λdi ⇒ ≥ = hx∗ , di λ λ 0 ∗ ⇒ f (x; d) ≥ hx , di (∀d ∈ X) ⇒ x∗ ∈ ∂f (x) . Ví dụ 1.1.1. Cho hàm affine f (x) = hx∗ , xi + α (x∗ ∈ X ∗ , α ∈ R). Khi đó, ∂f (x) = {x∗ } (∀x ∈ X). Ví dụ 1.1.2. 7
Cho hàm chỉ f (x) = δ (.| A), trong đó A là tập lồi khác ∅ Khi đó, với x ∈ A, x∗ ∈ ∂δ (x| A) ⇔ δ (x| A) ≥ δ (x| A) + hx∗ , x − xi (∀x ∈ X) ⇔ hx∗ , x − xi ≤ 0 (∀x ∈ A). Điều này có nghĩa là x∗ là véctơ pháp tuyến của A tại x. Như vậy, ∂δ (x| A) là nón pháp tuyến của A tại x, ∂δ (x| A) = N (x| A) . Chú ý: Với x ∈ / A, ∂δ (x| A) = ∅. Ví dụ 1.1.3. X = R, f (x) = |x| Với x 6= 0: f là hàm khả vi, và : n o −1 ∂f (x) = |x| x . Với x = 0: ∂f (0) = {ξ ∈ R : |z| ≥ hξ, zi , ∀z ∈ R} = {ξ ∈ R : |ξ| ≤ 1} = [−1, 1] . Định nghĩa 1.1.10. Hàm f được gọi là khả vi Gâteaux tại x ∈ X , nếu ∃x∗ ∈ X ∗ sao cho với mọi d ∈ X , f (x + td) = f (x) + t hx∗ , di + o (t) . (1.5) Khi đó, ta gọi x∗ là đạo hàm Gâteaux của f tại x: f 0G (x) = x∗ . Định lí 1.1.4. Giả sử f là hàm lồi trên X . Khi đó, a)Nếu f khả vi Gâteaux tại x với đạo hàm Gâteaux tại x là x∗ và 8
f khả dưới vi phân tại x, thì ∂f (x) = {x∗ }. b)Nếu f là hàm chính thường, liên tục tại x và ∂f (x) gồm một phần tử duy nhất x∗ thì f khả vi Gâteaux tại x và f 0G (x) = {x∗ }. Chứng minh. a) Từ (1.5) ta có: f 0 (x; d) = f 0G (x) , d = hx∗ , di . Do đó, y ∗ ∈ ∂f (x) ⇔ hy ∗ , di ≤ hx∗ , di (∀d ∈ X) ⇔ hx∗ − y ∗ , di ≥ 0 (∀d ∈ X) ⇔ x∗ − y ∗ = 0 hay x∗ = y ∗ . Vậy ∂f (x) = {x∗ }. b) Giả sử ∂f (x) = {x∗ }. Ta có: f 0 (x; d) liên tục. Do đó, f 0 (x; d) là hàm đóng. Vì vậy, ∀d ∈ X , ∗∗ f 0 (x; d) = f 0 (x, .) (d) (Định lý Fenchel-Moreau) = sup {hy ∗ , di : y ∗ ∈ ∂f (x)} = hx∗ , di . Suy ra: f 0G (x) = x∗ . Hệ quả 1.1.1. Giả sử X là không gian Banach, f là hàm lồi khả vi Fréchet tại x ∈ X với đạo hàm Fréchet tại x ∈ X là f 0 (x). Khi đó, ∂f (x) = f 0 (x) . Định lí 1.1.5. Giả sử f là hàm lồi chính thường trên không gian lồi địa phương Hausdorff X , liên tục tại x ∈ X . Khi đó, ∂f (x) khác ∅, lồi, compact yếu∗ . Đồng thời, f 0 (x; d) = max {hx∗ , di : x∗ ∈ ∂f (x)} . 9
Chứng minh. a) Ta chứng minh ∂f (x) lồi? Lấy x∗1 , x∗2 ∈ ∂f (x) và λ ∈ [0, 1]. Khi đó, ∀x ∈ X , hλx∗1 , x − xi ≤ λ (f (x) − f (x)) h(1 − λ) x∗2 , x − xi ≤ (1 − λ) (f (x) − f (x)) ⇒ hλx∗1 + (1 − λ) x∗2 , x − xi ≤ f (x) − f (x) (∀x ∈ X) ⇒ λx∗1 + (1 − λ) x∗2 ∈ ∂f (x) ⇒ ∂f (x) lồi. b) Ta chứng minh ∂f (x) 6= ∅. Theo Định lý 4.2 [1] f 0 (x; .) liên tục trên X. Do đó, ∂f (x) 6= ∅ (Mệnh đề 4.6 [1]). c) Ta chứng minh ∂f (x) compact yếu∗ . Do f 0 (x; d) liên tục, f 0 (x; d) là hàm đóng. Theo Định lý 4.5 [1], sup {hx∗ , di : x∗ ∈ ∂f (x)} = f 0 (x; d) < +∞ (∀d ∈ X) . Khi d chạy trên các tập hữu hạn A trên X , thì: −∞ < max f 0 (x; d) < +∞. d∈A Vì vậy, ∂f (x) bị chặn trên tôpô yếu∗ của X ∗ . Hd , trong đó Hd là nửa không gian đóng yếu∗ T Mặt khác, ∂f (x) = d∈X trong X ∗, Hd = {x∗ ∈ X ∗ : hx∗ , di ≤ f (x + d) − f (x)} . ⇒ ∂f (x) là tập đóng yếu∗ trong X ∗ . ⇒ ∂f (x) compact yếu∗ trong X ∗ . Mệnh đề 1.1.1. Giả sử f là hàm lồi chính thường trên X và λ > 0. Khi đó, ∀x ∈ X , ∂ (λf ) (x) = λ∂f (x) . 10
Định lí 1.1.6. (Moreau-Rockafellar) Giả sử f1 , f2 , ..., fm là hàm lồi chính thường trên X . Khi đó, ∀x ∈ X , ∂ (f1 + ... + fm ) (x) ⊃ ∂f1 (x) + ... + ∂fm (x) . m T Hơn nữa, nếu tại điểm x ∈ domfi , tất cả các hàm f1 , f2 , ..., fm i=1 liên tục (có thể trừ ra một hàm), thì ∂ (f1 + ... + fm ) (x) = ∂f1 (x) + ... + ∂fm (x) . Hệ quả 1.1.2. Giả sử f1 , f2 , ..., fm là các hàm lồi chính thường trên X và λ1 > 0, ..., λm > 0. Khi đó, ∀x ∈ X , ∂ (λ1 f1 + ... + λm fm ) (x) ⊃ λ1 ∂f1 (x) + ... + λm ∂fm (x) . m T Hơn nữa, nếu tại điểm x ∈ domfi , tất cả các hàm f1 , f2 , ..., fm i=1 liên tục (có thể trừ ra một hàm),thì với mọi x ∈ X , ∂ (λ1 f1 + ... + λm fm ) (x) = λ1 ∂f1 (x) + ... + λm ∂fm (x) . 1.2 Bài toán tối ưu và bài toán bất đẳng thức biến phân Xét bài toán quy hoạch lồi: M in {f (x) : x ∈ C} trong đó C là một tập lồi trong Rn . Trong [9] Mangasarian đã chứng minh rằng tập nghiệm của bài toán đó có thể đặc trưng bởi gradient của f khi f khả vi liên tục hai lần trên một tập lồi mở chứa C và bởi dưới vi phân của f khi f là liên tục và phần trong tương đối của tập nghiệm khác rỗng. 11
Giả sử X là không gian vectơ định chuẩn thực, C là tập lồi khác rỗng trong X . Với hàm f : X → (−∞, +∞] và x ∈ X với f (x) < +∞, đạo hàm theo phương của f tại x theo phương v ∈ X là: f 0 (x; v) := lim+ [f (x + tv) − f (x)] /t. t→0 Dưới vi phân của hàm lồi f tại x là: ∂f (x) := {ξ ∈ X ∗ : f (y) − f (x) ≥ hξ, y − xi , ∀y ∈ X}. Ta biết dưới vi phân của hàm f là đơn điệu, có nghĩa là: với (x, y) ∈ X × X, ξ ∈ ∂f (x) , η ∈ ∂f (y) ⇒ hξ − η, x − yi ≥ 0. Nếu hàm lồi f liên tục tại x thì ∂f (x) khác rỗng. Nếu f khả vi Gâteaux tại x thì ∂f (x) = {∇f (x)}. Với một tập lồi đóng C trong X và một ánh xạ F : X → X ∗ , bài toán bất đẳng thức biến phân là tìm véctơ x∗ ∈ C sao cho: (V IP (C, F )) hF (x∗ ), x − x∗ i ≥ 0 với mọi x ∈ C. Bài toán bất đẳng thức biến phân đối ngẫu là tìm x∗ ∈ C sao cho: (DV IP (C, F )) hF (x) , x∗ − xi ≤ 0 với mọi x ∈ C. Bài toán VIP(C,F) thuộc loại bài toán bất đẳng thức biến phân Stam- pachia, còn bài toán DVIP(C,F) được gọi là bài toán bất đẳng thức biến phân Minty (xem [6], [8]). Ký hiệu: Tập nghiệm của VIP(C,F) là C ∗ , và của DVIP(C,F) là C∗ . Rõ ràng là hF (x∗ ) , x∗ − x∗ i = 0, ∀ (x∗ , x∗ ) ∈ C ∗ × C∗ . Hàm sai khác đối ngẫu G(x) ghép với VIP(C,F) được xác định bởi, G (x) := sup {hF (c) , x − ci : c ∈ C} với x ∈ X. Ta ký hiệu: Λ(x) := {c ∈ C : hF (c), x − ci = G(x)} . 12
Dễ thấy rằng với x∗ ∈ C, x∗ ∈ C∗ khi và chỉ khi G (x∗ ) = 0 khi và chỉ khi x∗ ∈ Λ(x∗ ). Chú ý: G là không âm trên C và lồi trên toàn không gian X . Vì vậy C∗ cũng là tập nghiệm của bài toán quy hoạch lồi M in {G(x) : x ∈ C} khi cực tiểu bằng không Nhắc lại: Một ánh xạ F : X → X ∗ được gọi là giả đơn điệu trên C nếu: hF (x) , y − xi ≥ 0 ⇒ hF (y) , y − xi ≥ 0, với mỗi (x, y) ∈ C × C; F được gọi là giả đơn điệu∗ trên C nếu nó giả đơn điệu trên C và thỏa mãn: (x, y) ∈ C × C, hF (x) , x − yi = 0, hF (y) , x − yi = 0 ⇒ F (x) = kF (y) , với k > 0 nào đó. Nói riêng, F là giả đơn điệu+ nếu F là giả đơn điệu∗ trên C với k = 1. Rõ ràng là khi F là giả đơn điệu trên C thì C ∗ ⊆ C∗ . 13
Chương 2 Đặ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 Chương 2 trình bày các tính chất đặc trưng cho tập nghiệm của bài toán quy hoạch lồi trong trường hợp hàm mục tiêu khả vi Gâteaux, trường hợp bài toán quy hoạch lồi liên tục và bài toán bất đẳng thức biến phân. Kết quả chỉ ra rằng tập nghiệm của bài toán quy hoạch lồi nằm trong siêu phẳng mà vectơ pháp tuyến của nó bằng đạo hàm Gâteaux của hàm mục tiêu. Trong trường hợp quy hoạch lồi liên tục, một điểm chấp nhận được là nghiệm tối ưu khi và chỉ khi nó nằm trong siêu phẳng mà vectơ pháp tuyến của nó thuộc dưới vi phân của hàm mục tiêu tại điểm này. Trong một số trường hợp, tập nghiệm của bài toán bất đẳng thức biến phân trùng với tập nghiệm của bài toán quy hoạch lồi với hàm sai khác đối ngẫu là hàm mục tiêu. Các kết quả trình bày trong chương này là của Z. L. Wu - S. Y. Wu ([13], 2006). 2.1 Đặc trưng cho tập nghiệm trong trường hợp f khả vi Gâteaux Để đặc trưng tập nghiệm của bài toán quy hoạch lồi ta bắt đầu với phát biểu sau cho hàm không nhất thiết lồi. 14