›

Luận văn Độ nhạy của nghiệm hữu hiệu và điều kiện tối ưu

pdf 48 trang yendo 5190
Download
Bạn đang xem 20 trang mẫu của tài liệu "Luận văn Độ nhạy của nghiệm hữu hiệu và điều kiện tối ưu", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfluan_van_do_nhay_cua_nghiem_huu_hieu_va_dieu_kien_toi_uu.pdf

Nội dung text: Luận văn Độ nhạy của nghiệm hữu hiệu và điều kiện tối ưu

  1. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THỊ HỒNG ĐỘ NHẠY CỦA NGHIỆM HỮU HIỆU VÀ ĐIỀU KIỆN TỐI ƯU LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - Năm 2011 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  2. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THỊ HỒNG ĐỘ NHẠY CỦA NGHIỆM HỮU HIỆU VÀ ĐIỀU KIỆN TỐI ƯU Chuyên ngành: TOÁN ỨNG DỤNG Mã số : 60.46.36 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS. ĐỖ VĂN LƯU Thái Nguyên - Năm 2011 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  3. i Mục lục Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .i Mở đầu 1 Nội dung 4 1 ĐỘ NHẠY CỦA NGHIỆM HỮU HIỆU CỦA BÀI TOÁN ĐA MỤC TIÊU TUYẾN TÍNH 4 1.1 Bài toán nhiễu . . . . . . . . . . . . . . . . . . . . . . . . .4 1.2 Độ nhạy của đỉnh . . . . . . . . . . . . . . . . . . . . . . .6 1.3 Độ nhạy của diện . . . . . . . . . . . . . . . . . . . . . . . 14 2 ĐỘ NHẠY VÀ ĐIỀU KIỆN TỐI ƯU CHO NGHIỆM CỦA BÀI TOÁN ĐA MỤC TIÊU PHI TUYẾN 19 2.1 Các khái niệm và kết quả bổ trợ . . . . . . . . . . . . . . . 19 2.2 Điều kiện cần cấp 1 và cấp 2 cho nghiệm hữu hiệu . . . . . 22 2.3 Điều kiện đủ cấp hai cho nghiệm hữu hiệu . . . . . . . . . . 29 2.4 Phân tích độ nhạy của nghiệm hữu hiệu . . . . . . . . . . . 31 Kết luận 42 Tài liệu tham khảo 44 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  4. 1 Mở đầu Việc nghiên cứu sự phụ thuộc của nghiệm tối ưu của một bài toán tối ưu đơn hoặc đa mục tiêu theo các tham số nhiễu đóng một vai trò quan trọng trong lý thuyết tối ưu hóa. Ta gọi đó là các nghiên cứu về độ nhạy (sensitivity) của nghiệm tối ưu. Các kết quả nghiên cứu theo hướng này chỉ ra sự bảo toàn các tính chất nào đó của nghiệm tối ưu sau một nhiễu nhỏ. Lí thuyết độ nhạy của nghiệm hữu hiệu có nhiều ứng dụng trong kinh tế, vật lý, cơ học và một số ngành khoa học khác. S. Bolitinéanu và B.D Craven [5] đã nghiên cứu độ nhạy của nghiệm hữu hiệu của bài toán tối ưu đa mục tiêu tuyến tính trong trường hợp đa diện chấp nhận được không suy biến. M. El Maghri [8] nghiên cứu độ nhạy của nghiệm hữu hiệu của bài toán đa mục tiêu tuyến tính mà trong đó đa diện chấp nhận được có thể suy biến. Tác giả thiết lập các điều kiện cần và đủ cấp 2 cho đỉnh hữu hiệu và diện hữu hiệu của bài toán nhiễu. S. Bolitinéanu và M. El Maghri [6] nghiên cứu các điều kiện đủ để nghiệm hữu hiệu của bài toán nhiễu thuộc lớp C1 theo tham số nhiễu. Ở đây các tác giả nghiên cứu bài toán tối ưu đa mục tiêu phi tuyến khả vi Fréchet, có các ràng buộc đẳng thức và bất đẳng thức trong các không gian Banach vô hạn chiều. Trong trường hợp hữu hạn chiều, các tác giả thiết lập các điều kiện đủ để nghiệm hữu hiệu của bài toán nhiễu là Lipschitz địa phương theo tham số nhiễu. Luận văn trình bày các kết quả nghiên cứu về độ nhạy của đỉnh hữu hiệu và diện hữu hiệu của bài toán đa mục tiêu tuyến tính nhiễu, độ nhạy Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  5. 2 Fréchet và độ nhạy Lipschitz của nghiệm hữu hiệu của bài toán đa mục tiêu phi tuyến với hàm các hàm khả vi Fréchet. 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 trình bày các kết quả nghiên cứu của E. El Maghri [8] về độ nhạy của nghiệm hữu hiệu của bài toán đa mục tiêu tuyến tính nhiễu. Chú ý rằng các đỉnh của tập chấp nhận được có thể suy biến hoặc không suy biến. Các điều kiện cần và đủ cấp 2 cho đỉnh hữu hiệu và diện hữu hiệu của bài toán nhiễu được trình bày trong chương này. Chương 2 trình bày các điều kiện cần và đủ cấp 1 và cấp 2 của S. Bolitinéanu và E. El Maghri [6] cho nghiệm hữu hiệu của bài toán tối ưu đa mục tiêu phi tuyến với các hàm mục tiêu và ràng buộc khả vi Fréchet trong không gian Banach cùng với các điều kiện đủ để nghiệm hữu hiệu của bài toán nhiễu thuộc lớp C1 theo tham số nhiễu. Trong trường hợp hữu hạn chiều, các điều kiện đủ để nghiệm hữu hiệu của bài toán nhiễu là Lipschitz địa phương theo tham số nhiễu cũng được trình bày trong chương này. Nhân dịp này tác giả xin bày tỏ lòng biết ơn sâu sắc tới PGS. TS. Đỗ Văn Lưu đã hướng dẫn và chỉ bảo tận tình trong suốt quá trình làm luận văn. Thầy đã dành nhiều thời gian hướng dẫn và giải đáp các thắc mắc trong suốt quá trình làm luận văn. Tôi xin được bày tỏ lòng biết ơn sâu sắc đến thầy. Tác giả cũng xin gửi lời cảm ơn chân thành đến Ban giám hiệu, phòng Đào tạo, khoa Toán - Tin Trường Đại học Khoa Học, Đại học Thái Nguyên đã tạo điều kiện thuận lợi trong suốt quá trình học tập tại trường. Xin chân thành cảm ơn gia đình, bạn bè đồng nghiệp và các thành viên trong lớp cao học toán K3b đã luôn quan tâm, động viên, giúp đỡ tôi trong suốt thời gian học tập và quá trình làm luận văn. Tuy bản thân có nhiều cố gắng, song thời gian và năng lực của bản Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  6. 3 thân có hạn nên luận văn khó tránh khỏi những thiếu sót. Rất mong được sự đóng góp ý kiến của các thầy cô cùng toàn thể bạn đọc. Thái Nguyên, tháng 09 năm 2011. Tác giả Nguyễn Thị Hồng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  7. 4 Chương 1 ĐỘ NHẠY CỦA NGHIỆM HỮU HIỆU CỦA BÀI TOÁN ĐA MỤC TIÊU TUYẾN TÍNH Chương này trình bày các kết quả nghiên cứu của M. El Maghri [8] về độ nhạy của nghiệm hữu hiệu của bài toán đa mục tiêu tuyến tính nhiễu. Chú ý rằng các đỉnh của tập chấp nhận được có thể suy biến hoặc không suy biến. Các điều kiện cần và đủ cấp hai cho đỉnh hữu hiệu dưới một nhiễu nhỏ được trình bày cùng với các điều kiện cần và đủ cho diện hữu hiệu nhiễu đi qua một đỉnh như vậy. 1.1 Bài toán nhiễu Ta xét độ nhạy của bài toán đa mục tiêu tuyến tính nhiễu sau đây: (Pp) min C(p)x, A(p)x = b(p), x ≥ 0, r×n m×n m trong đó [C(.),A(.), b(.)] : N (0) → R × R × R là các hàm của q tham số nhiễu p ∈ N (0), N (0) là lân cận của điểm gốc 0 ∈ R . Ở đây ta có thể giả thiết rằng bài toán không nhiễu tương ứng với p = 0. Đa diện Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  8. 5 chấp nhận được của (Pp) là n Γ(p) = {x ∈ R : A(p)x = b(p), x ≥ 0}. Với mỗi p, tập các nghiệm hữu hiệu (nghiệm Pareto) và tập các nghiệm hữu hiệu yếu của (Pp) tương ứng là 0 0 0 Ee(p) = {x ∈ Γ(p): @x ∈ Γ(p),C(p)x ≤ C(p)x, C(p)x 6= C(p)x}, và 0 0 Ew(p) = {x ∈ Γ(p): @x ∈ Γ(p),C(p)x < C(p)x}. Để đơn giản cho việc trình bày, ta kí hiệu Eσ(p) là tập điểm σ-hữu hiệu phụ thuộc vào việc lựa chọn σ ∈ {w, e}. Với p = 0, ta kí hiệu (P0) := (P), Γ(0) := Γ,C(0) := C, A(0) := A, b(0) := b. r Γ(p) Với mỗi p, xét ánh xạ đa trị E(., p): R → 2 xác định với mọi r λ ∈ R bởi E(λ, p) = arg min λT C(p)x, (1.1) x∈Γ(p) trong đó λT là chuyển vị của vectơ λ. Ta có kết quả vô hướng hóa sau đây (xem [14]): Eσ(p) = E(Λσ, p), (1.2) trong đó ( r R+\{0}, nếu σ = w, Λσ = r intR+, nếu σ = e. Tất cả các kết quả trình bày trong chương này đúng trong trường hợp r tổng quát hơn khi nón thứ tự R+ được thay tương ứng bởi một tập con đóng bất kỳ Q và một nón lồi nhọn có phần trong không rỗng. Quan hệ thứ tự bộ phận được xác định tương ứng bởi y0 ≤ y ⇔ y − y0 ∈ Q, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  9. 6 và y0 < y ⇔ y − y0 ∈ intQ. r Trong trường hợp này R+ được thay thế trong Λσ bởi nón cực của Q khi σ = w và bởi nón cực chặt của Q khi σ = e. Giả thiết tổng quát (i) C(.) là liên tục tại p = 0 và b(.) là lớp C2 tại p = 0. (ii) A có hạng đầy (tức là rank A=m) và m < n. 1.2 Độ nhạy của đỉnh Giả sử v là một đỉnh của đa diện Γ. Như vậy rank A = m. Khi đó tồn tại B ⊂ {1, . . . , n} sao cho (sắp xếp lại các hàng nếu cần): A−1b v = B (1.3) 0 −1 −1 trong đó AB b ≥ 0,AB là ma trận nghịch đảo của AB (rank AB = m)với phân hoạch A = [ABAN ] (sắp xếp lại các cột của A nếu cần) và N = {1, . . . , n}\B. Cũng sắp xếp lại các biến, ta có thể viết:   xB n −1 −1 Γ = {x = ∈ R : xB + AB AN xN = AB b, x ≥ 0}. (1.4) xN Cùng cách phân hoạch ma trận A(p) = [AB(p)AN (p)]. Thế thì với mọi p gần 0, do tính liên tục của ánh xạ A(.), ma trận AB(p) là khả nghịch, và do đó   xB n −1 −1 Γ(p) = {x = ∈ R : xB + AB (p)AN (p)xN = AB (p)b(p), x ≥ 0}. xN (1.5) Vì vậy ta có thể xác định nhiễu của v bởi A−1(p)b(p) v(p) = B (1.6) 0 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  10. 7 −1 Nhắc lại rằng nếu AB b > 0 thì đỉnh v hoặc cơ sở B được gọi là không suy biến, và trong trường hợp này, B là cơ sở duy nhất xác định v theo (1.3). Ngược lại, v là đỉnh suy biến và nó có thể xác định bởi một số cơ sở suy biến. Như vậy, giả sử B(v) = {B ⊂ {1, . . . , n} : B xác định v}. (1.7) Nhận xét 1.1 −1 Khi v là không suy biến thì với mọi p gần 0, do tính liên tục, AB (p)b(p) > 0. Khi đó theo (1.5), (1.6), v(p) là đỉnh của Γ(p) với mọi p gần 0. Do đó nó là đỉnh nhiễu của v. Ta có thể thấy trong ví dụ sau đây khi v là suy biến, v(p) được cho bởi (1.6) có thể không là điểm chấp nhận được với bất kỳ B ∈ B(v) và p 6= 0. Ví dụ 1.1 Với mỗi tham số nhiễu p ∈ R, ta xét bài toán min x1, ( x1 − x2 = p, x1 ≥ 0, x2 ≥ 0. Ta có v = (0, 0) là đỉnh suy biến của đa diện không nhiễu Γ(p = 0). Nhưng với mọi p 0, v(p) = (0, −p) với B = {2} cũng không chấp nhận được. Do đó, ta tìm một số điều kiện đảm bảo rằng với mọi p gần 0, v(p) là đỉnh chấp nhận được của đa diện Γ(p). Ta xét các tập chỉ số: −1 D = {i ∈ B :(AB b)i = 0}, (1.8) và c −1 D = {i ∈ B :(AB b)i > 0}. (1.9) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  11. 8 −1 Sắp xếp lại phân hoạch các cột của AB và các hàng của AB như sau:  −1  −1 (AB )D AB = [ADADc ],AB = −1 . (AB )Dc −1 −1 Với mọi chỉ số i ∈ D, ta kí hiệu hàng thứ i của (AB )D bởi Ai và với bất kỳ chỉ số j, k ∈ {1, . . . , q}, 2 ∂b 2 ∂ b ∂jb := (0), ∂kjb := (0), ∂pj ∂pj∂pk 2 ∂ADc 2 ∂ ADc ∂jADc := (0), ∂kjADc := (0). ∂pj ∂pj∂pk Bổ đề sau đây trình bày điều kiện cần và đủ cấp 2 cho tính chấp nhận được của v(p) với mọi p gần 0. Bổ đề 1.1 Cho B ∈ B(v) và v(p) được xác định bởi (1.6). 1. Các điều kiện sau đây là các điều kiện cần để với mọi p gần 0, v(p) ∈ Γ(p): (i) Với mọi i ∈ D, vectơ (i) −1 −1 J = (Ai {∂jb − ∂jADc (AB )Dc b})j=1 q = 0, và (ii) Với mọi i ∈ D, q × q− ma trận đối xứng thực −1 −1 2 ! Ai {(∂kADc (AB )Dc ∂jADc + ∂jADc ADc ∂kADc − ∂kjADc ) H(i) = −1 −1 2 c c c c c × (AB )D b − (∂kAD (AB )D + ∂jAD AD )∂kb + ∂kjb} (k,j) là bán xác định dương. 2. Các điều kiện sau đây là các điều kiện đủ để với mọi p gần 0, v(p) ∈ Γ(p): (i)Với mọi i ∈ D , vec tơ J (i) = 0, và Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  12. 9 (ii)Với mọi i ∈ D, ma trận H(i) là xác định dương. Chứng minh −1 Tính chấp nhận được của v(p) theo (1.5), (1.6) tương đương với AB (p)b(p) ≥ 0. Điều này tương đương với −1 −1 (AB )D(p)b(p) = (Ai (p)b(p))i∈D ≥ 0, −1 bởi vì theo (1.9) và tính liên tục (AB )Dc (p)b(p) > 0 với mọi p gần 0. Kí −1 hiệu vi(p) = Ai (p)b(p) với mỗi i ∈ D. Sử dụng (1.8) ta suy ra vi(p) ≥ 0 q tương đương với vi(p) ≥ vi(0) với mọi p gần 0. Điều đó có nghĩa là 0 ∈ R là cực tiểu địa phương của mỗi hàm vô hướng p 7→ vi(p)(∀i ∈ D.) Do đó, Jacobian ! ∂v i (0) = 0 (1.10) ∂pj j=1 q và ma trận Hessian ! ∂2v i (0) (1.11) ∂pk∂pj (k,i)={1, ,q}2 bán xác định dương là các điều kiện cần. Điều kiện đủ là (1.10) đúng và ma trận Hessian cho bởi (1.11) là xác định dương. Như vậy ta sẽ chỉ ra rằng (1.10) và (1.11) tương ứng là J (i) và H(i) được cho trong bổ đề. −1 Từ AB (p)AB(p) = Im, trong đó Im là m × m− ma trận đồng nhất. Với mọi j ∈ {1, . . . , q}, ta có −1 ∂AB −1 ∂AB −1 (p) = −AB (p) (p)AB (p). (1.12) ∂pj ∂pj Từ đó suy ra với mọi i ∈ D, −1 ∂Ai −1 ∂AB −1 (p) = −Ai (p) (p)AB (p). (1.13) ∂pj ∂pj Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  13. 10 Sử dụng (1.13) và đạo hàm một tích, ta nhận được ∂v ∂(A−1(p)b(p)) i (p) = i (p) ∂pj ∂pj ( ) (1.14) −1 ∂AB −1 ∂b = Ai (p) − (p)AB (p)b(p) + (p) . ∂pj ∂pj Với p = 0, theo (1.8), (1.14) ta nhận được J (i) của bổ đề. Mặt khác, để xác định các hệ số Hessian của vi tại 0, ta đánh giá đạo hàm riêng của (1.14) bằng cách sau: 2 −1 ( ) ∂ vi ∂Ai ∂AB −1 ∂b (p) = (p) − (p)AB (p)b(p) + (p) ∂pk∂pj ∂pk ∂pj ∂pj ( 2 −1 ∂ AB −1 + Ai (p) − (p)AB (p)b(p) ∂pk∂pj ) ∂A ∂(A−1(p)b(p)) ∂2b − B (p) B (p) + (p) . ∂pj ∂pk ∂pk∂pj Sử dụng (1.10) và cách đánh giá (∂vi/∂pj)(0), ta nhận được −1 ! ∂(AB (p)b(p)) −1 ∂ADc −1 ∂b (0) = (AB )Dc − (0)(AB )Dc b + (0) . (1.15) ∂pk ∂pk ∂pk 2 Cuối cùng, bằng cách sử dụng (1.8), (1.15 ) để đánh giá (∂ vi/∂pk∂pj)(0) (i) ta nhận được H . Bổ đề được chứng minh.  Nhận xét 1.2 Nếu ta chỉ nhiễu vế phải của tập chấp nhận được, nghĩa là A(p) ≡ A(0) không phụ thuộc vào p, thì với mọi i ∈ D: m (i) −1 (i) X −1 2 J = Ai ∇b(0), và H = (Ai )j∇ bj(0), j=1 −1 −1 trong đó (Ai )j (tương ứng bj) là thành phần thứ j của vectơ Ai (tương ứng b) và ∇ là toán tử đạo hàm. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  14. 11 Ví dụ sau đây cho thấy rằng ngay cả khi v là σ- hữu hiệu, thì v(p) vẫn có thể không là σ- hữu hiệu với bất kỳ p 6= 0. Ví dụ 1.2 Với mỗi tham số nhiễu p > 0, xét bài toán min (x2 − px1, x2 − 2px1), ( 0 ≤ x1 ≤ 1, 0 ≤ x2 ≤ 1. Trong ví dụ này, ta có Γ(p) ≡ Γ(0) = [0, 1]×[0, 1] và Ee(0) = Ew(0) = 2 đoạn thẳng đóng nối điểm gốc với điểm (1,0) trong R . Mặt khác, với p > 0, ta có Ee(p) = Ew(p) = {(1, 0)}. Đỉnh v(p) ≡ v(0) = (0, 0) là σ- hữu hiệu với p = 0 và không là σ-hữu hiệu với mọi p > 0. Vì vậy ta tìm các điều kiện đảm bảo rằng v là σ-hữu hiệu và bảo đảm tính chất này với độ nhiễu nhỏ. Ta phân hoạch ma trận C = [CBCN ]. Do (1.4), (1.3) ta nhận được ∀x ∈ Γ,Cx = CBxB + CN xN = CbN xN + Cv, (1.16) trong đó CbN là rút gọn của ma trận C theo N tức là −1 CbN = CN − CBAB AN . (1.17) Ta cũng xét tập sau: S(v) := {B ∈ B(v): B thỏa mãn điều kiện đủ của bổ đề 1.1}. (1.18) Định lý sau đây chỉ ra rằng trong hầu hết các trường hợp, đỉnh nhiễu vẫn là σ-hữu hiệu ngay cả trong trường hợp suy biến. Định lý 1.1 Cho v là đỉnh bất kỳ (suy biến hoặc không) của đa diện Γ 1. v là σ- hữu hiệu của (P) khi và chỉ khi : T ∃λ ∈ Λσ, ∃B ∈ B(v): λ CbN ≥ 0. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  15. 12 2. Mỗi khẳng định sau đây là một điều kiện đủ để với mọi p gần 0, v(p) cho bởi (1.6) theo cơ sở B, là đỉnh σ-hữu hiệu của (Pp): (i) T ∃λ ∈ Λσ, ∃B ∈ S(v): λ CbN > 0, hoặc (ii) Ma trận A(p) ≡ A(0),C(p) ≡ C(0) không phụ thuộc vào p, (tức là chỉ có nhiễu vế phải của tập chấp nhận được) và T ∃λ ∈ Λσ, ∃B ∈ B(v): λ CbN ≥ 0. Chứng minh 1. Ta có thể tách chặt một đỉnh từ đa diện của nó: n T T ∃d ∈ R \{0} : ∀x ∈ Γ \{v}, d v < d x. (1.19) Mặt khác, bởi vì v là σ-hữu hiệu của (P), theo (1.2) tồn tại λ ∈ Λσ sao cho v ∈ E(λ, 0), tức là ∀x ∈ Γ, λT Cv ≤ λT Cx. Từ (1.19) suy ra với mọi ∗ k ∈ N , đỉnh v là nghiệm tối ưu duy nhất của mỗi bài toán nhiễu vô hướng sau đây: min c(k)x, (1.20) x∈Γ trong đó c(k) := λT C + (1/k)dT . Trong thuật toán đơn hình (xem [13]) với mỗi bài toán vô hướng (1.20), cần xác định cơ sở tối ưu cho nghiệm tối ưu v duy nhất của (1.20). Vì vậy tiêu chuẩn tối ưu đơn hình sau đây đúng ∀k ∈ ∗, ∃B ∈ B(v): c (k) ≥ 0, (1.21) N k bNk trong đó c (k) = c (k) − C (k)A−1A là hàm mục tiêu rút gọn và bNk Nk Bk Bk Nk Nk = {1, , n}\Bk. Mặt khác, ta có T 1 T cN (k) = λ CbN + db , (1.22) b k k k Nk trong đó dT = dT − dT A−1A và C cho bởi (1.17). Nhưng dãy bNk Nk Bk Bk Nk bNk (Bk)k thuộc tập hữu hạn B(v) cho bởi (1.7). Do đó tồn tại dãy dừng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  16. 13 (Bkj )j ⊂ B(v), tức là ∗ ∃J ∈ N : ∀j ≥ J, Bkj = BkJ . Đặt B = BkJ . Khi đó N = NkJ và theo (1.21), (1.22) ta có T 1 T ∀j ≥ J, λ CbN + dbN ≥ 0. kj Cho j % +∞ ta nhận được điều kiện cần. Ta có ngay điều ngược lại. T Thật vậy, nếu λ CbN ≥ 0 thế thì theo (1.4), (1.16) ta có T T T ∀x ∈ Γ, λ Cx = λ (CbN xN + Cv) ≥ λ Cv, có nghĩa là v ∈ E(λ, 0). Do đó theo (1.2) v là σ- hữu hiệu của (P). 2. Bây giờ giả thiết rằng tồn tại B ∈ S(v), trong đó S(v) được cho bởi (1.18). Theo bổ đề 1.1, với mọi p gần 0, v(p) cho bởi (1.6) theo cơ sở B, tức là B ∈ B(v(p)) là đỉnh của Γ(p). Giả sử rằng điều kiện (i) đúng và xét ma trận sau: −1 CbN (p) = CN (p) − CB(p)AB (p)AN (p). (1.23) Bởi vì p 7→ CbN (p) liên tục tại p = 0, từ (i) suy ra với mọi p gần 0 T λ CbN (p) > 0, và do B ∈ B(v(p)), khẳng định 1 áp dụng cho bài toán (Pp) ta suy ra v(p) là σ- hữu hiệu của (Pp) với mọi p gần 0. Bây giờ nếu ta giả sử điều kiện T (ii) đúng, thế thì ma trận CbN (p) ≡ CbN . Do đó, λ CbN (p) ≥ 0 với mọi p. Vì vậy, chứng minh giống như trên ta suy ra điều phải chứng minh.  Nhận xét 1.3 Khi lấy λ = 1, dễ thấy rằng định lý 1.1 cũng áp dụng được cho bài toán tuyến tính vô hướng (bài toán (P) với r = 1). Nhận xét 1.4 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  17. 14 Trong trường hợp không suy biến, ta có thể bỏ cụm từ ”∃B ∈ B(v)” trong định lí 1.1 bởi vì bất kì đỉnh không suy biến nào cũng xác định bởi cơ sở duy nhất B (tức là B(v) có một phần tử). Ta cũng có thể bỏ cụm từ ”∃B ∈ S(v)” bởi vì do nhận xét 1.1, v(p) ∈ Γ(p) với mọi p gần 0. 1.3 Độ nhạy của diện Cho F là một diện của đa diện đi qua một đỉnh của nó (suy biến hoặc không suy biến), trong đó đỉnh v cho bởi (1.3). Ta biết rằng F có thể được xác định bởi B ∈ B(v) và I ⊂ {1, , n} (nói chung I 6⊂ N trừ khi v là không suy biến) tức là F = {x = (xB, xN ) ∈ Γ: xI = 0} (1.24) Nhiễu của F là diện sau đây của đa diện nhiễu Γ(p) F (p) = {x ∈ Γ(p): xI = 0} (1.25) Cũng như trong phần trước, ta sẽ trình bày các điều kiện cần và đủ để diện F (p) là σ- hữu hiệu (tức là F (p) ⊂ Eσ(p)) với mọi p gần 0. Định lý 1.2 Giả sử F là một diện đi qua đỉnh v (suy biến hoặc không) của đa diện Γ. 1. F là σ- hữu hiệu của (P) nếu và chỉ nếu: T T ∃λ ∈ Λσ, ∃B ∈ B(v), ∃I ⊂ N : λ CbI ≥ 0, λ CbN\I = 0. (CbI có các cột Cbi(∀i ∈ I) và CbN\I có các cột khác của CbN ). 2. Mỗi khẳng định sau đây là một điều kiện đủ để với mọi p gần 0, F (p) cho bởi (1.25) là diện σ- hữu hiệu của (Pp): (i) Các cột của ma trận CbN\I sau đây là độc lập tuyến tính trong r R , và T T ∃λ ∈ intΛσ, ∃B ∈ S(v), ∃I ⊂ N : λ CbI > 0, λ CbN\I = 0, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  18. 15 hoặc (ii) Các ma trận A(p) ≡ A(0),C(p) ≡ C(0) là hằng số (tức là chỉ có nhiễu vế phải của tập chấp nhận được), và T T ∃λ ∈ Λσ, ∃B ∈ S(v), ∃I ⊂ N : λ CbI ≥ 0, λ CbN\I = 0. Chứng minh Trước hết ta cần bổ đề sau đây. Bổ đề 1.2 n n Cho F là một diện của đa diện P ⊂ R . Khi đó tồn tại d ∈ R sao cho: ∀x0 ∈ F, ∀x ∈ P \ F, dT x0 < dT x. Chứng minh n Ta biết rằng mỗi đa diện P ⊂ R có thể viết dưới dạng: n T P = {x ∈ R : aj x ≤ bj, ∀j ∈ {1, . . . , l}}, và mỗi diện F của P có dạng: n T F = {x ∈ R : aj x = bj, ∀j ∈ J}, P trong đó J ⊂ {1, . . . , l}. Đặt d = − j∈J aj. Lấy x ∈ P \ F , khi đó tồn 0 T 0 tại j ∈ J sao cho aj0 x < bj0 . Lấy x ∈ F , ta có ngay T 0 X T X T T d x = −bj0 − bj < −aj0 − aj x = d x. j∈J\{j0} j∈J\{j0} Bổ đề được chứng minh .  Bây giờ ta chứng minh định lý 1.2. 1. Bởi vì F là diện σ- hữu hiệu của (P), tồn tại λ ∈ Λσ sao cho F ⊂ E(λ, 0) cho bởi (1.1) (xem [14]) và từ bổ đề 1.2, ta suy ra ∗ ∀k ∈ N ,F = arg min c(k)x, (1.26) x∈Γ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  19. 16 trong đó c(k) = λT C + (1/k)dT , và d được cho bởi bổ đề 1.2. Do v ∈ F, theo nhận xét 1.3 và khẳng định 1 của định lý 1.1 áp dụng với mỗi bài toán vô hướng (1.26), ta nhận được: ∀k ∈ ∗, ∃B ∈ B(v): c (k) ≥ 0. (1.27) N k bNk Do c(k)x = c (k)x + c(k)x, theo (1.26) rõ ràng bNk Nk ∗ ∀k ∈ N ,F = {x = (xBk , xNk ) ∈ Γ: xIk = 0}, (1.28) trong đó Ik = {i ∈ Nk : bci(k) > 0}. Do đó, theo (1.27), Nk \ Ik = {i ∈ Nk : bci(k) = 0}. Nhưng dãy (Bk)k nằm trong tập hữu hạn B(v) cho bởi (1.7). Vì vậy tồn tại một dãy dừng (Bkj )j ⊂ B(v), tức là ∗ ∃J ∈ N , ∀j ≥ J, Bkj = BkJ . Đặt B = BkJ . Ta suy ra N = NkJ và vì thế ta có dãy (Ikj )j nằm trong tập hữu hạn {I ⊂ N}. Bằng lý luận tương tự ta có thể thay Ikj bởi I với mọi j đủ lớn. Do đó B ∈ B(v) và I ⊂ N. Hơn nữa, ∀j ≥ J, T 1 T bcI(kj) = λ CbI + dbI > 0, kj T T 1 T λ bcN\I(kj) = λ CbN\I + dbN\I = 0. kj T T Cho j % +∞, ta nhận được λ CbI ≥ 0 và λ CbN\I = 0 và điều kiện cần được chứng minh. Ngược lại, điều kiện Karush-Kuhn-Tucker cho bài toán vô hướng rút gọn T min λ CbN xN , ( −1 −1 AB AN xN ≤ AB b, xN ≥ 0, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  20. 17 là T T T −1 λ CbN − µN + νBAB AN = 0, ∀i ∈ N, (µN )i(xN )i = 0, −1 −1 ∀j ∈ B, (νB)j(AB AN xN − AB b)j = 0, −1 −1 µN ≥ 0, νB ≥ 0, xN ≥ 0,AB AN xN − AB b ≤ 0. Theo (1.4), (1.24 ) ta suy ra với mọi xb = (xbB, xbN ) ∈ F , các điểm T xN = xbN , µN = λ CbN và νB = 0 thỏa mãn các điều kiện này. Do đó, xbN là nghiệm tối ưu của bài toán rút gọn. Do vậy, từ (1.1), (1.4), (1.16) ta suy ra xb ∈ E(λ, 0). Như vậy, theo (1.2) ta có F ⊂ Eσ(0), nghĩa là F là điểm σ- hữu hiệu của (P). 2. Bởi vì B ∈ S(v) xác định trong (1.18), từ bổ đề 1.1 ta suy ra với mọi p gần 0, v(p) xác định trong (1.6) theo cơ sở B, là một đỉnh của Γ(p). Do đó, với mọi p gần 0, F (p) là một diện của Γ(p) đi qua đỉnh v(p). Giả T sử (i) đúng. Do tính liên tục của ánh xạ (λ, p) 7→ (λ )CbN (p), ta suy ra với mỗi λ gần λ và mỗi p gần 0. T λ CbI(p) > 0. (1.29) Bởi vì với p = 0, ma trận CbN\I(p) = [Cbi(p)]i∈N\I có hạng cột đầy (sắp xếp lại các hàng nếu cần) ta có thể viết " # C0 (p) C (p) = cN\I , (1.30) bN\I 00 Cc N\I(p) 0 với CcN\I(0) là khả nghịch. Do tính liên tục ta suy ra với mọi p gần 0, ma 0 T trận CcN\I(p) là khả nghịch. Nhưng λ CbN\I(0) = 0 và λ 6= 0 (do λ ∈ Λσ). Do vậy T 0T 00T 0T 00T 00 0 −1 λ = [λ λ ], λ = −λ Cc N\I(0)CcN\I(0) . (1.31) Với mọi p gần 0, xét vectơ T 00T 00 0 −1 00T λ (p) = [−λ Cc N\I(p)CcN\I(p) λ ]. (1.32) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  21. 18 Do tính liên tục của ánh xạ p 7→ λ(p), ta suy ra λ(p) ∈ intΛσ ⊂ Λσ với mọi p gần 0 bởi vì do (1.31), λ(0) = λ ∈ intΛσ. Theo (1.29), (1.30), (1.32) ta có T λ (p)CbI(p) > 0, T λ (p)CbN\I(p) = 0. Như vậy với mọi p gần 0, khẳng định 1 áp dụng cho diện F (p) chỉ ra rằng nó là σ- hữu hiệu của bài toán nhiễu (Pp). Điều kiện đủ cho (ii) ta T có ngay bởi vì CbN\I(p) ≡ CbN\I và CbI(p) ≡ CbI kéo theo λ CbN\I(p) = 0 và T λ CbI(p) ≥ 0. Từ đó ta áp dụng khẳng định 1 tương tự như (i). Định lý được chứng minh.  Nhận xét 1.5 Khi lấy λ = 1, ta thấy rằng định lý 1.2 cũng áp dụng được cho bài toán quy hoạch tuyến tính vô hướng (bài toán (P) với r = 1). Nhận xét 1.6 r Nếu σ = e thì Λσ là tập mở trong R vì vậy intΛσ = Λσ và ta có thể bỏ "int" trong (i) của định lý 1.2. Cũng theo (1.31), (1.32), điều kiện 0 0 0 "λ ∈ intΛσ" có trong (i) có thể yếu đi chỉ với "λ ∈ intΛσ", trong đó Λσ 0 là hình chiếu của Λσ trên trục λ . Nhận xét 1.7 Trường hợp riêng, diện F quy về đỉnh v, xảy ra khi và chỉ khi I = N. Khi đó, ma trận CbN\I là rỗng và nó có hạng cột đầy. Hơn nữa, do nhận xét trước, do λ0 là rỗng, ta có thể bỏ "int" trong định lý 1.2. Nhận xét 1.8 Trong trường hợp không suy biến, như nhận xét 1.4, chúng ta có thể bỏ "∃B ∈ B(v)" và " ∃B ∈ S(v)" trong định lý 1.2. Ta cũng có thể bỏ "∃I ⊂ N" do sự không suy biến của v ∈ F . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  22. 19 Chương 2 ĐỘ NHẠY VÀ ĐIỀU KIỆN TỐI ƯU CHO NGHIỆM CỦA BÀI TOÁN ĐA MỤC TIÊU PHI TUYẾN Chương này trình bày các điều kiện cần và đủ cấp 1, cấp 2 cho nghiệm hữu hiệu của bài toán tối ưu đa mục tiêu phi tuyến khả vi có ràng buộc, và các điều kiện đủ cho độ nhạy Fréchet của nghiệm hữu hiệu của bài toán nhiễu. Trong trường hợp hữu hạn chiều, chúng tôi trình bày điều kiện đủ cho độ nhạy Lipschitz và sự tồn tại đạo hàm theo phương của nghiệm hữu hiệu của bài toán nhiễu. Các kết quả trong chương này là của S. Bolitinéanu và M. El Maghri [6] 2.1 Các khái niệm và kết quả bổ trợ Xét các không gian Banach thực X, Y, Z. Không gian Y được trang bị một nón lồi đóng, nhọn Q, tức là αQ + βQ ⊂ Q với mọi α, β ∈ [0, +∞) và Q ∩ (−Q) = {0}. Nón Q xác định quan hệ thứ tự bộ phận 0 0 y Q y ⇐⇒ y − y ∈ Q. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  23. 20 Cho F, G, H là các ánh xạ khả vi cấp 2 theo nghĩa Fréchet m (F, G, H): X → Y × Z × R . Ta xét bài toán tối ưu vectơ sau đây: (V OP ) min F (x), G(x) = 0, m H(x) ∈ R− . Tập chấp nhận được của (VOP) kí hiệu là: m S = {x ∈ X : G(x) = 0,H(x) ∈ R− }. Ta xét ba loại nghiệm của bài toán (VOP). Điểm x∗ ∈ S là: (i) Nghiệm hữu hiệu yếu của bài toán (VOP) khi và chỉ khi @x ∈ S sao cho F (x∗) − F (x) ∈ intQ, trong đó intQ là phần trong (tô pô) của Q; (ii) Nghiệm hữu hiệu của (VOP) khi và chỉ khi @x ∈ S sao cho : F (x∗) − F (x) ∈ Q \{0}; (iii) Nghiệm hữu hiệu chính thường của (VOP) (xem [4]) khi và chỉ khi tồn tại một nón lồi đóng nhọn K với Q \{0} ⊂ intK, sao cho @x ∈ S để F (x∗) − F (x) ∈ K \{0}. Các tập điểm hữu hiệu chính thường, điểm hữu hiệu và điểm hữu hiệu yếu được kí hiệu lần lượt là Ep,Ee,Ew. Rõ ràng là Ep ⊂ Ee ⊂ Ew (2.1) Để đơn giản cho việc trình bày, chúng ta sẽ kí hiệu Eσ là tập điểm σ- hữu hiệu phụ thuộc vào sự lựa chọn σ ∈ {p, e, w}. ∗ ∗ m Hàm Lagrange L : X × Y × Z × R → R của bài toán vectơ (VOP) được cho bởi m X L(x, λ, u, v) = hλ, F (x)i + hu, G(x)i + vihi(x), i=1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  24. 21 trong đó (λ, u, v) là các nhân tử Lagrange; Y ∗ và Z∗ là các đối ngẫu tô pô của Y và Z; hλ, yi là giá trị của λ ∈ Y ∗ tại y ∈ Y . Kí hiệu (hi)i=1, ,m = H Với x∗ ∈ S, ta kí hiệu tập chỉ số của các ràng buộc tích cực là ∗ ∗ I(x ) = {i ∈ {1, . . . , m} : hi(x ) = 0}. Nón cực và nón cực chặt là ∗ Q+ = {λ ∈ Y : hλ, yi ≥ 0, ∀y ∈ Q}, 0 ∗ Q+ = {λ ∈ Y : hλ, yi > 0, ∀y ∈ Q \{0}}. Với λ ∈ Y ∗, ta xét bài toán vô hướng hóa của (VOP): (Pλ) minhλ, F (x)i, x ∈ S. ∗ S Tập nghiệm tối ưu của (Pλ) là ánh xạ đa trị E : Y → 2 , xác định với mọi λ ∈ Y ∗ bởi E(λ) := arg minhλ, F (x)i. x∈S Để đơn giản các ký hiệu, ta đặt: ( Q+\{0}, nếu σ = w, Λσ = 0 (2.2) Q+, nếu σ = p. Nhắc lại kết quả vô hướng hóa sau (xem [12]): [ Eσ ⊃ E(λ). (2.3) λ∈Λσ (2.3) trở thành đẳng thức nếu Y là phản xạ và (VOP) là lồi (tức là S là tập lồi và F là Q-lồi: ∀x, x0 ∈ X và α ∈ [0, 1], αF (x)+(1−α)F (x0)−F (αx+(1−α)x0) ∈ Q). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  25. 22 Chú ý rằng trong trường hợp này ta giả thiết G là afin và hi(i = 1 . . . m) là các hàm lồi. Điểm x∗ ∈ S được gọi là σ- hữu hiệu địa phương của (VOP), σ ∈ {p, e, w}, khi và chỉ khi S được thay bởi S ∩ N (x∗) trong định nghĩa điểm σ- hữu hiệu, trong đó N (x∗) là lân cận của x∗. Nhận xét 2.1 Kết quả vô hướng hóa (2.3) cũng đúng cho điểm σ- hữu hiệu địa phương, khi xét E(λ) là tập nghiệm tối ưu địa phương của (Pλ). Nhận xét 2.2 Theo nhận xét trên và các bao hàm thức (2.1)- (2.3), dễ dàng thấy rằng với bài toán (VOP) lồi, mọi nghiệm σ- hữu hiệu địa phương là nghiệm σ- hữu hiệu toàn cục. 2.2 Điều kiện cần cấp 1 và cấp 2 cho nghiệm hữu hiệu Trong phần này ta sẽ xét các trường hợp σ ∈ {e, w} và (VOP) có hữu hạn hàm mục tiêu, tức là r r Y = R ,Q = R+,F = (f1, . . . , fr). với tập chỉ số I ⊂ {1, . . . , l} và V = (v1, . . . , vl), ta kí hiệu |I| là bản số của I và VI = (vi)i∈I. Với x∗ ∈ S, ta xét tập ∗ Kσ(x ) = arg max |J|, ∗ J∈Jσ(x ) trong đó : ( {J ⊂ {1, . . . , r} : ∃xJ ∈ S, F (x∗) − F (xJ ) ∈ |J| \{0}}, nếu σ = e, J (x∗) = J J R+ σ J ∗ J |J| {J ⊂ {1, . . . , r} : ∃x ∈ S, FJ (x ) − FJ (x ) ∈ intR+ }, nếu σ = w. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  26. 23 Ta xét tập các điểm hữu hiệu mạnh: r \ Es = arg min fj(x) x∈S j=1 Mệnh đề sau đây là hiển nhiên. Mệnh đề 2.1 Nếu Es 6= ∅ thì Ee = Es. Bởi vì các tính chất của các phần tử của tập Es tương tự như các tính chất cực tiểu trong tối ưu vô hướng, và hầu hết các bài toán đa mục tiêu không có nghiệm hữu hiệu mạnh, cho nên ở đây ta sẽ xét trường hợp không tầm thường Es = ∅. Bổ đề 2.1 ∗ ∗ ∗ Nếu x ∈ Eσ thì Kσ(x ) 6= ∅, và ∀J ∈ Kσ(x ), ta có 1 ≤ |J| < r. Chứng minh j j ∗ Do Es = ∅, tồn tại j ∈ {1, . . . , r} và x ∈ S sao cho fj(x ) < fj(x ). ∗ ∗ ∗ Như vậy, {j} ∈ Jσ(x ). Do đó Kσ(x ) 6= ∅ và ∀J ∈ Kσ(x ), 1 ≤ |J| < r. ∗ ∗ Nếu |J| = r thì J = {1, . . . , r}, và J ∈ Jσ(x ) mâu thuẫn với x ∈ Eσ.  Nhận xét 2.3 Thay S bởi S ∩ N (x∗), trong đó N (x∗) là lân cận của x∗. Bổ đề 2.1 cũng đúng cho nghiệm σ- hữu hiệu địa phương. Ta xét điều kiện chính quy (CQ) cấp 1 và cấp 2 sau đây cho nghiệm hữu hiệu (tức là σ = e). Định nghĩa 2.1 ∗ 1 (i) Ta nói rằng x ∈ S thỏa mãn điều kiện chính quy (CQ)e nếu tồn ∗ tại J ∈ Ke(x ) sao cho ∗ a) ∇xG(x ) ∈ L(X, Z) là toàn ánh, ∗ b) ∃ξ ∈ Ker∇xG(x ): ∗ ∗ ∗ hξ, ∇xfj(x )i < 0, hξ, ∇xhi(x )i < 0, ∀j ∈ J, ∀i ∈ I = I(x ). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  27. 24 ∗ 2 (ii) Ta nói rằng x ∈ S thỏa mãn điều kiện chính quy (CQ)e theo các ∗ nhân tử Lagrange (λ, v) nếu tồn tại J ∈ Ke(x ) sao cho ∗ |J+| |I+| (a) C = ∇x(FJ+ , G, HI+ )(x ) ∈ L(X, R × Z × R ) là toàn ánh, (b) ∃ξ ∈ KerC : ∗ ∗ hξ, ∇xfj(x )i 0}, J0 = {j ∈ J : λj = 0}, I+ = {i ∈ I : vi > 0}, I0 = {i ∈ I : vi = 0}. Với các nghiệm hữu hiệu yếu (tức là σ = w ), ta sẽ xét điều kiện chính quy sau. Định nghĩa 2.2 ∗ 1 (i) Ta nói rằng x ∈ S thỏa mãn điều kiện chính quy (CQ)w nếu ∗ (a) ∇xG(x ) ∈ L(X, Y ) là toàn ánh, ∗ ∗ ∗ (b) ∃ξ ∈ Ker∇xG(x ): hξ, ∇xhi(x )i < 0, ∀i ∈ I = I(x ) ∗ 2 (ii) Ta nói rằng x ∈ S thỏa mãn điều kiện chính quy (CQ)w theo các ∗ nhân tử Lagrange (λ, v) nếu tồn tại J ∈ Kw(x ) và k ∈ {1, . . . , n}\ J sao cho (a) Toán tử:  ∗  ∇xFK+ (x ) −1K+ ∗ |K+| |I+| D =  ∇xG(x ) 0  ∈ L(X × R, R × Z × R ) ∗ ∇xHI+ (x ) 0 là toán ánh, (b) ∃(ξ, α) ∈ KerD : ∗ ∗ hξ, ∇xfj(x )i < α, hξ, ∇xhi(x )i < 0, ∀j ∈ K0, ∀i ∈ I0, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  28. 25 trong đó |K+| 1K+ = (1, , 1) ∈ R , K+ = {j ∈ J ∪ {k} : λi > 0}, K0 = {j ∈ J ∪ {k} : λj = 0}. Định lý tiếp theo sẽ trình bày các điều kiện cần cấp 1 và cấp 2 cho nghiệm σ- hữu hiệu địa phương của (VOP). Với tập J ⊂ {1, . . . , r}, |J| < r, và k ∈ {1, . . . , r}\ J, ta đặt:  r {λ ∈ R+ : λk = 1, λj = 0, ∀j 6∈ J ∪ {k}}, nếu σ = e, Ωσ(J, k) = r P {λ ∈ R+ : λj = 1, λj = 0, ∀j 6∈ J ∪ {k}}, nếu σ = w.  j∈J∪{k} Định lý 2.1 ∗ 1 Giả sử x là điểm σ- hữu hiệu địa phương thỏa mãn điều kiện (CQ)σ. ∗ 1 Nếu σ = w, chọn tùy ý J ∈ Kw(x ); nếu σ = e, ta lấy tập J trong (CQ)e. ∗ ∗ ∗ Khi đó với mỗi k ∈ {1, . . . , r}\ J, tồn tại λ ∈ Ωσ(J, k), u ∈ Z và ∗ m v ∈ R+ sao cho (i) Điều kiện dừng và điều kiện bù đúng: ∗ ∗ ∗ ∗ ∗ ∗ ∇xL(x , λ , u , v ) = 0, vi hi(x ) = 0, ∀i ∈ {1, . . . , m}. ∗ 2 ∗ ∗ m Hơn nữa, nếu x thỏa mãn điều kiện (CQ)σ theo (λ , v ) ∈ Ωσ(J, k) × R+ và nếu (i) thỏa mãn thì (ii) Điều kiện sau đúng: 2 ∗ ∗ ∗ ∗ ∗ h∇xL(x , λ , u , v )ξ, ξi ≥ 0, ∀ξ ∈ Ker∇x(FJ∪{k}, G, HI)(x ) . Chứng minh Trước hết ta chứng minh bổ đề sau: Bổ đề 2.2 ∗ ∗ Giả sử x ∈ Eσ. Với mỗi J ∈ Kσ(x ) và k ∈ {1, . . . , r}\ J, các phát biểu sau đây là đúng: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  29. 26 (i) Nếu σ = w thì (x∗, 0) là nghiệm tối ưu của bài toán vô hướng: ∗ (Pw(x )) min t, ∗ fj(x) − t ≤ fj(x ), ∀j ∈ J ∪ {k}, x ∈ S, t ∈ R. (ii) Nếu σ = e thì x∗ là nghiệm tối ưu của bài toán vô hướng: ∗ (Pe(x )) min fk(x), ∗ fj(x) ≤ fj(x ), ∀j ∈ J, x ∈ S. Chứng minh ∗ (i) Xét σ = w. Do Ew ⊂ S, rõ ràng là (x , 0) là chấp nhận được của ∗ ∗ bài toán Pw(x ). Nếu (x , 0) không là nghiệm tối ưu thì tồn tại điểm chấp ∗ nhận được (x, t) của bài toán Pw(x ) sao cho t |J|. Điều này mâu ∗ thuẫn với J ∈ Ke(x ).  Nhận xét 2.4 Dễ thấy (giống như nhận xét 2.3) bổ đề 2.2 vẫn đúng với mọi nghiệm σ- hữu hiệu địa phương x∗ của (VOP) và nhận được nghiệm tối ưu địa ∗ phương của bài toán vô hướng Pσ(x ). Bây giờ chúng ta quay lại chứng minh định lý 2.1: Trường hợp 1: σ = e. Với mỗi nghiệm hữu hiệu địa phương x∗, theo nhận Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  30. 27 ∗ ∗ xét 2.4 và bổ đề 2.2, ta có x là nghiệm tối ưu địa phương của (Pe(x )) mà hàm Lagrange là m X ∗ X Le(x, η, u, v) = fk(x) + (fj(x) − fj(x )) + hu, G(x)i + vihi(x), j∈J i=1 |J| ∗ m trong đó (x, η, u, v) ∈ X × R × Z × R . 1 Giả thiết (CQ)e chính là điều kiện chính quy Mangasarian- Fromovitz ∗ (xem[10]) cho bài toán vô hướng Pe(x ). Do vậy điều kiện cần cấp 1 Karush- ∗ ∗ ∗ ∗ Kuhn-Tucker đúng cho Pe(x ): tồn tại các nhân tử Lagrange (λJ , u , v ) ∈ |J| ∗ m R+ × Z × R+ sao cho ∗ ∗ ∗ ∗ ∗ ∗ ∇xLe(x , λJ , u , v ) = 0, vi hi(x ) = 0, ∀i ∈ {1, . . . m}. (2.4) Nếu ta đặt ∗ ∗ λk = 1vàλj = 0, ∀j ∈ {1, . . . , r}\ (J ∪ {k}), ∗ thì ta có λ ∈ Ωe(J, k) và điều kiện (i) đúng. ∗ 2 Mặt khác, nếu x thỏa mãn điều kiện (CQ)e (điều kiện chính quy ∗ ∗ ∗ Mangasarian- Fromovitz cấp 2) theo (λJ , v ) của bài toán Pe(x ), và nếu (i) đúng thì ta có thêm điều kiện: 2 ∗ ∗ ∗ ∗ ∗ h∇xLe(x , λJ , u , v )ξ, ξi ≥ 0, ∀ξ ∈ Ker∇x(FJ∪{k}, G, HI)(x ). (2.5) Vì vậy (ii) thỏa mãn. Trường hợp 2: σ = w. Đối với nghiệm hữu hiệu yếu địa phương x∗, từ ∗ ∗ nhận xét 2.4 và bổ đề 2.2, ta có (x , 0) là nghiệm tối ưu của Pw(x ) với hàm Lagrange là m X ∗ X Lw(x, t, η, u, v) = t+ ηj(fj(x)−t−fj(x ))+hu, G(x)i+ vihi(x), j∈J∪{k} i=1 |J|+1 ∗ m trong đó (x, t, η, u, v) ∈ X × R × R × Z × R . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  31. 28 1 Ta có điều kiện (CQ)w tương đương với điều kiện chính quy Mangasarian- ∗ ∗ Fromovitz của bài toán Pw(x ) tại (x , 0) ∗ (a) ∇(x,t)(G(x))(x , 0) ∈ L(X × R,Z) là toán ánh, ∗ (b) Tồn tại (ξ, α) ∈ Ker∇(x,t)(G(x))(x , 0) sao cho ∗ h(ξ, α), ∇(x,t)(fj(x) − t)(x , 0)i < 0, ∗ h(ξ, α), ∇(x,t)(hi(x) − t)(x , 0) < 0i, (∀j ∈ J ∪ {k}, ∀i ∈ I). ∗ ∗ ∗ Do đó, điều kiện Karush-Kuhn-Tucker đúng: tồn tại (λJ∪{k}, u , v ) ∈ |J|+1 ∗ m R+ × Z × R+ sao cho ∗ ∗ ∗ ∗ ∇(x,t)Lw(x , 0, λJ∪{k}, u , v ) = 0, (2.6) ∗ ∗ vi hi(x ) = 0, ∀i ∈ {1, , m}. Điều này tương đương với m X ∗ ∗ ∗ ∗ X ∗ ∗ λj ∇xfj(x ) + hu , ∇xG(x )i + vi ∇xhi(x ) = 0, j∈J∪{k} i=1 (2.7) X ∗ λj = 1. j∈J∪{k} ∗ Do vậy, nếu ta lấy λj = 0, với mỗi j 6∈ J ∪ {k}. Từ (2.7) ta nhận ∗ ∗ 2 được λ ∈ Ωw(J, k) và điều kiện (i) đúng. Mặt khác x thỏa mãn (CQ)w ∗ ∗ m theo (λ , v ) ∈ Ωw(J, k) × R+ và (i) đúng tương đương với điều kiện ∗ ∗ Mangasarian- Fromovitz cấp 2 cho bài toán Pw(x ) tại điểm (x , 0) theo ∗ ∗ (λJ∪{k}, v ) thỏa mãn (2.7). Vì vậy ta nhận được 2 ∗ ∗ ∗ ∗ h∇(x,t)Lw(x , 0, λJ∪{k}, u , v )(ξ, β), (ξ, β)i ≥ 0, (2.8) trên không gian không điểm của các gradient của các ràng buộc tích cực và hàm mục tiêu tại điểm (x∗, 0), tức là ∗ ∀(ξ, β) ∈ Ker∇(x,t)(FJ∪{k}(x) − t × 1J∪{k},G(x),HI(x), t)(x , 0) ∗ = Ker∇x(FJ∪{k}, G, HI)(x ) × {0}. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  32. 29 Nhưng (2.8) tương đương với  r m   X ∗ 2 ∗ ∗ 2 ∗ X ∗ 2 ∗ λj ∇xfj(x ) + hu , ∇xG(x )i + vi ∇xhi(x ) ξ, ξ ≥ 0, j=1 i−1 ∗ với mọi ξ ∈ Ker∇x(FJ∪{k}, G, HI)(x ). Như vậy điều kiện (ii) đúng và chứng minh định lý 2.1 hoàn thành. Nhận xét 2.5 Sử dụng (2.1) ta thấy rằng định lý 2.1 cũng đúng đối với nghiệm hữu hiệu chính thường địa phương. Nhận xét 2.6 2 1 (CQ)σ kéo theo (CQ)σ. Nhận xét 2.7 1 2 Một điều kiện đơn giản hơn và mạnh hơn (CQ)e và (CQ)e và do đó 1 2 ∗ là điều kiện đủ để có (CQ)e hoặc (CQ)e là toán tử ∇x(FJ , G, HI)(x ) là toàn ánh. Trong trường hợp hữu hạn chiều điều này có nghĩa là các vectơ ∗ ∗ ∗ {∇xfj(x ), ∇xgl(x ), ∇xhi(x ), ∀j ∈ J, ∀i ∈ I, l = 1, . . . , s} độc lập tuyến tính. 1 2 Ta có thể phát biểu nhận xét tương tự cho (CQ)w và (CQ)w. Ví dụ 1 ∗ một điều kiện đủ cho (CQ)w ∇x(G, HI)(x ) là toàn ánh. 2.3 Điều kiện đủ cấp hai cho nghiệm hữu hiệu Cũng như trong trường hợp vô hướng, điều kiện đủ cấp 2 cho nghiệm σ- hữu hiệu có thể phát biểu như sau: Định nghĩa 2.3 ∗ ∗ Ta nói rằng điểm x ∈ S thỏa mãn điều kiện (SC)σ nếu tồn tại λ ∈ ∗ ∗ ∗ m Λσ, u ∈ Z , v ∈ R+ và α > 0 sao cho các điều kiện sau đây đúng: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  33. 30 (i) Điều kiện dừng và điều kiện bù : ∗ ∗ ∗ ∗ ∗ ∗ ∇xL(x , λ , u , v ) = 0, vi hi(x ) = 0, ∀i ∈ {1, . . . , m}; 2 ∗ ∗ ∗ ∗ 2 ∗ (ii) h∇xL(x , λ , u , v )ξ, ξi ≥ αkξk , ∀ξ ∈ Ker∇x(G, HI)(x ); ∗ ∗ (iii) Điều kiện bù chặt: vi > 0, ∀i ∈ I = I(x ). Định lý dưới đây chỉ ra các điều kiện đủ. Định lý 2.2 ∗ ∗ Nếu điểm x ∈ S thỏa mãn điều kiện (SC)σ thì x là nghiệm σ- hữu hiệu địa phương của (VOP). Chứng minh: ∗ ∗ x ∈ S thỏa mãn điều kiện (SC)σ thì x thỏa mãn điều kiện đủ tối ưu cấp 2 của bài toán vô hướng (Pλ∗ ) (xem [2]). Do đó, x∗ là cực tiểu địa phương. Sử dụng (2.3) và nhận xét 2.1 ta suy ra điều phải chứng minh.  n s Trong phần này, ta xét trường hợp X = R ,Z = R ,G = (g1, , gs), Y có thể có số chiều vô hạn. Định nghĩa 2.4 ∗ 0 Ta nói rằng điểm x ∈ S thỏa mãn điều kiện (SC )σ nếu tồn tại ∗ ∗ ∗ ∗ m λ ∈ Λσ, u ∈ Z và v ∈ R+ sao cho các điều kiện sau đây đúng: (i) Điều kiện dừng và điều kiện bù: ∗ ∗ ∗ ∗ ∗ ∗ ∇xL(x , λ , u , v ) = 0, vi hi(x ) = 0, ∀i ∈ {1, ··· , m}; 2 ∗ ∗ ∗ ∗ ∗ (ii) h∇xL(x , λ , u , v )ξ, ξi ≥ 0, ∀ξ ∈ Ker∇x(G, HI+ )(x ) \{0}, ∗ ∗ trong đó I+ = {i ∈ I(x ): vi > 0}. Định lý 2.3 ∗ 0 ∗ Giả sử điểm x ∈ S thỏa mãn điều kiện (SC )σ. Khi đó, x là nghiệm σ- hữu hiệu địa phương của (VOP). Chứng minh Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  34. 31 Chứng minh giống như chứng minh định lý 2.2. Dễ thấy x∗ thỏa mãn điều kiện đủ cấp 2 mạnh của bài toán vô hướng (Pλ∗ ).  Nhận xét 2.8 Theo (2.1 ), khi lấy σ = p ta có thể thấy định lý 2.2 và 2.3 cũng đúng đối với các điểm hữu hiệu chính thường địa phương. Nhận xét 2.9 Ta có thể xét trường hợp Z có số chiều vô hạn. Bằng cách thay thế ∗ ∗ ∗ toán tử ∇x(G, HI+ )(x ) bởi toán tử ∇x(hλ ,F (x)i, G, HI)(x ) trong định nghĩa 2.4. Nhận xét 2.10 0 Điều kiện (i) của (SC)σ và (SC )σ là điều kiện cần cho nghiệm σ- hữu hiệu địa phương x∗, khi giả thiết một điều kiện chính quy đúng (chẳng 1 hạn (CQ)σ) Tuy nhiên, điều kiện (ii) của định nghĩa (2.3) hoặc (2.4) là mạnh hơn điều kiện (ii) của định lý (2.1). 2.4 Phân tích độ nhạy của nghiệm hữu hiệu Với mỗi giá trị của tham số nhiễu π ∈ Π ta xét bài toán tối ưu vectơ nhiễu sau đây: (V OP π) min F (x, π), G(x, π) = 0, m H(x, π) ∈ R− , trong đó m (F, G, H): X × Π → Y × Z × R , với X, Y, Z, Π là không gian Banach thực, X phản xạ. Tập chấp nhận được của bài toán (V OP π) là m S(π) = {x ∈ X : G(x, π) = 0,H(x, π) ∈ R− }. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  35. 32 Hàm Lagrange của bài toán (V OP π) là m X L(x, π, λ, u, v) = hλ, F (x, π)i + hu, G(x, π)i + vihi(x, π). i=1 Định nghĩa 2.5 Cho π∗ ∈ Π. Ta nói rằng x∗ ∈ S(π∗) thỏa mãn điều kiện độ nhạy đủ π∗ ∗ (SSC)σ của (V OP ) nếu x thỏa mãn (SC)σ của định nghĩa 2.3 đối với π∗ ∗ ∗ ∗ ∗ m (V OP ), tức là tồn tại λ ∈ Λσ, u ∈ Z , v ∈ R+ và α > 0 sao cho các quan hệ sau đây đúng: (i) Điều kiện dừng và điều kiện bù: ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∇xL(x , π , λ , u , v ) = 0, vi hi(x , π ) = 0, ∀i ∈ {1, . . . , m}; 2 ∗ ∗ ∗ ∗ ∗ 2 ∗ (ii) h∇xL(x , π , λ , u , v )ξ, ξi ≥ αkξk , ∀ξ ∈ Ker∇x(G, HI)(x ); (iii) Điều kiện bù chặt: ∗ ∗ ∗ ∗ ∗ vi > 0, ∀i ∈ I = I(x , π ) = {i ∈ {1, . . . , m} : hi(x , π ) = 0}. Hơn nữa, ta giả sử các điều kiện sau đây đúng: (iv) Tính chính quy: ∂2F ∂2G ∂2H ∂2F ∂2G ∂2H F, G, H, , , , , , ∂x2 ∂x2 ∂x2 ∂x∂π ∂x∂π ∂x∂π liên tục trong một lân cận của (x∗, π∗). (v) Điều kiện chính quy: ∗ |I| B = ∇x(G, HI)(x ) ∈ L(X, Z × R ) là toàn ánh. Ta có thể giả sử rằng bài toán không nhiễu là (V OP π∗ ), và nó ứng với ∗ π = π . Kết quả tiếp theo chỉ ra rằng với điều kiện (SSC)σ, điểm chấp nhận được của bài toán không nhiễu là điểm σ- hữu hiệu địa phương và Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  36. 33 bảo toàn tính chất này sau một nhiễu nhỏ. Định lý 2.4 ∗ ∗ π∗ Giả sử x ∈ S(π ) thỏa mãn (SSC)σ của (V OP ) với nhân tử La- grange (λ∗, u∗, v∗). Khi đó: (i) x∗ là nghiệm σ-hữu hiệu địa phương của bài toán không nhiễu (V OP π∗ ). (ii) Tồn tại một lân cận Ω ⊂ Π × Y ∗ của (π∗, λ∗) và C1 ánh xạ duy nhất ∗ m Ω ∩ (Π × Λσ) → X × Z × R , (π, λ) 7→ (x(π, λ), u(π, λ), v(π, λ)), (π∗, λ∗) 7→ (x∗, u∗, v∗) π sao cho x(π, λ) ∈ S(π) thỏa mãn (SSC)σ của (V OP ) với các nhân tử La- grange là (λ, u(π, λ), v(π, λ)). Như vậy với mỗi (π, λ) gần (π∗, λ∗), x(π, λ) là nghiệm σ- hữu hiệu địa phương của bài toán nhiễu (V OP π). Chứng minh Để chứng minh định lý này, trước tiên ta trình bày một kết quả về độ nhạy cho bài toán nhiễu vô hướng. Đây là một tổng quát hóa vô hạn chiều của định lý Fiacco [9]. Giả sử P, X, Z là các không gian Banach thực, X phản xạ và ánh xạ: m X × P 3 (x, p) 7→ (f(x, p), G˜(x, p), H˜ (x, p)) ∈ R × Z × R . Với mỗi giá trị của tham số nhiễu p ∈ P, xét bài toán tối ưu nhiễu vô hướng: (P˜p) min f(x, p), G˜(x, p) = 0 ˜ m H(x, p) ∈ R− Tập chấp nhận được của (P˜p) kí hiệu bởi S˜(p) và hàm Lagrange được cho Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  37. 34 bởi m X ˜ L˜(x, p, u, v) = f(x, p) + hu, G˜(x, p)i + vihi(x, p). i=1 ∗ Ta giả sử rằng bài toán không nhiễu là (P˜p∗ ) ứng với p = p . Trong trường hợp vô hướng này, các điều kiện (SSC)σ được mô tả bởi định nghĩa dưới đây. Định nghĩa 2.6 Ta nói rằng x∗ ∈ S˜(p∗) thỏa mãn điều kiện (SC) của bài toán vô hướng ˜ ∗ (Pp∗ ) nếu x thỏa mãn (SSC)σ trong trường hợp riêng Y = R, Π = P và F = f với λ∗ = 1. Kết quả tiếp theo là một tổng quát hóa vô hạn chiều định lý của Fiacco [9]. Bổ đề 2.3 ∗ ∗ Cho x ∈ S˜(p ) thỏa mãn (SC) của (P˜p∗ ) với các nhân tử Lagrange (u∗, v∗). Khi đó, (a) x∗ là cực tiểu địa phương chặt của bài toán vô hướng không nhiễu ∗ ∗ (P˜p∗ ) và các nhân tử Lagrange (u , v ) là duy nhất. (b) Tồn tại lân cận Ω˜ ⊂ P của p∗ và hàm khả vi liên tục duy nhất ∗ m Ω˜ → X × Z × R , p 7→ (x(p), u(p), v(p)), p∗ 7→ (x∗, u∗, v∗), sao cho x(p) ∈ S˜(p) thỏa mãn điều kiện (SC) của (P˜p) và có các nhân tử Lagrange duy nhất (u(p), v(p)). Như vậy với mọi p ∈ Ω˜, x(p) là cực tiểu địa phương chặt của bài toán vô hướng nhiễu (P˜p). Chứng minh (a) Ta biết rằng xem [3] x∗ là cực tiểu địa phương chặt. Với mỗi phần tử : ∗ m η = (u, v) ∈ Z × R , Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  38. 35 ta kí hiệu 0 ∗ |I| η = (u, vI) ∈ Z × R , trong đó I là tập chỉ số các ràng buộc tích cực của bài toán không nhiễu ∗ (P˜p∗ ) tại x và 0 X ˜ L˜I(x, p, η ) = f(x, p) + hu, G˜(x, p)i + vihi(x, p). i∈I Mỗi nhân tử Lagrange thỏa mãn ∗ ∗ ∗ 0 ∂f/∂x(x , p ) + B η = 0, vi = 0, ∀i∈ / I, ∗ ∗ ∗ ∗ ∗ |I| trong đó B ∈ L(W ,X ) là liên hợp của toán tử B và W = Z × R là |I| đối ngẫu của W = Z × R . Do B là toàn ánh [điều kiện (v)] và điều này kéo theo tính đơn ánh của B∗, ta suy ra tính duy nhất của η∗ = (u∗, v∗). (b) Tiếp theo, sử dụng định lý hàm ẩn ta sẽ chứng minh sự tồn tại và duy nhất của hàm khả vi liên tục: p 7→ (x, η0) = (x(p), η0(p)), thỏa mãn quan hệ dưới đây với mọi p gần p∗: 0 ∇xL˜I(x, p, η ) = 0, (2.9) G˜(x, p) = 0, (2.10) ˜ hi(x, p) = 0, ∀i ∈ I (2.11) (x(p∗), η0(p∗)) = (x∗, η0∗). (2.12) Ta chỉ cần chứng minh tính song ánh của toán tử Jacobian theo (x, η0), tại điểm x∗, p∗, η0∗ của hàm đã được xác định hệ trên. Đặt 2 ˜ ∗ ∗ ∗ 2 ˜ ∗ ∗ 0∗ A = ∇xL(x , p , η ) = ∇xLI(x , p , η ). Ta sẽ chỉ ra rằng toán tử Jacobian sau là song ánh: AB∗ J = ∈ L(X × W ∗,X∗ × W ). (2.13) B 0 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  39. 36 Giả sử (x, z) ∈ KerJ . Khi đó: Ax + B∗z = 0, Bx = 0. Vì vậy, x ∈ KerB, hAx, xi + hB∗z, xi = 0. Do đó, hAx, xi = 0, và điều kiện (ii) kéo theo x = 0. Khi đó, do tính đơn ánh của B∗, ta nhận được z = 0. Như vậy J là đơn ánh. Bây giờ ta xét (y, w) ∈ X∗ × W . Ta sẽ chỉ ra rằng hệ: Ax + B∗z = y, (2.14) Bx = w, (2.15) có nghiệm (x, z) ∈ X × W ∗. Bởi vì B là toàn ánh, ta có thể tìm được x0 ∈ X sao cho (2.15) thỏa mãn. Đặt x = x0 + x00, với x00 ∈ KerB, và cố định x0. Bởi vì Bx = w, ta chỉ cần tìm được x00 ∈ KerB, z ∈ W ∗ sao cho Ax” + B∗z = y − Ax0. Như vậy, ta phải chỉ ra: Γ = X∗, (2.16) trong đó Γ = AKerB + B∗(W ∗) = AKerB + (KerB)⊥, bởi vì B là toàn ánh kéo theo : B∗(W ∗) = (KerB)⊥, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  40. 37 trong đó (KerB)⊥ = {χ ∈ X∗ : hχ, ξi = 0, ∀ξ ∈ KerB}. xem [3]. Trước hết ta chứng minh Γ là tập con đóng của X∗. Xét dãy γ(i) = Aξ(i) + χ(i) ∈ Γ, với ξ(i) ∈ KerB, χ(i) ∈ (KerB)⊥, γ(i) hội tụ tới phần tử γ ∈ X∗. Ta có hγ(i) − γ(j), ξ(i) − ξ(j)i = hA(ξ(i) − ξ(j)), ξ(i) − ξ(j)i ≥ α||ξ(i) − ξ(j)||2. Từ đó α||ξ(i) − ξ(j)|| ≤ ||γ(i) − γ(j)||. (i) (i) Do đó, dãy (ξ )i hội tụ tới phần tử ξ. Từ đó suy ra dãy (χ )i cũng hội tụ tới phần tử χ. Nhưng KerB và (KerB)⊥ là đóng, nên γ = Aξ + χ ∈ Γ. Vậy Γ là đóng. Bây giờ ta giả sử rằng Γ 6= X∗, khi đó tồn tại γˆ ∈ Γ⊥ \{0}. Nhưng do tính phản xạ của X nên γˆ ∈ X \{0}. Như vậy ∀ξ ∈ KerB và z ∈ W ∗, Ta được: hAξ, γˆi = 0, hB∗z, γˆ = 0i. (2.17) Do vậy hz, Bγˆi = 0, ∀z ∈ W ∗. Sử dụng hệ quả của định lý Hahn- Banach, ta nhận được Bγˆ = 0, tức là γˆ ∈ KerB. Hơn nữa, khi lấy ξ =γ ˆ trong (2.17), từ điều kiện (ii) ta nhận được một mâu thuẫn: γˆ = 0. Do đó, Γ = X∗ và như vậy J là toàn ánh. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  41. 38 Theo định lý hàm ẩn, tồn tại duy nhất một hàm khả vi liên tục, xác định gần p∗ vào X × W ∗, 0 0 p 7→ (x, η ) = (x(p), η (p)) = (x(p), u(p), vI(p)), thỏa mãn (2.9)- (2.12). Hơn nữa, do tính liên tục và điều kiện độ bù chặt (iii), với mọi p gần p∗ ta có vi(p) > 0, ∀i ∈ I. Với mọi p gần p∗, ta đặt vi(p) = 0, ∀i∈ / I. Tính liên tục kéo theo: ∀p gần p∗, điều kiện (iv) thỏa mãn và ˜ hi(x(p), p) 0 sao cho 2 hApξ, ξi ≥ α(p)||ξ|| , ∀ξ ∈ KerBp, (2.18) trong đó 2 ˜ ˜ ˜ Ap = ∇xL(x(p), p, u(p), v(p)),Bp = ∇x(G, hI)(x(p), p). Theo bổ đề Hoffmann xem [2], tồn tại hằng số k1 > 0 sao cho dist(ξ, KerB) ≤ k1||Bξ||, ∀ξ ∈ X. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  42. 39 Điều này tương đương với việc nói rằng tồn tại hằng số k2 > 0 (k2 > k1) sao cho mỗi ξ ∈ X có thể viết được 0 00 00 ξ = ξ + ξ , với ξ ∈ KerB và ||ξ || ≤ k2||Bξ||. Ta lấy ξ ∈ KerBp. Do Bpξ = 0, ta nhận được: 00 ||ξ || ≤ k2||B − Bp||||ξ||. (2.19) Mặt khác, hApξ, ξi = hAξ, ξi + h(Ap − A)ξ, ξi (2.20) 2 ≥ hAξ, ξi − ||Ap − A||||ξ|| , và hAξ, ξi = hAξ0, ξ0i + 2hAξ0, ξ00i + hAξ00, ξ00i. Do đó hAξ, ξi ≥ α||ξ0||2 − ||ξ00||(2||A||||ξ0|| + ||A||||ξ00||); Nhưng từ (2.19) và do ||ξ0|| ≤ ||ξ|| + ||ξ00||, ta có 0 00 (2||A||||ξ || + ||A||||ξ ||) ≤ k3||ξ|| ∗ với k3 là hằng số không phụ thuộc ξ. Ta xét p trong lân cận của p sao cho k2||B − Bp|| ≤ 1/2. Khi đó do (2.19) và ||ξ0|| ≥ ||ξ|| − ||ξ00||, ta nhận được ||ξ0|| ≥ (1/2)||ξ||. Do đó, 2 2 hAξ, ξi ≥ (1/4)α|ξ|| − k2||B − Bp||||ξ|| k3. (2.21) Từ (2.20)- (2.21) ta suy ra (2.18) đúng với α(p) = (1/4)α − k2k3||B − Bp|| − ||Ap − A||, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  43. 40 và α(p) > 0, với p gần p∗. Do đó điều kiện (ii) thỏa mãn tại x(p). Như vậy x(p) thỏa mãn (SC). Bổ đề 2.3 được chứng minh.  Bây giờ ta quay lại chứng minh định lý 2.4 . Ta xét bài toán vô hướng hóa (V OP π) sau đây π (Pλ ) minhλ, F (x, π)i x ∈ S(π). Áp dụng bổ đề 2.3 cho f(x, p) = hλ, F (x, π)i, G˜(x, p) = G(x, π), H˜ (x, p) = H(x, π), với P = Π × Y ∗, p = (π, λ). π ˜ Trong trường hợp này, (Pλ ) là (Pp). Hơn nữa, x ∈ S(π) thỏa mãn π (SC) của bài toán vô hướng (Pλ ) với λ ∈ Λσ, tham số nhiễu (π, λ) và các π nhân tử Lagrange (u, v), khi và chỉ khi x thỏa mãn (SSC)σ của (V OP ) với nhân tử Lagrange (λ, u, v) và tham số nhiễu π. Nếu ta đặt Ω = Ω˜, thì rõ ràng ánh xạ cho trong định lý là hạn chế trên Ω ∩ (Π × Λσ) của ánh xạ đang xét trong bổ đề. Sử dụng (2.3) và nhận xét 2.1, suy ra kết luận cần chứng minh của định lý.  Bây giờ ta trình bày độ nhạy Lipschitz. π n Xét bài toán vectơ nhiễu (V OP ) trong trường hợp X = R ,Z = s q R ,G = (g1, . . . , gs). Không gian nhiễu là Π = R . Điều kiện Jittorntrum có thể phát biểu trong trường hợp vectơ như sau: Định nghĩa 2.7 ∗ ∗ 0 π∗ ∗ Ta nói rằng điểm x ∈ S(π ) thỏa mãn (SSC )σ của (V OP ) nếu x 0 thỏa mãn (SC )σ [điều kiện (i)-(ii) từ định nghĩa 2.4 ] và các điều kiện sau: 2 ∗ ∗ (iii) Các hàm F, gj, hi là lớp C với (x, π) trong lân cận của (x , π ) với ∀i, j; Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  44. 41 ∗ ∗ ∗ ∗ (iv) Các vectơ {∇xgj(x , π ), ∇xhi(x , π ), j = 1, . . . , s, ∀i ∈ I} là độc lập tuyến tính. Nhận xét 2.11 Trong trường hợp hữu hạn chiều, điều kiện (v) của (SSC)σ tương 0 đương với điều kiện (iv) của (SSC )σ. Định lý 2.5 ∗ ∗ 0 π∗ Cho điểm x ∈ S(π ) thỏa mãn (SSC )σ của (V OP ) với các nhân ∗ ∗ ∗ 0 tử Lagrange (λ , u , v ) cho bởi (i) của (SC )σ. Khi đó, (i) x∗ là nghiệm σ- hữu hiệu địa phương của bài toán không nhiễu (V OP π∗ ). q ∗ ∗ ∗ (ii) Tồn tại lân cận Ω ⊂ R × Y của (π , λ ) và ánh xạ Lipschitz duy nhất: q n s m Ω ∩ (R × Λσ) → R × R × R , (π, λ) 7→ (x(π, λ), u(π, λ), v(π, λ)), (π∗, λ∗) 7→ (x∗, u∗, v∗) có đạo hàm theo phương (một phía) cấp 1 tại (π∗, λ∗) theo mọi phương 0 π sao cho x(π, λ) ∈ S(π) và thỏa mãn điều kiện (SSC )σ của (V OP ) với các nhân tử Lagrange (λ, u(π, λ), v(π, λ)). Như vậy với mỗi (π, λ) gần (π∗, λ∗), x(π, λ) là một nghiệm σ- hữu hiệu địa phương của bài toán nhiễu (V OP π). Chứng minh Chứng minh dựa trên kết quả độ nhạy của bài toán vô hướng của Jittorntrum. Ta xét bài toán vô hướng tham số (P˜p) . Trong trường hợp hữu hạn chiều bài toán này có thể được viết lại như sau: (P˜p) min f(x, p), g˜j(x, p) = 0, ∀j = 1, . . . , s, ˜ hi(x, p) ≤ 0, ∀i = 1, . . . , m, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  45. 42 n l với X = R và P = R . Điều kiện Jittorntrum ở đây là (SCJ) tương tự 0 ∗ điều kiện (SSC )σ với λ = 1. Định lý 2.6 ([11]) ∗ ∗ Cho x ∈ S˜(p ) thỏa mãn (SCJ) của bài toán (P˜p∗ ) với các nhân tử Lagrange (u∗, v∗) cho bởi (i) từ định nghĩa 2.4. Khi đó, ∗ (a) x là điểm cực tiểu địa phương chặt của bài toán không nhiễu (P˜p∗ ) và các nhân tử (u∗, v∗) là duy nhất. (b) ∀p gần p∗, tồn tại duy nhất ánh xạ liên tục p 7→ (x(p), u(p), v(p)) sao cho (x(p∗), u(p∗), v(p∗)) = (x∗, u∗, v∗) và có đạo hàm theo phương cấp ∗ 1 tại p theo mọi phương và thỏa mãn (SCJ) của (P˜p). Như vậy, x(p) là cực tiểu địa phương chặt của bài toán nhiễu (P˜p) với các nhân tử Lagrange (u(p), v(p)). (c) ∃L > 0 và δ > 0 sao cho ∀p thỏa mãn ||p − p∗|| < δ, ||(x(p), u(p), v(p)) − (x∗, u∗, v∗)|| ≤ L||p − p∗||. Chứng minh định lý 2.5 cũng tương tự như chứng minh định lý 2.4 . 0 π Điểm x thỏa mãn (SSC )σ của (V OP ) khi và chỉ khi x thỏa mãn (SCF ) ˜ π cho (Pp) ≡ (Pλ ) với tham số nhiễu p = (π, λ). Như vậy, có thể kiểm tra π mọi giả thiết của định lý Jittorntrum đúng với bài toán vô hướng (Pλ ) và sử dụng (2.3) với nhận xét 2.1 ta suy ra kết luận của định lý 2.5.  Nhận xét 2.12 Ta có thể thấy từ (2.1) rằng định lý 2.4 và 2.5 cũng đúng cho các nghiệm hữu hiệu khi xét với σ = p. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  46. 43 Kết luận Luận văn đã trình bày các kết quả nghiên cứu về độ nhạy của đỉnh hữu hiệu và diện hữu hiệu của bài toán đa mục tiêu tuyến tính cùng với các kết quả về độ nhạy Fréchet và độ nhạy Lipschitz của nghiệm hữu hiệu của bài toán đa mục tiêu phi tuyến với các hàm khả vi Fréchet. Đối với bài toán đa mục tiêu tuyến tính, luận văn trình bày các điều kiện đảm bảo sau một nhiễu nhỏ, một đỉnh hữu hiệu và một diện hữu hiệu vẫn tương ứng là một đỉnh hữu hiệu và một diện hữu hiệu của bài toán nhiễu. Đối với bài toán đa mục tiêu phi tuyến với dữ liệu khả vi Fréchet, luận án trình bày các điều kiện đảm bảo nghiệm hữu hiệu của bài toán thuộc lớp C1 hoặc Lipschitz địa phương theo tham số nhiễu. Nghiên cứu độ nhạy của nghiệm hữu hiệu của bài toán tối ưu đa mục tiêu là đề tài thời sự, cần được tiếp tục nghiên cứu và phát triển. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  47. 44 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 và kỹ thuật Hà nội. [2] Đỗ Văn Lưu, (1999), Lý thuyết các điều kiện tối ưu, NXB Khoa học và kỹ thuật Hà nội. Tài liệu tiếng Anh [3] Alexée, V., Tikhomirov, V., M. and Fomin, S. (1982), Commande optimale , MIR, Moscow, Russia. [4] Benson, H., P. (1983), Efficient and Proper effciency in vector Maxi- mization with respect to cones, Journal of Mathematical Analysis and Applications, Vol 93, pp 273- 289. [5] Bolitinéanu, S. and Craven, B. D. (1992), Linear multicriteria sensi- tivity and shadow costs, Optimization 26, 115- 127. [6] Bolitinéanu, S. and El Maghri, M. (1998) , Second order effciency conditions and sensitivity of efficient points,Journal of Optimization Theory and Applications , 98(3), 569-592. [7] Dantzig, G. B., Orden, A. and Wolfe, P. (1955), The generalized sim- plex algorithm for minimizing a linear form under linear inequality restraints, Pacific Journal of Mathematics . 5, 183- 195. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  48. 45 [8] El Maghri, M. (2002), Degenerate linear multicriteria sensitivity, Op- timization . 51(1), 93-108. [9] Fiacco,A. (1983), Introduction to sensitivity and stability analysis in nonlinear programming, Academic Press, New York, New York. [10] Ioffe, A., D. and Tikhomirov, V., M. (1979), Theory of extremal prob- lems, North Holland Publishing Company, Amsterdam, Netherlands. [11] Jittorntrum, K. (1984), Solution point differentiability without strict complementarity in nonlinear programming, Mathematical Program- ming Studies, Vol 21, pp 127 - 138. [12] Luc, D., T. (1989), Theory of vector optimization , Lectures Notes in Economics and Mathematical Systems, Springer Verlag, Berlin, Ger- many. [13] Murty, K. G. (1983), Linear programming ,Wiley & Sons, New York. [14] Yu, P. L(1985), Multiple- Criteria decision making, Plenum, New York. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên