Tài liệu Qui hoạch toàn phương và bài toán bù tuyến tính

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

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

Mô tả:

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC HÀ THỊ MINH TRANG QUI HOẠCH TOÀN PHƯƠNG VÀ BÀI TOÁN BÙ TUYẾN TÍNH Quadratic Programming and the Linear Complementarity Problem 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 - 2014 Mục lục Lời nói đầu 2 Chương 1. Kiến thức chuẩn bị về ma trận 4 1.1 Ma trận xác định dương và nửa xác định dương . . . . . . . . . . 4 1.2 Một số kết quả về ma trận . . . . . . . . . . . . . . . . . . . . . . 6 1.3 P - ma trận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.4 Kiểm tra tính xác định của ma trận . . . . . . . . . . . . . . . . . 12 1.5 Hàm lồi và hàm toàn phương . . . . . . . . . . . . . . . . . . . . 15 Chương 2. Bài toán qui hoạch toàn phương 18 2.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2 Một số ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3 Sự tồn tại nghiệm tối ưu . . . . . . . . . . . . . . . . . . . . . . . 22 2.4 Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 Chương 3. Bài toán bù tuyến tính 30 3.1 Nội dung bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.2 Khái niệm nón bù . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.3 Phương pháp liệt kê giải bài toán . . . . . . . . . . . . . . . . . . 35 3.4 Ứng dụng vào qui hoạch tuyến tính . . . . . . . . . . . . . . . . . 39 3.5 Quan hệ với qui hoạch toàn phương . . . . . . . . . . . . . . . . . 41 Kết luận 43 1 Lời nói đầu Qui hoạch toàn phương (Quadratic Programming, viết tắt là QP) là bài toán tìm cực tiểu của một hàm bậc hai với các ràng buộc tuyến tính: 1 min{f (x) = xT Qx + cT x : x ∈ D}, (QP) 2 trong đó Q ∈ S n (ma trận vuông đối xứng), c ∈ Rn và D là tập lồi đa diện cho trước. Nếu Q xác định dương hay nửa xác định dương thì (QP) là bài toán qui hoạch toàn phương lồi, còn nếu Q không xác định thì (QP) là bài toán qui hoạch toàn phương không lồi. Các bài toán qui hoạch toàn phương rất được quan tâm nghiên cứu, vì nhiều vấn đề nảy sinh trong thực tiễn có thể diễn đạt dưới dạng bài toán (QP). Qui hoạch toàn phương, nói riêng là qui hoạch tuyến tính (Linear Programming, viết tắt là LP), liên quan chặt chẽ với bài toán bù tuyến tính. Bài toán bù tuyến tính (Linear Complementarity Problem, viết tắt là LCP), do R. W. Cottle và G. B. Dantzig [2] đề xuất năm 1968, là bài toán tổng quát mô tả thống nhất các bài toán qui hoạch tuyến tính, qui hoạch toàn phương và trò chơi song ma trận. Các nghiên cứu về bài toán bù tuyến tính đã đem lại nhiều lợi ích, vượt xa các kết quả cụ thể. Chẳng hạn, thuật toán xoay bù (complementarity pivot algorithm) lúc đầu được đề xuất cho bài toán bù tuyến tính đã được mở rộng trực tiếp để tạo ra các thuật toán hiệu quả tính điểm bất động Brouwer và Kakutani, tính các trạng thái cân bằng kinh tế, giải các hệ phương trình phi tuyến và tìm nghiệm tối ưu cho bài toán qui hoạch phi tuyến. Tương tự, các phương pháp lặp được đề xuất cho bài toán bù tuyến tính đã tạo điều kiện tốt cho việc xử lý các bài toán qui hoạch tuyến tính cỡ rất lớn mà không thể giải quyết bằng phương pháp đơn hình quen thuộc, do kích thước bài toán quá lớn đã gây ra nhiều khó khăn trong tính toán số. Vì những lẽ đó, trong lĩnh vực nghiên cứu bài toán bù tuyến tính người ta đã dành nhiều giải thưởng có giá trị cao cho những ai có thành tích xuất sắc trong học tập hoặc nghiên cứu về tối ưu hóa hoặc gắn bó với sự nghiệp ứng dụng tối ưu trong thực tiễn. 2 Mục tiêu của luận văn là tìm hiểu và trình bày khái quát về bài toán qui hoạch toàn phương (lồi và không lồi ), bài toán bù tuyến tính và phân tích mối quan hệ giữa bài toán qui hoạch toàn phương và bài toán bù tuyến tính. Nội dung luận văn được viết thành ba chương: Chương 1: “Kiến thức chuẩn bị về ma trận” nhắc lại khái niệm về ma trận xác định dương, nửa xác định dương và tóm tắt một số kết quả lý thuyết bổ ích về ma trận, cách kiểm tra tính xác định của ma trận. Các ma trận xác định dương và nửa xác định dương liên quan chặt chẽ với hàm toàn phương và qui hoạch toàn phương. Các kiến thức này sẽ được sử dụng đến ở các chương sau khi đề cập đến bài toán qui hoạch toàn phương và bài toán bù tuyến tính. Chương 2: “Bài toán quy hoạch toàn phương” trình bày nội dung bài toán qui hoạch toàn phương, một số ứng dụng của bài toán, sự tồn tại nghiệm của bài toán, đáng chú ý là Định lý Frank - Wolfe (1956) và Định lý Eaves (1971). Cuối chương trình bày định lý về điều kiện cần tối ưu KKT cho nghiệm cực tiểu địa phương và định lý điều kiện đủ tối ưu khi hàm mục tiêu f(x) lồi. Chương 3: “Bài toán bù tuyến tính” giới thiệu khái quát về bài toán bù tuyến tính và cách tiếp cận tổ hợp giải bài toán dựa trên khái niệm nón bù. Phân tích mối quan hệ của bài toán bù tuyến tính với qui hoạch tuyến tính và qui hoạch toàn phương, đặc biệt chỉ ra rằng bài toán qui hoạch tuyến tính và bài toán qui hoạch toàn phương có thể qui được về bài toán bù tuyến tính. Do thời gian và kiến thức còn hạn chế nên chắc chắn luận văn này còn có những thiếu sót nhất định, kính mong quí thầy cô và các bạn đóng góp ý kiến để tác giả tiếp tục hoàn thiện luận văn này. Trong quá trình học tập và thực hiện luận văn, tôi đã nhận được sự dạy bảo tận tình của các thầy cô giáo ở trường Đại học Khoa Học - Đại học Thái Nguyên. Đặc biệt là sự chỉ bảo, hướng dẫn trực tiếp của GS. TS Trần Vũ Thiệu. Nhân dịp này tôi xin bày tỏ lòng biết ơn sâu sắc tới GS. TS Trần Vũ Thiệu, tới Sở Giáo dục và Đào tạo Hải Phòng, trường THPT An Dương - Hải Phòng, các thầy cô giáo và các bạn đồng nghiệp đã giúp đỡ tôi trong suốt thời gian qua. Thái Nguyên, tháng 4 năm 2014 Tác giả Hà Thị Minh Trang Chương 1 Kiến thức chuẩn bị về ma trận Chương này nhắc lại khái niệm về ma trận xác định dương, nửa xác định dương và nêu một số kết quả lý thuyết hữu ích về ma trận, cách kiểm tra tính xác định của ma trận. Các ma trận xác định dương và nửa xác định dương liên quan chặt chẽ với hàm toàn phương và qui hoạch 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] - [5]. 1.1. Ma trận xác định dương và nửa xác định dương Mục này nhắc lại khái niệm về ma trận xác định dương và nửa xác định dương thường gặp trong qui hoạch toàn phương và bài toán bù tuyến tính. Định nghĩa 1.1. Ma trận Q vuông cấp n, đối xứng hay không đối xứng, gọi là xác định dương (positive definte matrix) nếu xT Qx > 0 với mọi x ∈ Rn , x 6= 0; Q gọi là nửa xác định dương (positive definte matrix) nếu xT Qx ≥ 0 với x ∈ Rn . Ma trận Q gọi là xác định âm (negative definite matrix) (nửa xác định âm - negative semidefinite matrix) nếu - Q là xác định dương (nửa xác định dương). Ma trận Q gọi là không xác định (indefinite matrix) nếu xT Qx dương với x này và âm với x khác.  Nếu Q không đối xứng, ta có thể thay nó bằng ma trận đối xứng Q + QT /2  mà không làm thay đổi tính xác định của ma trận, bởi vì xT Q + QT x = 2xT Qx. Ví dụ 1.1. Cho các ma trận ! 1 −1 A= ,B= −1 2 D= −1 1 1 −1 1 −1 −1 ! 1 ,E= 4 ! ,C= 1 0 0 −1 ! −2 1 1 −2 ! Có thể thấy A xác định dương, B nửa xác định dương, C xác định âm, D nửa xác định âm và E không xác định. Định nghĩa 1.2. Cho Q = (qij ) là ma trận vuông cấp n. Giả sử {i1 , . . . , ik } ⊆ {1, . . . , n} là tập chỉ số với các phần tử xếp theo thứ tự tăng dần. Xóa tất cả các phần tử của Q ở hàng i và cột i với i ∈ / {i1 , . . . , ik }, ta nhận được ma trận con cấp k × k của Q   qi1 i1 · · · qi1 ik  . ..  ...  .. .    qik i1 · · · qik ik Ma trận này gọi là ma trận con chính (principal submatrix) của Q xác định bởi tập chỉ số {i1 , . . . , ik }. Bằng cách đặt J = {i1 , . . . , ik }, ta ký hiệu ma trận con chính là QJJ . Đó là ma trận (qij : i ∈ J, j ∈ J}. Định thức của ma trận con chính gọi là định thức con chính (principal determinatnt) của Q xác định bởi tập chỉ số J. Ma trận con chính của Q xác định bởi tập J = ∅ (tập rỗng) là ma trận rỗng (không chứa phần tử nào). Qui ước định thức của ma trận rỗng bằng 1. Ma trận con chính của Q xác định bởi tập J = {1, . . . , n} chính là Q. Ma trận con chính của Q xác định bởi tập J 6= ∅ gọi là ma trận con chính khác rỗng (non-empty principal submatrix) của Q. Do số tập con khác rỗng của {1, . . . , n} là 2n − 1 nên có tất cả 2n − 1 ma trận con chính khác rỗng của Q. Các ma trận con chính của Q xác định bởi tập chỉ số J ⊂ {1, . . . , n} gọi là ma trận con chính thực sự (proper principal submatrix) của Q. Vì thế, mỗi ma trận con chính thực sự của Q có cấp k ≤ n − 1. Ví dụ 1.2. Cho  1 2 3     Q= 4 5 6   7 8 9 Ma trận con chính cấp 1, lần lượt tương ứng với J = {1} , {2} và {3}, là các phần tử đường chéo 1, 5 và 9. Ma trận con chính cấp 2, lần lượt tương ứng với J = {1, 2} , {1, 3} và {2, 3} là các ma trận 2 × 2 sau đây: ! ! ! 1 2 1 3 5 6 , và 4 5 7 9 8 9 5 Ma trận con chính cấp 3 × 3, tương ứng với J = {1, 2, 3}, chính là Q. Có tất cả 23 − 1 = 7 ma trận con chính khác rỗng. Định nghĩa 1.3. Ma trận con chính cấp k của Q, xác định bởi tập chỉ số J = {1, . . . , k}, tức là ma trận nhận được từ Q bằng cách bỏ đi n − k hàng và cột cuối, gọi là ma trận con chính chủ đạo (leading principal submatrix) cấp k của Q. Định thức của ma trận con chính chủ đạo được gọi là định thức con chính chủ đạo (leading principal subdeterminant). Trong Ví dụ 1.2, ma trận con chính chủ đạo cấp 1 là 1 (bỏ đi 2 hàng và 2 cột cuối). Ma trận con chính chủ đạo cấp 2 là ma trận con chính thứ nhất trong 3 ma trận con chính cấp 2 đã liệt kê và ma trận con chính chủ đạo cấp 3 chính là Q. Số ma trận con (định thức con) chính chủ đạo của ma trận cấp n × n bằng n. 1.2. Một số kết quả về ma trận Mục này nêu một số kết quả hữu ích trong nghiên cứu các ma trận xác định dương và nửa xác định dương. Kết quả 1.1. Nếu A = (a11 ) là ma trận cấp 1 × 1 thì A xác định dương khi và chỉ khi a11 > 0 và A nửa xác định dương khi và chỉ khi a11 ≥ 0. Chứng minh.Giả sử y = (y1 ) ∈ R1 . Khi đó, yT Ay =a11 y12 . Vì thế yT Ay > 0 với mọi y ∈ R1 , y 6= 0, khi và chỉ khi a11 > 0, do đó A xác định dương khi và chỉ khi a11 > 0. Cũng vậy, yT Ay ≥ 0 với mọi y ∈ R1 khi và chỉ khi a11 ≥ 0, do đó A nửa xác định dương khi và chỉ khi a11 ≥ 0.  Kết quả 1.2. Nếu Q là ma trận xác định dương (đối xứng hay không đối xứng) thì mọi ma trận con chính của Q đều xác định dương. Chứng minh. Xét ma trận con chính G xác định bởi tập chỉ số {1, 2}. ! ! q11 q12 y1 G= . Giả sử z = q21 q22 y2 Lấy y = (y1 , y2 , 0, 0, ..., 0)T . Khi đó y T Qy = z T Gz. Tuy nhiên, do Q xác định dương nên y T Qy > 0 với mọi y 6= 0. Do vậy z T Gz > 0 với mọi z 6= 0. Vì thế G cũng xác định dương. Dùng lập luận tương tự có thể chứng minh rằng mọi ma trận con chính của Q cũng xác định dương. 6  Kết quả 1.3. Nếu Q xác định dương thì qii > 0 với mọi i. Chứng minh suy từ Kết quả 1.2 Kết quả 1.4. Nếu Q là ma trận nửa xác định dương (đối xứng hay không đối xứng) thì mọi ma trận con chính của Q cũng nửa xác định dương. Chứng minh tương tự như trong chứng minh Kết quả 1.2. Kết quả 1.5. Nếu Q là ma trận nửa xác định dương thì qii ≥ 0 với mọi i. Chứng minh suy từ Kết quả 1.4. Kết quả 1.6. Cho Q là ma trận nửa xác định dương. Nếu qii = 0 thì qij + qji = 0 với mọi j khi Q không đối xứng và qij = qji = 0 với mọi j khi Q đối xứng. Chứng minh. Để xác định, giả sử q11 = 0 và giả sử q12 + q21 6= 0. Theo kết quả 1.4, ma trận con chính: q11 q12 ! = q21 q22 0 q12 ! q21 q22 phải nửa xác định dương, nghĩa là q22 y22 + (q12 + q21 ) y1 y2 ≥ 0 với mọi y1 , y2 . Do q12 + q21 6= 0 nên nếu chọn y1 = (−q22 − 1) / (q12 + q21 ) và y2 = 1 thì bất đẳng thức trước đó trở thành −1 ≥ 0, ta gặp mâu thuẫn. Vậy phải có q12 + q21 = 0. Trường hợp Q đối xứng thì q12 = q21 . Theo trên q12 + q21 = 0. Từ đó suy ra 2q12 = 2q21 = 0, tức q12 = q21 = 0.  Định nghĩa 1.4. (Bước xoay Gauss - Gaussian Pivot Step). Cho A = (aij ) là ma trận cấp m × n. Phần tử ở hàng r, cột s là ars . Với ars 6= 0, bước xoay Gauss biến đổi ma trận A theo công thức: aij → a0ij = aij − arj × (ais /ars ) với mọi i = r + 1, ... , m và mọi j = 1, ..., n tức là trừ mỗi hàng i > r một bội số thích hợp (cụ thể là ais /ars ) của hàng r. Có thể thấy a0is = 0 với mọi i > r. Ở bước xoay này, hàng r gọi là hàng xoay (pivot row), cột s gọi là cột xoay (pivot column) và ars gọi là phần tử trụ(pivot element). Bước xoay Gauss này gọi tắt là phép xoay (r, s) trên A và nó chỉ thực hiện được khi ars 6= 0 (r < m). Ví dụ 1.3. Phép xoay (1, 2) (a12 = 2 là phần tử trụ) trên ma trận A biến A thành B: 7     2 2 −2 0 2 2 −2 0      ⇒ B =  3 0 4 2 . A = 4 1 3 2     2 −2 0 1 4 0 −2 1 Kết quả 1.7. Cho D là một ma trận vuông đối xứng cấp n ≥ 2. Giả sử D xác định dương. Thực hiện phép xoay (1, 1) trên D để biến mọi phần tử ở cột 1, trừ phần tử đầu, thành 0. Ta nhận được ma trận E. Giả sử E1 là ma trận con nhận được từ E bằng cách bỏ đi hàng 1 và cột 1. Khi đó, E1 vẫn còn đối xứng và xác định dương. Ví dụ 1.4. Với phép xoay (1, 1) trên ma trận D vuông đối xứng xác định dương (cấp 3) ta nhận được ma trận E1 vuông đối xứng xác định dương (cấp 2): Kết quả 1.8. Ma trận vuông Q là xác định dương (hay nửa xác định dương) khi và chỉ khi Q + QT xác định dương (hay nửa xác định dương).  Chứng minh. Suy ra từ đẳng thức xT Q + QT x = 2xT Qx  Kết quả 1.9. Giả sử Q là ma trận vuông cấp n và A là ma trận cấp m × n. Khi đó ma trận vuông: E= Q −AT A ! 0 cấp (m + n) là nửa xác định dương khi và chỉ khi Q nửa xác định dương. T T Chứng minh. Đặt z = (y1 , ..., yn , t1 , ..., tm ) ∈ Rm+n và y = (y1 , ..., yn ) . Với mọi z ta có zT Ez = yT Qy. Vì thế zT Ez ≥ 0 với mọi z ∈ Rm+n khi và chỉ khi yT Qy ≥ 0 với mọi y ∈ Rn , nghĩa là E nửa xác định dương khi và chỉ khi Q nửa xác định  dương. Kết quả 1.10. Nếu B là ma trận vuông (cấp n) không suy biến thì ma trận D = BT B là ma trận đối xứng và xác định dương. T Chứng minh. Tính đối xứng là do DT = BT B = BT B = D. Với mọi y ∈  T 2 Rn , y 6= 0, ta có yT Dy = yT BT B y = (By) By = ||By|| > 0 do By 6= 0(B không suy biến và y 6= 0 kéo theo By 6= 0). Vì thế D xác định dương. 8  Kết quả 1.11. Nếu A là một ma trận tùy ý (vuông hay chữ nhật) thì AAT và AT A là đối xứng và nửa xác định dương.  Chứng minh. Tương tự như chứng minh Kết quả 1.10. Ví dụ 1.5. Với ma trận A cho dưới đây thì AAT xác định dương và AT A nửa xác định dương  1 0  A= ⇒ AT =  0 1 0 1 −1 1 −1  ! 1  2 −1 ⇒ AAT = , AT A =  0 −1 2 1 1 0 1  !    0 1   −1  . −1 2 1 • Nếu Q xác định dương thì nghịch đảo Q−1 tồn tại và xác định dương • Sau đây là một số kết quả liên quan đến định thức con chính của các ma trận xác định dương và nửa xác định dương. Kết quả 1.12. Cho Q là một ma trận xác định dương, đối xứng hay không đối xứng. Mọi định thức con chính của Q là số dương. Nói riêng, detQ > 0. Kết quả 1.13. Cho Q là một ma trận nửa xác định dương, đối xứng hay không đối xứng. Mọi định thức con chính của Q không âm. Nói riêng, detQ ≥ 0. Kết quả 1.14. (Tiêu chuẩn Silvester). a) Để cho ma trận vuông đối xứng Q là xác định dương thì điều kiện cần và đủ là mọi định thức con chính chủ đạo của Q dương, tức ∆1 > 0, ∆2 > 0, ... , ∆n > 0, trong đó q q 11 12 ∆1 = |q11 | , ∆2 = q21 q22 q11 q12 q 21 q22 , ..., ∆n = . .. .. . qn1 qn2 ··· ··· ... ··· q1n q2n .. . . qnn b) Để cho ma trận vuông đối xứng Q là xác định âm thì điều kiện cần và đủ là các định thức con chính chủ đạo của Q luân phiên đổi dấu, trong đó định thức n đầu tiên có dấu âm, tức là ∆1 < 0, ∆2 > 0, ..., (−1) ∆n > 0. 9 Ví dụ 1.6. Khác với Kết qủa 1.14, một ma trận vuông đối xứng có mọi định thức con chính chủ đạo không âm, nhưng ma trận đó không nửa xác định dương, như chỉ ra ở ma trận Q sau đây:   1 0 −1   có ∆1 = 1 > 0, ∆2 = Q= 0 0 0   −1 0 −1 1 0 0 0 ! = 0 và ∆3 = detQ = 0 T nhưng Q không nửa xác định dương, do (0, 0, 1) Q(0, 0, 1) = − 1 < 0 Kết quả 1.15. Một ma trận vuông đối xứng là xác định dương khi và chỉ khi mọi định thức con chính của nó thực sự dương. Chứng minh. Suy ra từ các Kết quả 1.12 và 1.14.  Nhận xét 1.1. Điều đáng chú ý là nếu Q là ma trận vuông đối xứng cấp n và nếu n định thức con chính chủ đạo (xem Định nghĩa 1.3) của Q là số dương thì theo các Kết quả 1.14 và 1.15, mọi định thức con chính của Q cũng là số dương. Kết quả này có thể sai nếu Q không đối xứng. Có thể chứng minh kết quả đáng chú ý sau. Kết quả 1.16. Nếu Q là một ma trận vuông đối xứng nửa xác định dương và nếu detQ > 0 thì Q xác định dương. Nhận xét 1.2. Kết quả trên có thể không còn đúng nếu Q không đối xứng. Chẳng hạn, ma trận Q dưới đây nửa xác định dương (theo Kết quả 1.9) và detQ > 0, nhưng Q không xác định dương (theo Kết quả 1.3) do Q không đối xứng: ! 1 −1 Q= , detQ = 1 > 0 1 0 Kết quả 1.17. Cho Q là một ma trận vuông cấp n nửa xác định dương, đối xứng  hay không đối xứng, nếu x̄ ∈ Rn sao cho x̄T Qx̄ = 0 thì Q + QT x̄ = 0 Chứng minh. Đặt D = Q + QT . D là ma trận đối xứng và nửa xác định dương (theo Kết quả 1.8). Với mọi x ∈ Rn thì xT Dx = 2xT Qx. Vì thế cũng có x̄T Dx̄ = 0. Ta cần chứng minh rằng Dx̄ = 0. Thật vậy, lấy bất kỳ x ∈ Rn . Với mọi λ ∈ Rn ta có (x̄ + λx)T D(x̄ + λx) ≥ 0, nghĩa là: λ2 xT Dx + 2λx̄T Dx̄ ≥ 0 10 do x̄T Dx̄ = 0. Nếu xT Dx = 0 thì ở bất đẳng thức trên cho λ = 1, sau đó - 1 ta suy ra x̄T Dx = 0. Còn nếu xT Dx 6= 0 thì do D nửa xác định dương nên xT Dx > 0. Trong trường hợp này, ta kết luận rằng 2x̄T Dx ≥ −λxT Dx với mọi λ > 0 và 2x̄T Dx ≤ −λxT Dx với mọi λ < 0. Chọn λ nhỏ tùy ý về giá trị tuyệt đối, từ các bất đẳng thức trên ta kết luận rằng trong trường hợp này phải có x̄T Dx = 0. Vậy, dù xT Dx = 0 hay xT Dx 6= 0 ta đều có xT Dx = 0 với mọi x ∈ Rn . Từ đó suy ra phải có x̄T D = 0 hay Dx̄ = 0 (nhớ là D đối xứng). Đó là điều cần chứng  minh 1.3. P - ma trận Mục này đề cập tới một lớp ma trận đặc biệt thường gặp trong các ứng dụng có tên gọi là P - ma trận. Định nghĩa 1.5. Một ma trận vuông, đối xứng hay không đối xứng, gọi là một P - ma trận (P - matrix) nếu và chỉ nếu mọi định thức con chính của nó đều thực sự dương. ! Ví dụ 1.7. Các ma trận sau là P - ma trận: 1 −1 Ma trận đơn vị I, , −1 2 1 2 Các ma trận sau không phải là P - ma trận: ! ! 0 1 −1 0 , , 0 1 0 10 ! ! 0 3 1 1 1 1 Kết quả 1.18. Một P - ma trận đối xứng là ma trận xác định dương. Một P ma trận không đối xứng có thể không xác định dương. Chứng minh. Theo Kết qủa 1.15, ma trận vuông đối xứng là xác định dương khi và chỉ khi nó là một P - ma trận. Xét ma trận không đối xứng: ! ! 1 0 2 3 B= , B + BT = 3 1 3 2 Ta thấy mọi định thức con chính của B bằng 1 nên B là một P - ma trận. Tuy   nhiên, vì det B + BT = − 5 < 0 nên theo Kết quả 1.12, B + BT không xác định dương, do đó theo Kết quả 1.8, B cũng không xác định dương. Thực ra có T thể kiểm tra thấy (1, − 1) B(1, − 1) = − 1 < 0. 11  Nhận xét 1.3. Theo Kết quả 1.15 và Định nghĩa 1.5, lớp ma trận xác định dương là một lớp con của lớp P - ma trận. Theo Kết quả 1.18, khi hạn chế ở ma trận đối xứng, tính chất của ma trận xác định dương trùng với tính chất của P - ma trận. Một P - ma trận không đối xứng có thể không xác định dương, như ma trận B cho trong chứng minh Kết quả 1.18, nhưng nó có thể nửa xác định dương, như ma trận M̃ (n) cho dưới đây, hoặc không  1  2  M̃ (n) =  .  ..  2 nửa xác định dương.  0 ··· 0  1 ··· 0   .. . . ..  . .  .  2 ··· 1 là ma trận tam giác dưới với mọi phần tử đường chéo bằng 1 và mọi phần tử dưới đường chéo bằng 2. Rõ ràng mọi định thức con chính của M̃ (n) bằng 1, do đó  T M̃ (n) là một P - ma trận. Tuy nhiên, M̃ (n) + M̃ (n) là ma trận với mọi phần tử bằng 2. Có thể kiểm tra lại rằng đó là ma trận nửa xác định dương, nhưng không xác định dương. 1.4. Kiểm tra tính xác định của ma trận • Có một số qui tắc kiểm tra đơn giản để nhận biết một ma trận vuông đối xứng cấp n là xác định dương (xác định âm), nửa xác định dương (nửa xác định âm) hay không xác định. Các qui tắc kiểm tra này chỉ đúng khi ma trận là đối  xứng. Nếu Q = (qij ) không đối xứng thì cần thay Q bởi Q + QT /2, rồi mới tiến hành kiểm tra. a) Kiểm tra ma trận xác định dương: Mọi định thức con chính chủ đạo của Q phải là số dương (Kết quả 1.14). Nói riêng, mọi phần tử đường chéo phải dương (Kết qủa 1.3), tức qii > 0 với mọi i = 1, ... , n. b) Kiểm tra ma trận nửa xác định dương: Mọi định thức con chính của Q phải không âm (suy từ Kết quả 1.13). Nói riêng, mọi phần tử đường chéo phải không âm (Kết quả 1.5), tức qii ≥ 0 với mọi i = 1, ... , n. Nhận xét 1.4. a) Cần phân biệt rõ sự khác nhau khi kiểm tra các ma trận xác định dương và nửa xác định dương: Để ma trận xác định dương, chỉ cần kiểm tra các định thức con chính chủ đạo dương là đủ, trong khi đó để ma trận nửa xác định dương ta cần kiểm tra mọi định thức con chính không âm. 12 b) Để chỉ rõ ma trận xác định âm (nửa xác định âm), ta chỉ cần kiểm tra ma trận đối của ma trận đó là xác định dương (nửa xác định dương). c) Nếu thấy ma trận vuông đối xứng có (ít nhất) hai phần tử đường chéo trái dấu nhau thì chắc chắn ma trận đó không xác định. Qui tắc kiểm tra tính xác định dương (xác định âm) của ma trận đã nêu trên dựa vào tiêu chuẩn Silvester nêu trong Kết quả 1.14. Tuy nhiên, đây không phải là một phương pháp hiệu quả (trừ khi n rất nhỏ) bởi vì việc tính các định thức con chính chủ đạo tốn khá nhiều thời gian và công sức. • Sau đây là một phương pháp khác kiểm tra tính xác định dương của ma trận vuông (cấp n) đối xứng Q, chỉ đòi hỏi nhiều nhất n bước xoay Gauss trên Q dọc theo đường chéo chính. Độ phức tạp tính toán của phương pháp này là O (n3 ) . Phương pháp dựa trên Kết quả 1.7. i) Nếu có bất kỳ phần tử đường chéo của Q không dương thì Q không xác định dương: dừng kiểm tra. ii) Trong Q, trừ các bội số thích hợp của hàng 1 vào tất cả các hàng (từ 2 tới n) sao cho mọi phần tử ở cột 1 (từ hàng 2 tới hàng n) biến thành 0. Ta nhận được ma trận Q1 . Nếu có phần tử đường chéo của Q1 không dương thì Q không xác định dương: dừng kiểm tra. iii) Trong Q1 , trừ các bội số thích hợp của hàng 2 vào tất các hàng (từ 3 tới n) sao cho mọi phần tử ở cột 2 (từ hàng 3 tới hàng n) biến thành 0. Ta nhận được ma trận Q2 . Nếu có phần tử đường chéo của Q2 không dương thì Q không xác định dương: dừng kiểm tra. iv) Tiếp tục làm như trên. Nếu quá trình kiểm tra không dừng ở các ma trận Q1 , Q2 , ... , Qn−1 thì mọi phần tử đường chéo của Qn−1 đều dương. Ta kết luận Q xác định dương và quá trình kiểm tra kết thúc. Ví dụ 1.8. Kiểm tra xem ma trận D sau đây có xác định dương      1 1 0 1 1 0 1          D=  1 2 −1  ⇒ D1 =  0 1 −1  ⇒ D2 =  0 0 −1 2 0 −1 2 0 hay không?  1 0  1 −1  . 0 1 Do D đối xứng và có mọi phần tử đường chéo là số dương nên ta thực hiện phép xoay (1, 1) trên D, ta nhận được D1 . D1 có mọi phần tử đường chéo dương nên ta thực hiện phép xoay (2, 2) trên D1 và nhận được D2 . D2 có mọi phần tử 13 đường chéo dương nên ta kết luận D xác định dương và dừng kiểm tra. Ví dụ 1.9. Kiểm tra xem ma trận B sau đây có xác định dương    1 0 1 1 0 0 2    0 2 2 0 2 0 4    T B=  ⇒ D = (B + B )/2 =  1 2 5 2 4 5 4    1 2 3 0 0 2 3     1 0 1 1 1 0 1 1     0 2 2 2 0 2 2 2     ⇒ D1 =    ⇒ D2 =  0 0 2 0 0 2 4 2     0 0 0 0 0 2 2 2 không?  1  2   3  3 Do B không đối xứng nên ta thay B bởi D = (B + B T )/2 (đối xứng). D có mọi phần tử đường chéo dương nên ta thực hiện phép xoay (1, 1) trên D và nhận được D1 . D1 có mọi phần tử đường chéo dương nên ta thực hiện phép xoay (2, 2) trên D1 và nhận được D2 . Do D2 có phần tử đường chéo không dương nên ta kết luận D không xác định dương, do đó B không xác định dương và dừng kiểm tra. • Bây giờ giả sử Q = (qij ) là một ma trận vuông đối xứng cấp n. Nếu Q có phần tử đường chéo là số âm thì Q không thể là ma trận nửa xác định dương (Kết quả 1.5): dừng kiểm tra. Cũng vậy, nếu Q có phần tử đường chéo bằng 0 và nếu trên hàng hoặc cột chứa phần tử 0 này có phần tử khác 0 thì Q không thể là ma trận nửa xác định dương (Kết quả 1.6): dừng kiểm tra. Nếu chưa dừng kiểm tra thì xét phần tử đường chéo khác 0 đầu tiên của Q. Giả sử phần tử này nằm ở hàng r, cột r. Gọi ma trận Q lúc này là Qr . Nếu Qr là ma trận tam giác trên và mọi phần tử đường chéo là số dương thì Q xác định dương, còn nếu mọi phần tử đường chéo không âm thì Q nửa xác định dương. Trái lại, trong Qr trừ các bội số thích hợp của hàng r vào các hàng (từ r + 1 trở đi) sao cho các phần tử ở cột r và hàng từ r + 1 trở đi biến thành 0. Xóa hàng r và cột r khỏi ma trận nhận được sau biến đổi, gọi ma trận con còn lại là Er . Nếu Er có phần tử đường chéo âm thì Q không nửa xác định dương: dừng kiểm tra. Cũng vậy, nếu Er có phần tử đường chéo bằng 0 và trên hàng hoặc cột chứa phần tử 0 này có phần tử khác 0 thì Q không nửa xác định dương: dừng kiểm tra. Trái lại, trong Qr xét phần tử đường chéo khác 0 đầu tiên tiếp theo (nếu còn). Giả sử phần tử này nằm ở hàng s, cột s. Gọi ma trận Qr lúc này là Qs . Tiếp tục 14 xét Qs như đã xét ở trên đối với Qr , v.v ... Cuối cùng, nếu mọi phần tử đường chéo của ma trận tam giác trên Qn−1 là các số không âm thì kết luận Q nửa xác định dương: kết thúc quá trình kiểm tra. Ví dụ 1.10. Kiểm tra xem ma trận Q sau có nửa xác định dương không? Q đối xứng và mọi phần tử trên đường chéo đều dương. Thực hiện phép xoay (1, 1) ta nhận được Q1 . Xóa khỏi Q1 hàng và cột đầu, ma trận còn lại E1 có phần tử đường chéo thứ nhất là 0, nhưng cả hàng và cột đầu của E1 đều là véctơ 0. Thực hiện phép xoay trên Q1 theo phần tử đường chéo khác 0 tiếp theo 3 ta được Q2 . Q2 là ma trận tam giác trên với mọi phần tử đường chéo không âm, vì thế ta kết luận Q là ma trận nửa xác định dương, nhưng không là ma trận xác định dương. Ví dụ 1.11. Kiểm tra xem ma trận B, D sau có nửa xác    2 4 0 1 −1 4     B= 0   −1 2 ,D =  4 0 5 0 5 3 4 0 −3 định dương không?   .  B và D là các ma trận đối xứng. B có phần tử đường chéo là số âm, còn D có phần tử đường chéo bằng 0 và trên hàng (cột) chứa phần tử 0 này có các phần tử khác 0. Vì thế, cả B và D đều không nửa xác định dương. 1.5. Hàm lồi và hàm toàn phương Định nghĩa 1.6. a) Hàm f : C → [−∞, +∞] xác định trên một tập lồi C ⊆ Rn gọi là một hàm lồi trên C nếu với mọi x1 , x2 ∈ C và mọi λ ∈ [0, 1] ta có   f[λx1 + (1 − λ)x2 ] ≤ λf x1 + (1 − λ)f x2 15 mỗi khi vế phải xác định, nghĩa là hệ thức trên cần được thỏa mãn trừ khi f (x1 ) = −f (x2 ) = ±∞ (vì biểu thức +∞ − ∞ không có nghĩa). b) Hàm f được gọi là hàm lồi chặt trên C nếu với mọi x1 , x2 ∈ C, x1 6= x2 , và mọi số thực λ ∈ (0, 1) ta có   f[λx1 + (1 − λ)x2 ] < λf x1 + (1 − λ)f x2 Hiển nhiên, một hàm lồi chặt là hàm lồi, nhưng điều ngược lại không đúng. Định nghĩa 1.7. a) Hàm f gọi là hàm lõm (hàm lõm chặt) trên C nếu -f là hàm lồi (hàm lồi chặt) trên C. b) Hàm f gọi là hàm tuyến tính afin (hay đơn giản là hàm afin) trên C nếu f hữu hạn và vừa lồi, vừa lõm trên C. Một hàm afin trên Rn có dạng f (x) = aT x + α với a ∈ Rn , α ∈ R bởi vì với mọi x1 , x2 ∈ Rn và mọi λ ∈ [0, 1] ta có   f[λx1 + (1 − λ)x2 ] = λf x1 + (1 − λ)f x2 Hàm tuyến tính là trường hợp riêng của hàm afin, khi α = 0. Tuy nhiên, hàm afin (nói riêng, hàm tuyến tính) không lồi chặt hay lõm chặt. Nhận xét 1.5. Hàm lồi f : C → [−∞, +∞] có thể được mở rộng thành hàm lồi xác định trên toàn không gian Rn bằng cách đặt f (x) = + ∞ với mọi x ∈ / C. Vì vậy để đơn giản, ta thường xét hàm lồi trên toàn Rn . Hàm lồi, hàm lõm có các tính chất quan trọng được nêu trong 2 định lý sau. Định lý 1.1. Mọi điểm cực tiểu địa phương của hàm lồi f trên tập lồi C khác rỗng đều là điểm cực tiểu toàn cục. Tập Argmin x∈C f (x) là tập con lồi của C. Tương tự, mọi điểm cực đại địa phương của hàm lõm f trên tập lồi C khác rỗng đều là điểm cực đại toàn cục. Tập Argmax x∈C f (x) là tập con lồi của C. Định lý 1.2. Một hàm lồi chặt f trên tập lồi C có nhiều nhất một điểm cực tiểu trên C, nghĩa là tập Argmin x∈C f (x) gồm nhiều nhất một phần tử. Tương tự, một hàm lõm chặt f trên tập lồi C có nhiều nhất một điểm cực đại trên C, nghĩa là tập các điểm cực đại Argmax x∈C f (x)gồm không quá một phần tử. Định nghĩa 1.8. Hàm toàn phương (quadratic function), còn gọi là hàm bậc hai là hàm có dạng q(x) = 1 T x Qx 2 + pT x + c, trong đó Q ∈ Rn×n đối xứng, 16 p ∈ Rn , c ∈ R, q(x) xác định trên toàn Rn . Lưu ý: khi Q = 0 (ma trận không) thì q(x) là hàm afin. Bây giờ ta xét đến tính lồi (lồi chặt), lõm (lõm chặt) của hàm toàn phương. Ta có sự kiện quan trọng sau. Định lý 1.3. Hàm toàn phương q(x) = 12 xT Qx + pT x + c lồi (lồi chặt) trên Rn khi và chỉ khi ma trận Q nửa xác định dương (xác định dương) và q lõm (lõm chặt) trên Rn khi và chỉ khi ma trận Q nửa xác định âm (xác định âm). Ví dụ 1.12. Xét hàm bậc hai q(x) = 12 (x21 − 2x1 x2 + 3x22 ) + x1 − 2x2 . Ta thấy ! ! 1 −1 1 Q= ,p = −1 3 −2 Do ma trận Q xác định dương nên hàm q(x) đã cho là lồi chặt trên R2 . Tóm lại, chương này đã nhắc lại khái niệm và kết qủa cơ bản về các ma trận xác định dương và nửa xác định dương. Hàm toàn phương và qui hoạch toàn phương liên quan mật thiết với ma trận xác định dương và nửa xác định dương. Đáng chú ý là hàm toàn phương là lồi (lồi chặt) khi và chỉ khi ma trân tương ứng là nửa xác định dương (xác định dương) và là lõm (lõm chặt) khi và chỉ khi ma trận tương ứng là nửa xác định âm (xác định âm). 17 Chương 2 Bài toán qui hoạch toàn phương Chương này trình bày một số kiến thức cơ bản về bài toán qui hoạch toàn phương: nội dung và ý nghĩa bài toán, sự tồn tại nghiệm và điều kiện tối ưu cho nghiệm bài toán. Nội dung của chương được tham khảo từ tài liệu [3] - [7]. 2.1. Phát biểu bài toán Qui hoạch toàn phương (Quadratic Programming, viết tắt là QP) là bài toán tối ưu với hàm mục tiêu bậc hai và với các ràng buộc đẳng thức hay bất đẳng thức tuyến tính. Mô hình toán học của qui hoạch toàn phương có dạng: 1 (QP) f (x) = xT Qx + pT x + c → min 2 với điều kiện: (2.1) aTi x = bi , i = 1, 2, . . . , k, (2.2) aTi x 6 bi , i = k + 1, . . . , m, (2.3) trong đó Q là ma trận đối xứng cấp n × n; p, ai ∈ Rn , bi , c ∈ R, k, m là các số nguyên không âm (0 6 k 6 m). Ký hiệu tập ràng buộc (hay miền chấp nhận được) của bài toán (2.1) - (2.3) là D = {x ∈ Rn : aTi x = bi , i = 1, 2, . . . , k, aTi x 6 bi , i = k + 1, . . . , m}. Nếu ma trận Q nửa xác định dương thì (QP) là bài toán qui hoạch toàn phương lồi (Convex QP) và nghiệm cực tiểu địa phương x∗ là nghiệm cực tiểu toàn cục. Nếu Q xác định dương thì (QP) là bài toán qui hoạch toàn phương lồi chặt (Strictly Convex QP) và x∗ là nghiệm cực tiểu toàn cục duy nhất. Nếu Q là ma trận không xác định thì (QP) là bài toán qui hoạch toàn phương không lồi (Nonconvex QP) rất đáng được chú ý. 18 Trường hợp hàm mục tiêu và các hàm ràng buộc bất đẳng thức đều là hàm lồi bậc hai, ta có bài toán qui hoạch toàn phương lồi với các ràng buộc toàn phương lồi (Quadratically Constrained Quadratic Program, viết tắt là QCQP): 1 f (x) = xT Q0 x + pT0 x + c0 → min (QCQP) 2 với các điều kiện 1 gi (x) = xT Qi x + pTi x + ci 6 0, i = 1, . . . , m, Ax = b, 2 n trong đó Qi ∈ S+ (nửa xác định dương), pi ∈ Rn , A ∈ Rm×n , b ∈ Rm , ci ∈ R, (i = 0, 1, . . . , m). Bài toán (QCQP) tìm cực tiểu hàm bậc hai lồi trên miền chấp nhận được là giao của các ellipsoid khi mọi Qi > 0 (xác định dương). Qui hoạch tuyến tính là trường hợp riêng của qui hoạch toàn phương và qui hoạch toàn phương lồi (khi Q = 0). Qui hoạch toàn phương lồi lại là trường hợp riêng của qui hoạch toàn phương lồi với các ràng buộc toàn phương lồi (khi Qi = 0 với mọi i = 1, . . . , m). Một trường hợp riêng quan trọng của bài toán qui hoạch toàn phương (QP) là khi nó chỉ có các ràng buộc về dấu đối với các biến. Khi đó, bài toán (QP) có dạng đơn giản 1 f (x) = xT Qx + pT x + c → min 2 với điều kiện x > 0. Nếu Q nửa xác định dương thì bài toán dạng đơn giản này hoàn toàn tương đương với bài toán bù tuyến tính LCP (p, Q) xét ở chương sau. Có nhiều ứng dụng trong công nghiệp và vật lý dẫn tới mô hình qui hoạch toàn phương lồi dạng đặc biệt trên. Các ứng dụng đó bao gồm bài toán tiếp xúc, bài toán chất lỏng nhớt, bài toán vật cản, bài toán xoắn chất dẻo đàn hồi cũng như nhiều bài toán biên tự do khác. 2.2. Một số ứng dụng Sau đây là một số ví dụ về bài toán qui hoạch toàn phương. A. Hồi qui tuyến tính Một trong những bài toán thống kê thường gặp là bài toán hồi qui tuyến tính: Tìm đường thẳng xấp xỉ tốt nhất dãy số liệu thống kê cho bởi n cặp điểm quan sát: (x1 , y1 ), (x2 , y2 ), . . . , (xn , yn ). 19
- Xem thêm -