Tài liệu Một phương pháp qui hoạch lồi giải bài toán chấp nhận lồi

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC VŨ THỊ NGỌC BÍCH MỘT PHƯƠNG PHÁP QUI HOẠCH LỒI GIẢI BÀI TOÁN CHẤP NHẬN LỒI LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2018 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC VŨ THỊ NGỌC BÍCH MỘT PHƯƠNG PHÁP QUI HOẠCH LỒI GIẢI BÀI TOÁN CHẤP NHẬN LỒI Chuyên ngành: Toán ứng dụng Mã số: 84 60 112 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 - 2018 i Mục lục Mở đầu 1 Chương 1 Bài toán qui hoạch lồi 3 1.1 1.2 Tập lồi, hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.1 Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.2 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Bài toán qui hoạch lồi . . . . . . . . . . . . . . . . . . . . . . . . . 16 Chương 2 Một phương pháp qui hoạch lồi giải bài toán chấp nhận lồi 2.1 2.2 24 Bài toán chấp nhận lồi và ví dụ . . . . . . . . . . . . . . . . . . . . 24 2.1.1 Bài toán chấp nhận lồi . . . . . . . . . . . . . . . . . . . . 24 2.1.2 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 Một phương pháp qui hoạch lồi giải bài toán chấp nhận lồi . . . . . 25 2.2.1 Tóm tắt hai phương pháp cơ bản: chiếu lần lượt và chiếu song song . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2.2 Thuật toán đạo hàm giải bài toán qui hoạch lồi . . . . . . . . 29 2.2.3 Phương pháp chuyển về bài toán qui hoạch lồi . . . . . . . . 32 Kết luận 41 Tài liệu tham khảo 42 1 Mở đầu Tối ưu hóa được khởi nguồn như một ngành của Toán học, có rất nhiều ứng dụng trong quy hoạch tài nguyên, thiết kế chế tạo máy, điều khiển tự động, quản trị kinh doanh... trong việc tạo nên các hệ hỗ trợ ra quyết định trong quản lý và phát triển các hệ thống lớn. Chính vì vậy, các lĩnh vực của tối ưu hóa ngày càng trở nên đa dạng mang nhiều tên gọi khác nhau như Quy hoạch toán học, Điều khiển tối ưu, Vận trù học, Lý thuyết trò chơi... Hiện nay môn học Tối ưu hóa được đưa vào giảng dạy trong nhiều chương trình đào tạo đại học cho các ngành khoa học cơ bản. Một trong những bài toán quan trọng của Tối ưu hóa là bài toán qui hoạch lồi. Nhiều bài toán quan trọng trong lĩnh vực toán học hoặc trong thực tế có thể chuyển về bài toán qui hoạch lồi (tìm cực tiểu của một hàm lồi trên một tập lồi). Đối với lớp bài toán này có nhiều phương pháp giải hiệu quả, ví dụ như phương pháp đạo hàm, phương pháp dưới đạo hàm, phương pháp điểm trong,. . . Bài toán chấp nhận lồi là bài toán tìm một điểm chung của một số hữu hạn hoặc vô hạn các tập lồi. Bài toán này rất quan trọng vì nhiều bài toán trong toán học cũng như trong các lĩnh vực thực tế khác đều có thể chuyển về bài toán chấp nhận lồi. Ví dụ như bài toán giải hệ phương trình, bài toán tìm nghiệm chung của các bài toán tối ưu, bất đẳng thức biến phân,. . . Chính vì vậy chúng tôi chọn đề tài: "Một phương pháp qui hoạch lồi giải bài toán chấp nhận lồi". Luận văn nghiên cứu về bài toán chấp nhận lồi và giới thiệu một vài phương pháp giải bài toán này, đặc biệt đi sâu vào phương pháp chuyển bài toán chấp nhận lồi về qui hoạch lồi. Nội dung luận văn gồm hai chương: Chương 1. "Bài toán qui hoạch lồi” giới thiệu các kiến thức cơ bản nhất về giải 2 tích lồi và bài toán qui hoạch lồi. Chương 2. "Một phương pháp qui hoạch lồi giải bài toán chấp nhận lồi" giới thiệu phương pháp chiếu lần lượt và chiếu song song, thuật toán đạo hàm để giải bài toán qui hoạch lồi. Cuối chương, đề cập đến một phương pháp giải bài toán chấp nhận lồi. Trong quá trình học tập và làm luận văn, từ bài giảng của các giáo sư, phó giáo sư công tác tại Viện Toán học, Viện Công nghệ Thông tin - Viện Hàn lâm Khoa học và Công nghệ Việt Nam, Đại học Thăng Long, các thầy cô trong trường Đại học Khoa học - Đại học Thái Nguyên, tôi đã trau dồi thêm rất nhiều kiến thức phục vụ cho việc nghiên cứu và công tác của bản thân. Tôi xin gửi lời cảm ơn chân thành đến các thầy cô. Tôi xin chân thành cảm ơ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 đã quan tâm và giúp đỡ tôi trong suốt thời gian học tập tại trường. Cuối cùng tôi xin gửi lời cảm ơn tới gia đình, bạn bè đã luôn động viên, giúp đỡ và tạo điều kiện tốt nhất cho tôi trong quá trình học tập, nghiên cứu và làm luận văn. Thái Nguyên, tháng 05 năm 2018 Học viên Vũ Thị Ngọc Bích 3 Chương 1 Bài toán qui hoạch lồi Chương này trình bày một số kiến thức của giải tích lồi như tập lồi, hàm lồi, bài toán qui hoạch lồi, đây là những kiến thức nền tảng, cần thiết phục vụ cho việc nghiên cứu và giải quyết đề tài. Nội dung của chương được tham khảo từ các tài liệu [1], [2] và [3]. 1.1 1.1.1 Tập lồi, hàm lồi Tập lồi Định nghĩa 1.1. Cho hai điểm a, b trong không gian Rn . Đường thẳng đi qua hai điểm a và b là tập tất cả các điểm x trong Rn có dạng x = λa + (1 − λ)b, λ ∈ R. Đoạn thẳng nối hai điểm a, b là tập hợp các điểm có dạng x = λa + (1 − λ)b, λ ∈ [0, 1]. Định nghĩa 1.2. Một tập C ⊆ Rn được gọi là một tập lồi nếu C chứa mọi đoạn thẳng đi qua hai điểm bất kỳ của nó. Tức là C lồi khi và chỉ khi ∀x, y ∈ C, ∀λ ∈ [0, 1] ⇒ λx + (1 − λ)y ∈ C. Ta nói x là tổ hợp lồi các điểm (vectơ) x1 , x2 , . . . , xk nếu x= k X j=1 j λj x , λj > 0, ∀j = 1, . . . , k, k X j=1 λj = 1. 4 Định nghĩa 1.3. 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, ∀λ ∈ Rn ⇒ λx + (1 − λ)y ∈ D. Mệnh đề 1.1. Tập hợp C 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à: C lồi khi và chỉ khi ∀k ∈ N, ∀λ1 , . . . , λk > 0 : k X 1 k λj = 1, ∀x , . . . , x ∈ C ⇒ k X λj xj ∈ C. j=1 j=1 Chứng minh. Điều kiện đủ là hiển nhiên từ định nghĩa. Ta chứng minh điều kiện cần bằng quy nạp theo số điểm. Với k = 2, điều cần chứng minh suy ra ngay từ định nghĩa của tập lồi và tổ hợp lồi. Giả sử mệnh đề đúng với k − 1 điểm. Ta cần chứng minh đúng với k điểm. Giả sử x là tổ hợp lồi của k điểm x1 , . . . , xk ∈ C. Tức là x= k X j λj x , λj > 0, ∀j = 1, . . . , k, k X λj = 1. j=1 j=1 Đặt k−1 X ξ= λj . j=1 Khi đó 0 < ξ < 1 và x= k−1 X j k λj x + λk x = ξ j=1 j=1 Do k−1 X λj j=1 và k−1 X λj ξ ξ xj + λk xk . =1 λj > 0 với mọi ∀j = 1, . . . , k − 1 nên theo giả thiết quy nạp, điểm ξ y := k−1 X λj j=1 ξ xj ∈ C. 5 Ta có x = ξy + λk xk . Do ξ > 0, λk > 0 và ξ + λk = k X λj = 1 j=1 nên x là một tổ hợp lồi của hai điểm y và xk đều thuộc C. Vậy x ∈ C. Mệnh đề 1.2. Nếu A, B là các tập lồi trong Rn , C là lồi trong Rm , thì các tập sau là lồi : A ∩ B := {x | x ∈ A, x ∈ B}; αA + βB := {x | x = αa + βb, a ∈ A, b ∈ B, α, β ∈ R}; A × C := {x ∈ Rn+m | x = (a, c), a ∈ A, c ∈ C}. Mệnh đề 1.3. D 6= ∅ là tập affine khi và chỉ khi nó có dạng D = M + a với M là không gian con của Rn và a ∈ Rn . 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. Định nghĩa 1.4. Siêu phẳng trong Rn là một tổ hợp các điểm có dạng {x ∈ Rn | aT x = α}, trong đó a ∈ Rn là một vectơ pháp tuyến của siêu phẳng. Một siêu phẳng sẽ chia không gian thành hai nửa không gian. Định nghĩa 1.5. Nửa không gian là một tập hợp có dạng {x | aT x ≥ α}, trong đó a 6= 0 và α ∈ R. Đây là nửa không gian đóng. Tập {x | aT x > α} là nửa không gian mở. 6 Như vậy một siêu phẳng chia không gian thành hai nửa không gian, mỗi nửa không gian ở về một phía của siêu phẳng. Nếu hai nửa không gian này là đóng thì phần chung của chúng chính là siêu phẳng đó. Định nghĩa 1.6. Một tập hợp S ⊂ Rn được gọi là một đơn hình có thứ nguyên bằng k (hoặc nói ngắn gọn là k-đơn hình) nếu S là tổ hợp lồi của k + 1 vectơ độc lập affine. Các vectơ này gọi là đỉnh của đơn hình. Ví dụ, một tam giác trong không gian 3 chiều là 2-đơn hình. Tập hợp ( ) k X Sk := x ∈ Rk | x ≥ 0, xj ≤ 1 j=1 được gọi là đơn hình chuẩn tắc trong Rk . Định nghĩa 1.7. 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. Như vậy, theo định nghĩa, một tập lồi đa diện là tập nghiệm của một hệ hữu hạn các bất phương trình tuyến tính. Dạng tường minh của một tập lồi đa diện được cho như sau  D := {x ∈ Rn | aj , x ≤ bj , j = 1, . . . , m}. Hoặc nếu ta kí hiệu A là ma trận có m hàng là các vectơ aj , j = 1, . . . , m và vectơ bT = (b1 , . . . , bm ) thì hệ trên được viết là D = {x ∈ Rn | Ax ≤ b}. Chú ý rằng do một phương trình ha, xi = b có thể viết lại một cách tương đương dưới dạng hai bất phương trình ha, xi ≤ b, h−a, xi ≤ b nên tập nghiệm của một hệ hữu hạn các phương trình và bất phương trình là một tập lồi đa diện. 7 Định nghĩa 1.8. 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.9. 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 sao cho a + λ(x − a) ∈ D. Tập các điểm trong tương đối của D ký hiệu là riD. Định nghĩa 1.10. Một tập D được gọi là nón nếu ∀λ > 0, ∀x ∈ D ⇒ λx ∈ D. Một nón 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. Hình 1.1: Nón lồi và nón không lồi Định nghĩa 1.11. Cho D ⊆ Rn là một tập lồi và x0 ∈ D.  (i) Tập ND (x0 ) := {ω ∈ Rn : ω, x − x0 ≤ 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 ) := {ω ∈ Rn : ω, x − x0 ≤ , ∀x ∈ D} được gọi là nón pháp tuyến  của D tại x0 . 8 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. Định nghĩa 1.12. 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 sup hv, xi < λ < inf hv, yi . x∈A y∈B Định lí 1.1. (Định lý tách 1). Cho C và D là các tập lồi khác rỗng trong Rn sao cho C ∩ D = ∅. Khi đó có một siêu phẳng tách C và D. Định lí 1.2. (Định lý tách 2). Cho C và D là các tập lồi khác rỗng trong Rn sao cho C ∩ D = ∅. Giả sử có ít nhất một tập là compact. Khi đó C và D có thể tách mạnh được. Bổ đề 1.1. (Bổ đề Farkas). Cho a ∈ Rn 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 Rm 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. 9 Hình 1.2: (a) Hai tập lồi C và D được tách hẳn bởi một siêu phẳng; (b) Hai tập lồi C và D được tách bởi siêu phẳng {x ∈ R2 | x2 = 0} nhưng không tách hẳn được; Hai tập C và D giao nhau bằng rỗng nhưng không thể tách được vì D không phải tập lồi Định nghĩa 1.13. 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 của y trên D và ký hiệu là π = PD (y). Theo định nghĩa, ta thấy hình chiếu PD (y) của y trên D là nghiệm của bài toán tối ưu  min x∈D  1 2 kx − yk : 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 kx − yk2 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.4. Cho D là một tập lồi đóng khác rỗng. Khi đó (i) Với mọi y ∈ Rn , π ∈ D hai tính chất sau là tương đương a) π = PD (y); b) y − π ∈ ND (π); (ii) Với mọi y ∈ Rn , hình chiếu PD (y) của y trên D luôn tồn tại và duy nhất; 10 (iii) kPD (x) − PD (y)k ≤ kx − yk, ∀x, y ∈ Rn (tính không giãn); (iv) kPD (x) − PD (y)k2 ≤ hPD (x) − PD (y), x − yi , ∀x, y ∈ Rn (tính đồng bức). 1.1.2 Hàm lồi Cho C ⊆ Rn là tập lồi và f : C → R. Ta sẽ ký hiệu domf := {x ∈ C | f (x) < +∞}; tập domf được gọi là miền hữu dụng của f . Tập epif := {(x, µ) ∈ C × R | f (x) ≤ µ} được gọi là đồ thị của hàm f . Bằng cách cho f (x) = +∞ nếu x 6∈ C, ta có thể coi f được xác định trên toàn không gian và hiển nhiên là domf = {x ∈ Rn | f (x) < +∞}; epif = {(x, µ) ∈ Rn × R | f (x) ≤ µ}. Do sẽ làm việc với hàm số nhận cả giá trị −∞ và +∞, nên như thường lệ, ta có quy ước sau: Nếu λ = 0, thì λf (x) = 0 với mọi x. Định nghĩa 1.14. Cho ∅ 6= C ⊆ Rn lồi và f : C → R. Ta nói f là hàm lồi trên C nếu epif là một tập lồi trong Rn+1 . Ta chủ yếu làm việc với hàm f : Rn → R ∪ {+∞}. Trong trường hợp này, dễ thấy rằng định nghĩa trên tương đương với f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y), ∀x, y ∈ C, ∀λ ∈ (0, 1). Hàm f : Rn → R ∪ {+∞} được gọi là lồi chặt trên C nếu f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y), x 6= y, ∀x, y ∈ C, ∀λ ∈ (0, 1). 11 Hình 1.3: Hàm lồi Định nghĩa 1.15. Một hàm f được gọi là chính thường nếu domf 6= ∅ và f (x) > −∞ với mọi x. Hàm f được gọi là đóng nếu epif là một tập đóng trong Rn+1 . Ví dụ 1.1. Cho f (x) := aT x + α, trong đó a ∈ Rn , α ∈ R. Dễ kiểm tra được f là một hàm vừa lồi, vừa lõm trên toàn không gian. Khi α = 0 thì hàm này được gọi là hàm tuyến tính. Ví dụ 1.2. Cho C 6= ∅ là một tập lồi. Đặt   0 δC (x) :=  +∞ nếu x ∈ C nếu x 6∈ C. Ta nói δC là hàm chỉ của C. Do C lồi, nên δC là một hàm lồi. Ví dụ 1.3. Cho C lồi đóng, hàm khoảng cách đến tập C được định nghĩa bởi dC (x) := min kx − yk y∈C là một hàm lồi. 12 Mệnh đề 1.5. Một hàm f : C → R là lồi trên C khi và chỉ khi ∀x, y ∈ C, ∀α > f (x), ∀β > f (y), ∀λ ∈ [0, 1] ⇒ f (λx + (1 − λ)y) ≤ λα + (1 − λ)β. Chứng minh. Giả sử f lồi. Chọn x, y, α, β như đã nêu trong mệnh đề. Chọn α0 ∈ (f (x), α) và β 0 ∈ (f (y), β). Vậy (x, α0 ) và (y, β 0 ) thuộc epif . Do epif lồi, nên ((1 − λ)x + λy, (1 − λ)α0 + λβ 0 ) ∈ epif. Do đó f ((1 − λ)x + λy) ≤ (1 − λ)α0 + λβ 0 ≤ (1 − λ)α + λβ. Ngược lại, chọn (x, µ) và (y, v) thuộc epif và λ ∈ (0, 1). Khi đó ∀ > 0, ta có f (x) < µ + , f (y) < v + . Do đó f ((1 − λ)α0 + λβ 0 ) < (1 − λ)(µ + ) + λ(v + ) = (1 − λ)µ + λv + . Điều này đúng với mọi  > 0 và cho  → 0 ta được f ((1 − λ)α0 + λβ 0 ) < (1 − λ)µ + λv. Chứng tỏ (1 − λ)(x, µ) + λ(y, v) ∈ epif. Vậy f lồi. Mệnh đề 1.6. Giả sử f là một hàm lồi không chính thường trên Rn và f 6≡ +∞. Khi đó f (x) = −∞, ∀x ∈ ri(domf ). Chứng minh. Theo định nghĩa hàm chính thường, nếu domf 6= ∅, thì tồn tại một x0 sao cho f (x0 ) = −∞. Giả sử x ∈ ri(domf ). Theo định nghĩa của điểm trong tương đối, tồn tại y ∈ domf thỏa mãn x = λy + (1 − λ)x0 với λ ∈ (0, 1). Do đó f lồi và f (y) < +∞, nên f (x) ≤ λf (y) + (1 − λ)f (x0 ) = −∞. 13 Mệnh đề 1.7. Nếu f là một hàm lồi trên Rn thì các tập mức Lf (α) := {x | f (x) ≤ α}, lf (α) := {x | f (x) < α} là lồi với mọi α ∈ R. Chứng minh. Trường hợp α = +∞ hoặc −∞ là hiển nhiên. Lấy x, y ∈ lf (α), tức là f (x) < α, f (y) < α. Do f lồi, theo Mệnh đề 1.3 với mọi α ∈ (0, 1), ta có f (λx + (1 − λ)y) < λα + (1 − λ)α = α. Vậy λx + (1 − λ)y ∈ lf (α). Tập Lf (α) = ∩µ>α lf (µ), nên nó là tập lồi. Định nghĩa 1.16. Một hàm f : Rn → R được gọi là nửa liên tục dưới, đối với E, tại một điểm x, nếu như với mọi dãy {xk } ⊂ E, xk → x ta có lim inf f (xk ) ≥ f (x). Hàm f được gọi là nửa liên tục trên, đối với E, tại x nếu −f nửa liên tục dưới đối với E, tại x. Hay là với mọi dãy {xk } ⊂ E, xk → x thì lim sup f (xk ) ≤ f (x). Hàm f được gọi là liên tục đối với E tại x nếu như nó vừa nửa liên tục trên và nửa liên tục dưới, đối với E, tại x. Cho hai hàm f và g xác định trên Rn , ta nói g là bao đóng của f , nếu epig = epif . Hàm f được gọi là đóng nếu epif = epif . Bao đóng của f được ký hiệu là f . Mệnh đề 1.8. Với mọi hàm f : Rn → R ∪ {+∞} các điều kiện sau là tương đương: i) Trên đồ thị của f là một tập đóng trên Rn+1 , nói cách khác f = f ; ii) Với mọi số thực α, tập mức dưới Lα (f ) := {x | f (x) ≤ α} là một tập đóng; iii) f nửa liên tục dưới trên Rn . 14 Chứng minh. (i)⇒(ii). Giả sử xj → x, f (xj ) ≤ α. Khi đó (xj , α) ∈ epif . Do epif đóng, nên (x, α) ∈ epif . Vậy x ∈ Lf (α). (ii)⇒(iii). Giả sử xj → x. Nếu lim inf f (xj ) < f (x), khi đó tồn tại α < f (x) sao cho f (xj ) ≤ α với mọi j đủ lớn. Vậy xj ∈ Lf (α) với mọi j đủ lớn. Do xj → x và Lf (α) đóng, nên x ∈ Lf (α). Tức là f (x) < α. Mâu thuẫn với điều ta giả sử là α < f (x). (iii)⇒(i). Giả sử (xj , µj ) ∈ epif và (xj , µj ) → (x, µ). Khi đó f (xj ) ≤ µj với mọi j. Do (iii), suy ra lim inf f (xj ) ≥ f (x). Vậy µ ≥ f (x). Suy ra (x, µ) ∈ epif , và do đó epif là tập đóng. Mệnh đề 1.9. Giả sử f là một hàm lồi chính thường trên Rn . Khi đó f liên tục tại mọi điểm x ∈ int(domf ). Chứng minh. Do f lồi, nên domf và int(domf ) là các tập lồi. Khi đó có một đơn hình n-chiều S ⊂ int(domf ). Giả sử ν 1 , . . . , ν n+1 là các đỉnh của đơn hình S. Với mọi x ∈ S, ta có x= n+1 X j=1 j λj ν , λj ≥ 0, n+1 X λj = 1. j=1 Do f lồi nên f (x) ≤ max{f (ν j ) | j = 1, . . . , n + 1}. Nhưng do phần trong của đơn hình S khác rỗng, nên f bị chặn trên trong một lân cận của một điểm x0 ∈ intS và do đó theo mệnh đề trên, f liên tục trên tập int(domf ). Mệnh đề 1.10. Cho f là một hàm lồi chính thường trên Rn và D ⊆ domf là một tập lồi đa diện. Khi đó f nửa liên tục trên, đối với tập D tại mọi điểm của D. Chứng minh. Xét x ∈ D. Bằng phép tịnh tiến (nếu cần), có thể giả thiết x = 0. Giả sử dãy {xk } ∈ D hội tụ đến x = 0. Gọi G là họ gồm 2n -đơn hình n-chiều. Mỗi đơn hình trong họ này đều có một đỉnh là 0 và n đỉnh còn lại là các điểm thuộc tập hợp {e1 , . . . , en , −e1 , . . . , −en }, trong đó ei là vectơ đơn vị thứ i (i = 1, . . . , n). Do 15 xk → 0, nên tồn tại một đơn hình S ∈ G sao cho xk ∈ S với vô hạn k. Để đơn giản, ta ký hiệu luôn dãy vô hạn này là {xk }. Gọi D1 = D ∩ S. Do D là tập đa diện lồi, nên D1 là một đa diện lồi bị chặn. Ký hiệu tập đỉnh của D1 là V1 . Khi đó mọi xk là tổ hợp lồi của 0 và các điểm của V1 . Tức là ! xk = 1− X λk (ν) 0 + Mặt khác do f lồi, nên P λk (ν)ν, ν∈V1 ν∈V1 trong đó λk (ν) ≥ 0 và X λk (ν) ≤ 1. Do xk → 0, nên λk (ν) → 0 với mọi ν ∈ V1 . ν∈V1 ! f (xk ) ≤ 1− X λk (ν) f (0) + ν∈V1 X λk (ν)f (ν). ν∈V1 Chú ý là, do ν ∈ V1 ⊂ D ⊂ domf , nên f (ν) < ∞. Từ đây và bất đẳng thức trên, cho k → +∞, ta suy ra lim sup f (xk ) ≤ f (0). k→∞ Vậy f nửa liên tục trên tại 0 ∈ D. Định lí 1.3. 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. Ký hiệu f 0 (a) hoặc ∇f (a) là đạo hàm của f tại a. Định lí 1.4. Cho f : D → R 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à ∀x ∈ A ma trận Hessian H(x) của f tại x nửa xác định dương, tức là y T H(x)y ≥ 0, ∀x ∈ D, y ∈ Rn . 1 Ví dụ 1.4. f (x) = xT Qx, trong đó Q là ma trận đối xứng nửa xác định dương. 2 16 1.2 Bài toán qui hoạch lồi Cho D ⊆ Rn và f : Rn → R. Xét bài toán qui hoạch toán học: min{f (x) | x ∈ D}, (P ) trong đó D là tập lồi trong Rn và f là hàm lồi xác định trên D. Bài toán trên được hiểu là tìm một điểm x∗ ∈ D sao cho f (x∗ ) ≤ f (x) với mọi x thuộc 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 ). Bài toán (P ) được gọi là qui hoạch lồi nếu D là một tập lồi và f là một hàm lồi trên D. 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}, (1.1) trong đó ∅ 6= X ⊆ Rn và gj , hi : Rn → R (j = 1, . . . , m, i = 1, . . . , p). Bài toán (P ) với D cho bởi (1.1) gọi là trơn nếu cả hàm mục tiêu và các ràng buộc trơn (khả vi). 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 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 1.17. Đ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. 17 Định lí 1.5. Cho (P ) là một qui hoạch lồi. Khi đó mọi nghiệm tối ưu địa phương đều là tối ưu toàn cục. Hơn nữa tập nghiệm tối ưu (toàn cục) là một tập lồi. Nếu f lồi chặt thì (P ) có nhiều nhất một nghiệm. Tiếp theo ta xét sự tồn tại nghiệm tối ưu của bài toán qui hoạch lồi. 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í 1.6. Đ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 ∈ R : f (x) ≤ t, x ∈ D} đóng và bị chặn dưới. 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 nghiệm cực tiểu của f trên D. Định lí 1.7. (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 f (x). Theo định nghĩa có một dãy {xk } ⊂ D sao cho x∈D k lim f (x ) = α. k→+∞