Tài liệu Từ bài toán quy hoạch toàn phương đến bất đẳng thức biến phân affine

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THỊ SIM TỪ BÀI TOÁN QUY HOẠCH TOÀN PHƯƠNG ĐẾN BẤT ĐẲNG THỨC BIẾN PHÂN AFFINE 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 THỊ SIM TỪ BÀI TOÁN QUY HOẠCH TOÀN PHƯƠNG ĐẾN BẤT ĐẲNG THỨC BIẾN PHÂN AFFINE 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 - 2017 i Mục lục Bảng ký hiệu 1 Lời nói đầu 2 1 Kiến thức chuẩn bị 4 1.1 Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1 Tập affine và bao affine . . . . . . . . . . . . . . 4 4 1.1.2 Tập lồi, nón lồi và bao lồi . . . . . . . . . . . . . 6 1.1.3 Điểm cực biên, phương lùi xa, nón lùi xa và phương cực biên . . . . . . . . . . . . . . . . . . . . . . . 8 Các định lý tách tập lồi . . . . . . . . . . . . . . . Tập lồi đa diện . . . . . . . . . . . . . . . . . . . 8 9 1.1.6 Hàm lồi và tính chất . . . . . . . . . . . . . . . . Hàm toàn phương . . . . . . . . . . . . . . . . . . . . . . 10 12 1.1.4 1.1.5 1.2 1.2.1 1.2.2 2 12 Hàm toàn phương . . . . . . . . . . . . . . . . . . 13 Bài toán quy hoạch toàn phương 15 2.1 Giới thiệu bài toán và sự tồn tại nghiệm . . . . . . . . . . 2.1.1 Định nghĩa bài toán quy hoạch toàn phương . . . . 15 15 2.1.2 2.1.3 Các dạng bài toán quy hoạch toàn phương . . . . . Điều kiện tồn tại nghiệm . . . . . . . . . . . . . . 17 17 Điều kiện tối ưu (Điều kiện Karush-Kuhn-Tucker (KKT)) . 29 2.2 3 Ma trận xác định dương và ma trận nửa xác định dương . . . . . . . . . . . . . . . . . . . . . . . . Bài toán bất đẳng thức biến phân affine 31 3.1 31 Giới thiệu bài toán . . . . . . . . . . . . . . . . . . . . . ii 3.1.1 Bất đẳng thức biến phân . . . . . . . . . . . . . . 31 3.2 3.1.2 Bất đẳng thức biến phân affine . . . . . . . . . . . 32 Sự tồn tại nghiệm của bài toán bất đẳng thức biến phân affine 36 3.3 Giải bài toán quy hoạch toàn phương bằng cách đưa về bài toán bất đẳng thức biến phân affine . . . . . . . . . . . . . 40 Kết luận 44 Tài liệu tham khảo 45 1 Bảng ký hiệu R hx, yi tập số thực tích vô hướng của hai vectơ x và y kxk chuẩn của vectơ x I A ⊆ Rn ánh xạ đơn vị A là tập con trong Rn dim A af f E số chiều của tập A bao affine của E cone E coA bao nón sinh bởi E bao lồi của tập A 2 Lời nói đầu Bài toán quy hoạch toàn phương lồi là một lớp bài toán quan trọng về tối ưu vì bài toán này có rất nhiều ứng dụng trong thực tế. Bài toán bất đẳng thức biến phân cũng là một lớp bài toán quan trọng. Một lớp bài toán bất đẳng thức biến phân hay được xét là bài toán bất đẳng thức biến phân affine. Có thể nói bài toán bất đẳng thức biến phân affine là một dạng tổng quát của bài toán quy hoạch toàn phương với ràng buộc lồi. Trong luận văn này xét đến mối quan hệ giữa bài toán quy hoạch toàn phương với ràng buộc lồi với bài toán bất đẳng thức biến phân. Ta nhận thấy là bài toán quy hoạch toàn phương lồi có thể mô tả dưới một bài toán bất đẳng thức biến phân đơn điệu. Tuy nhiên, không phải mọi bài toán bất đẳng thức biến phân affine đều sinh ra từ bài toán quy hoạch toàn phương. Qua đây ta thấy sự phát triển từ bài toán quy hoạch toàn phương đến bất đẳng thức biến phân affine. Cụ thể trong luận văn gồm ba chương: Chương 1: Kiến thức chuẩn bị. Trình bày một số kiến thức cơ bản nhất về tập lồi, hàm lồi và hàm toàn phương như: tập affine và bao affine; tập lồi, nón lồi và bao lồi; điểm cực biên, phương lùi xa, nón lùi xa và phương cực biên; các định lý tách tập lồi; tập lồi đa diện; hàm lồi và các tính chất; hàm toàn phương. Chương 2: Bài toán quy hoạch toàn phương. Trình bày định nghĩa bài toán quy hoạch toàn phương, các dạng bài toán, điều kiện tồn tại nghiệm và điều kiện tối ưu của bài toán quy hoạch toàn phương. Chương 3: Bài toán bất đẳng thức biến phân affine. Giới thiệu về bài toán bất đẳng thức biến phân affine, điều kiện tồn tại nghiệm của bài toán bất đẳng thức biến phân affine và phương pháp giải bài toán quy hoạch toàn phương bằng cách đưa về bài toán bất đẳng thức biến phân affine. 3 Luận văn này được thực hiện tại Trường Đại học Khoa học – Đại học Thái Nguyên và hoàn thành dưới sự hướng dẫn của GS. TSKH. Lê Dũng Mưu. Tác giả xin được bày tỏ lòng biết ơn chân thành và sâu sắc tới người hướng dẫn khoa học của mình, người đã đặt vấn đề nghiên cứu, dành nhiều thời gian hướng dẫn và tận tình giải đáp những thắc mắc của tác giả trong suốt quá trình làm luận văn. Tác giả cũng đã học tập được rất nhiều kiến thức chuyên ngành bổ ích cho công tác và nghiên cứu của bản thân. Tác giả xin bày tỏ lòng cảm ơn sâu sắc tới các thầy giáo, cô giáo đã tham gia giảng dạy lớp Cao học Toán K9Y (khóa 2015–2017); Nhà trường và các phòng chức năng của Trường; 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ác giả trong suốt thời gian học tập tại trường. Tác giả cũng xin gửi lời cảm ơn tới tập thể lớp Cao học Toán K9Y (khóa 2015–2017) đã luôn động viên và giúp đỡ tác giả rất nhiều trong quá trình học tập, nghiên cứu. Cuối cùng, tôi xin gửi lời cảm ơn chân thành tới gia đình, bạn bè, lãnh đạo đơn vị công tác và đồng nghiệp đã động viên, giúp đỡ và tạo điều kiện tốt nhất cho tôi khi học tập và nghiên cứu. Thái Nguyên, ngày 05 tháng 9 năm 2017 Tác giả luận văn Nguyễn Thị Sim 4 Chương 1 Kiến thức chuẩn bị Chương này trình bày một số kiến thức cơ bản nhất về tập lồi, hàm lồi, hàm toàn phương. Cụ thể: Mục 1.1 giới thiệu khái niệm tập lồi, hàm lồi. Mục 1.2 trình bày định nghĩa hàm toàn phương. Các kiến thức của chương này được viết trên cơ sở tổng hợp từ các tài liệu [1], [2] và [3]. 1.1 1.1.1 Tập lồi Tập affine và bao affine Cho x1 , x2 là hai điểm trong Rn . Đường thẳng đi qua x1 , x2 là tập tất cả
các điểm x ∈ Rn có dạng x = (1 − λ ) x1 + λ x2 = x1 + λ x2 − x1 với λ ∈ R. Định nghĩa 1.1.1. Tập A ⊆ Rn được gọi là tập affine (hay đa tạp tuyến tính) nếu (1 − λ ) x + λ y ∈ A ∀x, y ∈ A ∀λ ∈ R. Nhận xét 1.1.1. Nếu A là tập affine, thì với a ∈ Rn , A + a = {x + a : x ∈ A} là tập affine. Mệnh đề 1.1.1. Tập M ⊂ Rn là không gian con khi và chỉ khi là tập affine chứa 0. Nghĩa là, nếu x, y ∈ M thì mọi điểm λ x + µy cũng thuộc M với λ , µ ∈ R. 5 Định lý 1.1.1. Mỗi tập affine A không rỗng là một tập affine khi và chỉ khi A = a + L trong đó a ∈ A và L là một không gian con. Chứng minh. Giả sử A là một tập affine và a ∈ A. Khi đó, A = a + L với L = −a + A. Do −a ∈ Rn nên L = −a + A cũng là một tập affine. Hơn nữa, 0 ∈ L (vì a ∈ A) nên L là một không gian con. Ngược lại, giả sử A = a + L với a ∈ A và L là một không gian con. Do không gian con L là một tập affine nên A = a + L cũng là một tập affine. Không gian con L nói trên được gọi là không gian con song song với tập affine A: A//M. Nó được xác định một cách duy nhất.  Định nghĩa 1.1.2. Chiều (thứ nguyên) của một tập affine A không rỗng được định nghĩa là chiều của không gian con song song với nó. Kí hiệu dimA. Chú ý 1.1.1. Quy ước: dim∅ = −1. Giả sử L là một không gian con trong Rn , phần bù trực giao của L được xác định như sau: L⊥ = {x ∈ Rn : x⊥y, ∀y ∈ L}, trong đó x⊥y ⇔ (x, y) = 0.
⊥ Khi đó, tập L⊥ cũng là một không gian con và dim L+dim L⊥ = n, L⊥ = L. Định nghĩa 1.1.3. Tập affine n − 1 chiều trong Rn được gọi là một siêu phẳng. Mệnh đề 1.1.2. Giả sử β ∈ R, 0 6= b ∈ Rn . Khi đó, tập H = {x ∈ Rn : hx, bi = β } là một siêu phẳng trong Rn . Hơn nữa, mọi siêu phẳng đều có thể biểu diễn duy nhất bằng cách này. Định nghĩa 1.1.4. Điểm x ∈ Rn có dạng x = λ1 x1 + λ2 x2 + ... + λk xk với xi ∈ Rn và λ1 + λ2 + ... + λk = 1 gọi là một tổ hợp affine của các điểm x1 , x2 , ..., xk . A là một tập affine khi và chỉ khi A chứa mọi tổ hợp affine các phần tử thuộc nó. Giao của một họ bất kì các tập affine cũng là một tập affine. Cho E là một tập bất kì trong Rn , có ít nhất một tập affine chứa E, cụ thể là Rn . 6 Định nghĩa 1.1.5. Giao của tất cả các tập affine chứa E gọi là bao affine (affine hull) của E, ký hiệu là a f f E. Đó là tập affine nhỏ nhất chứa E. Định nghĩa 1.1.6. Điểm x ∈ Rn được gọi là tổ hợp affine của điểm x1 , ...., xm ∈ Rn , nếu m m ∃λ1 , ...., λm ∈ R, ∑ λi = 1 : x = ∑ λi xi . i=1 i=1 Định nghĩa 1.1.7. Tập m + 1 điểm b0 , b1 , ..., bm được gọi là độc lập affine nếu a f f {b0 , b1 , ...., bm } là m chiều. Nhận xét 1.1.2. b0 , b1 , ..., bm độc lập affine khi và chỉ khi b1 −b0 , ..., bm −b0 độc lập tuyến tính. Thật vậy, a f f {b0 , b1 , ..., bm } = L + b0 trong đó, L = a f f {0, b1 − b0 , ..., bm − b0 }. Do đó, dim L = m ⇔ b1 − b0 , b2 − b0 , ..., bm − b0 độc lập tuyến tính. 1.1.2 Tập lồi, nón lồi và bao lồi Cho hai điểm x1 , x2 ∈ Rn . Đoạn nối x1 , x2 được định nghĩa như sau:  1 2  x ; x = x ∈ A : x = λ x1 + (1 − λ ) x2 , 0 6 λ 6 1 . Định nghĩa 1.1.8. Tập C ⊂ Rn được gọi là lồi nếu: ∀x1 , x2 ∈ C ∀λ ∈ R : 0 6 λ 6 1 thì λ x1 + (1 − λ ) x2 ∈ C. Nói cách khác, nếu C chứa trọn đoạn thẳng nối hai điểm bất kì thuộc nó. Ví dụ 1.1.1. Trong R2 các hình tam giác, hình chữ nhật, hình tròn, hình elip đều là các tập lồi. Trong R3 các hình cầu, khối lăng trụ tam giác, khối chóp tứ giác là các tập lồi. Các nửa không gian, hình cầu đơn vị trong không gian Banach là các tập lồi. Một số hình vẽ về tập lồi, tập không lồi trong R2 (xem Hình 1.1). 7 Hình 1.1: Định nghĩa 1.1.9. Vectơ x ∈ Rn được gọi là tổ hợp lồi của vectơ x1 , ..., xm ∈ m Rn nếu ∃λi > 0, i = 1, 2, ..., m sao cho x = ∑ λi xm . i=1 Chú ý 1.1.2. Tập C lồi khi và chỉ khi nó chứa mọi tổ hợp lồi của các phần tử thuộc nó. Thứ nguyên (hay số chiều) của một tập lồi C, ký hiệu dimC là thứ nguyên của bao affine của nó. Một tập lồi C trong Rn gọi là thứ nguyên đầy nếu dimC = n. Định nghĩa 1.1.10. Một tập con M của Rn được gọi là một nón (mũi tại 0) nếu x ∈ M, λ > 0 thì λ x ∈ M. Nón M gọi là nón lồi nếu tập M lồi. Điểm gốc 0 có thể thuộc hoặc không thuộc M. Tập a + M (a ∈ Rn ) gọi là nón có mũi tại a. Nón M không chứa đường thẳng nào gọi là nón nhọn. Trong trường hợp này, gốc 0 gọi là đỉnh của M và là nón có đỉnh tại a. Mỗi nửa không gian đóng hay mở đều là một nón, nhưng không phải là một nón nhọn. Định nghĩa 1.1.11. Cho E là một tập lồi. Tập {λ x : x ∈ E, λ > 0} gọi là bao nón sinh bởi E và kí hiệu là coneE. Định nghĩa 1.1.12. Giả sử A ∈ Rn . Tương giao của tất cả các tập lồi chứa A được gọi là bao lồi (Convex hull) của tập A và ký hiệu là coA. Nhận xét 1.1.3. a) coA là một tập lồi. Đó là tập lồi nhỏ nhất chứa A. b) A lồi ⇔ A = coA. 8 1.1.3 Điểm cực biên, phương lùi xa, nón lùi xa và phương cực biên Cho tập lồi M ⊂ Rn . Một x ∈ Rn được gọi là điểm cực biên của M nếu x không thể biểu diễn được dưới dạng tổ hợp lồi chặt của hai điểm phân biệt bất kì nào của M. Số điểm cực biên của tập lồi có thể hữu hạn hoặc vô hạn. Khi tập lồi có hữu hạn điểm cực biên thì chúng thường được gọi là các đỉnh. Mệnh đề 1.1.3. Một tập lồi đóng khác rỗng M ⊂ Rn có điểm cực biên khi và chỉ khi nó không chứa trọn một đường thẳng nào. Định lý Krein–Milman. Một tập lồi đóng, bị chặn trong Rn là bao lồi của các điểm cực biên của nó. Cho tập lồi khác rỗng M ⊂ Rn . Vectơ d ∈ Rn , d 6= 0 gọi là phương lùi xa của M nếu {x + λ d|λ > 0} ⊂ M với mỗi x ∈ M. Rõ ràng, mọi nửa đường thẳng song song với một phương lùi xa d xuất phát từ một điểm bất kì của M đều nằm trọn trong M. Tập M không bị chặn khi và chỉ khi nó có một phương lùi xa. Tập tất cả các phương lùi xa của tập lồi M cùng vectơ 0 tạo thành một nón lồi và được gọi là nón lùi xa của M. Hai phương d 1 , d 2 là khác biệt nếu d 1 6= αd 2 với α > 0. Phương lùi xa d của M được gọi là phương cực biên của M nếu không tồn tại các phương lùi xa khác biệt d 1 , d 2 của M sao cho d = λ1 d 1 + λ2 d 2 , λ1 , λ2 > 0. 1.1.4 Các định lý tách tập lồi Cho hai tập C, D ⊂ Rn và siêu phẳng H = {x ∈ Rn | ha, xi = α} với a ∈ Rn \ {0} và α ∈ R. Ta nói: + Siêu phẳng H tách hai tập C và D nếu: ha, xi 6 α 6 ha, yi ∀x ∈ C ∀y ∈ D. + Siêu phẳng tách hẳn (hay tách chặt) hai tập và nếu: ha, xi < α < ha, yi ∀x ∈ C ∀y ∈ D. 9 Định lý 1.1.2. (Định lý tách I) Nếu hai tập lồi C, D ⊂ Rn không rỗng và rời nhau thì có một siêu phẳng tách chúng. Định lý 1.1.3. (Định lý tách II) Nếu hai tập lồi đóng C, D ⊂ Rn không rỗng rời nhau và một trong hai tập ấy là compact thì có một siêu phẳng tách hẳn chúng. 1.1.5 Tập lồi đa diện Chúng ta nhắc lại rằng: Tập lồi đa diện P ⊂ Rn là giao của một số hữu hạn nửa không gian con đóng. Tập lồi đa diện là một tập lồi đóng. Nếu tập lồi đa diện bị chặn thì được gọi là đa diện lồi hay gọi tắt là đa diện. Mỗi điểm cực biên của tập lồi đa diện được gọi là đỉnh. Mỗi tập con lồi khác rỗng F của tập lồi đa diện P được gọi là một diện của P nếu hễ F chứa một điểm trong tương đối của một đoạn thẳng nào đó thuộc P thì F chứa trọn cả đoạn thẳng đó, nghĩa là: y, z ∈ P, x = λ y + (1 − λ ) z ∈ F, 0 < λ < 1 ⇒ y ∈ F, z ∈ F. Định lý 1.1.4. Cho P là tập lồi đa diện được xác định bởi: i  a , x 6 bi , i = 1, ..., m. Khi đó, tập con lồi khác rỗng F ⊂ Rn là một diện của P nếu và chỉ nếu: 
 F = x| ai , x = bi , i ∈ I; ai , x 6 bi , i ∈ /I   trong đó i| ai , x = bi , ∀x ∈ P = I0 ⊂ I ⊂ {1, ..., m}. Từ định lý trên suy ra, một diện của tập lồi đa diện cũng là một tập lồi đa diện và mỗi đỉnh của một diện cũng là một đỉnh của P.  Định lý 1.1.5. (Định lý biểu diễn tập lồi của đa diện) Giả sử x1 , ..., xN là  các tập đỉnh và d 1 , ..., d M là các phương cực biên của tập lồi đa diện P. 10 Khi đó, mỗi điểm x ∈ P đều có thể biểu diễn dưới dạng: N M x = ∑ λi xi + ∑ µ j d j i=1 j=1 N trong đó, λi > 0, i = 1, ..., N; µ j > 0, j = 1, ..., M; ∑ λi = 1. i=1 Ví dụ 1.1.2. Từ hình vẽ dưới đây cho thấy cách biểu diễn một điểm thuộc tập lồi đa diện qua các đỉnh và cạnh vô hạn (mà đại diện là phương cực biên) của tập đó. 1.1.6 Hàm lồi và tính chất Giả sử D ⊂ Rn , f : D → R ∪ {±∞}. Định nghĩa 1.1.13. Trên đồ thị (epigraph) của hàm f , ký hiệu là epi f được định nghĩa là: epi f = {(x, r) ∈ D × R : f (x) 6 r} . Định nghĩa 1.1.14. Miền hữu hiệu của hàm f , ký hiệu là dom f được định nghĩa là: dom f = {x ∈ D : f (x) < +∞} . Định nghĩa 1.1.15. Hàm f được gọi là chính thường nếu dom f 6=  và f (x) > −∞ (∀x ∈ D). Định nghĩa 1.1.16. Hàm f được gọi là lồi trên D nếu epi f là tập lồi trong X × R. Hàm f được gọi là lõm trên D nếu − f là hàm lồi trên D. 11 Nhận xét 1.1.4. Nếu f lồi thì dom f lồi. Thật vậy, dom f là hình chiếu trên X của epi f : dim f = {x : f (x) < +∞} = {x : ∃r, (x, r) ∈ epi f } . Như vậy, dom f là ảnh của tập lồi epi f qua một ánh xạ tuyến tính. Do đó, dom f lồi. Ví dụ 1.1.3. Chuẩn Euclide là một hàm lồi trên Rn : 1 kxk = hx, xi 2 = x1 2 , ..., xn 2
12 , trong đó x = (x1 , ..., xn ) ∈ Rn . Định lý 1.1.6. Giải sử D là tập lồi trong không gian Rn , hàm f : D → (−∞, +∞]. Khi đó, f lồi trên D khi và chỉ khi: f (λ x + (1 − λ )y) 6 λ f (x) + (1 − λ ) f (y) ∀λ ∈ [0, 1] ∀x, y ∈ D. Định nghĩa 1.1.17. Ta gọi f là hàm lồi chặt trên tập X nếu f (λ x1 +(1−λ )x2 ) < λ f (x1 )+(1−λ ) f (x2 ) ∀x1 , x2 ∈ X, x1 6= x2 , 0 < λ < 1. Định nghĩa 1.1.18. Hàm f được gọi là hàm lồi mạnh nếu tồn tại số λ dương sao cho bất đẳng thức sau đúng với mọi x, y thuộc D và λ ∈ [0; 1]: f (λ x + (1 − λ )y) 6 λ f (x) + (1 − λ ) f (y) − λ (1 − λ )α kx − yk2 . Nhận xét 1.1.5. Hàm lồi mạnh ⇒ lồi chặt, hàm lồi chặt ⇒ hàm lồi. Định nghĩa 1.1.19. Hàm f được gọi là đóng nếu epi f đóng trong X × R. Mệnh đề 1.1.4. Nếu f xác định trên tập lồi X ⊂ Rn là hàm lồi thì tập {x ∈ X| f (x) 6 α} là tập lồi với mọi α ∈ R. Cho hàm lồi f1 xác định trên tập lồi X1 ⊂ Rn , hàm lồi f2 xác định trên tập lồi X2 ⊂ Rn và số thực λ > 0. Ta định nghĩa các phép toán sau: (λ f1 (x)) = λ f1 , x ∈ X1 ; 12 ( f1 + f2 )(x) = f1 (x) + f2 (x), x ∈ X1 ∩ X2 ; max { f1 , f2 } (x) := max { f1 (x), f2 (x)} , x ∈ X1 ∩ X2 . Khi đó, ta có các kết quả sau: Mệnh đề 1.1.5. Cho f1 là hàm lồi trên tập X1 , f2 là hàm lồi trên tập X2 và các số thực α, β . Khi đó, các hàm α f1 + β f2 và max { f1 , f2 } là hàm lồi trên X1 ∩ X2 . Mệnh đề 1.1.6. Nếu f là hàm lồi xác định trên tập lồi mở X ⊂ Rn thì f là hàm lồi liên tục trên X. Định lý 1.1.7. Cho hàm f khả vi trên tập lồi mở X ⊂ Rn , khi đó f là hàm lồi khi và chỉ khi f (y) − f (x) > h∇ f (x), y − xi ∀x, y ∈ X. Định lý 1.1.8. Cho f là hàm khả vi hai lần trên tập lồi mở X ⊂ Rn , khi đó là hàm lồi khi và chỉ khi ma trận Hesse ∇2 f (x) xác định dương trên X. Áp dụng định trên cho hàm f (x) = 12 hx, Qxi + hx, ci + α trong đó Q là ma trận đối xứng cấp n × n . Khi đó f là hàm lồi (tương ứng, lồi chặt) trên nếu là ma trận nửa xác định dương (tương ứng, xác định dương). 1.2 1.2.1 Hàm toàn phương Ma trận xác định dương và ma trận nửa xác định dương Định nghĩa 1.2.1. Ma trận thực vuông, đối xứng C (cấp n) gọi là xác định dương nếu xT Cx > 0 với ∀x 6= 0 (x ∈ Rn ), gọi là nửa xác định dương (hay xác định không âm) nếu xT Cx > 0 với mọi x ∈ Rn . Ma trận C gọi là xác định âm (hay nửa xác định âm) nếu −C là xác định dương (nửa xác định dương). Mệnh đề 1.2.1. Một tử thức chính bất kỳ của ma trận xác định dương (nửa xác định dương) là ma trận xác định dương (nửa xác định dương). Mệnh đề 1.2.2. Nếu ma trận C nửa xác định dương và xT Cx = 0 thì Cx = 0. Mệnh đề 1.2.3. Nếu ma trận C xác định dương thì ma trận nghịch đảo C−1 tồn tại và xác định dương. 13 Mệnh đề 1.2.4. Nếu A là một ma trận tùy ý (vuông hay chữ nhật ) thì A AT và AT A là các ma trận nửa xác định dương. Mệnh đề 1.2.5. Ma trận đối xứng, lũy đẳng là ma trận nửa xác định dương. 1.2.2 Hàm toàn phương Định nghĩa 1.2.2. (Hàm toàn phương) Hàm f : Rn → R được gọi là hàm toàn phương nếu tồn tại ma trận D ∈ Rn×n , vectơ c ∈ Rn và số thực α sao cho: 1 f (x) = xT Dx + cT x + α 2 (1.1) 1 n = hx, Dxi + hc, xi + α ∀x ∈ R . 2       d11 ... d1n c1 x1            Nếu D =   ... ... ...  , c =  ... , x =  ... thì (1.1) có thể viết thành dn1 ... dnn cn xn f (x) = 1 2 n n ! n ∑ ∑ dijxix j + ∑ cixi + α. j=1 i=1 i=1
Ta có xT Dx = 12 xT D + DT x với mọi x ∈ Rn , công thức (1.1) không
thay đổi nếu ta thay ma trận D bởi ma trận đối xứng 21 D + DT . Do đó, ta có thể giả sử rằng ma trận vuông D trong công thức (1.1) là ma trận đối xứng. Các không gian của n × n – ma trận đối xứng sẽ được biểu thị bởi Rn×n S . Ví dụ 1.2.1. Cho hàm bậc hai f (x) = x1 2 − 2x2 2 + 4x1 x2 . Rõ ràng " f (x) #là 1 2 một dạng toàn phương. Ma trận D của dạng toàn phương là D = . 2 −2 Ví dụ 1.2.2. Cho hàm bậc hai g(x) = 2x1 2 − x2 2 + 2x1 x2 − 6x1 x3 + x2 x3 . Rõ ràng g(x)  là một dạng toàn  phương 3 biến. Ma trận D của dạng toàn phương 2 1 −3   1  . 1 −1 là D =    2   1 −3 0 2 14 Định nghĩa 1.2.3. Một dạng toàn phương chính tắc là dạng toàn phương mà trong biểu thức xác định không chứa tích xi x j mà chỉ chứa các số hạng bình phương xi 2 . Ví dụ 1.2.3. Cho hàm bậc hai f (x) = x1 2 + 2x2 2 − 3x3 2 là một dạng chính tắc. Định nghĩa 1.2.4. Dạng toàn phương f (x) = xT A x gọi là xác định dương nếu xT A x > 0 với mọi x 6= 0, nghĩa là A là ma trận xác định dương. Ví dụ 1.2.4. Dạng toàn phương f (x) ="x1 2 + x2 2#là xác định dương vì có 1 0 ma trận A của dạng toàn phương là A = . 0 1 Định nghĩa 1.2.5. Dạng toàn phương gọi là nửa xác định dương nếu xT A x > 0 với mọi x và tồn tại ít nhất một x 6= 0 (x ∈ Rn ) sao cho xT A x = 0 nghĩa là A là ma trận nửa xác định dương nhưng không xác định dương. Ví dụ 1.2.5. Dạng toàn phương f (x) = (x1 − x2 )2 > 0 ∀x1 , x2 và f (x) = 0 ⇒ x1 = x2 = 1, vì thế f (x) là nửa xác định dương. Định nghĩa 1.2.6. Dạng toàn phương f (x) = xT A x gọi là xác đinh âm (nửa xác định âm) nếu − f (x) là xác định dương (nửa xác định dương). Với dạng toàn phương ta có thể kiểm tra tính xác định dương của nó nhờ dùng tính chất sau. * Dạng toàn phương f (x) = xT A x là xác định dương khi và chỉ khi mọi định thức con chính của  A đều dương.  Chẳng hạn, với n = 4 ta phải có      a11 a12 a13   a11 a12      a11 > 0,   > 0,  a21 a22 a23  > 0 và |A| > 0.  a21 a22     a31 a32 a33  Định nghĩa 1.2.7. Dạng toàn phương gọi là không xác định dấu nếu tồn tại x1 , x2 ∈ Rn \ {0} sao cho x1T A x1 > 0 và x2T A x2 < 0. 15 Chương 2 Bài toán quy hoạch toàn phương Chương này trình bày các kiến thức cơ bản về bài toán quy hoạch toàn phương. Cụ thể, Mục 2.1 giới thiệu bài toán quy hoạch toàn phương và nêu điều kiện tồn tại nghiệm của bài toán quy hoạch toàn phương. Mục 2.2 nêu điều kiện tối ưu (điều kiện Karush–Kuhn–Tucker). Các kiến thức của chương này được viết trên cơ sở của các tài liệu [4] và [5]. 2.1 Giới thiệu bài toán và sự tồn tại nghiệm 2.1.1 Định nghĩa bài toán quy hoạch toàn phương Định nghĩa 2.1.1. Bài toán min { f (x)|x ∈ ∆} trong đó hàm mục tiêu f là hàm toàn phương, tập ràng buộc ∆ ⊂ Rn là tập lồi đa diện được gọi là bài toán quy hoạch toàn phương (hay quy hoạch toàn phương) với ràng buộc tuyến tính. Nếu D là ma trận không, thì f là hàm tuyến tính. Do đó, lớp các bài toán quy hoạch tuyến tính là lớp con của lớp các bài toán quy hoạch toàn phương. Nếu f là hàm lồi thì bài toán min { f (x)|x ∈ ∆} được gọi là quy hoạch toàn phương lồi. Nếu f không là hàm lồi thì bài toán min { f (x)|x ∈ ∆} được gọi là quy hoạch toàn phương không lồi. Nếu ta bỏ đi hằng số α trong công thức của f thì ta vẫn không làm thay đổi tập nghiệm của bài toán quy hoạch toàn phương ban đầu. Do đó ta chỉ cần xét bài toán  min 1 f (x) = xT Dx + cT x| x ∈ ∆ 2  (2.1) 16  Nếu ta thay ma trận A = 12 D thì bài toán min f (x) = 12 xT Dx + cT x| x ∈ ∆  trở thành min f (x) = xT A x + cT x|x ∈ ∆ . Ví dụ 2.1.1. Cho bài toán quy hoạch toàn phương  min f (x) = −x1 2 + x2 2 : x = (x1 , x2 ) , 1 6 x1 6 3, 1 6 x2 6 3 . Ta có : 1 f (x) = (x1 + x2 ) 2 " #" # −2 0 x1 0 2 x2  ∆ = x|x = (x1 , x2 ) ∈ R2 ; 1 6 x1 , x2 6 3 . Định lý 2.1.1. Cho hàm f (x) = 12 xT D x + cT x + α trong đó D ∈ Rn×n s ,b∈ Rn , α ∈ R nếu D là ma trận nửa đối xứng xác định dương thì f là hàm lồi. Chứng minh. Ta có, hàm x → cT x + α là hàm lồi và tổng của hai hàm lồi là một hàm lồi. Do đó, ta chỉ cần chứng minh f1 (x) := xT D x là hàm lồi. Thật vậy, vì D là ma trận nửa xác định dương nên với mọi u ∈ Rn , v ∈ Rn , ta có 0 6 (u − v)T D(u − v) = uT D u − 2vT D u + vT D v ⇒ vT D v 6 uT D u − 2vT D(u − v). (2.2) Lấy x ∈ Rn , y ∈ Rn bất kỳ, t ∈ (0; 1), ta đặt: z = tx + (1 − t)y. Kết hợp với (2.2) ta có : zT D z 6 yT D y − 2zT D (y − z) zT D z 6 xT D x − 2zT D (x − z) Vì y − z = t(y − x) và x − z = (1 − t)(x − y) nên (1 − t)zT D z + t zT D z 6 (1 − t)yT D y + txT D x. Suy ra: f1 (tx + (1 − t)y) = f1 (z) 6 t f1 (x) + (1 − t) f1 (y). Vậy, f là hàm lồi. Nhận xét 2.1.1. Nếu ma trận D trong hàm mục tiêu của bài toán quy hoạch toàn phương là ma trận nửa xác định dương thì bài toán được gọi là quy hoạch toàn phương lồi.