ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC HOÀNG THỊ QUYÊN CỰC TIỂU HÓA MỘT HÀM HỢP LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - Năm 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC HOÀNG THỊ QUYÊN CỰC TIỂU HÓA MỘT HÀM HỢP 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 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Mục lục Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i Mở đầu 1 Nội dung 4 1 Cực tiểu hợp một hàm lồi và một hàmC 1,1 4 1.1 Đạo hàm cấp 2 suy rộng . . . . . . . . . . . . . . . . . . . 4 1.2 Cực tiểu hàm hợp của một hàm lồi và một hàm C 1,1 . . . . 9 1.3 Cực tiểu hợp của hàm lồi giá trị thực mở rộng và áp dụng . 19 2 Tối ưu đa mục tiêu với các hàm hợp của hàm lồi và Lipschitz địa phương 26 2.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . 26 2.2 Vô hướng hóa trong tối ưu đa mục tiêu với các hàm hợp . . 28 2.3 Điều kiện tối ưu cấp 1 . . . . . . . . . . . . . . . . . . . . . 32 2.4 Điều kiện tối ưu cấp 2 . . . . . . . . . . . . . . . . . . . . . 39 Kết luận 45 Tài liệu tham khảo 48 i Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Mở đầu Lớp các bài toán tối ưu với hàm mục tiêu là một hàm hợp, có hoặc không có ràng buộc tập là một bộ phận quan trọng của lớp các bài toán cực trị. Nhiều mô hình các bài toán tối ưu nảy sinh từ lí thuyết các bài toán xấp xỉ. Phương pháp hàm phạt cho phép ta có thể quy bài toán tối ưu đang xét về bài toán không có ràng buộc với hàm mục tiêu là hợp của một hàm lồi và một hàm Lipschitz địa phương hoặc C 1,1 -hàm. Nhiều tác giả đã và đang nghiên cứu đề tài này, và thu được nhiều kết quả phong phú. Jeyakumar-Yang [13] đã chứng minh các điều kiện tối ưu cấp 2 cho bài toán cực tiểu hóa hợp của một hàm lồi vô hướng nửa liên tục dưới và một hàm khả vi Gâteaux với gradient Lipschitz địa phương (C 1,1 -hàm). Yang-Jeyakumar [15] đã thiết lập các điều kiện tối ưu cấp 1 và cấp 2 cho nghiệm hữu hiệu yếu của bài toán đa mục tiêu cực tiểu hóa hợp của một hàm véc tơ lồi và một hàm Lipschitz địa phương bằng phương pháp vô hướng hóa. Đề tài "Về cực tiểu hóa một hàm hợp" là đề tài có tính thời sự và được nhiều tác giả quan tâm nghiên cứu. Chính vì thế em chọn đề tài này. Luận văn trình bày các điều kiện tối ưu cấp 1 và cấp 2 cho bài toán cực tiểu hóa một hàm lồi nửa liên tục dưới và C 1,1 -hàm, và bài toán cực 1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn tiểu hóa hợp của một hàm véc tơ lồi và một hàm Lipschitz địa phương. 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: Cực tiểu hợp một hàm lồi và một hàm C 1,1 . Chương này trình bày các điều kiện tối ưu cấp 2 của Jeyakumar-Yang [13] cho bài toán cực tiểu hóa hợp của một hàm lồi vô hướng, nửa liên tục dưới và một hàm C 1,1 dưới ngôn ngữ đạo hàm suy rộng cấp 2 theo nghĩa Clarke. Chương 2: Tối ưu đa mục tiêu với các hàm hợp của hàm lồi và hàm Lipschitz địa phương. Chương 2 trình bày các điều kiện tối ưu cấp 1 và cấp 2 của Yang- Jeyakumar [15] cho nghiệm hữu hiệu yếu của bài toán đa mục tiêu cực tiểu hợp của một hàm véc tơ lồi và một hàm Lipschitz địa phương bằng phương pháp vô hướng hóa. Chú ý rằng các điều kiện tối ưu cấp 2 được trình bày cho không gian hữu hạn chiều. 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. 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 K4B đã 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 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 2 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 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 07 năm 2012. Tác giả Hoàng Thị Quyên 3 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Chương 1 Cực tiểu hợp một hàm lồi và một hàmC 1,1 Chương 1 trình bày các điều kiện tối ưu cấp 2 của Jeyakumar-Yang [13] cho bài toán cực tiểu hóa hợp của một hàm lồi vô hướng, nửa liên tục dưới và một hàm C 1,1 dưới ngôn ngữ đạo hàm suy rộng cấp 2 theo nghĩa Clarke. 1.1 Đạo hàm cấp 2 suy rộng Xét bài toán tối ưu : (P ) min x∈X g(F (x)), trong đó X là không gian Banach, g là hàm lồi nửa liên tục dưới, F là C 1,1 hàm, tức là một hàm khả vi Gâteaux có đạo hàm Lipschitz địa phương. Trong mục này ta đưa ra các định nghĩa và một vài kết quả cơ bản về đạo hàm theo phương cấp hai suy rộng của C 1,1 hàm. Giả sử X là không gian Banach thực với chuẩn || . ||. Cặp chính tắc giữa 4 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn X và không gian đối ngẫu X ∗ được kí hiệu bởi ., .. Bây giờ ta đưa vào đạo hàm theo phương cấp hai suy rộng. Định nghĩa 1.1 Cho f : X → R là một C 1,1 hàm khi đó đạo hàm theo phương cấp hai suy rộng của f tại x theo phương (u, v) thuộc X × X được xác định bởi: f 00 (x, u, v) = lim sup y→x s→0 [∇f(y + su), v − ∇f(y), v] s Hessian suy rộng của f tại x theo phương u được xác định bởi: ∂ 00 f(x)(u) =  x ∗ ∈ X ∗ : f 00 (x, u, v ≥ x ∗ , v∀v ∈ X  . Chú ý rằng ánh xạ (u, v) → f 00 (x, u, v) là hữu hạn và dưới tuyến tính, ∂ 00 f(x)(u) là tập khác rỗng lồi, compac yếu ∗ trong X ∗ và với mỗi x, u, v ∈ X, f 00 (x; u, v) = max  x ∗ , v : x ∗ ∈ ∂ 00 f(x)(u)  . (1.1) Trong [5] đã chỉ ra rằng f 00 (x; u, v) = lim sup y→x s,t→0 [f(y + su + tv) − f(y + su) − f(y + tv) + f(y)] st (1.2) và nếu f khả vi liên tục 2 lần tại x thì Hessian suy rộng ∂ 00 f(x)(u) là tập một điểm với mọi u thuộc X. Định nghĩa 1.2 Cho f : X → R là hàm C 1,1 . Ta nói rằng hàm f là khả vi chặt hai 5 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn lần tại x nếu tồn tại toán tử tuyến tính D 2 f(x) : X → X ∗ sao cho: D 2 f(x)u, v = lim y→x s→0 [∇f(y + su), v − ∇f(y), v] s . (1.3) Mệnh đề sau đây cho phép ta nhận được một đặc trưng của tính khả vi chặt hai lần của một C 1,1 hàm. Mệnh đề 1.1 Cho f : X → R là C 1,1 hàm. Khi đó f là khả vi chặt hai lần tại x nếu và chỉ nếu giới hạn. lim y→x s,t→0 [f(y + su + tv) − f(y + su) − f(y + tv) + f(y)] st (1.4) tồn tại. Chú ý rằng trong trường hợp này, hai giới hạn (1.3) và (1.4) là bằng nhau. Chứng minh Giả sử f là khả vi chặt 2 lần tại x thì từ (1.2) ta có. lim sup y→x s,t→0 [f(y + su + tv) − f(y + su) − f(y + tv) + f(y)] st = lim sup y→x s→0 [∇f(y + su), v − ∇f(y), v] s = lim y→x s→0 [∇f(y + su), v − ∇f(y), v] s . Như vậy từ (1.3) ta có lim sup y→x s,t→0 [f(y + su + tv) − f(y + su) − f(y + tv) + f(y)] st 6 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn = D 2 f(x)u, v = −D 2 f(x)(−u), v = − lim sup y→x s,t→0 [f(y + s(−u) + tv) − f(y + s(−u)) − f(y + tv) + f(y)] st = lim inf y→x s,t→0 [f(y + (−s)u + tv) − f(y + (−s)u) − f(y + tv) + f(y)] (−s)t . Từ đó suy ra giới hạn (1.4) tồn tại. Giả sử rằng (1.4) tồn tại. Khi đó, lim sup y→x s,t→0 [f(y + su + sv) − f(y + su) − f(y + tv) + f(y)] st ≥ lim sup y→x s→0 [∇f(y + su), v − ∇f(y), v] s ≥ lim inf y→x s→0 [∇f(y + su), v − ∇f(y), v] s ≥ lim inf y→x s,t→0 [f(y + su + sv) − f(y + su) − f(y + tv) + f(y)] st . Do sự tồn tại của giới hạn (1.4), ta suy ra giới han (1.3) tồn tại.  Dễ dàng thấy rằng từ định nghĩa 1.2 ta suy ra nếu f 1 và f 2 hai lần khả vi chặt tại x và λ, µ ∈ R thì λf 1 + µf 2 là hai lần khả vi chặt tại x. Một C 1,1 -hàm là khả vi chặt hai lần tại x nếu và chỉ nếu ∂ 00 f(x)(u) là tập một điểm với mỗi u thuộc X. Trong trường hợp đó ∂ 00 f(x)(u) = {D 2 f(x)u} (xem [5]). Như vậy, mọi hàm khả vi liên tục Fréchet hai lần là khả vi chặt hai lần. Mệnh đề 1.2 ([5]) Giả sử f : X → R là một C 1,1 hàm. Khi đó, các ánh xạ x → f 00 (x; u, v) và (x, u) → f 00 (x; u, v) là nửa liên tục trên tại x và (x, u) 7 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn [...]... tương đương: (i) g(F(x)) nhận một cực tiểu địa phương tại z; (ii) L0 (z) = ∅ và ϕηε nhận một cực tiểu địa phương tại z với bất kỳ η > 0, ε > 0; 11 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn (iii) L0 (z) = ∅ và ϕηε nhận một cực tiểu địa phương tại z với η > 0, ε > 0 nào đó Chứng minh Trước hết ta chú ý rằng nếu g(F (x)) chỉ nhận một cực tiểu địa phương tại z thì 0 ∈... Chương 2 Tối ưu đa mục tiêu với các hàm hợp của hàm lồi và Lipschitz địa phương Chương 2 trình bày các điều kiện tối ưu cấp 1 và cấp 2 của YangJeyakumar [15] cho nghiệm hữu hiệu yếu của bài toán đa mục tiêu cực tiểu hợp của một hàm véc tơ lồi và một hàm Lipschitz địa phương bằng phương pháp vô hướng hóa 2.1 Phát biểu bài toán Xét bài toán tối ưu đa mục tiêu với hàm hợp lồi sau đây: (P1 ) V −M in(f (F1... : y ∗ ∈ [−1, 1] = u2 > 0, 1.3 ∀ 0 = u ∈ R Cực tiểu hợp của hàm lồi giá trị thực mở rộng và áp dụng Trong phần này ta chỉ ra các kết quả trong phần (1.2) có thể mở rộng ra đối với bài toán cực tiểu hợp của hàm giá trị thực mở rộng.Để trình bày các điều kiện cần và đủ dưới một lược đồ thống nhất ta hạn chế không gian là hữu hạn chiều Xét bài toán tối ưu hàm hợp lồi giá trị thực mở rộng sau: (P E) min... (x)(u) là tập một điểm với mỗi u thuộc X nếu và chỉ nếu f khả vi Gâteaux hai lần tại x Hơn nữa với mỗi u, v ∈ X , f ♦♦ (x; u, v) ≤ f 00 (x; u, v) và ∂ ♦♦ f (x)(u) ⊂ ∂ 00 f (x)(u) Tuy nhiên, hàm số x→f ♦♦ (x; u, v) nói chung không nửa liên tục trên tại x Hàm số x→f ♦♦ (x; u, v) là nửa liên tục trên tại x nếu và chỉ nếu f 1.2 ♦♦ (x; u, v) = f 00 (x; u, v) Cực tiểu hàm hợp của một hàm lồi và một hàm C 1,1... dưới dạng bài toán hàm hợp lồi (P) với một C 1,1 - hàm F Chúng ta bắt đầu bằng một thiết lập kết quả đối ngẫu địa phương trong không gian Banach khi giả sử hàm F là hàm Lipschitz địa phương chỉ với tính chất khả vi Gâteaux Khi sử dụng kết quả đối ngẫu và tính nửa liên tục trên của đạo hàm theo phương cấp hai suy rộng ta có thể dẫn các điều kiện cần và đủ cấp hai cho bài toán (P) với hàm hợp lồi C 1,1 ... xét bài toán cực tiểu hàm hợp lồi vô hạn chiều sau đây: (P ) min f (x) := g(F (x)), x∈X trong đó X là không gian Banach thực, g : Rm → R lồi, nửa liên tục dưới và F : X → Rm là C 1,1 Chú ý rằng các đòi hỏi thông thường của tính 9 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn khả vi Fréchet hai lần được quy về C 1,1 Chẳng hạn, hàm phạt cho bài toán cực tiểu C 1,1 được... sin( ))dt, t F (x) = x2 + x ∈ R 0 Khi đó, F là C 1,1 (xem [17]), g là lồi và a = 0 là một cực tiểu địa phương và cũng là một cực tiểu địa phương chặt cấp 2 của f = g ◦ F Ta có L(x, y ∗ ) = y ∗ , F (x) − g ∗ (y ∗ )   |x| 1  (t2 +t2 sin( ))dt − |y ∗ |, t  = y ∗ x2 + x ∈ R 0 Khi đó, K(0) = R, L0 (a) = [−1, 1] 18 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Ta có: L00... toán hàm hợp có ràng buộc bất đẳng thức thì điều kiện chính quy cơ bản là tương đương với điều kiện chính quy Slater type đã sử dụng trong [9] Xét bài toán: min g0 (F0 (x)), x ∈ C, gi (Fi (x)) ≤ 0, i = 1, m, 20 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn trong đó C là một tập lồi đóng của Rn , gi , i = 0, m là những hàm Lipschitz địa phương, và Fi , i = 0, m là các hàm. .. (i) Nếu a là cực tiểu địa phương của (PE) và tại đó điều kiện chính quy cơ bản đúng thì max L00 (a, y ∗ ; u, u) : y ∗ ∈ L0 (a) ≥ 0, ∀u ∈ K(a); (1.13) (ii) Nếu L0 (a) = ∅ và nếu max −L00 (a, y ∗ ; u, −u) : y ∗ ∈ L0 (a) > 0, ∀u ∈ D(a), thì a là một cực tiểu địa phương chặt cấp hai của (P) Chứng minh (i) Từ mệnh đề 4.1 [4] với α > 0 đủ nhỏ, ta có L0 (a) = L0 (a, α), K(a) ⊂ K(a, α), 22 Số hóa bởi Trung... lý 1.1 Với bài toán (P) ta giả sử rằng g là một hàm lồi nửa liên tục dưới và f là C 1,1 Khi đó, các kết quả sau đây đúng (i) Giả sử a thuộc X Nếu a là cực tiểu địa phương của(P) thì max L00 (a, y ∗ ; u, u) : y ∗ ∈ L0 (a) ≥ 0, ∀ u ∈ K(a); (1.8) (ii) Nếu a ∈ X = Rn và L0 (a) = ∅, và nếu max −L00 (a, y ∗ ; u, −u) : y ∗ ∈ L0 (a) ≥ 0, ∀ u ∈ D(a), thì a là cực tiểu địa phương chặt cấp 2 của (P), tức là ∃ . 4 1 Cực tiểu hợp một hàm lồi và một hàmC 1,1 4 1.1 Đạo hàm cấp 2 suy rộng . . . . . . . . . . . . . . . . . . . 4 1.2 Cực tiểu hàm hợp của một hàm lồi và một hàm C 1,1 . . . . 9 1.3 Cực tiểu hợp. của bài toán đa mục tiêu cực tiểu hóa hợp của một hàm véc tơ lồi và một hàm Lipschitz địa phương bằng phương pháp vô hướng hóa. Đề tài "Về cực tiểu hóa một hàm hợp& quot; là đề tài có tính. bài toán cực tiểu hóa một hàm lồi nửa liên tục dưới và C 1,1 -hàm, và bài toán cực 1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn tiểu hóa hợp của một hàm véc