Header Page of 161 TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI KHOA TOÁN TRẦN THỊ THUẬN LƯỢC ĐỒ VÔ HƯỚNG HÓA PASCOLETTI-SERAFINI VÀ ĐỘ NHẠY NGHIỆM KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Toán giải tích HÀ NỘI, 2016 Footer Page of 161 Header Page of 161 TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI KHOA TOÁN TRẦN THỊ THUẬN LƯỢC ĐỒ VÔ HƯỚNG HÓA PASCOLETTI-SERAFINI VÀ ĐỘ NHẠY NGHIỆM KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Toán giải tích Người hướng dẫn khóa luận TS Nguyễn Văn Tuyên HÀ NỘI, 2016 Footer Page of 161 Header Page of 161 LỜI CẢM ƠN Em xin gửi lời cảm ơn tới thầy cô giáo trường Đại học Sư phạm Hà Nội 2, thầy cô gióa khoa Toán giúp đỡ em trình học tập trường tạo điều kiện cho em hoàn thành đề tài khóa luận tốt nghiệp Đặc biệt em xin bày tỏ lòng biết ơn sâu sắc tới thầy Nguyễn Văn Tuyên, người thầy truyền thụ kiến thức, tận tình giúp đỡ, hướng dẫn em suốt trình học tập, nghiên cứu hoàn thiện khóa luận Trong trình nghiên cứu, không tránh khỏi sai sót hạn chế Em kính mong nhận đóng góp ý kiến thầy giáo, cô giáo toàn thể bạn đọc để khóa luận hoàn thiện Em xin chân thành cảm ơn ! Hà Nội, tháng năm 2016 Trần Thị Thuận Footer Page of 161 iii Header Page of 161 LỜI CAM ĐOAN Em xin cam đoan hướng dẫn thầy giáo Nguyễn Văn Tuyên khóa luận em hoàn thành không trùng với đề tài khác Trong làm khóa luận này, em kế thừa thành khoa học nhà khoa học với trân trọng biết ơn Hà Nội, tháng năm 2016 Sinh viên Trần Thị Thuận Footer Page of 161 Header Page of 161 Mục lục Lời mở đầu 1 Bài toán tối ưu véctơ 1.1 Một số khái niệm 1.2 Quan hệ hai quan hệ thứ tự 1.3 Điểm hữu hiệu 1.4 Sự tồn điểm hữu hiệu 11 1.5 12 Bài toán tối ưu véctơ (VOP) Lược đồ vô hướng hóa Pascoletti-Serafini độ nhạy nghiệm 15 2.1 Đặt toán 15 2.2 Sự tương đương toán véctơ toán vô hướng 17 2.3 Độ nhạy nghiệm toán toán tối ưu véctơ 23 Tài liệu tham khảo 30 Footer Page of 161 v Header Page of 161 Lời mở đầu Vô hướng hóa công cụ mạnh tối ưu véctơ , thay toán tối ưu véctơ họ toán tối ưu vô hướng Kĩ thuật không cho phép nghiên cứu định tính toán tối ưu mà cho phép ta sử dụng phương pháp giải số cho toán tối ưu vô hướng Một cách vô hướng cổ điển xét toán tổng có trọng hàm mục tiêu, hay tổng quát xét toán tối ưu vô hướng hàm mục tiêu hợp hàm mục tiêu phiếm hàm tuyến tính (một nhân tử) lấy nón đối ngẫu nón sinh thứ tự Một cách khác xét điều kiện tối ưu bậc nhất, nhân tử Lagrange đóng vai trò tham số vô hướng hóa Năm 1984, dựa ý tưởng mới, Pascoletti-Serafini [2] véctơ toán xét tích hợp hệ ràng buộc Hàm mục tiêu toán bổ trợ Pascoletti-Serafini số thực biểu diễn độ lớn khả di chuyển véctơ lấy từ phần tương đối nón sinh thứ tự Áp dụng cho toán tối ưu véctơ , toán bổ trợ Pascoletti-Serafini toán quy hoạch tuyến tính giải thuật toán thuật toán điểm thuật toán đơn hình Dantzig Đặc trưng điểm quan trọng việc sử dụng sử dụng phương pháp Pascolettin-Serafini cho toán tối ưu véctơ tuyến tính Lược đồ vô hướng hóa Pascoletti-Serafini Helbing [3, 4] sử dụng để đưa thuật toán lặp cho toán tối ưu véctơ phi tuyến tính để giải toán quy hoạch toàn phương véctơ Sau đó, StemaKarwat [5] khảo sát tính liên tục, tính Lipschitz, tính khả vi theo tham số nghiệm toán vô hướng lược đồ vô hướng hóa PascolettiSerafini Gần đây, cách sử dụng lược đồ vô hướng hóa này, Eichfelder phát triển báo [6, 7] sách [8] phương pháp giải với điều khiển tham số cải biên cho toán tối ưu véctơ tuyến tính Phương pháp áp dụng cho toán đa mục tiêu hai mức cho số toán y học Mục đích khóa luận trình bày số tính chất Footer Page of 161 Header Page of 161 lược đồ Pascoletti-Serafini cho toán tối ưu véctơ tổng quát Một số đặc trưng độ nhạy nghiệm toán tối ưu véctơ với hàm mục tiêu khả vi liên tục đến cấp hai khảo sát Các kết khóa luận trình bày sở báo [2] Pascoletti Serafini Ngoài phần mở đầu, kết luận tài liệu tham khảo, khóa luận gồm hai chương: Chương trình bày số kiến thức chuẩn bị Nội dung chương trình bày số kiến thức giải tích lồi toán tối ưu véctơ Chương trình bày lược đồ vô hướng hóa Pascolettin-Serafini Mục 2.1 trình bày số tính chất lược đồ vô hướng hóa PascolettinSerafini cho toán tối ưu véctơ Mục 2.3 trình bày độ nhạy nghiệm toán tối ưu véctơ ứng với tham số nhiễu nhỏ toán bổ trợ Hà Nội, ngày tháng năm Tác giả Trần Thị Thuận Footer Page of 161 Header Page of 161 Chương Bài toán tối ưu véctơ 1.1 Một số khái niệm Giả sử E không gian tuyến tính, R tập số thực Định nghĩa 1.1 Tập A ⊂ E gọi lồi, nếu: ∀x1 , x2 ∈ A; ∀λ ∈ R : ≤ λ ≤ ⇒ λx1 + (1 − λ)x2 ∈ A Ví dụ 1.1 Các nửa không gian tập lồi Hình tam giác, hình tròn mặt phẳng tập lồi Hình cầu đơn vị không gian Banach tập lồi Định nghĩa 1.2 Giả sử A ⊂ X Tương giao tất tập lồi chứa A gọi bao lồi tập A, kí hiệu coA Nhận xét 1.1 a) coA tập lồi Đó tập lồi bé chứa A; b) A lồi A = coA Định nghĩa 1.3 Tập C ⊂ E gọi nón có đỉnh nếu: ∀x ∈ C, ∀λ > ⇒ λx ∈ C C gọi nón có đỉnh x0 , C − x0 nón có đỉnh Định nghĩa 1.4 Nón C có đỉnh gọi nón lồi, C tập lồi, nghĩa là: ∀x, y ∈ C, ∀λ, µ > ⇒ λx + µy ∈ C Footer Page of 161 Header Page of 161 Ví dụ 1.2 Các tập sau Rn : {ξ1 , ξ2 , , ξn ∈ Rn : ξi ≥ 0, i = 1, , n} (nón orthant không âm) {ξ1 , ξ2 , , ξn ∈ Rn : ξi > 0, i = 1, , n} (nón orthant dương) nón lồi có đỉnh Đó nón lồi quan trọng Rn Ngoài ra, cho D ⊆ Rm nón lồi, nón cực dương D xác định bởi: D∗ := {x∗ ∈ Rm :< x∗ , x >≥ 0, ∀x ∈ D} Cho a, b ∈ Rm , a ≥D b a − b ∈ D; a ≥ m m ≥ 0, i = 1, , m Kí hiệu Rm + := {x ∈ R : x ≥ 0} cho g : X → R Hàm g gọi D- giống lồi S ⊆ X : ∀x1 , x2 ∈ S, ∀α ∈ [0, 1], ∃x ∈ S cho (1 − α)g(x1 ) + αg(x2 ) − g(x) ∈ D Điều biết đến [13] g hàm D- giống lồi tập g(S) + D lồi Định nghĩa 1.5 Tập A ⊂ Rn gọi tập affine, (1 − λ)x + λy ∈ A(∀x, y ∈ A, ∀λ ∈ R) Định nghĩa 1.6 Tương giao tất tập affine chứa tập A ⊂ Rn gọi bao affine A kí hiệu af f A Định nghĩa 1.7 Phần tương đối tập A ⊂ Rn phần A af f A (bao affine); kí hiệu riA Các điểm thuộc riA gọi điểm tương đối tập A Footer Page of 161 Header Page 10 of 161 Nhận xét 1.2 intA := {x ∈ Rn : ∃ > 0, x + B ⊂ A} , riA := {x ∈ af f A : ∃ > 0, (x + B) ∩ af f A ⊂ A} , B hình cầu đơn vị đóng Rn Tiếp theo xem xét số nón thường gặp Cho C nón lồi không gian véctơ tôpô E Kí hiệu l(C) := C ∩ (−C) (phần tuyến tính C); clC (bao đóng C); tập A ⊆ E, Ac phần bù A E, nghĩa Ac = E\A Định nghĩa 1.8 Chúng ta nói nón C là: (a) Nhọn l(C) = 0; (b) Nón sắc bao đóng nhọn; (c) Nón có giá chặt C\l(C) chứa nửa không gian mở nhất; (d) Nón (clC) + C\l(C) ⊆ C, tương đương clC + C\l(C) ⊆ C\l(C) Ví dụ 1.3 theo định nghĩa 1.8 Cho Rn không gian Euclide n-chiều Khi đó, nón orthant không âm Rn+ gồm tất vectơr Rn với toạ độ không âm nón lồi, sắc, đóng, có giá chặt nón Tập {0} nón, nón tầm thường Tập hợp véctơ với toạ độ dương nón đúng, nhọn, có giá chặt không nón sắc Bất kì nửa không gian đóng nón đúng, có giá chặt không nón nhọn Cho Ω không gian vectơr gồm tất dãy x = {xn } số thực Cho C = {x ∈ Ω : xn ≥ 0, ∀n}, C nón nhọn, lồi Tuy nhiên, ta chưa biết nón C nón nón sắc ta chưa biết tôpô xác định không gian Footer Page 10 of 161 Header Page 22 of 161 2.2 Sự tương đương toán véctơ toán vô hướng Định lý 2.1 Với nghiệm yếu x (P), ba (0, x, 0) nghiệm ◦ P(p, q) với p = F (x) q ∈ Λ ◦ Chứng minh Ta có: p = F (x), q ∈ Λ toán bổ trợ: P(p, q) Max{ξ | (ξ, x, λ) ∈ R × Λ, F (x) = p + ξq + λ} Từ ta suy toán: P(p, q) max{ξ | (ξ, x, λ) ∈ R × Λ, ξq ∈ −Λ} Ta lại có (0, x, 0) điểm chấp nhận P(p, q), từ ◦ ξq ∈ −Λ nên ta có −ξq ∈ Λ, q ∈ Λ ⊂ Λ Do ξ ≤ Vậy (0, x, 0) nghiệm toán P(p, q) Định lý 2.2 Với nghiệm (ξ, x, λ) P(p, q) x nghiệm hữu hiệu yếu (P) λ ∈ ∂Λ Chứng minh Nếu x không nghiệm hữu hiệu yếu (P), tồn x ∈ X λ ∈ Λ0 cho F (x ) = F (x) + λ Do (ξ, x, λ) nghiệm ◦ P(p, q), nên F (x ) = p + ξq + λ + λ Bây ta có λ + λ ∈ Λ tồn ◦ ε > cho λ + λ − εq ∈ Λ Vì vậy, từ F (x ) = p + (ε + ξ)q + λ + λ − εq, ta suy (ε + ξ, x , λ + λ − εq) điểm chấp nhận toán P(p, q)(mâu thuẫn giả thiết) Do x nghiệm hữu hiệu yếu (P) ◦ Cuối cùng, λ ∈ / ∂Λ λ phải nằm Λ Thế tồn ε > cho (ε + ξ, x, λ − εq) điểm chấp nhận toán P(p, q)(mâu thuẫn giả thiết) Vậy x nghiệm hữu hiệu yếu (P) λ ∈ ∂Λ Định lý 2.3 Cho (ξ, x, λ) nghiệm toán P(p, q) Khi đó, x trội x tồn số khác không λ ∈ ∂Λ cho (ξ, x , λ + λ ) nghiệm toán P(p, q) Chứng minh Nếu x trội x, tồn số khác không λ ∈ Λ cho F (x ) = F (x) + λ , Footer Page 22 of 161 17 Header Page 23 of 161 nghĩa là, F (x ) = p+ξq +(λ+λ ) Rõ ràng, (ξ, x , λ+λ ) nghiệm hữu hiệu ◦ ◦ (P) Từ Định lí 2.2, ta suy λ + λ ∈ ∂Λ Nếu λ ∈ Λ, λ + λ ∈ Λ Do đó, λ ∈ ∂Λ Điều ngược lại hiển nhiên Ba định lí trình bày mối liên hệ nghiệm địa phương toán tối ưu véctơ với nghiệm toán bổ trợ Ta giả sử rằng, X không gian tôpô ◦ Định lý 2.4 Nếu x Λ-tối ưu địa phương, ba (0, x, 0) ◦ nghiệm địa phương toán P (F (x), q) q ∈ Λ Chứng minh Giả sử điểm chấp nhận z = (0, x, 0) nghiệm địa phương toán P (F (x), q) Khi đó, lân cận Uξ × Ux × Uλ z, tồn điểm chấp nhận z = (ξ , x , λ ) với ξ > ◦ Khi đó, F (x ) = F (x) + ξ q + λ Vì ξ q + λ ∈ Λ Ux lân cận tùy ý ◦ x, nên x Λ-tối ưu địa phương Định lý 2.5 Nếu F liên tục z = (ξ, x, λ) nghiệm địa phương ◦ toán P(p, q), x Λ-tối ưu địa phương λ nằm biên ∂Λ Λ Chứng minh Ta chứng minh phản chứng Chọn lân cận Uξ × Ux × Uλ z lân cận U0 Y cho λ + U0 + U0 ⊂ Uλ Từ F liên tục, ta suy tồn lân cận W x thỏa mãn F (W ) ⊂ F (x) + U0 ◦ Do đó, x không Λ-tối ưu địa phương, tồn x ∈ W ∩ Ux cho F (x ) = F (x) + λ , Footer Page 23 of 161 18 Header Page 24 of 161 với ◦ λ ∈ U0 ∩ Λ, nghĩa F (x ) = p + ξq + λ + λ ◦ λ + λ ∈ Λ Bằng cách chọn > cho − q ∈ U0 ξ + ∈ Uξ ◦ λ + λ − q ∈ Λ, ta có F (x ) = p + (ξ + ε)q + (λ + λ − εq) λ + λ − εq ∈ λ + U0 + U0 ⊂ Uλ Vì vậy, (ξ + , x , λ + λ − q) điểm chấp nhận điều mâu thuẫn với tính tối ưu z Tương tự chứng minh Định lí 2.2, ta có λ ∈ ∂Λ Định lý 2.6 Giả sử F liên tục (ξ, x, λ) nghiệm địa phương toán P(p, q).Khi đó, lân cận x, tồn x cho x trội x lân cận (ξ, x, λ), tồn (ξ, x , λ + λ ) nghiệm toán P(p, q) với λ = 0, λ ∈ ∂Λ Chứng minh Cho Uξ × Ux × Uλ lân cận (ξ, x, λ) Khi F (x) + Uλ − λ lân cận F (x) Do tính liên tục F , ta suy tồn lân cận Vx x cho F (Vx ) ⊂ F (x) + Uλ − λ Do đó, tồn x ∈ Vx ∩ Ux số khác không λ ∈ Λ ∩ (U2 − λ) thỏa mãn F (x ) = F (x) + λ Do đó, λ + λ ∈ Uλ , Footer Page 24 of 161 19 Header Page 25 of 161 (ξ, x , λ + λ) nghiệm toán P(p, q) Hơn nữa, chứng minh Định lí 2.3, ta có λ ∈ ∂Λ Điều khẳng định chiều đảo định lý Chiều thuận định lý tầm thường không đòi hỏi giả thiết tính liên tục F ◦ Như ta biết nghiệm Λ-tối ưu Λ- tối ưu Do đó, để mối liên hệ nghiệm Λ-tối ưu nghiệm toán P(p, q) cần phải khảo sát thêm Định lý sau nghiệm chặt ◦ P(p, q) đủ để đặc trưng nghiệm Λ-tối ưu toán (P) Định lý 2.7 Một điểm x Λ- tối ưu nếu: (i) x tương ứng với nghiệm (ξ, x, λ) toán P(p,q) với q ∈ Λ0 đó; (ii) (∂Λ − λ) ∩ ∂Λ ∩ (F (X) − F (x)) = {0} Chứng minh Từ Định nghĩa điểm Λ- tối ưu Định lý 2.1, ta dễ dàng chứng minh phần thuận định lý Ta chứng minh phần đảo phản chứng Giả sử x Λ-tối ưu Khi tồn x số khác không λ ∈ Λ cho: F (x ) = F (x) + λ Do F (x ) = p + ξq + λ + λ Từ Định lí 2.2 ta có λ ∈ ∂Λ Ta λ λ + λ thuộc ∂Λ Thật vậy, giả sử ◦ λ ∈ Λ; tồn ε > cho (ξ + ε, x , λ + λ − εq) điểm chấp nhận được, mâu thuẫn với tính tối ưu (ξ, x, λ) Bằng lập luận tương tự ta λ + λ ∈ ∂Λ Footer Page 25 of 161 20 Header Page 26 of 161 Do = λ ∈ (∂Λ − λ) ∩ ∂Λ ∩ (F (X) − F (x)) Bằng lập luận tương tự chứng minh định lý ta thu kết sau Định lý 2.8 Cho F liên tục Khi đó, điểm x Λ-tối ưu địa phương tồn lân cận N x cho: (i) x tương ứng với nghiệm địa phương (ξ, x, λ) toán P(p, q) ◦ với q ∈ Λ đó; (ii) (∂Λ − λ) ∩ ∂Λ ∩ (F (N ) − F (x)) = {0} Các hệ sau quan trọng, giúp ta kiểm tra cách trực tiếp Λ-tối ưu qua nghiệm toán P(p, q) Hệ 2.1 Nếu nghiệm toàn cục (ξ, x, λ) toán P(p, q) chặt λ, x Λ-tối ưu Chứng minh Giả sử điều kiện (ii) Định lí 2.7 không Khi đó, tồn λ = cho λ ∈ ∂Λ, λ + λ ∈ ∂Λ; tồn x cho F (x ) = p + ξq + (λ + λ ) Do đó, (ξ, x , λ + λ ) (ξ, x, λ) nghiệm tối ưu P(p, q) λ + λ = λ Điều mâu thuẫn với tính tối ưu chặt λ Tương tự chứng minh Hệ 2.9 ta có hệ sau Hệ 2.2 Cho F liên tục Nếu nghiệm địa phương (ξ, x, λ) toán P(p, q) chặt λ, x Λ-tối ưu địa phương Footer Page 26 of 161 21 Header Page 27 of 161 Điều kiện (ii) Định lí 2.8 trình bày lại cách hình học mặt Λ sau Đặt Λ∗ = π ∈ L(Λ) : πλ ≥ 0, với λ ∈ Λ Với π ∈ Λ∗ \{0} ta định nghĩa mặt Λπ Λ Λπ = {λ ∈ Λ : πλ = 0} Dễ thấy Λπ nón lồi đóng chứa ∂Λ Với λ ∈ Λπ , đặt Λ∗λ = {π ∈ Λ∗ : λ ∈ Λπ } Đây tập hợp tất π liên kết với mặt Λ chứa λ Định lý 2.9 Nếu λ ∈ ∂Λ, (∂Λ − λ) ∩ ∂Λ = ∪{Λπ : π ∈ Λ∗λ } Chứng minh Trước hết chứng minh bao hàm thức ⊃ Lấy y ∈ Λπ ⊂ ∂Λ Do λ ∈ Λπ Λπ nón lồi, nên y + λ ∈ Λπ ⊂ ∂Λ Vì vậy, y = (y + λ) − λ ∈ ∂Λ − λ Ngược lại, giả sử y ∈ (∂Λ − λ) ∩ ∂Λ Khi đó, tồn số khác không π ∈ Λ∗ cho π(y + λ) = Từ πy ≥ πλ ≥ 0, Footer Page 27 of 161 22 Header Page 28 of 161 ta suy πy = πλ = 0, tức λ ∈ Λπ y ∈ Λπ Định lý chứng minh Dễ dàng kiểm tra điều kiện (ii) Định lí 2.7 tương đương với ΛΠ ∩ (F (X) − F (x)) = {0}, Π ∈ Λ∗λ Do đó, Định lí 2.7 phát biểu lại sau Định lý 2.10 Các điểm x Λ- tối ưu nếu: ◦ (i) x tương ứng với nghiệm (ξ, x, λ) P(p, q) với q ∈ Λ đó; (ii) x Λπ - tối ưu với π ∈ Λ∗λ , nghĩa là, với tất mặt Λ chứa λ 2.3 Độ nhạy nghiệm toán toán tối ưu véctơ Mục dành để khảo sát độ nhạy Λ-tối ưu địa phương thông qua toán P(p, q) với p q biến thiên Trong mục ta xét nghiệm tối ưu địa phương Một vài giả thiết bổ sung mục này, cụ thể: (a) X không gian Banach phản xạ (b) Λ nón đa diện Y = Rm với r phần tử sinh (c) F khả vi Fréchet liên tục đến cấp hai Trong mục Mục 2.4, kí hiệu Λ có nghĩa ma trận ◦ sinh r cột Như vậy, λ ∈ Λ, λ ∈ Λs với s ≥ 0, λ ∈ Λ, s > Với giả thiết toán P(p, q) trở thành: Cho (p, q) ∈ Rm × L(Λ), tìm giá trị lớn ξ, cho: F (x) − p − ξq − Λs = 0, s ≥ 0, với z = (ξ, x, s) ∈ R × X × Rr Footer Page 28 of 161 23 Header Page 29 of 161 Kết phần (Định lí 2.11) dựa vào ý tưởng rằng, điểm tối ưu, điều kiện bậc cho tập hợp phương trình có nghiệm phụ thuộc vào (p, q) Tuy nhiên, nghiệm điều kiện bậc tối ưu Do đó, buộc phải xét điều kiện đủ bậc hai Các bước khác chứng minh để điều kiện đủ bậc hai thỏa mãn toàn lân cận Điều kiện 2.1 Điều kiện đủ để điểm z = (ξ, x, s) tối ưu chặt toán P(p, q) tồn ≤ µ ∈ Rr , π ∈ Rm cho: (i) − πq = 0, πDF (x) = 0, µ = πΛ; (ii) s ≥ 0, F (x) − p − ξq − Λs = ; (iii) µs = ; (iv) ánh xạ R × X × Rrn (h1 , h2 , h3 ) → (qh1 − DF (x)h2 + Λn h3 ) ∈ Rm tràn ánh, với r = + rn Λ = [Λa Λn] phân chia giả thiết bất đẳng thức ràng buộc hoạt (tức là, Sa = 0) lại rn không hoạt (tức là, Sn > 0) Lưu ý rằng, ker D(F (x) − p − ξq − Λs) có phần bù tôpô R × X × Rr , có đối chiều hữu hạn (v) Dạng toàn phương πD2 F (x) xác định âm, tức là, tồn c > cho πD2 F (x)(h, h) ≤ −c h , không gian H(x) = {h ∈ X : DF (x)h ∈ range (Λn )} Nhận xét 2.3 DF (x) đạo hàm bậc F lấy giá trị x D2 F (x) đạo hàm bậc F lấy giá trị x Chú ý πΛ ≥ πΛn = Ràng buộc mà µi = si = Footer Page 29 of 161 24 Header Page 30 of 161 gọi suy biến Kết phần cần không suy biến ràng buộc Do đó, giả thiết từ đầu toán P(p, q) ràng buộc suy biến Giả định gắn (iv) (v) Điều kiện 2.1 Chúng ta đưa vào toán tử tuyến tính: A(x) : X × Rrn (h1 , h2 ) → DF (x)h1 − Λn h2 ∈ Rm phép chiếu P : X × X rn −→ X H(x) = P (kerA(x)) ánh xạ : T : R × X × Rrn × Rm (ξ, x, Sn , π) −→ (1 − πq, πDF (x), −πΛn , F (x) − p − ξq − Λn Sn ) ∈ R × X ∗ × Rrn × Rm Chú ý T triệt tiêu điểm tối ưu Trướng hết chứng minh số bổ đề sau Bổ đề 2.1 Giả sử (hk1 , hk2 ) dãy X × Rrn thỏa mãn A(x)(hk1 , hk2 ) −→ Khi đó, ta có dist(hk1 , H(x)) −→ Chứng minh Toán tử tuyến tính A(x) cảm sinh toán tử tuyến tính A(x) : (X × Rrn )/kerA(x) −→ Rm A(x) ánh xạ 1-1 tác động không gian hữu hạn chiều, Vì vậy, bị chặn Do [(hk1 , hk2 )] −→ 0, tức inf hk1 , hk2 − (h1 , h2 ) : (h1 , h2 ) ∈ kerA(x) → Footer Page 30 of 161 25 Header Page 31 of 161 Vì vậy, inf{ hk1 − h1 : h1 ∈ H(x)} −→ Bổ đề 2.2 Nếu Điều kiện 2.1 ràng buộc suy biến (ξ, x, sn ), cột Λn độc lập tuyến tính, DT (ξ, Sn , π) ánh xạ 1-1 tràn Chứng minh Trước hết, ta DT bị chặn Lấy dãy {hk }, hk = (hk1 , hk2 , hk3 , hk4 ) ∈ R × X × Rrn × Rm cho DT hk −→ 0, tức là, −hk4 q −→ 0, (2.1) πD2 F (x)hk2 + hk4 DF (x) −→ 0, (2.2) −hk4 Λn −→ 0, (2.3) −qhk1 − DF (x)hk2 − Λn hk3 −→ (2.4) Nhân (2.4) với π, ta hk1 −→ Do đó, từ Bổ đề 2.1 (2.4), ta có inf { h2 − hk2 : h2 ∈ H(x)} −→ Từ (2.3), hk4 Λn hk3 −→ 0, hk4 DF (x)hk2 −→ Điều kéo theo πD2 F (x)(hk2 , hk2 ) −→ 0, Footer Page 31 of 161 26 (2.5) Header Page 32 of 161 Chúng kết cuối kéo theo hk2 −→ Thật vậy, giả sử tồn > cho hk2 > , với k đủ lớn Đặt h−k = hk2 / hk2 , ta có: πD2 F (x)(h−k , h−k ) −→ (2.6) Từ (v) Điều kiện 2.1 ta có c h2 ≤ πD2 F (x)(h2 , h2 ) , với h2 ∈ H(x) Vì vậy, c h2 ≤ πD2 F (x) + πD2 F (x) h−k , h−k h2 − h−k h2 + h−k , với h2 ∈ H(x); nói riêng, c ≤ πD2 F (x) inf { h2 − h−k : h2 ∈ H(x), h2 = 1} + πD2 F (x)(h−k , h−k )} Bằng cách chuyển qua giới hạn sử dụng (2.5),(2.6), ta có < c ≤ Vì vậy, tồn dãy {hk2 } −→ Không làm tính tổng quát, ta giả sử hk2 −→ Bây giờ, từ (2.2), ta suy hk4 DF (x) −→ 0; Footer Page 32 of 161 27 Header Page 33 of 161 đó, từ (2.1),(2.2),(2.3) ta có: hk4 (q, DF (x), −Λn ) −→ Do (q, DF (x), −Λn ) tràn ánh [xem (iv) Điều kiện 4.1], tồn số α > cho: hk4 (q, DF (x), −Λn ) ≥ α (q, DF (x), −Λn hk4 Vì vậy, hk4 −→ Tương tự, giả thiết cột Λn , kéo theo hk3 −→ Do đó, DT bị chặn ánh xạ 1-1 Từ tính phản xạ X, DT toán tử tự liên hợp Do liên hợp toán tử liên tục bị chặn tràn ánh, nên DT tràn ánh Nhận xét 2.4 Cần nhấn mạnh giả thiét X = X ∗∗ cần thiết để chứng minh DT có toán tử ngược Bổ đề 2.3 Cho πD2 F (x) xác định âm H(x) Khi đó, tồn lân cận x π, cho πD2 F (x ) xác định âm H(x ), với x π lân cận Chứng minh Chúng ta chứng minh bổ đề phản chứng Lấy > xk −→ x, π k −→ π cho π k D2 F (xk )(hk , hk ) > − , hk = 1, hk ∈ H(xk ) Theo giả thiết, tồn c > cho −πD2 F (x)(h, h) ≥ c, với h ∈ H(x), h = Hơn nữa, ta có, πD2 F (xk )−πD2 F (x) +2 πD2 F (x) hk −h + π k −π D2 F (xk ) ≥ c− Số hạng tiến đến 0, F lần khả vi liên tục Rõ ràng số hạng Footer Page 33 of 161 28 Header Page 34 of 161 thứ tiến đến Đối với số hạng thứ 2, ý rằng, cách sử dụng định nghĩa H(xk ) áp dụng Bổ đề 2.1, ta có inf{ hk − h : h ∈ H(x), h = 1} −→ Hơn nữa, ≥ c − ε; tùy ý nên điều nàyvô lý Từ kết trên, ta có định lý sau Định lý 2.11 Giả sử Điều kiện 2.1 thỏa mãn nghiệm (ξ, x, s) Bài toán P(p, q) với ràng buộc không suy biến Giả sử s = (sa , sn ) với sa = 0, sn > Λ = (Λa , Λn ) với cột Λn độc lập tuyến tính Khi đó, tồn địa phương hàm ϕ khả vi thỏa mãn x = ϕ(p, q) x Λ-tối ưu Từ Định lý 2.11, ta có hệ trường hợp X không gian hữu hạn chiều Hệ trình bày mối quan hệ Điều kiện 2.1 điều kiện đủ Λ-tối ưu Hệ 2.3 Nếu z = (ξ, x, s) thỏa mãn Điều kiện 2.1 với X = Rn x Λ- tối ưu địa phương Footer Page 34 of 161 29 Header Page 35 of 161 Kết luận Khóa luận trình bày số tính chất lược đồ Pascoletti-Serafini cho toán tối ưu véctơ tổng quát Một số đặc trưng độ nhạy nghiệm toán tối ưu véctơ ứng với tham số nhiễu nhỏ toán bổ trợ khảo sát khóa luận Hy vọng khóa luận tài liệu tham khảo cho bạn đọc quan tâm đến vấn đề Footer Page 35 of 161 Header Page 36 of 161 Tài liệu tham khảo [1] Luc, D.T.: Theory of Vector Optimization Springer, Berlin (1989) [2] Pascoletti, A., Serafini, P.: Scalarizing véctơ optimization problems J Optim Theory Appl 42, 499– 524 (1984) [3] Helbig, S.: An interactive algorithm for nonlinear véctơ optimization Appl Math Optim 22, 147– 151 (1990) [4] Helbig, S.: On a constructive approximation of the efficient outcomes in bicriterion véctơ optimization J Glob Optim 5, 35–48 (1994) [5] Sterna-Karwat, A.: Lipschitz and differentiable dependence of solutions on a parameter in a scalarization method J Aust Math Soc A 42, 353–364 (1987) [6] Eichfelder, G.: An adaptive scalarization method in multiobjective optimization SIAM J Optim 19, 1694–1718 (2008) [7] Eichfelder, G.: Multiobjective bilevel optimization Math Program., Ser A 123, 419–449 (2010) [8] Eichfelder, G.: Adaptive Scalarization Methods in Multiobjective Optimization Springer, Berlin (2008) [9] Huong, T., Yen,D.: The Pascoletti-Serafini Scalarization Scheme and Linear Vector Optimization J Optim Theory Appl 162(2), 559–576 (2014) Footer Page 36 of 161 ... Chương trình bày lược đồ vô hướng hóa Pascolettin -Serafini Mục 2.1 trình bày số tính chất lược đồ vô hướng hóa PascolettinSerafini cho toán tối ưu véctơ Mục 2.3 trình bày độ nhạy nghiệm toán tối... Lược đồ vô hướng hóa Pascoletti- Serafini độ nhạy nghiệm 15 2.1 Đặt toán 15 2.2 Sự tương đương toán véctơ toán vô hướng 17 2.3 Độ nhạy nghiệm toán toán... tục, tính Lipschitz, tính khả vi theo tham số nghiệm toán vô hướng lược đồ vô hướng hóa PascolettiSerafini Gần đây, cách sử dụng lược đồ vô hướng hóa này, Eichfelder phát triển báo [6, 7] sách