Luận văn Thạc sĩ Khoa học: Một tiếp cận tối ưu hai cấp cho hiệu chỉnh bài toán cân bằng giả đơn điệu

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN - - - - - - - - - - - - - - - - - - - - - - -

NGUYỄN THỊ THANH HẢI

MỘT TIẾP CẬN TỐI ƯU HAI CẤP

CHO HIỆU CHỈNH BÀI TOÁN CÂN BẰNG

GIẢ ĐƠN ĐIỆU

LUẬN VĂN THẠC SỸ KHOA HỌC

Hà Nội – Năm 2015

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN - - - - - - - - - - - - - - - - - - - - - - -

NGUYỄN THỊ THANH HẢI

MỘT TIẾP CẬN TỐI ƯU HAI CẤP

CHO HIỆU CHỈNH BÀI TOÁN CÂN BẰNG

GIẢ ĐƠN ĐIỆU

Chuyên ngành: TOÁN ỨNG DỤNG

Mã số:

60.46.01.12 LUẬN VĂN THẠC SỸ KHOA HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC: GS.TSKH. LÊ DŨNG MƯU

Hà Nội – Năm 2015

Mục lục

Lời cảm ơn 3

Mở đầu 4

1 Kiến thức chuẩn bị

. . . . . . . . . . 1.1 Không gian Hilbert

1.2 Tập lồi, nón lồi, hàm lồi . . . . . . . . . . .

. . . 1.1.1 Không gian tuyến tính định chuẩn. . . 1.1.2 Không gian Hilbert . . . . . . . . . . . . . . . . . 1.2.1 Tập lồi . . . . 1.2.2 Nón lồi 1.2.3 Hàm lồi . . . . 1.2.4 Tính chất của hàm lồi . . 1.3 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 6 . . 6 . . 7 . . 8 . . 8 . . 9 . . . . 10 . . 11 . . 12 . . . . . . . . . . . . . . . . . .

2 Bài toán cân bằng

. . . . . . . . . . . . . . . . . . . . Phát biểu bài toán . . 2.1.1 2.1.2 Các khái niệm . 2.1 Bài toán cân bằng và các khái niệm . . .

. . .

. . . 2.2 Các trường hợp riêng của bài toán cân bằng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . .

. . . . . 2.2.1 Bài toán tối ưu . . . 2.2.2 Bài toán điểm bất động . 2.2.3 Bài toán cân bằng Nash trong trò chơi không hợp tác . . 2.2.4 Bài toán điểm yên ngựa . . . . 2.3 Sự tồn tại nghiệm của bài toán cân bằng . . 2.4 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 . 13 . . . 13 . . 13 . 18 . . . 18 . . 19 . 19 . . 20 . . 21 . . . 30 . . . . . . . . . . . . . . . . . . . .

3 Hiệu chỉnh dựa trên tối ưu hai cấp

3.1 Hiệu chỉnh bài toán cân bằng giả đơn điệu . . . . . . . . . . . . . 31 . . 31

MỤC LỤC

3.1.1 3.1.2

3.2 Thuật toán giải . . . .

. . . . . . . .

Phương pháp hiệu chỉnh Tikhonov . . Phương pháp điểm gần kề . . . . . . 3.2.1 Mô tả thuật toán . . . 3.2.2 Tính hội tụ của thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 . . 35 . . 40 . . 40 . . 42 . . 47 3.3 Kết luận . . . . . . .

Kết luận chung 48

Tài liệu tham khảo 49

LỜI CẢM ƠN

Qua luận văn này em xin bày tỏ lòng kính trọng và biết ơn sâu sắc đến Thầy GS.TSKH Lê Dũng Mưu, người đã tận tình chỉ bảo, hướng dẫn, giúp đỡ em trong suốt quá trình học tập, nghiên cứu và hoàn thiện luận văn này.

Tác giả xin trân trọng cám ơn Ban Giám hiệu, Phòng Đào tạo sau đại học đặc biệt là quý thầy cô trong Khoa Toán - Cơ - Tin học Trường Đại học Khoa học Tự nhiên - Đại học Quốc gia Hà Nội đã tạo điều kiện thuận lợi cho em hoàn thành khóa học này. Tác giả xin gửi lời cám ơn chân thành tới gia đình, đồng nghiệp, các anh chị, bạn bè trong lớp cao học khóa 2013 - 2015 đã luôn động viên, khích lệ tác giả cố gắng trong suốt khóa học để luôn đạt được kết quả học tập cao nhất.

Em xin chân thành cảm ơn!

MỞ ĐẦU

Lớp các bài toán cân bằng đang ngày càng được áp dụng nhiều vào các lĩnh vực trong cuộc sống như kinh tế, xã hội,... Chính vì vậy mà ngày càng được các nhà khoa học quan tâm, nghiên cứu. Hơn nữa, bài toán cân bằng còn là sự mở rộng của lớp các bài toán khác như bài toán tối ưu, bài toán bất đẳng thức biến phân, bài toán điểm bất động, bài toán cân bằng Nash, bài toán điểm yên ngựa,...

Mô hình chung cho bài toán cân bằng là

Tìm x∗ ∈ C sao cho f (x∗, y) ≥ 0 với mọi y ∈ C (EP(C, f ))

trong đó H là không gian Hilbert, C ⊆ H là một tập lồi và f : C ×C → R ∪ {+∞} là một song hàm.

Bài toán hiệu chỉnh được xây dựng bằng cách thay song hàm ban đầu bằng song hàm fε := f + εg, trong đó ε, g lần lượt là tham số hiệu chỉnh và song hàm hiệu chỉnh, thông thường ta chọn g là một song hàm đơn điệu mạnh. Nếu f là một song hàm đơn điệu thì fε là đơn điệu mạnh, khi đó bài toán hiệu chỉnh luôn có duy nhất nghiệm. Tuy nhiên, nếu f là một song hàm giả đơn điệu thì bài toán hiệu chỉnh trong trường hợp tổng quát không còn là đơn điệu mạnh hay đơn điệu, thậm chí không là giả đơn điệu do đó bài toán hiệu chỉnh nói chung không có nghiệm duy nhất, thậm chí tập nghiệm là không lồi, khi đó không thể áp dụng trực tiếp các phương pháp để hiệu chỉnh cho bài toán EP(C, f ) giả đơn điệu như trong trường hợp đơn điệu. Do đó, luận văn nghiên cứu và trình bày một số phương pháp hiệu chỉnh cho bài toán cân bằng giả đơn điệu và thông qua bài toán tối ưu hai cấp để tìm điểm giới hạn của các quỹ đạo nghiệm hiệu chỉnh.

Dựa trên ý tưởng của phương pháp hiệu chỉnh Tikhonov, trong [4] các tác giả đã

đưa ra phương pháp hiệu chỉnh với bài toán hiệu chỉnh như sau

(cid:26)Tìm x ∈ C sao cho

fk(x, y) := f (x, y) + εkg(x, y) ≥ 0 với mọi y ∈ C,

trong đó εk > 0 là tham số hiệu chỉnh, g(x, y) là một song hàm đơn điệu mạnh gọi là song hàm hiệu chỉnh.

MỞ ĐẦU

Năm 1970 Martine đưa ra phương pháp điểm gần kề cho bài toán bất đẳng thức biến phân đơn điệu và sau này được mở rộng bởi Rockafellar (1976) cho toán tử đơn điệu cực đaị. Bài toán hiệu chỉnh có dạng

(cid:26)Tìm xk ∈ C sao cho

fk(xk, y) := f (xk, y) + ck(cid:104)xk − xk−1, y − xk(cid:105) ≥ −δk với mọi y ∈ C,

trong đó ck > 0, δk > 0 lần lượt là các tham số hiệu chỉnh và sai số cho trước. Sự khác biệt giữa hai phương pháp này là ở phương pháp hiệu chỉnh điểm gần kề tại mỗi bước lặp bài toán hiệu chỉnh phụ thuộc vào điểm lặp ở bước trước và tham số hiệu chỉnh ck (cid:54)→ 0 khi k → ∞.

• Chương 1: Kiến thức chuẩn bị.

• Chương 2: Bài toán cân bằng.

• Chương 3: Hiệu chỉnh dựa trên tối ưu hai cấp.

Nội dung của luận văn gồm ba chương

Chương 1 trình bày một số kiến thức cơ sở như không gian tuyến tính, không gian Hilbert; các kiến thức về giải tích lồi như tập lồi, nón lồi, hàm lồi; các khái niệm về sự hội tụ yếu, hội tụ mạnh, hàm nửa liên tục trên, nửa liên tục dưới.

Chương 2 phát biểu bài toán cân bằng, một số trường hợp có thể đưa về bài toán

cân bằng và sự tồn tại nghiệm của bài toán.

Chương 3 trình bày phương pháp hiệu chỉnh bài toán cân bằng giả đơn điệu, thuật

toán tiếp cận dựa trên bài toán tối ưu hai cấp và sự hội tụ của thuật toán.

Mặc dù đã có nhiều cố gắng, song do thời gian và trình độ còn hạn chế nên luận văn khó tránh khỏi những thiếu sót. Vì vậy em rất mong nhận được sự góp ý của các thầy cô và các bạn để luận văn được hoàn thiện hơn.

Hà Nội, ngày 28 tháng 09 năm 2015

Tác giả

Nguyễn Thị Thanh Hải

Chương 1

Kiến thức chuẩn bị

Chương này chúng ta nhắc lại một số kiến thức về không gian tuyến tính, không gian Hilbert, tập lồi, nón lồi, hàm lồi; các khái niệm về sự hội tụ yếu, hội tụ mạnh, hàm nửa liên tục trên, nửa liên tục dưới. Các kiến thức này được lấy ra từ các tài liệu [1], [2].

1.1 Không gian Hilbert

1.1.1 Không gian tuyến tính định chuẩn.

Định nghĩa 1.1.1. Cho X là một không gian tuyến tính thực. Một chuẩn trên X, kí hiệu là (cid:107).(cid:107), là một ánh xạ

(cid:107).(cid:107) : X → R

thỏa mãn các tính chất sau

1. (cid:107)x(cid:107) ≥ 0, ∀x ∈ X; (cid:107)x(cid:107) = 0 ⇔ x = 0;

2. (cid:107)αx(cid:107) = |α|(cid:107)x(cid:107), ∀x ∈ X, α ∈ R;

3. (cid:107)x + y(cid:107) ≤ (cid:107)x(cid:107) + (cid:107)y(cid:107), ∀x, y ∈ X.

Khi đó (X, (cid:107).(cid:107)) được gọi là không gian tuyến tính định chuẩn.

Định nghĩa 1.1.2. Cho X là không gian tuyến tính thực, X được gọi là không gian tiền Hilbert nếu với mọi x, y ∈ X, xác định một tích vô hướng, kí hiệu là (cid:104)x, y(cid:105), thỏa mãn các tính chất

1. (cid:104)x, y(cid:105) = (cid:104)y, x(cid:105), ∀x, y ∈ X;

2. (cid:104)x + y, z(cid:105) = (cid:104)x, z(cid:105) + (cid:104)y, z(cid:105), ∀x, y, z ∈ X;

3. (cid:104)αx, y(cid:105) = α(cid:104)x, y(cid:105), ∀x, y ∈ X, α ∈ R;

4. (cid:104)x, x(cid:105) ≥ 0, ∀x ∈ X; (cid:104)x, x(cid:105) = 0 ⇔ x = 0.

Chương 1. Kiến thức chuẩn bị

1.1.2 Không gian Hilbert

Bổ đề 1.1.1. Mọi không gian tiền Hilbert X là không gian tuyến tính định chuẩn, với chuẩn được xác định như sau

(cid:107)x(cid:107) = (cid:112)(cid:104)x, x(cid:105), ∀x ∈ X.

Định nghĩa 1.1.3. Cho X là không gian định chuẩn. Dãy {xn} ⊆ X được gọi là dãy cơ bản trong X nếu

(cid:107)xn − xm(cid:107) = 0. lim n,m→∞

Nếu trong X, mọi dãy cơ bản đều hội tụ, tức là (cid:107)xn − xm(cid:107) → 0 kéo theo sự tồn tại

xo ∈ X sao cho xn → xo thì X được gọi là không gian đủ.

Định nghĩa 1.1.4. Không gian tiền Hilbert và đủ được gọi là không gian Hilbert.

Trong luận văn này ta thống nhất kí hiệu H là một không gian Hilbert trên trường

số thực.

Ví dụ 1.1.1.

Lấy H = Rnvới tích vô hướng xác định bởi hệ thức

xiyi. (cid:104)x, y(cid:105) = ∑ i=1→n

Trong đó x = (x1, x2, ..., xn), y = (y1, y2, ..., yn) ∈ Rn. Khi đó H là một không gian Hilbert.

Trên H có hai kiểu hội tụ sau

Định nghĩa 1.1.5. Xét dãy {xn}n≥0 và x thuộc không gian Hilbert thực H . Dãy {xn} được gọi là hội tụ mạnh đến x, kí hiệu là xn → x nếu

(cid:107)xn − x(cid:107) = 0. lim n→+∞

Dãy {xn} được gọi là hội tụ yếu đến x, kí hiệu là xn (cid:42) x nếu

(cid:104)w, xn(cid:105) = (cid:104)w, x(cid:105), ∀w ∈ H . lim n→+∞

Điểm x được gọi là điểm tụ mạnh (hay yếu) của dãy {xn} nếu từ dãy này có thể trích ra một dãy con hội tụ mạnh (hay yếu) tới x.

Mệnh đề 1.1.1. 1. Nếu {xn} hội tụ mạnh đến x thì cũng hội tụ yếu đến x.

2. Nếu {xn} hội tụ yếu đến x và limn→+∞ (cid:107)xn(cid:107) = (cid:107)x(cid:107) thì {xn} hội tụ mạnh đến x.

Chương 1. Kiến thức chuẩn bị

3. Mọi dãy hội tụ mạnh (yếu) đều bị chặn và giới hạn theo sự hội tụ mạnh (yếu)

nếu tồn tại là duy nhất.

4. Nếu H là không gian Hilbert hữu hạn chiều thì sự hội tụ mạnh và hội tụ yếu là

tương đương.

5. Nếu {xn} là dãy bị chặn trong không gian Hilbert H thì ta luôn trích ra được

một dãy con hội tụ yếu.

6. Nếu {xn} là dãy bị chặn trong không gian Hilbert hữu hạn chiều H thì ta luôn

trích ra được một dãy con hội tụ mạnh.

1.2 Tập lồi, nón lồi, hàm lồi

1.2.1 Tập lồi

Định nghĩa 1.2.1. Một tập C ⊆ H được gọi là một tập lồi nếu C chứa mọi đoạn thẳng đi qua hai điểm bất kỳ của nó. Tức là C lồi khi và chỉ khi

∀x, y ∈ C, ∀λ ∈ [0, 1] ⇒ λ x + (1 − λ )y ∈ C.

Mệnh đề 1.2.1. Tập hợp C là lồi khi và chỉ khi nó chứa mọi tổ hợp lồi của các điểm của nó. Tức là, C lồi khi và chỉ khi

k ∑ j=1

(1.1) λ j = 1, ∀x1, ..., xk ∈ C ⇒ λ jx j ∈ C. ∀k ∈ N, ∀λ1, λ2, ..., λk ≥ 0 :

Chứng minh.

Ta thấy, điều kiện đủ được suy ra trực tiếp từ định nghĩa. Ta chứng minh điều kiện cần bằng quy nạp. Với k = 2 công thức (1.1) tương đương với chứng minh C lồi khi và chỉ khi

∀λ1, λ2 ≥ 0 : λ1 + λ2 = 1, ∀x1, x2 ∈ C ⇒ λ1x1 + λ2x2 ∈ C.

Điều này suy ra trực tiếp từ định nghĩa của tập lồi và tổ hợp lồi. Giả sử mệnh đề đúng với (k − 1) điểm. Ta cần chứng minh đúng với k điểm.

Giả sử x là tổ hợp lồi của k điểm x1, ..., xk ∈ C. Tức là

k ∑ j=1

x = λ jx j, λ j ≥ 0, ∀ j = 1, 2, ..., k, λ j = 1.

Đặt

k−1 ∑ j=1

ξ = λ j.

Chương 1. Kiến thức chuẩn bị

Khi đó 0 < ξ < 1 và

k−1 ∑ j=1

x = λ jx j + λkxk = ξ x j + λkxk. λ j ξ

k−1 ∑ j=1

= 1 λ j ξ

ξ > 0 với mọi j = 1, 2, ..., k − 1, nên theo giả thiết quy nạp, điểm

và λ j

k ∑ j=1

x j ∈ C. y := λ j ξ

Ta có

x = ξ y + λkxk.

Do ξ > 0, λk > 0 và

k ∑ j=1

λ j = 1 ξ + λk =

(cid:3) nên x là tổ hợp lồi của hai điểm y và xk đều thuộc C. Vậy x ∈ C.

1.2.2 Nón lồi

Định nghĩa 1.2.2. Tập C được gọi là nón nếu với mọi λ > 0 và với mọi x ∈ C suy ra λ x ∈ C. Một nón được gọi là nón lồi nếu nó đồng thời là một tập lồi.

Mệnh đề 1.2.2. Một tập C là nón lồi khi và chỉ khi có các tính chất sau

1. λC ⊆ C ∀λ > 0;

2. C +C ⊆ C.

Chứng minh.

2(x + y) ∈ C. Vậy theo 1) ta có x + y ∈ C. Ngược lại, giả sử ta có 1) và 2). Từ 1) ta suy ra C là một nón.

Giả sử C là một nón lồi. Do C là một nón nên ta có 1). Mặt khác, do C là một tập lồi nên với mọi x, y ∈ C thì 1

Giả sử x, y ∈ C và λ ∈ [0, 1]. Từ 1) suy ra λ x ∈ C và (1 − λ )y ∈ C. Vậy C là một nón (cid:3) lồi.

Định nghĩa 1.2.3. Cho C ⊆ H là một tập lồi khác rỗng và x ∈ C. Khi đó tập

NC{x} := {w|(cid:10)w, y − x(cid:11) ≤ 0 ∀y ∈ C}

Chương 1. Kiến thức chuẩn bị

được gọi là nón pháp tuyến ngoài của C tại x. Tập

−NC{x} := {w|(cid:10)w, y − x(cid:11) ≤ 0 ∀y ∈ C}

được gọi là nón pháp tuyến trong của C tại x.

Định nghĩa 1.2.4. Cho C (cid:54)= /0 (không nhất thiết lồi) và y là một vectơ bất kỳ, đặt

(cid:107)x − y(cid:107). dC(y) := inf x∈C

Ta nói dC(y) là khoảng cách từ y đến C.

Nếu tồn tại π ∈ C sao cho dC(y) = (cid:107)π − y(cid:107), thì ta nói π là hình chiếu của y trên C,

kí hiệu pC(y).

Theo định nghĩa trên ta thấy rằng, hình chiếu pC(y) của y trên C sẽ là nghiệm của

bài toán tối ưu

(cid:107)x − y(cid:107)2|x ∈ C}. { min x 1 2

1.2.3 Hàm lồi

Định nghĩa 1.2.5. Cho C ⊆ H là một tập lồi và f : C → R ∪ {+∞}. Khi đó tập

dom f := {x ∈ C| f (x) < +∞}

được gọi là miền hữu dụng của tập f. Tập

epi f := {(x, µ) ∈ C × R | f (x) ≤ µ}

được gọi là trên đồ thị của hàm f.

1. Cho /0 (cid:54)= C ⊆ H lồi và f : C → R ∪ {+∞}. Ta nói f là hàm

Định nghĩa 1.2.6. lồi trên C nếu

f (cid:0)λ x + (1 − λ )y(cid:1) ≤ λ f (x) + (1 − λ ) f (y) ∀x, y ∈ C, ∀λ ∈ [0, 1].

2. Hàm f : H → R ∪ {+∞} được gọi là lồi chặt trên C nếu

f (cid:0)λ x + (1 − λ )y(cid:1) < λ f (x) + (1 − λ ) f (y) ∀x, y ∈ C, ∀λ ∈ (0, 1).

3. Hàm f : H → R ∪ {+∞} được gọi là lồi mạnh trên C với hệ số η nếu với mọi

x, y ∈ C và với mọi λ ∈ (0, 1)

f (cid:0)λ x + (1 − λ )y(cid:1) ≤ λ f (x) + (1 − λ ) f (y) − ηλ (1 − λ )(cid:107)x − y(cid:107)2. 1 2

Chương 1. Kiến thức chuẩn bị

4. Hàm f được gọi là hàm lõm trên C nếu − f là hàm lồi trên C.

Định nghĩa 1.2.7. Một hàm số thực ϕ được gọi là tựa lồi trên một tập lồi C nếu với mọi số thực γ tập mức dưới

{x ∈ C|ϕ(x) ≤ γ}

lồi. Tương tự hàm ϕ được gọi là tựa lõm trên C nếu −ϕ là hàm tựa lồi trên C.

Nhận thấy nếu ϕ là tựa lồi trên C thì với mọi x, y ∈ C và λ ∈ [0, 1] ta có

ϕ(λ x + (1 − λ )y) ≤ max(ϕ(x), ϕ(y)).

Tương tự nếu ϕ là tựa lõm trên C thì với mọi x, y ∈ C và λ ∈ [0, 1] ta có

ϕ(λ x + (1 − λ )y) ≥ min(ϕ(x), ϕ(y)).

Từ định nghĩa ta thấy, mọi hàm lồi (lõm) trên C, đều tựa lồi (tựa lõm) trên C.

Định nghĩa 1.2.8. Cho f là một hàm lồi trên tập lồi A. Một véc tơ y∗ ∈ H được gọi là dưới vi phân của f tại x∗ ∈ A nếu

f (x) ≥ f (x∗) + (cid:104)y∗, x − x∗(cid:105), ∀x ∈ A.

Tập hợp tất cả các điểm y∗ thỏa mãn bất đẳng thức trên được kí hiệu là ∂ f (x∗).

Định nghĩa 1.2.9. Hàm f : H → R ∪ {+∞} được gọi là nửa liên tục dưới đối với E tại một điểm x nếu như với mọi dãy {xn} ⊂ E, xk → x ta có lim in f f (xk) ≥ f (x).

Hàm f : H → R ∪ {+∞} được gọi là nửa liên tục trên đối với E tại một điểm x

nếu như với mọi dãy {xn} ⊂ E, xk → x ta có lim sup f (xk) ≤ f (x).

Hàm f được gọi là nửa liên tục dưới (nửa liên tục trên) đối với E trong tập A nếu

nó nửa liên tục dưới (nửa liên tục trên) đối với E tại mọi điểm thuộc A.

Nhận xét Nếu f là nửa liên tục dưới thì − f là nửa liên tục trên. Khi f liên tục (nửa liên tục) tại một điểm x, đối với toàn không gian, thì ta nói đơn

giản f liên tục (nửa liên tục) tại x.

1.2.4 Tính chất của hàm lồi

Mệnh đề 1.2.3. Một hàm f : C → R ∪ {+∞} là lồi trên C khi và chỉ khi

∀x, y ∈ C, ∀α > f (x), ∀β > f (y), ∀λ ∈ [0, 1]

⇒ f (λ x + (1 − λ )y) ≤ λ α + (1 − λ )β .

Chương 1. Kiến thức chuẩn bị

Chứng minh.

Điều kiện cần. Giả sử f lồi. Chọn x, y, α, β thỏa mãn các giả thiết của mệnh đề. Chọn α (cid:48) ∈ ( f (x), α) và β (cid:48) ∈ ( f (y), β ). Vậy (x, α (cid:48)) và (y, β (cid:48)) thuộc epi f . Do epi f lồi, nên

((1 − λ )x + λ y, (1 − λ )α (cid:48) + λ β (cid:48)) ∈ epi f .

Do đó

f ((1 − λ )x + λ y) ≤ (1 − λ )α (cid:48) + λ β (cid:48) < (1 − λ )α + λ β .

Điều kiện đủ. Chọn (x, µ) và (y, υ) thuộc epi f và λ ∈ (0, 1). Khi đó, với mọi ε > 0, ta có

f (x) < µ + ε, f (y) < υ + ε.

Do đó

f [(1 − λ )α (cid:48) + λ β (cid:48)] < (1 − λ )(µ + ε) + λ (υ + ε),

= (1 − λ )µ + λ υ + ε.

Điều này đúng với mọi ε > 0, nên cho ε → 0, ta được

f [(1 − λ )α (cid:48)] ≤ (1 − λ )µ + λ υ.

Chứng tỏ

(1 − λ )(x, µ) + λ (y, υ) ∈ epi f .

(cid:3) Vậy f lồi.

1.3 Kết luận

Chương 1 đã trình bày một số kiến thức chuẩn bị cho nội dung chính của luận văn. Các kiến thức về giải tích hàm như không gian tuyến tính định chuẩn, không gian tiền Hilbert, không gian Hilbert; sự hội tụ mạnh, hội tụ yếu trong không gian Hilbert. Các kiến thức về giải tích lồi như tập lồi, nón lồi, hàm lồi, hàm lồi chặt, hàm lồi mạnh với hệ số η; các tính chất của hàm lồi; khái niệm về hàm nửa liên tục trên, nửa liên tục dưới.

Chương 2

Bài toán cân bằng

Chương này chúng ta nhắc lại các khái niệm về song hàm cân bằng, toán tử cân bằng và phát biểu bài toán cân bằng. Một số bài toán có thể đưa về dạng bài toán cân bằng và sự tồn tại nghiệm của bài toán. Các kiến thức này được tham khảo từ các tài liệu [2], [3].

2.1 Bài toán cân bằng và các khái niệm

Trong kinh tế và nhiều lĩnh vực khác bài toán cân bằng có nhiều ý nghĩa quan trọng. Hơn nữa, bài toán là sự mở rộng của nhiều bài toán khác như bài toán tối ưu, bài toán bất đẳng thức biến phân, bài toán cân bằng Nash, bài toán điểm yên ngựa,... Vì vậy mà lớp các bài toán cân bằng được nhiều nhà toán học quan tâm, nghiên cứu.

2.1.1 Phát biểu bài toán

Định nghĩa 2.1.1. Giả sử C ⊆ H là một tập lồi, đóng, khác rỗng và f : H × H → R ∪ {+∞} thỏa mãn f (x, x) = 0 với mọi x ∈ C. Khi đó ta gọi hàm f là một song hàm cân bằng trên C.

Cho f là một song hàm cân bằng trên C. Ta xét bài toán

Tìm x∗ ∈ C sao cho f (x∗, y) ≥ 0, ∀y ∈ C. (EP(C, f ))

Ta kí hiệu bài toán này là EP(C, f ) và gọi là bài toán cân bằng, tập nghiệm của nó được kí hiệu là S(C, f ).

2.1.2 Các khái niệm

Định nghĩa 2.1.2. Song hàm f : H × H → R ∪ {+∞} được gọi là

Chương 2. Bài toán cân bằng

1. đơn điệu mạnh trên C với hệ số γ > 0 nếu

f (x, y) + f (y, x) ≤ −γ(cid:107)x − y(cid:107)2, ∀x, y ∈ C;

2. đơn điệu trên C nếu

f (x, y) + f (y, x) ≤ 0, ∀x, y ∈ C;

3. giả đơn điệu trên C nếu

f (x, y) ≥ 0 ⇒ f (y, x) ≤ 0, ∀x, y ∈ C.

Từ định nghĩa trên ta suy ra: 1) ⇒ 2) ⇒ 3).

Điều ngược lại chưa chắc đã đúng.Thật vậy, để làm rõ vấn đề này ta xét một số ví

dụ sau.

Ví dụ 2.1.1.

Xét song hàm

f (x, y) = ε(cid:104)x, y − x(cid:105), ∀x, y ∈ H ,

trong đó ε > 0. Với hằng số γ > 0 nào đó thỏa mãn γ ≤ ε ta có

f (x, y) + f (y, x) = ε(cid:104)x, y − x(cid:105) + ε(cid:104)y, x − y(cid:105);

= ε(cid:104)−x + y, x − y(cid:105); = −ε(cid:107)x − y(cid:107)2 ≤ −γ(cid:107)x − y(cid:107)2.

Chứng tỏ f là song hàm đơn điệu mạnh trên H . Do γ > 0 nên từ đẳng thức

f (x, y) + f (y, x) ≤ −γ(cid:107)x − y(cid:107)2

ta suy ra

f (x, y) + f (y, x) ≤ 0 ∀x, y ∈ H ,

chứng tỏ f là đơn điệu trên H . Giả sử f (x, y) ≥ 0 với mọi x, y ∈ H . Khi đó, do

f (x, y) + f (y, x) ≤ 0,

suy ra

f (y, x) ≤ − f (x, y) ≤ 0, ∀x, y ∈ H .

Vậy f là song hàm giả đơn điệu.

Chương 2. Bài toán cân bằng

Ví dụ 2.1.2.

Xét song hàm

f (x, y) = (x2 + 1)(y − x), ∀x, y ∈ R.

Giả sử f (x, y) ≥ 0 với mọi x, y ∈ R, suy ra y ≥ x với mọi x, y ∈ R. Khi đó

f (y, x) = (y2 + 1)(x − y) ≤ 0, ∀x, y ∈ R.

Vậy f là song hàm giả đơn điệu. Tuy nhiên

f (x, y) + f (y, x) = (x2 + 1)(y − x) + (y2 + 1)(x − y); = −(x − y)2(x + y).

Khi đó, nếu chọn x, y ∈ R sao cho x (cid:54)= y và x + y < 0 thì f (x, y) + f (y, x) > 0, nghĩa là f không đơn điệu trên R.

Ví dụ 2.1.3.

Cho không gian Hilbert thực

∞ ∑ i=1

|xi|2 < +∞, ∀xi ∈ R(cid:9). H = l2 := (cid:8)x = (x1, x2, ..., xi, ...) :=

Tích vô hướng và chuẩn trên H tương ứng được xác định bởi

∞ ∑ i=1

(cid:104)x, y(cid:105) := (cid:107)x(cid:107) := (cid:112)(cid:104)x, x(cid:105) xiyi,

y = (y1, y2, ..., yi, ...) = (y1, (cid:98)y) ∈ H , với mọi x = (x1, x2, ..., xi, ...) = (x1, (cid:98)x) ∈ H , trong đó

(cid:98)x := (x2, ..., xi, ...), (cid:98)y := (y2, ..., yi, ...).

Kí hiệu

∞ ∑ i=2

xiyi, (cid:107)(cid:98)x(cid:107) := (cid:112)(cid:104)(cid:98)x, (cid:98)x(cid:105).

(cid:104)(cid:98)x, (cid:98)y(cid:105) := √ Xét tập C = {x ∈ H : (cid:107)x(cid:107) ≤ 2} và hàm f : C ×C → R được cho bởi

f (x, y) = (2 − (cid:107)(cid:98)x(cid:107))(cid:104)(cid:98)x, (cid:98)y − (cid:98)x(cid:105).

Nhận thấy, tập nghiệm của bài toán EP(C, f ) là

(cid:101)C := S(C, f ) = {(x1, 0, ..., 0, ...) : x1 ∈ R)}.

Chương 2. Bài toán cân bằng

Với x, y ∈ C ta có 2 − (cid:107)(cid:98)x(cid:107) > 0 và 2 − (cid:107)(cid:98)y(cid:107) > 0. Do đó

f (x, y) = (2 − (cid:107)(cid:98)x(cid:107))(cid:104)(cid:98)x, (cid:98)y − (cid:98)x(cid:105) ≥ 0; ⇒ (cid:104)(cid:98)x, (cid:98)y − (cid:98)x(cid:105) ≥ 0; ⇒ (cid:104)(cid:98)y, (cid:98)x − (cid:98)y(cid:105) ≤ 0; ⇒ f (y, x) = (2 − (cid:107)(cid:98)y(cid:107))(cid:104)(cid:98)y, (cid:98)x − (cid:98)y(cid:105) ≤ 0.

√ y = (0, Chứng tỏ f là song hàm giả đơn điệu trên C. Lấy x = (0, 1, 0, ..., 0, ...),

2, 0, ..., 0, ...) ∈ C. Khi đó √ 2, 0, ..., 0, ...) (cid:98)x = (1, 0, ..., 0, ...), (cid:98)y = (

và √ 2. (cid:107)(cid:98)x(cid:107) = 1, (cid:107)(cid:98)y(cid:107) =

Nhận thấy

√ √ √ √ f (x, y) + f (y, x) = (2 − 1) × 1 × ( 2 − 1) + (2 − 2) × 2 × (1 − 2) √ √ = ( 2 − 1) × (2 2 − 1) > 0.

Vậy, f không đơn điệu trên C.

Định nghĩa 2.1.3. Cho C ⊂ H . Toán tử F : C → H được gọi là

1. đơn điệu mạnh trên C với hệ số γ > 0 nếu

(cid:104)F(x) − F(y), x − y(cid:105) ≥ γ(cid:107)x − y(cid:107)2, ∀x, y ∈ C;

2. đơn điệu trên C nếu

(cid:104)F(x) − F(y), x − y(cid:105) ≥ 0, ∀x, y ∈ C;

3. giả đơn điệu trên C nếu

(cid:104)F(x), x − y(cid:105) ≤ 0 ⇒ (cid:104)F(y), y − x(cid:105) ≥ 0.

Ta đặt

f (x, y) = (cid:104)F(x), y − x(cid:105).

Khi đó toán tử cân bằng trở thành song hàm cân bằng.

Chương 2. Bài toán cân bằng

Nhận xét Nếu F là toán tử đơn điệu mạnh, đơn điệu hoặc giả đơn điệu trên C thì f cũng là

song hàm đơn điệu mạnh, đơn điệu hoặc giả đơn điệu trên C. Thật vậy Nếu toán tử F là đơn điệu mạnh trên C với hệ số γ > 0, khi đó

(cid:104)F(x) − F(y), x − y(cid:105) ≥ γ(cid:107)x − y(cid:107)2, ∀x, y ∈ C;

⇔ (cid:104)F(x), x − y(cid:105) − (cid:104)F(y), x − y(cid:105) ≥ γ(cid:107)x − y(cid:107)2, ∀x, y ∈ C;

⇔ −(cid:104)F(x), y − x(cid:105) − (cid:104)F(y), x − y(cid:105) ≥ γ(cid:107)x − y(cid:107)2, ∀x, y ∈ C;

⇔ − f (x, y) − f (y, x) ≥ γ(cid:107)x − y(cid:107)2, ∀x, y ∈ C;

⇔ f (x, y) + f (y, x) ≤ −γ(cid:107)x − y(cid:107)2, ∀x, y ∈ C;

Vậy f là song hàm đơn điệu mạnh trên C với hệ số γ > 0. Nếu toán tử F là đơn điệu trên C, khi đó

(cid:104)F(x) − F(y), x − y(cid:105) ≥ 0, ∀x, y ∈ C;

⇔ (cid:104)F(x), x − y(cid:105) − (cid:104)F(y), x − y(cid:105) ≥ 0, ∀x, y ∈ C;

⇔ −(cid:104)F(x), y − x(cid:105) − (cid:104)F(y), x − y(cid:105) ≥ 0, ∀x, y ∈ C;

⇔ − f (x, y) − f (y, x) ≥ 0, ∀x, y ∈ C;

⇔ f (x, y) + f (y, x) ≤ 0, ∀x, y ∈ C;

Vậy f là song hàm đơn điệu trên C. Nếu toán tử F là giả đơn điệu trên C, khi đó nếu

(cid:104)F(x), x − y(cid:105) ≤ 0 thì (cid:104)F(y), y − x(cid:105) ≥ 0, ∀x, y ∈ C;

⇔ −(cid:104)F(x), y − x(cid:105) ≤ 0 thì (cid:104)F(y), y − x(cid:105) ≥ 0, ∀x, y ∈ C;

⇔ −(cid:104)F(x), y − x(cid:105) ≤ 0 thì − (cid:104)F(y), x − y(cid:105) ≥ 0, ∀x, y ∈ C;

suy ra

− f (x, y) ≤ 0 thì − f (y, x) ≥ 0, ∀x, y ∈ C;

⇔ f (x, y) ≥ 0 thì f (y, x) ≤ 0 ∀x, y ∈ C.

Vậy f là song hàm giả đơn điệu trên C. Sau đây ta xét một vài trường hợp riêng có thể đưa về bài toán cân bằng.

Chương 2. Bài toán cân bằng

2.2 Các trường hợp riêng của bài toán cân bằng

2.2.1 Bài toán tối ưu

Cho hàm số ϕ : C → R. Xét bài toán tối ưu

(OP) Tìm x∗ ∈ C sao cho ϕ(x∗) ≤ ϕ(y), ∀y ∈ C.

Đặt

f (x, y) := ϕ(y) − ϕ(x).

Rõ ràng f (x, x) = ϕ(x) − ϕ(x) = 0. Vậy f là một song hàm cân bằng. Khi đó bài toán tối ưu (OP) tương đương với bài toán

Tìm x∗ ∈ C sao cho ϕ(y) − ϕ(x∗) ≥ 0, ∀y ∈ C

hay

Tìm x∗ ∈ C sao cho f (x∗, y) ≥ 0, ∀y ∈ C.

Đây chính là bài toán cân bằng. Nhận thấy, tập nghiệm của bài toán tối ưu (OP) chính là S(C, f ). Thật vậy, giả sử x∗ ∈ C là nghiệm của bài toán (OP), theo định nghĩa ta có

ϕ(x∗) ≤ ϕ(y), ∀y ∈ C.

Suy ra

ϕ(y) − ϕ(x∗) ≥ 0, ∀y ∈ C.

Mặt khác

f (x, y) := ϕ(y) − ϕ(x), ∀x, y ∈ C,

nên

f (x∗, y) := ϕ(y) − ϕ(x∗) ≥ 0, ∀y ∈ C.

Vậy x∗ là nghiệm cuả bài toán EP(C, f ). Ngược lại, lấy x∗ ∈ C là nghiệm của bài toán EP(C, f ). Khi đó f (x∗, y) ≥ 0 với mọi y ∈ C. Theo cách đặt ta có

f (x∗, y) := ϕ(y) − ϕ(x∗) ≥ 0, ∀y ∈ C.

Suy ra ϕ(y) ≥ ϕ(x∗), ∀y ∈ C. Vậy x∗ là nghiệm của bài toán (OP).

Chương 2. Bài toán cân bằng

2.2.2 Bài toán điểm bất động

Cho F : C → C là một ánh xạ đơn trị. Xét bài toán điểm bất động sau

Tìm x∗ sao cho F(x∗) = x∗. (F(C, F))

Đặt f (x, y) = (cid:104)x − F(x), y − x(cid:105), thì f là một song hàm cân bằng với mọi y ∈ C.

Khi đó bài toán điểm bất động F(C, F) trở thành bài toán EP(C, f ), tập nghiệm

của F(C, F) chính là S(C, f ).

Thật vậy, giả sử x∗ là nghiệm của bài toán F(C, F). Tức là F(x∗) = x∗. Khi đó

f (x∗, y) = (cid:104)x∗ − F(x∗), y − x∗(cid:105); = (cid:104)0, y − x∗(cid:105);

= 0 ≥ 0, ∀y ∈ C.

Vậy x∗ là nghiệm của bài toán cân bằng EP(C, f ).

Ngược lại, giả sử x∗ là điểm sao cho f (x∗, y) ≥ 0, ∀y ∈ C. Khi đó:

(cid:104)x∗ − F(x∗), y − x∗(cid:105) ≥ 0, ∀y ∈ C.

Chọn y = F(x∗)

(cid:104)x∗ − F(x∗), F(x∗) − x∗(cid:105) ≥ 0, ∀y ∈ C; ⇔ −||x∗ − F(x∗)||2 ≥ 0, ∀y ∈ C.

⇒ x∗ = F(x∗) ∀y ∈ C. Vậy x∗ là điểm bất động của C.

2.2.3 Bài toán cân bằng Nash trong trò chơi không hợp tác

Xét một trò chơi không hợp tác gồm có p đấu thủ, đấu thủ thứ i có tập chiến lược là Ci ∈ Rpi và có hàm chi phí là fi := C → R với C := C1 × C2 × ... × Cp tương ứng, tức là, nếu đối thủ thứ nhất, thứ hai, ..., thứ p, lần lượt chọn chiến lược chơi là x1 ∈ C1, x2 ∈ C2, ..., xp ∈ Cp , thì chi phí của mỗi đối thủ tương ứng sẽ là f1(x1, x2, ..., xp), f2(x1, x2, ..., xp), ..., f p(x1, x2, ..., xp). Mục tiêu của mỗi đối thủ là tìm kiếm một chiến lược chơi trong tập chiến lược chơi tương ứng để làm cực tiểu chi phí của mình. Ký hiệu x = (x1, x2, ..., xp), một điểm x∗ ∈ C được gọi là điểm cân bằng Nash nếu

i , x∗

p) ≤ fi(x∗

i , x∗

1, ..., x∗

i−1, x∗

i+1, ..., x∗

1, ..., x∗

i−1, y∗

i+1, ..., x∗ p)

fi(x∗

Chương 2. Bài toán cân bằng

i ∈ Ci và với mọi i = 1, 2, ..., p. Khi đó bài toán cân bằng Nash được phát

với mọi y∗ biểu như sau

p) ∀yi ∈ Ci, ∀i = 1, 2, ..., p.

i , x∗

i−1, y∗

i+1, ..., x∗

(N(C, f )) fi(x∗) ≤ fi(x∗ (cid:26) Tìm x∗ ∈ C sao cho 1, ..., x∗

Đặt

p ∑ j=1

f (x, y) := (cid:2) f j(x) − f j(x1, ..., x j−1, y j, x j+1, ..., xp)(cid:3).

Nhận thấy, nếu x∗ là một điểm cân bằng Nash thì f (x∗, y) ≥ 0 với mọi y ∈ C. Khi đó bài toán cân bằng Nash N(C, f ) trở thành bài toán cân bằng EP(C, f ).

p) với x∗

j ∈ C j là một điểm cân bằng Nash.

1, ..., x∗

Ngược lại, giả sử x∗ ∈ C là nghiệm của EP(C, f ) tức là f (x∗, y) ≥ 0 với mọi y ∈ C.

p) < f j(x∗

p).

1, ..., x∗

j−1, y j, x∗

j−1, x∗

1, ..., x∗

j+1, ..., x∗ p), theo định nghĩa của hàm f ta

j−1, y j, x∗

j+1, ..., x∗

j+1, ..., x∗ 1, ..., x∗

j, x∗ Khi đó với phương án y = (x∗ có

Ta sẽ chứng tỏ x∗ = (x∗ Thật vậy, giả sử x∗ không là một điểm cân bằng Nash, khi đó sẽ tồn tại j và một y j ∈ C j sao cho f j(x∗

p) − f j(x∗) < 0.

j+1, ..., x∗

1, ..., x∗

j−1, y j, x∗ Điều này mâu thuẫn với giả thiết x∗ là nghiệm của EP(C, f ), hay x∗ là một điểm cân bằng Nash.

f (x∗, y) = f j(x∗

2.2.4 Bài toán điểm yên ngựa

Trong nhiều vấn đề, ta thường phải làm việc việc với một hàm số thực của hai nhóm biến có tính chất là tựa lồi theo nhóm biến thứ nhất khi nhóm biến thứ hai cố định và tựa lõm theo nhóm biến thứ hai, khi nhóm biến thứ nhất cố định. Các song hàm này được gọi là hàm yên ngựa. Định nghĩa 2.2.1. Cho C ⊆ H , D ⊆ H là các tập lồi khác rỗng và ϕ : C × D → R. Hàm ϕ được gọi là hàm yên ngựa trên C × D, nếu với mọi y ∈ D cố định, hàm ϕ(., y) tựa lồi trên C và với mọi x ∈ C cố định, hàm ϕ(x, .) tựa lõm trên D.

Hột hàm yên ngựa cũng được gọi là hàm tựa - lồi tựa - lõm. Do mọi hàm lồi đều là tựa lồi và mọi hàm lõm đều là tựa lõm, nên hàm lồi - lõm (nói riêng hàm song tuyến) là hàm yên ngựa.

Định nghĩa 2.2.2. Một điểm (x∗, y∗) ∈ C × D được gọi là điểm yên ngựa của hàm ϕ trên C × D nếu

ϕ(x∗, y) ≤ ϕ(x∗, y∗) ≤ ϕ(x, y∗), ∀x ∈ C, ∀y ∈ D.

Chương 2. Bài toán cân bằng

Xét bài toán tìm điểm yên ngựa sau

(cid:26) Tìm điểm (x∗, y∗) ∈ C × D sao cho (2.2.1) ϕ(x∗, y) ≤ ϕ(x∗, y∗) ≤ ϕ(x, y∗), ∀x, y ∈ C × D.

Ta sẽ chỉ ra rằng, bài toán tìm điểm yên ngựa có thể mô tả dưới dạng bài toán cân bằng như sau. Với mỗi u = (x(cid:48), y(cid:48)), v = (x, y) ∈ K := C × D, đặt

f (u, v) := ϕ(x, y(cid:48)) − ϕ(x(cid:48), y).

Khi đó, nếu u∗ = (x∗, y∗) ∈ K là nghiệm của EP(K, f ), tức là

f (u∗, v) ≥ 0, ∀v ∈ K,

thì

ϕ(x∗, y) ≤ ϕ(x, y∗), ∀(x, y) ∈ K.

Lần lượt thay x = x∗, y = y∗ vào bất đẳng thức này ta được

ϕ(x∗, y) ≤ ϕ(x∗, y∗) ≤ ϕ(x, y∗), ∀(x, y) ∈ K.

Vậy (x∗, y∗) là điểm yên ngựa của ϕ trên K.

Ngược lại, giả sử (x∗, y∗) là điểm yên ngựa của ϕ trên K. Theo định nghĩa ta có

ϕ(x∗, y) ≤ ϕ(x∗, y∗) ≤ ϕ(x, y∗), ∀x ∈ C, ∀y ∈ D.

Suy ra

ϕ(x, y∗) − ϕ(x∗, y) ≥ 0 ∀x, y ∈ K,

hay

f (u∗, v) ≥ 0 ∀v ∈ K.

Vậy u∗ = (x∗, y∗) là nghiệm của EP(K, f ).

2.3 Sự tồn tại nghiệm của bài toán cân bằng

Trong mục này chúng ta sẽ xét tới sự tồn tại nghiệm của bài toán cân bằng trong các trường hợp compact và trường hợp có điều kiện bức. Trước hết chúng ta nhắc lại định lý cực đại Berge sau

Định lý 2.3.1. Cho X, Y là các không gian Tô pô, F : X ×Y → 2Y là ánh xạ nửa liên tục trên trên X sao cho F(x) compact, hơn nữa F(X) compact. Giả sử f : X ×Y → R là một hàm số nửa liên tục trên trên X. Khi đó, hàm giá trị tối ưu

g(x) := max{ f (x, y) : y ∈ F(x)}

Chương 2. Bài toán cân bằng

nửa liên tục trên và ánh xạ tập nghiệm tối ưu

S(x) := {y ∈ F(x) : f (x, y) = g(x)}

nửa liên tục trên.

Ta xét sự tồn tại nghiệm của bài toán cân bằng dựa trên các giả thiết sau đây

f (., y) là hàm nửa liên tục trên, yếu trên H đối với mỗi y ∈ C; f (x, .) là hàm lồi, nửa liên tục dưới yếu trên H và khả vi trên dom f (x, .) đối

Tồn taị một tập compact B ⊂ H và một vectơ y0 ∈ B ∩C sao cho Cho C ⊆ H là một tập lồi, đóng, khác rỗng và f : H × H → R ∪ {+∞} Giả thiết (A1) (A2) với mỗi x ∈ C; (A3)

f (x, y0) < 0 ∀x ∈ C \ B.

Giả thiết (A3) còn được gọi là điều kiện bức. Ta xét định lý sau.

Định lý 2.3.2. (Ky Fan’theorem). Giả sử C là một tập lồi đóng, khác rỗng trong không gian Hilbert H và f : C ×C → R ∪ {+∞} là một song hàm cân bằng xác định trên C. Nếu f thỏa mãn giả thiết A1 và f (x, .) là tựa lồi trên C với mỗi x ∈ C cố định. Khi đó nếu C là tập compact hoặc điều kiện bức (A3) được thỏa mãn thì bài toán EP(C, f ) có nghiệm.

Mệnh đề 2.3.1. 1. Nếu hàm f đơn điệu mạnh trên C và thỏa mãn các giả thiết

(A1), (A2), thì EP(C, f ) có nghiệm duy nhất.

2. Nếu hàm f thỏa mãn các giả thiết (A1), (A2) và giả đơn điệu trên C thì nghiệm

của EP(C, f ) là một tập lồi, đóng yếu.

3. Nếu hàm f thỏa mãn các giả thiết (A1), (A2) và (A3) thì tập nghiệm của EP(C, f )

là khác rỗng.

Mệnh đề 2.3.2. Giả sử f thỏa mãn các giả thiết (A1) và (A2). Xét các mệnh đề sau

1. Tồn tại một véctơ y0 ∈ C sao cho

L(y0, f ) := {x ∈ C : f (x, y0) ≥ 0}

là một tập bị chặn.

2. Tồn tại một hình cầu đóng B ⊆ H và một vectơ y0 ∈ C ∩ B sao cho

f (x, y0) < 0, ∀x ∈ C \ B.

Chương 2. Bài toán cân bằng

3. Tập nghiệm S(C, f ) của bài toán EP(C, f ) là khác rỗng và compact yếu.

Khi đó 1) ⇒ 2) ⇒ 3). Hơn nữa nếu f là giả đơn điệu trên C thì S(C, f ) là lồi và tập

L>(y0, f ) : {x ∈ C : f (x, y0) > 0}

là rỗng với mọi y0 ∈ S(C, f ).

Chứng minh.

1) ⇒ 2): Từ giả thiết 1), ta chọn B là hình cầu đóng chứa L(y0, f ). Khi đó

{x ∈ C \ B : f (x, y0) ≥ 0} = /0.

Vậy f (x, y0) < 0, ∀x ∈ C \ B.

2) ⇒ 3): Từ Mệnh đề 2.3.1 ta có S(C, f ) (cid:54)= /0 . Do C là tập đóng yếu, f (., y) là hàm nửa liên tục trên yếu trên C và tập nghiệm S(C, f ) là đóng yếu. Hơn nữa, từ 2) và từ định nghĩa của L(y0, f ), ta có

S(C, f ) ⊆ L(y0, f ) ⊆ C ∩ B.

Do đó, S(C, f ) là tập compact yếu. Lấy y0 ∈ S(C, f ). Khi đó f (y0, x) ≥ 0 với mọi x ∈ C. Do tính chất giả đơn điệu của (cid:3) song hàm nên f (x, y0) ≤ 0 với mọi x ∈ C. Do đó, L> = /0.

Mệnh đề 2.3.3. (Trường hợp compact) Cho C là một tập lồi, compact, khác rỗng và song hàm cân bằng f : C ×C → R ∪ +{∞} thỏa mãn các tính chất sau

1. f(.,y) nửa liên tục trên yếu trên H với mọi y ∈ C.

2. f(x,.) lồi, nửa liên tục dưới và khả dưới vi phân trên H với mọi x ∈ C.

Khi đó bài toán EP(C, f ) có nghiệm.

Chứng minh.

Với mỗi x ∈ C ta gọi S(x) là tập nghiệm của bài toán

min{ f (x, y) : y ∈ C}.

Do C là compact và f (, .) nửa liên tục dưới trên H nên bài toán này có nghiệm. Hơn nữa do C lồi, compact, f (x, .) lồi nên S(x) lồi, compact. Theo Định lý Berger thì ánh xạ S(.) nửa liên tục trên. Vậy, theo định lý về điểm bất động, tồn tại x∗ ∈ C thỏa mãn x∗ ∈ S(x∗). Ta sẽ chỉ ra x∗ là nghiệm của bài toán cân bằng EP(C, f ).

Chương 2. Bài toán cân bằng

Thật vậy, do f (x, .) lồi, khả dưới vi phân nên theo điều kiện cần và đủ tối ưu của

qui hoạch lồi ta có

0 ∈ ∂2 f (x∗, x∗) + NC(x∗),

theo định nghĩa của dưới vi phân và nón pháp tuyến ta có

∃v∗ ∈ ∂2 f (x∗, x∗) thỏa mãn (cid:104)v∗, y − x∗(cid:105) ≥ 0, ∀y ∈ C.

Do v∗ ∈ ∂2 f (x∗, x∗) nên

(cid:104)v∗, y − x∗(cid:105) ≤ f (x∗, y) − f (x∗, x∗) = f (x∗, y), ∀y ∈ C.

(cid:3) Vậy f (x∗, y) ≥ 0, ∀y ∈ C, hay x∗ là nghiệm của bài toán EP(C, f ).

Hệ quả 2.3.1. (Trường hợp có điều kiện bức).Cho C là một tập lồi, đóng (không cần compact) và song hàm cân bằng f thỏa mãn các điều kiện của Mệnh đề 2.3.3. Giả sử điều kiện bức (K1) sau đây được thỏa mãn. Tồn tại tập compact B sao cho

C ∩ B (cid:54)= ∅, ∀x ∈ C \ B, ∀y ∈ C : f (x, y) < 0.

Khi đó bài toán EP(C, f ) có nghiệm.

Chứng minh.

Theo Mệnh đề 2.3.3, bài toán EP(C, f ) trên tập C ∩ B với hàm cân bằng f có nghiệm, tức là tồn tại x∗ ∈ C ∩ B. Từ điều kiện bức (K1) và tính lồi của tập C ta có thể suy ra x∗ cũng là nghiệm của bài (cid:3) toán EP(C, f ).

Ngoài ra để chứng minh sự tồn tại nghiệm của bài toán cân bằng ta có thể dựa vào

Định lý minimax sau. Cho một song hàm f := C × D → R. Ta xét định lý sau (Định lý minimax).

Định lý 2.3.3. Cho C ⊆ H , D ⊆ H là các tập lồi, đóng khác rỗng và f : C × D → R. Giả sử với mọi y ∈ D, hàm f (., y) là hàm tựa lồi, nửa liên tục dưới trên C và với mọi x ∈ C, hàm f (x, .) là hàm tựa lõm, nửa liên tục trên trên D. Khi đó nếu có một trong hai điều kiện sau

(A) Có một tập hữu hạn N∗ ⊂ D và một số η∗ > γ sao cho tập

f (x, y) ≤ η∗} C(N∗) := {x ∈ C| max y∈N∗

compact.

Chương 2. Bài toán cân bằng

(B) Có một tập hữu hạn M∗ ⊂ C và một số γ∗ < η sao cho tập

f (x, y) ≥ γ∗} D(M∗) := {y ∈ D| min x∈M∗

compact. Khi đó

f (x, y). inf x∈C f (x, y) = inf x∈C sup y∈D sup y∈D

Cụ thể hơn, ta có

f (x, y) f (x, y) = inf x∈C min x∈C(N∗) sup y∈D sup y∈D

nếu có (A) và

y∈D(M∗))

f (x, y) f (x, y) = max inf x∈C inf x∈C sup y∈D

nếu có (B).

Để chứng minh Định lý minimax, ta xét bổ đề sau

Bổ đề 2.3.1. Cho C ⊆ H , D ⊆ H là các tập lồi, đóng khác rỗng và f : C × D → R. Giả sử với mọi y ∈ D, hàm f (., y) tựa lồi, nửa liên tục dưới trên C và với mọi x ∈ C, hàm f (x, .) tựa lõm, nửa liên tục trên trên D. Khi đó ta có

1. Với mọi γ (cid:48) > γ := supy∈D infx∈C f (x, y) và mọi tập hữu hạn N ⊂ D, tập

f (x, y) ≤ γ (cid:48)} (cid:54)= ∅. C(N) := {x ∈ C| max y∈N

2. Với mọi η (cid:48) < η = infx∈C supy∈D f (x, y) và mọi tập hữu hạn M ⊂ C, tập

f (x, y) ≥ η (cid:48)} (cid:54)= ∅. D(M) := {y ∈ D| min x∈M

Chứng minh.

γ(y) := {x ∈ C| f (x, y) ≤ γ (cid:48)}. C(cid:48)

γ(y) lồi đóng. Ta chứng minh 1) γ(y) (cid:54)= ∅). C(cid:48)

1. Đặt

Do C lồi, f (., y) tựa lồi và nửa liên tục dưới, nên C(cid:48) bằng qui nạp theo số phần tử của N (khẳng định 1) có nghĩa là (cid:84) y∈N

γ(y) = {x ∈ C| f (x, y) ≤ γ (cid:48)}.

γ(N) = C(cid:48) C(cid:48)

Khi N chỉ có duy nhất một phần tử y, tập

f (x, y), γ (cid:48) > γ ≥ inf x∈C

Chương 2. Bài toán cân bằng

suy ra

γ(N) (cid:54)= ∅.

∃ x ∈ C sao cho f (x, y) ≤ γ (cid:48).

Suy ra C(cid:48) Vậy 1) đúng khi N có một phần tử.

Giả sử 1) đúng với N có k phần tử.

k (cid:92)

γ (cid:48)(yi) (cid:54)= ∅, C(cid:48)

i=1

Tức là

k+1 (cid:92)

γ (cid:48)(yi) (cid:54)= ∅, C(cid:48)

i=1

ta chứng minh (i) đúng khi N có k + 1 phần tử. tức là chứng minh

trong đó N := {y1, ..., yk, yk+1}. Thật vậy, Đặt

γ (cid:48)(yi) := Cγ (cid:48)(yi) ∩Cγ (cid:48)(yk+1) C(cid:48)

(i = 1, ..., k).

k+1 (cid:92)

k (cid:92)

Khi đó

γ (cid:48)(yi). C(cid:48)

i=1

Cγ (cid:48)(yi) =

γ (cid:48)(yi) (cid:54)= ∅, nếu như các tập C(cid:48)

k (cid:84) i=1

γ (cid:48)(yi) = Cγ (cid:48)(yi) ∩Cγ (cid:48)(yk+1) (cid:54)= ∅. C(cid:48)

Theo giả thiết qui nạp

Ta chứng minh với hai điểm bất kỳ a, b ∈ D, thì Cγ (cid:48)(a) ∩Cγ (cid:48)(b) (cid:54)= ∅.

Giả sử ngược lại, tồn tại hai điểm a, b ∈ D sao cho Cγ (cid:48)(a) ∩Cγ (cid:48)(b) = ∅.

f (x, y), nên Cα(y) (cid:54)= ∅, ∀y ∈ D. inf x∈C Lấy α ∈ (γ, γ (cid:48)) bất kỳ. Khi đó γ < α < γ (cid:48) suy ra α > sup y∈D

Lấy yt := ta + (1 − t)b với 0 ≤ t ≤ 1. Do D lồi, nên yt ∈ D.

Với mọi x ∈ Cα(yt) ta có f (x, yt) ≤ α. Do f là tựa lõm theo biến thứ hai, nên f (x, yt) ≥ min{ f (x, a), f (x, b)}.

Vậy min{ f (x, a), f (x, b)} ≤ α.

Do đó

f (x, a) ≤ α hoặc f (x, b) ≤ α ∀x ∈ Cα(yt),

Chương 2. Bài toán cân bằng

suy ra

Cα(yt) ⊂ Cα(a) ∪Cα(b). Do Cα(a),Cα(b),Cα(yt) lồi và Cα(a) ∩Cα(b) = ∅ nên

Cα(yt) ⊂ Cα(a) hoặc Cα(yt) ⊂ Cα(b).

Đặt

Ma := {t|0 ≤ t ≤ 1 : Cα(yt) ⊂ Cα(a)};

Mb := {t|0 ≤ t ≤ 1 : Cα(yt) ⊂ Cα(b)}.

Khi đó

0 ∈ Ma, 1 ∈ Mb và Ma ∪ Mb = [0, 1].

Tương tự, ta có

Cα(yt) ⊂ Cα(yt1) ∪Cα(yt2), ∀t ∈ [t1,t2] ⊂ [0, 1].

Nhận thấy

t ∈ Ma ⇒ [0,t] ∈ Ma và t ∈ Mb ⇒ [t, 1] ∈ Mb.

Đặt s := sup Ma. Giả sử s ∈ Ma.

Do α > γ ≥ inf f (x, ys), nên tồn tại x ∈ C sao cho f (x, ys) < α. Do tính nửa liên tục trên của f (x, .) nên f (x, ys) < α với mọi t > s và đủ gần s. Hay x ∈ Cα(yt) với mọi t đủ gần s. Khi đó Cα(yt) ⊂ Cα(a). Theo định nghĩa của Ma, ta có t ∈ Ma. Tuy nhiên, t > s = sup Ma, điều này mâu thuẫn, Vậy Cα(a) ∩Cα(b) (cid:54)= ∅. Hay

f (x, y) ≤ γ (cid:48)} (cid:54)= ∅. C(N) := {x ∈ C| max y∈N

2. Do hàm f là tựa lõm và nửa liên tục trên theo biến thứ hai nên − f là tựa lồi và

nửa liên tục dưới theo biến thứ hai và

(− f (x, y)(cid:1). − min x∈M (cid:0) inf y∈D f (x, y)(cid:1) = max x∈M (cid:0) sup y∈D

Vậy

f (x, y) ≥ η (cid:48)} (cid:54)= ∅. D(M) := {y ∈ D| min x∈M

(cid:3)

Chứng minh định lý Minimax

Giả sử giả thiết (A) được thỏa mãn. Khi đó γ < +∞.

Chương 2. Bài toán cân bằng

f (x, y). inf x∈C f (x, y) ≤ inf x∈C f (x, y), ta chỉ cần chứng minh γ ≥ inf x∈C Do sup y∈D sup y∈D sup y∈D

Lấy α ∈ (γ, η) bất kỳ và xét tập

C(cid:48)(y) := C(N∗) ∩C(y).

C(cid:48) (cid:54)= ∅.

C(y). C(cid:48)(y) = (cid:84) y∈D Áp dụng bổ đề trên với tập N = N∗ ∪ {y} và γ (cid:48) = α, ta có C(cid:48) (cid:54)= ∅ và họ tập {C(cid:48)|y ∈ D} có tính chất tương giao hữu hạn. Hơn nữa, tất cả các tập này đều nằm trong tập compact C(N∗). Do đó theo định lý tương giao hữu hạn của các tập lồi đóng, ta có (cid:84) y∈D Mặt khác, theo định nghĩa của C(cid:48)(y) thì (cid:84) y∈D

C(y). Ta có Lấy x∗ ∈ (cid:84) y∈D

x∗ ∈ C(N∗), f (x∗, y) ≤ α, ∀y ∈ D.

Suy ra

f (x∗, y) ≤ α. min x∈C(N∗) sup y∈D f (x, y) ≤ sup y∈D

Do α là số bất kỳ thỏa mãn α ≥ γ, nên ta có điều phải chứng minh là

x∈C(N∗)

f (x, y). γ ≥ min sup y∈D

Nhận xét 1. Điều kiện (A) sẽ thỏa mãn nếu có điều kiện bức sau

(AC) Có một tập hữu hạn N∗ ⊂ D sao cho

f (x, y) → +∞ khi x ∈ C, (cid:107)x(cid:107) → +∞. max y∈N∗

Điều kiện (B) sẽ thỏa mãn nếu có điều kiện bức sau:

(BC) Có một tập hữu hạn M∗ ⊂ C sao cho

f (x, y) → +∞ khi y ∈ D, (cid:107)y(cid:107) → +∞. min y∈M∗

Thật vậy, giả sử có (AC). Ta có thể giả thiết

f (x, y) < +∞. inf x∈C γ := sup y∈D

Lấy η > γ, khi đó tập

f (x, y) ≤ η} C(N∗) := {x ∈ D| sup y∈N∗

Chương 2. Bài toán cân bằng

bị chặn (và do đó compact). Vậy (AC) kéo theo (A). Nhận xét 2. Nếu (C) là tập compact thì (A) thỏa mãn và nếu (D) là tập compact thì (B) thỏa mãn.

Sau đây ta sẽ chứng minh một kết quả về sự tồn tại nghiệm của bài toán cân bằng

EP(C, f ) dựa trên định lý Minimax.

Mệnh đề 2.3.4. Cho C là một tập lồi đóng, khác rỗng và hàm φ có các tính chất: φ (x, .) là hàm tựa lồi, nửa liên tục dưới trên C , φ (., y) là hàm tựa lõm, nửa liên tục trên trên C. Ngoài ra φ (y, y) = 0 với mọi y ∈ C. Giả sử

(A1) Có một tập hữu hạn N∗ ⊂ C sao cho tập

φ (x, y) ≥ 0} C(N∗) := {x ∈ C| min y∈N∗

compact, hoặc

(B1) Có một tập hữu hạn M∗ ⊂ C sao cho tập

φ (x, y) ≤ 0} D(M∗) := {y ∈ C| min x∈M∗

compact. Khi đó bài toán (EP) có nghiệm.

Chứng minh. Đặt f (x, y) := −φ (x, y) và D ≡ C. Khi đó hàm f thỏa mãn điều kiện

của định lý Minimax, khi đó ta có

f (x, y). (2.1) inf x∈C f (x, y) = inf x∈C sup y∈C sup y∈C

Ta sẽ chứng minh

f (x, y) = 0. (2.2) inf x∈C sup y∈C

Thật vậy, ta có

f (x, x) = 0; inf x∈C f (x, y) ≥ inf x∈C sup y∈C

có được đẳng thức cuối là do f (x, x) = 0.

Mặt khác,

f (y, y). (2.3) inf x∈C sup y∈C f (x, y) ≤ sup y∈C

Từ (2.1), (2.2) và (2.3) ta có

f (x, y) = 0. inf x∈C f (x, y) = inf x∈C sup y∈C sup y∈C

Chương 2. Bài toán cân bằng

Giả sử điều kiện (A1) thỏa mãn, theo Định lý minimax tồn tại x ∈ C(N∗) ⊂ C sao

cho

f (x, y) = 0. min x∈C(N∗) sup y∈C

f (x, y). Do f (., y) nửa liên tục dưới trên C, nên s cũng nửa liên tục Đặt s(x) := sup y∈C

dưới trên C. Mặt khác, do C(N∗) là tập compact nên tồn tại x∗ ∈ C(N∗), sao cho

s(x) = 0. s(x∗) = min x∈C(N∗)

Hay

f (x∗, y) = 0. s(x∗) = sup y∈C

Suy ra

f (x∗, y) ≤ 0, ∀y ∈ C.

Vậy φ (x∗, y) = − f (x∗, y) ≥ 0 với mọi y ∈ C. Chứng tỏ x∗ là nghiệm của bài toán cân (cid:3) bằng EP(C, f ) Nhận xét.

Điều kiện (A1) sẽ thỏa mãn nếu có điều kiện bức sau: Tồn tại tập hữu hạn N∗ ⊂ C

φ (x, y) → −∞ khi x ∈ C, (cid:107)x(cid:107) → +∞. sao cho min y∈N∗

Điều kiện (B1) sẽ thỏa mãn nếu có điều kiện bức sau: Tồn tại tập hữu hạn M∗ ⊂ C

φ (x, y) → +∞ khi y ∈ C, (cid:107)y(cid:107) → −∞. sao cho max x∈M∗

2.4 Kết luận

Chương 2 đã trình bày được các khái niệm về song hàm cân bằng, toán tử cân bằng và bài toán cân bằng; các khái niệm về song hàm đơn điệu mạnh, đơn điệu, giả đơn điệu.

Một số bài toán có thể đưa về dạng bài toán cân bằng. Phát biểu và chứng minh sự tồn tại nghiệm của bài toán cân bằng.

Chương 3

Hiệu chỉnh dựa trên tối ưu hai cấp

Bài toán cân bằng hai cấp là bài toán có dạng

Tìm x∗ ∈ S f sao cho g(x∗, y) ≥ 0, ∀y ∈ S f

trong đó S f là tập nghiệm của bài toán cân bằng

Tìm u ∈ C sao cho f (u, y) ≥ 0, ∀y ∈ C

với C là một tập lồi, đóng, khác rỗng trong không gian Hilbert H và f , g : C ×C → R ∪ {+∞} là các song hàm cân bằng xác định trên C. Bài toán cân bằng chứa nhiều lớp bài toán quan trọng khác như là các trường hợp riêng của nó như bài toán bất đẳng thức biến phân hai cấp, bài toán bất đẳng thức biến phân trên tập nghiệm của bài toán cân bằng.

Bài toán tối ưu hai cấp là bài toán tìm cực tiểu của một hàm chuẩn trên tập nghiệm của bài toán cân bằng ban đầu. Trong chương này chúng ta sẽ nghiên cứu hai phương pháp hiệu chỉnh cho bài toán cân bằng giả đơn điệu đó là phương pháp Tikhonov và phương pháp điểm gần kề. Thuật toán và tính hội tụ của thuật toán hiệu chỉnh dựa trên bài toán tối ưu hai cấp. Các kết quả được lấy ra từ các tài liệu [3], [4], [5], [6], [7].

3.1 Hiệu chỉnh bài toán cân bằng giả đơn điệu

3.1.1 Phương pháp hiệu chỉnh Tikhonov

Phương pháp hiệu chỉnh Tikhonov là một trong những phương pháp cơ bản thường được sử dụng để giải các bài toán đặt không chỉnh. Ý tưởng của phương pháp hiệu chỉnh Tikhonov cho bài toán cân bằng là thay song hàm f bằng một song hàm fε := f + εg, trong đó ε > 0 là tham số hiệu chỉnh và g là song hàm đơn điệu mạnh được gọi là song hàm hiệu chỉnh, sau đó xét bài toán cân bằng với song hàm fε.

Xét bài toán cân bằng

Tìm x∗ ∈ C sao cho f (x∗, y) ≥ 0, ∀y ∈ C,

Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp

trong đó C là một tập lồi đóng trong H , f : C ×C → R là một song hàm giả đơn điệu trên C. Khi đó bài toán hiệu chỉnh được xây dựng như sau.

(cid:26)Tìm x ∈ C sao cho (EP(C, fε)) fε(x, y) := f (x, y) + εg(x, y) ≥ 0, ∀y ∈ C

trong đó g(x, y) là một song hàm đơn điệu mạnh được gọi là song hàm hiệu chỉnh, ε > 0 là tham số hiệu chỉnh.

Định lý sau đây cho thấy, khi song hàm cân bằng f là giả đơn điệu, bài toán hiệu chỉnh EP(C, fε) có nghiệm khi và chỉ khi bài toán ban đầu EP(C, f ) có nghiệm và mặc dù không có nghiệm duy nhất nhưng mọi quỹ đạo nghiệm của nó đều hội tụ đến nghiệm của bài toán EP(C, f ) gần với nghiệm dự đoán xg nhất.

Định lý 3.1.1. Giả sử f là giả đơn điệu trên C và thỏa mãn các giả thiết (A1), (A2). Khi đó các khẳng định sau là tương đương

1. S(C, fε) khác rỗng với mọi ε > 0 và limε→0+ x(ε) tồn tại, với x(ε) chọn tùy ý

trong S(C, fε).

2. S(C, fε) khác rỗng với mọi ε > 0 và limε→0+ sup(cid:107)x(ε)(cid:107) < ∞, với x(ε) chọn tùy

ý trong S(C, fε).

3. S(C, f ) (cid:54)= 0.

Hơn nữa, nếu một trong các khẳng định trên được thỏa mãn thì

x(ε) = x∗, lim ε→0+

trong đó x∗ là nghiệm duy nhất của bài toán cân bằng EP( (cid:101)C, g) với (cid:101)C := S(C, f ), g là một song hàm đơn điệu mạnh thỏa mãn

∃δ > 0 : |g(x, y)| ≤ δ (cid:107)x − xg(cid:107).(cid:107)y − x(cid:107), ∀x, y ∈ C.

Ngoài ra nếu g là song hàm khoảng cách thì x∗ là hình chiếu của xg trên tập nghiệm của bài toán EP(C, f ).

Tuy nhiên, nhiều khi bài toán hiệu chỉnh còn khó giải hơn bài toán ban đầu, vì vậy để hạn chế phần nào nhược điểm nói trên ta thay thế bất đẳng thức fε(x, y) ≥ 0 trong bài toán EP(C, fε) bởi bất đẳng thức fε(x, y) ≥ −δ trong đó δ ≥ 0 là một hằng số cho trước. Khi đó bài toán EP(C, fε) với song hàm hiệu chỉnh là song hàm khoảng cách g(x, y) = (cid:104)x − xg, y − x(cid:105) trở thành bài toán hiệu chỉnh

(cid:26)Tìm x ∈ C sao cho (EPδ (C, fε)) fε(x, y) := f (x, y) + ε(cid:104)x − xg, y − x(cid:105) ≥ −δ , ∀y ∈ C

Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp

Kí hiệu Sδ (C, fε) là tập nghiệm của bài toán EPδ (C, fε).

Nhận xét. Nếu x thỏa mãn fε(x, y) ≥ 0 với mọi y ∈ C thì cũng thỏa mãn fε(x, y) ≥ −δ với mọi y ∈ C, do đó

S(C, fε) ⊆ Sδ (C, fε).

Ta xét bổ đề sau

Bổ đề 3.1.1. Giả sử f là giả đơn điệu trên C. Khi đó với mọi ε > 0, δ ≥ 0, x ∈ S(C, f ), x(ε) ∈ Sδ (C, fε) và xg ∈ C, ta có

, 1. (cid:107)xg − x(ε)(cid:107)2 + (cid:107)x(ε) − x(cid:107)2 ≤ (cid:107)xg − x(cid:107)2 + 2 δ ε (cid:32) (cid:33)

∩C, 0, 2. Sδ (C, fε) ⊂ B (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) + (cid:114)(cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) + x + xg 2 x − xg 2 δ ε

+ , 3. (cid:107)x(ε) − xg(cid:107) ≤ (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) + (cid:114)(cid:13) (cid:13) (cid:13) (cid:13) 2 (cid:13) (cid:13) x − xg 2 x − xg 2 δ ε

trong đó kí hiệu B(x, r) là hình cầu đóng tâm x, bán kính r.

Chứng minh. Giả thiết x ∈ S(C, f ), do f là giả đơn điệu nên ta có

f (x, y) ≥ 0 ⇒ f (y, x) ≤ 0, ∀y ∈ C. (3.1)

Do x(ε) ∈ Sδ (C, fε) nên

(3.2) f (x(ε), y) + ε(cid:10)x(ε) − xg, y − x(ε)(cid:11) ≥ −δ , ∀y ∈ C.

Thay y = x(ε) vào bất đẳng thức thứ hai trong công thức (3.1), và y = x vào công thức (3.2) ta được

f (x(ε), x) ≤ 0 và f (x(ε), x) + ε(cid:10)x(ε) − xg, x − x(ε)(cid:11) ≥ −δ .

2(cid:105)

Từ đó ta có

2 − (cid:13) (cid:13)xg − x(ε)(cid:13) (cid:13)

. = (cid:10)x(ε) − xg, x − x(ε)(cid:11) ≥ − (cid:104)(cid:13) 2 − (cid:13) (cid:13)xg − x(cid:13) (cid:13) (cid:13)x(ε) − x(cid:13) (cid:13) δ ε 1 2 Do đó

. (cid:107)xg − x(ε)(cid:107)2 + (cid:107)x(ε) − x(cid:107)2 ≤ (cid:107)xg − x(cid:107)2 + 2 δ ε Vậy 1) được chứng minh.

Mặt khác, ta có

2 + (cid:13) (cid:13)x(ε) − xg(cid:13) (cid:13) (cid:13)

2 ≤ (cid:13) (cid:13)[x(ε) − xg] − [x − xg](cid:13) (cid:13)

, (cid:13)x − xg(cid:13) 2 + 2 (cid:13) δ ε

Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp

trong đó

. (cid:13)x(ε) − xg(cid:13) (cid:13) 2 − (cid:10)x(ε) − xg, x − xg(cid:11) ≤ (cid:13) δ ε Do đó

= ; (cid:13) (cid:13) (cid:13)x(ε) − (cid:13) 2 (cid:13) (cid:13) (cid:13) 2 (cid:13) (cid:13) x + xg 2 x − xg 2

; (cid:13) (cid:13) (cid:13) (cid:13) 2 (cid:13) (cid:13) x − xg 2

+ ≤ . (cid:13) 2 (cid:13) (cid:13) (cid:13) (cid:13)x(ε) − xg − (cid:13) (cid:13)x(ε) − xg(cid:13) = (cid:13) 2 − (cid:10)x(ε) − xg, x − xg(cid:11) + (cid:13) x − xg (cid:13) (cid:13) (cid:13) 2 δ ε

(cid:3) Khi đó 2), 3) được chứng minh.

Bổ đề 3.1.2. Giả sử f là giả đơn điệu trên C và thỏa mãn các giả thiết (A1), (A2). Khi đó, nếu tập nghiệm S(C, f ) là khác rỗng thì với mọi ε > 0, δ ≥ 0 tập δ − nghiệm Sδ (C, fε) là khác rỗng và compact yếu.

Chứng minh.

Theo Mệnh đề 2.3.2, ta luôn tìm được một vectơ y0 ∈ C sao cho tập

Lδ (y0, fε) := (cid:8)x ∈ C : fε(x, y0) := f (x, y0) + ε(cid:10)x − xg, y0 − x(cid:11) ≥ −δ (cid:9)

là bị chặn. Lấy y0 ∈ S(C, f ) và x ∈ Lδ (y0, fε). Từ định nghĩa của Lδ (y0, fε) ta có

fε(x, y0) = f (x, y0) + ε(cid:10)x − xg, y0 − x(cid:11) ≥ −δ .

Từ điều kiện f (y0, x) ≥ 0, do f là giả đơn điệu nên ta có f (x, y0) ≤ 0. Do đó

(cid:10)x − xg, y0 − x(cid:11) ≥ − . δ ε Khi đó

(cid:2)(cid:107)xg − y0(cid:107)2 − (cid:107)xg − x(cid:107)2 − (cid:107)x − y0(cid:107)2(cid:3) = (cid:10)x − xg, y0 − x(cid:11) ≥ − . 1 2 δ ε

Từ đó

, (cid:107)xg − x(cid:107)2 + (cid:107)x − y0(cid:107)2 ≤ (cid:107)xg − y0(cid:107)2 + 2 δ ε trong đó (cid:114)

(cid:107)xg − x(cid:107) ≤ , (cid:107)xg − y0(cid:107)2 + 2 δ ε suy ra (cid:114)

(cid:107)x(cid:107) ≤ (cid:107)xg(cid:107) + (cid:107)y0 − xg(cid:107)2 + 2 , ∀x ∈ Lδ (y0, fε). δ ε

Vậy tập Lδ (y0, fε) là bị chặn.

Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp

Ví dụ 3.1.1.

Ta xét song hàm giả đơn điệu được xác định như ở Ví dụ 2.1.3

Xét bài toán hiệu chỉnh

(cid:26) Tìm xk ∈ C sao cho (EP(C, fεk)) fεk(xk, y) := f (xk, y) + εk(cid:104)xk − xg, y − xk(cid:105) ≥ −δk, ∀y ∈ C,

i , ...) ∈ C là nghiệm dự đoán của bài toán EP(C, f ); {εk}, {δk}

1, xg

2, ..., xg

trong đó xg = (xg

1) + εk(cid:104)(cid:98)xk − (cid:98)xg, (cid:98)y − (cid:98)xk(cid:105)

là hai dãy số dương đơn điệu giảm về 0 thỏa mãn → 0 khi k → ∞, và

1)(y1 − xk

= εk(xk fεk(xk, y) = (2 − (cid:107)(cid:98)xk(cid:107))(cid:104)(cid:98)xk, (cid:98)y − (cid:98)xk(cid:105) + εk(xk 1 − xg δk εk 1 − xg 1)(y1 − xk 1) + ε(cid:104)(2 − (cid:107)(cid:98)xk(cid:107) + εk)(cid:98)xk − εk(cid:98)xg, (cid:98)y − (cid:98)xk(cid:105).

1, (2 − (cid:107)(cid:98)xk(cid:107) + εk)(cid:98)xk − εk(cid:98)xg = 0

1 = xg xk 1, (cid:98)xk) là một nghiệm của bài toán EP(C, fεk).

Ta nhận thấy, nếu

được thỏa mãn thì xk = (xk Từ đẳng thức (2 − (cid:107)(cid:98)xk(cid:107) + εk)(cid:98)xk − εk(cid:98)xg = 0 ta suy ra

. 0 ≤ (cid:107)(cid:98)xk(cid:107) = (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) ≤ 2 − √ 2 ε √ 2 + εk εk(cid:98)xg 2 − (cid:107)(cid:98)xk(cid:107) + εk

Do khi k → ∞ thì εk → 0 nên

k→+∞

1,(cid:98)0) = (xg

1, 0, ..., 0, ...) ∈ (cid:101)C. Hơn nữa, x∗ là nghiệm

εk √ 0 ≤ limk→+∞(cid:107)(cid:98)xk − (cid:98)0(cid:107) = limk→+∞(cid:107)(cid:98)xk(cid:107) ≤ lim 2 − √ 2 2 + εk

⇒ limk→+∞(cid:107)(cid:98)xk − (cid:98)0(cid:107) = 0. Điều này chứng tỏ (cid:98)xk hội tụ mạnh về (cid:98)0. Do đó, xk hội tụ mạnh về x∗ := (xg duy nhất của bài toán cân bằng đơn điệu mạnh EP( (cid:101)C, g) với

1)(y1 − x1) + (cid:104)(cid:98)x − (cid:98)xg, (cid:98)y − (cid:98)x(cid:105) ≥ 0.

g(x, y) := (x1 − xg

3.1.2 Phương pháp điểm gần kề

Trong phần này chúng ta sẽ nghiên cứu phương pháp điểm gần kề cho bài toán cân bằng giả đơn điệu. Kết quả hội tụ của phương pháp này cho thấy phương pháp điểm gần kề cũng có thể sử dụng cho bài toán cân bằng giả đơn điệu. Tuy nhiên, khác với phương pháp hiệu chỉnh Tikhonov, ở phương pháp này, tại mỗi bước lặp, bài toán hiệu chỉnh phụ thuộc vào điểm lặp ở bước trước và tham số hiệu chỉnh ck > 0 không cần dần đến 0.

Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp

Xuất phát từ một điểm x0 ∈ C cho trước, tại mỗi bước lặp k = 1, 2, ... xét bài toán

hiệu chỉnh

(cid:26)Tìm xk ∈ C sao cho

fk(xk, y) := f (xk, y) + ck(cid:104)xk − xk−1, y − xk(cid:105) ≥ −δk, ∀y ∈ C

trong đó tham số ck > 0 và sai số δk ≥ 0 cho trước. Ta gọi nghiệm của bài toán hiệu chỉnh trên là δk − nghiệm và kí hiệu tập tất cả các δk − nghiệm là Sδk(C, fk). Gọi dãy {xk} với xk ∈ Sδk(C, fk) là một quỹ đạo xấp xỉ gần kề.

Định lý sau đây sẽ chỉ ra rằng, đối với bài toán cân bằng giả đơn điệu, mặc dù bài toán hiệu chỉnh không có duy nhất nghiệm nhưng mọi quỹ đạo xấp xỉ đều có cùng một giới hạn.

k=1

δk ck

< +∞. Khi đó Định lý 3.1.2. Giả sử f là giả đơn điệu trên C thỏa mãn các giả thiết (A1), (A2) và bài toán EP(C, f ) là có lời giải. Lấy {ck} và {δk} là hai dãy số dương sao cho ck ≤ c < +∞, ∀k, và ∑∞

1. Đối với mỗi k ∈ N tập nghiệm Sδk(C, fk) khác rỗng, đóng và bị chặn đều. Khi đó

ta có

, (cid:107)xk−1 − xk(cid:107)2 + (cid:107)xk − x(cid:107)2 ≤ (cid:107)xk−1 − x(cid:107)2 + 2 (3.3) δk ck

trong đó x ∈ S(C, f ), xk ∈ Sδk(C, fk).

2. Xét dãy {xk} bất kỳ, trong đó xk chọn tùy ý trong tập Sδk(C, fεk), hội tụ yếu đến một nghiệm của bài toán EP(C, f ). Hơn nữa, nếu {xk} có một điểm hội tụ mạnh, khi đó toàn bộ dãy sẽ hội tụ mạnh đến một nghiệm của bài toán EP(C, f ) ban đầu.

Chứng minh.

1. Từ Bổ đề 3.1.2 với xg = xk−1 ∈ C và ε = ck > 0 ta thấy, với mọi k = 1, 2, 3, ... tập nghiệm của bài toán cân bằng EP(C, fk) là đóng, rỗng và bị chặn đều. Áp dụng ý 1) trong Bổ đề 3.1.1 với

xg = xk−1, x(ε) = xk, ε = ck, δ = δk.

ta được

(cid:107)xk−1 − xk(cid:107)2 + (cid:107)xk − x(cid:107)2 ≤ (cid:107)xk−1 − x(cid:107)2 + 2 δk ck

là điều phải chứng minh. 2. Gọi x là điểm bất động bất kỳ trong tập nghiệm của bài toán EP(C, f ), lấy xk ∈

Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp

Sδk(C, fk) với k ≥ 1. Từ (3.3) ta có

. (cid:107)xk − x(cid:107)2 ≤ (cid:107)xk−1 − x(cid:107)2 + 2 (3.4) δk ck

< +∞, ta có Từ ∑+∞ k=1 δk ck (3.5) (cid:107)xk − x(cid:107) = µ < ∞. lim x→∞

Dùng bất đẳng thức (3.3) ta có thể viết lại như sau

. (cid:107)xk − xk−1(cid:107)2 ≤ (cid:107)xk−1 − x(cid:107)2 − (cid:107)xk − x(cid:107)2 + 2 δk ck

Khi đó, do (3.5) và → 0 khi k → ∞, ta có δk ck

(cid:107)xk − xk−1(cid:107) = 0. (3.6) lim k→∞

Đặt

∞ ∑ j=1

M := 2 < ∞. δ j c j

Khi đó, từ (3.4)

k ∑ j=1

(cid:107)xk − x(cid:107)2 ≤ (cid:107)xg − x(cid:107)2 + 2 ≤ (cid:107)xg − x(cid:107)2 + M ∀k; δ j c j

(cid:113) ⇒ (cid:107)xk − x(cid:107) ≤

(cid:107)xg − x(cid:107)2 + M ∀k; (cid:113) ⇒ (cid:107)xk(cid:107) ≤ (cid:107)x(cid:107) + (cid:107)xg − x(cid:107)2 + M ∀k;

(cid:113) (cid:107)xg − x(cid:107)2 + M) ∩C ∀k. ⇒ xk ∈ Sδk(C, fk) ⊂ B(0, (cid:107)x(cid:107) +

j} ≤ {xk} sao cho

Do {xk} là bị chặn nên tồn tại một dãy con {xk

(cid:113) (cid:107)xg − x(cid:107)2 + M) ∩C. xk j (cid:42) x∗ ∈ B(0, (cid:107)x(cid:107) +

(3.7) Do xk j là một δk j-nghiệm của bài toán cân bằng EP(C, fk j) với mọi k j, ta có fk j(xk j, y) = f (xk j, y) + ck j(cid:104)xk j − xk j−1, y − xk j(cid:105) ≥ −δk j, ∀y ∈ C.

Kết hợp với (3.6), với f là nửa liên tục trên yếu, và điều kiện

0 < ck j < c < +∞, δk j (cid:38) 0

cùng với (3.7), trong đó

0 ≤ limk j→∞ fk j(xk j, y) ≤ limk j→∞ f (xk j, y) ≤ f (x∗, y), ∀y ∈ C

Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp

2 ∈ S(C, f ).

1, x∗

2 là hai điểm tụ yếu phân biệt của {xk}. Khi đó x∗ i (i = 1, 2) đóng vai trò như x ta được

cho thấy x∗ ∈ S(C, f ). Ta cần chỉ ra rằng x∗ là điểm tụ yếu duy nhất của {xk}. 1, x∗ Thật vậy, giả sử x∗ Áp dụng (3.5) với x∗

i (cid:107) = µi,

(cid:107)xk − x∗ i = 1, 2. (3.8) lim k→∞

Rõ ràng

1, x∗

1 − x∗

2(cid:105) = (cid:107)xk − x∗

2(cid:107)2 − (cid:107)xk − x∗

1(cid:107)2 − (cid:107)x∗

1 − x∗

2(cid:107)2.

2(cid:104)xk − x∗ (3.9)

1 là một điểm tụ yếu của {xk}, từ (3.8), (3.9) dẫn đến

Do x∗

1, x∗

1 − x∗

2(cid:105) = µ 2

2 − µ 2

1 − (cid:107)x∗

1 − x∗

2(cid:107)2.

(cid:104)xk − x∗ 0 = 2 lim k→∞

2 − µ 2 µ 2

1 = (cid:107)x∗

1 − x∗

2(cid:107)2 > 0.

Do đó,

1 và x∗

2 cho nhau và lập luận tương tự ta cũng thu được kết quả

1 − µ 2 µ 2

2 = (cid:107)x∗

2 − x∗

1(cid:107)2 > 0.

Thay đổi vai trò của x∗

Điều này là vô lý. Vậy x∗ là duy nhất.

Giả sử dãy con {xk j} ⊆ {xk} hội tụ mạnh tới x∗ ∈ H . Khi đó x∗ ∈ S(C, f ).

Áp dụng công thức (3.4) với x = x∗ ta được

, ∀k ∈ N. (cid:107)xk − x∗(cid:107)2 ≤ (cid:107)xk−1 − x∗(cid:107)2 + 2 (3.10) δk ck

k=1

δk ck

< +∞, lấy l ∈ N sao cho Với γ > 0 bất kỳ, do limk j→∞ ||xk j − x∗|| = 0 và ∑∞

∞ ∑ i=kl+1

(cid:107)xkl − x∗(cid:107) ≤ ≤ . và γ 2 4 δi ci γ √ 2

Do đó, với k > kl + 1, từ (3.10) ta được

(cid:107)xk − x∗(cid:107)2 ≤ (cid:107)xk−1 − x∗(cid:107)2 + 2 ;

+ ); δk ck δk ≤ (cid:107)xk−2 − x∗(cid:107)2 + 2( ck δk−1 ck−1 ≤ ...;

+ + ... + ≤ (cid:107)xkl − x∗(cid:107)2 + 2( ); δk ck δk−1 ck−1 δkl+1 ckl+1

≤ + = γ 2. γ 2 2 γ 2 2

Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp

Do đó,

(cid:107)xk − x∗(cid:107) ≤ γ, ∀k > kl + 1.

Vậy, với γ > 0 tùy ý ta luôn có

(cid:107)xk − x∗(cid:107) = 0, lim k→∞

(cid:3) hay {xk} hội tụ mạnh về x∗, vậy ta có điều cần chứng minh.

k=1

δk ck

< +∞. Khi đó Định lý 3.1.3. Giả sử C ⊆ Rn là một tập lồi, đóng, khác rỗng, f là giả đơn điệu trên C, f (., y) là nửa liên tục trên với mỗi y ∈ C, f (x, .) là nửa lên tục dưới và lồi với mỗi x ∈ C, bài toán cân bằng EP(C, f ) có nghiệm. Lấy {ck}, {δk} là hai dãy số dương sao cho ck < c < +∞ và ∑∞

1. Với mọi k, tập δk-nghiệm của bài toán EP(C, fk) là khác rỗng và compact.

2. Mọi dãy {xk}, với xk là một δk-nghiệm của bài toán EP(C, fk) đều hội tụ mạnh

tới các nghiệm của bài toán EP(C, f ).

Chứng minh. Áp dụng Định lý 3.1.2 và do mọi dãy bị chặn bất kỳ trong không gian Rn đều là

một dãy hội tụ mạnh nên ta có điều phải chứng minh. Nhận xét. Các kết quả trên đã chỉ ra rằng, mọi quỹ đạo của thuật toán điểm gần kề đều có chung một điểm giới hạn yếu. Tuy nhiên việc tìm điểm giới hạn này là một việc khó do sự hội tụ là không mạnh và các kết quả trên không chỉ ra được điểm giới hạn này. Để làm rõ điều này ta xét ví dụ sau.

Ví dụ 3.1.2.

Xét song hàm cân bằng giả đơn điệu trong Ví dụ 2.1.3.

Ta xét bài toán hiệu chỉnh

1, xg

2, ..., xg

(cid:26) Tìm xk ∈ C sao cho (3.1.1) fk(xk, y) := f (xk, y) + ck(cid:104)xk − xk−1, y − xk(cid:105) ≥ −δk, ∀y ∈ C,

k=1

1 − xk−1 1

1) + ck(cid:104)(cid:98)xk − (cid:98)xk−1, (cid:98)y − (cid:98)xk(cid:105),

< +∞. Khi đó trong đó x0 = xg = (xg i , ...) là điểm xuất phát của dãy lặp, đóng vai trò là nghiệm dự đoán của bài toán EP(C, f ); {ck}, {δk} là hai dãy số không âm sao cho ck ≤ c < +∞ với mọi k ∈ N và ∑∞ δk ck

= ck(xk )(y1 − xk fk(xk, y) = (2 − (cid:107)(cid:98)xk(cid:107))(cid:104)(cid:98)xk, (cid:98)y − (cid:98)xk(cid:105) + ck(xk 1 − xk−1 1 )(y1 − xk 1) + ck(cid:104)(2 − (cid:107)(cid:98)xk(cid:107) + ck)(cid:98)xk − ck(cid:98)xk−1, (cid:98)y − (cid:98)xk(cid:105).

Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp

1 = xk−1 xk 1

Nhận thấy, nếu

, (2 − (cid:107)(cid:98)xk(cid:107) + ck)(cid:98)xk − ck(cid:98)xk−1 = 0

1, (cid:98)xk) là một nghiệm của bài toán EP(C, fk) và ta có

được thỏa mãn thì xk = (xk

ck √ . 0 ≤ (cid:107)(cid:98)xk(cid:107) = (cid:13) (cid:13) (cid:13) ≤ (cid:13) (cid:13) (cid:13) 2 − √ 2 2 + ck ck(cid:98)xk−1 2 − (cid:107)(cid:98)xk(cid:107) + ck

Tuy nhiên, khác với phương pháp hiệu chỉnh Tikhonov, khi cho k → ∞ thì ck (cid:54)→ 0 do đó, từ ước lượng trên ta không suy ra được dãy {xk} hội tụ mạnh đến một nghiệm cụ thể nào của bài toán EP(C, f ) mà chỉ có thể kết luận được rằng dãy này bị chặn, hội tụ yếu về một nghiệm nào đó của bài toán ban đầu.

3.2 Thuật toán giải

Như chúng ta đã biết, đối với bài toán cân bằng đơn điệu, nhờ tính đơn điệu mạnh của các bài toán hiệu chỉnh, các thuật toán hiệu chỉnh Tikhonov và điềm gần kề có thể dẫn đến những phương pháp giải chấp nhận được. Còn đối với bài toán cân bằng giả đơn điệu, các bài toán hiệu chỉnh nói chung là không đơn điệu mạnh, thậm chí không giả đơn điệu, vì vậy các phương pháp giải đòi hỏi tính đơn điệu không thể áp dụng được. Trong trường hợp này, các điểm giới hạn là điểm chiếu của các nghiệm dự đoán xg trên tập nghiệm của bài toán EP(C, f ). Các điểm giới hạn này có thể thu được dựa vào bài toán tối ưu hai cấp

min{(cid:107)x − xg(cid:107)2 với x ∈ S(C, f )}. (BO)

3.2.1 Mô tả thuật toán

2 (cid:107)x − y(cid:107)2, ∀x, y ∈ C;

Như ta đã biết, khi f là giả đơn điệu trên C, tập nghiệm S(C, f ) của bài toán EP(C, f ) là một tập lồi. Do đó (BO)là bài toán tìm cực tiểu của một hàm chuẩn trên một tập lồi.

Giả sử tập nghiệm S(C, f ) của bài toán EP(C, f ) là khác rỗng và f là liên tục yếu, giả đơn điệu trên C. Xét một song hàm L : H × H → R thỏa mãn các điều kiện sau (B1)L(x, x) = 0, ∃β > 0 : L(x, y) ≥ β (B2)L là liên tục yếu, L(x, .) là khả vi, lồi mạnh trên H với mọi x ∈ C và ∇2L(x, x) = 0 với mọi x ∈ H .

Ta xét bổ đề sau

Bổ đề 3.2.1. Giả sử f thỏa mãn các giả thiết (A1), (A2) và L thỏa mãn giả thiết (B1), (B2). Khi đó, với mọi ρ > 0, các mệnh đề sau đây là tương đương

Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp

1. x∗ là nghiệm của bài toán cân bằng;

2. x∗ ∈ C : f (x∗, y) + L(x∗, y) ≥ 0, ∀y ∈ C; 1 ρ

3. x∗ = argmin{ f (x∗, y) + L(x∗, y) : y ∈ C}. 1 ρ

Thuật toán.

Chọn ρ > 0 và η ∈ (0, 1). Khởi đầu với x1 := xg ∈ C (xg có vai trò như là một nghiệm dự đoán). Nếu x1 ∈ S(C, f ), thì x1 là một nghiệm của bài toán tối ưu (BO), ngược lại ta thực hiện phép lặp đối với k theo các bước sau. Bước 1. Giải các bài toán quy hoạch lồi mạnh

min{ f (xk, y) + L(xk, y) : y ∈ C} (CP(xk)) 1 ρ

để tìm nghiệm duy nhất yk. Nếu yk = xk, chọn uk := xk và chuyển đến Bước 3. Ngược lại chuyển sang Bước 2 Bước 2.(Qui tắc tìm kiếm theo tia Amijio) Tìm một số nguyên, không âm nhỏ nhất mk , m là một số nguyên, thỏa mãn

(3.11) zk,m := (1 − η m)xk + η myk,

f (zk,m, yk) + L(xk, yk) ≤ 0. (3.12) 1 ρ

Đặt ηk := η mk, zk := zk,mk, tính

(3.13) uk := PC(xk − σkgk), σk =

−ηk f (zk, yk) (1 − ηk)(cid:107)gk(cid:107)2 , trong đó gk ∈ ∂2 f (zk, zk), dưới đạo hàm của hàm lồi f (zk, .) tại zk. Bước 3. Xây dựng các nửa không gian

Ck := {y ∈ H : (cid:107)uk − y(cid:107)2 ≤ (cid:107)xk − y(cid:107)2};

Dk := {y ∈ H : (cid:104)xg − xk, y − xk(cid:105) ≤ 0}.

Bước 4. Đặt Bk = Ck ∩ Dk ∩C và tính xk+1 := PBk(xg). Nếu xk+1 ∈ S(C, f ), kết luận xk+1 là nghiệm của bài toán (BO). Ngược lại, tăng k lên 1 và lặp lại quá trình. Chú ý.

Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp

(i) Việc tìm kiếm theo tia trong Bước 2 là hoàn toàn xác định được, vì trái lại với

mọi số nguyên không âm m ta có

f (zk,m, yk) + L(xk, yk) > 0. (3.14) 1 ρ

Cho m → ∞, do tính nửa liên tục trên yếu của f (., yk), ta có

ρ L(xk, xk) = 0, cho thấy xk là một nghiệm của bài toán quy

f (xk, yk) + L(xk, yk) ≥ 0, 1 ρ

trong đó f (xk, xk) + 1 hoạch lồi mạnh CP(xk). Do đó xk = yk, điều này mâu thuẫn vì việc tìm kiếm theo tia chỉ được thực hiện khi xk (cid:54)= yk. Chú ý rằng mk > 0. Thật vậy, nếu mk = 0 khi đó ta có zk = yk, do đó

L(xk, yk) = f (zk, yk) + L(xk, yk) ≤ 0, 1 ρ 1 ρ

do L không âm, L(xk, yk) = 0 và từ

L(xk, yk) ≥ (cid:107)xk − yk(cid:107)2, β 2

ta có xk = yk.

(ii) gk (cid:54)= 0 và kích thước σk các bước ở (3.13) cho thấy xk (cid:54)= yk. Thật vậy, nếu gk = 0 khi đó, do gk ∈ ∂2 f (zk, zk) ta có

2 (cid:107)xk − yk(cid:107)2.

f (zk, x) ≥ (cid:104)gk, x − zk(cid:105) + f (zk, zk) = 0, ∀x ∈ C.

Từ (3.12) ta có L(xk, yk) ≤ 0, nhưng do giả thiết (B1) L(xk, yk) ≥ β Do đó xk = yk.

3.2.2 Tính hội tụ của thuật toán

Bổ đề và định lý sau cho thấy tính hội tụ mạnh của các dãy {xk}, {uk} trong thuật

toán trên.

Bổ đề 3.2.2. Từ các giả thiết của Bổ đề 3.2.1 ta có Giả sử f thỏa mãn các giả thiết (A1), (A2) và L thỏa mãn giả thiết (B1), (B2)

k (cid:107)gk(cid:107)2, ∀x∗ ∈ S(C, f ), ∀k.

(3.15) (cid:107)uk − x∗(cid:107)2 ≤ (cid:107)xk − x∗(cid:107)2 − σ 2

Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp

Chứng minh.

Đặt vk = xk − σkgk. Từ uk = PC(vk), ta có

(cid:107)uk − x∗(cid:107)2 = (cid:107)PC(vk) − PC(x∗)(cid:107)2 ≤ (cid:107)vk − x∗(cid:107)2;

(3.16)

k (cid:107)gk(cid:107)2 − 2σk(cid:104)gk, xk − x∗(cid:105).

= (cid:107)xk − x∗ − σkgk(cid:107)2; = (cid:107)xk − x∗(cid:107)2 + σ 2

Do gk ∈ ∂2 f (zk, zk) nên ta có

(cid:104)gk, xk − x∗(cid:105) = (cid:104)gk, xk − zk + zk − x∗(cid:105);

(3.17)

= (cid:104)gk, xk − zk(cid:105) + (cid:104)gk, zk − x∗(cid:105); ≥ (cid:104)gk, xk − zk(cid:105) − f (zk, x∗).

Vì x∗ ∈ S(C, f ) nên f (x∗, zk) ≥ 0, f là giả đơn điệu suy ra − f (zk, x∗) ≥ 0. Do đó, từ (3.16) ta có

(cid:104)gk, xk − x∗(cid:105) ≥ (cid:104)gk, xk − zk(cid:105) (3.18)

(zk − yk). Khi đó Trong đó xk − zk = ηk 1 − ηk

(cid:104)gk, xk − zk(cid:105) = (3.19) (cid:104)gk, zk − yk(cid:105) = σk(cid:107)gk(cid:107)2. ηk 1 − ηk

Đẳng thức cuối cùng được suy ra từ định nghĩa của σk trong công thức (3.13) của thuật toán. Kết hợp với các công thức (3.16), (3.18), và (3.19) ta thu được (3.15).

Định lý 3.2.1. Giả sử f là song hàm liên tục yếu, f(x,.) là lồi, khả dưới vi phân trên C với mọi x ∈ C và bài toán EP(C, f ) có nghiệm. Khi đó cả hai dãy {xk}, {uk} đều hội tụ tới nghiệm duy nhất của bài toán tối ưu hai cấp (BO).

Chứng minh.

Ta có S(C, f ) ⊆ Bk với mọi k. Thật vậy, từ Định lý 3.1.2 ta có

(cid:107)un − x∗(cid:107)2 ≤ (cid:107)xn − x∗(cid:107)2, ∀x∗ ∈ S(C, f ),

do đó S(C, f ) ⊆ Ck. Ta chứng minh S(C, f ) ⊆ Dk bằng phương pháp qui nạp. Với k = 1 thì D1 = H nên S(C, f ) ⊆ D1. Giả sử S(C, f ) ⊆ Dk, tức là (cid:104)xg − xk, x∗ − xk(cid:105) ≤ 0 với mọi x∗ ∈ S(C, f ). Khi đó S(C, f ) ⊆ Bk = Ck ∩ Dk. Mặt khác theo định nghĩa xk+1 = PBk(xg) nên ta có

(cid:104)x∗ − xk+1, xk+1 − xg(cid:105) ≤ 0, ∀x∗ ∈ S(C, f ),

Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp

hay

(cid:104)xk+1 − x∗, xg − xk+1(cid:105) ≤ 0, ∀x∗ ∈ S(C, f ).

Vậy S(C, f ) ⊆ Dk+1, suy ra S(C, f ) ⊆ Bk. Từ định nghĩa của Dk, ta có

xk = PDk(xg).

Do xk+1 ∈ Dk nên

(cid:107)xk − xg(cid:107) ≤ (cid:107)xk+1 − xg(cid:107), ∀k ∈ C.

Hơn nữa, xk = PDk(xg) và S(C, f ) ⊂ Dk với mọi k nên ta có

(cid:107)xk − xg(cid:107) ≤ (cid:107)x∗ − xg(cid:107), ∀x∗ ∈ S(C, f ), ∀k. (3.20)

Do đó {xk} bị chặn. Do tính bị chặn của {xk} và (cid:107)xk − xg(cid:107) ≤ (cid:107)xk+1 − xg(cid:107) với mọi k nên limk (cid:107)xk − xg(cid:107) tồn tại. Ta chứng minh (cid:107)xk+1 − xk(cid:107) → 0 khi k → ∞..

Thật vậy, do xk ∈ Dk và xk+1 ∈ Dk, Dk là một tập lồi nên ta có

∈ Dk.

kk+1 + xk 2 Mặt khác, xk = PDk(xg) nên theo tính chất lồi mạnh của hàm (cid:107)xg − .(cid:107)2 ta có

(cid:107)xg − xk(cid:107)2 ≤ (cid:13)

+ (cid:13) 2; (cid:13) (cid:13)xg − xk − xg 2

xk+1 + xk (cid:13) 2; (cid:13) 2 xk+1 − xg 2 (cid:107)xg − xk+1(cid:107)2 + = (cid:107)xg − xk(cid:107)2 − (cid:107)xk+1 − xk(cid:107)2. 1 2 = (cid:13) (cid:13) 1 2 1 4

Suy ra

(cid:107)xk+1 − xk(cid:107)2 ≤ (cid:107)xg − xk+1(cid:107)2 − (cid:107)xg − xk(cid:107)2. 1 2

Do lim (cid:107)xk − xg(cid:107) tồn tại nên ta suy ra (cid:107)xk+1 − xk(cid:107) → 0 khi k → ∞. Mặt khác, xk+1 ∈ Bk ⊆ Ck, từ định nghĩa của Ck ta có

(cid:107)uk − xk+1(cid:107) ≤ (cid:107)xk+1 − xk(cid:107).

Do đó,

(cid:107)uk − xk(cid:107) ≤ (cid:107)uk − xk+1(cid:107) + (cid:107)xk+1 − xk(cid:107) ≤ 2(cid:107)xk+1 − xk(cid:107),

và (cid:107)xk+1 − xk(cid:107) → 0, tức là (cid:107)uk − xk(cid:107) → 0 khi k → ∞.

Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp

Sau đây ta sẽ chỉ ra rằng một điểm tụ yếu bất kỳ của dãy {xk} đều là một nghiệm của bài toán EP(C, f ). Thật vậy, lấy x là một điểm tụ yếu bất kỳ của dãy {xk}. Không mất tính chất tổng quát, ta giả sử xk (cid:42) x. Ta xét hai trường hợp Trường hợp 1. Việc tìm kiếm theo tia chỉ xảy ra ở hữu hạn điểm. Trong trường hợp này, theo thuật toán, uk = xk với mọi k vô hạn, do đó yk = xk là một nghiệm của bài toán EP(C, f ) với mọi k. Do vậy, trường hợp này luôn đúng. Trường hợp 2. Việc tìm kiếm theo tia xảy ra tại vô hạn điểm.

Khi đó ta trích ra một dãy con và giả thiết rằng việc tìm kiếm theo tia là thực hiện

được với mọi k. Ta xét hai khả năng

(a) limkηk > 0.

Do xk (cid:42) x và (cid:107)uk − xk(cid:107) → 0 nên uk (cid:42) x. Áp dụng công thức (3.15) với x∗ ∈ S(C, f ) ta thấy σk(cid:107)gk(cid:107)2 → 0. Do định nghĩa của σk nên ta có

− (cid:104)gk, yk − zk(cid:105) → 0. ηk 1 − ηk

Từ điều kiện limkηk > 0, giả sử (cid:104)gk, yk − zk(cid:105) → 0. Mặt khác từ giả thiết (B1) và qui tắc tìm kiếm Armijo ta có

(cid:107)xk − yk(cid:107)2 ≤ 0 ≤ L(xk, yk) ≤ −(cid:104)gk, yk − zk(cid:105) → 0. β 2ρ 1 2ρ

Do đó, (cid:107)xk − yk(cid:107) → 0. Do xk (cid:42) x nên yk (cid:42) x, trong đó yk là nghiệm của bài toán

(cid:110) f (xk, y) + (cid:111) . min L(xk, y) : y ∈ C (CP(Ck)) 1 ρ

Khi đó ta có thể viết lại như sau

f (xk, y) + L(xk, y) ≥ f (xk, yk) + L(xk, yk) ∀y ∈ C. 1 ρ 1 ρ

Cho k tiến ra vô cùng, do tính liên tục yếu của f và L nên

f (x, y) + L(x, y) ≥ f (x, y) + L(x, y) ∀y ∈ C, 1 ρ 1 ρ

điều này cho thấy y là nghiệm của bài toán CP(x). Do (cid:107)xk − yk(cid:107) → 0 và xk (cid:42) x, yk (cid:42) y nên suy ra x = y. Vậy theo Bổ đề 3.2.1 x là một nghiệm của bài toán EP(C, f ).

(b) limk ηk = 0.

Trong trường hợp này dãy {yk} cũng bị chặn. Thật vậy, do yk là nghiệm của bài toán CP(xk), hàm mục tiêu là liên tục yếu, lồi mạnh và lời giải là không đổi. Theo Định lý

Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp

Berge, ánh xạ xk → s(xk) := yk là liên tục yếu. Từ tính chất bị chặn của {xk} ta suy ra {yk} bị chặn, suy ra yk (cid:42) y.

Lập luận tương tự như trước ta được

f (x, y) + L(x, y) ≤ f (x, y) + L(x, y), ∀y ∈ C (3.21) 1 ρ 1 ρ

Mặt khác, do mk là số tự nhiên nhỏ nhất thỏa mãn quy tắc tìm kiếm theo tia Armijo nên

f (zk,mk−1, yk) + L(xk, yk) > 0. (3.22)

1 ρ Trong đó zk,mk−1 (cid:42) x khi k → ∞. Từ bất đẳng thức (3.22), do tính liên tục yếu của f và L ta thu được giới hạn

f (x, y) + L(x, y) ≥ 0. (3.23) 1 ρ

Thay y = x vào (3.21) ta được

f (x, y) + L(x, y) ≤ 0, 1 ρ

kết hợp với (3.23) ta được

f (x, y) + L(x, y) = 0. (3.24) 1 ρ

Từ (3.24) và

f (x, x) + L(x, x) = 0, 1 ρ

suy ra cả x, y đều là nghiệm của bài toán

(cid:110) f (x, y) + (cid:111) . min L(x, y) : y ∈ C 1 ρ

Do đó x = y, theo Bổ đề 3.2.1 x là nghiệm của bài toán EP(C, f ). Hơn nữa, từ điều kiện (cid:107)uk − xk(cid:107) → 0 ta có thể kết luận rằng, mọi điểm tụ yếu của {xk} đều là một nghiệm của bài toán EP(C, f ).

Ta cần chỉ ra {xk} hội tụ mạnh đến nghiệm duy nhất của bài toán hai cấp (BO). Nhận thấy mọi điểm tụ yếu của {xk} đều thuộc tập nghiệm S(C, f ). Gọi x∗ là một điểm tụ bất kỳ của dãy {xk}, s = PS(C, f )(xg). Khi đó, tồn tại dãy con {xk j} của dãy {xk} sao cho xk j → x∗ khi j → ∞.

Theo chứng minh trên ta có x∗ ∈ S(C, f ) và từ định nghĩa của s ta suy ra

sup(cid:107)xk − xg(cid:107) ≤ (cid:107)s − xg(cid:107). (cid:107)s − xg(cid:107) ≤ (cid:107)x∗ − xg(cid:107) = lim j (cid:107)xk j − xg(cid:107) ≤ lim k

Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp

Bất đẳng thức cuối xảy ra do xk+1 = PBk(xg) và s ∈ S(C, f ) ⊆ Bk với mọi k. Do đó

lim (cid:107)xk − xg(cid:107) = (cid:107)s − xg(cid:107) = (cid:107)x∗ − xg(cid:107).

(cid:3) Do x∗ ∈ S(C, f ), s = PS(C, f )(xg) và S(C, f ) là một tập lồi đóng nên hình chiếu của xg lên S(C, f ) là duy nhất, suy ra x∗ = s, do đó xk → s khi k → ∞ là nghiệm của bài toán (BO). Từ (cid:107)xk − uk(cid:107) → 0 ta có uk → Psxg.

3.3 Kết luận

Chương 3 đã trình bày được phương pháp hiệu chỉnh Tikhonov và phương pháp hiệu chỉnh điểm gần kề, sử dụng các phương pháp này vào việc giải bài toán cân bằng giả đơn điệu trong không gian Hilbert thông qua việc giải bài toán tối ưu hai cấp.

Chứng tỏ các bài toán hiệu chỉnh có nghiệm khi bài toán gốc có nghiệm và mọi quỹ đạo nghiệm của bài toán hiệu chỉnh đều hội tụ về cùng một nghiệm là nghiệm của bài toán ban đầu.

KẾT LUẬN CHUNG

Luận văn đã trình bày các vấn đề chính sau đây - Các khái niệm về không gian tuyến tính định chuẩn, không gian tiền Hilbert,

không gian Hilbert, sự hội tụ yếu, hội tụ mạnh trong không gian Hilbert. - Các định nghĩa về tập lồi, nón lồi, hàm lồi và tính chất của hàm lồi. - Phát biểu bài toán cân bằng, sự tồn tại nghiệm của bài toán cân bằng. Trình bày một số trường hợp có thể đưa về bài toán cân bằng như bài toán tối ưu, bài toán điểm bất động, bài toán cân bằng Nash, bài toán điểm yên ngựa.

- Trình bày phương pháp hiệu chỉnh Tikhonov và phương pháp điểm gần kề cho bài toán cân bằng giả đơn điệu, thuật toán hiệu chỉnh dựa trên bài toán tối ưu hai cấp và sự hội tụ của thuật toán.

TÀI LIỆU THAM KHẢO

Tiếng Việt [1] Đỗ Văn Lưu, Giải tích hàm, (2009), NXB khoa học kỹ thuật, Hà Nội. [2] Lê Dũng Mưu, Nguyễn Văn Hiền, Nguyễn Hữu Điển (2015), Giáo trình giải

tích lồi ứng dụng, NXB ĐHQG Hà Nội.

Tiếng Anh [3] Bui V.Dinh, Pham G.Hung, Le D.Muu (2014), Bilevel optimization as a regu- larization approach to pseudomonotone equilibrium problems, Numerical Functional Analysis and Optimization. 35:539-563.

[4] Pham G. Hung, Le D. Muu (2011), The Tikhonov regularization extended to equilibrium problems involving pseudomontone bifunctions, Nonlinear Analysis 74:6121 – 6129.

[5] M. Bianchi and S. Schaible (1996), Generalized monotone bifunctions and

equilibrium problems, Journal of Optimization Theory and Applications. 90:31–43.

[6] G. Mastroeni (2003), On auxiliary priciple for equilibrium problems, Kluwer

Academic, Dordrecht, pp. 289–298.

[7] L. D. Muu (1984), Stability property of a class of variational inequality, Opti-

mization 15:347–351.