Tài liệu Phương pháp giải quy hoạch toàn phương

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC VŨ THỊ ĐÀO PHƯƠNG PHÁP GIẢI QUI HOẠCH TOÀN PHƯƠNG Chuyên ngành: TOÁN ỨNG DỤNG Mã số: 60.46.36 LUẬN VĂN THẠC SĨ KHOA HỌC Người hướng dẫn khoa học GS.TS. TRẦN VŨ THIỆU Thái Nguyên – 2011 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Mục lục LỜI NÓI ĐẦU 3 1 MỘT SỐ KIẾN THỨC CHUẨN BỊ 5 1.1 TẬP AFIN VÀ TẬP LỒI . . . . . . . . . . . . . . . . . 5 1.1.1 Tập afin. . . . . . . . . . . . . . . . . . . . . . 5 1.1.2 Tập lồi. . . . . . . . . . . . . . . . . . . . . . . 6 HÀM TOÀN PHƯƠNG VÀ HÀM LỒI . . . . . . . . . 8 1.2.1 Ma trận xác định dương . . . . . . . . . . . 8 1.2.2 Hàm toàn phương và hàm lồi . . . . . . . . 9 1.3 BÀI TOÁN QUI HOẠCH TOÀN PHƯƠNG LỒI . . . 13 1.4 BÀI TOÁN TỐI ƯU PHI TUYẾN . . . . . . . . . . . 15 1.5 PHÂN TÍCH CHOLESKY VÀ PHÂN TÍCH QR . . . 16 1.5.1 Phân tích Cholesky . . . . . . . . . . . . . . 17 1.5.2 Phân tích QR . . . . . . . . . . . . . . . . . . 17 1.2 2 BÀI TOÁN QUI HOẠCH TOÀN PHƯƠNG 19 2.1 ĐIỀU KIỆN TỐI ƯU . . . . . . . . . . . . . . . . . . 19 2.2 BÀI TOÁN ĐỐI NGẪU . . . . . . . . . . . . . . . . . 25 2.3 QUAN HỆ ĐỐI NGẪU . . . . . . . . . . . . . . . . . . 28 3 PHƯƠNG PHÁP KHỬ BIẾN SỐ 32 3.1 NỘI DUNG PHƯƠNG PHÁP . . . . . . . . . . . . . 32 3.2 VÍ DỤ MINH HỌA . . . . . . . . . . . . . . . . . . . . 34 1 1Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3.3 PHƯƠNG PHÁP KHỬ SUY RỘNG . . . . . . . . . . 39 3.4 PHƯƠNG PHÁP NHÂN TỬ LAGRANGE . . . . . . . 44 4 PHƯƠNG PHÁP TẬP TÍCH CỰC 47 4.1 BÀI TOÁN VÀ Ý TƯỞNG THUẬT TOÁN . . . . . . 47 4.2 PHƯƠNG PHÁP TẬP TÍCH CỰC . . . . . . . . . . . 49 4.2.1 Hàm mục tiêu lồi 4.2.2 Các bước thuật toán . . . . . . . . . . . . . 50 4.2.3 Thuật toán tập tích cực . . . . . . . . . . . 52 4.2.4 Ví dụ minh họa . . . . . . . . . . . . . . . . . 53 . . . . . . . . . . . . . . . 49 4.3 SỰ HỘI TỤ CỦA THUẬT TOÁN . . . . . . . . . . . 56 4.4 HÀM MỤC TIÊU KHÔNG LỒI . . . . . . . . . . . . . 59 KẾT LUẬN 60 TÀI LIỆU THAM KHẢO 61 2 2Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn LỜI NÓI ĐẦU Qui hoạch toàn phương là bài toán qui hoạch phi tuyến đơn giản nhất. Đó 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. Nếu dạng toàn phương xác định dương hay nửa xác định dương thì ta có bài toán qui hoạch toàn phương lồi, còn nếu dạng toàn phương không xác định thì ta có bài toán qui hoạch toàn phương không lồi. Các bài toán này quan trọng và rất được quan tâm nghiên cứu vì nhiều vấn đề nảy sinh trong kinh tế, tài chính, công nghiệp và kỹ thuật có thể diễn đạt như một bài toán qui hoạch toàn phương. Luận văn trình bày nội dung bài toán qui hoạch toàn phương, nêu các điều kiện tối ưu (cần và đủ), lý thuyết đối ngẫu trong qui hoạch toàn phương lồi và đề cập tới hai phương pháp giải thông dụng: phương pháp giảm biến, phương pháp tập tích cực. Việc tìm hiểu chủ đề này là rất cần thiết và hữu ích giúp hiểu và vận dụng các phương pháp qui hoạch toàn phương vào các bài toán tối ưu khác. Nội dung luận văn được chia thành bốn chương: Chương 1 “Kiến thức chuẩn bị” nhắc lại vắn tắt một số kiến thức cơ sở cần thiết về giải tích lồi và bài toán tối ưu, trước hết là các khái niệm về tập afin, tập lồi, hàm lồi, hàm toàn phương cùng một số tính chất cơ bản của chúng. Một số cách phân tích ma trận ra thành thừa số (dạng Cholesky, dạng QR) cũng được đề cập tới. Các kiến thức này sẽ được sử dụng ở các chương sau khi giải bài toán qui hoạch toàn phương với ràng buộc tuyến tính. Chương 2 “Bài toán qui hoạch toàn phương” đề cập tới bài toán qui hoạch toàn phương tổng quát. Đó là bài toán tìm cực tiểu của một hàm bậc hai (có thể không lồi) với các ràng buộc tuyến tính. Nêu các điều kiện tối ưu (cần và đủ) và trình bày một số kết quả chính trong lý thuyết đối ngẫu của qui hoạch toàn phương lồi, tương tự như quan hệ đối ngẫu trong qui hoạch tuyến tính. Chương 3 “Phương pháp khử biến số” đề cập tới bài toán tối ưu với hàm mục tiêu bậc hai và ràng buộc đẳng thức tuyến tính. Nêu hai cách đưa bài toán đã cho về bài toán không ràng buộc: phương pháp khử biến số (hạ thấp thứ nguyên) và phương pháp khử suy rộng, dựa 3 3Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn trên phân rã không gian thành tổng của hai không gian con bù nhau. Để giải bài toán không ràng buộc, ta dùng các phương pháp tìm cực tiểu tự do của hàm n biến số. Cách tìm các nhân tử Lagrange tương ứng với lời giải tối ưu của bài toán cũng được đề cập tới. Phương pháp này sẽ được sử dụng ở chương sau, khi xem xét cách giải qui hoạch toàn phương với ràng buộc bất đẳng thức tuyến tính. Chương 4 “Phương pháp tập tích cực” trình bày phương pháp tập tích cực giải qui hoạch toàn phương với ràng buộc bất đẳng thức tuyến tính, bằng cách đưa về giải một dãy bài toán với ràng buộc đẳng thức tuyến tính, theo các phương pháp đã giới thiệu ở Chương 3. Tính hữu hạn của thuật toán được chứng minh cho bài toán qui hoạch toàn phương lồi. Do thời gian và kiến thức còn hạn chế nên luận văn này mới chỉ đề cập tới những nội dung và các tính chất cơ bản của bài toán qui hoạch toàn phương và phương pháp giải qui hoạch toàn phương, chưa đi sâu vào kỹ thuật lập trình thực thi thuật toán. Trong quá trình viết luận văn cũng như trong xử lý văn bản chắc chắn không tránh khỏi những sai sót. Tác giả rất mong nhận được sự góp ý của các thầy cô và các bạn đồng nghiệp để luận văn được hoàn thiện hơn. Nhân dịp này, tác giả xin bày tỏ lòng biết ơn sâu sắc đến thầy hướng dẫn GS-TS Trần Vũ Thiệu đã tận tình giúp đỡ trong suốt quá trình làm luận văn. Tác giả xin trân trọng cảm ơn các các thầy, cô giáo Trường Đại học Khoa học - Đại học Thái Nguyên, Viện Toán học Viện Khoa học và Công nghệ Việt Nam, đã giảng dạy và tạo mọi điều kiện thuận lợi trong quá trình tác giả học tập và nghiên cứu. Tác giả cũng xin chân thành cảm ơn Ban giám hiệu, các Phòng, Ban chức năng của Trường Cao đẳng Công nghiệp Việt Đức (Sông Công - Thái Nguyên) và tập thể bạn bè đồng nghiệp cùng gia đình đã quan tâm giúp đỡ, động viên để tác giả hoàn thành tốt luận văn này. Thái Nguyên, tháng 09/2011 Tác giả Vũ Thị Đào 4 4Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Chương 1 MỘT SỐ KIẾN THỨC CHUẨN BỊ Chương này trình bày tóm tắt một số kiến thức cơ bản về tập afin, tâp lồi, hàm lồi, hàm toàn phương; về điều kiện cần, điều kiện đủ đối với nghiệm tối ưu của bài toán tối ưu phi tuyến và một số kiến thức về ma trận có liên quan. Nội dung trình bày trong chương này chủ yếu dựa trên các tài liệu [1], [2], [5]. 1.1 1.1.1 TẬP AFIN VÀ TẬP LỒI Tập afin. Trước hết là những khái niệm liên quan đến tập afin: Định nghĩa 1.1. Một tập M ⊂ Rn được gọi là tập afin nếu ∀a, b ∈ M, λ ∈ R ⇒ λa + (1 − λ)b ∈ M, tức là hễ M chứa hai điểm nào đó thì M chứa cả đường thẳng qua hai điểm ấy. Một số tính chất cơ bản của các tập afin: • Nếu M là tập afin thì a + M = {a + x : x ∈ M } cũng là tập afin ∀a ∈ Rn • M là tập afin chứa gốc khi và chỉ khi M là một không gian con của Rn • Giao của một họ bất kỳ các tập afin cũng là một tập afin. 5 5Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn • Nếu x1 , ..., xk thuộc tập afin M thì mọi tổ hợp afin của các điểm này cũng thuộc M , nghĩa là xi ∈ M (i = 1, ..., k), λ1 + ... + λk = 1 ⇒ λ1 x1 + ... + λk xk ∈ M • Một tập afin bất kỳ có dạng M = {x : Ax = b} với A ∈ Rm×n , b ∈ Rm . Ngược lại, mọi tập có dạng trên đều là tập afin. (Đó là tập nghiệm của một hệ phương trình tuyến tính). Bao afin của một tập E là giao của tất cả các tập afin chứa E, ký hiệu aff(E). Đó là tập afin nhỏ nhất chứa E. Từ các tính chất của tập afin suy ra: k k P P i i x ∈ aff(E) ⇔ x = λi x , x ∈ E, λi = 1 i=1 i=1 Có thể thấy: một tập M 6= ∅ là afin khi và chỉ khi M = x0 + L với x0 ∈ M và L là một không gian con. L được xác định một cách duy nhất và được gọi là không gian con song song với M . (M nhận được bằng cách tịnh tiến L tới x0 ). Thứ nguyên (hay số chiều) của một tập afin M , ký hiệu dim M , được định nghĩa là số chiều của không gian con song song với nó. Định nghĩa 1.2. Một tập afin trong Rn có thứ nguyên n − 1 được gọi là một siêu phẳng. Có thể thấy siêu phẳng là tập có dạng H = {x :< a, x >= α} với a ∈ Rn (Đó là tập nghiệm của một phương trình tuyến tính trong Rn ). Một tập k điểm x1 , x2 , ..., xk gọi là độc lập afin nếu k − 1 véctơ x2 −x1 , ..., xk −x1 độc lập tuyến tính. Qua n điểm độc lập afin trong Rn có một siêu phẳng duy nhất. Một tập có dạng H = {x :< a, x >≤ α} (hay H = {x :< a, x >< α}) được gọi là một nửa không gian đóng (mở). 1.1.2 Tập lồi. Sau đây là một số khái niệm liên quan đến tập lồi. Định nghĩa 1.3. Tập hợp C ⊂ Rn được gọi là lồi nếu ∀a, b ∈ C, 0 ≤ λ ≤ 1 ⇒ λa + (1 − λ)b ∈ C 6 6Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn tức là hễ C chứa hai điểm nào đó thì nó chứa cả đoạn thẳng nối hai điểm ấy. Ví dụ 1.1 (về tập lồi). Tập hợp rỗng, toàn không gian Rn , mọi tập afin, siêu phẳng, nửa không gian (đóng, mở), hình cầu, ... đều là những tập lồi. Trong R2 , các hình tam giác, hình vuông, hình tròn, hình elip đều là các tập hợp lồi. Tuy nhiên, đường tròn hay hình vành khăn không phải là tập hợp lồi. Hình 1.1. a) Các tập hợp lồi b) Các tập hợp không lồi Thứ nguyên hay số chiều của một tập lồi C là thứ nguyên của bao afin của C. Trong Rn một tập lồi thứ nguyên n được gọi là tập lồi thứ nguyên đầy đủ. Sau đây là một số tính chất cơ bản của các tập lồi: • Giao của một họ bất kỳ các tập lồi cũng là một tập lồi. • Nếu C, D là tập lồi thì C + D = {x + y : x ∈ C, y ∈ D}, αC = {αx : x ∈ C} và C −D = C +(−1)D cũng là tập lồi. Nếu C ⊂ Rn , D ⊂ Rm là các tập lồi thì tích C × D = {(x, y) : x ∈ C, y ∈ D} ⊂ Rn × Rm cũng là tập lồi. • Tập hợp tất cả các tổ hợp lồi của một số hữu hạn điểm trong Rn là một tập lồi. Nếu x1 , x2 , ..., xk thuộc một tập lồi C thì mọi tổ hợp lồi của các điểm này cũng thuộc C, nghĩa là xi ∈ C, λi ≥ 0 (i = 1, ..., k) , λ1 + ... + λk = 1 ⇒ λ1 x1 + ... + λk xk ∈ C. • Một tập hợp lồi có thể giới nội hoặc không giới nội. Nếu tập lồi C ⊂ Rn không giới nội thì có véctơ t ⊂ Rn (t 6= 0) sao cho với mọi x ∈ C tia x + λt, λ ≥ 0 nằm trọn trong C. Một véctơ t như thế gọi là một phương vô hạn của tập lồi C. 7 7Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Cho một tập bất kỳ E ⊂ Rn . Giao của tất cả các tập lồi chứa E được gọi là bao lồi của E, ký hiệu conv(E). Đó là tập lồi nhỏ nhất chứa E. Có thể thấy: • conv(E) trùng với tập tất cả các tổ hợp lồi của các phần tử thuộc E. • Bao đóng của một tập lồi cũng là tập lồi. Cho C ⊂ Rn là một tập lồi. Điểm x ∈ C gọi là điểm cực biên của C nếu x không thể biểu diễn dưới dạng một tổ hợp lồi của hai điểm phân biệt bất kỳ khác của C, nghĩa là không tồn tại hai điểm y, z ∈ C, y 6= z sao cho x = λy + (1 − λ)z với 0 < λ < 1 Định lý 1.1 (Định lý tách). Cho hai tập hợp lồi C, D ⊂ Rn , khác rỗng và không có điểm chung (C ∩ D = ∅). Khi đó, có thể tách chúng bởi một siêu phẳng, nghĩa là tồn tại véctơ t ∈ Rn , t 6= 0 và số α ∈ R sao cho tT x ≥ a ≥ tT y với mọi x ∈ C và mọi y ∈ D. 1.2 1.2.1 HÀM TOÀN PHƯƠNG VÀ HÀM LỒI Ma trận xác định dương Trước hết, ta nhắc lại định nghĩa và một số tính chất về ma trận. Định nghĩa 1.4. Ma trận vuông, đối xứng C (cấp n) gọi là xác định dương nếu xT Cx > 0 với mọ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.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). Hệ quả 1.1. Các phần tử trên đường chéo chính của một ma trận xác định dương (nửa xác định dương) là dương (không âm). 8 8Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Mệnh đề 1.2. Nếu C nửa xác định dương và xT Cx = 0 thì Cx = 0 Mệnh đề 1.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. Mệnh đề 1.4. Nếu A là một ma trận tuỳ ý (vuông hay chữ nhật) thì AAT và AT A là các ma trận nửa xác định dương (T là ký hiệu chuyển vị ma trận). Mệnh đề 1.5.Ma trận đối xứng, luỹ đẳng là ma trận nửa xác định dương. 1.2.2 Hàm toàn phương và hàm lồi Định nghĩa 1.5. Hàm toàn phương (hay dạng toàn phương) là một hàm số có dạng n P n P T f (x) = x Cx = cij xi xj , i=1 j=1 trong đó C = [cij ] là ma trận vuông, đối xứng cấp n cho trước (tuỳ ý). Dạng toàn phương f (x) = xT Cx gọi là xác định dương nếu xT Cx > 0 với mọi x 6= 0, nghĩa là C là ma trận xác định dương. Ví dụ 1.2. Dạng toàn phương f (x) = x21 + x22 là xác định dương (n = 2). Dạng toàn phương gọi là nửa xác định dương nếu xT Cx ≥ 0 với mọi x và tồn tại ít nhất một x 6= 0 (x ∈ Rn ) sao cho xT Cx = 0, nghĩa là C là ma trận nửa xác định dương, nhưng không xác định dương. Ví dụ 1.3. Dạng toàn phương f (x) = (x1 − x2 )2 ≥ 0 với mọi x1 , x2 và bằng 0 khi x1 = x2 = 1, vì thế f (x) là nửa xác định dương. Dạng toàn phương f (x) = xT Cx gọi là xác định â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 các dạng toàn phương có ít biến (n nhỏ) ta có thể kiểm tra tính xác định dương của nó nhờ dùng tính chất sau đây (mạnh hơn Mệnh đề 1.1). * Dạng toàn phương f (x) = xT Cx là xác định dương khi và chỉ khi 9 9Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn mọi định thức con chính của C đều dương. Chẳng hạn, với n = 4 ta phải có: c11   c11 c12   > 0, > 0,  c21 c22    c11 c12 c13      c21 c22 c23  > 0 và C  > 0.   c31 c32 c33  Định nghĩa 1.6. Một hàm f (x) xác định trên một tập hợp lồi C ⊂ Rn gọi là lồi trên C nếu với mọi x, y ∈ C và mọi số thực λ ∈ [0, 1] ta có f [λx + (1 − λ)y] ≤ λf (x) + (1 − λ)f (y) Nếu bất đẳng thức trên thoả mãn với dấu < đối với mọi x, y ∈ C, x 6= y mọi 0 < λ < 1 thì f (x) được gọi là lồi chặt trên C. Hàm f (x) gọi là lõm (lõm chặt) trên C nếu−f (x) là lồi (lồi chặt) trên C. Có thể chứng minh rằng hàm f (x) là lồi khi và chỉ khi a) Tập epif ≡ {(x, t) ∈ Rn × R : x ∈ C, t ≥ f (x)} là lồi, hoặc  m m
P P k λk f xk với mọi xk ∈ C, λk ≥ 0 với mọi k b) f λk x ≤ và m P k=1 k=1 λk = 1, trong đó m là số nguyên ≥ 2 (bất đẳng thức Jensen). k=1 Ví dụ 1.4 (về hàm lồi): • Hàm tuyến tính afin f (x) = < c, x > +α là vừa lồi vừa lõm, vì với mọi x, y ∈ Rn và với mọi λ ta có f [λx + (1 − λ)y] = λf (x) + (1 − λ)f (y). Tuy nhiên, hàm đó không phải là hàm lồi chặt hay lõm chặt. √ • Hàm chuẩn f (x) = kxk = < x, x >, x ∈ Rn , là hàm lồi. • Hàm khoảng cách từ điểm x ∈ Rn tới một tập hợp lồi, đóng C ⊂ Rn : f (x) = inf kx − yk cũng là hàm lồi. y∈C Tiêu chuẩn nhận biết hàm lồi. Hàm f (x) là lồi trên toàn Rn khi và chỉ khi có một trong bốn điều kiện sau đây (giả thiết hàm f khả vi nếu cần): a) f (y) − f (x) ≥ < ∇f (x), y − x > với mọi x, y ∈ Rn . 10 10Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2 ∂ f (x) b) Ma trận các đạo hàm cấp hai ∂xi ∂xj là nửa xác định dương với mọi x. c)ϕ(λ) = f (x0 + λd) là hàm lồi theo λ đối với mọi x0 , d ∈ Rn . d)ϕ0 (λ) = < ∇f (x0 + λd), d > là hàm không giảm theo λ với mọi x 0 , d ∈ Rn . Một số tính chất đơn giản của hàm lồi: • Mọi tổ hợp tuyến tính dương của các hàm lồi là hàm lồi và là lồi chặt nếu ít nhất một trong các hàm đã cho là lồi chặt. • Nếu f (x) lồi thì f (Ax + b) cũng lồi, trong đó A là một ma trận vuông cấp n và b ∈ Rn • Nếu các hàm fi (x), i = 1, ..., m là lồi (nói riêng là tuyến tính afin) thì hàm max fi (x) cũng lồi. 1≤i≤m • Mọi điểm cực tiểu địa phương của một hàm lồi f (x) trên một tập hợp lồi đóng C đều là điểm cực tiểu toàn cục của f (x) trên C. Hàm lồi chặt có nhiều nhất một điểm cực tiểu. • Nếu hàm f (x) lồi thì tập Cα ≡ {x ∈ Rn : f (x) ≤ α} là lồi với bất kỳ số thực α ∈ Rn . Hơn nữa, nếu f (x) = < p, x > + < x, Cx > với C là ma trận xác định dương thì tập Cα là giới nội (bị chặn). Mệnh đề 1.6. Dạng toàn phương nửa xác định dương f (x) = xT Cx = < x, Cx > là một hàm lồi đối với mọi x ∈ Rn . Chứng minh: Ta cần chứng tỏ rằng với 0 ≤ λ ≤ 1 và mọi x, y ∈ Rn ta có: f [λx + (1 − λ)y] ≤ λf (x) + (1 − λ)f (y) ⇔ f [λx + (1 − λ)y] − λf (x) − (1 − λ)f (y) ≤ 0 Do < y, Cx >= < x, Cy > nên vế trái của bất đẳng thức trên có thể viết thành: < λx + (1 − λ) y, C [λx + (1 − λ) y] > −λ < x, Cx > − (1 − λ) < y, Cy > = λ2 < x, Cx > +(1 − λ)2 < y, Cy > +2λ (1 − λ) < x, Cy > 11 11Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn −λ < x, Cx > − (1 − λ) < y, Cy >
= λ − λ < x, Cx > + (1 − λ) [(1 − λ) < y, Cy > − < y, Cy >] +2λ (1 − λ) < x, Cy > = λ (λ − 1) < x, Cx > +λ (λ − 1) < y, Cy > −2λ (λ − 1) < x, Cy > = λ (λ − 1) [< x, Cx > + < y, Cy > −2 < x, Cy >] = λ (λ − 1) < x − y, C (x − y) >≤ 0 2 Bất đẳng thức cuối có được là do < x − y, C (x − y) >≥ 0 với mọi x, y ∈ Rn , và λ (λ − 1) < 0 với mọi 0 < λ < 1 và λ(λ − 1) = 0 với λ = 0 hay λ = 1. Vậy f (x) = xT Cx = < x, Cx > là hàm lồi với mọi x ∈ Rn .  Mệnh đề 1.7.Cho ma trận đối xứng, nửa xác định dương C và cho p, x0 ∈ Rn . Khi đó: < p, x > + 21 < x, Cx > ≥ < p, x0 > + 12 < x0 , Cx0 > + < x − x0 , p + Cx0 > ∀x ∈ Rn . Ta thấy f (x) = < p, x > + 21 < x, Cx > là hàm lồi khả vi và ∇f (x0 ) = Cx0 + p. Vì thế, bất đẳng thức trên được suy ra từ tính chất của hàm lồi khả vi. Tuy nhiên, ta có thể chứng minh trực tiếp nó như sau: Chứng minh. Do C đối xứng, nửa xác định dương nên ta có < x, Cx0 >= < x0 , Cx > và < x − x0 , C(x − x0 ) >= < x0 , Cx0 > + < x, Cx > −2 < x, Cx0 > ≥ 0 hay < x, Cx > ≥ 2 < x, Cx0 > − < x0 , Cx0 > Từ đó < p, x > + 12 < x, Cx > ≥ < p, x > − 21 < x0 , Cx0 > + < x, Cx0 > Bằng cách thêm vào vế phải < p, x0 > − < x0 , p > + < x0 , Cx0 > − < x0 , Cx0 >= 0 và ghép lại các số hạng ta được bất đẳng thức cần chứng minh: < p, x > + 21 < x, Cx > ≥ < p, x0 > + 21 < x0 , Cx0 > + < x − x0 , p + Cx0 >.  12 12Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1.3 BÀI TOÁN QUI HOẠCH TOÀN PHƯƠNG LỒI Qui hoạch toàn phương lồi là bài toán tìm cực tiểu của một hàm lồi, bậc hai với các ràng buộc tuyến tính. Xét hai dạng bài toán cơ bản sau đây: Dạng chính tắc: f (x) = p0 + < p, x > + 21 < x, Cx >→ min, Ax = b, x ≥ 0, x = (x1 , x2 , ..., xn )T ∈ Rn là véctơ biến cần tìm; C - ma trận vuông đối xứng cấp n nửa xác định dương; A - ma trận cấp m × n (A ∈ Rm×n ); p - véctơ n thành phần (p ∈ Rn ); b - véctơ m thành phần (b ∈ Rm ); p0 - hằng số (thông thường p0 = 0) . Giả thiết mọi thành phần của véctơ b không âm (nếu cần thì đổi dấu cả hai vế của phương trình tương ứng với thành phần bi < 0 trong hệ Ax = b). Dạng chuẩn tắc: f (x) = p0 + < p, x > + 21 < x, Cx >→ min, Ax ≥ b, x ≥ 0, Ý nghĩa các ký hiệu như trong bài toán dạng chính tắc. Ở đây, thay cho Ax = b, ta xét ràng buộc Ax ≥ b. Ngoài ra, có thể xét bài toán chỉ với ràng buộc đẳng thức hay bất đẳng thức: min{< p, x > + 12 < x, Cx >: Ax = b} hay min{< p, x > + 12 < x, Cx >: Ax ≥ b}. Cũng có thể xét bài toán có cả ràng buộc đẳng thức và bất đẳng thức. Nhiều vấn đề thực tiễn có thể diễn đạt dưới dạng bài toán qui hoạch toàn phương. Chẳng hạn, bài toán lựa chọn vốn đầu tư cổ phiếu, bài 13 13Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn toán khẩu phần thức ăn với hàm mục tiêu bậc hai, cân bằng hoá học, phân phối tài nguyên, mạng điện, cơ học kết cấu, phân tích hồi qui, v.v ... Khi C = 0 các bài toán nêu trên trở thành bài toán qui hoạch tuyến tính. Vì thế, bài toán qui hoạch toàn phương lồi là mở rộng trực tiếp của bài toán qui hoạch tuyến tính và nó là cầu nối giữa qui hoạch tuyến tính và qui hoạch lồi. Cũng như đối với bài toán qui hoạch tuyến tính, bằng cách thực hiện các phép biến đổi đơn giản, ta có thể dễ dàng chuyển bài toán qui hoạch toàn phương từ dạng này sang dạng khác (với ràng buộc đẳng thức, bất đẳng thức hay cả hai). Vì vậy, ta chỉ cần chọn một dạng thuận tiện để nghiên cứu là đủ mà không làm mất tính tổng quát của các kết quả nghiên cứu. Bài toán cực đại: g → max có thể đưa về bài toán cực tiểu: f = −g → min với cùng các ràng buộc và ta có hệ thức gmax = max{g(x) : x ∈ D} = −fmin = −min{f (x) : x ∈ D} Nếu bài toán qui hoạch toàn phương được xét ở dạng bài toán tìm cực đại (tìm max) thì phải giả thiết hàm mục tiêu là hàm lõm, nghĩa là ma trận C nửa xác định âm. Trong trường hợp này hàm mục tiêu thường được viết ở dạng < p, x > − 21 < x, Cx > với C xác định dương hay nửa xác định dương. Để dễ hình dung, ta mô tả vắn tắt ý nghĩa hình học của bài toán qui hoạch toàn phương lồi với hai biến (có thể mở rộng cho trường hợp nhiều biến, tuy nhiên sẽ mất tính trực quan hình học). Ta giới hạn xét trường hợp ma trận C xác định dương. Trong trường hợp này hàm f (x) lồi chặt và đường mức f (x) = const tạo nên các đường elip. Tâm chung của các đường elip này sẽ là điểm cực tiểu tự do (cực tiểu không ràng buộc) của hàm f (x) trên toàn Rn ). Tập ràng buộc là một tập lồi đa diện. Bài toán đặt ra là: tìm một điểm của tập lồi đa diện nằm trên đường mức với giá trị f nhỏ nhất (trường hợp ma trận C xác định dương thì điểm cực tiểu là duy nhất). Trong trường hợp hai biến có 3 khả năng sau đây xảy ra (Xem các Hình 1.2a, 1.2b và 1.2c với m = 2): 14 14Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Hình 1.2. a) x∗ là đỉnh b) x∗ là điểm biên c) x∗ là điểm trong Ký hiệu x∗ là điểm cực tiểu cần tìm. So với qui hoạch tuyến tính, có một điểm khác biệt đáng chú ý: đối với hàm mục tiêu tuyến tính bao giờ cũng có một đỉnh của đa diện ràng buộc là điểm tối ưu của bài toán. Nhưng đối với hàm mục tiêu lồi bậc hai, điểm cực tiểu (hữu hạn), ngay cả khi nó duy nhất, có thể ở trên biên (Hình 1.2b) hay ở phần trong (Hình 1.2c) của đa diện ràng buộc. Do đó, trong qui hoạch tuyến tính nếu lời giải tối ưu là duy nhất và không suy biến thì có đúng n (trong số m + n) ràng buộc của bài toán được thoả mãn như đẳng thức tại điểm tối ưu, còn trong qui hoạch toàn phương có không quá n ràng buộc được thoả mãn như đẳng thức tại điểm tối ưu. 1.4 BÀI TOÁN TỐI ƯU PHI TUYẾN Xét bài toán tối ưu phi tuyến (P) min{f (x) : hi (x) = 0, i = 1, ..., m; gj (x) ≤ 0, j = 1, ..., p} trong đó f, hi , i = 1, ..., m, và gj , j = 1, ..., p, là các hàm hai lần khả vi liên tục (thuộc lớp C 2 ). Ký hiệu h(x) = (h1 (x), ..., hm (x))T ∈ Rm và g(x) = (g1 (x), ..., gp (x))T ∈ Rp . Điểm x thoả mãn h(x) = 0 và g(x) ≤ 0 gọi là một điểm (lời giải) chấp nhận được hay một phương án của bài toán (P). Tập các phương án D = {x ∈ Rn : h(x) = 0, g(x) ≤ 0} gọi là tập ràng buộc hay miền chấp nhận được của bài toán. Đó là một tập lồi khi hi (i = 1, ..., m) là các hàm afin và gj (j = 1, ...., p) là các hàm lồi. Giả thiết D khác rỗng. Một phương án đạt cực tiểu của hàm f được gọi là một phương án (điểm hay lời giải) tối ưu. Khi đó, ta nói mỗi phương trình hi (x) = 0 là một ràng buộc đẳng thức, mỗi bất phương trình gj (x) ≤ 0 là một ràng buộc bất đẳng thức. 15 15Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Hàm Lagrange tương ứng với bài toán (P) được xác định như sau: L(x, µ, λ) = f (x) +h(x)T µ + g(x)T λ trong đó x ∈ Rn , µ ∈ Rm và λ ∈ Rp , λ ≥ 0. Giả sử x∗ là một điểm chấp nhận của (P), ta ký hiệu I(x∗ ) = {j : 1 ≤ j ≤ p, gj (x∗ ) = 0}. Bài toán (P) được gọi là chính qui tại điểm x∗ (hay x∗ là điểm chính qui của (P)) nếu hệ {∇h1 (x∗ ), ..., ∇hm (x∗ ) và ∇gj (x∗ ), j ∈ I(x∗ )} độc lập tuyến tính. Điều kiện cần tối ưu (Định lý Karush - Kuhn - Tucker). Giả sử x∗ ∈ D là điểm cực tiểu địa phương của f trên D và x∗ là điểm chính qui của (P). Khi đó, có các véctơ µ∗ ∈ Rm và λ ∈ Rp thoả mãn:   ∇f (x∗ ) + ∇h(x∗ )T µ∗ + ∇g(x∗ )T λ∗ = 0 g(x∗ )T λ∗ = 0, λ∗ ≥ 0,  h(x∗ ) = 0, g(x∗ ) ≤ 0 (do x∗ ∈ D). Điều kiện đủ tối ưu cấp hai. Nếu (x∗ , µ∗ ,λ∗ ) thoả mãn các điều kiện • h(x∗ ) = 0, g(x∗ ) ≤ 0 (nghĩa là x∗ ∈ D) • ∇x L(x∗ , µ∗ , λ∗ ) ≡ ∇f (x∗ ) + ∇h(x∗ )T µ∗ + ∇g(x∗ )T λ∗ = 0 • λ∗j gj (x∗ ) = 0, j = 1, ..., p, λ∗ ≥ 0 • λ∗j > 0 khi gj (x∗ ) = 0 (điều kiện bù chặt) • dT ∇2xx L(x∗ , µ∗ , λ∗ )d > 0, ∀d ∈ D(x∗ ), d 6= 0, trong đó D(x∗ ) = {d : ∇hi (x∗ )T d = 0, i = 1, ..., m, ∇gj (x∗ )T d = 0, j ∈ I(x∗ )} thì x∗ là một điểm cực tiểu địa phương của bài toán (P). 1.5 PHÂN TÍCH CHOLESKY VÀ PHÂN TÍCH QR Mục này nêu cách phân tích ma trận thành nhân tử Cholesky và phân tích QR, dùng trong phương pháp giải qui hoạch toàn phương. 16 16Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1.5.1 Phân tích Cholesky Một ma trận A đối xứng, xác định dương (cấp n) có thể biểu diễn dưới dạng A = LLT , trong đó L là một ma trận tam giác dưới với các phần tử trên đường chéo dương. Phân tích Cholesky chính là tìm ma trận L đó. L có tối đa (n2 + n)/2 phần tử khác không. Chúng được xác định từ (n2 + n)/2 phương trình: a11 = (l11 )2 từ đó tính được l11 a21 = l11 l21 .. . từ đó tính được l21 an1 = l11 ln1 từ đó tính được ln1 a22 = (l21 )2 + (l22 )2 từ đó tính được l22 a23 = l21 l31 + l22 l32 .. . từ đó tính được l32 Cách phân tích này cần tất cả n3 /3 phép toán và nó được sử dụng để giải hệ phương trình tuyến tính dạng Ax = b, trong đó A là một ma trận đối xứng xác định dương và b ∈ Rn . Dùng cách phân tích Cholesky hệ này được viết thành LLT x = b và có thể giải nó theo hai bước: 1. Giải hệ Ly = b để tìm y bằng cách thế từ trên xuống dưới. 2. Giải hệ LT x = y để tìm x bằng cách thế từ dưới lên trên. Ví dụ với ma trận  1 1 A= 1 1 1.5.2 1 2 3 4 1 3 6 10   1 1  4  thì L = 1 1 10 20 1 0 1 2 3 0 0 1 3   0 1  0 , LT = 0 0 0 1 0 1 1 0 0 1 2 1 0  1 3  3 1 Phân tích QR Cho ma trận A ∈ Rm×n . Phân tích QR của ma trận A là cách biểu diễn A = QR, trong đó Q ∈ Rm×n là một ma trận trực giao và 17 17Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn R ∈ Rm×n là một ma trận tam giác trên. Nhớ rằng Q ∈ Rm×n là ma trận trực giao nếu các cột (hay các hàng) của Q tạo thành một cơ sở trực giao của Rm (nghĩa là mỗi cột có chuẩn bằng 1 và các cột trực giao nhau từng đôi một). Hơn nữa, dễ tính được ma trận nghịch đảo của Q : Q−1 = QT . Khi m = n thì phân tích QR nhận được bằng cách nhân bên trái A với n ma trận trực giao Q1 , Q2 , ..., Qn sao cho cột đầu tiên dưới đường chéo của Q1 A bằng không, hai cột đầu dưới đường chéo của Q2 Q1 A bằng không, ... , Qn Qn−1 ...Q1 A là ma trận tam giác trên. Khi đó, A = QR với Q = QT1 QT2 ...QTn và R = Qn Qn−1 ...Q1 A. Chính xác hơn, mỗi ma trận Qi qui 0 các phần tử nằm dưới đường chéo chính ở cột thứ i của ma trận Qi−1 ...Q1 A và giữ nguyên i−1 cột đầu của ma trận đó. Qi được gọi là biến đổi Householder và có dạng Qi = I − ui (ui )T , trong đó (ui )j = 0 với j = 1, 2, ..., i − 1 và các thành phần khác được chọn sao cho Qi là trực giao và tạo ra các phần tử 0 cần thiết ở cột i. Với ma trận đặc A ∈ Rm×n , để nhận được phân tích QR của A cần khoảng (4/3)m2 n phép toán. Nói riêng, khi m = n chi phí này bằng (4/3)n3 . Cách phân tích này thường được sử dụng để giải hệ phương trình tuyến tính dạng Ax = b, trong đó A ∈ Rm×n và b ∈ Rm . Hệ này trở thành: QRx = b, nghĩa là Rx = QT b. Khi đó, x được tìm bằng cách thế ngược, do R là ma trận tam giác trên. > Tóm lại, chương này giới thiệu khái quát một số kiến thức cơ bản về giải tích lồi (tâp lồi, hàm lồi, hàm lồi toàn phương), về bài toán qui hoạch toàn phương lồi, về điều kiện cần tối ưu, điều kiện đủ tối ưu cho nghiệm của bài toán tối ưu phi tuyến và một số kiến thức về ma trận có liên quan. 18 18Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Chương 2 BÀI TOÁN QUI HOẠCH TOÀN PHƯƠNG Chương này đề cập tới bài toán qui hoạch toàn phương tổng quát. Đó là bài toán tìm cực tiểu của một hàm bậc hai (có thể không lồi) với các ràng buộc tuyến tính. Nêu các điều kiện tối ưu (cần và đủ) và trình bày một số kết quả chính trong lý thuyết đối ngẫu của qui hoạch toàn phương lồi. Qui hoạch toàn phương lồi là một trường hợp riêng của qui hoạch lồi. Tuy nhiên, nhiều sự kiện trong qui hoạch toàn phương lồi có thể chứng minh trực tiếp, đơn giản mà không cần sử dụng đến các kết quả của qui hoạch lồi. Nội dung chính của chương được tham khảo trong các tài liệu [2], [3], [5] và [6]. 2.1 ĐIỀU KIỆN TỐI ƯU Qui hoạch toàn phương là lớp bài toán đơn giản nhất trong các bài toán tối ưu phi tuyến có ràng buộc. Đó 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 dạng đẳng thức hay bất đẳng thức tuyến tính. Xét qui hoạch toàn phương, ký hiệu bài toán (QP), có dạng như sau: 1 min {Q(x) = xT Cx + pT x} 2 (2.1) với các ràng buộc tuyến tính (đẳng thức và bất đẳng thức): aTi x = bi , i = 1, ..., k, (2.2) aTi x ≥ bi , i = k + 1, ..., m, (2.3) 19 19Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn