ĐẠ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 TỐN TỐI ƯU KHƠNG TRƠN LUẬN VĂN THẠC SĨ TỐN HỌC Thái Nguyên - Năm 2011 Số hóa 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 Chun ngành: TỐ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 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 Nội dung XẤP XỈ TỐI ƯU KHƠNG TRƠN BẰNG DÃY CÁC BÀI TỐN TỐI ƯU TRƠN 1.1 Xấp xỉ tốn khơng trơn 1.2 Các kiến thức bổ trợ 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 tốn quy hoạch liên tục khơng trơn 15 1.6 Bài tốn điều khiển tối ưu khơng trơn 22 10 PHƯƠNG PHÁP XẤP XỈ TRƠN CHO BÀI TỐ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 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 Trung tâm Học liệu – Đại học Thái Ngun http://www.lrc-tnu.edu.vn Mở đầu Lí thuyết tốn tối ưu không trơn phận quan trọng lí thuyết tốn cực trị có nhiều ứng dụng kinh tế, kĩ thuật Lí thuyết gradient jacobian suy rộng Clarke đời (xem [4]) trở thành cơng cụ hữu hiệu để xử lí tốn tối ưu khơng trơn với hàm Lipschitz địa phương Định lý Rademacher hàm Lipschitz xác định không gian hữu hạn chiều khả vi hầu khắp nơi miền xác định Sử dụng tích chất kĩ thuật lí thuyết hàm suy rộng, Craven [5] đưa phương pháp xấp xỉ trơn cho toán tối ưu với hàm Lipschitz địa phương 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 điều kiện cần tối ưu cho tốn tối ưu khơng trơn với ràng buộc nón ràng buộc đẳng thức, tốn quy hoạch liên tục khơng trơn tốn điều khiển tối ưu không trơn vài kết đối ngẫu Bằng phương pháp xấp xỉ trơn [5], B.D.Craven D.V.Lưu [9] chứng minh điều kiện Lagrange cần đủ cho tốn minimax vectơ khơng trơn với ràng buộc nón Luận văn trình bày điều kiện tối ưu cho toán tối ưu với hàm Lipschitz địa phương, có ràng buộc nón ràng buộc đẳng thức, tốn quy hoạch liên tục khơng trơn, tốn điều khiển tối ưu khơng trơn Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn toán minimax vectơ không trơn thiết lập phương pháp xấp xỉ trơn B.D.Craven Luận văn bao gồm phần mở đầu, hai chương, kết luận danh mục tài liệu tham khảo Chương trình bày điều kiện cần tối ưu B.D.Craven [5] cho toán tối ưu với hàm Lipschitz địa phương, có ràng buộc đẳng thức ràng buộc nón, tốn quy hoạch liên tục khơng trơn tốn điều khiển tối ưu không trơn với thời gian cố định ràng buộc trạng thái thiết lập phương pháp xấp xỉ trơn B.D.Craven Một số kết đối ngẫu trình bày chương Chương trình bày điều kiện Lagrange B.D.Craven D.V.Lưu [9] cho toán minimax vectơ với hàm Lipschitz địa phương ràng buộc nón Nhân dịp 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 hồn thành luận văn Tơi xin chân thành cảm ơn Khoa Tố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 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 hồn thành khóa học Xin chân thành cảm ơn gia đình, bạn bè đồng nghiệp thành viên lớp cao học tốn K3b ln quan tâm, động viên, giúp đỡ tơi suốt thời gian học tập q trình làm luận văn Tuy thân có nhiều cố gắng, song thời gian, trình độ điều kiện Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn nghiên cứu hạn chế nên luận văn khó tránh khỏi thiếu sót Rất mong đóng góp ý kiến thầy bạn đồng nghiệp để luận văn hoàn thiện Thái Nguyên, tháng 09 năm 2011 Tác giả Nguyễn Thị Trang Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Chương XẤP XỈ TỐI ƯU KHƠNG TRƠN BẰNG DÃY CÁC BÀI TỐN TỐI ƯU TRƠN Chương trình bày điều kiện cần tối ưu cho toán tối ưu với hàm Lipschitz địa phương bao gồm ràng buộc nón ràng buộc đẳng thức, tốn quy hoạch liên tục khơng trơn tốn điều khiển tối ưu khơng trơn với thời gian cố định có ràng buộc trạng thái thiết lập phương pháp xấp xỉ trơn Các kết chương B.D.Craven [5] 1.1 Xấp xỉ tốn khơng trơn Xét tốn cực tiểu có ràng buộc: Minimize f (x), x∈X0 − g(x) ∈ S, (1.1) h(x) = 0, X0 tập Rn , f : X0 → R, g : X0 → Rm , h : Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn X0 → Rr hàm Lipschitz địa phương, không thiết khả vi Fréchet, S nón lồi đóng Rm có phần khác rỗng Chú ý tập chấp nhận được: Γ := {x ∈ X0 | − g(x) ∈ S, h(x) = 0} tốn (1.1) đóng, X0 lân cận mở Γ Như f , g xác định lân cận tập chấp nhận Γ Gọi kx số Lipschitz g x Giả sử tốn (1.1) có cực tiểu địa phương x ∈ Γ, với f , g không m khả vi x Nếu S orthant khơng âm Rm + R ràng buộc (1.1) có dạng gj (x) ≤ (j = 1, 2, , m) Khi đó, lí thuyết gradient suy rộng Clarke áp dụng để nhận điều kiện cần F.John Kuhn- Tucker Ta xấp xỉ toán (1.1) toán trơn, áp dụng lý thuyết Lagrangian thơng thường Khi ta nhận điều kiện tối ưu cho toán khơng trơn (1.1) với ràng buộc nón ràng buộc đẳng thức Phương pháp xấp xỉ dựa kĩ thuật lý thuyết hàm suy rộng Với tham số η dương đủ nhỏ, ta đặt f (x − s)ϕ(s)ds; f (x : η) = X g(x − s)ϕ(s)ds; g(x : η) = (1.2) X h(x − s)ϕ(s)ds; h(x : η) = X X = Rn , f, g, h X0 , ds độ đo Lebesgue Rn , ϕ(s) = Φ(η −1 ||s||)η −1 , ||.|| chuẩn Euclide Φ : R → R Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn hàm có đạo hàm cấp thỏa mãn (-1,1) cho X Φ(.), Φ(.) = ngồi ϕ(s)ds = (xem [5]) Kí hiệu f (x : η), g (x : η), h (x : η) đạo hàm f ( : η), g( : η), h( : η) Theo Định lý Rademacher f, g, h khả vi Fréchet trừ tập N có độ đo Lebesgue Bởi tập khơng ảnh hưởng đến việc lấy tích phân, với η đủ nhỏ, ||g (x − s)ϕ(s)|| kx ϕ(s) g (x − s)ϕ(s)ds ∈ C(η) := co{g (s)|||s − x|| < η, s ∈ N }, g (x : η) = X (1.3) co kí hiệu bao lồi, co kí hiệu bao lồi đóng Chú ý < η < η kéo theo C(η ) ⊂ C(η) Với η đủ nhỏ, C(η) nằm hình cầu đóng có bán kính kx khơng gian Rm×n m × n- ma trận Vì C(η) compact, C(η) = ∅ ∂g(x) := (1.4) η>0 ˜ Vì ∂g(x) bao lồi đóng điểm giới hạn dãy {g (xk )}, với {xk } → x, xk điểm khả vi g Dưới vi phân suy rộng Clarke ∂g(x) ˜ bao lồi điểm giới hạn Tập đóng vậy, ∂g(x) = ∂g(x) ˜ (x) = ∂f (x) ∂h(x) ˜ Tương tự ta có ∂f = ∂h(x) Từ (1.3) (1.4), λ ∈ Rm ˜ ˜ ˜ ∂(λ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 M chứa ma trận M0 cấp m × m khơng suy biến Kí hiệu (M ) chuẩn ma trận ||M0−1 ||, M0 m × m- ma trận khơng suy biến M , ˜ M có hạng đầy Nếu M khơng có hạng đầy ta đặt (M ) = ∞ ∂h(x) ˜ ˜ có hạng đầy (∂h(x)) := { (M )|M ∈ ∂h(x)} bị chặn Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 32 Nếu = τ ∈ Q∗ τ σ > Bây xét toán sau: (OP (α, β)) W M INx m(x; α, β), − g(x : α) ∈ T ; (OP (α, β)τ ) M INx τ m(x; α, β), − g(x : α) ∈ T Mệnh đề 2.2 Giả sử g Lipschitz địa phương; x ¯ cực tiểu địa phương toán (OP (0,0):τ ), giả thiết Mệnh đề 2.1 Khi đó, m(x; α, β) đạt cực tiểu địa phương yếu, với ràng buộc −g(x : α) ∈ T , điểm x = x(α, β), x(α, β) → x¯ α, β → Chứng minh Theo Mệnh đề (2.1), toán (IP (α, β )) đạt cực đại địa phương yếu y(x; α, β) y(.; , ) Lipschitz (¯ x; 0, 0) Từ (2.2) tất giả thiết [6, Bổ đề 3] thỏa mãn cho toán (OP (α, β); τ ) Vì vậy, τ x( : α, β) đạt cực đại địa phương với ràng buộc −g(x : α) ∈ T , điểm x(α, β), x(α, β) → x¯ α, β → Khi đó, x(α, β) cực tiểu địa phương yếu toán (OP (α, β )) 2.1.2 Làm trơn hàm lồi bất biến địa phương Hàm khả vi F : Rn → Rr lồi bất biến p ∈ Rn theo nón thứ tự Q ⊂ Rn với tồn hàm η(x, p) cho (∀x)F (x) − F (p) − F (p)η(x, p) ∈ Q Ta giả sử rằng, với p cố định , η(x, p) = x − p + o(||x − p||) Vì thế, η(., p) liên tục, η(p, p) = Hàm Lipschitz F : Rn → Rr Q- lồi Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 33 bất biến p (∀x)(∀ξ ∈ F (p))F (x) − F (p) − ξη(x, p) ∈ Q, ∂F (p) Jacobian suy rộng Clarke F p Theo định lý Rademacher F khả vi trừ tập N0 độ đo Lebesgue Định nghĩa 2.1 Hàm Lipschitz F : R → Rr Q- quy lồi bất biến gần p, tồn hàm liên tục η(., ) cho với u lân cận p u ∈ N0 , (∀x)F (x) − F (u) − F (u)η(x − u + p, p) ∈ Q Rõ ràng Q- quy lồi bất biến gần p kéo theo Q- bất biến p Mệnh đề 2.3 Giả sử F (.) Q- quy lồi bất biến gần p Khi đó, hàm trơn sau Q− lồi bất biến p: F (x − s)φ(s|α)ds, F (x, α) := Rn φ chọn phần 2.1.1, với hàm scale F (.) α đủ nhỏ Nhận xét 2.1 Kết luận không giả thiết "Q- lồi bất biến gần p" thay lồi bất biến điểm lân cận p, tổng hàm lồi bất biến không thiết lồi bất biến hàm scale khác Đặc biệt, với C - hàm F , tính lồi bất biến p tăng cường thành (∀x)F (x) − F (p) − F (p)η(x, p) − σ||x − p||2 ∈ Q, Số hóa Trung tâm Học liệu – Đại học Thái Ngun http://www.lrc-tnu.edu.vn 34 σ ∈ Q F - bất biến gần p Khi đó, (∀x)F (x) − F (p) − F (p)η(x, p) ∈ intQ, với δ đủ nhỏ, (∀x)(∀u, ||u − p|| < δ) F (x) − F (u) − F (u)η(x − u + p, p) ∈ Q Với hàm F lớp C ∞ , để đơn giản lấy p = F (p) = xét F (z) = Az + z T B.z; T η(z, 0) = z + z D.z Ở B tập ma trận Hessian thành phần Bk F , cách tương tự cho D Khi đó, theo định nghĩa tính lồi bất biến gần đòi hỏi ma trận B − (A − uT B.)D bán xác định dương, ||u − || đủ nhỏ, AD biểu diễn ma trận s Ask Dk Vì ma trận B − AD phải xác định dương, kéo theo F trở thành lồi bất biến gần Chứng minh Mệnh đề 2.3 Sử dụng tính khả vi F ( : α) tính chất Lipschitz F (.) ta có F (x − s)φ(s|α)ds, F (x, α) := Rn F (x − s) khơng xác định tập có độ đo khơng Vì thế, với {uj } → p với uj ∈ N0 , φ(.|α) ≥ ta có F (uj + y : α) − F (uj : α) − F (uj : α)η(p + y, p) [F (uj + y − s) − F (uj − s) − F (uj − s)η(p + y, p)]φ(s|α)ds = Rn với [ ] ∈ Q với hầu hết s, với uj uj − s lân cận p Do đó, F (uj + y : α) − F (uj : α) − F (uj : α)η(p + y, p) ∈ Q Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 35 Vì vậy, F (p + y : α) − F (p : α) − F (p : α)η(p + y, p) ∈ Q Nhận xét Giả sử F : R → Rr (ở r < n) lồi bất biến điểm hình cầu B tâm p, theo nón thứ tự Q ⊂ Rr Nếu F khả vi u ∈ B|{p} F (u + z : α) − F (u : α) = [F (u + z − s) − F (u − s)]φ(s|α)ds F (u − s)ω(z, u − s)φ(s|α)ds = F (u|α)θ(z, u) (ở ω(z, u − s) := η(z + u − s, s)), tồn θ(z, u) thỏa mãn phương trình tuyến tính: Mθ(z, u) ≡ F (u−s)φ(s|α)ds]θ(z, u) = F (u−s)ω(z, u)−φ(s|α)ds Xét giả thiết sau: với δ > đủ nhỏ, tồn s, với ||s|| < δ cho F (u − s) có hạng đầy Điều kéo theo, tồn hàm φ(.) ≥ với giá nằm hình cầu bán kính δ , cho M có hạng đầy Vì vậy, θ(z, u) tồn tại, θ(z, p) giới hạn Vì vậy, F ( : α) lồi bất biến Nếu f khả vi p, p điểm Karush- Kuhn- Tucker làm cực tiểu hàm F1 (.) cho Fj (.) ≤ 0(j = 2, 3, , r), F (p) khơng có hạng đầy, F (p − s) có hạng đầy, với ||s|| > đủ nhỏ 2.2 Điều kiện cần cho minimax Giả sử toán (WMM1): (IPx ) : W M AXy f (x, y) cho − h(x) ∈ S := Rp+ Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn (2.4) 36 đạt cực đại địa phương (không nhất) y = y(x), với y(¯ x) = y¯ ràng buộc (IPx¯ ) tích cực y¯ Theo [10], ta xây dựng toán (M Px¯ ) cách thêm p − k ràng buộc vào (IPx¯ ): φ(j) (y−¯ y ) := aTj (y−¯ y )+ (y−¯ y )T Aj (y−¯ y ) ≤ (j = 1, 2, , p−k) (2.5) Ma trận Aj chọn (xem [10]) cho φ(j) thỏa mãn tính chất lồi bất biến Khi đó, y¯ cực đại yếu (M Px¯ ) Tương tự, hàm: ψ (j) (y − y¯) := bTj (y − y¯) + (y − y¯)T Bj (y − y¯) (j = 1, 2, , s − l) chọn Định lý 2.2, với Bj chọn để thỏa mãn tính chất lồi bất biến Chú ý φ(j) (0) = ψ (j) (0) = Với giả thiết Mệnh đề 2.1, toán trơn (IP (α, β)) đạt cực đại địa phương yếu y = y(x; α.β), y(.; , ) thỏa mãn điều kiện Lipschitz Ta xét dạng trơn toán (M Px ): W M AXy f (x, y : α, β), (M IP (α, β)) : (2.6) − h(j) (y : β ≤ 0) (i = 1, 2, , p) φ(j) (y − y(x; α, β)) ≤ (j = 1, 2, , p − k) Khi đó, y(x; α, β) cực đại địa phương yếu (M IP (α, β)) Với điều kiện quy điều kiện Karush- Kuhn- Tucker yếu [5, định lí 1] đúng: τ (x : α, β)fy (x, y(x : α, β) : α, β) (WKT) (j) = µj (x; α, β)aTj ; λj (x : α, β)hj (y(x; α, β) : β) + j j λi (x; α, β)h(i) (y(x; α, β) : β) = 0, với nhân tử Lagrangian không âm τ (x; α, β), λj (x; α, β), µj (x; α, β) Lấy tổng j ràng buộc tích cực ( h(i) (¯ y ) = 0), Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn j với 37 j = 1, , k − p Định lí 2.1 Giả sử (¯ x, y¯) minimax địa phương yếu toán (WMM1) Giả sử rằng: (i) Giả thiết Mệnh đề 2.1 2.2 đúng; (ii) Với ξi ∈ ∂h(i) (¯ y ) mà h(i) (¯ y ) = 0, tập gradient ξi với gradient aTj (j = 1, , p − k) ràng buộc thêm vào, tập độc lập tuyến tính; (iii) Hàm vectơ H(.) bao gồm −f (x, ), h(i) (.) mà h(i) (¯ y ) = 0, φ(i) (.)(j = 1, 2, , k − p), Q × Rp - lồi bất biến gần điểm y lân cận y¯, ||x − x¯|| đủ nhỏ; (iv) Các nhân tử Lagrangian (WKT) liên tục (¯ x, 0, 0); (v) Các nhân tử Lagrangian (OP (α, β)) liên tục (0, 0); (vi) (∀η ∈ ∂g(¯ x))0 ∈ int[g(Cx) + η(Rn ) + T ] Khi đó, với nón K ⊃ Q với δ > đó, (∀x, −g(x) ∈ T ), ||x − x¯|| < δ)(∃∧(x) ∈ L(Rp+ , K)), M (x) ∈ L(Rp−k x, y¯), η ∈ ∂g(¯ x), x) , Q), ξ ∈ ∂x f (¯ + , K), π ∈ L(T−g(¯ ∈ ∂y [f (x, y(x)) − ∧h(y(x))] − M (x)a; ∧(x)h(y(x)) = 0; ran[ξ + π η] ⊂ U Chứng minh Từ (iii) Mệnh đề 2.3, hàm vectơ H(.) bao gồm hàm mục tiêu −f (x, : α, β), h(i) (.; β) mà h(i) (¯ y ) = 0, φ(i) (.) (j = 1, 2, , k − p) Q × Rp+ - lồi bất biến y lân cận y¯, ||x − x ¯|| đủ Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 38 nhỏ Từ Mệnh đề 2.1, toán (IP (α, β)) đạt cực đại địa phương yếu y = y(x; α, β) α β ||x − x ¯|| đủ nhỏ Từ (ii), điều kiện ổn định Robinson (xem [14] [16]) cho (IP Cx ) Bởi điều kiện địi hỏi thuộc phần tập bao gồm gradients, vi phân suy rộng Clarke mà nửa liên tục cho nên, điều kiện ổn định mở rộng cho (M IP (α, β)) với ||x − x ¯|| đủ nhỏ Khi đó, ta áp dụng [10, Mệnh đề 1] cho (M IP (α, β)) mà địi hỏi giả thiết tính lồi bất biến (iii), tồn nón K ⊃ Q cho điều kiện Karush- Kuhn- Tucker mạnh đúng: fy (x, y(x; α, β) : α, β) − ∧(x; α, β)hy (y(x; α, β) : β) − M (x; α, β)α = 0; (2.7) ∧(x; α, β)h(y(x; α, β) : β) = 0, với nhân tử Lagrangian ∧ (x; α, β) ∈ L(Rp+ , K) M (x; α, β) ∈ L(Rp−k + , K) Theo Mệnh đề 2.2, hàm m(., α, β) đạt cực tiểu địa phương yếu với ràng buộc −g(.; α) ∈ T x(α, β), x(α, β) → x ¯ α, β → Từ (vi), hàm trơn g thỏa mãn điều kiện Robison: ∈ int[g(¯ x; α) + gx (¯ x; α)(Rn ) + T ] α đủ nhỏ Từ [6, Định lý 1] ta suy tồn nhân tử Lagrangian π(α, β) ∈ L(Rs , Rr ) thỏa mãn ran[mx (¯ x; α, β) + π(α, β)gx (¯ x; α)] ⊂ U ; π(α, β)(T−g(¯x;α) ) ⊂ Q Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 39 Từ [11, Mệnh đề 2] ta suy mx (¯ x; α, β) = fx (¯ x, y¯ : α, β) Do đó, ran[fx (¯ x, y¯ : α, β) + π(α, β)gx (¯ x; α) ⊂ U (2.8) Cho α, β → ta có ∧ (x; α, β) → ∧(x) M (x; α, β) → M (x) (các giới hạn tồn (iv)), π(α, β) → π ¯ (do giả thiết (v)) Vế trái (2.7) tiến đến phần tử ∂y (f −∧(x)h−M (x)a)(x, y(x)), fx (¯ x, y¯; α, β) gx (¯ x, α) tến đến phần tử ∂x f (¯ x, y¯) ∂g(¯ x) Vì kết đạt suy lấy giới hạn từ (2.7) (2.8) Nhận xét 2.3 Nếu giả thiết (vi) thay giả thiết: với ηj ∈ ∂gi (¯ x), tập ηi ràng buộc tích cực với bTj (j = 1, 2, , s − l) độc lập tuyến tính, kết luận đúng; bao hàm thức ran[ξ¯+ π ¯ η¯] ⊂ U thay bởi: ¯ ∈ ∂x [f (¯ x, y¯) + π ¯ g(¯ x)] + Ξb, π ¯ g(¯ x) = 0, ¯ ∈ L(Rs−l , H), H nón thỏa mãn π ¯ ∈ L(Rs+ , H), Ξ Q ⊂ K ⊂ H Định lý 2.1 giả sử nhân tử Lagrangian hàm liên tục tham số Xét điều kiện Karush- Kuhn- Tucker mạnh: fy (x, y(x; α, β) : α, β) = (x; α, β)ky (y(x; α, β) : α, β), bao gồm ∧ M , ky bao gồm hy a Trong trường hợp p × m ma trận ky có hạng đầy p ≤ n, phương trình tuyến tính giải được, với hàm liên tục α, β Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 40 2.3 Điều kiện đủ cho minimax Nhắc lại [13] hàm đa trị Φ : Rn → Rm gọi giả Lipschitz gần (¯ x, y¯) ∈ grΦ (đồ thị Φ) với môđun c > tồn lân cận U x¯ V y¯ cho (∀x, x ∈ U )Φ(x ) ∩ V ⊂ Φ(x) + c||x − x ||B1 (0), B1 (0) hình cầu đơn vị đóng Kí hiệu jacobian suy rộng Clarke theo x y ∂x ∂y N(v, Ω) nón pháp tuyến Clarke tập Ω điểm v ∈ Ω Định nghĩa hàm Lagrangian: L(x, y; ∧, M, Π, Ξ) := f (x, y)−∧h(y)−M φ(y −Cy)+Πg(x)+Ξψ(x− x¯) Hàm F (.) đạt cực tiểu địa phương mạnh x ¯ theo nón H (xem [4]) F (x) − F (¯ x) ∈ H với x chấp nhận gần x¯ Định lí 2.2 Giả sử (¯ x, y¯) điểm chấp nhận toán (WMM1), k ≤ p ràng buộc từ −h(.) ∈ S tích cực y¯, l ≤ s ràng buộc từ −g(.) ∈ T tích cực x¯ Giả sử (a) Với nón lồi đóng K H đó, Q ⊂ K ⊂ H , s−l (∃∧ ∈ L(S−h(¯y) , K), M ∈ L(Rp−k x) , H), Ξ ∈ L(R+ , H)) + , K), Π ∈ L(T−g(¯ (0, 0) ∈ ∂x L(¯ x, y¯; ∧, M , Π, Ξ) × ∂y L(¯ x, y¯; ∧, M , Π, Ξ); (ở ∂x L không phụ thuộc vào (∧, M ), ∂y L không phụ thuộc vào (Π, Ξ)); (b) Với ||x− x ¯|| đủ nhỏ, hàm vectơ bao gồm −f (x, ), h(.) φ(j) (.− y¯)(j = p−k 1, 2, , p − k) (như (2.5)) Q × S × R+ - lồi bất biến điểm Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 41 y lân cận y¯ với hàm scale không phụ thuộc vào x, hàm vectơ bao gồmf (., y¯), g(.) ψ (j) ( − x ¯)(j = 1, 2, , s − l) Q × T × Rs−l + lồi bất biến x ¯; (c) (ζ, 0) ∈ N((¯ x, z¯), Ω) ⇒ ζ = 0, Ω := ker ∂y L ∩ (Rn × ker[∧h(y) + M Φ(y − y¯)])∩ ([Rn × Rm × {(∧, M ) : ∧(S) + M (Rp−k + ) ⊂ K}]) Khi đó, (¯ x, y¯) minimax mạnh địa phương (WMM1), với ràng buộc thêm φ(j) (y − y¯) ≤ 0(j = 1, 2, , p − k) ψ (j) (x − x ¯) ≤ (j = 1, 2, , s − l) theo nón K H Chứng minh Xác định hàm đa trị Φ sau: Φ(x) := {z = (y, ∧, M ) : ∈ ∂y L(x, y; ∧, M, Π, Ξ), ∧h(y)+M φ(y−¯ y) = (p−k) ∧ (S) + M (R+ ) ⊂ K} Ở ∂y L(.) không chứa Π Ξ Từ giả thiết (a), ta có z¯ := (¯ y , ∧, M ) ∈ Φ(¯ x) Từ định nghĩa Φ(.) ta suy grΦ = Ω Sử dụng giả thiết (c), ta có (ζ, 0) ∈ N((¯ x, z¯), grΦ) ⇒ ζ = Theo Aubin [3] Rockafellar [14], điều kiện đảm bảo Φ giả Lipschitz Vì thế, ||x − C x ¯|| đủ nhỏ, Φ(x) = ∅ Vì vậy, (∃z(x) = (y(x), ∧(x), M (x)) Số hóa Trung tâm Học liệu – Đại học Thái Nguyên Φ(x))z(¯ x) = (¯ y , ∧, M ) http://www.lrc-tnu.edu.vn 42 Từ giả thiết (b), −h(y) ∈ S, φ(j) (y − y¯) 0(j = 1, 2, , p − k), f (x, y(x)) − f (x, y) = L(x, y(x); ∧(x), M (x), Π, Ξ) − L(x, y; ∧(x), M (x), Π, Ξ) + ∧(x)[−h(y) + h(y(x))] + M (x)[−φ(y − y¯) + φ(y(x) − y¯)] ∈ −A(x)ζ(y, y(x)) + Q + K ⊂ K, A(x) ∈ ∂y L(x, y(x); ∧(x), M (x), Π, Ξ), ζ(y, y(x)) hàm scale giả thiết (b), φ := (φ(1) , , φ(p−k) ) giá trị Π Ξ khơng đóng vai trị quan trọng tính tốn Vì vậy, y(x) cực đại mạnh theo nón K tốn (WMM1) với ràng buộc thêm φ(j) (y − y¯) ≤ 0(j = 1, 2, , p − k) Do z(x) ∈ Φ(x) giả thiết (a) (b), ||x − x ¯|| đủ nhỏ, −g(x) ∈ T ψ (j) (x − x¯) ≤ 0(j = 1, 2, , s − l) f (x, y(x)) − f (¯ x, y¯) = f (x, y(x)) − f (x, y) + f (x, y¯) − f (¯ x, y¯) = L(x, y(x); ∧(x), M (x), Π, Ξ) − L(x, y; ∧(x), M (x), Π, Ξ) + L(x, y¯; ∧, M , Π, Ξ) − L(¯ x, y¯; ∧, M , Π, Ξ) − ∧(x)h(¯ y ) − M (x)φ(0) + ∧(x)h(y(x)) + M (x)φ(y(x) − y¯) + Π[−g(x) + g(¯ x)] + Ξ[−ψ(x − x¯) + ψ(0)] ∈ −A(x)ζ(¯ y , y(x)) + K + Bγ(x, x¯) + H + K + H ⊂ H, đó, A(x) ζ(.) trên, B ∈ ∂x L(¯ x, y¯; ∧, M , Π, Ξ), γ(.) hàm scale giả thiết (b), ψ := (ψ (1) , , ψ (s−l) ) Vì vậy, x ¯ cực tiểu mạnh theo nón H tốn ngồi (WMM1) với ràng buộc thêm ψ (j) (x − x¯) ≤ (j = 1, 2, , s − l) Nhận xét 2.4 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 43 Giả sử hàm vectơ Θ(x) đạt cực tiểu địa phương yếu z = p với ràng buộc −γ(x) ∈ Γ, nón lồi Γ có điểm Khi đó, khơng có nghiệm x thỏa mãn Θ(x) − Θ(p) ∈ −intQ, − γ(x) ∈ intΓ Nếu hàm vectơ (Θ, γ) convexlike tồn nhân tử (τ, λ) ∈ Q∗ × Γ∗ , khơng đồng thời 0, cho τ T [Θ(x) − Θ(p)] + λT γ(x) ≥ với x gần p Chú ý tính convexlike (khả vi) kéo theo tính lồi bất biến Nếu điều kiện Slater đúng: −γ(c) ∈ intΓ với c đó, nhân tử τ = Khi đó, tồn ma trận Y với Y thuộc nón ma trận S := {y : y(Γ) ⊂ Q}, cho Θ(x) + Y γ(x) đạt cực tiểu yếu (x, y) = (p, Y ) theo nón Q S Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 44 Kết luận Luận văn trình bày phương pháp xấp xỉ trơn cho toán tối ưu với hàm Lipschitz địa phương dựa kĩ thuật lí thuyết hàm suy rộng B.D.Craven [5] điều kiện tối ưu cho toán với hàm Lipschitz địa phương thiết lập phương pháp xấp xỉ trơn Các tốn khơng trơn trình bày luận văn bao gồm: toán quy hoạch với ràng buộc đẳng thức ràng buộc nón, tốn quy hoạch liên tục khơng trơn, tốn điều khiển tối ưu khơng trơn tốn minimax vectơ khơng trơn với ràng buộc nón Phương pháp xấp xỉ trơn Craven tỏ hiệu để xử lí tốn với hàm Lipschitz địa phương khơng gian hữu hạn chiều Với tốn không gian vô hạn chiều phải tiếp cận cách khác Điều kiện tối ưu không trơn đề tài nhiều nhà toán học quan tâm nghiên cứu Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 45 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 Kỹ thuật, Hà Nội [2] Đỗ Văn Lưu (1999) Giải tích Lipschitz, NXB Khoa học Kỹ thuật, Hà Nội Tài liệu tiếng Anh [3] J.P.Aubin (1984), ’Lipschitz behaviour of solutions to convex minimization problems’, Math Oper Res, 9, 87-111 [4] F H Clarke (1983), Optimization and nonsmooth analysis, WileyInterscience, New York [5] B D Craven (1986), ’Nondifferentiable optimization by smooth approximation’ , Optimization 17, 3-17 [6] B D Craven (1994), ’ Convergence of discrete approximations for constrained minimization’ , J Austral Math Soc (Series B)35 ,5059 [7] B D Craven (1978) Mathematical Programming and Control Theory Chapman and Hall, London Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 46 [8] B D Craven (1981) Invex functions and constrained local minima, Bull Austral.Math Soc 24, 357- 366 [9] B D Craven and D V Luu (1998), Lagrangian conditions for a nonsmooth vector- valued minimax, J Austral Math Soc (Series A) 65, 163 - 175 [10] B D Craven and D V Luu (1994), ’Constrained minimax for a vector-valued function’, Optimization 31, 199 - 208 [11] I Ekeland (1979), Nonconvex minimization problems Bull Amer Math Soc (new series) 1, 443 - 474 [12] M.A Hanson (1981), On sufficiency of the Kuhn- Tucker conditions., J Math.Anal Appl, 80, 545 - 550 [13] B Mordukhovich (1994), ’Stability theory for parametric generalized equation and variational inequalities via nonsmooth analysis’, Trans Amer Math Soc 343, 609 - 657 [14] R T Rockafellar, (1985), ’ Lipschitzian properties of multifunctions’, Nonlinear Anal 9, 867 - 885 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ... đưa phương pháp xấp xỉ trơn cho toán tối ưu với hàm Lipschitz địa phương 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 điều kiện cần tối ưu cho tốn tối ưu khơng... 1.5 Bài tố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 PHƯƠNG PHÁP XẤP XỈ TRƠN CHO BÀI TOÁN MINIMAX VECTƠ KHÔNG TRƠN... Chương XẤP XỈ TỐI ƯU KHƠNG TRƠN BẰNG DÃY CÁC BÀI TỐN TỐI ƯU TRƠN Chương trình bày điều kiện cần tối ưu cho toán tối ưu với hàm Lipschitz địa phương bao gồm ràng buộc nón ràng buộc đẳng thức, toán