Chương 1 BÀI TOÁN CÂN BẰNG VÀ MỘT SÔ BÀI TOÁN LIÊN QUAN 1.1 Một số kiến thức chuẩn bị 1.1 Không gian Hilbert Định nghĩa 1. Cho ? là không gian vectơ thực, được trang bị một tích vô hướng, ký hiệu (.), và đầy đủ đối với chuẩn lal] = VÁz. Khi đó ?( được gọi là một không gian Hilbert thực. Như ta đã biết tích vô hướng (z, ) là một hàm liên tục và thỏa mãn bất đẳng thức Cauchy-Schwarz |œ,)| < ll>llllw||.yw<?, và khong gian R” 1A mot không gian Hilbert với tích vô hướng và chuẩn tương ứng là n h 1/2 (x,y) = So reyes llzll = (5z) , k=l k=l trong đó, # := (#1,đa,.,®u), := (UI, 9, ---a) € JR", Sau đây chúng tôi nhắc lại một số tính chất hữu dụng của chuẩn và được sự dụng nhiều trong chứng minh hội tụ của các thuật toán sau này.
[11] Với mỗi +, € ?í(, ta có () lle — yll? = Ilzl — l|w|Ủ — 2œ — 9. Cho {z#} là một dãy trong không gian Hilbert ?(. Khi đó, a) {z"} được gọi là hội tụ mạnh tới z € ?( nếu di lJøt — z|| =0, Ky, ky hiéu x b) {z"} được gọi là hội tụ yếu tới z € ?( nếu k lim (a" — x,y) =0 véi mọi y € H, k-+00 ký hiệu #Š — ø. [6] Cho H la mét khong gian Hilbert, H* là không gian đối ngẫu ctia H.
Day {x"} va x thudc H. Khi do, ta có (i) Nếu #* —> œ thà ø# — œ; (ii) Nếu +* — œ tà ||z*|| — ||+|| trong H, thà z* — 2; () Nếu không gian ?( là hữu hạn chiều, thì sự hội tụ mạnh uà hội tụ yếu trong ?( là tương đương nhau; (iv) Néu day {x*} bi chan trong khong gian Hilbert H, thi ta ludn trích ra được đấu con của nó hội tụ yếu trong ?(; (u) Nếu ck sx 0à ƒ* —y Ƒ thì ƒ#(a*) — f(x). Phép chiếu trong không gian Hilbert đóng một vai trò quan trong trong lý thuyết tối ưu cũng như trong các phương pháp giải bài toán bất đẳng thức biến phân và bài toán cân bằng. Cho Œ C ?, khác rỗng.
Dat do(x) := inf ||a — z||. c(x) := inf ||a — 2|| Ta goi do(z) 1a khoang cach tit x tdi tap C. Néu tồn tại z* € C sao cho de(z) = ||# — +*||, thì 2* được gọi là hình chiếu vuông góc (gọi tắt là hình chiếu) của + lên Œ và được ký hiệu #* = Pc(z). (ii) U = Pc(œ) khi 0à chỉ khi l# — |Ẻ < llz — z|Ủ ~ llu — z|.2 Hàm lồi và một số khái niệm liên quan Cho Ở là tập con khác rỗng của không gian Hilbert ? và hàm ƒ : C 4 [—œ, +oo].
Khi đó, các tập domƒ := {1 € C: f(x) < +00} epif := {(a,a)€ CxR: f(x) < a} lần lượt được gọi là miền xác định và tập trên đồ thị của hàm f. Ham ƒ được gọi là chính thường trên Ở nếu domƒ # Ú and ƒ(z) > —oo V+ € Œ. Cho Œ là một tập con, lồi khác rỗng của ? và hàm ƒ : Œ — Rn{+œ}. Khi đó, ƒ được gọi là hàm lồi trên Œ nếu tập trên đồ thị của nó là tập lồi trong ? x R.
Ta có mệnh đề sau Mệnh đề 1. [7] Cho Œ là một tập con, lồi khác rỗng cia H va ham ƒ:C + Rn{+ee}. Khi đó, f là một hàm lồi trên Ơ khi va chỉ khi ƒ#@z + (L— À)y) < Àƒ(z) + (1— ÀA)ƒ(9) Vz,y € C,VA € [0, 1]. (1) Nếu tồn tại m > 0 để ƒ(z) — #||z|l? lồi thì ta nói ƒ lồi mạnh với hằng số mm.
(2) Nếu ƒ(Az+(1—À)#) < Àƒ(z)+(1—À)ƒ() Vz,€ Œ,z # u,VA € (0,1) thì ta nói ƒ lồi chặt. Cho Ở là một tập con, lồi khác rỗng của ? và g: Ở -> IR là một hàm lồi, chính thường. Khi đó p € C được gọi là dưới đạo hàm của ø tai 2° € C, néu (p,«— 2°) < g(x) —g(a°) Vee. Tap tất cả các dưới đạo hàm của ø tại z0 € Œ được gọi là dưới vi phân của ø tại z? và được ký hiệu là 0g(z).
Vậy 6g(zÐ):—={p€1?4: (p,zS— +”) < g(a) — g(a®) Va € Ch. Ham ø được gọi là khả dưới vi phân tại z? nếu Øø(z) # Ú và hàm lồi g dude gọi là khả dưới vi phân trên tập Ở nếu ø khả dưới vi phân tại mọi điểm trên Œ. Cho Ở là một tập con, lồi và khác rỗng của R”. Xét ham chi trên Œ " 0 khix € C, Ct) = +00 khiz € C.
Khi đó 9ôc(z°) = No(2°) Va eC, trong đó Wo(#Ð) là nón pháp tuyến ngoài của Œ tại z và được xác định bởi No(2®) = {w EH: w,a—2°) <0, Va eC}. [3| Giá st gi, g2,., gm la ham loi chính thường trên R” va œ€ dơmg. Khi đó, vdi moi x € R” ta cé Ô(Ø1 + ø +. Hon nita, néu céc ham gi, g2,-.,9m (co thể trừ một hàm) liên tục tại mọi điểm ® € n†" dơmg,, thi O(g1 + 92 +.
[2| Giả sử g là hàm lỗi chính thường trên ?( uà z € dong. Khi đó, ta có i) Ðg(+) # © g nửa liên tục dưới tại 0. ii) g kha vi tai x° thi Og(2°) = {Vg(2°)}. Cho C là một tập con, khác rỗng cla H va g là một hàm tit C vao RU {+00}.
Diém z? € Ở được gọi là cực tiểu địa phương của hàm 9 sào cho g trên Œ, nếu tồn tại lân cận (+9) của + —œ < gø(#)<gø() V+zc€ŒnU(z°). Điểm z? được gọi là cực tiểu toàn cục của ƒ trên Ở, nếu —oo < g(a°) < g(a) Vr eC. [7] Cho g: H + RU {+o} là một hàm léi chinh thudng va Œ G2 là tập lồi, khác rỗng. Khi đó mọi điểm cuc tiéu dia phương của g trên Œ ` cững là cực tiểu toần cuc va tập tất cá các điểm cực tiểu toàn cục sol(g) := argmin{g(x) : x € C} là tập lồi.
Hơn nữa, nếu g là loi chat va Sol(g) # II thà Sol(g) có duy nhất một phần tủ. Cho g : H > RU {+00} la một hầm loi chính thường, khả dưới ơi phân. [2] Cho g: H > RU {+00} là một hàm lồi, khả dưới ưi phân va C CH la tap loi, khác rỗng. Khi đó, nếu g liên tục tại một điểm nào đó của Œ uà # € argmin{g(z) : + € C} thì 0€ Og(%) + NeŒ).1) Noguoc lai, néu (1.1) ding tai thi T € argmin{g(x) : x € Ch.
Cho Œ là tập con khác rỗng của không gian Hilbert ? và hàm ƒ : Ở + R,2° € C. khi dé (a) ƒ là nữa liên tục dưới tại z? nêu V{z} C Œ,#+# — z? suy ra lim inf f («*) > f(x) E00 10 (b) ƒ là nữa liên tục dưới yếu tại z? nếu V{z} C Ơ,# — # suy ra lim inf f(x") > ƒ(z) —>O© (c) ƒ là nữa liên tục trên tại #2? nếu — ƒ nữa liên tục dưới tại z?. (d) f là nữa liên tục trên yếu tại z? nếu — ƒ nữa liên tục dưới yếu tại z?. Cho Œ là tập lồi đóng khác rỗng trong ? và g : C > (—œ, +œ] là hàm lồi, chính thường và nửa liên tục dưới.
Toán tử gần kề của ø trên Œ được ký hiệu proxs(.) và được cho bởi : 1 2 proxz(x) := argmin 4 g(u) + sllu —#|“:ucC},zc?1. Ta có một số tính chất quan trọng của toán tử proximal Ménh dé 1. [16] Véi mdi x € C va uới mọi ụ € Œ. Các khẳng định sau đâu la tương đương (i) w= proxg(x).3 Tính đơn điệu của song hàm Để xét tính duy nhất nghiệm và một số phương pháp tìm nghiệm của bài toán cân bằng, ta cần nhắc lại định nghĩa về tính đơn điệu của song hàm cân bằng ƒ.
Cho Œ là tập con lồi đóng khác rỗng trong ?. Song hàm ƒ : Œ x Œ — R được gọi là (a) +-đơn điệu mạnh trên Ở nếu tồn tại hằng số + > 0 sao cho ƒf(œ,w) + ƒ(u. Từ định nghĩa trên, ta suy ra mối quan hệ sau: (a) = (b) = (c) = (e) = (a). Trong trường hợp tổng quát, các chiều ngược lại nói chung là không đúng.
Gia stt song ham f : C x C + lR xác định bởi f(x,y) = (F(+),— +} vdi moi x,y € Ơ. Bằng định nghĩa, ta dễ chỉ ra rằng các khái niệm về tính đơn điệu của song hàm ƒ và các khái niệm đơn điệu tương ứng của hàm giá F (vi du song ham f đơn điệu mạnh tương ứng với ánh xạ #' là đơn điệu mạnh) là tương đương. Cho tap Ci := { € R: x < —2},C) ={x © R: x < 0} va song ham f:C x C —-R xac dinh béi f(a,y) = (24+ x) (x — 9). Khi đó ƒ đơn điệu mạnh trên C1, đơn điệu chặt trên Ca.
Nhưng ƒ không đơn điệu mạnh trên Ca. Thật uậu, với mọi x,y € ŒI, ta có fay +fyr) = (2+z”)(øœ—w)+(2+2)(w— +) = (œ+w)(- 0) < —4(x— 0). 13 Như vậy, ƒ đơn điệu mạnh trên C¡ với hằng sé Ø = 4. Tương tự với z, € C2, z # 1 ta có f(x,y) + f(.#) = (œ + 9)(œ — u)” <0, do đó, ƒ đơn điệu chặt trên Ca.
Giả sử ƒ đơn điệu manh trên C2; với hệ số đ > 0. Khi đó, ta có f(,u) + ƒu,#) € ~0(œ — y)” Va,y € Co. Suy ra, z+<=j_ ŸWz,€ Ca. Chon x = —//4 và = —8/2 cùng thuộc Œạ, thay vào bất đẳng thức trên ta thu được —Š < —8, vô lý.
Dãn đến, ƒ không đơn điệu mạnh trén C9. Xét song hàm ƒ : R x R —> R xác định bởi ƒ(œ,) = #”(w— #). Khi đó, ƒ giả đơn điệu trên C := R \ {0}. Nhưng ƒ không đơn điệu trên Œ Thật uậy, Giả sử z, € Ở và ƒ(z,) = z?(u— z) > 0.
Vì zụ # 0, nên suy ra > ø và do đó ƒ(g,#) = 02(œ — ) < 0. Vậy, ƒ giả đơn điệu trên C. Mặt khác với moi x, y € (—co, 0) va x # , ta có 2 ƒ(œ. Do vậy, ƒ không đơn điệu trên Œ.4 Một số bổ đề kỹ thuật Trong mục này, chúng tôi nhắc lại một vài kết quả đã biết và sẽ được dùng để chứng minh sự hội tụ của các thuật toán trong các chương sau.
|24| Gid sit {xy} la mét day trong H uà 9 C 2Á lồi, đóng thỏa mãn các điều kiện sau 14 (¡) Với mỗi zọ € Q, giới hạn tim \|an — Xol| ton tai; (ii) Tap céc diém tu yéu ctia {xn} thude vaio tap Q. Khi đó {„} hội tụ yếu tới một điểm thuộc ©.