ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC  - NGUYỄN VĂN MẠNH MỘT PHƯƠNG PHÁP TÁCH GIẢI MỘT LỚP BÀI TOÁN TỐI ƯU LỒI MẠNH LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2016 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC  - NGUYỄN VĂN MẠNH MỘT PHƯƠNG PHÁP TÁCH GIẢI MỘT LỚP BÀI TOÁN TỐI ƯU LỒI MẠNH Chuyên ngành : Toán ứng dụng Mã số : 60 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: GS.TSKH Lê Dũng Mưu THÁI NGUYÊN - 2016 Mục lục Mở đầu 1 Bài toán tối ưu lồi 1.1 Kiến thức chuẩn bị 1.2 Hàm lồi 1.3 Bài toán tối ưu lồi 12 1.3.1 Các khái niệm 12 1.3.2 Sự tồn nghiệm tối ưu 13 1.3.3 Điều kiện tối ưu 15 1.4 Tối ưu có ràng buộc 16 1.4.1 Đối ngẫu 16 1.4.2 Điều kiện tối ưu có ràng buộc 20 Một thuật toán tách giải toán tối ưu lồi mạnh 26 2.1 Toán tử chiếu lên tập lồi đóng 26 2.2 Một thuật toán chiếu giải toán tối ưu lồi 30 30 2.2.1 Thuật toán chiếu đạo hàm 2.2.2 Một thuật toán tách giải toán tối ưu lồi mạnh 35 Kết luận 42 Tài liệu tham khảo 43 DANH MỤC CÁC KÍ HIỆU Kí hiệu Ý nghĩa Rn Không gian Euclide n - chiều trường số thực; N Tập số tự nhiên; xi Tọa độ thứ i x; xT Véctơ hàng (chuyển vị x); < x; y >= xT y Tích vơ hướng vectơ x y ; ||x|| Chuẩn Euclide x; ∇f (x) Đạo hàm f theo x; ∂f (x) Dưới vi phân f theo x; ∂ε f (x) ε - vi phân f theo x Mở đầu Bài toán tối ưu hàm lồi mạnh với ràng buộc lồi lớp toán quan trọng toán quy hoạch lồi Bài tốn có nhiều ứng dụng vấn đề thực tế Ngồi tốn xuất toán phụ phương pháp giải toán tối ưu lồi tổng quát, tốn khác tốn cân bằng, mơ hình kinh tế, kĩ thuật Chính toán cực tiểu hàm lồi mạnh vấn đề quan trọng nhiều nhà toán học ngồi nước nghiên cứu, nhằm mục đích đưa thuật toán hiệu để giải lớp toán Trong phương pháp giải, phương pháp tách có nhiều ưu điểm, đặc biệt phương pháp cho phép tách ràng buộc phức tạp thành ràng buộc đơn giản dễ tính tốn Vì thực đề tài Một phương pháp tách giải lớp toán tối ưu lồi mạnh Luận văn chia làm chương: Chương 1: Bài toán tối ưu lồi Chương trình bày số kiến thức giải tích lồi, phát biểu tốn tối ưu, tồn nghiệm điều kiện tối ưu Chương 2: Một thuật toán tách giải toán tối ưu lồi mạnh Chương trình bày chi tiết tốn tử chiếu lên tập lồi đóng tính chất toán tử chiếu; thuật toán chiếu đạo hàm Cuối chương thuật toán chiếu tách để giải số toán tối ưu lồi mạnh qua m cho phép tránh phải tính hình chiếu PD tập D = Dj j=1 nhiều trường hợp tính hình chiếu PD khó, chí khơng thực được, thay vào ta tách, chiếu lên tập Dj tính hình chiếu PDj dễ dàng Nhân dịp tơi xin bày tỏ lịng biết ơn sâu sắc tới GS TSKH Lê Dũng Mưu, người thầy tận tâm, nhiệt tình hướng dẫn, cung cấp tài liệu, truyền đạt cho kiến thức q trình học tập ln giúp đỡ, động viên tơi hồn thành luận văn Tơi xin trân trọng cảm ơn Ban giám hiệu, Phịng Đào tạo, Khoa Tốn – Tin 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 cao học khóa 2014 – 2016 quan tâm giúp đỡ tơi suốt q trình học tập trường Tôi xin cảm ơn trường Đại học Hạ Long – Quảng Ninh gia đình tạo điều kiện tốt cho việc học tập Cảm ơn bạn bè đồng nghiệp hỗ trợ việc hoàn thành luận văn Thái Nguyên, tháng 10 năm 2016 Học viên Nguyễn Văn Mạnh Chương Bài tốn tối ưu lồi Chương trình bày số kiến thức giải tích lồi, giới thiệu toán tối ưu, tồn nghiệm tối ưu, điều kiện tối ưu tối ưu không ràng buộc, tối ưu có ràng buộc điều kiện tối ưu Kuhn - Tucker Nội dung chương trích dẫn chủ yếu từ tài liệu tham khảo [1]; [2]; [3] [5] 1.1 Kiến thức chuẩn bị Để thuận tiện cho người đọc, phần ta xét số khái niệm kết sử dụng phần Định nghĩa 1.1 Cho hai điểm a, b ∈ Rn Tập tất điểm x ∈ Rn có dạng x = (1 − λ)a + λb , ≤ λ ≤ gọi đoạn thẳng nối a b kí hiệu [a, b] Định nghĩa 1.2 Một tập D ⊆ Rn gọi tập affine D chứa trọn đường thẳng qua hai điểm x, y ∈ D, tức ∀x, y ∈ D, ∀λ ∈ R ⇒ λx + (1 − λ)y ∈ D Mệnh đề 1.1 Tập D = ∅ tập affine có dạng D = M + a, M ⊆ Rn , a ∈ Rn Không gian M xác định gọi không gian song song D Định nghĩa 1.3 Thứ nguyên (chiều) tập affine D thứ nguyên không gian song song với D kí hiệu dim D Định nghĩa 1.4 Siêu phẳng không gian Rn tập hợp điểm có dạng {x ∈ Rn : aT x = α} a ∈ Rn véc tơ khác α ∈ R Định nghĩa 1.5 Cho a ∈ Rn véc tơ khác α ∈ R Tập {x ∈ Rn : aT x ≥ α} gọi nửa không gian đóng tập {x ∈ Rn : aT x > α} gọi nửa không gian mở Định nghĩa 1.6 Một tập D ⊆ Rn gọi tập lồi, D chứa đoạn thẳng qua hai điểm Tức D tập lồi ∀x, y ∈ D, ∀λ ∈ [0, 1] ⇒ λx + (1 − λ)y ∈ D Định lý 1.1 Tập lồi đóng với phép giao, phép cộng, phép nhân với số thực Tức là, C D hai tập lồi Rn C ∩ D, λC + βD tập lồi Định nghĩa 1.7 Ta nói x tổ hợp lồi điểm (vectơ) x1 , x2 , , xk k k λj xj , λj ≥ (j = 1, , k), x= j=1 λj = j=1 Mệnh đề 1.2 Tập hợp D lồi chứa tổ hợp lồi điểm Tức là, D lồi k ∀k ∈ N, ∀λ1 , , λk ≥ : k λj = 1, j=1 ∀x1 , , xk ∈ D ⇒ λj xj ∈ D j=1 Định nghĩa 1.8 Một tập gọi tập lồi đa diện, giao số hữu hạn nửa khơng gian đóng Định nghĩa 1.9 Bao lồi tập D giao tất tập lồi chứa D Bao lồi tập D ký hiệu coD Bao lồi tập D tập lồi nhỏ chứa D Định nghĩa 1.10 Thứ nguyên tập lồi D cho thứ nguyên đa tạp affine nhỏ chứa D Đa tạp affine gọi bao affine D ký hiệu af f D Thứ nguyên tập lồi D kí hiệu dim D Định nghĩa 1.11 Một điểm a tập lồi D gọi điểm tương đối với x ∈ D có số λ > a + λ(x − a) ∈ D Tập điểm tương đối D kí hiệu riD Định nghĩa 1.12 Một tập D gọi nón ∀λ > 0, ∀x ∈ D ⇒ λx ∈ D Một nón gọi nón nhọn khơng chứa đường thẳng Một nón gọi nón lồi đồng thời tập lồi Nếu nón lồi lại tập lồi đa diện ta nói tập lồi đa diện Định nghĩa 1.13 Cho D ⊆ Rn tập lồi x0 ∈ D (i) Tập ND (x0 ) := {ω ∈ Rn : ω, x − x0 ≤ 0, ∀x ∈ D} gọi nón pháp tuyến ngồi D x0 tập −ND (x0 ) gọi nón pháp tuyến D x0 (ii) Tập NDε (x0 ) := {ω ∈ Rn : ω, x − x0 ≤ ε, ∀x ∈ D} gọi nón pháp tuyến ε D x0 Ta có ∈ ND (x0 ) (hoặc thực phép dời từ x0 → 0) dùng định nghĩa ta có ND (x0 ) nón lồi đóng Định nghĩa 1.14 Cho hai tập C D, ta nói siêu phẳng H := {x : v, x = λ} (i) Tách hai tập C D v, a ≤ λ ≤ v, b , ∀a ∈ C, ∀b ∈ D; (ii) Tách chặt C D nếu: v, a < λ < v, b , ∀a ∈ C, ∀b ∈ D; (iii) Tách mạnh C D nếu: sup v, x < λ < inf v, y y∈B x∈A Bổ đề 1.1 Trong Rn cho tập lồi đóng C = ∅ điểm a ∈ / C Bao tồn x0 ∈ C cho: a − x0 , x − x0 ≤ 0, ∀x ∈ C Định lý 1.2 (Định lí tách 1) Cho C D hai tập lồi khác rỗng Rn cho C ∩ D = ∅ Khi có siêu phẳng tách C D Chứng minh Xét C − D := {x − y |x ∈ C, y ∈ D } Ta có C − D lồi ∈ / C − D Thật vậy, giả sử ∈ C − D Khi ta có x − y = 0, suy x = y ∈ C ∩ D (vô lý) Đặt E := cl (C − D) Với a ∈ ri(C − D), ∈ / C − D, nên điểm không thuộc ri(C − D) đoạn [a, 0] điểm biên C − D, suy ∈ / E ∈ E\riE + Nếu ∈ / E Theo Bổ đề 1.1, ta có x0 ∈ E : t = − x0 = cho t, x − x0 ≤ 0, ⇒ t, z ≤ 0, ∀z ∈ E ⇒ sup t, z ≤ ⇒ t, x − y ≤ 0, ∀x ∈ C, ∀y ∈ D ∀x ∈ E 29 Điều với xλ ∈ C λ ∈ (0; 1) Do cho λ tiến tới 0, ta π − y, x − π ≥ 0, ∀x ∈ C Vậy y − π ∈ NC (π) Bây giả sử có b) Với x ∈ C , có: ||y − π||2 ≤ (y − π)T (y − x) ≤ ||y − π||||y − x|| Suy ||y − π|| ≤ ||y − x||, ∀x ∈ C π = P (y) (ii) Do y − π ∈ NC (π), nên π − y, x − π ≥ 0, ∀x ∈ C Vậy π − y, x = π − y, π siêu phẳng tựa C π Siêu phẳng tách y khỏi C y khác π , nên π − y, y − π = −||π − y||2 < (iii) Do z − P (x) ∈ NC (P (z)) với z , nên áp dụng với z = x z = y , ta có: x − P (x), P (y) − P (x) ≤ y − P (y), P (x) − P (y) ≤ Cộng hai bất đẳng thức lại P (y) − P (x), P (y) − P (x) + x − y ≤ Từ theo bất đẳng thức Cauchy-Schwarz, suy ||P (x) − P (y)|| ≤ ||x − y|| Để chứng minh tính đồng bức, áp dụng tính chất b) (i), với P (x) P (y), ta có: P (x) − x, P (x) − P (y) ≤ y − P (y), P (x) − P (y) ≤ 30 Cộng hai bất đẳng thức ta P (x) − P (y) + y − x, P (x) − P (y) = P (x) − P (y), y − x + ||P (x) − P (y)||2 ≤ Chuyển vế ta có P (x) − P (y), y − x ≥ ||P (x) − P (y)||2 Đây tính đồng ta cần chứng minh 2.2 2.2.1 Một thuật toán chiếu giải toán tối ưu lồi Thuật toán chiếu đạo hàm Xét tốn tối ưu lồi khơng ràng buộc (P): {f (x) : x ∈ C} , (P) C tập lồi đóng khác rỗng f hàm lồi khả vi phân C Bước chuẩn bị ∞ βj với βj > cho: Chọn chuỗi j=1 ∞ ∞ βj2 < +∞ βj = +∞, j=1 j=1 Chọn x1 ∈ C điểm xuất phát Bước lặp k Bắt đầu vào bước lặp ta có xk ∈ C Tính g k ∈ ∂f (xk ) a) Nếu g k = dừng thuật tốn xk nghiệm tối ưu (P) b) Nếu g k = 0, tính xk+1 = PC xk − αk g k , βk γk k+1 với ak := γ k := max 1, ||g k || • Nếu x = xk thuật tốn dừng, xk nghiệm tối ưu 31 tốn • Trái lại, cho k ← k + lặp lại bước lặp k với k := k + Định lý 2.2 Xét tốn tối ưu lồi khơng ràng buộc (P) (i) Nếu thuật toán dừng lại bước lặp k xk nghiệm tối ưu tốn (P) (ii) Nếu thuật tốn kéo dài vơ hạn, xk hội tụ đến nghiệm x∗ toán (P) nghĩa ||xk − x∗ || → k → ∞ Chứng minh (i) Nếu thuật toán dừng bước lặp thứ k g k = xk = PC xk − αk g k Trường hợp 1: g k = ∈ ∂f (xk ), theo định nghĩa đạo hàm, ta có: 0, x − xk + f (xk ) ≤ f (x) ≤ 0, ∀x ∈ C Do f (xk ) ≤ f (x), ∀x ∈ C (2.1) Tức xk nghiệm tối ưu toán (P) Trường hợp 2: xk = xk+1 = PC xk − αk g k Sử dụng tính chất phép chiếu meetric, ta có: (xk − αk g k ) − xk , x − xk ≤ ⇔ −αk g k , x − xk ≤ ⇔ g k , x − xk ≤ (2.2) Do g k ∈ ∂f (xk ), ta có g k , x − xk + f (xk ) ≤ f (x) Kết hợp với bất đẳng thức (2.2), cho f (xk ) ≤ f (x) với x ∈ C Khi xk nghiệm tối ưu toán (P) (ii) Ta giả sử thuật tốn khơng dừng Cho x∗ nghiệm toán (P) Khẳng định (ii) chứng minh dựa vào bổ đề Bổ đề 2.1 Ta có: ||xk+1 − xk || ≤ βk , ∀k ∈ N 32 Chứng minh Theo định nghĩa αk ta có: αk ||g k || = βk ||g k || ≤ βk max {1, ||g k ||} Khi xk+1 = PC xk − αk g k , ta có: xk − αk g k − xk+1 , x − xk+1 ≤ 0, ∀x ∈ C (2.3) Thay x xk : ||xk − xk+1 ||2 ≤ αk g k , xk − xk+1 ≤ αk ||g k ||||xk − xk+1 || (2.4) ≤ βk ||xk − xk+1 || Suy ||xk − xk+1 || ≤ βk Bổ đề 2.2 Dãy ||xk − x∗ ||2 hội tụ với x ∈ C Chứng minh Ta có ||xk − x∗ ||2 = ||xk+1 − xk ||2 − xk − xk+1 , x∗ − xk+1 + ||xk+1 − x∗ ||2 Do ||xk+1 − x∗ ||2 = ||xk − x∗ ||2 − ||xk+1 − xk ||2 + xk − xk+1 , x∗ − xk+1 (2.5) Chú ý từ (2.4) ta có αk − g k , xk − xk+1 ≤ βk ||xk − xk+1 || ≤ βk2 (2.6) Từ (2.5) (2.6), ta có: ||xk+1 − x∗ ||2 ≤ ||xk − x∗ ||2 − ||xk+1 − xk ||2 + αk g k , x∗ − xk+1 ≤ ||xk − x∗ ||2 + αk g k , x∗ − xk+1 = ||xk − x∗ ||2 + αk g k , x∗ − xk + αk g k , xk − xk+1 ≤ ||xk − x∗ ||2 + αk g k , x∗ − xk+1 + 2βk2 (2.7) 33 Từ g k ∈ ∂f (xk ) ta có: g k , x∗ − xk ≤ f (x∗ ) + f (xk ) (2.8) Thay (2.8) vào (2.7): ||xk+1 − x∗ ||2 ≤ ||xk − x∗ ||2 + 2αk (f (x∗ ) − f (xk )) + 2βk2 (2.9) Khi x∗ nghiệm tối ưu, f (xk ) ≥ f (x∗ ) từ (2.9) ta có ||xk+1 − x∗ ||2 ≤ ||xk − x∗ ||2 + 2βk2 , ∞ từ giả thiết k=0 βk2 < +∞ theo Bổ đề 2.2 dãy ||xk − x∗ ||2 hội tụ Bổ đề 2.3 Ta có: lim sup f (xk ) = (2.10) k→+∞ x∈C Chứng minh Từ Bổ đề 2.1, ta có: ≤ 2αk (f (xk ) − f (x∗ )) ≤ ||xk − x∗ ||2 + 2βk2 (2.11) Kết hợp hai trường hợp ta có: ∞ αk (f (xk ) − f (x∗ )) 0≤2 k=0 m ∗ ≤ ||x − x || − ||x m+1 ∗ βk2 − x || + k=0 m ≤ ||x0 − x∗ ||2 + βk2 k=0 ≤ ||xk − x∗ ||2 + αk g k , x∗ − xk+1 + 2βk2 Cho m → +∞ ta có: ∞ m k 0≤2 ∗ ∗ k=0 m Do k=0 βk2 αk (f (x ) − f (x )) ≤ ||x − x || + (2.12) k=0 βk2 < +∞ ta có: +∞ αk (f (xk ) − f (x∗ )) < +∞, k=0 (2.13) 34 αk = βk βk ≥ max {1, ||g k ||} L0 (2.14) Kết hợp với (2.13): L0 +∞ +∞ k αk (f (xk ) − f (x∗ )) < +∞ ∗ βk (f (x ) − f (x )) ≤ (2.15) k=0 k=0 +∞ βk = +∞, suy ra: Do k=0 lim sup(f (xk ) − f (x∗ )) = (2.16) k→+∞ x∈C Áp dụng Bổ đề 2.1, Bổ đề 2.2 Bổ đề 2.3 ta có khẳng định (ii) định lý chứng minh Theo định nghĩa limsup, tồn dãy xkj dãy xk cho: lim (f (xkj ) − f (x∗ )) = lim sup(f (xk ) − f (x∗ )) k→+∞ k→+∞ = Do xkj bị chặn, ta giả sử rằng: lim xkj = x¯ j→+∞ Khi f (x∗ ) − f (¯ x) = lim (f (x∗ ) − f (xkj )) k→+∞ = − lim (f (xkj ) − f (x∗ )) k→+∞ = − lim sup(f (xk ) − f (x∗ )) k→+∞ x∈C = Vì x ¯ nghiệm tối ưu toán, nên dãy xkj dãy xk hội tụ đến x ¯, đó: lim xk = lim xkj = x¯ k→+∞ Như dãy xk hội tụ đến x ¯ k→+∞ xk − x¯ hội tụ 35 Trong số tốn, phương pháp nhìn chung việc tính hình chiếu PD gặp nhiều khó khăn Khi ta phải dùng phương pháp m Dj chiếu tách tập D = j=1 2.2.2 Một thuật toán tách giải toán tối ưu lồi mạnh Xét toán m {f (x) : x ∈ D = Dj }, j=1 với f hàm lồi, khả vi không gian Rn , Dj tập lồi Bổ đề 2.4 Giả sử {αk } dãy số không âm cho αk ≤ (1 − λk )αk + λk δk + σk , k = 0, 1, 2, {λk } ⊂ (0, 1), {δk } , {σk } thỏa mãn điều kiện sau: ∞ λk = ∞; (i) k=1 (ii) lim sup δk ≤ 0; k→∞ ∞ |σk | < ∞ (iii) k=1 Khi lim αk = x→∞ Giả sử: f (x) hàm lồi, nửa liên tục khả vi phân D với x ∈ D; H(x) := ∂f (x) L-Lipschitz D; F : H → 2H ánh xạ đa giá trị D ⊆ domF Với x ∈ D, g ∈ F (x) ta định nghĩa: y(x) := x − α1 g , α > Ta có kết Bổ đề 2.5 Nếu F hàm lồi mạnh hệ số β L-Lipschitz D thì: 2β L2 y(x) − y(x ) ≤ (1 − + 2) x − x , α α ∀g ∈ F (x), g = PF (x ) (g) ∀x, x ∈ D; 36 Ta có thuật tốn phối hợp phương pháp Gradient phương pháp lặp Mann-Kranosel’skii Thuật tốn: m µj = (chẳng hạn µj = Chọn số µj > (j = 1, , m) : j=1 m, ∀j = 1, , m); dãy {λk }k≥0 : ∞ ∞ k→∞ |λk − λk−1 | < +∞, λk = +∞, < λk < 1, lim λk = 0, k=0 k=0 , k = 0, 1, 2, ) k+1 + Bước 0: Chọn x0 ∈ D, k = 0; (chẳng hạn λk = + Mỗi bước lặp k , lấy g k ∈ ∂f (xk ) y k := arg { g k , y − xk + k+1 x m k := λk y + (1 − λk ) α y − xk , y ∈ Rn } = xk − α1 g k ; µj PDj (xk ), j=1 α > L2 2β PDj (xk ) hình chiếu điểm xk tập Dj , L số Lipschitz đạo hàm: ||∇f (x) − ∇f (x )|| ≤ L||x − x ||, ∀x, x ∈ Rn Thuật tốn kéo dài vơ hạn, dừng chừng xk = y k = xk+1 Khi xk điểm cực tiểu Nếu trái lại ta có kết Định lý 2.3 Giả sử f hàm lồi mạnh với hệ số β , nửa liên tục Khi dãy xk hội tụ đến nghiệm x∗ (P) Chứng minh m Đặt P (x) := µj PDj (x) j=1 Khi ta có P (x) = x x ∈ Dj , ∀j = 1, 2, , m Tức x thuộc miền chấp nhận toán Bước 1: Chúng ta xk , y k , g k , P (xk ) dãy bị chặn 37 Thật vậy, theo định nghĩa y k , xk+1 , P (xk ), ta có: xk+1 − x∗ = λk y k + (1 − λk )P (xk ) − x∗ = λk (y k − x∗ ) + (1 − λk )[P (xk ) − P (x∗ ) ≤ λk y k − x∗ + (1 − λk ) P (xk ) − P (x∗ ) ≤ λk xk − g k − x∗ + (1 − λk ) xk − x∗ α (2.17) Vì f hàm lồi mạnh, hệ số β nên ∂f (x) vi phân hàm mục tiêu x : g k ∈ ∂f (xk ), ta có: x − x − (g k − g ∗ ) α ∗ k = yk − y∗ 2β L + ) xk − x∗ α α 2 k = (1 − γ) x − x∗ , ≤ (1 − < γ = − 1− 2β α + L α2 (2.18) < Như vậy: xk − x∗ − k (g − g ∗ ) ≤ (1 − γ) xk − x∗ α Điều suy 1 k g − x∗ = xk − x∗ − (g k − g ∗ ) − g ∗ α α α ∗ g ≤ xk − x∗ − (g k − g ∗ ) + α α ∗ g ≤ (1 − γ) xk − x∗ + α Thay bất đẳng thức vào (2.17) ta được: xk − λk ∗ g α g∗ + γλk αγ (2.19) xk+1 − x∗ ≤ (1 − γλk ) xk − x∗ + = (1 − γλk ) xk − x∗ ≤ max k x −x ∗ g∗ , αγ (2.20) Điều có nghĩa xk+1 − x∗ ≤ max x0 − x∗ , g∗ αγ 38 Như xk bị chặn Mà lim λk = 0, từ suy y k , P (xk ) k→∞ bị chặn Bước 2: Chúng ta chứng minh xk → k → ∞ Thật vậy, ta có: x k+1 ∗ −x Lấy xkj λk ∗ λk ∗ = x −x + g − g α α λ2k ∗ λk ∗ k+1 ∗ = x + g −x + g α α λk λk −2 g ∗ , xk+1 − x∗ + g ∗ α α = λk xk − x∗ − (g k − g ∗ ) + (1 − λk ) P (xk ) − P (x∗ ) α λ2 λk ∗ k+1 g ,x − x∗ − k2 g ∗ −2 α α k ∗ k ∗ ≤ λk x − x − (g − g ) + (1 − λk ) P (xk ) − P (x∗ ) α λk −g ∗ , xk+1 − x∗ +2 α 2αβ − L2 λk k ∗ λ x − x ≤ 1− + −g ∗ , xk+1 − x∗ k α α (2.21) k+1 ∗ dãy mà xkj → x lim sup −g ∗ , xk+1 − x∗ = lim −g ∗ , xkj − x∗ k→∞ k→∞ ∗ ∗ (2.22) = −g , x − x Như vậy, từ (2.21) (2.22), áp dụng Bổ đề 2.4, kết luận xk − x∗ → k → ∞ Ví dụ 2.1 Xét tốn {f (x1 , x2 ) = x21 + 2x22 : x ∈ D = D1 ∩ D2 } đó: D2 = D1 = (x1 , x2 ) : x21 + x22 ≤ , (x1 , x2 ) : −2 ≤ x1 ≤ ; −2 ≤ x2 ≤ 39 Hình 2.1: Miền D = D1 ∩ D2 Dễ thấy f hàm lồi mạnh, với hệ số β = 2, số Lipschitz √ L2 = 5, chẳng hạn α = đạo hàm L = Chọn α > 2β Chọn số µ1 = µ2 = thỏa mãn: µ1 + µ2 = 1; µ1 , µ2 > Chọn dãy λk = k+1 , k = 0, 1, 2, thỏa mãn: ∞ ∞ k k=0 k Ta có g = ∂f (x ) = 2xk1 4xk2 k=0 Chọn x0 = (−1, 0) ∈ D ⇒ g = y = x − g0 = α 0 |λk − λk−1 | < +∞ λk = +∞, lim λk = 0, k→∞ −1 −2 −2 − 0 = −2 0 x = λ0 y + (1 − λ0 ) µ1 PD1 (x ) + µ2 PD2 (x ) = y = ⇒g = −4 −2 40 1 y =x − 1 αg = − 23 − − 43 = −4 x2 = λ1 y + (1 − λ1 ) µ1 PD1 (x1 ) + µ2 PD2 (x1 )   −4 −2 −1 1 1  + + = = 2 0 ⇒g = −23 18 y = x − g2 = −23 36 16 −23 36 16 − −23 18 = −23 54 16 ⇒ x3 = λ2 y + (1 − λ2 ) µ1 PD1 (x2 ) + µ2 PD2 (x2 )    92 23 −23 √ − 54  − 9193  36  = + + 3 √ 27 16 9193 Ví dụ 2.2 Xét tốn {f (x1 , x2 ) = x21 + 3x22 : x ∈ D = D1 ∩ D2 }, đó: D1 = (x1 , x2 ) : x21 + x22 ≤ , D2 = (x1 , x2 ) : (x1 − 2)2 + x22 ≤ Hình 2.2: Miền D = D1 ∩ D2 Dễ thấy f hàm lồi mạnh, với hệ số β = 2, số Lipschitz √ L2 đạo hàm L = 10 Chọn α > = 10, chẳng hạn α = 11 Chọn 2β 41 số µ1 = µ2 = thỏa mãn: µ1 + µ2 = 1; µ1 , µ2 > Chọn dãy λk = , k = 0, 1, 2, thỏa mãn: k+1 ∞ ∞ |λk − λk−1 | < +∞ λk = +∞, lim λk = 0, k→∞ k=0 k=0 k 2xk1 k Ta có g = ∂f (x ) = 6xk2 Chọn x0 = (1, 0) ∈ D ⇒ g = 1 y = x − g0 = α − 11 0 = 0 11 0 x = λ0 y + (1 − λ0 ) µ1 PD1 (x ) + µ2 PD2 (x ) = y = 18 11 ⇒g = 11 y = x − g1 = α 11 18 11 − 11 81 121 = 0 x2 = λ1 y + (1 − λ1 ) µ1 PD1 (x1 ) + µ2 PD2 (x1 ) = 2 ⇒g = 81 121 0 + = 283 484 283 242 y = x − g2 = 11 1 + 2 283 484 − 11 283 242 = 2547 5324 ⇒ x3 = λ2 y + (1 − λ2 ) µ1 PD1 (x2 ) + µ2 PD2 (x2 ) = 2547 5324 + + 0 = 31714 63888 42 Kết luận Luận văn trình bày vấn đề sau: Trình bày kiến thức tập lồi, hàm lồi, hàm lồi mạnh Phát biểu toán tối ưu, tồn nghiệm tối ưu điều kiện tối ưu không ràng buộc, tối ưu có ràng buộc, điều kiện Kuhn Tucker ví dụ minh họa Trình bày kiến thức tốn tử chiếu lên tập lồi đóng, tính chất tốn tử chiếu thuật tốn chiếu đạo hàm để giải toán đặc biệt thuật toán chiếu tách để giải tốn tối ưu lồi mạnh, qua cho phép tránh phải tính hình chiếu PD m tập D = Dj nhiều trường hợp tính hình chiếu PD j=1 khó, chí khơng thực được, thay vào ta tách, chiếu lên tập Dj tính hình chiếu PDj dễ dàng Mặc dù cố gắng kiến thức thời gian có hạn nên kết luận văn cịn nhiều hạn chế chắn không tránh khỏi thiếu sót, mong nhận nhiều ý kiến đóng góp q báu thầy bạn bè đồng nghiệp 43 Tài liệu tham khảo Tài liệu Tiếng Việt [1] Nguyễn Văn Hiền, Lê Dũng Mưu, Nguyễn Hữu Điển (2015), Giáo trình Giải tích lồi ứng dụng, NXB Đại học Quốc gia Hà Nội [2] Trần Vũ Thiệu, Nguyễn Thị Thu Thủy (2011), Giáo trình tối ưu phi tuyến, NXB Đại học Quốc gia Hà Nội Tài liệu Tiếng Anh [3] P M Duc, L D Muu, A splitting algorithm for a class of bilevel equilibrium problems involving nonexpansive mappings, Optimization (will publish) [4] Nesterov YU E (1983), A method of solving convex programming problems with convergence rate O(1/ k2), Soviet Math Dokl, 27(2), pp 372 - 377 [5] H Tuy (1998), Convex Analysis and Global Optimization, Springer ... Mở đầu Bài toán tối ưu hàm lồi mạnh với ràng buộc lồi lớp toán quan trọng tốn quy hoạch lồi Bài tốn có nhiều ứng dụng vấn đề thực tế Ngoài toán xuất toán phụ phương pháp giải toán tối ưu lồi tổng... Mạnh Chương Bài toán tối ưu lồi Chương trình bày số kiến thức giải tích lồi, giới thiệu tốn tối ưu, tồn nghiệm tối ưu, điều kiện tối ưu tối ưu khơng ràng buộc, tối ưu có ràng buộc điều kiện tối. .. Một thuật toán tách giải toán tối ưu lồi mạnh 26 2.1 Tốn tử chiếu lên tập lồi đóng 26 2.2 Một thuật toán chiếu giải toán tối ưu lồi 30 30 2.2.1 Thuật toán chiếu