Tài liệu (Luận văn thạc sĩ) Bài toán bù tuyến tính và ứng dụng

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC VƯƠNG THỊ HUỆ CHI BÀI TOÁN BÙ TUYẾN TÍNH VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2014 1 Mục lục Lời nói đầu 2 Chương 1. Bài toán bù tuyến tính 1.1. Bài toán bù tuyến tính (LCP) . . . . . . . . . . . . . . . 1.1.1. Mô tả bài toán . . . . . . . . . . . . . . . . . . . 1.1.2. Nguồn gốc bài toán bù tuyến tính . . . . . . . . 1.2. Quan hệ với các bài toán VI và MPEC . . . . . . . . . . 1.2.1. Bài toán bất đẳng thức biến phân . . . . . . . . 1.2.2. Bài toán qui hoạch toán học với ràng buộc cân bằng 1.3. Sự tồn tại và duy nhất nghiệm của bài toán LCP . . . . 4 4 4 7 12 12 15 18 Chương 2. Phương pháp giải bài toán 2.1. Phương pháp Lemke . . . . . . . . 2.1.1. Phương pháp Lemke . . . . 2.1.2. Ví dụ minh họa . . . . . . . 2.1.3. Sự hội tụ hữu hạn . . . . . 2.2. Phương pháp điểm trong . . . . . . . . . . . 21 21 21 24 27 31 Chương 3. Một số ứng dụng của bài toán bù tuyến tính 3.1. Trò chơi Steckelberg . . . . . . . . . . . . . . . . . . . . 3.2. Trò chơi song ma trận . . . . . . . . . . . . . . . . . . . 3.2.1. Trò chơi song ma trận . . . . . . . . . . . . . . . 3.2.2. Nghiệm trò chơi song ma trận . . . . . . . . . . . 35 35 36 36 39 Kết luận 40 Tài liệu tham khảo 41 bù . . . . . . . . . . tuyến . . . . . . . . . . . . . . . . . . . . tính . . . . . . . . . . . . . . . . . . . . . . . . . 2 Lời nói đầu 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 đề 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 ra ngoài khuôn khổ bài toán bù. Chẳng hạn, thuật toán xoay bù (comple-mentarity 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 các bài toán qui hoạch phi tuyến. Bài toán bù tuyến tính là bài toán tìm véctơ z ∈ Rn nghiệm đúng hệ z ≥ 0, q + M z ≥ 0, z T (q + M z) = 0 hoặc chỉ rõ hệ trên vô nghiệm, với véctơ q ∈ Rn và ma trận M ∈ Rn×n cho trước. Ký hiệu bài toán này là LCP (q, M) hay đơn giản là LCP nếu không cần chỉ rõ q và M (T là ký hiệu chuyển vị vectơ hay ma trận). Bài toán bù tuyến tính LCP (q, M) có nhiều ứng dụng trong lý thuyết và thực tiễn, như trong qui hoạch toàn phương, trò chơi song ma trận, cân bằng thị trường và trong nhiều bài toán kinh tế, công nghiệp và vật lý khác. Mục tiêu của luận văn này là tìm hiểu và trình bày khái quát về bài toán bù tuyến tính, mối quan hệ giữa bài toán bù tuyến tính với bài toán bất đẳng thức biến phân và bài toán qui hoạch toán học với ràng buộc cân bằng. Tìm hiểu các phương pháp giải chính và một số ứng dụng của bài toán bù tuyến tính vào mô hình trò chơi. Luận văn được viết thành ba chương. Chương 1 “Bài toán bù tuyến tính" trình bày các khái niệm cơ bản về bài toán bù tuyến tính, nguồn gốc bài toán và sự tồn tại duy nhất nghiệm của bài toán. Bài toán bù có nhiều ứng dụng và liên quan chặt chẽ với một số bài toán dạng tổng quát hơn, hiện đang rất được quan tâm nghiên cứu, đó là bài toán bất đẳng thức biến phân và bài toán qui 3 hoạch toán học với ràng buộc cân bằng. Vì thế trong chương cũng sẽ đề cập tới hai bài toán này. Chương 2 “Phương pháp giải bài toán bù tuyến tính” giới thiệu hai phương pháp tiêu biểu giải bài toán bù tuyến tính: phương pháp Lemke (1968) và phương pháp điểm trong (Kojima, 1988). Phương pháp Lemke có nhiều điểm giống với phương pháp đơn hình trong qui hoạch tuyến tính, nhưng khác ở cách chọn biến để đưa vào cơ sở, phương pháp này cho phép giải bài toán bù tuyến tính không suy biến sau một số hữu hạn bước. Tuy vậy, trong trường hợp xấu nhất thời gian chạy của nó là một hàm mũ. Phương pháp điểm trong dựa trên ý tưởng các thuật toán điểm trong giải qui hoạch tuyến tính, cho phép giải bài toán bù tuyến tính với ma trận M nửa xác định dương trong thời gian đa thức. Chương 3 "Một số ứng dụng của bài toán bù tuyến tính" trình bày hai mô hình trò chơi thường gặp trong các ứng dụng của bài toán bù tuyến tính: trò chơi Stackelberg và trò chơi song ma trận. Trò chơi Stackelberg liên quan chặt chẽ với bài toán qui hoạch toán học với ràng buộc cân bằng (MPEC) và là sự mở rộng ý tưởng của trò chơi Nash. Có thể tìm nghiệm cân bằng Nash của trò chơi song ma trận nhờ lập và giải một bài toán bù tuyến tính thích hợp. 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 sau này. Nhân dịp này tác giả luận văn xin bày tỏ lòng biết ơn sâu sắc tới 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ả trân trọng cảm ơn các giảng viên Trường Đại học Khoa học – Đại học Thái Nguyên, Viện Toán học – Viện Hàn lâm Khoa học và Công nghệ Việt Nam 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. Thái Nguyên, tháng 3 năm 2014 Tác giả Vương Thị Huệ Chi 4 Chương 1 Bài toán bù tuyến tính Chương này trình bày các khái niệm cơ bản về bài toán bù tuyến tính, nguồn gốc bài toán và sự tồn tại duy nhất nghiệm của bài toán. Bài toán bù có nhiều ứng dụng và liên quan chặt chẽ với một số bài toán dạng tổng quát hơn, hiện đang rất được quan tâm nghiên cứu, đó là bài toán bất đẳng thức biến phân và bài toán qui hoạch toán học với ràng buộc cân bằng, vì thế trong chương sẽ giới thiệu về hai bài toán này. Nội dung của chương được tham khảo từ các tài liệu [3], [4], [6] và [7]. 1.1. 1.1.1. Bài toán bù tuyến tính (LCP) Mô tả bài toán Bài toán bù tuyến tính (Linear Complementarity Problem, viết tắt LCP) là bài toán tìm một véctơ trong không gian véctơ thực hữu hạn chiều thỏa mãn một hệ bất đẳng thức nào đó. Cụ thể, bài toán bù tuyến tính được phát biểu như sau. Định nghĩa 1.1.([3], tr.1) Cho véctơ q ∈ Rn và ma trận M ∈ Rn×n , hãy tìm véctơ z ∈ Rn sao cho: z≥0 (1.1) q + Mz ≥ 0 (1.2) z T (q + M z) = 0 (1.3) hoặc chỉ ra véctơ z như thế không tồn tại. Ta ký hiệu bài toán này là LCP (q, M ). Trong các tài liệu về toán, có thể tìm thấy các trường hợp riêng của bài toán bù tuyến tính rất sớm từ những năm 1940, tuy nhiên bài toán bù bắt đầu thu hút sự chú ý chỉ từ giữa những năm 1960, khi bài toán trở thành một chủ đề nghiên cứu riêng. Sau đây là một số thuật ngữ chính thường dùng trong bài toán bù tuyến tính: Véctơ z thỏa mãn các bất đẳng thức trong (1.1) và (1.2) được gọi là chấp nhận được. Nếu véctơ chấp nhận được z thỏa mãn chặt (như bất đẳng thức) các bất đẳng thức trong (1.1 ) - (1.2) thì nó được 5 gọi là chấp nhận được chặt. Bài toán LCP (q, M ) gọi là chấp nhận được (hay chấp nhận được chặt) nếu có tồn tại véctơ chấp nhận được (hay chấp nhận được chặt). Tập tất cả các véctơ chấp nhận được của bài toán LCP (q, M ) gọi là miền chấp nhận được và ký hiệu là FEA (q, M ). Đặt w = q + Mz (1.4) Véctơ chấp nhận được z của LCP (q, M ) thỏa mãn (1.3) khi và chỉ khi zi wi = 0 với mọi i = 1, 2, ..., n. (1.5) Điều kiện (1.5) thường được dùng thay cho điều kiện (1.3). zi và wi gọi là một cặp bù và chúng được gọi là bù nhau. Véctơ z thỏa mãn (1.5) được gọi là các véctơ bù. Vì thế, LCP là bài toán tìm véctơ chấp nhận được và bù. Một véctơ như thế gọi là một nghiệm (solution) của LCP. Bài toán LCP (q, M ) gọi là giải được (solvable) nếu nó có nghiệm. Ký hiệu tập nghiệm của LCP (q, M ) là SOL (q, M ). Chú ý là nếu q ≥ 0 thì LCP (q, M ) luôn giải được với véctơ 0 là nghiệm tầm thường. Cách xác định w như trên thường được dùng để diễn đạt theo cách khác của bài toán LCP (q, M ), thuận tiện hơn cho xây dựng các thuật toán giải. Cụ thể là bài toán tìm các véctơ không âm w và z trong Rn thỏa mãn (1.4) và (1.5). Để tiện cho trích dẫn về sau, ta viết lại các điều kiện (1.1) - (1.4) của bài toán LCP dưới dạng w ≥ 0, z ≥ 0, w = q + M z, z T w = 0. Ràng buộc z T w = 0 được gọi là ràng buộc bù (Complementarity Constraint) và có thể viết dưới dạng z⊥w, trong đó ⊥ là ký hiệu "vuông góc". Trường hợp riêng của bài toán LCP (q, M ) khi q = 0 rất đáng được chú ý. Bài toán này được gọi là bài toán bù tuyến tính thuần nhất tương ứng với ma trận M. Một tính chất đặc thù của bài toán LCP (0, M ) là nếu z ∈ SOL(0, M ) thì λz ∈ SOL(0, M ) với mọi số thực λ ≥ 0. Bài toán bù tuyến tính thuần nhất có véctơ 0 là nghiệm tầm thường. Câu 6 hỏi "liệu bài toán đặc biệt này có nghiệm khác thường hay không" có ý nghĩa rất quan trọng về lý thuyết và thuật toán. Ví dụ 1.1(Bài toán một chiều). Cho trước hai số thực q, m ∈ R, tìm hai biến số z, w ∈ R sao cho z ≥ 0, w ≥ 0, w = q + mz và z(q + mz) = 0. Đó là bài toán bù tuyến tính trong R. Hình 1.1 minh họa hình ảnh hình học của bài toán này trong trường hợp q > 0, m < 0. Bài toán ở Hình 1.1 có 2 nghiệm: q (z = 0, w = q) và (z = − , w = 0). m Nói chung, bài toán này có mấy nghiệm? Câu trả lời cho trong bảng sau (tùy thuộc giá trị của q và m). Có thể phát biểu bài toán bù (Complementarity Problem, viết tắt là CP) ở dạng tổng quát hơn như sau. Định nghĩa 1.2. (xem [4], tr. 4-5). Cho nón K ⊆ Rn (tức là x ∈ K ⇒ λx ∈ K với mọi số λ ≥ 0) và hàm F : K → Rn . Bài toán bù, ký hiệu là CP (K, F ), là bài toán tìm một véctơ z ∈ Rn thỏa mãn các điều kiện: K 3 z⊥F (z) ∈ K ∗ 7 trong đó ⊥ là ký hiệu "vuông góc" và K ∗ là nón đối ngẫu (dual cone) của K được xác định bởi  K ∗ = d ∈ Rn : z T d ≥ 0 với mọi z ∈ K , tức là K ∗ gồm tất cả các véctơ không tạo thành góc tù với bất kỳ véctơ nào trong K. Thay cho ký hiệu ⊥ , ta có thể viết bài toán bù CP (K, F ) dưới dạng z ∈ K, F (z) ∈ K ∗ và z T F (z) = 0. Bài toán bù tuyến tính LCP là trường hợp riêng của bài toán bù CP khi K = Rn+ (do đó K ∗ = Rn+ ) và F (z) = q + M z với q ∈ Rn và M ∈ Rn×n . Luận văn này chủ yếu tập trung xét bài toán bù tuyến tính LCP. 1.1.2. Nguồn gốc bài toán bù tuyến tính Về lịch sử, bài toán LCP được xem như sự diễn đạt thống nhất của các bài toán qui hoạch tuyến tính, qui hoạch toàn phương và bài toán trò chơi song ma trận. Thực ra, bài toán qui hoạch toàn phương luôn đã và sẽ tiếp tục là nguồn ứng dụng cực kỳ quan trọng của bài toán LCP. Một số thuật toán có hiệu quả cao để giải qui hoạch toàn phương là dựa trên cách diễn đạt của bài toán LCP. Còn về bài toán trò chơi song ma trận, bài toán LCP đã là phương tiện để khám phá ra một công cụ hiệu quả, có tính chất kiến thiết, để tính toán nghiệm cân bằng. Bài toán bù tuyến tính có nhiều ứng dụng phong phú và đa dạng. Trong mục này ta sẽ mô tả một số ứng dụng cổ điển này và trong mỗi ứng dụng sẽ chỉ ra một số tính chất đặc biệt của ma trận M trong bài toán LCP tương ứng. 8 • Qui hoạch toàn phương Xét bài toán qui hoạch toàn phương (Quadratic Program, viết tắt là QP) 1 f (x) = cT x + xT Qx → min 2 với các điều kiện Ax ≥ b, x ≥ 0, trong đó Q ∈ Rn×n đối xứng, c ∈ Rn , A ∈ Rm×n và b ∈ Rm . Trường hợp Q = 0 ta nhận được bài toán qui hoạch tuyến tính (Linear Program, viết tắt là LP). Nếu x là một nghiệm tối ưu địa phương của bài toán QP thì tồn tại véctơ y ∈ Rm sao cho cặp (x, y) thỏa mãn điều kiện Karush-Kuhn-Tucker, gọi tắt là điều kiện KKT : u = c + Qx − AT y ≥ 0, x ≥ 0, xT u = 0, (1.6) v = −b + Ax ≥ 0, y ≥ 0, y T v = 0. (1.7) Thêm vào đó, nếu Q là ma trận nửa xác định dương, nghĩa là hàm mục tiêu f (x) là lồi thì (1.6) - (1.7) là điều kiện đủ để cho véctơ x là một nghiệm tối ưu toàn cục của bài toán qui hoạch toàn phương lồi. Các điều kiện (1.6) - (1.7) xác định bài toán bù tuyến tính LCP (q, M ) với     c Q −AT q= và M = −b A 0 Để ý là ma trận M không đối xứng (trừ khi A không có hoặc bằng 0) mặc dù Q đối xứng. Tuy thế, M có tính chất gọi là song đối xứng (bisymmetry). Theo định nghĩa, một ma trận vuông N là song đối xứng nếu sau khi hoán vị một tập như nhau các hàng và cột, có thể đưa ma trận về dạng   G −AT N= A H với G và H đối xứng. Nếu Q nửa xác định dương như trong qui hoạch toàn phương lồi thì M là một ma trận song đối xứng. (Nhớ rằng ma trận vuông Q là nửa xác định dương nếu z T Qz ≥ 0 với mọi véctơ z). Một trường hợp riêng quan trọng của bài toán 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 x. Khi đó, bài toán 9 QP có dạng đơn giản f (x) = cT x + xT Qx → min 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 LCP (c, Q). 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 mà ta vừa chỉ ra là tương đương với bài toán bù tuyến tính LCP (c, Q). 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. LCP có vai trò quan trọng trong việc giải số các bài toán ứng dụng này. • Trò chơi song ma trận Trò chơi song ma trận (Bimatrix Game), ký hiệu G(A, B), gồm hai người chơi, gọi là người chơi I và người chơi II. Mỗi người chơi (Player) có một số hữu hạn hành động (actions), gọi là các chiến lược đơn (pure strategies), được quyền lựa chọn. Trong loại trò chơi này không nhất thiết một người thắng, một người thua. Vì thế, thuật ngữ trò chơi song ma trận thường có nghĩa là một trò chơi hữu hạn (finite), hai người (two-person), tổng khác không (nonzero-sum). Trò chơi đối kháng hai người với tổng bằng không thường được xét trong qui hoạch tuyến tính. Ta hình dung người chơi I có m chiến lược đơn, người chơi II có n chiến lược đơn. Các chữ cái A và B trong ký hiệu trò chơi G(A, B) là các ma trận cấp m × n với các phần tử biểu thị chi phí hai người chơi phải trả. Như vậy, khi người chơi I chọn chiến lược đơn i (i = 1, ..., m) và người chơi II chọn chiến lược đơn j (j = 1, ..., n) thì mỗi người chơi phải trả một chi phí tương ứng là aij và bij . Do không đòi hỏi tổng hai chi phí này bằng 0 nên có thể có aij + bij 6= 0. Chiến thuật hỗn hợp (mixed strategy) hay chiến thuật ngẫu nhiên (randomized strategy) của người chơi I là véctơ x ∈ Rm với thành phần P xi biểu thị xác suất chọn chiến lược đơn i, tức là x ≥ 0 và m i=1 xi = 1. Chiến lược hỗn hợp của người chơi II được định nghĩa tương tự. Do đó, nếu x và y là cặp chiến lược hỗn hợp tương ứng của người chơi I và II 10 thì chi phí kỳ vọng (trung bình) của họ lần lượt được tính bởi xT Ay và xT By. Cặp chiến lược (x∗ , y ∗ ) với x∗ ∈ Rm , y ∗ ∈ Rn được gọi là một nghiệm cân bằng Nash (Nash equilibrium) nếu ∗ T ∗ ∗ T (x ) Ay ≤ x Ay với mọi x ≥ 0 và m X xi = 1, i=1 ∗ T ∗ ∗ T (x ) By ≤ (x ) By với mọi y ≥ 0 và n X yj = 1. j=1 Nói cách khác, cặp chiến lược (x∗ , y ∗ ) là nghiệm cân bằng Nash nếu không người chơi nào được lợi hơn (theo nghĩa chi phí trung bình thấp hơn) khi đơn phương thay đổi chiến lược của mình. Kết quả cơ bản trong lý thuyết trò chơi khẳng định rằng một nghiệm cân bằng Nash như thế luôn tồn tại. Để đưa mô hình trò chơi G(A, B) về bài toán bù tuyến tính ta giả thiết A và B là hai ma trận dương (theo mọi phần tử). Giả thiết này hoàn toàn hợp lý, bởi vì bằng cách thêm vào mỗi phần tử aij và bij cùng một số dương đủ lớn sẽ làm chúng trở thành số dương và biến đổi này không hề ảnh hưởng gì đến nghiệm cân bằng. Sau đó, ta xét bài toán bù LCP u = −em + Ay ≥ 0, x ≥ 0, xT u = 0, (1.8) v = −en + B T x ≥ 0, y ≥ 0, y T v = 0, (1.9) trong đó em ∈ Rm và en ∈ Rn là các véctơ có mọi thành phần bằng 1. Có thể thấy rằng nếu (x∗ , y ∗ ) là một nghiệm cân bằng Nash thì (x0 , y 0 ) là một nghiệm của (1.8) - (1.9) với x∗ 0 x = (x∗ )T By ∗ 0 và y = y∗ (x∗ )T Ay ∗ (1.10) Ngược lại, rõ ràng là nếu (x0 , y 0 ) là một nghiệm của (1.8) - (1.9) thì x0 và y 0 phải khác không. Vậy (x∗ , y ∗ ) là một nghiệm cân bằng Nash với x0 y0 ∗ x = T 0 và y = T 0 . em x en y ∗ Giả thiết A và B là các ma trận dương đảm bảo cho các véctơ x0 và y 0 xác định theo (1.10) là không âm. Giả thiết này cũng rất cần thiết cho 11 quá trình giải bài toán LCP với các điều kiện (1.8) - (1.9). Véctơ q và ma trận M xác định bài toán LCP với các điều kiện (1.8) - (1.9) được cho bởi     −em 0 A q= và M = −en BT 0 Trong bài toán LCP (q, M ) này ma trận M không âm, có cấu trúc và véctơ q khá đặc biệt. • Cân bằng thị trường Cân bằng thị trường (Market Equilibrium) là trạng thái của nền kinh tế trong đó nhu cầu của người tiêu dùng và khả năng cung cấp của người sản xuất cân bằng nhau theo mức giá hiện hành. Ta hãy xét một bài toán cân bằng thị trường cụ thể mà ở đó véctơ cung được mô tả bởi một mô hình qui hoạch tuyến tính để thu hút các đặc điểm kỹ thuật hay công nghệ trong hoạt động sản xuất. Hàm nhu cầu thị trường được sinh ra bởi mô hình kinh tế lượng với giá cả hàng hóa xem như các biến độc lập chính. Về mặt toán học, mô hình cân bằng thị trường là tìm véctơ giá p∗ và véctơ nhu cầu tiêu dùng r∗ sao cho các điều kiện nêu sau đây được thỏa mãn: (i) về phía cung: cT x → min với các điều kiện Ax ≥ b, (1.11) Bx ≥ r∗ , (1.12) x ≥ 0, trong đó c là véctơ chi phí cho hoạt động cung cấp, x là véctơ mức hoạt động sản xuất, điều kiện (1.11) biểu thị các ràng buộc về công nghệ sản xuất và (1.12) là các ràng buộc đòi hỏi về nhu cầu tiêu dùng. (ii) về phía cầu: r∗ = Q(p∗ ) = Dp∗ + d, (1.13) trong đó Q(•) là hàm nhu cầu thị trường với p∗ và r∗ lần lượt là véctơ giá và véctơ cầu. Giả thiết Q(•) là hàm afin. (iii) điều kiện cân bằng: p∗ = π ∗ , (1.14) 12 với π ∗ là véctơ đối ngẫu (hay véctơ giá bóng - shadow prices, tức là giá cung trên thị trường) tương ứng với ràng buộc (1.12). Để đưa mô hình trên về bài toán bù tuyến tính, ta chú ý rằng véctơ x∗ là một nghiệm tối ưu của bài toán qui hoạch tuyến tính về cung khi và chỉ khi tồn tại véctơ v ∗ sao cho y ∗ = c − AT v ∗ − B T π ∗ ≥ 0, x∗ ≥ 0, (y ∗ )T x∗ = 0, u∗ = −b + Ax∗ ≥ 0, v ∗ ≥ 0, (u∗ )T v ∗ = 0, δ ∗ = −r∗ + Bx∗ ≥ 0, π ∗ ≥ 0, (δ ∗ )T π ∗ = 0, (1.15) Thay thế hàm nhu cầu (1.13) của r∗ và dùng điều kiện cân bằng (1.14), ta kết luận rằng các điều kiện (1.15) tạo nên bài toán bù tuyến tính LCP (q, M ) với     c 0 −AT −B T q =  −b  và M =  A (1.16) 0 0  −d B 0 −D Nhận xét là ma trận M trong (1.16) là song đối xứng nếu ma trận D là đối xứng. Trong trường hợp này, bài toán LCP trên đây trở thành điều kiện Karush-Kuhn-Tucker cho bài toán toàn phương 1 dT p + pT Dp + bT v → max 2 với các điều kiện AT v + B T p ≤ c, (1.17) p ≥ 0, v ≥ 0. Mặt khác, nếu D là á đối xứng thì M không là song đối xứng và không tồn tại mối liên hệ giữa mô hình cân bằng thị trường và bài toán toàn phương (1.17). Câu hỏi liệu D có đối xứng hay không có liên quan đến tính khả tích của hàm nhu cầu Q(•). Bất kể D có đối xứng hay không, ma trận M là nửa xác định dương nếu −D cũng là nửa xác định dương. 1.2. 1.2.1. Quan hệ với các bài toán VI và MPEC Bài toán bất đẳng thức biến phân Bất đẳng thức biến phân (Variational Inequality, viết tắt là VI) bao gồm lớp bài toán rộng hơn bài toán bù tuyến tính LCP. Cách phát biểu 13 toán học của bài toán bất đẳng thức biến phân như sau. Định nghĩa 1.3 ([4], tr. 2). Tìm véctơ z ∈ K ⊂ Rn sao cho (y − z)T F (z) ≥ 0 với mọi y ∈ K, (1.18) trong đó K là một tập lồi đóng và F là một hàm liên tục từ K vào Rn cho trước. Ta dùng ký hiệu VI (K, F ) để chỉ bài toán bất đẳng thức biến phân nêu trên. Có thể giải thích ý nghĩa hình học của bài toán bất đẳng thức biến phân, hay chính xác hơn của các bất đẳng thức (1.18) như sau. Điểm z ∈ K là một nghiệm của bài toán VI (K, F ) khi và chỉ khi F (z) không tạo nên một góc tù với mọi véc tơ có dạng y − z với y ∈ K. Ta hình thức hóa nhận xét này nhờ dùng khái niệm nón pháp tuyến (normal cone). Cụ thể, với mỗi tập lồi đóng K và bất kỳ véctơ z 0 ∈ K, ta định nghĩa nón pháp tuyến (ngoài) của K tại z 0 là tập  NK (z 0 ) = d ∈ Rn : dT (y − z 0 ) ≤ 0 với mọi y ∈ K . Các véctơ trong tập này được gọi là véctơ pháp tuyến (ngoài) của tập K tại z 0 . Khi đó, bất đẳng thức (1.18) nói rằng véctơ z ∈ K là một nghiệm của VI (K, F ) khi và chỉ khi −F (z) là véctơ pháp tuyến của K tại z (tức −F (z) ∈ NK (z)) hay 0 ∈ F (z) + NK (z). Nón pháp tuyến đóng một vai trò quan trọng trong giải tích lồi và trong lý thuyết qui hoạch phi tuyến. Bài toán bù tuyến tính LCP là một trường hợp riêng của bất đẳng thức biến phân. Có thể nhận thấy điều này bằng cách đặt y = 0 và đòi 14 hỏi z và F (z) không âm, tức là z, F (z) ∈ Rn+ . Các ràng buộc nhận được z ≥ 0, F (z) ≥ 0 và z T F (z) ≤ 0 có thể diễn đạt nhờ toán tử bù như sau: 0 ≤ z⊥F (z) ≥ 0. Đó là ràng buộc bù của bài toán LCP. Định lý sau cho thấy rằng bài toán LCP (q, M ) và bài toán VI (R+ , q + M z) có nghiệm như nhau. Định lý 1.1 ([7], tr. 7). Cho F = q + M z với q ∈ Rn , M ∈ Rn×n và z ∈ Rn+ . Khi đó, bài toán bất đẳng thức biến phân VI (Rn+ , q + M z) và bài toán bù tuyến tính LCP (q, M ) có tập nghiệm trùng nhau hoặc cùng vô nghiệm. Chứng minh. Giả sử z là một nghiệm của bài toán VI (Rn+ , F ), tức là z ∈ Rn+ và (y − z)T F (z) ≥ 0 với mọi y ∈ Rn+ . Nói riêng, với y = 0 ta nhận được z T F (z) ≤ 0. Do z ∈ Rn+ nên 2z ∈ Rn+ nên với y = 2z ta lại được z T F (z) ≥ 0. Hai bất đẳng thức vừa nhận được cho thấy z T F (z) = 0. Từ đó suy ra y T F (z) ≥ 0 với mọi y ∈ Rn+ . Bất đẳng thức này kéo theo F (z) ≥ 0 (vì nếu có F (Z)i < 0 thì cho yk = 0 với mọi k 6= i và yi → +∞ sẽ dẫn tới mâu thuẫn), nghĩa là z là một nghiệm của bài toán LCP (q, M). Ngược lại, giả sử z là một nghiệm của bài toán LCP (q, M ), tức là z ≥ 0, F (z) = M z + q ≥ 0 và z T F (z) = 0. Từ đó suy ra (y − z)T F (z) = y T F (z) ≥ 0 với mọi y ∈ Rn+ (do y ≥ 0 và F (z) ≥ 0), tức z cũng là một nghiệm của bài toán VI (Rn+ , F ).  Có thể mở rộng định lý trên cho bài toán bù CP ở dạng tổng quát (xem Định nghĩa 1.2). Mối liên hệ giữa bài toán bất đẳng thức biến phân VI (K, F) và bài toán bù CP (K, F) với K là một nón được nêu trong kết quả cơ bản sau. Định lý 1.2 ([4], tr. 4). Cho K là một nón trong Rn . Véctơ z là một nghiệm của bài toán VI (K, F ) khi và chỉ khi z là một nghiệm của bài toán CP (K, F ). Chứng minh. Giả sử z là một nghiệm của bài toán VI (K, F ), tức là z ∈ K và (y − z)T F (z) ≥ 0 với mọi y ∈ K. Do K chứa gốc nên với 15 y = 0 ta nhận được z T F (z) ≤ 0. Hơn nữa, do z ∈ K, K là một nón nên 2z ∈ K và với y = 2z ta được z T F (z) ≥ 0. Kết hợp hai bất đẳng thức trên cho thấy z T F (z) = 0. Từ đó suy ra y T F (z) ≥ 0 với mọi y ∈ K. Vậy F (z) ∈ K ∗ (theo định nghĩa của K ∗ ). Tóm lại, z ∈ K, F (z) ∈ K ∗ và z T F (z) = 0, tức là z là một nghiệm của bài toán bù CP (K, F ). Ngược lại, giả sử z là một nghiệm của bài toán bù CP (K, F ), tức là z ∈ K, F (z) ∈ K ∗ và z T F (z) = 0. Từ đó suy ra (y − z)T F (z) = y T F (z) ≥ 0 với mọi y ∈ K (do y ∈ K và F (z) ∈ K ∗ ), tức z cũng là một nghiệm của bài toán VI (K, F ).  1.2.2. Bài toán qui hoạch toán học với ràng buộc cân bằng Qui hoạch toán học với ràng buộc cân bằng (Mathematical Programs with Equilibrium Constrains, viết tắt là MPEC) là một hướng nghiên cứu hoàn toàn mới và là hướng mở rộng của tối ưu hai cấp (Bilevel Programming, viết tắt là BP). Các ràng buộc cân bằng thường được biểu thị dưới dạng một hệ bù hay một bất đẳng thức biến phân, trong đó dạng đầu là trường hợp riêng của dạng sau. MPEC có phạm vi ứng dụng rộng rãi, chẳng hạn trong kinh tế và trong nghiên cứu thị trường điện năng. Các khái niệm của MPEC bắt nguồn từ các khái niệm kinh tế trong trò chơi Stackelberg. Trò chơi Stackelberg và trò chơi song ma trận sẽ được đề cập chi tiết hơn ở Chương cuối của luận văn. MPEC là bài toán tối ưu được phân thành hai cấp. Bài toán này đôi khi còn gọi là bài toán qui hoạch toán học với các ràng buộc bù (Mathematical Programs with Complementarity Constraints, viết tắt là MPCC), do các ràng buộc cân bằng được mô tả bởi một hệ bù. Các ràng buộc bù lại có thể phân chia thành các bài toán bù hỗn hợp (viết tắt là MCP) và bài toán bù tuyến tính tổng quát (viết tắt là GLCP). Bài toán GLCP (còn được biết với tên gọi bài toán bù tuyến tính trên các nón) là sự hợp nhất các lớp bài toán bù tuyến tính đơn điệu, qui hoạch tuyến tính, qui hoạch lồi toàn phương và bài toán bù tuyến tính đơn điệu hỗn hợp. 16 Theo [6], MPEC là một bài toán tối ưu với hai nhóm biến: x ∈ Rn và y ∈ Rm , trong đó một số hay tất cả các ràng buộc của bài toán được xác định bởi một bất đẳng thức biến phân hay một hệ bù phụ thuộc tham số với y là các biến chính và x là véctơ tham số của bài toán. Chính xác hơn, có thể phát biểu mô hình toán học của bài toán MPEC như sau. Giả sử f : Rm+n → R và F : Rm+n → Rm là các hàm cho trước, Z ⊆ Rm+n là một tập đóng khác rỗng và C : Rn → Rm là một ánh xạ đa trị với ảnh là các tập lồi đóng (có thể rỗng), tức là với mỗi x ∈ Rn , C(x) là một tập con lồi đóng (có thể rỗng) trong Rm .Tập các véctơ x ∈ Rn với C(x) 6= Ø gọi là miền hữu dụng (domain) của C và được ký hiệu là dom (C). Giả sử X là hình chiếu của Z trên Rn , tức là X = {x ∈ Rn : ∃y ∈ Rm sao cho (x, y) ∈ Z} . Hàm f là hàm mục tiêu toàn thể cần tìm cực tiểu, F là hàm cân bằng của bài toán bên trong (ở mức dưới), Z là miền chấp nhận được đối với các cặp (x, y) của bài toán ở mức trên. Tập C(x) xác định các giá trị y chấp nhận được đối với mỗi x ∈ X cho trước. Ta giả thiết X ⊆ dom(C). Với các định nghĩa trên, dạng tổng quát của bài toán qui hoạch toán học với ràng buộc cân bằng MPEC như sau: min f (x, y) x,y với các điều kiện (x, y) ∈ Z, y ∈ S(x), trong đó với mỗi x ∈ X, S(x) là tập nghiệm của bất đẳng thức biến phân (VI) được xác định bởi cặp (F (x, •), C(x)), tức là y ∈ S(x) khi và chỉ khi y ∈ C(x) và y thỏa mãn hệ bất đẳng thức (z − y)T F (x, y) ≥ 0 với mọi z ∈ C(x). Như đã thấy ở Mục 1.2.1, bài toán bù tuyến tính là một trường hợp riêng của bài toán bất đẳng thức biến phân. Hàm f là hàm mục tiêu của bài toán ở mức trên, F là hàm cân bằng của bài toán ở mức dưới. Về mặt tính toán, dạng tổng quát này của bài toán MPEC là rất khó 17 giải. Bài toán qui hoạch toán học với ràng buộc cân bằng nói chung là một bài toán NP-khó. Có một số cách diễn đạt khác của bài toán cân bằng. Cách phát biểu có thiên hướng về điều kiện bù như sau (xem [7], tr. 4-5): min f (x) x với điều kiện c(x) ≥ 0, 0 ≤ x1 ⊥ x2 ≥ 0, trong đó ⊥ là toán tử bù, nghĩa là đối với mỗi cặp bù i của hai véctơ x1 và x2 . Nếu x1i 6= 0 thì x2i = 0 và ngược lại. Các bài toán MPEC này lại có thể biến đổi thành bài toán qui hoạch phi tuyến (Nonlinear Programming, viết tắt là NLP) bằng cách thay ràng buộc bù 0 ≤ x1 ⊥ x2 ≥ 0 bởi ràng buộc X 1 x2 ≤ 0, trong đó X 1 = diag(x1 ). Cách làm này cho phép diễn đạt bài toán MPEC như một bài toán qui hoạch phi tuyến min f (x) x với điều kiện c(x) ≥ 0, (1.19) x1 , x2 ≥ 0, X 1 x2 ≤ 0. Có nhiều khó khăn nghiêm trọng khi giải bài toán (1.19), chủ yếu do không thỏa mãn các giả thiết ổn định chuẩn. Tuy nhiên vẫn có ít nhiều thành công trong việc tìm nghiệm tối ưu địa phương của bài toán (1.19) nhờ áp dụng phương pháp dãy qui hoạch toàn phương [5]. Sự mô tả bài toán bất đẳng thức biến phân cho thấy mối liên hệ giữa bài toán MPEC và bài toán LCP. Như đã thấy, các ràng buộc cân bằng của bài toán MPEC được diễn đạt dưới dạng các bất đẳng thức biến phân. Như vậy, do bài toán LCP là một trường hợp riêng của bất đẳng thức biến phân nên một lớp bài toán con của MPEC là những bài toán có các ràng buộc cân bằng được xác định bởi một bài toán LCP. Theo nghĩa đó, LCP là một trường hợp riêng của bài toán MPEC. 18 1.3. Sự tồn tại và duy nhất nghiệm của bài toán LCP Tính đơn điệu là khái niệm trung tâm trong nghiên cứu sự tồn tại và duy nhất nghiệm của bài toán bù tuyến tính và bài toán bất đẳng thức biến phân. Như sẽ đề cập tới ở chương sau, phương pháp điểm trong có thể giải bài toán LCP đơn điệu trong thời gian đa thức. Vì thế LCP đơn điệu xem như một "bài toán dễ". Sau đây sẽ trình bày một số định lý cơ bản về sự tồn tại và duy nhất nghiệm của bài toán LCP. Trước tiên ta nêu một số định nghĩa cần thiết. Định nghĩa 1.4 (Tử thức chính). Cho A là một ma trận cấp n × n. Ma trận con cấp k × k của A tạo nên bằng cách bỏ đi (n − k) hàng và (n − k) cột như nhau của A gọi là ma trận con chính (principal submatrix) của A. Định thức của ma trận con chính của A gọi là tử thức chính (principal minor) của A. Một lớp ma trận đảm bảo cho bài toán LCP (q, M ) có nghiệm là lớp P-ma trận. Định nghĩa 1.5 (P-ma trận). Ma trận vuông thực M gọi là một P-ma trận nếu zi (M z)i > 0, i = 1, ..., n với mọi 0 6= z ∈ Rn . Có thể chứng minh được rằng LCP (q, M ) có ít nhất một nghiệm với mọi véctơ thực q nếu M là một P-ma trận và mọi tử thức con chính của M là số dương. Định lý 1.3 ([7], tr. 8). Cho M ∈ Rm×m là một P-ma trận với mọi tử thức con chính là số dương. Khi đó, bài toán LCP (q, M ) có nghiệm với mọi véctơ q ∈ Rm Như đã nói ở trên, một số kết quả chính về sự tồn tại và duy nhất nghiệm liên quan chặt chẽ với tính đơn điệu của bài toán. Có nhiều kiểu đơn điệu khác nhau và chúng có vai trò quan trọng đối với sự tồn tại nghiệm của bài toán LCP và bài toán VI. Trong luận văn này tính đơn điệu được định nghĩa như sau. Định nghĩa 1.6 (Tính đơn điệu). Một ánh xạ F : K ⊆ Rm → Rm gọi là 19 1. đơn điệu trên K nếu với mọi cặp (u, v) ∈ K × K (u − v)T (F (u) − F (v)) ≥ 0 2. đơn điệu chặt trên K nếu với mọi cặp (u, v) ∈ K × K, u 6= v (u − v)T (F (u) − F (v)) > 0. 3. đơn điệu mạnh trên K nếu tồn tại hằng số c > 0 sao cho với mọi cặp (u, v) ∈ K × K (u − v)T (F (u) − F (v)) ≥ c ku − vk2 . Các kết quả nêu dưới đây lấy nguyên gốc từ ([6], tr. 55) ở đó chúng được trình bày cho bài toán bất đẳng thức biến phân. Theo Định lý 1.1, các kết quả của Định lý 1.4 cũng đúng cho bài toán LCP. Định lý 1.4. Cho K ⊆ Rm là một tập lồi đóng và F : K → Rm là một ánh xạ liên tục. Ký hiệu SOL (F, K) là tập nghiệm (có thể rỗng) của VI (F, K). Khi đó: 1. Nếu F đơn điệu trên K thì SOL (F, K) là một tập lồi đóng. 2. Nếu F đơn điệu chặt trên K thì SOL (F, K) gồm nhiều nhất một phần tử. 3. Nếu F đơn điệu mạnh trên K thì SOL (F, K) gồm đúng một phần tử. Sự tồn tại nghiệm được đảm bảo khi q không âm. Sự kiện này sẽ được sử dụng trong phương pháp Lemke trình bày ở chương sau. Định lý 1.5. ([7], tr. 9). Nếu q không âm thì bài toán LCP (q, M ) luôn giải được với z = 0 là nghiệm tầm thường. Chứng minh. Chỉ cần đặt z = 0 và kiểm tra lại rằng các ràng buộc trong Định nghĩa 1.1 về bài toán bù tuyến tính LCP được thoả mãn với mọi q ≥ 0.  Tóm lại, chương này đã đề cập tới ba bài toán tối ưu trong không gian hữu hạn chiều, liên quan chặt chẽ với nhau: bài toán bù tuyến tính LCP (q, M) (bù phi tuyến CP (K, F)), bài toán bất đẳng thức biến phân VI (K, F) và bài toán qui hoạch toán học với ràng buộc cân bằng MPEC. Bài toán bù tuyến tính (bù phi tuyến) là trường hợp riêng của bài toán bất đẳng thức biến phân khi nón K = Rn+ và F (z) = q + M z(K ⊆ Rn+ )).