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

ĐẠ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 ĐẠ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 iMụ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 1Mở đầ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 2Fré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 3thâ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 4Chươ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, trong đó [C(.), A(.), b(.)] : N (0) → Rr×n × Rm×n × Rm là các hàm của tham số nhiễu p ∈ N (0),N (0) là lân cận của điểm gốc 0 ∈ Rq. Ở đâ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 5chấp nhận được của (Pp) là Γ(p) = {x ∈ Rn : 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à Ee(p) = {x ∈ Γ(p) : @x′ ∈ Γ(p), C(p)x′ ≤ C(p)x,C(p)x′ 6= C(p)x}, và 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. Với mỗi p, xét ánh xạ đa trị E(., p) : Rr → 2Γ(p) xác định với mọi λ ∈ Rr bởi E(λ, p) = arg min x∈Γ(p) λTC(p)x, (1.1) 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 đó Λσ = { Rr+\{0}, nếu σ = w, intRr+, 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 tổng quát hơn khi nón thứ tự Rr+ đượ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 y′ ≤ y ⇔ y − y′ ∈ Q, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 6và y′ < y ⇔ y − y′ ∈ intQ. Trong trường hợp này Rr+ đượ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): v = [ A−1B b 0 ] (1.3) trong đó A−1B b ≥ 0, A−1B 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: Γ = {x = [ xB xN ] ∈ Rn : xB + A−1B ANxN = A−1B b, x ≥ 0}. (1.4) 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 đó Γ(p) = {x = [ xB xN ] ∈ Rn : xB + A−1B (p)AN(p)xN = A−1B (p)b(p), x ≥ 0}. (1.5) Vì vậy ta có thể xác định nhiễu của v bởi v(p) = [ A−1B (p)b(p) 0 ] (1.6) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 7Nhắc lại rằng nếu A−1B 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 Khi v là không suy biến thì với mọi p gần 0, do tính liên tục,A−1B (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) = (p, 0) cho bởi (1.6) với B = {1} là không chấp nhận được, và 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ố: D = {i ∈ B : (A−1B b)i = 0}, (1.8) và Dc = {i ∈ B : (A−1B b)i > 0}. (1.9) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 8Sắp xếp lại phân hoạch các cột của AB và các hàng của A −1 B như sau: AB = [ADADc], A −1 B = [ (A−1B )D (A−1B )Dc ] . Với mọi chỉ số i ∈ D, ta kí hiệu hàng thứ i của (A−1B )D bởi A−1i và với bất kỳ chỉ số j, k ∈ {1, . . . , q}, ∂jb := ∂b ∂pj (0), ∂2kjb := ∂2b ∂pj∂pk (0), ∂jADc := ∂ADc ∂pj (0), ∂2kjADc := ∂2ADc ∂pj∂pk (0). 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ơ J (i) = (A−1i {∂jb− ∂jADc(A−1B )Dcb})j=1...q = 0, và (ii) Với mọi i ∈ D, q × q− ma trận đối xứng thực H(i) = ( A−1i {(∂kADc(A−1B )Dc∂jADc + ∂jADcADc∂kADc − ∂2kjADc) × (A−1B )Dcb− (∂kADc(A−1B )Dc + ∂jADcADc)∂kb+ ∂2kjb} ) (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 9(ii)Với mọi i ∈ D, ma trận H(i) là xác định dương. Chứng minh Tính chấp nhận được của v(p) theo (1.5), (1.6) tương đương vớiA−1B (p)b(p) ≥ 0. Điều này tương đương với (A−1B )D(p)b(p) = (A −1 i (p)b(p))i∈D ≥ 0, bởi vì theo (1.9) và tính liên tục (A−1B )Dc(p)b(p) > 0 với mọi p gần 0. Kí hiệu vi(p) = A −1 i (p)b(p) với mỗi i ∈ D. Sử dụng (1.8) ta suy ra vi(p) ≥ 0 tương đương với vi(p) ≥ vi(0) với mọi p gần 0. Điều đó có nghĩa là 0 ∈ Rq 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 ( ∂vi ∂pj (0) ) j=1...q = 0 (1.10) và ma trận Hessian ( ∂2vi ∂pk∂pj (0) ) (k,i)={1,...,q}2 (1.11) 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ổ đề. Từ A−1B (p)AB(p) = Im, trong đó Im là m ×m− ma trận đồng nhất. Với mọi j ∈ {1, . . . , q}, ta có ∂A−1B ∂pj (p) = −A−1B (p) ∂AB ∂pj (p)A−1B (p). (1.12) Từ đó suy ra với mọi i ∈ D, ∂A−1i ∂pj (p) = −A−1i (p) ∂AB ∂pj (p)A−1B (p). (1.13) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 10 Sử dụng (1.13) và đạo hàm một tích, ta nhận được ∂vi ∂pj (p) = ∂(A−1i (p)b(p)) ∂pj (p) = A−1i (p) { − ∂AB ∂pj (p)A−1B (p)b(p) + ∂b ∂pj (p) } . (1.14) 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: ∂2vi ∂pk∂pj (p) = ∂A−1i ∂pk (p) { − ∂AB ∂pj (p)A−1B (p)b(p) + ∂b ∂pj (p) } + A−1i (p) { − ∂ 2AB ∂pk∂pj (p)A−1B (p)b(p) − ∂AB ∂pj (p) ∂(A−1B (p)b(p)) ∂pk (p) + ∂2b ∂pk∂pj (p) } . Sử dụng (1.10) và cách đánh giá (∂vi/∂pj)(0), ta nhận được ∂(A−1B (p)b(p)) ∂pk (0) = (A−1B )Dc ( − ∂ADc ∂pk (0)(A−1B )Dcb+ ∂b ∂pk (0) ) . (1.15) Cuối cùng, bằng cách sử dụng (1.8), (1.15 ) để đánh giá (∂2vi/∂pk∂pj)(0) ta nhận được H(i). 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: J (i) = A−1i ∇b(0), và H(i) = m∑ j=1 (A−1i )j∇2bj(0), trong đó (A−1i )j (tương ứng bj) là thành phần thứ j của vectơ A −1 i (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 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) = đoạn thẳng đóng nối điểm gốc với điểm (1,0) trong R2. 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 + CNxN = ĈNxN + Cv, (1.16) trong đó ĈN là rút gọn của ma trận C theo N tức là ĈN = CN − CBA−1B 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 : ∃λ ∈ Λσ,∃B ∈ B(v) : λT ĈN ≥ 0. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 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) ∃λ ∈ Λσ,∃B ∈ S(v) : λT ĈN > 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à ∃λ ∈ Λσ,∃B ∈ B(v) : λT ĈN ≥ 0. Chứng minh 1. Ta có thể tách chặt một đỉnh từ đa diện của nó: ∃d ∈ Rn \ {0} : ∀x ∈ Γ \ {v}, dTv < dTx. (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 ∈ Γ, λTCv ≤ λTCx. 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 x∈Γ c(k)x, (1.20) trong đó c(k) := λTC + (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 ∈ N∗,∃Bk ∈ B(v) : ĉNk(k) ≥ 0, (1.21) trong đó ĉNk(k) = cNk(k) − CBk(k)A−1BkANk là hàm mục tiêu rút gọn và Nk = {1, ..., n}\Bk. Mặt khác, ta có ĉNk(k) = λ T ĈNk + 1 k d̂TNk, (1.22) trong đó d̂TNk = d T Nk − dTBkA−1BkANk và ĈNk cho bởi (1.17). Nhưng dãy (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 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ó ∀j ≥ J, λT ĈN + 1 kj d̂TN ≥ 0. Cho j ↗ +∞ ta nhận được điều kiện cần. Ta có ngay điều ngược lại. Thật vậy, nếu λT ĈN ≥ 0 thế thì theo (1.4), (1.16) ta có ∀x ∈ Γ, λTCx = λT (ĈNxN + Cv) ≥ λTCv, 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: ĈN(p) = CN(p)− CB(p)A−1B (p)AN(p). (1.23) Bởi vì p 7→ ĈN(p) liên tục tại p = 0, từ (i) suy ra với mọi p gần 0 λT ĈN(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 (ii) đúng, thế thì ma trận ĈN(p) ≡ ĈN . Do đó, λT ĈN(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 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: ∃λ ∈ Λσ,∃B ∈ B(v),∃I ⊂ N : λT ĈI ≥ 0, λT ĈN\I = 0. (ĈI có các cột Ĉi(∀i ∈ I) và ĈN\I có các cột khác của ĈN). 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 ĈN\I sau đây là độc lập tuyến tính trong Rr, và ∃λ ∈ intΛσ,∃B ∈ S(v),∃I ⊂ N : λT ĈI > 0, λT ĈN\I = 0, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 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à ∃λ ∈ Λσ,∃B ∈ S(v),∃I ⊂ N : λT ĈI ≥ 0, λT ĈN\I = 0. Chứng minh Trước hết ta cần bổ đề sau đây. Bổ đề 1.2 Cho F là một diện của đa diện P ⊂ Rn. Khi đó tồn tại d ∈ Rn sao cho: ∀x′ ∈ F, ∀x ∈ P \ F, dTx′ < dTx. Chứng minh Ta biết rằng mỗi đa diện P ⊂ Rn có thể viết dưới dạng: P = {x ∈ Rn : aTj x ≤ bj,∀j ∈ {1, . . . , l}}, và mỗi diện F của P có dạng: F = {x ∈ Rn : aTj x = bj,∀j ∈ J}, trong đó J ⊂ {1, . . . , l}. Đặt d = −∑j∈J aj. Lấy x ∈ P \ F , khi đó tồn tại j′ ∈ J sao cho aTj′x < bj′. Lấy x′ ∈ F , ta có ngay dTx′ = −bj′ − ∑ j∈J\{j′} bj < −aTj′ − ∑ j∈J\{j′} aTj x = d Tx. 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 x∈Γ c(k)x, (1.26) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 16 trong đó c(k) = λTC + (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 ∈ N∗,∃Bk ∈ B(v) : ĉNk(k) ≥ 0. (1.27) Do c(k)x = ĉNk(k)xNk + c(k)x, theo (1.26) rõ ràng ∀k ∈ N∗, F = {x = (xBk, xNk) ∈ Γ : xIk = 0}, (1.28) trong đó Ik = {i ∈ Nk : ĉi(k) > 0}. Do đó, theo (1.27), Nk \ Ik = {i ∈ Nk : ĉi(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 , ĉI(kj) = λ T ĈI + 1 kj d̂TI > 0, λT ĉN\I(kj) = λT ĈN\I + 1 kj d̂TN\I = 0. Cho j ↗ +∞, ta nhận được λT ĈI ≥ 0 và λT ĈN\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 minλT