Tài liệu Ứng dụng tối ưu hóa toán học giải bài toán Markowitz tối ưu hóa danh mục đầu tư chứng khoán

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA TOÁN - CƠ - TIN HỌC Trần Thị Như Hoa ỨNG DỤNG TỐI ƯU HÓA TOÁN HỌC GIẢI BÀI TOÁN MARKOWITZ TỐI ƯU HÓA DANH MỤC ĐẦU TƯ CHỨNG KHOÁN KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC CHÍNH QUY Ngành: Toán - Tin ứng dụng Người hướng dẫn: PGS.TS Nguyễn Hữu Điển Hà Nội - 2010 LỜI CẢM ƠN Trước khi trình bày nội dung chính của khóa luận, em xin bày tỏ lòng biết ơn sâu sắc tới PGS.TS Nguyễn Hữu Điển người đã tận tình hướng dẫn để em có thể hoàn thành khóa luận này. Em cũng xin bày tỏ lòng biết ơn chân thành tới toàn thể các thầy cô giáo trong khoa Toán - Cơ - Tin học, Đại học Khoa Học Tự Nhiên, Đại Học Quốc Gia Hà Nội đã dạy bảo em tận tình trong suốt quá trình học tập tại khoa. Nhân dịp này em cũng xin được gửi lời cảm ơn chân thành tới gia đình, bạn bè đã luôn bên em, cổ vũ, động viên, giúp đỡ em trong suốt quá trình học tập và thực hiện khóa luận tốt nghiệp. Hà Nội, ngày 19 tháng 05 năm 2010 Sinh viên Trần Thị Như Hoa Mục lục Lời mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Chương 1. Một số kiến thức liên quan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.Bài toán quy hoạch tuyến tính gốc và đối ngẫu . . . . . . . . . . . . . . . . 6 1.2.Phương pháp đơn hình giải bài toán QHTT. . . . . . . . . . . . . . . . . . . . 8 Chương 2. Bài toán quy hoạch toàn phương . . . . . . . . . . . . . . . . . . . . . . . . 13 2.1.Đặt vấn đề . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2.Bài toán quy hoạch toàn phương dạng chuẩn. . . . . . . . . . . . . . . . . 13 2.2.1. Điều kiện tối ưu Karush-Kuhn-Tucker (KT) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.Phương pháp điểm trong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1. Hướng đi sử dụng phương pháp Newton-Raphson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.2. Tính toán chiều dài mỗi bước lặp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.3. Tiêu chuẩn hội tụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.4. Thuật toán điểm trong. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.Phương pháp gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.1. Ý tưởng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.2. Thuật toán gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 14 15 15 16 16 17 17 17 2.5.Phương pháp sử dụng các mở rộng của phương pháp đơn hình . . . . 18 2.5.1. Phát biểu bài toán và điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.2. Hướng giải quyết vấn đề . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 19 Chương 3. Giải bài toán Markowitz - tối ưu hóa danh mục đầu tư . . . 21 3.1.Tổng quan về bài toán Markowitz . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.1.1. Phát biểu bài toán Markowitz cơ bản và các tính chất . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.2. Các khái niệm và thông số . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.3. Thuộc tính của bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.4. Một số kết quả nghiên cứu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.Phương pháp giải bài toán Markowitz gốc . . . . . . . . . . . . . . . . . . . 3.2.1. Mô hình cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2. Điều kiện Kuhn-Tucker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.3. Trường hợp đặc biệt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.4. Tìm nghiệm cơ sở của bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.5. Ví dụ minh họa thuật giải . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 23 25 25 26 27 28 28 32 33 33 3.3.Thuật giải Markowitz tổng quát . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1. Mô hình bài toán tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2. Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.3. Tìm nghiệm cơ sở của bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.4. Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 40 42 43 45 Phụ lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3 Lời mở đầu Ngày nay, tối ưu hóa đã trở thành một lĩnh vực rất phát triển, góp phần quan trọng trong việc ứng dụng khoa học công nghệ vào cuộc sống và sản xuất. Quy hoạch toàn phương (QHTP) là một lĩnh vực của tối ưu hóa đã được phát triển từ đầu của thế kỷ 20, đến nay toàn bộ lý thuyết toán học cho lĩnh vực này có thể nói là đã rất hoàn thiện. Chúng ta có hai lý do chính để yêu thích QHTP. Đầu tiên là về mặt thực tiễn, một mô hình rất quan trọng trong vấn đề tối ưu hóa đầu tư tài chính yêu cầu giải bài toán quy hoạch toàn phương. Lý do thứ hai cho sự yêu thích của chúng ta đó là dạng bài toán và cách giải QHTP là cầu nối tới một lĩnh vực mang tính rộng lớn hơn rất nhiều đó là quy hoạch lồi. Chúng ta sẽ đi vào vấn đề ứng dụng thực tiễn của QHTP, một vấn đề mà rất nhiều người quan tâm, không chỉ các nhà toán học mà các nhà kinh tế cũng đang nghiên cứu tỉ mỉ mô hình này. Khóa luận tập trung làm rõ một số vấn đề sau: Trình bày bài toán quy hoạch toàn phương tổng quát, các phương pháp chủ yếu để giải bài toán. Sau đó đi vào bài toán Markowitz: tối ưu hóa danh mục đầu tư chứng khoán. Bài toán Markowitz được trình bày dưới 2 dạng, dạng gốc và dạng tổng quát. Và cuối cùng là các ví dụ cũng như kết quả tính toán bằng số để minh họa cho bài toán. Bố cục của khóa luận bao gồm 3 chương và 1 phụ lục: • Chương 1 của khóa luận trình bày tóm tắt về bài toán quy hoạch tuyến tính gốc và đối ngẫu, thuật toán đơn hình để giải bài toán quy hoạch tuyến tính, các định lý và kết quả cơ bản liên quan đến khóa luận. • Chương 2 của khóa luận đi vào trình bày tổng quan về bài toán quy hoạch toàn phương, một số phương pháp chủ yếu để giải bài toán như phương pháp điểm trong, phương pháp gradient, phương pháp sử dụng những mở rộng của phương pháp đơn hình. • Chương 3 trình bày các kiến thức về kinh tế liên quan, đặt bài toán Markowitz, các điều kiện để bài toán tối ưu, sau đó đi vào trình bày phương pháp giải bài toán Markowitz gốc với các ràng buộc dạng đẳng thức và bài toán Markowitz tổng quát với số ràng buộc lớn hơn, có thêm các ràng buộc dạng bất đẳng thức. • Phụ lục sử dụng bảng tính excel làm việc với bài toán trong thực tế. Do thời gian thực hiện khóa luận không nhiều, kiến thức còn hạn chế nên khi làm khóa luận không tránh khỏi những hạn chế và sai sót. Tác giả mong nhận được sự góp ý và những ý kiến phản biện của quý thầy cô và bạn đọc. Xin chân thành cảm ơn! Hà Nội, ngày 19 tháng 05 năm 2010 Sinh viên Trần Thị Như Hoa 5 Chương 1 Một số kiến thức liên quan 1.1. Bài toán quy hoạch tuyến tính gốc và đối ngẫu Bài toán quy hoạch tuyến tính[1] (QHTT) tổng quát có thể được phát biểu dưới dạng: n min(max){ f (x) := ∑ c jx j} (1.1) j=1   ∑nj=1 ai j x j = bi , i = 1, . . . , m1 ,     n a x ≤ b , i = m + 1, . . . , m , ∑ j=1 i j j i 1 2 thỏa mãn: D := n  ∑ j=1 ai j x j ≥ bi , i = m2 + 1, . . . , m,     l j ≤ x j ≤ u j , j = 1, . . . , n. trong đó x j gọi là các biến, c j gọi là thành phần của véctơ hệ số hàm mục tiêu (hàm giá), ai j gọi là hệ số ràng buộc, bi gọi là hệ số vế phải, l j < u j lần lượt gọi là các cận dưới và cận trên (giới hạn dưới và trên) của biến x j (i = 1, . . . , m, j = 1, . . . , n). Để nghiên cứu tính chất và các phương pháp giải bài toán quy hoạch tuyến tính (1.1) người ta thường chuyển bài toán này về một trong hai dạng chính tắc và chuẩn tắc. Trong khóa luận này chỉ để cập đến bài toán quy hoạch tuyến tính dạng chính tắc như sau: min f (x) = cT x thỏa mãn: D p = ( Ax = b x ≥ 0. (1.2) Trong đó x = (x1 , . . . , xn )T gọi là các biến cần tối ưu, c = (c1 , . . . , cn )T là véctơ hàm mục tiêu, ma trận A = (ai j )m×n là ma trận hệ số ràng buộc và b = (b1 , . . . , bm )T gọi là véctơ vế phải. Hàm f gọi là hàm mục tiêu, tập D p gọi 6 là tập ràng buộc. Ma trận A được giả thiết là có hạng đủ, rank A = m ≤ n và bài toán gọi là bài toán QHTT gốc, ký hiệu là (P). Một điểm x ∈ D p gọi là một điểm (hay phương án) chấp nhận được. Điểm ∗ x ∈ D p gọi là nghiệm (hay phương án tối ưu) của bài toán (1.2) nếu f (x∗ ) ≤ f (x) với mọi x ∈ D p . Vì D p là tập lồi đa diện, nên x ∈ D p là đỉnh của D p thì x gọi là phương án cực biên (phương án cơ sở). Nếu x∗ là điểm cực biên (đỉnh) của D p và tối ưu thì x∗ gọi là phương án cực biên tối ưu. Cho một phương án cơ sở (hay một đỉnh) x, ký hiệu J+ (x) = { j ∈ {1, . . . , n} : x j > 0} gọi là tập chỉ số cơ sở của x. Nếu |J+ (x)| = m thì x gọi là phương án không suy biến, còn nếu |J+(x)| < m thì x gọi là phương án suy biến. Ta công nhận kết quả sau: tập hợp các véctơ B+ (x) = {A j | j ∈ J+ (x)} (1.3) gồm các véctơ cột của A sẽ là một hệ độc lập tuyến tính. Nếu r := |J+ (x)| < m thì ta bổ sung thêm m − r véctơ còn lại của A vào B+ (x) sao cho ta thu được hệ gồm m véctơ cột của A độc lập tuyến tính, ký hiệu là B(x). Hệ véctơ B(x) gọi là hệ véctơ cơ sở (hay gọi tắt là cơ sở) của phương án cực biên x. Thông thường ta thường gọi J(x) là tập chỉ số cơ sở thay cho gọi cơ sở B(x). Lập hàm Lagrange cho bài toán QHTT gốc (P) như sau: L(x, y, s) = cT x + yT (b − Ax) + sT x (1.4) trong đó y và s ≥ 0 là các nhân tử Lagrange. Khi đó bài toán đối ngẫu (dạng Lagrange) của bài toán gốc (P) sẽ có dạng (sẽ ký hiệu là (D)): max g(y, s) = bT y ( AT y + s = c thỏa mãn: Dd = s ≥ 0. (1.5) Biến s gọi là biến bù, g gọi là hàm mục tiêu đối ngẫu và Dd gọi là miền ràng buộc đối ngẫu. Hiển nhiên Dd cũng là tập lồi đa diện và bài toán (1.5) cũng là bài toán QHTT. Với mọi bộ ba (x, y, s) sao cho x ∈ D p và (y, s) ∈ Dd ta đặt τ (x, y, s) = f (x) − g(y, s) = sT x, (1.6) gọi là khoảng trống đối ngẫu. Theo định lý đối ngẫu yếu thì τ (x, y, s) ≥ 0, và nếu τ (x, y, s) = 0 thì (x, y, s) sẽ là nghiệm của cặp bài toán gốc đối ngẫu (P)(D). Còn theo định lý đối ngẫu mạnh thì nếu x∗ là nghiệm tối ưu của bài toán gốc (P) thì sẽ tồn tại nghiệm tối ưu (y∗ , s∗ ) của bài toán đối ngẫu (D) sao cho τ ∗ = τ (x∗ , y∗ , s∗ ) = 0 và ngược lại. 7 1.2. Phương pháp đơn hình giải bài toán QHTT. Một trong những phương pháp nổi tiếng và hiệu quả là phương pháp đơn hình, được G. B. Dantzig phát minh ra năm 1947. Phần này sẽ trình bày tóm tắt lại tư tưởng cơ bản và nội dung của phương pháp đơn hình, phương pháp này sẽ được sử dụng để tính toán nhiều trong khóa luận. Trước hết ta chỉ ra một tính chất quan trọng của bài toán quy hoạch tuyến tính là nghiệm sẽ nằm ở điểm cực biên. Bổ đề 1.2.1. Giả sử bài toán QHTT gốc (1.2) có nghiệm tối ưu thì nó sẽ có nghiệm tối ưu x∗ nằm ở đỉnh. Do tính chất đặc biệt của bài toán QHTT nên thuật toán đơn hình đã tận dụng rất hiệu quả các tính chất này để tạo ra một thuật toán rất hiệu quả. Đặc biệt là các tính chất: • Miền ràng buộc của bài toán QHTT là một tập lồi đa diện với số điểm cực biên là hữu hạn. • Nếu bài toán QHTT có nghiệm tối ưu thì sẽ có nghiệm tối ưu nằm ở đỉnh. Ý tưởng của thuật toán Bước 1: Xuất phát từ một đỉnh x0 của miền ràng buộc. Bước 2: Nếu x0 là nghiệm tối ưu, dừng thuật toán. Nếu không chuyển sang bước 3. Bước 3: Từ x0 tìm cách di chuyển đến đỉnh kề tiếp theo của miền ràng buộc tốt hơn đỉnh x0 (theo nghĩa giá trị hàm mục tiêu nhỏ hơn). Bước 4: Lặp lại Bước 2, 3 với x0 thay bằng x1 . Do số đỉnh của miền ràng buộc là hữu hạn, nên nếu bài toán có nghiệm, sau hữu hạn bước ta sẽ tìm được đỉnh tối ưu. Có nhiều vấn đề cần giải quyết trong phương pháp đơn hình, bao gồm: • Tìm đỉnh xuất phát, vấn đề này thường được giải quyết dựa vào phương pháp hai pha hoặc đánh thuế (hai phương pháp này cũng cho biết miền ràng buộc có rỗng hay không). • Kiểm tra bài toán có nghiệm hay vô nghiệm (có bị chặn dưới hay không). • Kiểm tra đỉnh x0 có là tối ưu hay không? • Từ đỉnh x0 làm thế nào di chuyển đến đỉnh x1 tốt hơn x0 ? 8 Thuật toán đơn hình. • Đầu vào: Ma trận A = (ai j )m×n , véctơ b, véctơ c. Phương án cơ sở x0 và cơ sở tương ứng J(x0 ). • Đầu ra: Phương án cơ sở tối ưu x∗ và giá trị mục tiêu tối ưu f (x∗ ) hoặc chỉ ra bài toán không có nghiệm tối ưu (tức là hàm mục tiêu không bị chặn dưới). • Thuật toán: Bước khởi tạo: 1. Tìm một phương án cơ sở xuất phát x0 ứng với cơ sở xuất phát J0 := B(x0 ). 2. Tính các hệ số khai triển Z = (z jk ) và các ước lượng ∆k theo các công thức tương ứng sau    Ak = ∑ j∈J0 z jk A j ∀ j = 1, n ∆k = ∑ j∈J0 z jk c j − ck ∀k ∈ / J0   ∆ = 0 ∀k ∈ J0 k Bước 1: Kiểm tra tiêu chuẩn tối ưu. 1. Nếu ∆k ≤ 0 với mọi k ∈ / J0 thì x0 là phương án tối ưu. Kết thúc thuật toán. 2. Nếu ∃∆k > 0, chuyển sang bước 2. Bước 2: Kiểm tra tính bị chặn của hàm mục tiêu. Với mỗi k ∈ / J0 mà ∆k > 0 ta kiểm tra các hệ số khai triển Zk = (z jk ). 1. Nếu có một ∆k > 0 mà tất cả các hệ số khai triển z jk ≤ 0, (∀ j ∈ J0 ) thì kết luận hàm mục tiêu không bị chặn dưới. Bài toán không có phương án hữu hạn. Kết thúc thuật toán. 2. Nếu với mọi k ∈ / J0 mà tồn tại ít nhất một hệ số z jk > 0 thì tiến hành tìm phương án mới x1 tốt hơn x0 bằng cách chuyển sang bước 3. Bước 3: Tìm phương án mới 1. Chọn véctơ As đưa vào cơ sở: Có thể bất kỳ s ∈ / J ) sao cho ∆s > 0. Thông thường chọn s sao cho ∆s lớn nhất 2. Chọn véctơ Ar đưa ra khỏi cơ sở theo quy tắc: 9 3. Tính phương án mới x1 và giá trị hàm mục tiêu mới theo công thức:   / J0 , k 6= s  00 với k ∈ x1 = zxr với k = s rs   x0 − x0r z j ∈ J0 j zrs js với x0r f (x ) = f (x ) − ∆s zrs 1 0 Bước 4: Tính các hệ số khai triển và ước lượng mới theo công thức ( zrk nếu j = s 1 z jk = zrs z z jk − zrkrs z js nếu j ∈ J0 , j = r zrk ∆1k = ∆k − ∆s zr s Bước 5: Quay về bước 1 với phương án cơ sở mới x1 và cơ sở mới J1 := J(x1 ). Để thuật tiện cho việc "thực hành" thuật toán đơn hình giải bài toán QHTT dạng chuẩn tắc. Ta sử dụng một bảng gọi là Bảng đơn hình gồm n + 3 cột và m + 3 hàng như sau: Cơ sở cJ Phương án 1 2 J xJ c1 c2 J1 c j1 x j1 z j1 1 z j1 2 J2 c j2 x j2 z j2 1 z j2 2 .. .. .. .. .. . . . . . Jm c jm x jm z jm 1 z jm 2 f (x) ∆1 ∆2 ··· k · · · ck · · · z j1 3 · · · z j2 3 .. .. . . · · · z jm 3 · · · ∆k ··· n · · · cn · · · z j1 n · · · z j2 n .. .. . . · · · z jm n · · · ∆n Lưu ý phần bảng dành cho các hệ số khai triển z jk : • Các cột ứng với các j ∈ J0 sẽ là các véctơ đơn vị với hệ số 1 nằm trên dòng với chỉ số j. • Với k ∈ / J0 thì cột k của bàng đơn hình là hệ số khai triển của Ak của ma trận A theo cơ sở J0. Ta ký hiệu cột này là Zk nghĩa là Ak = BJ0 Zk hay Zk = (BJ0 )−1 Ak , ở đây BJ0 là ma trận cơ sở (BJ0 = A j | j ∈ J0. Đặc biệt khi ta chọn được một ma trận BJ0 có dạng ma trận đơn vị thì hệ số khai triển trên các cột j với j ∈ J0 sẽ chính là cột véctơ đơn vị z jk = e j , còn các hệ số khai triển trên các cột k ∈ / J0 chính là z jk = Ak . 10 • Dòng ước lượng là dòng cuối cùng của bảng và được tính bởi∆k = cTJ0 Zk − ck và ∆ j = 0, (∀ j ∈ J0 ). • Giá trị hàm mục tiêu chính là f (x) = cTJ0 xJ ) . Một trong những chi tiết quan trọng trong phương pháp đơn hình là: Từ nghiệm x∗ của bài toán gốc (P), ta có xây dựng lại được nghiệm đối ngẫu hay không?. Phương pháp đơn hình gốc - đối ngẫu sẽ cho phép thu được bộ ba nghiệm (x∗ , y∗ , s∗ ) cho cặp bài toán gốc, đối ngẫu. Trên thực tế, ta có thể xuất phát từ nghiệm của bài toán gốc (P) là x∗ với cơ sở AJ ∗ , ta có thể thu được nghiệm của bài toán đối ngẫu (D) như sau: • Giả sử x∗ là nghiệm của bài toán gốc (P) ứng với cơ sở tối ưu AJ ∗ . Khi đó ta có: x∗J ∗ = A−1 J ∗ b, với x∗J ∗ = (x∗j ) j∈J ∗ và (x∗j ) j∈J ∗ = (0). • Khi đó AJ ∗ cũng sẽ là cơ sở đối ngẫu của bài toán đối ngẫu (D) và nghiệm đối ngẫu (y∗ , s∗ ) được tính theo công thức: T y∗ = (A−1 J ∗ ) cJ ∗ , s∗ = c − AT y∗ , trong đó cJ ∗ = (c j ) j∈J ∗ . • Khi đó khoảng trống đối ngẫu sẽ là: τ ∗ = (x∗ )T s∗ = 0. Theo định lý về độ lệch bù thì nếu x∗j > 0 thì s∗j = 0, do đó dễ thấy s∗J ∗ = 0. Trong thực tế, bài toán QHTT thường không phải là bài toán dạng chuẩn tắc với véctơ vế phải b không âm, nên ta không thể có ngay được phương án xuất phát x0 để thực hiện phương pháp đơn hình. Do vậy người ta thường sử dụng một trong hai phương pháp: Phương pháp đơn hình hai pha và phương pháp đánh thuế. Trong khóa luận này sẽ sử dụng phương pháp đơn hình hai pha với nội dung được tóm tắt như sau: Trước hết, đối với bài toán gốc (P), không mất tính tổng quát ta có thể xem các bi ≥ 0 với mọi i = 1, m . Nếu trái lại ta nhân hai vế của ràng buộc thứ i với −1. Ta lập bài toán phụ sau m min fa (u) := ∑ un+ j (1.7) j=1  n   ∑ j=1 ai j x j + un+i = bi , thoả mãn Da := x j ≥ 0, ( j = 1, n)   un+i ≥ 0, (i = 1, m) 11 (i = 1, m) Các biến un+i với (i = 1, m) gọi là các biến giả. Nếu ta ký hiệu e = (1, 1, . . . , 1)T là véctơ gồm m thành phần là 1, u = (un+1 , un+2 , . . . , un+m )T và E là ma trận đơn vị cấp m thì ta có thể viết bài toán trên dưới dạng fa (u) := eT u ( Ax + Eu = b thoả mãn Da := x ≥ 0, u ≥ 0 min (1.8) Khi đó, quan hệ giữa hai bài toán (1.7) và (1.8) được chỉ ra như sau: • Bài toán (1.8) có một phương án cơ sở xuất phát là (x, u)T := (0, b)T . • Bài toán (1.2) có phương án chấp nhận được khi và chỉ khi bài toán phụ (1.8) có phương án tối ưu (x, u)T với tất cả các biến giả un+i = 0, (i = 1, m. Do đó phương pháp đơn hình hai pha được thực hiện như sau: Pha 1: Lập bài toán phụ cho bài toán (P), giải bài toán phụ bằng phương pháp đơn hình. Nếu bài toán phụ vô nghiệm hoặc có nghiệm không là nghiệm chấp nhận của bài toán (P), dừng thuật toán. Ngược lại, chuyển sang pha 2. Pha 2: Sử dụng thuật toán đơn hình giải bài toán (P) với phương án xuất phát thu được từ pha 1. 12 Chương 2 Bài toán quy hoạch toàn phương 2.1. Đặt vấn đề Chúng ta vừa xét bài toán QHTT với hàm mục tiêu và các ràng buộc là tuyến tính. Trong thực tế thì có một số lượng lớn các ứng dụng, bài toán mà hàm mục tiêu của chúng không ở dạng tuyến tính mà có dạng bậc hai. Những bài toán mà hàm mục tiêu là bậc hai của các biến tối ưu và tất cả các ràng buộc là tuyến tính thì bài toán có dạng quy hoạch toàn phương (QHTP). Với bài toán dạng này thì các phương pháp giải có mối quan hệ tới các mở rộng của bài toán quy hoạch tuyến tính. Trong phần đầu tiên sẽ giới thiệu về bài toán quy hoạch toàn phương dạng chuẩn và điều kiện tối ưu Karush Kunh Tucker. Phần 2, 3 và 4 sẽ đề cập tới phương pháp điểm trong, phương pháp active-set, phương pháp gradient để giải quyết bài toán. Trong phần cuối chương sẽ đề cập đến phương pháp sử dụng các mở rộng của phương pháp đơn hình để giải bài toán QHTP. 2.2. Bài toán quy hoạch toàn phương dạng chuẩn Bài toán quy hoạch toàn phương dạng chuẩn phát biểu dưới dạng: 1 min cT x + xT Qx 2 ( Ax = b thỏa mãn: x≥0 (a) (b) (2.1) Trong đó xn×1 là biến tối ưu, Am×n là ma trận ràng buộc bm×1 là véctơ của các ràng buộc vế phải, cn×1 là véctơ của hàm mục tiêu, Qn×n là ma trận trong hàm mục tiêu. Dễ thấy rằng bài toán quy hoạch toàn phương là lồi khi Qn×n là ma trận vuông xác định dương. 13 2.2.1. Điều kiện tối ưu Karush-Kuhn-Tucker (KT) Điều kiện KT [4] này là điều kiện cần và đủ để bài toán có nghiệm. Các điều kiện tối ưu này gắn với việc chuyển bài toán QHTP về dạng bài toán không ràng buộc bằng cách xét hàm Lagrange. Hàm Lagrange[4] gắn với bài toán (1.1) có dạng như sau: 1 L(x, u, v, s) = cT x + xT Qx + uT (−x + s2 ) + vT (−Ax + b) 2 Trong đó u ≥ 0 là nhân tử Lagrange liên kết với ràng buộc bất đẳng thức x ≥ 0 , s là biến phụ liên kết với ràng buộc x ≥ 0, vm×1 là nhân tử Lagrange liên kết với ràng buộc Ax = b (hay −Ax + b = 0) Lấy vi phân hàm Lagrange theo từng biến ta được: ∂L = 0 → c + Qx − u − AT v = 0 ∂x ∂L = 0 → Ax − b = 0 ∂v ∂L = 0 → −x + s2 = 0 ∂u ∂L = 0 → ui si = 0 i = 1 . . . n ∂s ui ≥ 0 i = 1 . . . n (2.2) Điều kiện tối ưu của bài toán QHTP đạt được khi giải quyết hệ phương trình sau: (a) Ax − b = 0 (Điều kiện cơ sở) T (b) − Qx + A v + u = c (Điều kiện đối ngẫu) (c) ui xi = 0 i = 1 . . . n (Điều kiện phụ bổ sung) (d) xi ≥ 0, ui ≥ 0 i = 1 . . . n (2.3) Định nghĩa ma trận chéo cỡ n × n: U = diag[ui ] X = diag[xi ] Và véctơ e: eT = (1 . . . 1) Điều kiện phụ bổ sung (2.3 c) được viết lại như sau: XUe = 0. 2.3. Phương pháp điểm trong Phương pháp điểm trong (interior point method) cơ bản đi giải quyết hệ phương trình (2.3). Hệ (2.3) là phi tuyến bởi điều kiện (2.3 c). Chúng ta sẽ sử dụng một phương pháp lặp như Newton-Raphson để giải hệ phương trình này. 14 Các phương trình tuyến tính sẽ thỏa mãn ở mỗi bước lặp, với phương trình (2.3 c) không thỏa mãn ở mỗi bước, ta sử dụng một tham số µ > 0 để chỉ thị lỗi này. Điều kiện (2.3 c) được viết lại như sau: XUe = µ e 2.3.1. Hướng đi sử dụng phương pháp Newton-Raphson Ở mỗi lần lặp ta cần tính toán giá trị mới của (2n + m) biến (x, u, v). Sử dụng phương pháp Newton-Raphson giá trị mới của các biến đạt được bằng cách giải hệ sau:      Axk − b dx A 0 0 −Q I AT  du  = − −Qx + AT vk + uk − c . dv XUe − µ k e U X 0 Biến đổi hệ này ta tính được dv : A[XQ +U]−1 XAT dv = r p + A[XQ +U]−1 (Xrd − rc ) Biết dv ta tính được dx , du : dx = [XQ +U]−1 (XAT dv − Xrd + rc ) du = X −1 (rc −Udx ) 2.3.2. Tính toán chiều dài mỗi bước lặp Kí hiệu α là chiều dài mỗi bước lặp, ta có công thức tính phần tử thứ (k + 1) qua phần tử thứ k như sau: xk+1 = xk + α p dx uk+1 = uk + αd du vk+1 = vk + αd dv (2.4) Chiều dài của mỗi bước được chọn: xi , dxi < 0] dxi ui αd = β min[1, − , dui < 0] dui 0 ≤ β ≤ 1, β thường lấy bằng 0, 999 α p = β min[1, − 15 (2.5) 2.3.3. Tiêu chuẩn hội tụ Với ε1 , ε2 , ε3 là các số dương nhỏ. Sử dụng tính chất tối ưu: ||Axk − b|| ≤ ε1 ||b|| + 1 ||rd || ≤ ε2 δd = ||Qxk + c|| + 1 (xk )T u k , n là số biến tối ưu µ ≤ ε3 Với µ = n Với ý tưởng như trên, thuật toán điểm trong[4] được mô tả như sau: δp = (2.6) 2.3.4. Thuật toán điểm trong. Bước khởi tạo: Đầu tiên khởi tạo k = 0, giá trị tùy ý (≥ 0) của x, u, v ví dụ xk = uk = e = (1 . . . 1) và vk = 0 Điểm kế tiếp xk+1 được tính như sau: (xk )T u ] [ n k Bước 1: Kiểm tra tiêu chuẩn hội tụ. Đặt µ = (k + 1) Kiểm tra điều kiện ||Axk − b|| ≤ ε1 ||b|| + 1 ||rd || ≤ ε2 δd = ||Qxk + c|| + 1 µ ≤ ε3 (2.7) r p = −Axk + b rd = Qxk − AT vk − uk + c rc = −XUe + µ k e (2.8) δp = Bước 2: Tính r p , rd , rc Bước 3: Tìm dv Bước 4: Tìm dx , du . Bước 5: Tính toán bước tăng α p ,α d . Bước 6: Tính giá trị điểm kế tiếp xk+1 , uk+1 , vk+1 . 16 2.4. Phương pháp gradient 2.4.1. Ý tưởng Ta biết rằng véctơ gradient của f tại x0 có dạng: δ f (x0 ) δ f (x0 ) δ f (x0 ) ∇ f (x ) = ( , ,..., ) δ x1 δ x2 δ xn 0 Véctơ gradient ∇ f (x0 ) chỉ ra hướng tăng nhanh nhất của hàm mục tiêu tại x0 . Vậy véctơ −∇ f (x0 ) gọi là đối gradient chỉ ra hướng giảm nhanh nhất của hàm mục tiêu tại x0 . Từ ý tưởng trên thì thuật toán gradient[1] được phát biểu như sau: 2.4.2. Thuật toán gradient • Đầu vào: Ma trận A = (ai j )m×n , véctơ b, véctơ c. Phương án cơ sở x0 và cơ sở tương ứng J(x0 ). • Đầu ra: Phương án cơ sở tối ưu x∗ và giá trị mục tiêu tối ưu f (x∗ ) hoặc chỉ ra bài toán không có nghiệm tối ưu (tức là hàm mục tiêu không bị chặn dưới). • Thuật toán: Bước 1: Tìm phương án x0 thuộc miền ràng buộc M, cho k = 0. Bước 2: Đã có xk (k ≥ 0) ta xác định độ dài bước: Việc dịch chuyển từ t k theo hướng −∇ f (xk ) tới điểm xk + [−∇ f (xk )]λ kéo theo biến đổi hàm f một số gia: ∆ f = − f [xk − ∇ f (xk )λ ] + f (xk ) Giá trị λ mà với nó số gia ∆ f đạt giá trị lớn nhất (tức là hàm f giảm được nhiều nhất) có thể xác định tại điểm dừng của hàm ∆ f : ∆f = 0 ≈ −∇ f [xk − ∇ f (xk )λ ](−∇ f (xk ) = 0 dλ (*) Từ phương trình (*) ta tìm được điểm dừng λ ∗ . d 2∆ f ∗ Nếu tại điểm dừng λ ta có < 0 thì ta có điểm cực đại λ ∗ của ∆ f . 2 dλ Do đó: xk+1 = xk + [−∇ f (xk )]λ ∗ 17 Bước 3: Thử xem xk+1 có thuộc M? Nếu điểm xk+1 vượt ra khỏi miền ràng buộc thì ta phải rút ngắn bước λ sao cho được một điểm trên biên theo hướng đã chọn. Bước 4: Kiểm tra xk+1 là điểm tối ưu hay không? 1. Nếu ∇ f (xk+1 ) = 0 thì xk+1 là điểm tối ưu. 2. Nếu ∇ f (xk+1 ) 6= 0 thì xk+1 chưa là điểm tối ưu, ta tăng k lên 1 và quay trở lại bước 2. 2.5. Phương pháp sử dụng các mở rộng của phương pháp đơn hình Trong chương thứ nhất chúng ta đã đi tìm hiểu phương pháp đơn hình và ứng dụng để giải các bài toán quy hoạch tuyến tính, trong phần này ta sẽ xẽ xem xét những mở rộng của phương pháp này[6] để giải bài toán quy hoạch toàn phương. Đầu tiên ta kiểm tra điều kiện Karush Kuhn-Tucker (KKT) cho bài toán quy hoạch toàn phương và nhận thấy từ điều kiện này trả về một hệ các phương trình tuyến tính và các ràng buộc bổ sung, để giải được hệ này cần sử dụng tới các mở rộng của phương pháp đơn hình. 2.5.1. Phát biểu bài toán và điều kiện tối ưu Dạng của bài toán quy hoạch toàn phương với các ràng buộc bất đẳng thức 1 min f (x) = cT x + xT Qx 2 ( Ax ≤ b (a) thỏa mãn: x≥0 (b) Hàm Lagrange gắn với bài toán: 1 L(x, µ ) = cx + xT Qx + uT (−x + s2 ) + µ (Ax − b) 2 18 (2.9) Trong đó µm×1 là nhân tử Lagrange liên kết với ràng buộc Ax ≤ b.Điều kiện KKT cho tối ưu cục bộ của bài toán là: δL ≥ 0, δxj δL ≤ 0, δµj δL = 0, xj δxj µ j gi (x) = 0, x j ≥ 0, µ j ≥ 0, j = 1...n c + xT Q + µ A ≥ 0 (a) i = 1...m Ax − b ≤ 0 (b) j = 1...n xT (cT + Qx + AT µ ) = 0 (c) i = 1...m j = 1...n i = 1...m µ (Ax − b) = 0 x≥0 µ ≥0 (d) (e) (f) (2.10) Biến đổi các phương trình (2.10 a) - (2.10 e) về dạng bài toán giải dễ dàng hơn bằng cách thêm biến phụ không âm y ∈ Rn vào bất đẳng thức (2.10 a) và v ∈ Rm vào bất đẳng thức (2.10 b) ta được cT + Qx + AT µ T − y = 0 và Ax − b + v = 0 Với việc di chuyển các hằng số về bên phải, điều kiện KKT được viết lại như sau: Qx + AT µ T − y = −cT (a) Ax + v = b (b) (2.11) (c) x ≥ 0, µ ≥ 0, y ≥ 0, v ≥ 0 yT x = 0, µ v = 0 (d) 2.5.2. Hướng giải quyết vấn đề Ta chuyển bài toán (2.11 a) - (2.11 d) về dạng của bài toán quy hoạch tuyến tính, khi đó ta sẽ áp dụng được thuật toán đơn hình với bài toán này. Để chuyển bài toán về dạng tuyến tính thì cần biến đổi dạng của phương trình (2.11 d). • Nếu các giá trị vế phải là âm thì nhân phương trình với (-1). • Thêm các biến giả vào mỗi phương trình. • Ta lập bài toán phụ với hàm mục tiêu là tổng của các biến giả trên. Bài toán phụ sẽ giải theo phương pháp đơn hình (cụ thể là thuật toán đơn hình hai pha đề cập ở chương một). Để minh họa cho phương pháp này chúng ta xét ví dụ sau: Ví dụ: min f (x) = −8x1 − 16x2 + x21 + 4x22 thỏa mãn: x1 + x2 ≤ 5, x1 ≤ 3, x1 ≥ 0, x2 ≥ 0 19 (2.12)