Xemtailieu Tải về Phương pháp xấp xỉ trơn cho bài toán tối ưu không trơn
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THỊ TRANG PHƯƠNG PHÁP XẤP XỈ TRƠN CHO BÀI TOÁN TỐI ƯU KHÔNG TRƠN 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 http://www.lrc-tnu.edu.vn ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THỊ TRANG PHƯƠNG PHÁP XẤP XỈ TRƠN CHO BÀI TOÁN TỐI ƯU KHÔNG TRƠN 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 http://www.lrc-tnu.edu.vn i Mục lục Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i Mở đầu 1 Nội dung 4 1 XẤP XỈ TỐI ƯU KHÔNG TRƠN BẰNG DÃY CÁC BÀI TOÁN TỐI ƯU TRƠN 4 1.1 Xấp xỉ bài toán không trơn . . . . . . . . . . . . . . . . . . 4 1.2 Các kiến thức bổ trợ . . . . . . . . . . . . . . . . . . . . . 8 1.3 Điều kiện cần Lagrange không trơn 1.4 Đối ngẫu Wolfe suy rộng . . . . . . . . . . . . . . . . . . . 13 1.5 Bài toán quy hoạch liên tục không trơn . . . . . . . . . . . 15 1.6 Bài toán điều khiển tối ưu không trơn . . . . . . . . . . . . 22 . . . . . . . . . . . . . 10 2 PHƯƠNG PHÁP XẤP XỈ TRƠN CHO BÀI TOÁN MINIMAX VECTƠ KHÔNG TRƠN 2.1 28 Các kiến thức bổ trợ . . . . . . . . . . . . . . . . . . . . . 28 2.1.1 Bài toán minimax đã làm trơn . . . . . . . . . . . . 29 2.1.2 Làm trơn hàm lồi bất biến địa phương . . . . . . . . 32 2.2 Điều kiện cần cho minimax 2.3 Điều kiện đủ cho minimax . . . . . . . . . . . . . . . . . . 40 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên . . . . . . . . . . . . . . . . . 35 http://www.lrc-tnu.edu.vn i Kết luận 43 Tài liệu tham khảo 45 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 1 Mở đầu Lí thuyết các bài toán tối ưu không trơn là một bộ phận quan trọng của lí thuyết các bài toán cực trị và có nhiều ứng dụng trong kinh tế, kĩ thuật. Lí thuyết gradient và jacobian suy rộng Clarke ra đời (xem [4]) đã trở thành công cụ hữu hiệu để xử lí các bài toán tối ưu không trơn với các hàm Lipschitz địa phương. Định lý Rademacher chỉ ra rằng một hàm Lipschitz xác định trong không gian hữu hạn chiều thì khả vi hầu khắp nơi trong miền xác định của nó. Sử dụng tích chất này và kĩ thuật của lí thuyết hàm suy rộng, Craven [5] đã đưa ra phương pháp xấp xỉ trơn cho bài toán tối ưu với các hàm Lipschitz địa phương trong không gian hữu hạn chiều. Bằng phương pháp xấp xỉ trơn, Craven [5] đã thiết lập cho các điều kiện cần tối ưu cho bài toán tối ưu không trơn với ràng buộc nón và ràng buộc đẳng thức, bài toán quy hoạch liên tục không trơn và bài toán điều khiển tối ưu không trơn và một vài kết quả về đối ngẫu. Bằng phương pháp xấp xỉ trơn trong [5], B.D.Craven và D.V.Lưu [9] đã chứng minh các điều kiện Lagrange cần và đủ cho bài toán minimax vectơ không trơn với các ràng buộc nón. Luận văn đã trình bày các điều kiện tối ưu cho bài toán tối ưu với các hàm Lipschitz địa phương, có ràng buộc nón và ràng buộc đẳng thức, bài toán quy hoạch liên tục không trơn, bài toán điều khiển tối ưu không trơn 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 2 và bài toán minimax vectơ không trơn được thiết lập bằng phương pháp xấp xỉ trơn của B.D.Craven. 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 điều kiện cần tối ưu của B.D.Craven [5] cho bài toán tối ưu với các hàm Lipschitz địa phương, có ràng buộc đẳng thức và ràng buộc nón, bài toán quy hoạch liên tục không trơn và bài toán điều khiển tối ưu không trơn với thời gian cố định và ràng buộc trạng thái được thiết lập bằng phương pháp xấp xỉ trơn của B.D.Craven. Một số kết quả đối ngẫu cũng được trình bày trong chương này. Chương 2 trình bày các điều kiện Lagrange của B.D.Craven và D.V.Lưu [9] cho bài toán minimax vectơ với các hàm Lipschitz địa phương và ràng buộc nón. Nhân dịp này tôi xin bày tỏ lòng biết ơn sâu sắc tới PGS.TS Đỗ Văn Lưu, người đã tận tình hướng dẫn, giúp đỡ tôi hoàn thành bản luận văn này. Tôi xin chân thành cảm ơn Khoa Toán- Tin, Phòng đào tạo sau đại học trường Đại học Khoa học - Đại học Thái Nguyên cùng các thầy cô giáo đã tham gia giảng dạy khóa học. Tôi xin chân thành cảm ơn trường Hữu Nghị 80, Tổ Toán trường Hữu Nghị 80 đã tạo điều kiện cho tôi hoàn thành khóa học này. 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, trình độ và điều kiện 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 3 nghiên cứu còn hạn chế 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ô và các bạn đồng nghiệp để luận văn được hoàn thiện hơn. Thái Nguyên, tháng 09 năm 2011. Tác giả Nguyễn Thị Trang 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 4 Chương 1 XẤP XỈ TỐI ƯU KHÔNG TRƠN BẰNG DÃY CÁC BÀI TOÁN TỐI ƯU TRƠN Chương 1 trình bày các điều kiện cần tối ưu cho bài toán tối ưu với các hàm Lipschitz địa phương bao gồm các ràng buộc nón và ràng buộc đẳng thức, bài toán quy hoạch liên tục không trơn và bài toán điều khiển tối ưu không trơn với thời gian cố định và có ràng buộc trạng thái được thiết lập bằng phương pháp xấp xỉ trơn. Các kết quả trong chương này là của B.D.Craven [5]. 1.1 Xấp xỉ bài toán không trơn Xét bài toán cực tiểu có ràng buộc: Minimize f (x), x∈X0 − g(x) ∈ S, (1.1) h(x) = 0, trong đó X0 là một tập con của Rn , f : X0 → R, g : X0 → Rm , h : 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 5 X0 → Rr là các hàm Lipschitz địa phương, không nhất thiết khả vi Fréchet, S là một nón lồi đóng trong Rm có phần trong khác rỗng. Chú ý rằng tập chấp nhận được: Γ := {x ∈ X0 | − g(x) ∈ S, h(x) = 0} của bài toán (1.1) là đóng, và X0 là một lân cận mở của Γ. Như vậy f , g được xác định lân cận của tập chấp nhận được Γ. Gọi kx là hằng số Lipschitz của g tại x. Giả sử bài toán (1.1) có cực tiểu địa phương tại x ∈ Γ, với f , g không m cùng khả vi tại x. Nếu S là orthant không âm Rm + trong R thì ràng buộc (1.1) có dạng gj (x) ≤ 0 (j = 1, 2, ..., m). Khi đó, lí thuyết gradient suy rộng Clarke có thể áp dụng để nhận được điều kiện cần F.John hoặc Kuhn- Tucker. Ta sẽ xấp xỉ bài toán (1.1) bằng các bài toán trơn, và áp dụng lý thuyết Lagrangian thông thường. Khi đó ta sẽ nhận được các điều kiện tối ưu cho bài toán không trơn (1.1) với các ràng buộc nón và ràng buộc đẳng thức. Phương pháp xấp xỉ ở đây dựa trên kĩ thuật trong lý thuyết hàm suy rộng. Với tham số η dương đủ nhỏ, ta đặt Z f (x : η) = ZX g(x : η) = ZX h(x : η) = f (x − s)ϕ(s)ds; g(x − s)ϕ(s)ds; (1.2) h(x − s)ϕ(s)ds; X trong đó X = Rn , f, g, h bằng 0 ở ngoài X0 , ds là độ đo Lebesgue trong Rn , ϕ(s) = Φ(η −1 ||s||)η −1 , trong đó ||.|| là chuẩn Euclide và Φ : R → R 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 6 là một hàm có đạo hàm các cấp và thỏa mãn 0 5 Φ(.), Φ(.) = 0 ở ngoài R (-1,1) sao cho X ϕ(s)ds = 1 (xem [5]). Kí hiệu f 0 (x : η), g 0 (x : η), h0 (x : η) là đạo hàm của f (. : η), g(. : η), h(. : η). Theo Định lý Rademacher f, g, h khả vi Fréchet trừ ra tập N có độ đo Lebesgue bằng 0. Bởi vì tập này không ảnh hưởng đến việc lấy tích phân, với mọi η đủ nhỏ, ||g 0 (x − s)ϕ(s)|| 5 kx ϕ(s) và Z 0 g (x : η) = g 0 (x − s)ϕ(s)ds ∈ C(η) := co{g 0 (s)|||s − x|| < η, s 6∈ N }, X (1.3) trong đó co kí hiệu bao lồi, và co kí hiệu bao lồi đóng. Chú ý rằng 0 < η 0 < η kéo theo C(η 0 ) ⊂ C(η). Với η đủ nhỏ, C(η) nằm trong hình cầu đóng có bán kính kx trong không gian Rm×n các m × n- ma trận. Vì thế C(η) là compact, và \ e ∂g(x) := C(η) 6= ∅. (1.4) η>0 ˜ Vì vậy ∂g(x) là bao lồi đóng các điểm giới hạn của các dãy {g 0 (xk )}, với {xk } → x, xk là điểm khả vi của g . Dưới vi phân suy rộng Clarke ∂g(x) ˜ bằng bao lồi của các điểm giới hạn này. Tập đó đóng vì vậy, ∂g(x) = ∂g(x). ˜ (x) = ∂f (x) và ∂h(x) ˜ Tương tự ta có ∂f = ∂h(x). Từ (1.3) và (1.4), nếu λ ∈ Rm thì ˜ ˜ ˜ ∂(λg)(x) = λ∂g(x) := {λω|ω ∈ ∂g(x)}. (1.5) Nhắc lại ma trận M cấp m × n với m < n, có hạng đầy nếu M chứa ma trận con M0 cấp m × m không suy biến. Kí hiệu %(M ) là chuẩn ma trận ||M0−1 ||, trong đó M0 là m × m- ma trận con không suy biến của M , ˜ nếu M có hạng đầy. Nếu M không có hạng đầy ta đặt %(M ) = ∞. ∂h(x) ˜ ˜ có hạng đầy nếu %(∂h(x)) := {%(M )|M ∈ ∂h(x)} là bị chặn. 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ải về bản full