Luận văn Thạc sĩ Toán học: Một số định lý tồn tại nghiệm trong quy hoạch toàn phương

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:42

Thêm vào BST

Báo xấu

44
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề tài luận văn đề cập tới các định lý tồn tại nghiệm của các dạng khác nhau của bài toán quy hoạch toàn phương lồi hoặc không lồi và giới thiệu một kết quả tổng quát mới, nêu ra trong tài liệu tham khảo về sự tồn tại nghiệm của bài toán quy hoạch toàn phương trong không gian Hilbert. Mời các bạn tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Một số định lý tồn tại nghiệm trong quy hoạch toàn phương

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN HỮU SƠN MỘT SỐ ĐỊNH LÝ TỒN TẠI NGHIỆM TRONG QUY HOẠCH TOÀN PHƯƠNG LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2017
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN HỮU SƠN MỘT SỐ ĐỊNH LÝ TỒN TẠI NGHIỆM TRONG QUY HOẠCH TOÀN PHƯƠNG 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.TS. TRẦN VŨ THIỆU Thái Nguyên - 2017
i Mục lục Lời cảm ơn ii Bảng ký hiệu 1 Mở đầu 2 1 Bài toán quy hoạch toàn phương trong Rn 4 1.1 Định lý cơ bản của quy hoạch tuyến tính . . . . . . . . . . . . 4 1.2 Định lý Frank-Wolfe của quy hoạch toàn phương . . . . . . . 6 1.3 Mở rộng định lý Frank - Wolfe . . . . . . . . . . . . . . . . . . 12 1.3.1 Quy hoạch toàn phương với ràng buộc toàn phương . . 13 1.4 Quy hoạch đa thức lồi . . . . . . . . . . . . . . . . . . . . . . 15 2 Quy hoạch toàn phương trong không gian Hilbert 17 2.1 Giả thiết cơ bản và các bổ đề phụ trợ . . . . . . . . . . . . . . 17 2.2 Định lý kiểu Frank - Wolfe thứ nhất . . . . . . . . . . . . . . 21 2.3 Trường hợp một ràng buộc . . . . . . . . . . . . . . . . . . . . 29 2.4 Định lý kiểu Frank - Wolfe thứ hai . . . . . . . . . . . . . . . 33 Kết luận 37 Tài liệu tham khảo chính 38
ii Lời cảm ơn Luận văn thạc sĩ chuyên ngành Toán ứng dụng với đề tài “MỘT SỐ ĐỊNH LÍ TỒN TẠI NGHIỆM TRONG QUY HOẠCH TOÀN PHƯƠNG” là kết quả của quá trình cố gắng không ngừng của bản thân và được sự giúp đỡ, động viên khích lệ của các thầy cô, bạn bè đồng nghiệp và người thân. Qua trang viết này tôi xin gửi lời cảm ơn tới những người đã giúp đỡ tôi trong thời gian học tập - nghiên cứu khoa học vừa qua. Tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy tôi GS.TS. Trần Vũ Thiệu, người đã trực tiếp hướng dẫn luận văn, đã tận tình chỉ bảo và hướng dẫn tôi tìm ra hướng nghiên cứu, tìm kiếm tài liệu, giải quyết vấn đề... nhờ đó tôi mới có thể hoàn thành luận văn cao học của mình. Từ tận đáy lòng, tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc nhất tới Thầy của tôi và tôi sẽ cố gắng hơn nữa để xứng đáng với công lao của Thầy. Tôi xin chân thành cảm ơn Ban giám hiệu, phòng Đào tạo và các thầy cô 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 muốn bày tỏ lòng biết ơn sâu sắc tới những người thân trong gia đình, đặc biệt là bố mẹ. Những người luôn động viên, chia sẽ mọi khó khăn cùng tôi trong suốt thời gian tôi theo học thạc sĩ tại trường Đại học Khoa học - Đại học Thái Nguyên. Thái Nguyên, ngày 20 tháng 5 năm 2017 Tác giả luận văn Nguyễn Hữu Sơn
1 Bảng ký hiệu R tập số thực R+ tập số thực không âm R ∪ {±∞} tập số thực mở rộng H không gian Hilbert l2 không gian các dãy số vô hạn kxk chuẩn của véc-tơ x ∈ H |x| giá trị tuyệt đối của x ∈ R {xn } hay {xk } dãy điểm trong H xk * x0 xk hội tụ yếu (hội tụ theo tích vô hướng) tới x0 xk → x0 xk hội tụ mạnh (hội tụ theo chuẩn) tới x0 hx, yi tích vô hướng của hai véc-tơ x, y ∈ H [x, y] đoạn thẳng nối x và y x≤y véc-tơ x nhỏ hơn hay bằng véc-tơ y (xi ≤ yi , ∀i = 1, ..., n) x≥y véc-tơ x lớn hơn hay bằng véc-tơ y (xi ≥ yi , ∀i = 1, ..., n) conv{x1 , ..., xk } bao lồi của các điểm x1 , ..., xk dC (x) khoảng cách từ điểm x tới tập C A+B tổng véc-tơ của hai tập A và B A−B hiệu véc-tơ của hai tập A và B A∪B hợp của hai tập A và B A∩B giao của hai tập A và B A×B tích Đề các của hai tập A và B A⊂B A là tập con của B (mọi phần tử của A là phần tử của B) A⊆B A là tập con (có thể bằng) của B 0+ F nón lùi xa của tập lồi F intS phần trong của S(= intH S)
2 Mở đầu Khi xét bài toán tối ưu min{f (x) : x ∈ D} ta thường đặt ra câu hỏi: Với những điều kiện nào của hàm hàm mục tiêu f và tập ràng buộc D thì bài toán có nghiệm tối ưu? Trong quy hoạch tuyến tính ta đã biết sự kiện quen thuộc sau: một hàm tuyến tính bị chặn dưới trên tập lồi đa diện D 6= ∅ phải đạt cực tiểu trên D. Tính chất này được xem như định lý cơ bản của quy hoạch tuyến tính. Frank - Wolfe [5] đã chỉ ra rằng nếu một hàm toàn phương (bất kể hàm đó lồi hay không) mà bị chặn dưới trên tập lồi đa diện D 6= ∅ thì hàm đó chắc chắn đạt cực tiểu trên D. Kết quả này được biết với tên gọi định lý Frank - Wolfe trong quy hoạch toàn phương và định lý này là một mở rộng của định lý cơ bản trong quy hoạch tuyến tính. Tiếp đó nhiều tác giả khác đã mở rộng định lý Frank - Wolfe cho các lớp hàm mục tiêu khác và tập ràng buộc D có thể khác tập lồi đa diện. Đề tài luận văn đề cập tới các định lý tồn tại nghiệm của các dạng khác nhau của bài toán quy hoạch toàn phương lồi hoặc không lồi và giới thiệu một kết quả tổng quát mới, nêu ra trong tài liệu tham khảo [4] về sự tồn tại nghiệm của bài toán quy hoạch toàn phương trong không gian Hilbert. Để hiểu rõ các dạng bài toán quy hoạch toàn phương và các định lý tồn tại nghiệm sẽ trình bày, luận văn nhắc lại một số khái niệm cần thiết về tập lồi, hàm toàn phương, dạng thức Legendre, toán tử compact trong không gian Hilbert và các kết quả về sự tồn tại nghiệm của các bài toán quy hoạch toàn phương trong Rn Các kiến thức và kết quả cơ bản này chủ yếu được trình bày ở chương 1 của luận văn. Nội dung tiếp theo của luận văn là giới thiệu kết quả nghiên cứu mới [4] về sự tồn tại nghiệm của bài toán quy hoạch toàn phương không lồi trong không gian Hilbert. Các định lý kiểu Frank - Wolfe thứ nhất và thứ hai và các hệ quả trong các trường hợp riêng. Những nội dung này sẽ được trình bày chi tiết ở chương 2 của luận văn.
3 Luận văn được viết dựa chủ yếu trên trên các tài liệu tham khảo [1] − [8] hiện có và gồm hai chương. Chương 1 "Bài toán quy hoạch toàn phương trong Rn " trình bày các kết quả về sự tồn tại nghiệm của bài toán quy hoạch tuyến tính (định lý cơ bản của quy hoạch tuyến tính), bài toán quy hoạch toàn phương với các ràng buộc tuyến tính (định lý Frank - Wolfe trong quy hoạch toàn phương), bài toán quy hoạch toàn phương với các ràng buộc toàn phương và trong quy hoạch đa thức lồi. Với mỗi lớp bài toán được xét đều có dẫn ra các ví dụ phân tích các giả thiết nêu trong các định lý tương ứng. Chương 2 "Quy hoạch toàn phương trong không gian Hilbert" trình bày kết quả nghiên cứu mới ở [4] về sự tồn tại nghiệm của bài toán quy hoạch toàn phương không lồi với miền ràng buộc được xác định bởi các bất đẳng thức tuyến tính hay toàn phương lồi trong không gian Hilbert. Để thu được các kết quả này, các tác giả [4] đã sử dụng các tính chất của dạng thức Legendre hoặc các tính chất của toán tử compac với miền giá trị đóng. Các kết quả về sự tồn tại nghiệm được thiết lập không cần đến tính lồi của hàm mục tiêu hoặc tính compact của tập ràng buộc và chúng bao hàm như trường hợp riêng một số kết quả về sự tồn tại nghiệm của bài toán quy hoạch toàn phương trong không gian Rn .
4 Chương 1 Bài toán quy hoạch toàn phương trong Rn Chương này trình bày các kết quả về sự tồn tại nghiệm của bài toán quy hoạch tuyến tính, bài toán quy hoạch toàn phương với các ràng buộc tuyến tính và bài toán quy hoạch toàn phương với các ràng buộc toàn phương. Nội dung của chương được tham khảo chủ yếu từ các tài liệu [1] − [3] và [5] − [7]. 1.1 Định lý cơ bản của quy hoạch tuyến tính Bài toán quy hoạch tuyến tính, ký hiệu (LP ), có thể phát biểu dưới dạng: min{f (x) = cT x : Ax ≤ b}, (LP) trong đó A ∈ Rm×n (ma trận cấp m × n), b ∈ Rm , c, x ∈ Rn (x - véc tơ biến cần tìm). Trong quy hoạch tuyến tính ta đã biết sự kiện quen thuộc với tên gọi "định lý cơ bản của quy hoạch tuyến tính". Nội dung định lý như sau. Định lý 1.1.1 ([7], Định lý 9, tr. 312). Một hàm tuyến tính f (x) = cT x bị chặn dưới trên một tập lồi đa diện D 6= ∅ phải đạt cực tiểu trên D. Chứng minh. Giả sử D = {x ∈ Rn : Ax ≤ b}. Theo định lý biểu diễn tập lồi đa diện, mọi x ∈ D có biểu diễn p X q X r X p X i j k x= λi u + µj v + γk w , λi ≥ 0, λi = 1, µj ≥ 0, λi , µj , γk ∈ R, i=1 j=1 k=1 i=1 trong đó Aui ≤ b, i = 1, . . . , p, Av j ≤ 0, j = 1, . . . , q, Awk = 0, k = 1, . . . , r, hwi , wj i = 0, i 6= j. (Nếu D không chứa đường thẳng nào, tức là r = 0, thì
5 có thể lấy ui là các đỉnh của D và v j là các tia cực biên của nón lồi đa diện K = {x ∈ Rn : Ax ≤ 0}.) Khi đó, hàm f (x) = cT x trên D được cho bởi p X q X r X T T i T j f (x) = c x = λi c u + µj c v + γk cT wk . (1.1) i=1 j=1 k=1 Do cT x bị chặn dưới với mọi µj ≥ 0 và mọi γk ∈ R, cho nên phải có cT v j ≥ 0, j = 1, . . . , q, cT wk = 0, k = 1, . . . , r và khi đó, rõ ràng (1.1) đạt Xp cực tiểu với điều kiện λi ≥ 0, λi = 1, µj ≥ 0, γk ∈ R. i=1 Vì thế, bằng cách đặt f ∗ = min{cT ui : i = 1, . . . , p}, I1 = {i : cT ui = f ∗ }, I2 = {j : cT v j = 0}, ∗ ∗ ∗ ∗ có thể thấy cực Xtiểu của (1.1) đạt được tại λi , µi , γk sao cho λi = 0 với i∈/ I1 , λ∗i ≥ 0, λ∗i = 1, µ∗j ≥ 0, j ∈ I2 , µ∗j = 0 với j ∈ / I2 . Tập nghiệm của i∈I1 bài toán (LP ) là ( X X X∗ = x∗ : x∗ = λi ui + µj v j i∈I1 j∈I2 r ) X X + γk wk , λi ≥ 0, λi = 1, µj ≥ 0, γk ∈ R . k=1 i∈I1 Liệu định lý này còn đúng nếu hàm f khác hàm tuyến tính hoặc tập ràng buộc D không còn là tập lồi đa diện? Nhận xét 1.1.2 Định lý 1.1.1 nói chung không còn đúng nếu hoặc f khác hàm tuyến tính hoặc tập D không là tập lồi đa diện. Các Ví dụ 1.1.3 và 1.1.4 dưới đây minh hoạ cho nhận xét này. Ví dụ 1.1.3 Bài toán với hàm mục tiêu tuyến tính và D khác tập lồì đa diện: min{x2 : x1 x2 ≥ 1, x1 ≥ 0, x2 ≥ 0}
6 vô nghiệm, mặc dù θ := inf{x2 : x1 x2 ≥ 1, x1 ≥ 0, x2 ≥ 0} = 0 > −∞ (xem Hình 1.1). Hình 1.1: Ví dụ 1.1.3 Ví dụ 1.1.4 Bài toán tối ưu với hàm mục tiêu khác hàm tuyến tính có thể vô nghiệm ngay cả(khi hàm mục tiêu có cận dưới hữu hạn. Chẳng hạn, bài 1 toán cực tiểu: min : x ∈ D ≡ R vô nghiệm, trong khi 1 + x2 ( ) 1 θ := inf :x∈R (xem Hình 1.2). 1 + x2 Hình 1.2: Ví dụ 1.1.4 1.2 Định lý Frank-Wolfe của quy hoạch toàn phương Xét bài toán quy hoạch toàn phương, ký hiệu là (QP ), có dạng 1 min{f (x) = xT Qx + cT x : Ax ≤ b}, (QP) 2
7 với Q ∈ S n (ma trận đối xứng), A ∈ Rm×n (ma trận cấp m × n), b ∈ Rm và c ∈ Rn . Quy hoạch tuyến tính là trường hợp riêng của quy hoạch toàn phương (khi Q = 0). Ký hiệu D = {x ∈ Rn : Ax ≤ b} và θ = inf f (x) : x ∈ D. Rõ ràng là nếu D = ∅ hoặc nếu θ = −∞ thì bài toán (QP ) không có nghiệm. Câu hỏi đặt ra là liệu với D 6= ∅ và θ > −∞ thì (QP ) luôn có nghiệm hay không? Vào năm 1956 M. Frank và F. Wolfe trong [3] đã công bố một kết quả quan trọng, được biết với tên gọi định lý Frank-Wolfe, giải đáp câu hỏi nêu trên về sự tồn tại nghiệm của bài toán quy hoạch toàn phương (QP ). 1 Định lý 1.2.1 (Định lý Frank-Wolfe). Nếu hàm toàn phương f (x) = xT Qx+ 2 cT x bị chặn dưới trên một tập lồi đa diện D khác rỗng (tức θ > −∞) thì f phải đạt cực tiểu trên D, nghĩa là tồn tại véctơ x¯ ∈ D sao cho f (¯ x) ≤ f (x) với mọi x ∈ D. Có nhiều cách chứng minh định lý Frank - Wolfe. Sau đây tôi trình bày chứng minh nêu ở [8] (không rõ tác giả) khá ngắn gọn cho định lý Frank - Wolfe, dựa trên định lý quen biết về biểu diễn tập lồi đa diện qua các đỉnh và cạnh của nó). Để tiện theo dõi, sau đây sẽ nhắc lại một số khái niệm và kết quả đã có về giải tích lồi (xem [1], [2]). Định nghĩa 1.2.2 Tập M ⊆ Rn gọi là một tập afin nếu λa + (1 − λ)b ∈ M với mọi a, b ∈ M và mọi λ ∈ R, tức là nếu M chứa trọn đường thẳng đi qua hai điểm bất kỳ của nó. Nói riêng tập ∅, tập gồm duy nhất một điểm và toàn bộ Rn đều là các tập afin. Siêu phẳng trong Rn là một tập afin có dạng H = {x ∈ Rn : aT x = α} với a ∈ Rn , a 6= 0, và α ∈ R. Có thể chứng minh được rằng tập M (khác rỗng) là tập afin khi và chỉ khi M = a + L, trong đó a ∈ M và L là một không gian con (được xác định duy nhất), gọi là không gian con song song với M . Từ đó, ta định nghĩa thứ nguyên hay số chiều của tập afin M , ký hiệu dimM , bằng số chiều của không gian con L song song với M . Định nghĩa 1.2.3 Cho E là một tập bất kỳ trong Rn . Giao của tất cả các tập afin chứa E gọi là bao afin của E, ký hiệu là af f E. Đó là tập afin nhỏ nhất chứa E.
8 Định nghĩa 1.2.4 Thứ nguyên hay số chiều của tập lồi C ⊆ Rn , ký hiệu dimC, là thứ nguyên hay số chiều của bao afin của nó. Một tập lồi C trong Rn gọi là có thứ nguyên đầy đủ nếu dimC = n. Có thể chứng minh rằng tập lồi C trong Rn có phần trong khác rỗng khi và chỉ khi C có thứ nguyên đầy đủ, tức là intC 6= ∅ ⇔ dimC = n. Định nghĩa 1.2.5 Cho C là một tập lồi trong Rn . Véc - tơ d ∈ Rn , d 6= 0, gọi là một hướng lùi xa của C nếu {x + λd : λ ≥ 0} ⊂ C với mọi x ∈ C (mọi tia xuất phát từ một điểm bất kỳ x ∈ C theo hướng d đều nằm trọn trong C). Tập tất cả các hướng lùi xa của C, cùng với véc - tơ 0, gọi là nón lùi xa của C, ký hiệu là recC hoặc 0+ C. Có thể chứng minh được rằng tập lồi đóng C là compact khi và chỉ khi nón lùi xa của nó gồm duy nhất điểm 0, tức là recC = {0}. Hơn nữa, với tập lồi đa diện thì D = {x ∈ Rn : Ax ≤ b}(A ∈ Rm×n , b ∈ Rm ) ⇒ recC = {d ∈ Rn : Ad ≤ 0}. Chứng minh nêu dưới đây dựa chủ yếu vào tài liệu [8] với một số diễn giải cần thiết. Chứng minh định lý Frank - Wolfe. Ta giả thiết D không bị chặn, vì nếu D bị chặn thì định lý đúng với mọi hàm liên tục. Vì vậy, theo định lý biểu diễn tập lồi đa diện, ta có thể viết D = {x : Ax ≤ b} = {p + λs : p ∈ P, s ∈ S, λ ≥ 0}, trong đó P là một đa diện lồi và S là giao của nón lùi xa recD (nón các hướng lùi xa của D) với mặt cầu đơn vị trong Rn . Để ý là cả P và S là các tập compact (đóng và bị chặn). Vì D không bị chặn, tức recD 6= {0}, nên tập S khác rỗng. Ta chứng minh bằng qui nạp theo số chiều của D. Không giảm tổng quát, ta có thể giả thiết D có phần trong khác rỗng, nghĩa là dimD = n. Rõ ràng định lý đúng với n = 1, bởi vì trong trường hợp này hàm một biến f (x) = ax2 + bx + c là một tam thức bậc hai bị chặn dưới theo giả thiết và D là một tia hay cả đường thẳng (do D không bị chặn) trong R1 .
9 Giả thiết qui nạp: Giả sử n > 1 và định lý đúng cho mọi tập lồi đa diện khác rỗng với số chiều nhỏ hơn n. Theo giả thiết θ = inf {f (x) : x ∈ D} > −∞. Khi đó, theo định nghĩa của hàm f , với mọi x = p + λs ∈ D (p ∈ P, s ∈ S, λ ≥ 0) ta có 1 f (x) = f (p + λs) = f (p) + λ(c + Qp)T s + λ2 sT Qs ≥ θ. 2 Do f (x) = f (p + λs) ≥ θ với mọi λ ≥ 0 nên phải có sT Qs ≥ 0 với mọi s ∈ S (vì trái lại f (x) → −∞ khi cho λ → +∞, trái với θ > −∞). Xét hai trường hợp: • Trường hợp 1: sT Qs > 0 với mọi s ∈ S. Đặt α = min{sT Qs : s ∈ S} và β = min{(c + Qp)T s : p ∈ P, s ∈ S}. Do P và S compact nên α và β tồn tại. Ta có α > 0 > β. Như vậy, trong trường hợp này sT Qs ≥ α > 0 với mọi s ∈ S và (c + Qp)T s ≥ β với mọi p ∈ P, s ∈ S. Do đó với mọi λ ≥ 0 thì 1 1 f (p + λs) = f (p) + λ(c + Qp)T s + λ2 sT Qs ≥ f (p) + λβ + λ2 α. 2 2 Với p và s cố định, cực tiểu của f (p + λs) theo λ ≥ 0 đạt tại T ¯ = max{0, − (c + Qp) s }, λ sT Qs trong khi đó cực tiểu của 1 ˆ = − β > 0. f (p) + λβ + λ2 α đạt tại λ 2 α β Giá trị lớn nhất trong hai giá trị này là − . Do đó ta có thể tìm cực tiểu α của f trên tập compact β {p + λs : p ∈ P, s ∈ S, λ ∈ [0, − ]}. α Rõ ràng tập này chứa một điểm x¯ sao cho x) = min{f (x) : x ∈ D}. f (¯
10 • Trường hợp 2: s¯T Q¯ s = 0 với s¯ nào đó thuộc S. Khi đó, do s¯ ∈ S nên với mọi x ∈ D và mọi λ ≥ 0 ta có x + λ¯ s ∈ D và s) = f (x) + λ(c + Qx)T s¯ ≥ θ. f (x + λ¯ Như vậy phải có (c + Qx)T s¯ ≥ 0 với mọi x ∈ D (vì nếu có (c + Qx)T s¯ < 0 s) → −∞ khi λ → +∞, trái với θ > −∞ theo giả thiết). thì f (x + λ¯ + Trước hết giả sử tồn tại y ∈ D sao cho y + λ¯ s ∈ D với mọi λ ∈ R, nghĩa là A(y + λ¯ s) ≤ b với mọi λ ∈ R. Điều này kéo theo A¯ s = 0. Từ đó suy ra x + λ¯ s ∈ D với mọi x ∈ D và mọi λ ∈ R. Hơn nữa do s) = f (x) + λ(c + Qx)T s¯ ≥ θ. f (x + λ¯ nên (c + Qx)T s¯ = 0 với mọi x ∈ D và do đó f (x + λ¯ s) = f (x) với mọi x ∈ D và mọi λ ∈ R. Điều này cho thấy khi chiếu D lên siêu phẳng trực giao với S¯ giá trị hàm f không thay đổi. Do hình chiếu này là một tập lồi đa diện với số chiều bằng n − 1 nên theo giả thiết qui nạp, f đạt cực tiểu tại một điểm thuộc hình chiếu, chẳng hạn tại điểm x¯. Khi đó có λ ∈ R sao cho x¯ + λ¯ s∈D với f (¯ x + λ¯ s) = f (¯ x), nghĩa là x¯ + λ¯ s là nghiệm cực tiểu cần tìm. + Tiếp đó giả sử rằng với mỗi x ∈ D tồn tại λ ∈ R sao cho x + λ¯ s ∈ D. Đặt λx = min{λ ∈ R : x + λ¯ s ∈ D}. Khi đó với mọi x ∈ D ta có λx ∈ (−∞, 0] và x + λx s¯ ∈ ∂D, trong đó ∂D là ký hiệu biên của D. Vì thế f (x + λx s¯) = f (x) + λx (c + Qx)T s¯ ≤ f (x) (bất đẳng thức cuối là do λx ≤ 0 và (c + Qx)T s¯ ≥ 0 với mọi x ∈ D). Bất đẳng thức này cho thấy ta có thể tìm cực tiểu của f trên các diện thuộc biên ∂D, các diện này có số chiều thấp hơn số chiều của D. Theo giả thiết qui nạp, cực tiểu của f trên D đạt được trên biên ∂D. Ví dụ 1.2.6 và 1.2.7 minh họa Định lý Frank-Wolfe cho trường hợp tập D không bị chặn. Ví dụ 1.2.6 Xét bài toán tối ưu lồi hai biến: min{f (x) = x21 + 2x22 − x1 x2 : −x1 + x2 = 1, x1 ≥ 0, x2 ≥ 0}.
11 1 Trong bài toán này f (x) = x21 + 2x22 − x1 x2 = (x1 − x2 )2 + x21 + 3x22 ≥ 0 2 2 2 với mọi x ∈ R và D = {x ∈ R : −x1 + x2 = 1, x1 ≥ 0, x2 ≥ 0} là tập lồi đa diện không bị chặn (nửa đường thẳng). Do f (x) bị chặn dưới trên D nên theo Định lý Frank-Wolfe, bài toán đã cho có nghiệm. Có thể thấy nghiệm cực tiểu của bài toán là x¯ = (0, 1)T với fmin = f (¯ x) = 2 (Xem Hình 1.3). Hình 1.3: Ví dụ 1.2.6 Ví dụ 1.2.7 Xét bài toán tối ưu không lồi với các ràng buộc bất đẳng thức tuyến tính: 1 min{f (x) = (4x21 − x22 ) + 2x1 : 2x1 + x2 ≥ 3, 2x1 − x2 ≥ 1}. 2 Ta có 1 1 1 f (x) = (4x21 − x22 ) + 2x1 = ((2x1 + 1)2 − x22 ) − 2 2 2 1 1 1 1 = (2x1 + x2 + 1)(2x1 − x2 + 1) − ≥ (3 + 1)(1 + 1) − = 3, 5. 2 2 2 2 Do f (x) bị chặn dưới trên D = {x ∈ R2 : 2x1 + x2 ≥ 3, 2x1 − x2 ≥ 1} nên theo Định lý Frank-Wolfe, bài toán trên có nghiệm. Có thể thấy nghiệm cực 1 tiểu của bài toán là x¯ = (1, 1)T và fmin = f (¯ x) = (4 − 1) + 2 = 3, 5 (Xem 2 Hình 1.4).
12 Hình 1.4: Ví dụ 1.2.7 Nhận xét 1.2.8 Frank và Wolfe (1956) còn cho biết I. Kaplansky đã chỉ ra rằng bài toán tìm cực tiểu một hàm đa thức bậc lớn hơn 2 trên một tập lồi đa diện khác rỗng có thể vô nghiệm ngay cả khi hàm đã cho bị chặn dưới trên tập lồi đa diện đó. Ví dụ sau minh họa cho nhận xét này. Ví dụ 1.2.9 (Frank-Wolfe, 1956). Cho f (x) = x21 +(1−x1 x2 )2 là hàm đa thức bậc 4 (khác hàm toàn phương) của x1 và x2 . Giả sử D = {x = (x1 , x2 ) ∈ R2 : x1 ≥ 0, x2 ≥ 0}. Ta thấy f (x) ≥ 0 với mọi x ∈ R2 . Với mọi xk = 1 ( , 1 + k), k ∈ N , ta có k 2 f (xk ) = → 0 khi k → ∞. k2 Điều này chứng tỏ θ := inf{f (x) : x ∈ D} = inf{f (x) : x ∈ R2 } = 0. Có thể thấy cả hai bài toán inf{f (x) : x ∈ D} và inf{f (x) : x ∈ R2 } đều vô nghiệm. 1.3 Mở rộng định lý Frank - Wolfe Có nhiều tác giả nghiên cứu mở rộng định lý Frank - Wolfe. Sau đây là một số kết quả đáng chú ý.
13 1.3.1 Quy hoạch toàn phương với ràng buộc toàn phương Xét bài toán tối ưu có ràng buộc: min{f0 (x) : fi (x) ≤ 0, i = 1, ..., m}, (P) 1 trong đó fi (x) = xT Qi x + qiT x + ci , i = 0, 1, .., m, với Qi ∈ Rn×n , qi ∈ 2 Rn , ci ∈ R. Như đã biết, fi là hàm tuyến tính afin khi Qi = 0; hàm fi lồi khi và chỉ khi Qi nửa xác định dương và lồi chặt khi và chỉ khi Qi xác định dương. Trái lại, hàm fi không lồi. Ta nhắc lại, f : Rn −→ R là hàm tựa lồi nếu với mọi x, y ∈ Rn , λ ∈ [0, 1] ta có f [λx+(1−λ)y] ≤ max{f (x), f (y)} ⇔ Cα = {x ∈ Rn : f (x) ≤ α} lồi, ∀α ∈ R. Giả thiết: (a) Tập chấp nhận được D = {x ∈ Rn : fi (x) ≤ 0, i = 1, ..., m} = 6 ∅, (b) Hàm f0 (x) bị chặn dưới trên D, nghĩa là inf{f0 (x) : x ∈ D} > −∞. Với giả thiết trên, Z. Q. Luo và S. Zang [6] đã chứng minh các kết quả sau. 1. Hàm f0 chắc chắn đạt cực tiểu trên D trong các trường hợp sau. Định lý 1.3.1 ([6], Định lý 3). Với giả thiết a)−b), nếu f0 tựa lồi (nói riêng, f0 lồi) trên D và nếu mọi hàm ràng buộc fi (i = 1, . . . , m) lồi thì f0 đạt cực tiểu trên D. (Trường hợp này gọi là bài toán quy hoạch lồi toàn phương với các ràng buộc toàn phương) Ví dụ sau cho thấy, trong Định lý 1.3.1 không thể thiếu giả thiết f0 lồi (hay tựa lồi). Ví dụ 1.3.2 ([6], Ví dụ 2). Xét bài toán cực tiểu trong R4 : min{f0 (x) : f1 (x) ≤ 0, f2 (x) ≤ 0} với f0 (x) = f0 (x1 , x2 , x3 , x4 ) := x21 − 2x1 x2 + x3 x4 , f1 (x) = f1 (x1 , x2 , x3 , x4 ) := x21 − x3 ≤ 0, f2 (x) = f2 (x1 , x2 , x3 , x4 ) := x22 − x4 ≤ 0,
14 Có thể thấy f0 (x) không lồi, nhưng f1 (x) và f2 (x) lồi. Hơn nữa, do x3 ≥ x21 và x4 ≥ x22 nên x3 x4 ≥ x21 x22 . Như vậy, với mọi véc-tơ chấp nhận được x = (x1 , x2 , x3 , x4 )T sẽ có f0 (x) = x21 − 2x1 x2 + x3 x4 ≥ x21 − 2x1 x2 + x21 x22 = (x1 x2 − 1)2 + x21 − 1 > −1. (1.2) Mặt khác, xét dãy 1 1 xk = (xk1 , xk2 , xk3 , xk4 ) = ( , k, 2 , k 2 ), k = 1, 2, . . . k k Có thể kiểm tra lại rằng xk = (xk1 , xk2 , xk3 , xk4 )T thỏa mãn các ràng buộc và 1 f0 (xk ) = f0 (xk1 , xk2 , xk3 , xk4 ) = ( − 1) −→ −1. k2 Điều này cùng với (1.2) chỉ ra rằng inf f0 trên tập chấp nhận được bằng −1. Nhưng bất đẳng thức (1) cho thấy rằng cận dưới đó không đạt được tại bất cứ điểm chấp nhận được nào. Định lý 1.3.3 ([6], Định lý 2). Với giả thiết a) − b), nếu hàm f0 không lồi trên D và nếu có nhiều nhất một hàm ràng buộc fi (i = 1, . . . , m) lồi phi tuyến (mọi ràng buộc khác là tuyến tính afin) thì f0 đạt cực tiểu trên D. (Trường hợp này gọi là bài toán quy hoạch toàn phương với một ràng buộc toàn phương) Ví dụ sau đây cho thấy, trong Định lý 1.3.3 không thể thiếu giả thiết về tính lồi của hàm ràng buộc trong bất đẳng thức toàn phương duy nhất (nếu có). Ví dụ 1.3.4 ([6], Ví dụ 3). Xét bài toán tối ưu với một ràng buộc toàn phương trên R2 min{x2 : xy ≥ 1, x ≥ 0, y ≥ 0}. Rõ ràng là cận dưới lớn nhất (infimum) của bài toán này bằng 0, nhưng cận dưới đó không đạt được tại bất kỳ điểm chấp nhận được nào. Để ý rằng trong trường hợp này, hàm ràng buộc trong bất đẳng thức xy ≥ 1 là không lồi, mặc dù tập chấp nhận được là lồi. Hai định lý vừa nêu trên được xem là sự mở rộng tự nhiên của định lý Frank - Wolfe cho bài toán quy hoạch toàn phương với các ràng buộc toàn phương, thường được ký hiệu là (CQCQP ).
15 2. Với giả thiết a) − b), nói chung hàm f0 không đạt cực tiểu trên D trong các trường hợp sau (chẳng hạn, trừ ra khi f0 là hàm hằng trên D): + Có ít nhất một hàm ràng buộc fi (i = 1, . . . , m) không lồi (Qi 6= 0, không xác định dương hay nửa xác định dương), kể cả khi f0 là hàm lồi. + Hàm f0 không lồi và có ít nhất hai hàm ràng buộc fi (i = 1, . . . , m) lồi phi tuyến. 1.4 Quy hoạch đa thức lồi Ta biết rằng mỗi hàm đa thức bậc p trên Rn được biểu diễn (duy nhất) bởi tổng Xp f (x) = ϕi (x), i=0 trong đó ϕi (x) ≡ 0 với một số chỉ số i nào đó, ϕ0 là hàm hằng và ϕi , i ≥ 1, là các dạng thức bậc i, tức là các đa thức thỏa mãn ϕi (tx) = ti ϕi (x), ∀t ∈ R, ∀x ∈ Rn . Hơn nữa, nếu f là đa thức lồi bậc p thì hàm ϕp trong biểu diễn trên là lồi. Xét bài toán tối ưu với các hàm đa thức: (P ) min{f0 (x) : x ∈ X}, trong đó X = {x ∈ Rn : fi (x) ≤ 0, i = 1, . . . , m} (1.3) và f0 , f1 , . . . , fm là các đa thức thực của các biến x1 , . . . , xn . Tập có dạng (1.3) gọi là tập đa thức. Nếu các đa thức f0 , f1 , . . . , fn là lồi thì (P ) được gọi là một quy hoạch đa thức lồi và X được gọi là tập đa thức lồi. E. G. Belousov và D. Klatte [3] đã nêu các kết quả mở rộng định lý Frank - Wolfe cho các hàm đa thức lồi. Định lý 1.4.1 ([3], Định lý 3). Giả sử f0 , f1 , . . . , fm là các hàm đa thức lồi trên Rn . Nếu f0 bị chặn dưới trên tập khác rỗng X = {x ∈ Rn : fi (x) ≤ 0, i = 1, . . . , m} thì f0 chắc chắn đạt cực tiểu trên X.
16 Ví dụ sau cho thấy trong Định lý 1.4.1 không thể bỏ giả thiết lồi của hàm f0 Ví dụ 1.4.2 Xét quy hoạch trùng phương trong R3 , với ma trận Hess của hàm mục tiêu chỉ có một giá trị riêng âm: f0 (x) = f0 (x1 , x2 , x3 ) := −f1 (x)−f2 (x)+(x2 −x3 )2 = 2x1 −2x2 x3 +1 −→ min, f1 (x) = f1 (x1 , x2 , x3 ) := x22 −x1 ≤ 0, f2 (x) = f2 (x1 , x2 , x3 ) := x23 −x1 −1 ≤ 0. Mọi mặt, với bất kỳ véc-tơ chấp nhận được (x1 , x2 , x3 )T ta luôn có f0 (x1 , x2 , √ √ x3 ) > 0. Mặt khác, xét dãy xk = (xk1 , xk2 , xk3 ) = (k, k, k + 1), k = 1, 2, . . . Có thể kiểm tra lại rằng xk = (xk1 , xk2 , xk3 ) chấp nhận được và √ √ 1 f0 (xk1 , xk2 , xk3 )( k − k + 1)2 = √ √ −→ 0. ( k + k + 1)2 Điều này cùng với f0 (x1 , x2 , x3 ) > 0 kéo theo inf f0 trên tập chấp nhận được bằng 0. Tuy nhiên, bất đẳng thức f0 (x1 , x2 , x3 ) > 0 cho thấy inf f0 không thể đạt được tại bất cứ véc-tơ chấp nhận được nào. Trong ví dụ này f0 là hàm không lồi cũng không lõm. Thu được cùng một kết quả như vậy bằng cách dùng đa thức lõm làm hàm mục tiêu. f0 (x1 , x2 , x3 ) := −2f1 (x) − 2f2 (x) + (x2 − x3 )2 := −(x2 + x3 )2 + 4x1 + 2. Rõ ràng là ma trận Hess của cả hai hàm mục tiêu f0 (x) = 2x1 − 2x2 x3 + 1 và f0 (x) = −(x2 + x3 )2 + 4x1 + 2 chỉ có một giá trị riêng âm. Câu hỏi mở (mở rộng Định lý 1.3.3), chưa có lời giải: Nếu f0 là đa thức bậc hai tùy ý và bị chặn dưới trên tập ràng buộc X, trong đó có nhiều nhất một hàm ràng buộc fi (i = 1, . . . , m) phi tuyến (nhưng là đa thức lồi, không nhất thiết toàn phương lồi) thì liệu f0 có chắc chắn đạt cực tiểu trên X không? Kết luận chương. Chương này đã giới thiệu định lý Frank - Wolfe trong quy hoạch toàn phương (ràng buộc tuyến tính) và một số mở rộng của định lý này cho quy hoạch toàn phương với các ràng buộc toàn phương và quy hoạch đa thức lồi.