Tài liệu Bài toán quy hoạch toàn phương có ràng buộc nón

  • Số trang: 36 |
  • Loại file: PDF |
  • Lượt xem: 78 |
  • Lượt tải: 0
nhattuvisu

Đã đăng 27127 tài liệu

Mô tả:

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN NGỌC HẢI BÀI TOÁN QUY HOẠCH TOÀN PHƯƠNG CÓ RÀNG BUỘC NÓN 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: PGS. TS. NGUYỄN NĂNG TÂM Thái Nguyên - 2014 Soá hoùa bôûi Trung taâm Hoïc lieäu ĐHTN http://www.lrc.tnu.edu.vn/ LỜI CẢM ƠN Luận văn được hoàn thành tại trường Đại học khoa học - Đại học Thái Nguyên dưới sự hướng dẫn của PGS. TS. Nguyễn Năng Tâm. Tác giả xin được bày tỏ lòng biết ơn chân thành sâu sắc tới PGS. TS. Nguyễn Năng Tâm, người đã tận tình hướng dẫn về phương hướng, nội dung và phương pháp nghiên cứu trong suốt quá trình nghiên cứu, thực hiện và hoàn thành luận văn. Tác giả cũng xin gửi lời cảm ơn chân thành tới Ban giám hiệu trường Đại học khoa học - Đại học Thái Nguyên, phòng sau đại học đã tạo điều kiện rất thuận lợi về mọi mặt cho tác giả trong quá trình tác giả học tập, nghiên cứu và hoàn thành luận văn. Thái Nguyên, tháng 06 năm 2014 Tác giả Nguyễn Ngọc Hải i Soá hoùa bôûi Trung taâm Hoïc lieäu ĐHTN http://www.lrc.tnu.edu.vn/ LỜI CAM ĐOAN Tôi xin cam đoan luận văn là công trình nghiên cứu của riêng tôi dưới sự hướng dẫn trực tiếp của PGS. TS. Nguyễn Năng Tâm. Trong quá trình nghiên cứu đề tài luận văn, tôi đã kế thừa thành quả khoa học của các nhà toán học và các nhà khoa học khác với sự trân trọng và biết ơn. Thái Nguyên, tháng 06 năm 2014 Tác giả Nguyễn Ngọc Hải ii Soá hoùa bôûi Trung taâm Hoïc lieäu ĐHTN http://www.lrc.tnu.edu.vn/ Mục lục Mở đầu 1 1 KIẾN THỨC CHUẨN BỊ 5 1.1. Khái niệm về không gian Hilbert . . . . . . . . . . . . . 5 1.2. Khái niệm về ánh xạ đa trị . . . . . . . . . . . . . . . . 11 2 BÀI TOÁN QUY HOẠCH TOÀN PHƯƠNG CÓ RÀNG BUỘC NÓN 12 2.1. Bài toán tối ưu . . . . . . . . . . . . . . . . . . . . . . . 12 2.2. Bài toán quy hoạch toàn phương có ràng buộc nón . . . 13 2.3. Điều kiện cực trị cho bài toán qui hoạch toàn phương có ràng buộc nón . . . . . . . . . . . . . . . . . . . . . . . . 14 2.4. Sự ổn định của bài toán quy hoạch toàn phương có ràng buộc nón . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.4.1. Sự ổn định của tập hợp điểm KKT . . . . . . . . 17 2.4.2. Sự ổn định của tập nghiệm toàn cục . . . . . . . 22 2.4.3. Tính liên tục của hàm giá trị tối ưu . . . . . . . . 26 2.5. Kết luận chương 2 . . . . . . . . . . . . . . . . . . . . . 29 iii Soá hoùa bôûi Trung taâm Hoïc lieäu ĐHTN http://www.lrc.tnu.edu.vn/ Kết luận 30 Tài liệu tham khảo 30 iv Soá hoùa bôûi Trung taâm Hoïc lieäu ĐHTN http://www.lrc.tnu.edu.vn/ CÁC KÝ HIỆU THƯỜNG DÙNG Rn không gian Euclid n-chiều k.k chuẩn Euclid trong Rn hx, yi tích vô hướng của hai véc tơ x; y   B x0 , ε = x ∈ Rn : x − x0 < 0 hình cầu mở trong Rn có tâm tại x0 , bán kính ε A ∈ Rn×n ma trận đối xứng clS bao đóng của tập hợp S intS miền trong của tập hợp S S (Q, a, c) tập hợp các điểm KKT loc (Q, c, a) nghiệm địa phương của (P ) Sol (Q, c, a) nghiệm (toàn cục) của (P ) 1 Soá hoùa bôûi Trung taâm Hoïc lieäu ĐHTN http://www.lrc.tnu.edu.vn/ MỞ ĐẦU 1. Lý do chọn đề tài Lý thuyết tối ưu có nhiều ứng dụng trong lý thuyết cũng như trong các bài toán thực tế chẳng hạn, 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, kiến trúc đô thị, công nghệ thông tin.... 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. 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, kỹ thuật - công nghệ, kinh tế - quản lý, sinh học - nông nghiệp, xã hội - nhân văn, sinh thái - môi trường ... Quy hoạch toàn phương là một trong những lĩnh vực của Tối ưu hóa. Lý thuyết quy hoạch toàn phương đã và đang được nhiều tác giả quan tâm nghiên cứu [5], [7]. Sau một thời gian học cao học, với mong muốn tìm hiểu sâu hơn về toán ứng dụng, tôi chọn đề tài Bài toán quy hoạch toàn phương có ràng buộc nón để nghiên cứu. 2. Mục đích nghiên cứu Mục đích nghiên cứu nhằm nắm được các định nghĩa, định lí, tính chất của Bài toán quy hoạch toàn phương có ràng buộc nón và các ứng dụng của bài toán liên quan đến các vấn đề thực tiễn. Qua đó, giúp củng cố các kiến thức đã được học như: không gian Rn , không gian affine, giải tích hàm,. . . Soá hoùa bôûi Trung taâm Hoïc lieäu ĐHTN http://www.lrc.tnu.edu.vn/ 3 3. Nhiệm vụ nghiên cứu Hệ thống hoá các vấn đề lý luận về các kiến thức cơ sở liên quan đến nội dung chính của bài toán. Hệ thống hoá các định nghĩa, tính chất, ví dụ và ứng dụng của Bài toán quy hoạch toàn phương có ràng buộc nón. 4. Giả thuyết khoa học Trên cơ sở nghiên cứu mở rộng bài toán quy hoạch toàn phương để áp dụng giải quyết các vấn đề thực tiễn, các bài toán thực tế của con người nhằm nâng cao hiệu quả công việc. 5. Phương pháp nghiên cứu Quá trình làm luận văn đã sử dụng kết hợp nhiều phương pháp nghiên cứu, nhưng chủ yếu là phương pháp tổng kết kinh nghiệm. Cụ thể, kết hợp phương pháp tổng hợp, so sánh, phân tích, nhận xét trong quá trình nghiên cứu lí thuyết. Đầu tiên, sau khi tìm được nguồn tài liệu tham khảo thì tổng hợp các kiến thức trong đó với các kiến thức sẵn có. Sau đó, tiến hành so sánh, phân tích chúng, chọn ra những kiến thức trọng tâm, đáng ghi nhớ, từ đó đưa ra những nhận xét riêng. Cuối cùng, tổng hợp, trình bày lại theo ý hiểu một cách rõ ràng. 6. Đóng góp của luận văn Hệ thống hoá các vấn đề lý luận liên quan đến đề tài. Soá hoùa bôûi Trung taâm Hoïc lieäu ĐHTN http://www.lrc.tnu.edu.vn/ 4 Vận dụng Bài toán quy hoạch toàn phương có ràng buộc nón vào giải quyết các bài toán, các vấn đề thực tế trong cuộc sống con người. 7. Cấu trúc luận văn Ngoài phần mở đầu, kết luận và danh mục tài liệu tham khảo, luận văn có 2 chương: Chương 1: Kiến thức chuẩn bị 1.1. Khái niệm về không gian Hilbert 1.2. Khái niệm về ánh xạ đa trị 1.3. Kết luận chương 1 Chương 2: Bài toán Quy hoạch toàn phương có ràng buộc nón 2.1. Bài toán tối ưu 2.2. Bài toán quy hoạch toàn phương có ràng buộc nón 2.3. Điều kiện cực trị cho bài toán quy hoạch toàn phương có ràng buộc nón 2.4. Sự ổn định của bài toán quy hoạch toàn phương có ràng buộc nón 2.5. Kết luận chương 2 Soá hoùa bôûi Trung taâm Hoïc lieäu ĐHTN http://www.lrc.tnu.edu.vn/ Chương 1 KIẾN THỨC CHUẨN BỊ Những nội dung trình bày trong chương này chủ yếu lấy từ [1], [3], [4] và [7]. 1.1. Khái niệm về không gian Hilbert Cho V là không gian véc tơ trên trường số thực R. Định nghĩa 1.1. Ta gọi mỗi ánh xạ h., .i : V × V → R; (x, y) 7→ hx, yi là một tích vô hướng trên V nếu các điều kiện sau đây thỏa mãn: Với mọi x, y, z ∈ V và α ∈ R i) hx, yi = hy, xi ii) hαx, yi = α hx, yi iii) hx, y + zi = hx, yi + hx, zi iv) hx, xi ≥ 0, hx, xi = 0 khi và chỉ khi x = 0 Số hx, yi được gọi là tích vô hướng của x và y. Không gian véc tơ V cùng với một tích vô hướng xác định được gọi là không gian có tích vô hướng và thường được viết là (V, h., .i). Soá hoùa bôûi Trung taâm Hoïc lieäu ĐHTN http://www.lrc.tnu.edu.vn/ 6 Định nghĩa 1.2. Cho không gian véc tơ V cùng với một tích vô hướng h., .i xác định . Khi đó công thức kxk = p hx, xi xác định một chuẩn trên V . Nếu không gian có tích vô hướng (V, h., .i) với chuẩn xác định như trên là một không gian đủ, thì ta goi (V, h., .i) là một không gian Hilbert. Ta gọi số chiều của V là số chiều của không gian Hilbert (V, h., .i). Định nghĩa 1.3. Cho V là một không gian Hilbert và a ∈ V . Ta gọi mỗi không gian con tuyến tính X của V là một không gian con, mỗi tập có dạng a + X trong V là một không gian affine con của V . Ví dụ 1.1. Lấy V = Rn . Với x = (x1 , . . . , xn ), y = (y1 , . . . , yn ) ∈ V biểu thức hx, yi = n X xi yi i=1 xác định một tích vô hướng trên không gian Rn và với chuẩn kxk = p hx, xi Rn trở thành một không gian Hilbert hữu hạn chiều. Định nghĩa 1.4. Cho x0 ∈ V, ε > 0 ta gọi tập   B x0 , ε = x ∈ V | kx − x0 k < 0 là hình cầu mở trong không gian V có tâm tại x0 , bán kính ε. Tập U ∈ V gọi là mở nếu với mọi x0 ∈ U tồn tại ε > 0 sao cho  B x0 , ε ⊂ U. Tập F ∈ V được gọi là đóng nếu U = V \ F là mở. Soá hoùa bôûi Trung taâm Hoïc lieäu ĐHTN http://www.lrc.tnu.edu.vn/ 7 Định nghĩa 1.5. Tập S ⊂ V được gọi là lồi nếu với mọi x, y ∈ S, đoạn thẳng nối x, y đều nằm trong S. Nói cách khác, S ⊂ V là tập lồi khi và chỉ khi: ∀x, y ∈ S, ∀λ ∈ [0, 1] ta cóx = λx1 + (1 − λ) x2 ∈ S. Ví dụ 1.2. Các tập S sau đây là tập lồi:   i) S = x = x1 , x2 , x3 ∈ R3 : 2x1 − x2 + 3x3 = 5 .   ii) S = x = x1 , x2 , x3 ∈ R3 : 2x1 − x2 + 3x3 ≤ 5 .   iii) S = x ∈ R : x = x1 , x2 : x1 + x2 ≤ 9 . Các tính chất của tập lồi Cho tập lồi S1 , S2 ⊂ Rn . Khi đó: 1) S1 ∩ S2 là tập lồi.  2) S1 + S2 = x : x = x1 + x2 với x1 ∈ S1 , x2 ∈ S2 là tập lồi. 3) S1 − S2 cũng là tập lồi. Định nghĩa 1.6. Cho tập lồi khác rỗng S ⊂ V . Hàm số f : S → R được gọi là hàm lồi nếu ∀x, y ∈ S, ∀λ ∈ [0, 1] ta có f (λx + (1 − λ) y) ≤ λf (x) + (1 − λ) f (y) . Ví dụ 1.3. i) Hàm số f : R → R với f (x) = x2 là một hàm lồi. ii) Hàm số hai biến f : R2 → R với f (x, y) = x2 + y 2 là hàm lồi. Định nghĩa 1.7. Cho S ⊂ V là một tập hợp khác rỗng. S được gọi là nón nếu ∀λ > 0 và x ∈ S ta luôn có λx ∈ S. Nón S được gọi là nón lồi nếu S là tập lồi. Nón S được gọi là nón lồi đóng nếu S vừa là nón lồi vừa là tập đóng. Định nghĩa 1.8. Cho một tập hợp khác rỗng S ⊂ V. Nón đối cực của ∗ S, được ký hiệu là S , là tập hợp {y ∈ V | hy, xi ≤ 0, ∀x ∈ S}. Nếu S là tập rỗng thì nón đối cực sẽ là V . Soá hoùa bôûi Trung taâm Hoïc lieäu ĐHTN http://www.lrc.tnu.edu.vn/ 8 Định lý 1.1. Cho V là không gian Hilbert với x, y ∈ V ta luôn có bất đẳng thức sau |hx, yi| ≤ kxkkyk. Bất đẳng thức này được gọi là bất đẳng thức Cauchy- Schwartz. Chứng minh. Nếu x = 0 thì hiển nhiên nhiên bất đẳng thức CauchySchwartz đúng. Xét trường hợp x 6= 0. Với t ∈ R, đặt ϕ(t) = htx + y, tx + yi. Theo định nghĩa tích vô hướng ta có ϕ(t) ≥ 0, ∀t. Ta lại có ϕ(t) = hx, xit2 + 2hx, yit + hy, yi là một tam thức bậc hai biến t. Do tính không âm của ε(t) ta phải có ∆ = hx, yi2 − hx, xi.hy, yi ≤ 0. Từ đây suy ra |hx, yi| ≤ kxkkyk, ta có điều phải chứng minh. Định lý 1.2. Cho V là một không gian Hilbert. Khi đó h., .i : V × V → R là một hàm liên tục Chứng minh. Cho {xn }, {yn } là hai dãy trong không gian Hilbert V lần lượt hội tụ về x0 và y0 . Khi đó, ta có |hxn , yn i − hx0 , y0 i| 6 |hxn , yn i − hxn , y0 i| + |hxn , y0 i − hx0 , y0 i| = |hxn , yn − y0 i| + |hxn − x0 , y0 i| ≤ kxn kkyn − y0 k + kxn − x0 kky0 k. Theo giả thiết {xn } hội tụ trong V nên nó bị chặn, nghĩa là tồn tại số M > 0 sao cho kxn k ≤ M với mọi n ∈ N. Vì vậy, ta có |hxn , yn i − hx0 , y0 i| ≤ M kyn − y0 k + kxn − x0 kky0 k. Soá hoùa bôûi Trung taâm Hoïc lieäu ĐHTN http://www.lrc.tnu.edu.vn/ 9 Chuyển qua giới hạn ta được lim |hxn , yn i − hx0 , y0 i| = 0. n→∞ Vậy định lý được chứng minh. Định lý 1.3. Cho S là một tập lồi đóng khác rỗng trong không gian Hilbert V . Khi đó, với mỗi x ∈ V tồn tại duy nhất y ∈ S sao cho kx − yk = inf{kx − zk | z ∈ S}. Ta kí hiệu d(x, S) = inf{kx − zk | z ∈ S}. Định nghĩa 1.9. Hai phần tử x và y của không gian Hilbert V gọi là trực giao nếu hx, yi = 0, kí hiệu x⊥y. Nếu S là một tập con của không gian Hilbert V thì tập S ⊥ = {x ∈ V | x⊥y ∀y ∈ S} gọi là phần bù trực giao của S. Định lý 1.4. Giả sử S là một không gian con đóng của không gian Hilbert V . Khi đó mỗi phần tử x ∈ V biểu diễn được một cách duy nhất dưới dang x = y + z, trong đó y ∈ S và z ∈ S ⊥ . Chứng minh. Nếu x ∈ S thì đặt y = x, z = 0. Ta có khẳng định đúng. Xét trường hợp x ∈ / S. Vì S đóng nên tồn tại duy nhất y ∈ S sao cho kx − yk = d(x, S). Đặt z = x − y, ta có x = y + z, Ta phải chứng minh z ∈ S ⊥ . Thật vậy, với mọi α ∈ R, u ∈ S ta có kzk = kx − yk ≤ kx − (y + αu)k = kz − αuk. Soá hoùa bôûi Trung taâm Hoïc lieäu ĐHTN http://www.lrc.tnu.edu.vn/ 10 Từ đó suy ra kzk2 ≤ hz − αu, z − αu = kzk2 − αhu, zi − αhz, ui + α2 kuk2 . Chọn α = hz, ui và kuk, ta suy ra 0 ≤ −|hz, ui|2 . Do đó, hz, ui = 0 với mọi u ∈ S và kuk = 1. Như vậy ta đã chỉ ra z ∈ S ⊥ . Tiếp theo ta chứng minh sự biểu diễn là duy nhất, giả sử x = y1 +z1 với y1 ∈ S, z1 ∈ S ⊥ . Khi đó, y−y1 = z1 −z, ta có y−y1 ∈ S và y−y1 ∈ S ⊥ . Từ đó suy ra hy − y1 , y − y1 i = 0. Do vậy y = y1 và do đó z = z1 . Vậy định lý được chứng minh. Định nghĩa 1.10. Theo định lý trên, mọi x ∈ V đều biểu diễn được duy nhất dạng x = y + z với y ∈ S, z ∈ S ⊥ . Như vậy, V = S ⊕ S ⊥ . Ánh xạ P : V → S, xác định P (x) = y với x = y + z ∈ S ⊕ S ⊥ , được gọi là phép chiếu trực giao từ V lên S Định lý 1.5. Phép chiếu trực giao P từ không gian Hilbert V lên không gian con đóng S 6= {0} là một toán tử tuyến tính liên tục. Chứng minh. Với x1 , x2 ∈ V, α ∈ R, theo định lý 1.4 ta có x1 = P x1 + z1 ; x2 = P x2 + z2 , trong đó z1 , z2 ∈ S ⊥ . Vì vậy x1 + x2 = P x1 + P x2 + z1 + z2 , trong đó P x1 + P x2 ∈ S, z1 + z2 ∈ S ⊥ . Từ tính duy nhất của sừ biểu diễn trong định lý trên ta suy ra P (x1 + x2 ) = P x1 + P x2 . Soá hoùa bôûi Trung taâm Hoïc lieäu ĐHTN http://www.lrc.tnu.edu.vn/ 11 Tương tự P (αx1 ) = αP (x1 ). Vậy P tuyến tính. Mặt khác, với x ∈ V ta có kxk2 = kP xk2 kzk2 ≥ kP xk2 . Từ đó suy ra P bị chặn. Vậy P liên tục. Định được chứng minh. 1.2. Khái niệm về ánh xạ đa trị Định nghĩa 1.11. Cho X, Y là những tập hợp tập hợp. Ta gọi mỗi quy tắc F cho ứng với mỗi phần tử x của X với duy nhất một tập con F (x) của Y là một ánh xạ đa trị từ X vào Y , kí hiệu F : X ⇒ Y . Cho anh xạ đa trị F : W ⇒ V trong đó W là tập hợp con của không gian Hilbert. Định nghĩa 1.12. Ta nói F là nửa liên tục trên (usc) tại ω ∈ W nếu đối với mỗi tập hợp mở Ω ⊂ V thỏa mãn F (ω) ⊂ Ω, khi đó tồn tại δ > 0 sao cho F (ω 0 ) ⊂ Ω với mọi ω 0 ∈ W thoả mãn tính chất kω 0 − ωk < δ. Định nghĩa 1.13. Chúng ta nói rằng F là nửa liên tục dưới (lsc) tại ω ∈ W nếu đối với mỗi tập hợp mở Ω ⊂ V thỏa mãn F (ω) ∩ Ω 6= ∅, khi đó tồn tại δ > 0 sao cho F (ω 0 ) ∩ Ω 6= ∅ với mọi ω 0 ∈ W thoả mãn tính chất kω 0 − ωk < δ. Nếu F đồng thời nửa liên tục trên và là nửa liên tục dưới tại ω, thì ta nói rằng nó là liên tục tại ω. Kết luận chương 1 Trong chương này đã sơ lược trình bày một số kiến thức cơ bản sẽ sử dụng trong phần sau. Soá hoùa bôûi Trung taâm Hoïc lieäu ĐHTN http://www.lrc.tnu.edu.vn/ Chương 2 BÀI TOÁN QUY HOẠCH TOÀN PHƯƠNG CÓ RÀNG BUỘC NÓN Mục đích của chương này là trình bày một vài tính chất định tính của bài toán cực tiểu hoá hàm toàn phương trên giao của không gian con affine và hình nón lồi đóng n chiều có miền trong khác rỗng. Những nội dung trình bày trong chương này lấy từ [3], [5], [6] và [7]. 2.1. Bài toán tối ưu Bài toán tối ưu là bài toán có dạng: inf f (x) với x ∈ D, (2.1) trong đó D là một tập con của một không gian tô pô X, f : D → R là một hàm số. Hàm f gọi là hàm mục tiêu, tập D gọi là miền ràng buộc hoặc tập chấp nhân được của bài toán (2.1). Nếu D = X thì ta nói bài toán (2.1)không có ràng buộc. Như vậy, ta cần tìm điểm x ∈ D sao cho hàm mục tiêu f (x) đạt được giá trị bé nhất - cực tiểu hoá. Điểm x ∈ D được gọi là điểm chấp nhận được của bài toán (2.1). Định nghĩa 2.1. Điểm x∗ ∈ X được gọi là nghiệm tối ưu (hay nghiệm) Soá hoùa bôûi Trung taâm Hoïc lieäu 12 ĐHTN http://www.lrc.tnu.edu.vn/ 13 toàn cục của bài toán (2.1) nếu x∗ ∈ D và f (x∗ ) 6 f (x) ∀x ∈ D. Điểm x∗ ∈ D được gọi là nghiệm tối ưu địa phương của (2.1) nếu tồn tại một lân cận mở U trong X của điểm x∗ sao cho f (x∗ ) ≤ f (x) , ∀x ∈ U ∩ D. Dễ thấy, mọi nghiệm tối ưu toàn cục cũng là phương án tối ưu địa phương, trong khi đó một phương án tối ưu địa phương không nhất thiết là phương án tối ưu toàn cục. 2.2. Bài toán quy hoạch toàn phương có ràng buộc nón Cho (V, h., .i) là không gian Hinbert hữu hạn chiều và K ⊂ V là hình nón lồi đóng với đối ngẫu dương K ∗ := {y ∈ V : hy, xi ≥ 0, ∀x ∈ K} . Giả sử miền trong intK của K là khác rỗng và K nhọn, nghĩa là K ∩ (−K) = {0} . Kí hiệu LS (V ) là tập hợp các toán tử tuyến tính đối xứng Q : V → V . Do đó, cho bất kỳ Q ∈ LS (V ) và x, y ∈ V, luôn có hQx, yi = hx, Qyi . Ta gọi bài toán sau là Bài toán quy hoạch toàn phương có ràng buộc nón 1 inf f (x, Q, c) := hx, Qxi + hc, xi 2 với x ∈ a + X, x ∈ K Soá hoùa bôûi Trung taâm Hoïc lieäu ĐHTN http://www.lrc.tnu.edu.vn/ (2.2) 14 trong đó Q ∈ LS (V ) , c, a ∈ V và X ⊂ V là một không gian con tuyến tính. Gần đây, đã có thuật toán cho (2.2) được đề nghị trong khuôn khổ của đại số Jordan-Euclide [6] . Dễ dàng chỉ ra rằng bài toán quy hoạch toàn phương với ràng buộc tuyến tính là trường hợp đặc biệt của (2.2). Bài toán phụ miền tin cậy cũng là một trường hợp đặc biệt của (2.2). Thật thế, lấy V = Rn và K là hình nón Lorentz trong V , nghĩa là ( ) n−1 X K = x = (x1 , ..., xn ) : x2n ≥ x2i . i=1 Lấy X = {x = (x1 , ..., xn ) : xn = 0} và a = (0, ..., 0, µ) với µ > 0, ta có ( (a + X) ∩ K = x = (x1 , ..., xn−1 , µ) : n−1 X ) x2i ≤ µ2 . i=1 Do đó (2.2) trở thành vấn đề về cực tiểu hoá hàm toàn phương trên hình cầu đóng với tâm 0 và bán kính µ > 0 trong không gian Rn−1 . Đó chính là bài toán phụ miền tin cậy. 2.3. Điều kiện cực trị cho bài toán qui hoạch toàn phương có ràng buộc nón Bổ đề 2.1. Cho x ∈ K, giả sử  K (x) = y ∈ E : x + ty ∈ K, t > 0 đủ nhỏ Khi đó đối ngẫu của nó K (x)∗ = {s ∈ K ∗ : hx, si = 0} . Soá hoùa bôûi Trung taâm Hoïc lieäu ĐHTN http://www.lrc.tnu.edu.vn/ 15 Chứng minh. Dễ dàng thấy rằng K(x) là một nón lồi. Vì K ⊂ K(x), ta có K (x)∗ ⊂ K ∗ . Giả sử s ∈ K ∗ , hx, si = 0. Nếu y ∈ K (x) thì tồn tại t > 0 sao cho x + ty ∈ K. Khi đó hs, x + tyi = t hs, yi ≥ 0. Do đó, hs, yi ≥ 0. Như vậy {s ∈ K ∗ : hx, si = 0} ⊂ K (x)∗ . Ngược lại, giả sử s ∈ K (x)∗ ⊂ K ∗ . Khi đó ta có hs, yi ≥ 0. Tuy nhiên, −x ∈ K (x) . Thực vậy, nếu 0 < t < 1, x + t (−x) = (1 − t) x ∈ K, nghĩa là −x ∈ K (x), nhưng khi đó hs, −xi ≥ 0, nghĩa là hs, xi ≤ 0. Vì vậy, hs, xi = 0. Ta đi đến kết luận K (x)∗ ⊂ {s ∈ K ∗ | hx, si = 0} . Điều kiện cần cực trị bậc nhất cho (2.2) có thể phát biểu như sau Định lý 2.1. Nếu x ∈ K ∩ (a + X) là cực tiểu địa phương của (2.2), thì có r ≥ 0 và s ∈ K ∗ sao cho (r, s) 6= (0, 0) , r (Qx + c) − s ∈ X ⊥ , và hx, si = 0, trong đó X ⊥ thay cho không gian con trực giao của X. Nếu thêm vào đó (a + X) ∩ (intK) là rỗng, thì có thể lấy r = 1. Chứng minh. Kí hiệu f (x) = 1 2 hx, Qxi + hc, xi. Giả sử π : E → X ⊥ là phép chiếu trực giao. Đặt  N = (t, π (p)) ∈ R × X ⊥ | t = hf 0 (x∗ ) , pi , p ∈ K (x∗ ) và  P = (t, y) ∈ R × X ⊥ : t < 0, y = 0 . Ta khẳng định rằng N ∩ P = ∅. Thực vậy, nếu N ∩ P 6= ∅, thì tồn tại p ∈ K (x∗ ) ∩ X sao cho hf 0 (x∗ ) , pi < 0. Tuy nhiên, khi đó x∗ + tp ∈ (a + X) ∩ K, với t > 0 đủ bé. Soá hoùa bôûi Trung taâm Hoïc lieäu ĐHTN http://www.lrc.tnu.edu.vn/
- Xem thêm -