Luận văn Nghiên cứu hiệu chỉnh hóa trong bài toán cân bằng

λ → 0, do tính liên tục của f nên: 0 ≤ f(x∗, y), ∀y ∈ K. ⇒ x∗ là nghiệm của bài toán cân bằng. Ta có điều phải chứng minh.  Nhận xét [2] ? Mệnh đề đảo của định lí 2.1.1 không đúng. Thật vậy, lấy N = 1 và lấy K = [0, 2] và kí hiệu S1 là tập nghiệm của bài toán đối ngẫu, S2 là tập nghiệm của bài toán cân bằng. Khi đó, a, f(x, y) = (x− y)2 ⇒ S1 = ∅, S2 = [0, 2] ⇒ S1 * S2. b, f(x, y) = max{0, | x− y | −1} ⇒ S1 = {1}, S2 = [0, 2] ⇒ S1 * S2. ? Khi f là giả đơn điệu, nghĩa là ∀x, y ∈ K : f(x, y) ≥ 0 ⇒ f(y, x) ≤ 0, mệnh đề đảo của 2.1.1 đúng. Khi đó, bài toán đối ngẫu và bài toán cân bằng có cùng tập nghiệm. Ta có thuật toán chiếu 2.1 sau để giải bài toán đối ngẫu. Thuật toán chiếu 2.1 [2] Bước 1: Cho k = 0, x0 ∈ K và r0 = ‖ x0 ‖. Bước 2: Lấy xk và rk (i) Định nghĩa: 17 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Kk = {x ∈ K : ‖ x ‖≤ rk + 1}. (2.1a) (ii) Tìm yk ∈ Kk có tính chất: max y∈Kk f(y, xk)− k ≤ f(yk, xk), (2.1b) với {k}k≥0 ⊂ [0,+∞] là dãy thoả mãn lim k→+∞ k = 0. (iii) Tính xk+1 dạng: xk+1 = xk + tk [ PLf (yk)(x k)− xk], (2.1c) trong đó, PLf (yk)(x k) là phép chiếu trực giao của xk lên Lf(yk), và Lf(yk) = {x ∈ K | f(yk, x) ≤ 0} là tập lồi, {tk}k≥0 ⊂ [α, 2− α] với α ∈ [0, 1]. (iv) Tính rk thông qua: rk+1 = max{rk, ‖ xk+1 ‖} (2.1d) và trở về (i) của bước 2. Mệnh đề 2.1.1. [2] Thuật toán chiếu 2.1 được xác định đúng đắn. Chứng minh • Chứng minh (2.1b) đúng. Thật vậy, từ công thức (2.1a) và (2.1d) ta có: Kk ⊂ Kk+1, ∀k ∈ N. Do x0 ∈ K và ‖ x0 ‖≤ r0 + 1 nên suy ra x0 ∈ K0 ⇒ x0 ∈ Kk, ∀k ∈ N Mặt khác, K là tập đóng nên mọi Kk là khác rỗng và compact. Lại do tính liên tục của f nên f(., yk) đạt cực đại trên Kk, vì vậy tồn tại yk ∈ Kk thoả mãn: max y∈Kk f(y, xk)− k ≤ f(yk, xk). • Chứng minh (2.1c) đúng. Thật vậy, do tính lồi của f(yk, .) và tính lồi của tập K nên tập khác rỗng: Lf(y k) = {x ∈ K | f(yk, x) ≤ 0} 18 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn là tập lồi, đóng. Do đó, xk+1 = xk + tk [ PLf (yk)(x k)− xk] được xác định duy nhất. Vậy mệnh đề được chứng minh.  Mệnh đề 2.1.2. [2] Giả sử rằng: +∞⋂ k=0 Lf(y k) 6= ∅, (2.3) thì: a, ∀x∗ ∈ +∞⋂ k=0 Lf(y k) dãy {‖ xk − x∗ ‖}k≥0 không tăng và do đó hội tụ. b, Dãy {xk}k≥0 bị chặn. c, lim k→+∞ ‖ xk+1 − xk ‖= 0. Chứng minh a, Cho x∗ ∈ +∞⋂ k=0 Lf(y k), từ công thức (2.1c) của thuật toán 2.1 ta có xk+1 = xk + tk [ PLf (yk)(x k)− xk] do đó: ‖ xk+1 − x∗ ‖2 = ‖ xk + tk[PLf (yk)(xk)− xk]− x∗ ‖2 = ‖ xk − x∗ ‖2 + tk2 ‖ PLf (yk)(xk)− xk ‖2 + 2 tk 〈 xk − x∗, PLf (yk)(xk)− xk 〉 . (2.4) Ta lại có: 2 tk 〈 xk − x∗, PLf (yk)(xk)− xk 〉 = = 2 tk 〈 xk − PLf (yk)(xk) + PLf (yk)(xk)− x∗, PLf (yk)(xk)− xk 〉 = −2 tk ‖ xk − PLf (yk)(xk) ‖2 +2 tk 〈 PLf (yk)(x k)− x∗, PLf (yk)(xk)− xk 〉 . (2.5) Từ (2.4) và (2.5) ta có: ‖ xk+1 − x∗ ‖2 = ‖ xk − x∗ ‖2 + tk2 ‖ PLf (yk)(xk)− xk ‖2 − − 2 tk ‖ xk − PLf (yk)(xk) ‖2 + + 2 tk 〈 PLf (yk)(x k)− x∗, PLf (yk)(xk)− xk 〉 . (2.6) 19 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Do tính chất của phép chiếu trực giao và x∗ ∈ Lf(yk) nên số hạng cuối cùng của (2.6) không dương, tức là: 2 tk 〈 PLf (yk)(x k)− x∗, PLf (yk)(xk)− xk 〉 ≤ 0. (2.7) Từ (2.6), (2.7) và ∀k ∈ N ta suy ra: ‖ xk+1 − x∗ ‖2 ≤‖ xk − x∗ ‖2 + tk2 ‖ PLf (yk)(xk)− xk ‖2 − − 2 tk ‖ xk − PLf (yk)(xk) ‖2 = ‖ xk − x∗ ‖2 −tk(2− tk) ‖ xk − PLf (yk)(xk) ‖2 ≤‖ xk − x∗ ‖2 . (2.8) Vậy dãy {‖ xk − x∗ ‖}k≥0 không tăng và do đó hội tụ. b, Theo kết quả a, ta có dãy {‖ xk − x∗ ‖}k≥0 hội tụ. Mặt khác, ‖ xk ‖= ‖ xk − x∗ + x∗ ‖≤‖ xk − x∗ ‖ + ‖ x∗ ‖. ⇒ {xk}k≥0 bị chặn. c, Ta viết lại (2.8) dạng: tk(2− tk) ‖ xk − PLf (yk)(xk) ‖2≤‖ xk − x∗ ‖2 − ‖ xk+1 − x∗ ‖2 . (2.9) Vì 0 < α ≤ tk ≤ 2− α với 0 < α < 1 ta có 0 < α(2− α) ≤ tk(2− tk). Từ (2.9) ta suy ra: α(2− α) ‖ xk − PLf (yk)(xk) ‖2≤‖ xk − x∗ ‖2 − ‖ xk+1 − x∗ ‖2 . (2.10) Từ (2.10), 0 < α(2− α) và tính hội tụ của {‖ xk − x∗ ‖}k≥0 ta có: lim k→+∞ {xk − PLf(yk)(xk)} = 0. (2.11) Do đó, lim k→+∞ xk+1 − xk tk = 0. Vì 0 < α ≤ tk ≤ 2−α nên (xk+1−xk) → 0 khi k → +∞.  Mệnh đề 2.1.3. [3] Giả sử: i, Dãy {xk}k≥0 bị chặn, ii, lim k→+∞ ‖ xk+1 − xk ‖= 0. Khi đó, dãy {xk}k≥0 hội tụ tới nghiệm x∗ của bài toán cân bằng. 20 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Chứng minh • Do xk+1 = xk + tk [ PLf(yk)(x k)− xk]⇒ xk+1 − xktk = [PLf(yk)(xk)− xk]. Từ giả thiết ii, ta suy ra: lim k→+∞ {xk − PLf(yk)(xk)} = 0. • Chứng minh {yk}k≥0 bị chặn? Theo giả thiết ta có dãy {xk}k≥0 bị chặn, do vậy ∃ r > 0 sao cho: ‖ xk ‖≤ r, ∀k ∈ N. Từ công thức (2.1d) của thuật toán chiếu 2.1: rk+1 = max{rk, ‖ xk+1 ‖} ta có: rk = max{‖ x0 ‖, . . . , ‖ xk ‖}. Do đó, rk ≤ r, ∀k ∈ N. Lại từ (2.1a) ta có Kk = {x ∈ K : ‖ x ‖≤ rk + 1} nên Kk ⊂ B(0, r + 1). Từ (2.1b) ta có max y∈Kk f(y, xk)− k ≤ f(yk, xk), yk ∈ Kk, ∀k ∈ N, do vậy: ‖ yk ‖≤ r + 1. Do đó, {yk}k≥0 bị chặn. • Giả sử x là điểm giới hạn của dãy {xk}k≥0 ⊂ K, với K đóng, x ∈ K. Tồn tại dãy con {xkn}kn≥0 của dãy {xk}k≥0 thoả mãn: lim kn→+∞ xkn = x. Tương ứng ta xét dãy con {ykn}kn≥0 cũng bị chặn. Do đó, tồn tại dãy con {yknp}knp≥0 của dãy {ykn}kn≥0 hội tụ, giả sử hội tụ tới y, tức là: lim knp→+∞ yknp = y. Để cho ngắn gọn, ta kí hiệu yknp ≡ ykn, ta cũng làm tương tự với xknp , ta kí hiệu xknp ≡ xkn. • Ta chứng minh f(y, x) = 0? Thật vậy, từ trên có lim k→+∞ {xk−PLf(yk)(xk)} = 0 nên limk→+∞PLf(yk)(x k) = x. 21 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Do tính liên tục của f nên suy ra: f(y, x) = f ( lim kn→+∞ ykn, lim kn→+∞ PLf(ykn )(x kn) ) = lim kn→+∞ f ( ykn, PLf(ykn )(x kn) ) ≤ 0. (2.12) Trong đó, PLf(ykn )(x kn) ∈ Lf(ykn) = {x ∈ K | f(ykn, x) ≤ 0}. Từ (2.1a), (2.1d) có xk ∈ Kk, ∀k ∈ N. Từ định nghĩa 2.1.1 và (2.1b), với ∀k ∈ N ta có: 0 = f(xk, xk) ≤ max y∈Kk f(y, xk) ≤ f(yk, xk) + k. (2.13) Do lim k→+∞ k = 0 và f liên tục nên từ (2.12) suy ra: 0 ≤ lim kn→+∞ {f(ykn, xkn) + kn} = f( lim kn→+∞ ykn, lim kn→+∞ xkn) + lim kn→+∞ kn = f(y, x). (2.14) Kết hợp (2.12), (2.14) suy ra: f(y, x) = 0. (2.15) • Với mọi 0 < δ < 1, x ∈ [intB(0, r∗ + 1− δ)] ∩K, với r∗ = sup k∈N rk? Do rk bị chặn nên r ∗ = sup k∈N rk là hữu hạn. Với 0 < δ < 1 xét B(0, r∗ + 1− δ) ≡ B(δ) Từ (2.1d) có ‖ xk ‖≤ rk ≤ r∗ < r∗+1−δ, ∀k ∈ N, nên suy ra x ∈ intB(δ). Vậy x ∈ [intB(0, r∗ + 1− δ)] ∩K. • Cho B̂(δ) = B(δ) ∩ K, xét bài toán cân bằng (ÊPδ) với hàm f và tập chấp nhận B̂(δ): Tìm x̂ ∈ (ÊPδ) thoả mãn f(x̂, y) ≥ 0, ∀y ∈ B̂(δ) (ÊPδ) Khi đó ta có khẳng định sau: x ∈ B̂(δ) là nghiệm của bài toán (ÊPδ), với 0 < δ < 1. Thật vậy, lấy dãy {rk}k∈N không giảm: rk ≤ rk+1. Chọn k0 ∈ N thoả mãn 22 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn rk0 ≥ r∗ − δ. Khi đó: r∗ + 1− δ ≤ rk + 1, ∀k ≥ k0. Do đó, B̂(δ) ⊂ Kk, ∀k ≥ k0. Lấy z ∈ B̂(δ), ta có z ∈ Kk, ∀k ≥ k0. Vì vậy, f(z, xk) ≤ max y∈Kk f(y, xk) ≤ f(yk, xk) + k, ∀k ≥ k0. (2.16) Do tính liên tục của f , công thức (2.14), (2.15), (2.16) ta có: f(z, x) = f(z, lim kn→+∞ xkn) = lim kn→+∞ f(z, xkn) (2.16) ≤ lim kn→+∞ {f(ykn, xkn) + kn} = f(y, x) = 0. (2.17) Tức là, f(z, x) ≤ 0, ∀z ∈ B̂(δ). (2.18) Từ (2.18), do x ∈ K, với mỗi 0 < δ < 1 ta có: x ∈ ⋂ x∈B̂(δ) Lf(z). Theo định lí 2.1.1 suy ra x là nghiệm của bài toán (ÊP δ) với 0 < δ < 1. • x là nghiệm của bài toán cân bằng 1.1? Cho x là nghiệm của bài toán (ÊPδ), tức là f(x, y) ≥ 0, ∀y ∈ B̂(δ). Theo giả thiết có f(x, x) = 0. Từ các điều trên ta khẳng định x là nghiệm của bài toán tối ưu lồi: min y∈B̂(δ) f(x, y). (2.19) Hàm g : Rn → R ∪ {+∞} có dạng: g(y) = f(x, y) si y ∈ K,+∞ si y 6∈ K. 23 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Với hàm g vừa định nghĩa ta có thể viết lại (2.19) như sau: min y∈B(δ) g(y). Ta đã chứng minh được x là điểm cực tiểu của g trên B(δ), thuộc phần trong của B(δ). Lại do g là hàm lồi, nên x là điểm cực tiểu không ràng buộc của g. Tức là, g(x) ≤ g(y), ∀y ∈ Rn, trong đó g(x) = f(x, x) = 0 ≤ g(y) = f(x, y), ∀y ∈ K. Vậy x là nghiệm của bài toán cân bằng 1.1. •Ta chứng minh lim k→+∞ xk = x ? Ta đã chứng minh được x ∈ ⋂ z∈B̂(δ) Lf(z). Vì thế f(z, x) ≤ 0, ∀z ∈ K, ‖ z ‖≤ r∗ + 1− δ. Do δ ∈ [0, 1] ta có f(z, x) ≤ 0, ∀z ∈ K, ‖ z ‖≤ r∗ + 1. Lại do tính liên tục của hàm f nên f(z, x) ≤ 0, ∀z ∈ K, ‖ z ‖≤ r∗ + 1. Do yk ∈ Kk, ∀k ∈ N nên ‖ yk ‖≤ rk+1 ≤ r∗+1 ⇒ f(yk, x) ≤ 0, ∀k ∈ N. ⇒ x ∈ +∞⋂ k=0 Lf(y k). Theo mệnh đề 2.1.2a, ta có {‖ xk − x}k≥0 hội tụ. Vì thế dãy con {‖ xkn−x}kn≥0 hội tụ về 0, nên {‖ xk−x}k≥0 hội tụ về 0, tức là lim k→+∞ xk = x.  Định lí sau đây sẽ chỉ ra tính chất hội tụ thuật toán chiếu liên tiếp 2.1. Định lý 2.1.2. [2] Cho {xk}k≥0 và {yk}k≥0 ⊂ K là dãy được tính từ thuật toán 2.1. Khi đó: a, Nếu +∞⋂ k=0 Lf(y k) 6= ∅, (2.20) thì {xk}k≥0 hội tụ đến nghiệm của bài toán cân bằng. b, Nếu bài toán cân bằng vô nghiệm thì {xk}k≥0 không hội tụ. 24 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Chứng minh a, Do +∞⋂ k=0 Lf(y k) 6= ∅ và theo mệnh đề 2.1.2, 2.1.3 suy ra {xk}k≥0 hội tụ đến nghiệm của bài toán cân bằng. b, Bằng phản chứng, giả sử {xk}k≥0 ⊂ Rn hội tụ tới nghiệm x∗ ∈ Rn. Do {xk}k≥0 hội tụ nên {xk}k≥0 bị chặn và lim k→+∞ {xk+1 − xk} = 0. Phần còn lại của chứng minh được lập luận như trong chứng minh mệnh đề 2.1.3. Do đó, x∗ là nghiệm của bài toán cân bằng 1.2.1. Mâu thuẫn với giả thiết. Vậy bài toán cân bằng vô nghiệm.  Hệ quả 2.1.1. [2] Nếu bài toán đối ngẫu có nghiệm thì {xk}k≥0 hội tụ tới nghiệm của bài toán cân bằng. Chứng minh Do bài toán đối ngẫu có nghiệm nên ⋂ y∈K Lf(y) 6= ∅ nên +∞⋂ k=0 Lf(y k) 6= ∅, vì ⋂ y∈K Lf(y) ⊂ +∞⋂ k=0 Lf(y k). Theo định lí 2.1.2 suy ra điều phải chứng minh. Hệ quả 2.1.2. [2] Cho {xk}k≥0, {yk}k≥0 là các dãy được tính từ thuật toán 2.1. Nếu f là giả đơn điệu và hoặc {xk}k≥0 hoặc {yk}k≥0 bị chặn thì {xk}k≥0 hội tụ đến nghiệm của bài toán cân bằng. Chứng minh Nếu {xk}k≥0 bị chặn thì {yk}k≥0 cũng bị chặn (theo chứng minh mệnh đề 2.1.3). Giả sử {yk}k≥0 bị chặn và theo giả thiết f là giả đơn điệu nên suy ra +∞⋂ k=0 Lf(y k) 6= ∅. Theo định lí 2.1.2 suy ra điều phải chứng minh.  2.2. Phương pháp đạo hàm tăng cường giải bài toán cân bằng Phương pháp đạo hàm tăng cường lần đầu tiên được Korpelevich đề xuất để giải bài toán tìm điểm yên ngựa, sau đó được phát triển cho bài toán bất 25 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn đẳng thức biến phân. Phương pháp đạo hàm tăng cường giải bài toán cân bằng là sự mở rộng của nguyên lí bài toán cân bằng phụ. Nhưng ở phương pháp đạo hàm tăng cường cho phép giải các bài toán không cần giả thiết đơn điệu mạnh cho hàm f mà chỉ yêu cầu hàm này thoả mãn điều kiện Lipschitz. Trước tiên ta định nghĩa bài toán cân bằng phụ. Định nghĩa 2.2.1. [2] Cho L : K ìK → R và  > 0, ta xét bài toán cân bằng phụ sau: Tìm x∗ ∈ K sao cho : f(x∗, y) + L(x∗, y) ≥ 0, ∀y ∈ K (2.21) Mệnh đề 2.2.1. [2] Cho f : K ìK → R với f(x, x) = 0,∀x ∈ K và cho x∗ ∈ K. Giả sử f(x∗, .) : K → R là hàm lồi khả vi. Cho L : KìK → R là hàm lồi, khả vi, không âm trên tập lồi K theo biến thứ hai y (∀x ∈ K) và thoả mãn: a, L(x, x) = 0,∀x ∈ K; b, ∇yL(x, x) = 0,∀y ∈ K. Khi đó, x∗ ∈ K là nghiệm của bài toán cân bằng khi và chỉ khi nó là nghiệm của bài toán cân bằng phụ (2.21). Chứng minh (⇒) Do x∗ ∈ K là nghiệm của bài toán cân bằng nên f(x∗, y) ≥ 0 với ∀y ∈ K. Ta có  > 0 ⇒ f(x∗, y) ≥ 0,∀y ∈ K, ∀x∗ ∈ K. Vì L : K ìK → R là hàm lồi, khả vi, không âm trên tập lồi K thoả mãn: a, L(x, x) = 0,∀x ∈ K; b, ∇yL(x, x) = 0,∀y ∈ K. nên L(x∗, y) ≥ 0,∀x∗, y ∈ K ⇒ f(x∗, y) + L(x∗, y) ≥ 0,∀y ∈ K. Vậy x∗ ∈ K là nghiệm của bài toán cân bằng phụ. (⇐) Cho x∗ ∈ K là nghiệm của bài toán cân bằng phụ, ta sẽ chứng minh x∗ ∈ K cũng là nghiệm của bài toán cân bằng. Do x∗ ∈ K là nghiệm của bài toán cân bằng phụ nên nó cũng là nghiệm 26 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn tối ưu của bài toán: min y∈K {f(x∗, y) + L(x∗, y)}. Mặt khác, ta có f(x∗, y) + L(x∗, y) ≥ 0,∀y ∈ K, ⇒ f(x∗, x∗) + L(x∗, x∗) = 0. Ta có x∗ ∈ K là nghiệm tối ưu của bài toán min y∈K {f(x∗, y) + L(x∗, y)}. ⇔ 〈∇yf(x∗, x∗) +∇yL(x∗, x∗), y − x∗〉 ≥ 0,∀y ∈ K. Theo giả thiết, ∇yL(x, x) = 0,∀y ∈ K nên〈 ∇yf(x∗, x∗), y − x∗ 〉 ≥ 0,∀y ∈ K. ⇔ 〈∇yf(x∗, x∗), y − x∗〉 ≥ 0,∀y ∈ K. >0⇔ 〈∇yf(x∗, x∗), y − x∗〉 ≥ 0,∀y ∈ K. Do K là hàm lồi và theo tính chất lồi khả vi của f(x∗, .) : K → R nên theo định nghĩa ta có: f(x∗, y) ≥ f(x∗, x∗) + 〈∇yf(x∗, x∗), y − x∗〉,∀y ∈ K. ⇒ f(x∗, y) ≥ f(x∗, x∗) = 0,∀y ∈ K. Vậy x∗ ∈ K là nghiệm của bài toán cân bằng, mệnh đề được chứng minh. Chú ý Nếu G : K → R là hàm lồi mạnh, khả vi và L(x, y) = G(y)− G(x)− 〈∇G(x), y − x〉,∀x, y ∈ K. (2.22) thì hàm L thoả mãn các tính chất của mệnh đề 2.2.1. Hệ quả 2.2.1. [2] x∗ ∈ K là nghiệm của bài toán cân bằng khi và chỉ khi nó là nghiệm tối ưu của bài toán tối ưu: min y∈K {f(x∗, y) + L(x∗, y)}. Hệ quả 2.2.2. [2] Cho f : K ìK → R với f(x, x) = 0,∀x ∈ K. Giả sử f(x∗, .) : K → R là hàm lồi, khả vi và  > 0. Khi đó, x∗ ∈ K là nghiệm của bài toán cân bằng khi và chỉ khi x∗ ∈ K là nghiệm của bài toán cân bằng phụ (2.21) và hàm L được định nghĩa theo (2.22).. Nhận xét ? x∗ ∈ K là nghiệm của bài toán cân bằng khi và chỉ khi nó là nghiệm của 27 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn bài toán tối ưu: min y∈K {ξf(x∗, y) + G(y)− G(x∗)− 〈∇G(x∗), y − x∗〉}. Hay min y∈K {ξf(x∗, y) + G(y)− 〈∇G(x∗), y〉}. ? Do G là hàm lồi mạnh nên nghiệm của bài toán: min y∈K {ξf(x∗, y) + G(y)− 〈∇G(x∗), y〉} nếu tồn tại là duy nhất. Trong toàn phần này nếu không nói gì thêm ta giả sử f(x, .) đóng, lồi và khả dưới vi phân trên K, với ∀x ∈ K. Sau đây ta đưa ra thuật toán giải bài toán cân bằng phụ. Thuật toán 2.2 [2] Bước 0: Lấy x0 ∈ K,  > 0 và k := 0; Bước 1: Giải bài toán: min y∈K {f(xk, y) + G(y)− 〈OG(xk), y − xk〉}. (2.22a) có nghiệm tối ưu duy nhất yk. Nếu yk = xk thì thuật toán dừng và kết luận xk là nghiệm của bài toán cân bằng. Trái lại, ta chuyển sang bước 2. Bước 2: Giải bài toán: min y∈K {f(yk, y) + G(y)− 〈OG(xk), y − xk〉}. (2.22b) tìm nghiệm duy nhất xk+1. Bước 3: Lấy k := k + 1 và quay lại bước 1. Bổ đề dưới đây chỉ ra rằng nếu thuật toán 2.2 kết thúc tại bước lặp k nào đó thì ta tìm được nghiệm của bài toán cân bằng. Bổ đề 2.2.1. [6] Nếu thuật toán kết thúc tại điểm lặp xk thì xk là nghiệm của bài toán cân bằng. 28 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Chứng minh Nếu xk = yk thì do f(x, x) = 0 nên ta có: f(xk, yk) + G(yk)− G(xk)− 〈OG(xk), yk − xk〉} = 0. Do yk = xk là nghiệm của (2.22a), ta có: 0 = f(xk, yk) + G(yk)− G(xk)− 〈OG(xk), yk − xk〉} ≤ f(xk, y) + G(y)− G(xk)− 〈OG(xk), y − xk〉}, ∀y ∈ K. Từ mệnh đề 2.2.1 suy ra xk là nghiệm của bài toán cân bằng.  Ta kí hiệu K∗ là tập nghiệm của bài toán cân bằng và Kd là tập nghiệm của bài toán đối ngẫu (2.1). Định lí sau chỉ ra tính hội tụ của thuật toán. Định lý 2.2.1. [6] Giả sử rằng: i, G lồi mạnh với hệ số β > 0 và khả vi liên tục trên tập mở Ω ⊇ K. ii, Tồn tại hằng số c1 và c2 > 0 thoả mãn: f(x, y) + f(y, x) ≥ f(x, z)− c1 ‖ y − x ‖2 −c2 ‖ z − y ‖2 ∀x, y, z ∈ K. (2.23) Khi đó: a, Với mọi x∗ ∈ Kd, thì l(xk)−l(xk+1) ≥ (β 2 −c1 ) ‖ yk−xk ‖2 +(β 2 −c2 ) ‖ xk+1−yk ‖2 (2.24) với l(y) := G(x∗)− G(y)− 〈∇G(y), x∗ − y〉, ∀y ∈ K. b, Giả sử f là nửa liên tục dưới trên K ì K, f(., y) là nửa liên tục trên trên K và 0 <  < min { β 2c1 , β 2c2 } , thì dãy {xk} bị chặn và mọi điểm tụ của nó là nghiệm của bài toán cân bằng. Hơn thế, nếu Kd = K∗ (trong trường hợp này f là giả đơn điệu trên K) thì {xk} hội tụ tới nghiệm của bài toán cân bằng. Chứng minh a, Lấy x∗ ∈ Kd bất kì. Theo định nghĩa của hàm l và cho xk, xk+1 ∈ K, 29 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn ta có: l(xk)− l(xk+1) = G(xk+1)− G(xk) + 〈∇G(xk+1), x∗ − xk+1〉 − 〈∇G(xk), x∗ − xk〉 = G(xk+1)− G(xk) + 〈∇G(xk+1)−∇G(xk), x∗ − xk+1〉 − 〈∇G(xk), xk+1 − xk〉. (2.25) Ta có xk+1 là nghiệm của bài toán: min y∈K {f(yk, y) + G(y)− G(xk)− 〈∇G(xk), y − xk〉}, nếu và chỉ nếu 0 ∈ ∂2 { f(yk, xk+1)+G(xk+1)−G(xk)−〈∇G(xk), xk+1−xk〉}+NK(xk+1). với NK(x) là nón pháp tuyến của K tại x ∈ K. Do f(yk, .) là khả dưới vi phân và G là lồi mạnh, khả vi trên K nên theo định lí Moreau-Rockafella ∃w ∈ ∂2f(yk, xk+1) thoả mãn:〈∇G(xk+1)−∇G(xk), y − xk+1〉 ≥ 〈w, xk+1 − y〉, y ∈ K. Mặt khác ta có:〈∇G(xk+1)−∇G(xk), y − xk+1〉 ≥ f(yk, xk+1)− f(yk, y), ∀y ∈ K. Nếu x∗ = y thì bất đẳng thức trên có dạng:〈∇G(xk+1)−∇G(xk), x∗ − xk+1〉 ≥ f(yk, xk+1)− f(yk, x∗). Do x∗ là nghiệm của bài toán (2.1) nên f(yk, x∗) ≤ 0. Vì vậy〈∇G(xk+1)−∇G(xk), x∗ − xk+1〉 ≥ f(yk, xk+1). (2.26) Từ (2.23) với x = xk, y = yk và z = xk+1, khi đó (2.26) được viết:〈∇G(xk+1)−∇G(xk), x∗ − xk+1〉 ≥ f(xk, xk+1)− f(xk, yk) −  c1 ‖ yk − xk ‖2 −  c2 ‖ xk+1 − yk ‖2 . (2.27) 30 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Từ bước 1 của thuật toán 2.2 ta có yk là nghiệm của bài toán: min y∈K {f(xk, y) + G(y)− G(xk)− 〈∇G(xk), y − xk〉}, nên có 0 ∈ ∂2 { f(xk, yk) + G(yk)− G(xk)− 〈∇G(xk), yk − xk〉}+ NK(yk). Tương tự ta thấy rằng f(xk, y)− f(xk, yk) ≥ 〈∇G(yk)−∇G(xk), yk − y〉, y ∈ K. Với y = xk+1 ta có: f(xk, xk+1)− f(xk, yk) ≥ 〈∇G(yk)−∇G(xk), yk − xk+1〉. (2.28) Từ (2.25), (2.27), (2.28) ta suy ra l(xk)− l(xk+1) ≥ G(xk+1)− G(xk)− 〈∇G(xk), xk+1 − xk〉 + 〈∇G(yk)−∇G(xk), yk − xk+1〉 −  c1 ‖ yk − xk ‖2 − c2 ‖ xk+1 − yk ‖2 = G(xk+1)− G(xk)− 〈∇G(xk), yk − xk〉 + 〈∇G(yk), yk − xk+1〉 −  c1 ‖ yk − xk ‖2 − c2 ‖ xk+1 − yk ‖2 = [G(xk+1)− G(yk)− 〈∇G(yk), xk+1 − yk〉] + [G(yk)− G(xk)− 〈∇G(xk), yk − xk〉] −  c1 ‖ yk − xk ‖2 − c2 ‖ xk+1 − yk ‖2 . (2.29) Vì G lồi mạnh với hệ số β nên với mọi x, y ta có: G(y)− G(x)− 〈∇G(x), y − x〉 ≥ β 2 ‖ y − x ‖2, ∀x, y ∈ K. (2.30) Từ (2.29), (2.30) và ∀k ≥ 0 ta có: l(xk)− l(xk+1) ≥ (β 2 −  c1 ) ‖ yk − xk ‖2 +(β 2 −  c2 ) ‖ xk+1 − yk ‖2 . (2.31) 31 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Ta có điều phải chứng minh. b, Từ giả thiết 0 <  < min { β 2c1 , β 2c2 } , ta có: β 2 −  c1 > 0, β 2 −  c2 > 0. Vì vậy từ bất đẳng thức (2.31) ta có khẳng định sau: l(xk)− l(xk+1) ≥ (β 2 −  c1 ) ‖ yk − xk ‖2≥ 0, ∀k. (2.32) Do đó, dãy {l(xk)k≥0} là dãy không tăng. Nó bị chặn dưới bởi 0 nên nó hội tụ đến l∗.Trong (2.32) cho k chạy từ 0 đến m và cộng lại ta có: (β − c1) m∑ k=0 ‖ yk − xk ‖2≤ l(x0)− l(xk+1), ∀m ≥ 0. Dãy {l(xk)}k≥0 hội tụ, cho m →∞ từ bất đẳng thức cuối có: ∞∑ k=0 ‖ yk − xk ‖2< ∞. Từ đó kéo theo: lim k→+∞ ‖ yk − xk ‖= 0. (2.33) Do G là β−lồi mạnh và từ định nghĩa của l(xk) ta có thể viết: 0 ≤ β 2 ‖ x∗ − xk ‖2≤ l(xk), ∀k Vậy {l(xk)} hội tụ và dãy {xk}k≥0 bị chặn nên nó có ít nhất một điểm tụ. Gọi x ∈ K là điểm tụ và {xki}i≥0 là dãy con của {xk} nên có: lim i→+∞ xki = x. Từ (2.33) ta có lim i→+∞ yki = x. Quay lại bước 1 của thuật toán 2.2, ta có: f(xki, y) + G(y)− G(xki)− 〈∇G(xki), y − xki〉 ≥ f(xki, yki) + G(yki)− G(xki)− 〈∇G(xki), yki − xki〉, ∀y ∈ K. 32 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Vì f là nửa liên tục dưới trên K ìK, f(., y) là nửa liên tục trên trên K và f(x, x) = 0, cho i → +∞ ta có; f(x, y) + G(y)− G(x)− 〈∇G(x), y − x〉 ≥ 0, ∀y ∈ K, với x là nghiệm của bài toán 2.22 và L(x, y) = G(y)−G(x)〈∇G(x), y−x〉. Theo mệnh đề 2.2.1 thì x là nghiệm của bài toán cân bằng. Giả sử rằng Kd = K∗, ta khẳng định dãy {xk}k≥0 hội tụ đến x. Thật vậy, theo định nghĩa của l(xk) với x∗ = x ∈ Kd, có l(x) = 0. Vì vậy, do G là β− lồi mạnh nên ta có thể viết: l(xk)− l(x) = G(x)−G(xk)−〈∇G(xk), xk−x〉 ≥ β 2 ‖ xk−x ‖2, ∀k ≥ 0. (2.34) Mặt khác, do {l(xk)}k≥0 không tăng và l(xki) → l(x), ta có l(xk) → l(x) khi k → +∞. Vì vậy, từ (2.34) suy ra lim k→+∞ xk = x ∈ K∗.  Chú ý Điều kiện (2.23) không đủ để suy ra f là liên tục. Trong thực tế, nếu f(x, y) = ϕ(y)−ϕ(x) thì rõ ràng (2.21) luôn đúng với ∀c1 ≥ 0, c2 ≥ 0 và hàm ϕ tuỳ ý. Cho K là tập lồi đa diện dạng: K := {x ∈ Rn : Ax ≤ b}. (2.35) và hàm f : K ìK → R ∪ {+∞} có dạng: f(x, y) := 〈 F (x) + Qy + q, y − x〉, (2.36) với F : K → Rn, Q ∈ Rnìn là ma trận đối xứng xác định dương và q ∈ Rn. Do Q là đối xứng nửa xác định dương, f(x, .) là lồi với mọi x ∈ K. Ta sẽ minh hoạ thuật toán 2.2 cho lớp bài toán cân bằng này. Trước tiên ta có một số kết quả sau: Bổ đề 2.2.2. [5] Nếu f : K → Rn là τ−đơn điệu mạnh trên K. Khi đó: a, f đơn điệu trên K khi τ =‖ Q ‖. b, f là (τ− ‖ Q ‖)−đơn điệu mạnh trên K khi τ >‖ Q ‖. 33 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Chứng minh Từ định nghĩa của hàm f ta có: f(x, y) + f(y, x) = 〈 Q(y − x), y − x〉− 〈F (y)− F (x), y − x〉. (2.37) Mặt khác, 〈 Q(y − x), y − x〉 ≤‖ Q ‖‖ y − x ‖2 . (2.38) Do F là τ−đơn điệu mạnh trên K, tức là〈 F (y)− F (x), y − x〉 ≥ τ ‖ y − x ‖2, Từ (2.37), (2.38) suy ra f(x, y) + f(y, x) ≤ 0, khi τ =‖ Q ‖. Vậy f đơn điệu trên K khi τ =‖ Q ‖. Khi τ >‖ Q ‖ từ (2.37), (2.38) ta suy ra f(x, y)+f(y, x) ≤‖ Q ‖‖ y−x ‖2 −τ ‖ y−x ‖2= −(τ− ‖ Q ‖) ‖ y−x ‖2 . Vậy f là (τ− ‖ Q ‖)− đơn điệu mạnh trênK khi τ >‖ Q ‖.  Bổ đề 2.2.3. [5] Nếu F là liên tục L−Lipschitz trên K, tức là ‖ F (y)− F (x) ‖≤ L ‖ y − x ‖ ∀x, y ∈ K, thì f thoả mãn tiêu chuẩn kiểu Lipschitz (2.23), tức là ta có: f(x, y) + f(y, z) ≥ f(x, z)− c1 ‖ y − x ‖2 −c2 ‖ z − y ‖2 ∀x, y, z ∈ K, với c1 > 0, c2 > 0 thoả mãn: 2 √ c1c2 ≥ L+ ‖ Q ‖ . Chứng minh Với mọi x, y, z ∈ K ta có: f(x, y) + f(y, z)− f(x, z) = 〈F (y)− F (x), z = y〉+ 〈Q(y − z), y − x〉, Theo bất đẳng thức Cauchy-Schwartz, ta có:〈 Q(y − z), y − x〉 ≥ − ‖ Q ‖‖ z − y ‖‖ y − x ‖ . và 〈 F (y)− F (x), z − y〉 ≥ − ‖ F (y)− F (x) ‖‖ z − y ‖ . 34 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Do F là L− Lipschitzs, ta có thể viết: − ‖ F (y)− F (x) ‖‖ z − y ‖≥ −L ‖ y − x ‖‖ z − y | . Do vậy ta suy ra f(x, y) + f(y, z)− f(x, z) ≥ −(L+ ‖ Q ‖) ‖ y − x ‖‖ z − y ‖ . Vì vậy, theo giả thiết có: −(L+ ‖ Q ‖) ‖ y − x ‖‖ z − y ‖≥ −c1 ‖ y − x ‖2 −c2 ‖ z − y ‖2 . Suy ra f(x, y) + f(y, z) ≥ f(x, z)− c1 ‖ y − x ‖2 −c2 ‖ z − y ‖2 .  • Trường hợp đặc biệt, khi F là đơn ánh và F (x) = Px, P ∈ Rnìn, thì hàm f được định nghĩa bởi (2.36) dạng f(x, y) = 〈 Px + Qy + q, y − x〉, (2.39) Ta giả sử rằng ma trận P,Q được chọn thoả mãn Q là đối xứng xác định dương và Q− P là nửa xác định âm. Khi đó, f thoả mãn một số tính chất sau đây: i, f đơn điệu, f(., y) liên tục và f(x, .) khả vi trên tập lồi K. ii, Với mọi x, y, z ∈ K ta có: f(x, y) + f(y, z) ≥ f(x, z)− c1 ‖ z − y ‖2 −c2 ‖ y − x ‖2, (2.40) với c1 = c2 = 1 2 ‖ P −Q ‖ . Thật vậy, với mọi x, y, z ∈ K, do Q− P là nửa xác định âm nên ta có: f(x, y) + f(y, x) = 〈 (Q− P )(y − x), y − x〉 ≤ 0. Do đó, f là đơn điệu trên K. Rõ ràng, f(x, .) khả vi, do Q đối xứng nửa xác định dương nên f(x, .) lồi với mọi x. 35 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Từ ii, ta thấy rằng, với mọi x, y, z ∈ K có: f(x, y) + f(y, z)− f(x, z) = = 〈 Px + Qy + q, y − x〉+ 〈Py + Qz + q, z − y〉− 〈Px + Qz + q, z − x〉 = 〈 Px + Qy, y − x〉+ 〈Py + Qz, z − y〉− 〈Px + Qz, z − x〉 + 〈 q, y − x + z − y − (z − x)〉 = 〈 Px + Qy, y − x〉+ 〈Py + Qz, z − y〉− 〈Px + Qz, z − x〉 = 〈 Px, y − x− (z − x)〉+ 〈Qz, z − y − (z − x)〉+ 〈Qy, y − x〉+ + 〈 Py, z − y〉 = 〈 Px, y − z〉+ 〈Qz, x− y〉+ 〈Qy, y − x〉+ 〈Py, z − y〉 = 〈 P (y − x), z − y〉+ 〈Q(z − y), x− y〉 = 〈 P (y − x), z − y〉+ 〈QT (x− y), z − y〉 = 〈 P (y − x), z − y〉+ 〈Q(x− y), z − y〉 doQ = QT = 〈 (P −Q)(y − x), z − y〉. Từ đó suy ra: f(x, y) + f(y, z)− f(x, z) = 〈(P −Q)(y − x), z − y〉 ≥ −2‖ P −Q ‖ 2 ‖ y − x ‖‖ z − y ‖ ≥ −‖ P −Q ‖ 2 ‖ y − x ‖2 −‖ P −Q ‖ 2 ‖ z − y ‖2 Theo cách đặt, c1 = c2 = 1 2 ‖ P −Q ‖, ta suy ra (2.40). Ví dụ 2.2.1. [5] áp dụng thuật toán 2.2 với hàm chính quy hoá bậc hai G(x) := 12 ‖ x ‖2 để giải bài toán cân bằng. Trong đó, f(x, y) := 〈 Px−Qy + q, y − x〉 và K := {x ∈ Rn : Ax ≤ b}. Trong trường hợp này, theo thuật toán tại bước 1 ta có bài toán con: min y∈K {f(x, y) + 1 2 ‖ y − x ‖2}. 36 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Theo (2.39) f(x, .) là hàm lồi toàn phương, nên bài toán con có thể giải trên MATLAB Optimization Toolbox. Với n = 5 và ma trận P,Q có dạng: Q =  1.6 1 0 0 0 1 1.6 0 0 0 0 0 1.5 1 0 0 0 1 1.5 0 0 0 0 0 2  ; P =  3.1 2 0 0 0 2 3.6 0 0 0 0 0 3.5 2 0 0 0 2 3.3 0 0 0 0 0 3  Với q = (1,−2,−1, 2,−1)T , K = { x ∈ R5 : 5∑ i=1 xi ≥ −1,−5 ≤ xi ≤ 5, i = 1, . . . , 5 } , c1 = c2 = 1 2 ‖ Q − P ‖= 1.4525,  = 12c1 = 0.7262, x0 = (1, 3, 1, 1, 2)T và ζ = 10−3 ta có: k xk1 x k 2 x k 3 x k 4 x k 5 0 1.00000 3.00000 1.00000 1.00000 2.00000 1 -0.34415 1.59236 0.68742 -0.15427 0.63458 2 -0.67195 1.10393 0.65016 -0.57872 0.30562 3 -0.73775 0.92351 0.66742 -0.74459 0.22567 4 -0.74236 0.85342 0.68785 -0.81261 0.20624 5 -0.73668 0.82486 0.70195 -0.84184 0.20152 6 -0.73168 0.81276 0.71030 -0.85493 0.20037 7 -0.72864 0.80747 0.71491 -0.86100 0.20009 8 -0.72700 0.80511 0.71737 -0.86389 0.20002 9 -0.72617 0.80403 0.71865 -0.86529 0.20001 10 -0.72576 0.80354 0.71931 -0.86598 0.20000 Nghiệm xấp xỉ