Tài liệu Bài toán quy hoạch lồi

i Mục lục Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i Lời cảm ơn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Chương 1. Các kiến thức cơ bản về tập lồi và hàm lồi . . . . . . . . . 2 1.1. Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2. Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Chương 2. Điều kiện cực tiểu hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . 12 2.1. Bài toán quy hoạch lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.1.1. Các khái niệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.2. Sự tồn tại nghiệm tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.3. Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2. Tối ưu có ràng buộc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1. Đối ngẫu Lagrange. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2. Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 13 14 16 16 19 Chương 3. Một số phương pháp giải bài toán quy hoạch lồi . . 27 3.1. Các thuật toán sử dụng đạo hàm bậc nhất . . . . . . . . . . 27 3.1.1. 3.1.2. 3.1.3. 3.1.4. Thuật toán gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Phương pháp chiếu Gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Thuật toán chiếu dưới gradient xấp xỉ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Thuật toán Frank-Wolfe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 30 32 38 3.2. Phương pháp Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.3. Phương pháp hàm phạt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.3.1. Phương pháp hàm phạt điểm ngoài. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2. Phương pháp hàm phạt điểm trong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 48 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 ii LỜI CẢM ƠN Trước khi trình bày nội dung chính của khóa luận, em xin bày tỏ lòng biết ơn sâu sắc tới GS.TSKH. Lê Dũng Mưu người đã tận tình hướng dẫn và giúp đỡ em trong suốt quá trình học tập và nghiên cứu để em có thể hoàn thành khóa luận này. Em cũng xin bày tỏ lòng biết ơn chân thành tới quý thầy, cô giáo Viện Toán học - Viện Khoa học và Công nghệ Việt Nam đã giảng dạy và giúp đỡ em hoàn thành khóa học. Nhân dịp này em cũng xin chân thành cảm ơn Ban Giám hiệu, các bạn đồng nghiệp Trường Đại học Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên, gia đình và bạn bè đã luôn động viên, giúp đỡ và tạo điều kiện cho em về mọi mặt trong suốt quá trình học tập và thực hiện khóa luận tốt nghiệp. Mặc dù đã có nhiều cố gắng nhưng Luận văn khó tránh khỏi những thiếu sót. Tác giả rất mong nhận được ý kiến đóng góp của quý thầy, cô và bạn đọc để luận văn được hoàn thiện hơn. Xin trân trọng cảm ơn! Hà Nội, ngày 30 tháng 08 năm 2011 Tác giả Quách Thị Mai Liên 1 MỞ ĐẦU Quy hoạch lồi là một lớp bài toán cơ bản của tối ưu hóa. Một đặc điểm cơ bản nhất của lớp bài toán này là mọi điểm cực tiểu địa phương đều là cực tiểu tuyệt đối. Tính chất quan trọng này cho phép các lý thuyết có tính địa phương, như giới hạn, vi phân,... có thể áp dụng trực tiếp vào quy hoạch lồi. Lý thuyết về bài toán quy hoạch lồi đã được quan tâm nghiên cứu nhiều và đã thu được nhiều kết quả quan trọng dựa trên lý thuyết của giải tích lồi và tối ưu hóa; về phương diện tính toán, đã có khá nhiều phương pháp hữu hiệu cho lớp bài toán này. Các phương pháp đó đã được giới thiệu trong cuốn sách Tối ưu lồi (Convex Optimization) của các tác giả Stephen Boyd and Lieven Vandenberghe do nhà xuất bản Cambridge University Press in năm 2004. Mục đích của bản luận văn này là để trình bày một số phương pháp cơ bản nhất cho bài toán quy hoạch lồi. Cụ thể luận văn trình bày các phương pháp sau: các phương pháp sử dụng đạo hàm bậc nhất, phương pháp Newton và các phương pháp hàm phạt. Luận văn gồm có 3 chương: • Chương 1: Giới thiệu các kiến thức cơ bản nhất về giải tích lồi, đặc biệt chú trọng vào phép chiếu vuông góc lên một tập lồi đóng và tính dưới vi phân của hàm lồi; chúng được sử dụng trong các chương tiếp theo. • Chương 2: Trình bày đối ngẫu Lagrange và áp dụng Định lý Krush Kuhn - Tucker, Định lý Kuhn - Tucker để giải bài toán quy hoạch lồi và các định lý về sự tồn tại nghiệm tối ưu của bài toán quy hoạch lồi. • Chương 3: Trình bày các phương pháp giải bài toán quy hoạch lồi như: phương pháp dùng đạo hàm bậc nhất gradient, chiếu gradient và trường hợp tổng quát của nó là chiếu dưới gradient xấp xỉ, thuật toán Frank Wolf, phương pháp Newton dùng đạo hàm bậc hai và các phương pháp hàm phạt. 2 Chương 1 Các kiến thức cơ bản về tập lồi và hàm lồi Trong luận văn này, ta chỉ xét không gian hữu hạn chiều IRn với tích vô hướng được ký hiệu là h., .i và chuẩn tương ứng được ký hiệu là k.k. Chương này trình bày một số kiến thức cơ bản nhất của giải tích lồi sẽ được sử dụng ở chương sau. Nội dung của chương được trích dẫn chủ yếu từ tài liệu tham khảo [1] và [3]. 1.1. Tập lồi Định nghĩa 1.1. Cho hai điểm a, b ∈ IRn . (i) Một đường thẳng đi qua hai điểm a, b là tập hợp có dạng {x ∈ IRn : x = αa + βb, α, β ∈ IR, α + β = 1}. (ii) Đoạn thẳng nối hai điểm a, b trong IRn có dạng {x ∈ IRn : x = αa + βb, α ≥ 0, β ≥ 0, α + β = 1}. Định nghĩa 1.2. Một tập D được gọi là tập affine nếu D chứa mọi đường thẳng đi qua hai điểm bất kỳ x, y ∈ D, tức là ∀x, y ∈ D, ∀λ ∈ IR ⇒ λx + (1 − λ)y ∈ D. Mệnh đề 1.1. Tập D 6= ∅ là tập affine khi và chỉ khi nó có dạng D = M + a với M là một không gian con của IRn và a ∈ IRn . Không gian M được xác định duy nhất và được gọi là không gian con song song của D. 3 Định nghĩa 1.3. Thứ nguyên (hay chiều) của một tập affine D là thứ nguyên của không gian con song song với D và được ký hiệu là dim D. Định nghĩa 1.4. Siêu phẳng trong không gian IRn là một tập hợp các điểm có dạng {x ∈ IRn : aT x = α}, trong đó a ∈ IRn là một vectơ khác 0 và α ∈ IR. Định nghĩa 1.5. Cho a ∈ IRn là một vectơ khác 0 và α ∈ IR. Tập {x : aT x ≥ α}, được gọi là nửa không gian đóng và tập {x : aT x > α} gọi là nửa không gian mở. Định nghĩa 1.6. Một tập D được gọi là một tập lồi nếu ∀a, b ∈ D và 0 ≤ λ ≤ 1 ⇒ λa + (1 − λ)b ∈ D. Định lí 1.1. Tập lồi là đóng với phép giao, phép cộng, phép nhân với một số thực. Tức là, nếu C và D là hai tập lồi trong IRn thì C ∩ D, λC + βD cũng là các tập lồi. Định nghĩa 1.7. Ta nói x là tổ hợp lồi của các điểm (vectơ) x1 , ..., xk nếu x= k X λj xj , λj ≥ 0 (j = 1, ..., k), j=1 k X λj = 1. j=1 Mệnh đề 1.2. Tập hợp D là lồi khi và chỉ khi nó chứa mọi tổ hợp lồi của các điểm của nó. Tức là, D lồi khi và chỉ khi ∀k ∈ IN, ∀λ1 , ..., λk ≥ 0 : k X λj = 1, ∀x1 , ..., xk ∈ D ⇒ j=1 k X λj xj ∈ D. j=1 Định nghĩa 1.8. Một tập được gọi là tập lồi đa diện nếu nó là giao của một số hữu hạn các nửa không gian đóng. 4 Định nghĩa 1.9. Bao lồi của một tập D là giao của tất cả các tập lồi chứa D. Bao lồi của tập D được ký hiệu là coD. Bao lồi của một tập D là tập lồi nhỏ nhất chứa D. Định nghĩa 1.10. Thứ nguyên của một tập lồi D được cho bởi thứ nguyên của đa tạp affine nhỏ nhất chứa D. Đa tạp affine này được gọi là bao affine của D và được ký hiệu là aff D. Thứ nguyên của tập lồi D sẽ được ký hiệu là dimD. Định nghĩa 1.11. Một điểm a của một tập lồi D gọi là điểm trong tương đối nếu với mọi x ∈ D đều có một số λ > 0 để cho a + λ(x − a) ∈ D. Tập các điểm trong tương đối của D được ký hiệu riD. Định nghĩa 1.12. Một tập D được gọi là nón nếu ∀λ > 0, ∀x ∈ D ⇒ λx ∈ D. Một nón được gọi là nón nhọn nếu nó không chứa đường thẳng. Một nón được gọi là nón lồi nếu nó đồng thời là tập lồi. Nếu nón lồi này lại là một tập lồi đa diện thì ta nói nó là nón lồi đa diện. Định nghĩa 1.13. Cho D ⊆ IRn là một tập lồi và x0 ∈ D. (i) Tập ND (x0 ) := {ω ∈ IRn : hω, x − x0 i ≤ 0, ∀x ∈ D}. gọi là nón pháp tuyến ngoài của D tại x0 và tập −ND (x0 ) được gọi là nón pháp tuyến trong của D tại x0 . (ii) Tập ND (x0 ) := {ω ∈ IRn : hω, x − x0 i ≤ , ∀x ∈ D} được gọi là nón pháp tuyến  của D tại x0 . Hiển nhiên 0 ∈ ND (x0 ) và dùng định nghĩa ta có ND (x0 ) là một nón lồi đóng. Trong chương 2 và chương 3, ta sẽ sử dụng các định lý tách tập lồi, đây cũng là những định lý cơ bản nhất của giải tích lồi. 5 Định nghĩa 1.14. Cho hai tập C và D, ta nói rằng siêu phẳng H := {x : hv, xi = λ} (i) tách hai tập C và D nếu hv, ai ≤ λ ≤ hv, bi, ∀a ∈ C, b ∈ D. (ii) tách chặt C và D nếu: hv, ai < λ < hv, bi, ∀a ∈ C, b ∈ D. (iii) tách mạnh C và D nếu: suphv, xi < λ < inf hv, yi. y∈B x∈A Định lí 1.2 (Định lý tách 1). Cho C và D là hai tập lồi khác rỗng trong IRn sao cho C ∩ D = ∅. Khi đó có một siêu phẳng tách C và D. Định lí 1.3 (Định lý tách 2). Cho C và D là hai tập lồi khác rỗng trong IRn sao cho C ∩ D = ∅. Giả sử có ít nhất một tập là compăc. Khi đó hai tập C và D có thể tách mạnh được bởi một siêu phẳng. Hệ quả 1.1 (Bổ đề Farkas). Cho a ∈ IRn và A là ma trận cấp m × n. Khi đó ha, xi ≥ 0 với mọi x thỏa mãn Ax ≥ 0, khi và chỉ khi tồn tại y ≥ 0 thuộc IRm sao cho a = AT y . Ý nghĩa hình học của bổ đề Farkas: siêu phẳng đi qua gốc tọa độ ha, xi = 0 để nón Ax ≥ 0 về một phía của nó khi và chỉ khi vectơ pháp tuyến a của siêu phẳng nằm trong nón sinh bởi các hàng của ma trận A. Định nghĩa 1.15. Cho D 6= ∅ (không nhất thiết lồi) và y là một vectơ bất kỳ, đặt: dD (y) := inf kx − yk. x∈D Ta nói dD (y) là khoảng cách từ y đến D. Nếu tồn tại π ∈ D sao cho dD (y) = ky − πk, thì ta nói π là hình chiếu (vuông góc) của y trên D và ký hiệu là π = PD (y). 6 Theo định nghĩa, ta thấy rằng hình chiếu PD (y) của y trên D là nghiệm của bài toán tối ưu   1 min kx − yk2 : x ∈ D . x∈D 2 Nói cách khác việc tìm hình chiếu của y trên D có thể đưa về việc tìm cực tiểu của hàm toàn phương ||x − y||2 trên D. Nếu D 6= ∅ thì dD (y) hữu hạn, vì 0 ≤ dD (y) ≤ kx − yk, ∀x ∈ D. Mệnh đề 1.3. Cho D là một tập lồi đóng khác rỗng. Khi đó (i) Với mọi y ∈ IRn , π ∈ D hai tính chất sau là tương đương: a) π = PD (y), b) y − π ∈ ND (π). (ii) Với mọi y ∈ IRn , hình chiếu PD (y) của y trên D luôn tồn tại và duy nhất. (iii) kPD (x) − PD (y)k ≤ kx − yk, ∀x, y ∈ IRn (tính không giãn), (iv) kPD (x)−PD (y)k2 ≤ hPD (x)−PD (y), x−yi, ∀x, y ∈ IRn (tính đồng bức). 1.2. Hàm lồi Trong phần này ta chỉ xét những hàm f không nhận giá trị −∞. Định nghĩa 1.16. Một hàm số f xác định trên tập lồi D được gọi là (i) lồi trên D nếu f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y), ∀x, y ∈ D, 0 < λ < 1. (ii) lồi chặt nếu f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y), ∀x, y ∈ D, 0 < λ < 1. (iii) lõm (lõm chặt) nếu −f là lồi (lồi chặt). 7 Định lí 1.4. Cho f và g là các hàm lồi trên tập lồi C và D tương ứng. Khi đó các hàm số αf +βg, (∀α, β ≥ 0) và max{f, g} cũng lồi trên C ∩D. Một hàm lồi có thể không liên tục tại một điểm trên biên miền xác định của nó. Tuy nhiên, nó liên tục tại mọi điểm trong của tập đó theo định lý sau: Định lí 1.5. Một hàm lồi xác định trên tập lồi D thì liên tục tại mọi điểm trong của D. Tính chất sau đây đặc trưng cho một hàm lồi khả vi, và thuận lợi để kiểm tra tính lồi của một hàm số. Ký hiệu f 0 (a) hoặc ∇f (a) là đạo hàm của f tại a. Định lí 1.6. Cho f : D → IR là một hàm khả vi trên tập lồi mở D. Điều kiện cần và đủ để f lồi trên D là f (x) + h∇f (x), y − xi ≤ f (y), ∀x, y ∈ D. Nếu f khả vi hai lần thì điều kiện cần và đủ để f lồi trên D là với mọi x ∈ A ma trận Hessian H(x) của f tại x xác định không âm, tức là y T H(x)y ≥ 0, ∀x ∈ D, y ∈ IRn . Như vậy, một dạng toàn phương xT Qx là một hàm lồi khi và chỉ khi Q xác định không âm. Một dạng toàn phương là một hàm lồi chặt khi và chỉ khi ma trận của nó xác định dương. Tính khả vi của một hàm lồi giữ vai trò quan trọng trong các phương pháp tối ưu hóa. Lớp các hàm lồi có những tính chất khả vi rất đẹp mà các lớp hàm khác không có. Giả sử f : IRn → IR ∪ {+∞} là hàm lồi. Ta có các khái niệm sau Định nghĩa 1.17. Cho  > 0. Một véc tơ w ∈ IRn được gọi là một − dưới gradient của f tại x0 ∈ IRn nếu: hw, x − x0 i ≤ f (x) − f (x0 ) + , ∀x ∈ IRn . 8 Tập hợp tất cả các −dưới gradient gọi là − dưới vi phân của hàm f tại x0 , kí hiệu là ∂ f (x0 ) := {w ∈ IRn : hw, x − x0 i ≤ f (x) − f (x0 ) + , ∀x ∈ IRn }. Định nghĩa 1.18. Véctơ w ∈ IRn được gọi là dưới gradient của f tại x0 ∈ IRn nếu: hw, x − x0 i ≤ f (x) − f (x0 ), ∀x ∈ IRn . Tập hợp tất cả các dưới gradient của hàm f tại x0 được gọi là dưới vi phân của f tại x0 , kí hiệu là: ∂f (x0 ) := {w ∈ IRn : hw, x − x0 i ≤ f (x) − f (x0 ), ∀x ∈ IRn }. Hàm f được gọi là khả dưới vi phân tại x0 nếu ∂f (x0 ) 6= ∅. Ví dụ 1.1. Cho D là một tập lồi, khác rỗng của không gian IRn . Xét hàm chỉ trên tập D  0 nếu x ∈ D, δD (x) := +∞ nếu x ∈ / D. Với mọi x0 ∈ D ta có: w ∈ ∂δD (x0 ) ⇔ δD (x) − δD (x0 ) ≥ hw, x − x0 i, ∀x ∈ D ⇔ 0 ≥ hw, x − x0 i, ∀x ∈ D ⇔ w ∈ ND (x0 ). Chứng tỏ ∂δD (x0 ) = ND (x0 ), ∀x0 ∈ D. Cũng có trường hợp tồn tại những điểm x∗ tại đó f không có dưới vi phân, nghĩa là tập ∂f (x∗ ) có thể là một tập rỗng. Tuy nhiên, đối với hàm lồi, ta có định lý sau: Định lí 1.7. Cho f là một hàm lồi (hữu hạn) trên tập lồi D. Lúc đó f có dưới vi phân tại mọi điểm thuộc riD. Từ định lý này suy ra rằng nếu f là một hàm lồi trên toàn không gian IRn thì nó có dưới vi phân tại mọi điểm, vì riIRn = IRn . 9 Định nghĩa 1.19. Ta gọi đạo hàm theo hướng d của một hàm số f (không nhất thiết là lồi) tại điểm x là đại lượng f 0 (x, d) := lim+ λ→0 f (x + λd) − f (x) λ nếu giới hạn này tồn tại. Định lí 1.8. Nếu f là một hàm lồi trên tập lồi D thì với mọi x ∈ D và mọi d sao cho x + d ∈ D, đạo hàm theo hướng d của f tại x luôn tồn tại và nghiệm đúng f 0 (x, d) ≤ f (x + d) − f (x). Ngoài ra với mỗi điểm x cố định, f 0 (x, .) là một hàm lồi trên tập lồi {d : x + d ∈ D}. Từ định lý này dễ dàng suy ra rằng nếu f khả vi thì f 0 (x, d) = h∇f (x), di, ∀d. (1.1) Nói chung một hàm lồi không nhất thiết khả vi tại mọi điểm. Dưới vi phân là một khái niệm mở rộng của đạo hàm trong trường hợp hàm không khả vi. Trong trường hợp ∂f (x∗ ) chỉ gồm duy nhất một điểm thì f khả vi tại x∗ . Trong phần tiếp theo, ta sẽ định nghĩa về  - nghiệm và  - chiếu của một hàm lồi. Định nghĩa 1.20. Cho D ⊆ IRn là tập lồi, f : D → IR là hàm lồi và  ≥ 0. Xét bài toán: min f (x). x∈D (P ) Một điểm x̄ ∈ D được gọi là  - nghiệm của bài toán (P ) nếu: f (x̄) ≤ min f (x) + . x∈D Mệnh đề 1.4. Vectơ x̄ ∈ D là  - nghiệm của bài toán (P ) khi và chỉ khi 0 ∈ ∂ f (x̄). 10 Chứng minh. Giả sử x̄ ∈ D là  - nghiệm của bài toán (P ). Khi đó f (x̄) ≤ f (x) + , ∀x ∈ D. Suy ra h0, x − x̄i ≤ f (x) − f (x̄) + , ∀x ∈ D ⇔ 0 ∈ ∂ (f (x̄)) . Ngược lại, nếu 0 ∈ ∂ (f (x̄)) thì ta có: h0, x − x̄i ≤ f (x) − f (x̄) + , ∀x ∈ D. Chứng tỏ x̄ là − nghiệm của bài toán (P ). Định nghĩa 1.21. Cho D là một tập lồi đóng khác rỗng trong IRn , x ∈ IRn và  ≥ 0 . Một điểm px ∈ D được gọi là  - chiếu của x trên D nếu px là một  - nghiệm của bài toán  1 min kx − yk2 y∈D 2  (Q) nghĩa là: 1 1 kx − px k2 ≤ kx − PD (x)k2 + , 2 2 trong đó PD (x) là hình chiếu của x trên D. Mệnh đề 1.5. Cho D là tập lồi đóng khác rỗng. Khi đó px là  - chiếu của x trên D khi và chỉ khi hx − px , px − yi ≥ −, ∀y ∈ D. Chứng minh. Giả sử px là  − chiếu của x trên D. Ta có   1 1 kx − yk2 + δD (y) min kx − yk2 ⇔ min y∈D 2 2 trong đó δD (y) là hàm chỉ của y trên tập D. Đặt 1 f (y) := kx − yk2 , x ∈ IRn . 2 (1.2) (1.3) 11 Theo Định nghĩa 1.21, px là  − nghiệm của bài toán (1.3). Từ Mệnh đề 1.4 ta được 0 ∈ ∂ [f (px ) + δD (px )] = ∂ f (px ) + ∂ δD (px ). (1.4) Theo Ví dụ 1.1, ∂ δD (px ) = ND (px ) nên từ (1.4) ta có: 0 ∈ {−x + px } + ND (px ). Suy ra (x − px ) ∈ ND (px ) ⇔ hx − px , ω − px i ≤ , ∀ω ∈ D. Ngược lại, giả sử có (1.2). Ta có kx − PD (x)k2 = kx − px k2 + 2hx − px , px − PD (x)i + kpx − PD (x)k2 ≥ kx − px k2 + 2hx − px , px − PD (x)i. Suy ra kx − PD (x)k2 ≥ kx − px k2 − 2. Chứng tỏ px là − chiếu của x trên D. 12 Chương 2 Điều kiện cực tiểu hàm lồi Chương này trình bày một số kiến thức quan trọng phục vụ cho chương 3. Đó là đối ngẫu Lagrange và áp dụng vào giải bài toán tối ưu lồi; các định lý cơ bản như Định lý Karush - Kuhn - Tucker, Định lý Kuhn Tucker. Nội dung của chương chủ yếu được trích dẫn từ tài liệu tham khảo [1]. 2.1. Bài toán quy hoạch lồi 2.1.1. Các khái niệm Cho D ⊆ IRn và f : IRn → IR. Xét bài toán quy hoạch toán học min{f (x) : x ∈ D}. (P ) Bài toán này được hiểu là hãy tìm một điểm x∗ ∈ D sao cho f (x∗ ) ≤ f (x) với mọi x ∈ D. Mỗi điểm x∗ ∈ D được gọi là một phương án chấp nhận được của bài toán (P ). Tập D được gọi là miền (tập) chấp nhận được, f được gọi là hàm mục tiêu của bài toán (P ). Thông thường, tập D được cho như là tập nghiệm của một hệ bất đẳng thức hoặc đẳng thức có dạng D := {x ∈ X : gj (x) ≤ 0, hi (x) = 0, j = 1, ..., m, i = 1, ..., p}, (2.1) trong đó ∅ 6= X ⊆ IRn và gj , hi : IRn → IR (j = 1, ...m, i = 1, ...p). Bài toán (P ) với D cho bởi (2.1) gọi là trơn nếu cả hàm mục tiêu và các ràng buộc đều trơn (khả vi). 13 Bài toán (P ) có rất nhiều ứng dụng trong các lĩnh vực khác nhau. Ví dụ, trong kinh tế nó là bài toán xác định phương án sản xuất sao cho chi phí thấp nhất. Trong ví dụ này, x là phương án sản xuất mà mỗi tọa độ xj của nó là số lượng sản phẩm loại j cần sản xuất, còn f (x) là chi phí ứng với phương án x. Bài toán (P ) trong mô hình này có nghĩa là tìm một phương án sản xuất trong tập hợp các phương án chấp nhận được D sao cho chi phí sản xuất ứng với phương án này là thấp nhất. Định nghĩa 2.1. Điểm x∗ ∈ D được gọi là lời giải tối ưu địa phương của bài toán (P) nếu tồn tại một lân cận U của x∗ sao cho f (x∗ ) ≤ f (x), ∀x ∈ U ∩ D. và x∗ gọi là lời giải tối ưu toàn cục của (P) nếu f (x∗ ) ≤ f (x), ∀x ∈ D. 2.1.2. Sự tồn tại nghiệm tối ưu Xét bài toán tối ưu toàn cục (P ). Có 4 trường hợp tồn tại nghiệm tối ưu của bài toán này • D = ∅ (Không có nghiệm).
• f không bị chặn dưới trên D inf f (x) = −∞ . x∈D • inf f (x) < ∞ nhưng giá trị cực tiểu không đạt được trên D. x∈D • tồn tại x∗ ∈ D sao cho f (x∗ ) = min f (x). x∈D Câu hỏi đặt ra: Làm thế nào để kiểm tra được bài toán (P ) có nghiệm hay không? Câu trả lời là, nói chung điều này là không dễ dàng. Định lí 2.1. Điều kiện cần và đủ để tồn tại nghiệm tối ưu toàn cục của bài toán (P ) là F + (D) := {t ∈ IR : f (x) ≤ t, x ∈ D}, đóng và bị chặn dưới. 14 Chứng minh. Nếu x∗ là nghiệm tối ưu thì F + (D) = [f (x∗ ), +∞] đóng (là phần bù của một tập mở) và bị chặn dưới. Ngược lại, giả sử F + (D) bị chặn dưới. Đặt t∗ = inf F + (D) thì t > −∞. Do F + (D) đóng, t∗ ∈ F + D nên tồn tại x∗ ∈ D sao cho f (x∗ ) = t∗ . Chứng tỏ x∗ là một điểm cực tiểu của f trên D. Định lí 2.2 (Weierstrass). Nếu D là tập compact và f nửa liên tục dưới trên D, thì bài toán (P ) có nghiệm tối ưu. Chứng minh. Đặt α := inf x∈D f (x). Theo định nghĩa có một dãy {xk } ⊂ D sao cho limk→+∞ f (xk ) = α. Do D compact nên có một dãy con hội tụ về x0 ∈ D, không giảm tính tổng quát có thể coi xk → x0 . Vì f nửa liên tục dưới nên α > −∞. Nhưng x0 ∈ D nên theo định nghĩa của α, ta phải có f (x0 ) ≥ α. Vậy f (x0 ) = α. Định lí 2.3. Nếu f nửa liên tục dưới trên D và thỏa mãn điều kiện bức sau f (x) → +∞ khi x ∈ D, kxk → +∞ thì f có điểm cực tiểu trên D. Chứng minh. Đặt D(a) := {x ∈ D : f (x) ≤ f (a)} với a ∈ D. Rõ ràng, D(a) đóng và bị chặn nên f có điểm cực tiểu trên D(a) và điểm đó cũng chính là điểm cực tiểu của f trên D. 2.1.3. Điều kiện tối ưu Định lí 2.4. Giả sử D là tập lồi và f là hàm lồi, khả dưới vi phân trên D. Khi đó x∗ là nghiệm tối ưu của bài toán (P) nếu và chỉ nếu 0 ∈ ∂f (x∗ ) + ND (x∗ ), trong đó ND (x∗ ) ký hiệu nón pháp tuyến của D tại x∗ . Chứng minh. ” ⇐ ” : Giả sử có (2.2). Khi đó tồn tại p∗ sao cho p∗ ∈ ∂f (x∗ ) ∩ (−ND (x∗ )). (2.2) 15 Do p∗ ∈ ∂f (x∗ ) nên hp∗ , x − x∗ i ≤ f (x) − f (x∗ ), ∀x. và vì p∗ ∈ ND (x∗ ) nên hp∗ , x − x∗ i ≥ 0, ∀x ∈ D. Vậy f (x) − f (x∗ ) ≥ 0, ∀x ∈ D. Chứng tỏ x∗ là nghiệm tối ưu của bài toán (P ). ” ⇒ ” : Giả sử x∗ là nghiệm tối ưu. Bằng cách lấy không gian affine của D, ta có thể giả sử D là một tập có số chiều đầy đủ. Do D là tập lồi, intD 6= ∅. Xét hai tập sau E := {(t, x) ∈ IR × IRn : t > f (x) − f (x∗ ), x ∈ D}; G := {0} × D. Cả E và G đều là tập lồi (do D và f lồi). Hơn nữa, G ∩ E = ∅. Áp dụng định lý siêu phẳng tách tồn tại (u0 , u) 6= 0 ∈ IR × IRn sao cho u0 t + uT x ≤ u0 0 + uT y, ∀(t, x) ∈ E, y ∈ D (2.3) Từ (2.3), cho t → +∞, ta thấy u0 ≤ 0. Cũng từ (2.3) nếu u0 = 0 thì hu, x − yi ≤ 0, ∀x, y ∈ D. (2.4) Hiển nhiên, 0 ∈ D và bằng phép tịnh tiến ta có thể giả sử 0 ∈ intD. Theo (2.4) ta có u = 0 (không xảy ra vì u0 = 0). Do đó u0 < 0. Chia cả 2 vế của (2.3) cho −u0 > 0, ta có −t + uT x ≤ uT y, ∀x, y ∈ D. Cho t → f (x) − f (x∗ ), ta được −[f (x) − f (x∗ )] + uT x ≤ uT y, ∀x, y ∈ D. Thay y = x∗ vào (2.5), ta được −[f (x) − f (x∗ )] + uT x ≤ uT x∗ , ∀x ∈ D. (2.5) 16 Do đó f (x∗ ) − f (x) + uT (x − x∗ ) ≤ 0, ∀x ∈ D. (2.6) Nếu x 6∈ C , bằng cách lấy f (x) = ∞ nên từ (2.6) ta cũng nhận được f (x∗ ) − f (x) + uT (x − x∗ ) ≤ 0, ∀x ∈ X. nghĩa là u ∈ ∂f (x∗ ). Mặt khác, thay x = x∗ vào (2.5), ta có uT (y − x∗ ) ≥ 0, ∀y ∈ D. Suy ra −u ∈ ND (x∗ ). Kết hợp với u ∈ ∂f (x∗ ), ta được 0 ∈ ∂f (x∗ ) + ND (x∗ ). Hệ quả 2.1. Với các giả thiết như Định lý 2.4, nếu x∗ ∈ intD là nghiệm tối ưu của bài toán (P ) thì 0 ∈ ∂f (x∗ ). Hơn nữa, nếu f khả vi và D = IRn thì 0 = ∇f (x∗ ). 2.2. Tối ưu có ràng buộc 2.2.1. Đối ngẫu Lagrange Đối ngẫu là một phần quan trọng của bài toán tối ưu. Có rất nhiều kiểu đối ngẫu, nhưng đối ngẫu Lagrange được sử dụng rộng rãi hơn cả. Đối ngẫu Lagrange dựa trên cơ sở hàm Lagrange. Ta xét bài toán min{f (x) : x ∈ X, gj (x) ≤ 0, j = 1, ..., m} (P ) trong đó X ⊆ IRn là tập lồi khác rỗng. Từ bài toán trên, ta định nghĩa bài toán tối ưu khác có dạng max{d(y) : y ∈ Y } (D) trong đó Y ⊆ IRm . Định nghĩa 2.2. Bài toán (D) được gọi là đối ngẫu của bài toán (P ) nếu với mọi điểm chấp nhận được x của (P ) và mọi y chấp nhận được của (D), ta có f (x) ≥ d(y). 17 Bài toán (D) được gọi là đối ngẫu chính xác của bài toán (P ) nếu (D) là bài toán đối ngẫu của (P ) và tồn tại x∗ ∈ (P ), y ∗ ∈ (D) sao cho f (x∗ ) ≤ d(y ∗ ). Từ Định nghĩa 2.2 ta thấy rằng, nếu bài toán (D) là đối ngẫu chính xác của bài toán (P ) thì f (x∗ ) = d(y ∗ ) và hiển nhiên (P ) cũng là đối ngẫu chính xác của (D). Xét bài toán (P ), ta định nghĩa hàm Lagrange L(x, y) := f (x) + m X yj gj (x). j=1 Lấy hàm mục tiêu của bài toán đối ngẫu là d(y) := inf L(x, y). x∈X (LD) m . Khi đó bài toán đối ngẫu trở thành và miền ràng buộc của (LD) bằng IR+ sup d(y) := sup inf L(x, y). y≥0 y≥0 x∈X Định lí 2.5. Bài toán (LD) là đối ngẫu của bài toán (P ). Chứng minh. Ta có d(y) = inf L(x, y) ≤ f (x) + x∈X m X yj gj (x) ≤ f (x), ∀x ∈ X, ∀y ∈ Y. j=1 Chứng tỏ (LD) là đối ngẫu của bài toán (P ). Nhận xét 2.1. Nhìn chung, một cặp đối ngẫu chưa chắc đã là đối ngẫu chính xác như ví dụ sau đây sẽ chỉ ra. Ví dụ 2.1. Xét bài toán min{f (x) = −x2 , x ∈ X = [0, 2], x − 1 ≤ 0}, 18 Ta thấy f (1) = min f = −1. Hàm Lagrange của bài toán là L(x, y) = −x2 + y(x − 1), y ≥ 0, x ∈ X = [0, 2]. Ta thấy max d(y) = 0. y≥0 Vậy cặp đối ngẫu là không chính xác. Vậy cần thêm điều kiện gì để hai bài toán (P ) và (LD) là cặp đối ngẫu chính xác? Ta có định lý sau: Định lí 2.6 (Đối ngẫu chính xác). Giả sử (i) (P ) có một lời giải tối ưu, (ii) Các hàm f và gj , (j = 1, ..., m) lồi và liên tục trên X . (iii) Điều kiện Slater thỏa mãn, nghĩa là có x0 sao cho gj (x0 ) < 0 với mọi j. Khi đó (P ) và (LD) là cặp đối ngẫu chính xác. Chứng minh. Giả sử g(x) := (g1 (x), . . . , gm (x))T . Lấy A := {(t, z) ∈ IR × IRn : t > f (x), z ≥ g(x), x ∈ X}. Do f và gj (j = 1, ..., m) lồi nên tập A là lồi. Giả sử x∗ là nghiệm tối ưu của bài toán (P ) thì (f (x∗ ), 0) 6∈ A. Theo định lý tách tồn tại (α, y) 6= 0 thuộc IR × IRn sao cho: αt + y T z ≥ αf (x∗ ), ∀(t, z) ∈ A. (2.7)