Luận văn Thạc sĩ Toán học: Quy hoạch toàn phương

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PDF | Số trang:58

Thêm vào BST

Báo xấu

161
lượt xem 18
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn Thạc sĩ Toán học: Quy hoạch toàn phương tập trung làm rõ tính chất của bài toán quy hoạch toàn phương; phương pháp giải bài toán quy hoạch toàn phương. Mời các bạn tham khảo luận văn để hiểu rõ hơn về những nội dung này.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Quy hoạch toàn phương

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH Nguyễn Mai Anh Phương QUY HOẠCH TOÀN PHƯƠNG LUẬN VĂN THẠC SĨ TOÁN HỌC Thành phố Hồ Chí Minh – 2012
BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH Nguyễn Mai Anh Phương QUY HOẠCH TOÀN PHƯƠNG Chuyên ngành: Toán Giải Tích Mã số: 60 46 01 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC TS. Trịnh Công Diệu Thành phố Hồ Chí Minh – 2012
Lời Cảm Ơn Trước khi trình bày nội dung của luận văn, tôi xin bày tỏ lòng biết ơn sâu sắc tới TS. Trịnh Công Diệu người đã tận tình hướng dẫn để tôi có thể hoàn thành luận văn này. Tôi 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ô đã tham gia giảng dạy lớp cao học toán giải tích khóa 21, cảm ơn các thầy cô trong ban giám hiệu và phòng sau đại học của trường Đại học sư phạm Tp. Hồ Chí Minh. Nhân dịp này tôi cũng xin được gửi lời cảm ơn tới gia đình, bạn bè đã luôn bên tôi cổ vũ, động viên, giúp đỡ tôi trong suốt quá trình học tập và thực hiện luận văn. Tp. Hồ Chí Minh, năm 2012 Nguyễn Mai Anh Phương
Mục Lục Lời Nói Đầu ................................................................................................................1 Một Số Kí Hiệu ..........................................................................................................3 Chương 1: MỞ ĐẦU .................................................................................................4 1.1. Một số kiến thức bổ sung .................................................................................4 1.1.1. Tập lồi .......................................................................................................4 1.1.2. Hàm lồi ......................................................................................................7 1.1.3. Ma trận nửa xác định dương, nửa xác định âm .........................................9 1.2. Một số kết quả cơ bản trong lý thuyết tối ưu ...................................................9 1.2.1. Định nghĩa .................................................................................................9 1.2.2. Tính chất..................................................................................................10 1.3. Định nghĩa bài toán quy hoạch toàn phương .................................................11 1.3.1. Định nghĩa hàm toàn phương ..................................................................11 1.3.2. Định nghĩa bài toán quy hoạch toàn phương ..........................................11 1.3.3. Các dạng quy hoạch toàn phương ...........................................................13 Chương 2: TÍNH CHẤT CỦA BÀI TOÁN QUY HOẠCH TOÀN PHƯƠNG 14 2.1. Điều kiện tồn tại nghiệm ................................................................................14 2.1.1. Định lý Frank-Wolfe ...............................................................................14 2.1.2. Định lý Eaves ..........................................................................................20 2.2. Tính chất tập nghiệm của bài toán quy hoạch toàn phương ..........................28 2.2.1. Tính bị chặn của tập nghiệm ...................................................................28 2.2.2. Tính đóng của tập nghiệm .......................................................................31 2.2.3. Tính hữu hạn của tập nghiệm ..................................................................32 2.2.4. Tính lồi đa diện của tập nghiệm ..............................................................33 2.2.5. Tính chất của tập Sol ( P ) ∩ int ∆ ............................................................34 Chương 3: PHƯƠNG PHÁP GIẢI BÀI TOÁN QUY HOẠCH TOÀN PHƯƠNG .................................................................................................................35 3.1. Điều kiện Kuhn-Tucker .................................................................................35 3.2. Thuật toán giải quy hoạch toàn phương lồi ...................................................37
3.2.1. Thuật toán Wolfe.....................................................................................38 3.2.2. Ví dụ minh họa ........................................................................................45 Kết Luận...................................................................................................................52 Tài Liệu Tham Khảo ...............................................................................................53
1 Lời Nói Đầu Lý thuyết tối ưu (ta thường gọi là bài toán Quy hoạch) có nhiều áp dụng trong thực tế. Trong chương trình học đại học đã có giáo trình Quy hoạch tuyến tính trình bày phương pháp giải các bài toán Quy hoạch tuyến tính. Tuy nhiên, khi xây dựng mô hình toán cho một vấn đề thực tế không phải lúc nào ta cũng có mô hình tuyến tính. Chẳng hạn, Harry Markowitz đã mô hình hóa quá trình lựa chọn danh mục đầu tư chứng khoán (nhờ đó nhận được giải Noben kinh tế năm 1990) dưới dạng một bài toán Quy hoạch mà hàm mục tiêu không phải là tuyến tính. Mục tiêu của bài toán Markowitz là tìm tỉ trọng của các chứng khoán trong danh mục đầu tư sao cho giảm tới mức tối thiểu phương sai (rủi ro) của danh mục mà đạt được một mức thu nhập đã định. Giải liên tiếp các bài toán với các mức thu nhập mục tiêu người ta xác định được một tập hợp các danh mục đầu tư có hiệu quả. Từ đây nhà đầu tư có thể lựa chọn một danh mục nằm trong tập hợp này dựa trên quan điểm của mình về việc đánh đổi giữa thu nhập và rủi ro. Mô hình toán học như sau: n n min= S p2 f= ( x) ∑∑ x x s =i 1 =j 1 i j ij với các ràng buộc: n ∑xr = r, i =1 i i n ∑x i =1 i = 1, 0 ≤ xi ≤ 1 (i = 1, 2,..., n) Trong đó, • S p2 là phương sai thu nhập của danh mục đầu tư. • xi là tỉ trọng của chứng khoán i trong danh mục đầu tư gồm n chứng khoán. • ri là thu nhập kỳ vọng của chứng khoán i . • r là thu nhập dự tính của toàn bộ danh mục đầu tư.
2 Cũng có rất nhiều vấn đề trong thực tế khi mô hình hóa lên cũng có dạng tương tự như trường hợp trên và trong nghiên cứu về lý thuyết tối ưu đã có một hướng nghiên cứu dành cho lớp các bài toán có dạng này: min{xT Qx + cT x + α | x ∈ ∆} với Q ∈  nS×n (là ma trận đối xứng cấp n), c ∈  n , α ∈  và ∆ ∈  n là tập lồi đa diện. Người ta gọi lớp các bài toán Quy hoạch có dạng trên là bài toán Quy hoạch toàn phương. Đó chính là đối tượng được khảo sát trong luận văn: Quy hoạch toàn phương. Bố cục của luận văn bao gồm 3 chương: • Chương 1: Mở đầu. Trình bày một số khái niệm và tính chất cơ bản của giải tích lồi, của lý thuyết tối ưu và định nghĩa bài toán quy hoạch toàn phương. • Chương 2: Tính chất của bài toán Quy hoạch toàn phương. Trình bày định lý tồn tại nghiệm và các tính chất tập nghiệm của bài toán quy hoạch toàn phương. • Chương 3: Phương pháp giải bài toán Quy hoạch toàn phương. Chương này đề cập đến phương pháp giải Quy hoạch toàn phương lồi dựa trên sự mở rộng của phương pháp đơn hình. Do thời gian thực hiện luận văn không nhiều, kiến thức còn hạn chế nên khi làm luận văn không tránh khỏi những hạn chế và sai sót. 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! Tp. Hồ Chí Minh, năm 2012 Nguyễn Mai Anh Phương
3 Một Số Kí Hiệu Kí hiệu Nghĩa của kí hiệu n Không gian các vec tơ n chiều.  n×m Không gian các ma trận cấp n × m .  nS×m Không gian các ma trận đối xứng cấp n × m . xT Vectơ chuyển vị của vectơ x ( x là ma trận cột tọa độ). AT Ma trận chuyển vị của ma trận A . 〈.,.〉 Tích vô hướng của hai vectơ. affM Bao affine của tập M. extrM Tập các điểm cực biên của M. domf Miền hữu hiệu của hàm f . epif Trên đồ thị của hàm f . ∆ ( A, b ) Tập ràng buộc của bài toán Quy hoạch toàn phương (QHTP) xác định bởi Ax ≥ b . Sol ( P ) Tập nghiệm của bài toán QHTP. loc( P ) Tập nghiệm cực tiểu địa phương của bài toán QHTP.  Kết thúc chứng minh.
4 Chương 1: MỞ ĐẦU 1.1. Một số kiến thức bổ sung 1.1.1. Tập lồi 1.1.1.1. Tập affine Cho x1 , x 2 là hai điểm trong  n . Tập hợp tất cả các điểm x ∈  n sao cho: x= λ x1 + (1 − λ ) x 2 , ∀λ ∈  được gọi là đường thẳng đi qua x1 và x 2 . Tập M ⊆  n được gọi là tập affine nếu M chứa trọn cả đường thẳng đi qua hai điểm bất kỳ của M , tức là: ∀x1 , x 2 ∈ M , λ ∈  ⇒ λ x1 + (1 − λ ) x 2 ∈ M k Ta gọi một điểm x ∈  n có dạng x = ∑ λi x i với λ1 , λ2 ,..., λk ∈  và i =1 k ∑λ i =1 i = 1 là tổ hợp affine của các điểm x1 , x 2 ,..., x k ∈  n . Mệnh đề 1.1 Tập M ⊆  n , khác rỗng là tập affine nếu và chỉ nếu M= x 0 + L trong đó x 0 ∈ M , L ⊆  n là không gian con. Khi đó, L được gọi là không gian con song song với tập affine M . Số chiều của tập affine M cũng chính là số chiều của L . Bao affine của một tập E ⊆  n là giao của tất cả các tập affine chứa E . Đó là tập affine nhỏ nhất chứa E , ký hiệu là affE . Số chiều của một tập M là số chiều của bao affine của nó, ký hiệu là dim M . Cho tập M ⊆  n có dim M < n . Một điểm a ∈ M được gọi là điểm trong tương đối của M nếu tồn tại hình cầu mở B (a, ε ) sao cho ( B (a, ε ) ∩ affM ) ⊂ M . Phần trong tương đối của tập M , ký hiệu là riM là tập chứa tất cả các điểm trong tương đối của M .
5 1.1.1.2. Tập lồi và điểm cực biên Cho hai điểm x1 , x 2 thuộc  n . Tập tất cả các điểm có dạng: x= λ x1 + (1 − λ ) x 2 , 0 ≤ λ ≤ 1 được gọi là đoạn thẳng nối x1 , x 2 . Ký hiệu: [ x1 , x 2 ] . Tập M ⊆  n được gọi là tập lồi nếu nó chứa trọn đoạn thẳng nối hai điểm bất kỳ thuộc nó, tức là: ∀x1 , x 2 ∈ M ,0 ≤ λ ≤ 1 ⇒ λ x1 + (1 − λ ) x 2 ∈ M k k Ta gọi một điểm x ∈  có dạng x = ∑ λi x với λ1 ,..., λk ≥ 0 và n i ∑λ i = 1 là tổ hợp i =1 i =1 lồi của các điểm x1 , x 2 ,..., x k ∈  n . Nếu λi > 0 với mọi i = 1, 2,..., k thì ta nói x là tổ hợp lồi chặt của các điểm x1 , x 2 ,..., x k ∈  n . Mệnh đề 1.2 Một tập M ⊂  n là tập lồi khi và chỉ khi nó chứa tất cả các tổ hợp lồi của những phần tử thuộc nó. Mệnh đề 1.3 Nếu M , N là tập lồi, α ∈  thì M + N , α M cũng là tập lồi. Bao lồi của tập E ⊂  n là giao của tất cả các tập lồi chứa E và được ký hiệu là convE . Đó là tập lồi nhỏ nhất chứa E . Cho tập lồi M ⊂  n . Một điểm x ∈  n đượ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.4 Một tập lồi đóng khác rỗng M ⊂  n 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ý 1.1 (định lý Krein-Milman) Một tập lồi đóng, bị chặn trong  n là bao lồi của các điểm cực biên của nó. 1.1.1.3. Nón lồi, phương lùi xa, phương cực biên Tập M ⊂  n được gọi là nón nếu x ∈ M , λ ≥ 0 ⇒ λ x ∈ M . Nếu M vừa là tập lồi vừa là nón thì M được gọi là nón lồi.
6 Cho tập lồi khác rỗng M ⊂  n . Vectơ d ≠ 0 được 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 lùi xa của M . Hai phương d 1 , d 2 là khác biệt nếu d 1 ≠ α 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 λ1d 1 + λ2 d 2 ; λ1 , λ2 > 0 . khác biệt d 1 , d 2 của M sao cho d = 1.1.1.4. Các định lý tách tập lồi Cho hai tập C , D ⊂  n và siêu phẳng H= {x ∈  n | 〈 a, x〉= α } với a ∈  n \ {0} và α ∈  . Ta nói: + Siêu phẳng H tách hai tập C và D nếu: 〈 a, x〉 ≤ α ≤ 〈 a, y〉 ∀x ∈ C , ∀y ∈ D . + Siêu phẳng H tách hẳn (hay tách chặt) hai tập C và D nếu: 〈 a, x〉 < α < 〈 a, y〉 ∀x ∈ C , ∀y ∈ D . Định lý 1.2 (định lý tách I) Nếu hai tập lồi C , D ⊂  n không rỗng và rời nhau thì có một siêu phẳng tách chúng. Định lý 1.3 (định lý tách II) Nếu hai tập lồi đóng C , D ⊂  n 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.1.5. Tập lồi đa diện Tập lồi đa diện P ⊂  n 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
7 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.4 Cho P là tập lồi đa diện được xác định bởi: 〈 a i , x〉 ≤ bi , i =1,..., m Khi đó, tập con lồi khác rỗng F ⊂ P là một diện của P nếu và chỉ nếu: F = { x | 〈 a i , x〉 = bi , i ∈ I ; 〈 a i , x〉 ≤ bi , i ∉ I } trong đó {i | 〈 a i , x〉= bi , ∀x ∈ P}= I 0 ⊂ 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.5 (định lý biểu diễn tập lồi đa diện) Giả sử {v1 ,..., v N } là tập các đỉnh và {d 1 ,..., d M } là tập các phương cực biên của tập lồi đa diện P . Khi đó, mỗi điểm x ∈ P đều có thể biểu diễn dưới dạng: N M =x =i 1 =j 1 ∑ λi vi + ∑ µ j d j N trong đó λi = ≥ 0, i 1,..., N ; µ j ≥= ∑ λi 1 . 0, j 1,..., M ; = i =1 1.1.2. Hàm lồi 1.1.2.1. Định nghĩa Cho hàm f : X → [ −∞; +∞ ] xác định trên tập lồi X ⊂  n . Khi đó, các tập: domf= { x ∈ X | f ( x) < +∞} = epif {( x,α ) ∈ X ×  | f ( x) ≤ α } được gọi là miền hữu hiệu và trên đồ thị của hàm f . Nếu domf ≠ ∅ và f ( x) > −∞ thì hàm f gọi là chính thường. Hàm f được xác định ở trên được gọi là hàm lồi nếu epif là một tập lồi trên  n ×  .
8 Ta có nhận xét, nếu f là hàm lồi thì domf là tập lồi. Thật vậy, domf là hình chiếu trên X của epif : = domf } { x | ∃r , ( x, r ) ∈ epif } . { x | f ( x) < +∞= Do đó, domf là ảnh của tập lồi epif qua một ánh xạ tuyến tính nên domf là tập lồi. Định lý 1.6 Giả sử X ⊂  n là tập lồi và f : X → ( −∞; +∞ ] . Khi đó, f lồi trên X . Khi và chỉ khi: f (λ x1 + (1 − λ ) x 2 ) ≤ λ f ( x1 ) + (1 − λ ) f ( x 2 ) ∀x1 , x 2 ∈ X , ∀λ ∈ [ 0,1] . Ta gọi f là hàm lồi chặt trên tập lồi X nếu: f (λ x1 + (1 − λ ) x 2 ) < λ f ( x1 ) + (1 − λ ) f ( x 2 ) ∀x1 , x 2 ∈ X , x1 ≠ x 2 ,0 < λ < 1 . Hàm f được gọi là hàm lõm nếu − f là hàm lồi, tương tự f được gọi là hàm lõm chặt nếu − f là hàm lồi chặt. 1.1.2.2. Tính chất của hàm lồi Mệnh đề 1.5 Nếu f xác định trên tập lồi X ⊂  n là hàm lồi thì tập { x ∈ X | f ( x) ≤ α } là tập lồi với mọi α ∈  . Cho hàm lồi f1 xác định trên tập lồi X 1 ⊂  n , hàm lồi f 2 xác định trên tập lồi X 2 ⊂  n và số thực λ > 0 . Ta định nghĩa các phép toán sau: (= λ f1 ( x) ) : λ f1 ( x) x ∈ X 1 ( f1 + f 2 ) ( x)=: f1 ( x) + f 2 ( x) x ∈ X 1 ∩ X 2 max { f1 , f 2 } ( x) : max { f1 ( x), f 2 ( x)} x ∈ X 1 ∩ X 2 = Khi đó, ta có các kết quả sau: Mệnh đề 1.6 Cho f1 là hàm lồi trên tập X 1 , f 2 là hàm lồi trên tập X 2 và các số thực α , β > 0 . Khi đó, các hàm α f1 + β f 2 và max { f1 , f 2 } là hàm lồi trên X1 ∩ X 2 . Mệnh đề 1.7 Nếu f là hàm lồi xác định trên tập lồi mở X ⊂  n thì f là hàm liên tục trên X .
9 Định lý 1.7 Cho hàm f khả vi trên tập lồi mở X ⊂  n . Khi đó, f là hàm lồi khi và chỉ khi: f ( y ) − f ( x) ≥ 〈∇f ( x), y − x〉 ∀x, y ∈ X Định lý 1.8 Cho f là hàm khả vi hai lần trên tập lồi mở X ⊂  n . Khi đó, f là hàm lồi khi và chỉ khi ma trận Hesse ∇ 2 f ( x) là nửa xác định dương trên X . Hàm f là hàm lồi chặt trên X nếu ∇ 2 f ( x) xác định dương trên X . 1 Áp dụng định lý trên cho hàm f ( x)= 〈 x, Qx〉 + 〈 x, c〉 + α trong đó Q là ma 2 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 nếu Q là ma trận nửa xác định dương (tương ứng, xác định dương). 1.1.3. Ma trận nửa xác định dương, nửa xác định âm Định nghĩa: Ma trận D ∈  n×n được gọi là xác đinh dương nếu xT Dx > 0 ∀x ∈  n \ {0} . Nếu xT Dx ≥ 0, ∀x ∈  n thì D được gọi là ma trận nửa xác định dương. Định nghĩa: Ma trận D ∈  n×n được gọi là xác đinh âm nếu xT Dx < 0 ∀x ∈  n \ {0} . Nếu xT Dx ≤ 0, ∀x ∈  n thì D được gọi là ma trận nửa xác định âm. 1.2. Một số kết quả cơ bản trong lý thuyết tối ưu 1.2.1. Định nghĩa Bài toán tối ưu tổng quát được phát biểu như sau: min f ( x) x ∈ D ( P1 ) hoặc max f ( x) x ∈ D ( P2 ) trong đó D ⊂  n được gọi là tập nghiệm chấp nhận được hay tập ràng buộc và hàm f : D →  là hàm mục tiêu. Mỗi điểm x ∈ D được gọi là một nghiệm chấp nhận được hay một phương án chấp nhận được.
10 Điểm x∗ ∈ D mà f ( x* ) ≤ f ( x), ∀x ∈ D được gọi là nghiệm tối ưu, hoặc nghiệm toàn cục tối ưu, hoặc nghiệm cực tiểu toàn cục, hoặc đơn giản là nghiệm của bài toán ( P1 ) . Người ta còn gọi một nghiệm tối ưu là một phương án tối ưu. Điểm x∗ ∈ D được gọi là nghiệm cực tiểu toàn cục chặt của bài toán ( P1 ) nếu: f ( x* ) < f ( x), ∀x ∈ D, x ≠ x* . Điểm x∗ ∈ D được gọi là nghiệm tối ưu địa phương hoặc nghiệm cực tiểu địa phương của bài toán ( P1 ) nếu tồn tại một ε − lân cận B ( x* , ε ) của điểm x∗ ∈ D sao cho f ( x* ) ≤ f ( x), ∀x ∈ B ( x* , ε ) ∩ D . Điểm x∗ ∈ D được gọi là nghiệm tối ưu địa phương chặt hoặc nghiệm cực tiểu địa phương chặt của bài toán ( P1 ) nếu: f ( x* ) < f ( x), ∀x ∈ B ( x* , ε ) ∩ D, x ≠ x* . Các khái niệm tương tự cũng được định nghĩa cho bài toán ( P2 ) . 1.2.2. Tính chất Định lý 1.9 Cho hàm lồi f :  n →  và tập lồi khác rỗng D ⊂  n . Xét bài toán min { f ( x) | x ∈ D} . Khi đó: i) Nếu x* là một nghiệm tối ưu địa phương của bài toán này thì x* cũng là nghiệm tối ưu toàn cục. ii) Nếu x* là một nghiệm tối ưu địa phương chặt hoặc f là hàm lồi chặt thì x* là nghiệm tối ưu toàn cục chặt duy nhất của bài toán. Định lý 1.10 Điều kiện cần và đủ để bài toán ( P1 ) có nghiệm tối ưu là tập {t ∈  | t ≥ f ( x), x ∈ D} đóng và có một cận dưới hữu hạn. f ( D)+ = Định lý 1.11 Nếu tập D là tập compact và hàm f là hàm liên tục trên D thì cả hai bài toán ( P1 ) và ( P2 ) đều có nghiệm tối ưu.
11 1.3. Định nghĩa bài toán quy hoạch toàn phương 1.3.1. Định nghĩa hàm toàn phương Hàm f :  n →  được gọi là hàm toàn phương nếu tồn tại ma trận D ∈  n×n và tồn tại vectơ c ∈  n và số thực α sao cho: 1 T 1 f ( x )= x Dx + cT x + α = 〈 x, Dx〉 + 〈 c, x〉 + α ∀x ∈  n . (1.1) 2 2 x ( D + DT ) x, ∀x ∈  n . Nên ta có thể giả sử ma trận D trong công 1 T Ta có x= T Dx 2 thức (1.1) là ma trận đối xứng. Thật vậy, ta chỉ cần thay ma trận D trong công thức (1.1) bởi ma trận đối xứng 1 2 ( D + DT ) . Ví dụ: xét hàm toàn phương f ( x) =+ ( x1 , x2 ) ∈  2 . Ta có: x12 x22 , xT = 1  2 0   x1  f ( x) = ( x1 , x2 ) .  .  2  0 2   x2  1.3.2. Định nghĩa bài toán quy hoạch toàn phương Định nghĩa: 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 ∆ ⊂  n 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). Nếu D là ma trận không, α = 0 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 hàm 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  1 T  xét bài toán min =f ( x) x Dx + cT x | x ∈ ∆  .  2 
12 1  1 T  Nếu ta thay ma trận Q = D thì bài toán min =f ( x) x Dx + cT x | x ∈ ∆  2  2  trở thành min { f= ( x) xT Qx + cT x | x ∈ ∆} . Ví dụ: Cho bài toán quy hoạch toàn phương min { x12 − x22 | ( x1 , x2 ) ∈  2 ;1 ≤ x1 , x2 ≤ 3} Ta có: 1  2 0   x1  f ( x) = ( x1 , x2 ) .  .  2  0 −2   x2  =∆ { x= |x ( x , x ) ∈  ;1 ≤ x , x T 1 2 2 1 2 ≤ 3} 1 T Định lý 1.12. Cho hàm f ( x= ) x Dx + cT x + α trong đó D ∈  nS×n , c ∈  n , 2 α ∈  . Khi đó, nếu D là ma trận nử 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 Dx 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 ∈  n , v ∈  n . Ta có: 0 ≤ (u − v)T D(u − v= ) u T Du − 2vT Du + vT Dv. Suy ra: vT Dv ≤ u T Du − 2vT D(u − v). Lấy x ∈  n , y ∈  n bất kỳ, t ∈ (0;1) . Ta đặt: z := tx + (1 − t ) y . Thế vào biểu thức trên ta được: z T Dz ≤ yT Dy − 2 z T D( y − z ) z T Dz ≤ xT Dx − 2 z T D( x − z ) Vì y − z = t ( y − x) và x − z = (1 − t )( x − y ) nên: (1 − t ) z T Dz + tz T Dz ≤ (1 − t ) yT Dy + txT Dx. Suy ra: f1 (tx + (1 − t ) y= ) f1 ( z ) ≤ tf1 ( x) + (1 − t ) f1 ( y ). Vậy, f1 là hàm lồi. 
13 Từ định lý trên ta có nhận xét, 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 xác định dương thì bài toán được gọi là quy hoạch toàn phương lồi. 1.3.3. Các dạng quy hoạch toàn phương Tập ràng buộc ∆ của bài toán quy hoạch toàn phương là tập lồi đa diện. Nên ∆ có thể được biểu diễn qua các hệ phương trình, hệ bất phương trình. Do đó, bài toán quy hoạch toàn phương có thể được phát biểu dưới các dạng sau: 1  min  xT Dx + cT x : x ∈  n , Ax ≥ b  2  1  min  xT Dx + cT x : x ∈  n , Ax ≥ b, x ≥ 0  2  1  min  xT Dx + cT x : x ∈  n , Ax ≥ b, Cx = d 2  1  min  xT Dx + cT x : x ∈  n , Ax ≤ b, x ≥ 0  2  min { xT Qx + cT x : x ∈  n , Ax ≤ b, x ≥ 0} .
14 Chương 2: TÍNH CHẤT CỦA BÀI TOÁN QUY HOẠCH TOÀN PHƯƠNG 2.1. Điều kiện tồn tại nghiệm Xét bài toán quy hoạch toàn phương:  1 T  min = f ( x) : x Dx + cT x  2 (2.1) v.d .k x ∈  n , Ax ≥ b trong đó D ∈  m×n , c ∈  n , b ∈  m . Tập ràng buộc và giá trị tối ưu của bài toán được viết dưới dạng: { x  n : Ax ≥ b} ∆( A, b) :=∈ =θ : inf { f ( x) : x ∈ ∆( A, b)}. ∅ thì θ = +∞ (quy ước). Nếu ∆( A, b) ≠ ∅ thì có hai trường Nếu ∆ ( A, b) = hợp xảy ra: hoặc là θ ∈  hoặc là θ = −∞ (khi đó, bài toán không có nghiệm). Một vấn đề được đặt ra là khi trường hợp θ ∈  xảy ra thì bài toán có nghiệm tối ưu hay không? Ta có nhận xét, bài toán tối ưu với hàm mục tiêu không phải là hàm toàn phương có thể không có nghiệm ngay cả khi giá trị tối ưu của nó là hữu hạn. Chẳng 1  hạn, xét ví dụ: cho bài toán min  : x ∈ , x ≥ 1 . Khi đó, bài toán không có x  1  nghiệm, trong khi giá trị tối ưu của nó = θ inf  : x ∈ , x= ≥ 1 0 là hữu hạn. x  Định lý Frank-Wolfe được phát biểu sau đây sẽ cho ta biết điều kiện tồn tại nghiệm của bài toán (2.1). 2.1.1. Định lý Frank-Wolfe Định lý 2.1 (định lý Frank-Wolfe) = Nếu θ inf { f ( x) : x ∈ ∆( A, b)} là một số thực hữu hạn thì bài toán (2.1) có nghiệm. Chứng minh
15 Giả sử θ ∈  . Ta cần chứng minh bài toán (2.1) có nghiệm. Do θ ∈  nên ∆( A, b) ≠ ∅ . Lấy x 0 ∈ ∆( A, b) , với ρ > 0 tùy ý. Đặt ∆ ρ =∆( A, b) ∩ B ( x 0 , ρ ) . Suy ra, ∆ ρ là tập lồi, khác rỗng và compact. Xét bài toán: min { f ( x) : x ∈ ∆ ρ } . (2.1’) Theo định lý Weierstrass tồn tại y ∈ ∆ ρ sao cho: f ( y= ρ : min { f ( x ) : x ∈ ∆ ρ } ) q= Vì tập nghiệm của bài toán (2.1’) là khác rỗng và compact nên tồn tại yρ ∈ ∆ ρ sao cho: yρ= { − x 0 min y − x 0 : y ∈ ∆ ρ= , f ( y ) qρ . } Khi đó, luôn tồn tại ρˆ > 0 sao cho yρ − x 0 < ρ , ∀ρ ≥ ρˆ . (2.2) Thật vậy, giải sử trái lại chúng ta tìm được dãy tăng {ρ k } : ρ k → +∞ sao cho với mỗi k tồn tại yρk ∈ ∆ ρk sao cho f ( y= ρk ) x 0 ρ k . Để đơn giản cho qρ k , y ρ k − = ký hiệu ta viết y k thay cho yρk . Vì y k ∈ ∆( A, b) nên Ai y k ≥ bi , ∀i =1,..., m. Với i = 1 ta có dãy { A1 y k } bị chặn dưới nên tồn tại dãy {k '} ⊂ {k} sao cho lim A1 y k ' tồn tại (có thể xảy ra trường hợp lim A1 y k ' = +∞ ). Không mất tính tổng k '→∞ k '→∞ quát ta giả sử {k '} ≡ {k} , khi đó lim A1 y k tồn tại. Tương tự, với i = 2 ta cũng có k →∞ lim A2 y k tồn tại. Tiếp tục quá trình trên với i = m ta có lim Am y k tồn tại. Khi đó, k →∞ k →∞ với mỗi i ∈ {1,..., m} ta có lim Ai y k tồn tại. k →∞ Đặt I = {1,...,m} , I 0 ={ i ∈ I 0 : lim Ai y k = k →∞ } bi , I1 = I \ Io = { i ∈ I : lim Ai y k > bi . k →∞ } Khi đó, tồn tại ε > 0 sao cho lim Ai y k ≥ bi + ε , ∀i ∈ I1 . k →∞