NGUYỄN THỊ HUYỀN
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————–
BÀI TOÁN CỰC TIỂU HÀM LỒI
VÀ HÀM TỰA LỒI TRÊN TẬP LỒI
LUẬN VĂN THẠC SĨ TOÁN HỌC
THÁI NGUYÊN - 2020
NGUYỄN THỊ HUYỀN
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————–
BÀI TOÁN CỰC TIỂU HÀM LỒI
VÀ HÀM TỰA LỒI TRÊN TẬP LỒI
Chuyên ngành: Toán ứng dụng Mã số: 8 46 01 12
Người hướng dẫn khoa học GS.TSKH. LÊ DŨNG MƯU
LUẬN VĂN THẠC SĨ TOÁN HỌC
THÁI NGUYÊN - 2020
Lời cam đoan
Tôi xin cam đoan số liệu và kết quả nghiên cứu trong luận văn “Bài
toán cực tiểu hàm lồi và hàm tựa lồi trên tập lồi” của riêng bản thân tôi
dưới sự hướng dẫn khoa học của GS.TSKH. LÊ DŨNG MƯU là trung
thực, không có bất kỳ sự sao chép hay sử dụng để bảo vệ một học vị nào và
chưa từng được công bố dưới bất kì hình thức nào.
Tất cả những sự giúp đỡ cho việc xây dựng cơ sở lý luận cho bài luận
đều được trích dẫn đầy đủ và ghi nguồn gốc rõ ràng. Nếu phát hiện có sự
sao chép kết quả nghiên cứu của đề tài khác, tôi xin hoàn toàn chịu trách
Thái Nguyên, ngày 10 tháng 1 năm 2021
Tác giả
NGUYỄN THỊ HUYỀN
i
nhiệm.
Lời cảm ơn
Trong thời gian hoàn thành luận văn tôi đã nhận được nhiều sự giúp
đỡ, đóng góp ý kiến và chỉ bảo nhiệt tình của GS.TSKH. LÊ DŨNG
MƯU.
Ngoài ra, trong quá trình học tập và làm luận văn, từ các bài giảng
của các Giáo sư, Phó Giáo sư đang công tác tại Viện Toán học, các Thầy
Cô trong Trường Đại học Khoa học Thái Nguyên, tôi đã trau dồi thêm rất
nhiều kiến thức, kỹ năng phục vụ cho việc nghiên cứu và công tác của bản
thân. Từ đáy lòng mình, tôi xin bày tỏ lòng cảm ơn sâu sắc tới các Thầy
Cô.
Tôi cũng muốn gửi lời cảm ơn bộ môn Toán ứng dụng và tin học.
Khoa Toán - Tin Trường Đại học Khoa học Thái Nguyên, đã tạo mọi điều
kiện thuận lợi, hướng dẫn, phản biện để tôi có thể hoàn thành tốt luận văn
này. Do thời gian có hạn, bản thân tôi còn hạn chế nên luận văn có thể có
những thiếu sót. Tôi mong muốn nhận được ý kiến phản hồi, đóng góp và
xây dựng của các thầy cô, và các bạn.
Thái Nguyên, ngày 10 tháng 1 năm 2021
Tác giả
NGUYỄN THỊ HUYỀN
ii
Tôi xin chân thành cảm ơn!
Mục lục
Lời cam đoan i
Lời cảm ơn ii
Mục lục iv
Danh mục các ký hiệu, các chữ viết tắt v
Lời mở đầu 1
1 Hàm lồi, hàm tựa lồi trên tập lồi 3
1.1 Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Định nghĩa và ví dụ . . . . . . . . . . . . . . . . . . 3
1.1.2 Tổ hợp lồi và các tính chất cơ bản . . . . . . . . . . 4
1.2 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.1 Định nghĩa, ví dụ . . . . . . . . . . . . . . . . . . . 6
1.2.2 Các tính chất cơ bản . . . . . . . . . . . . . . . . . 8
1.2.3 Dưới vi phân của hàm lồi . . . . . . . . . . . . . . . 11
1.3 Hàm tựa lồi . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3.1 Định nghĩa, ví dụ . . . . . . . . . . . . . . . . . . . 13
1.3.2 Các tính chất cơ bản . . . . . . . . . . . . . . . . . 14
1.3.3 Đạo hàm và dưới vi phân của hàm tựa lồi . . . . . . 16
2 Bài toán cực tiểu hàm lồi và hàm tựa lồi 22
iii
2.1 Bài toán cực tiểu hàm lồi . . . . . . . . . . . . . . . . . . . 22
2.1.1 Phát biểu bài toán, ví dụ . . . . . . . . . . . . . . . 22
2.1.2 Một thuật toán chiếu dưới đạo hàm . . . . . . . . . 28
2.2 Bài toán cực tiểu hàm tựa lồi . . . . . . . . . . . . . . . . . 28
2.2.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . 29
2.2.2 Một thuật toán chiếu dưới đạo hàm . . . . . . . . . 29
Kết luận 36
iv
Tài liệu tham khảo 37
Một số ký hiệu và chữ viết tắt
Rn không gian Euclide n−chiều
xT
trục số thực mở rộng R = R ∪ {−∞, +∞}
coA
chuyển vị của x
coA
bao lồi của A
ri(A)
bao lồi đóng của A
int(A)
tập điểm trong tương đối của tập A
f
tập hợp các điểm trong của A
domf
hàm bao đóng của f
epif
miền hữu dụng của f
∂f (x)
trên đồ thị của f
(cid:50)
dưới vi phân của f tại x
v
kết thúc chứng minh
Lời mở đầu
Ngày nay, lý thuyết về các tập lồi, hàm lồi và hàm tựa lồi có một ví
trí quan trọng trong toán học nói chung, trong giải tích nói riêng cụ thể liên
quan đến hầu hết các ngành như giải tích hàm, hình học, toán kinh tế, giải
tích lồi,...Trong đó có một tính chất cơ bản của hàm lồi được sử dụng rộng
rãi trong toán học đó là: bất kì cực tiểu địa phương nào cũng có cực tiểu
toàn cục.
Cực tiểu hàm lồi và hàm tựa lồi trên tập lồi là một lớp bài toán cơ
bản của tối ưu hóa. Cực tiểu hàm lồi trên tập lồi gọi là quy hoạch lồi, có
tính chất cơ bản là mọi điểm cực tiểu địa phương đều là cực tiểu tuyệt đối.
Tính chất quan trọng này cho phép các lý thuyết có tính địa phương như
giới hạn, vi phân,... có thể áp dụng vào quy hoạch lồi. Lý thuyết về bài toán
quy hoạch lồi đã được nghiên cứu nhiều và đã thu được nhiều kết quả quan
trọng dựa trên lý thuyết của giải tích lồi và tối ưu hóa.
Mục tiêu của luận văn là giới thiệu một số kiến thức cơ bản về hàm
lồi và hàm tựa lồi. Đặc biệt nội dung chính của luận văn sẽ tập trung đi
sâu vào dưới vi phân của hàm lồi và hàm tựa lồi. Tiếp đến sẽ giới thiệu hai
thuật toán chiếu dưới đạo hàm để giải bài toán cực tiểu hàm lồi và hàm tựa
lồi trên tập lồi.
Ngoài phần mở đầu, kết luận và danh mục tài liệu tham khảo, luận
văn gồm hai chương sau:
Chương 1. Hàm lồi, hàm tựa lồi trên tập lồi
1
Trong chương này chúng tôi giới thiệu tổng quan và trình bày về một
số khái niệm cơ bản, tính chất và ví dụ minh họa của tập lồi, hàm lồi, hàm
tựa lồi được trích dẫn trong tài liệu số [1] và [2], đặc biệt đi sâu vào khái
niệm dưới vi phân hàm lồi và hàm tựa lồi.
Chương 2. Bài toán cực tiểu hàm lồi và hàm tựa lồi
Đây là phần chính của luận văn, trong chương này, chúng tôi trình
bày bài toán cực tiểu hàm lồi và hàm tựa lồi, các ví dụ minh họa. Phần cuối
của luận văn sẽ trình bày về hai thuật toán chiếu dưới đạo hàm được trích
dẫn trong tài liệu số [2], [3], [4], [5] và [6].
2
Tôi xin chân thành cảm ơn!
Chương 1
Hàm lồi, hàm tựa lồi trên tập lồi
Chương mở đầu của luận văn chúng tôi trình bày khái niệm, một số
tính chất cơ bản của tập lồi, hàm lồi, hàm tựa lồi và các ví dụ minh họa.
Đặc biệt phần cuối của chương sẽ đi sâu vào khái niệm dưới vi phân hàm
lồi và hàm tựa lồi. Các kiến thức ở chương này được tổng hợp từ các tài
liệu [1] và [2].
1.1 Tập lồi
Phần mở đầu của chương này chúng tôi trình bày về một số định
1.1.1 Định nghĩa và ví dụ
nghĩa, ví dụ và các tính chất cơ bản của tập lồi.
Một đường thẳng nối hai điểm (hai véc tơ) a, b trong Rn là tập hợp
{x ∈ Rn | x = αa + βb, α, β ∈ R, α + β = 1} .
tất cả các véc tơ x ∈ Rn có dạng
{x ∈ Rn | x = αa + βb, α ≥ 0, β ≥ 0, α + β = 1} .
3
Đoạn thẳng nối hai điểm a và b trong Rn là tập hợp các véc tơ x có dạng
Định nghĩa 1.1.1. Một tập C ⊆ Rn được gọi là một tập lồi, nếu C chứa
∀x, y ∈ C, ∀λ ∈ [0, 1] ⇒ λx + (1 − λ)y ∈ C.
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
Ví dụ 1.1.2. Các tam giác và hình tròn trong mặt phẳng là các tập lồi.
Hình cầu đơn vị trong không gian Banach là tập lồi.
A được gọi là bao lồi (convex hull) của tập A và kí hiệu là coA.
Định nghĩa 1.1.3. Giả sử A ⊂ C, khi đó giao của tất cả các tập lồi chứa
• coA là một tập lồi. Đó là tập lồi nhỏ nhất chứa A.
• A lồi khi và chỉ khi A = coA.
Nhận xét 1.1.4. Từ định nghĩa trên ta rút ra được nhận xét sau:
Định nghĩa 1.1.5. Giả sử A ⊂ C, khi đó giao của tất cả các tập lồi đóng
chứa A được gọi là bao lồi đóng của tập A và kí hiệu là coA.
Nhận xét 1.1.6. coA là một tập lồi đóng. Đó là tập lồi đóng nhỏ nhất
1.1.2 Tổ hợp lồi và các tính chất cơ bản
chứa A.
λixi gọi là tổ hợp lồi của x1, . . . , xn ∈
n (cid:80) i=1
Định nghĩa 1.1.7. Tổ hợp tuyến tính
n (cid:88)
λi ≥ 0, ∀i,
λi = 1.
i=1
Rn nếu
Mệnh đề 1.1.8. Giả sử C là tập lồi, x1, . . . , xn ∈ C. Khi đó, C chứa tất
4
cả các tổ hợp lồi của x1, . . . , xn.
Định nghĩa 1.1.9. Một tập C được gọi là tập affine nếu nó chứa đường
∀x, y ∈ C, ∀λ ∈ R ⇒ λx + (1 − λ)y ∈ C.
thẳng đi qua hai điểm bất kỳ của nó, tức là
Vậy tập affine là một trường hợp riêng của tập lồi.
Định nghĩa 1.1.10. Tương tự như tổ hợp lồi, x được gọi là tổ hợp affine
k (cid:88)
k (cid:88)
x =
λjxj,
λj = 1, λj > 0, ∀j = 1, . . . , k.
j=1
j=1
của các điểm (véc tơ) x1, . . . , xn ∈ Rn nếu
Tập hợp của các tổ hợp affine của các điểm (véc tơ) x1, . . . , xn ∈ Rn thường
được gọi là bao affine của các điểm (véc tơ) này.
j=1 λjxj với các λj > 0, ∀j =
1, . . . , k sẽ được gọi là một tổ hợp lồi của các điểm (véc tơ) x1, ..., xk.
Nhận xét 1.1.11. Một tổ hợp affine x = (cid:80)k
Mệnh đề 1.1.12. Cho X là tập khác rỗng, X được gọi là tập affine khi và
chỉ khi nó có dạng X = L + a với L là một không gian con và a ∈ X. Hơn
nữa không gian con L này là duy nhất.
Định nghĩa 1.1.13. (Toán tử chiếu lên tập lồi đóng) Cho C là một tập lồi
dC(y) := inf||x − y|| ∀x ∈ C.
đóng khác rỗng của R. Gọi y là một véc tơ bất kì, đặt
dC(y) = ||π − y||, thì ta nói π là hình chiếu vuông góc của y trên C.
Khi đó ta nói dC(y) là khoảng cách từ y tới C. Nếu tồn tại π ∈ C sao cho
Định lý 1.1.14. (Định lý tồn tại duy nhất) Cho C là một tập lồi đóng khác
5
rỗng. Khi đó:
(i) Với mọi y ∈ R, π ∈ C hai tính chất sau là tương đương:
a) π = pC(y),
b) y − π ∈ NC(π), trong đó NC(π) là nón pháp tuyến của tập C tại π. (ii) Với mọi y ∈ Rn, hình chiếu pC(y) của y trên C luôn tồn tại và duy
nhất.
(iii) Nếu y /∈ C, thì (cid:104)pC(y) − y, x − pC(y)(cid:105) = 0 là siêu phẳng tựa của C
∀x ∈ C
(cid:104)pC(y) − y, x − pC(y)(cid:105) ≥ 0,
tại pC(y) và tách hẳn y khỏi C, tức là
(cid:104)pC(y) − y, y − pC(y)(cid:105) < 0.
và
(iv) Ánh xạ y (cid:44)→ pC(y) có các tính chất sau:
a) (cid:107)pC(x) − pC(y)(cid:107) ≤ (cid:107)x − y(cid:107) ∀x, ∀y, (tính không giãn). b) (cid:104)pC(x) − pC(y), x − y(cid:105) ≥ (cid:107)pC(x) − pC(y)(cid:107)2 , (tính đồng bức).
1.2 Hàm lồi
Trong mục này chúng tôi trình bày định nghĩa về hàm lồi, các tính
chất cơ bản của hàm lồi, ví dụ, đặc biệt đi sâu vào khái niệm, tính chất cơ
1.2.1 Định nghĩa, ví dụ
bản của dưới vi phân hàm lồi.
domf := {x ∈ C | f (x) < +∞}
Cho C ⊆ Rn là tập lồi và một ánh xạ f : C → R. Ta kí hiệu
epif := {(x, µ) ∈ C × R | f (x) ≤ µ}
6
Tập domf được gọi là miền hữu dụng (effective domain) của f. Tập
được gọi là trên đồ thị (epigraph) của hàm f.
Định nghĩa 1.2.1. Cho C là tập khác rỗng, C ⊆ Rn là lồi và f : C → R.
Khi đó ta nói f là hàm lồi (convex function) trên C, nếu epif là một tập
lồi trong Rn+1.
f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y),
∀x, y ∈ C, ∀λ ∈ (0, 1). (1.1)
Xét hàm f : Rn → R ∪ {+∞}, định nghĩa trên là tương đương với
Hàm f : Rn → R ∪ {+∞} được gọi là lồi chặt (strictly convex function)
f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y),
∀x, y ∈ C, ∀λ ∈ (0, 1). (1.2)
trên C nếu
Hàm f : Rn → R ∪ {+∞} được gọi là lồi mạnh (strongly convex function)
trên C với hệ số η > 0, nếu ∀x, y ∈ C, ∀λ ∈ (0, 1) ta có:
f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) −
ηλ(1 − λ)(cid:107)x − y(cid:107)2.
1 2
(1.3)
C, nếu −f lồi trên C.
Hàm f : Rn → R ∪ {+∞} được gọi là một hàm lõm (concave function) trên
Ví dụ 1.2.2. Hàm affine f (x) := aT x + α trong đó a ∈ Rn, α ∈ R được gọi
là hàm lồi. Hơn nữa khi α = 0, thì hàm trên được gọi là hàm tuyến tính.
Định nghĩa 1.2.3. Cho f : Rn → R ∪ {+∞} và C ⊆ Rn là một tập lồi
khác rỗng và η là một số thực. Ta nói η là hệ số lồi của f trên C, nếu với
ηλ(1 − λ)(cid:107)x − y(cid:107)2.
f [(1 − λ)x + λy] ≤ (1 − λ)f (x) + λf (y) −
1 2
mọi λ ∈ (0, 1), mọi x, y ∈ C, ta có:
Nếu η = 0 thì f là hàm lồi trên C. Hơn nữa nếu η > 0 thì f là hàm lồi
7
mạnh trên C với hệ số η.
f (x) > −∞ với mọi x. Hàm f được gọi là đóng (closed function), nếu epif
Một hàm f được gọi là chính thường (proper function) nếu domf (cid:54)= 0 và
là một tập đóng trong Rn+1.
Lf (α) := {x|f (x) ≤ α},
lf (α) := {x|f (x) < α}
Mệnh đề 1.2.4. Nếu f là một hàm lồi trên Rn thì các tập mức
1.2.2 Các tính chất cơ bản
là lồi với mọi α ∈ R.
Định nghĩa 1.2.5. Cho E là một tập lồi đóng khác rỗng, một hàm f :
Rn → 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 xk ⊂ E, xk → x ta có lim inff (xk) ≥ f (x). Hàm f được gọi là
nửa liên tục trên, đối với E, tại x nếu −f nửa liên tục dưới, đối với E, tại x.
Nói một cách khác với mọi dãy xk ⊂ E, xk → x thì lim supf (xk) ≤ f (x).
Hàm f được gọi là liên tục đối với E, tại x nếu như nó vừa nửa liên tục
trên và nửa liên tục dưới, đối với E, tại x.
Mệnh đề 1.2.6. (Tính liên tục) Cho f : Rn → R ∪ {+∞}, khi đó các điều
kiện sau là tương đương:
(i) Trên đồ thị của f là một tập đóng trên Rn+1, tức là f = f .
(ii) Với mọi số thực α, tập mức dưới Lf (α) := {x|f (x) ≤ α} là một tập
đóng.
(iii) Hàm f là nửa liên tục dưới trên R.
Chứng minh. Ta sẽ tiến hành chứng minh các điều kiện trên là tương đương:
8
(i) → (ii). Giả sử xj → x, f (xj) ≤ α. Khi đó (xj, α) ∈ epif .
Do đó epif đóng nên (x, α) ∈ epif . Vậy x ∈ Lf (α).
α < f (x) sao cho f (xj) ≤ α với mọi j đủ lớn. Vậy xj ∈ Lf (α).
(ii) → (iii). Giả sử xj → x. Nếu lim inff (xj) < f (x), khi đó tồn tại
Do xj → x và Lf (α) đóng nên x ∈ Lf (α). Tức là f (x) ≤ α điều này mâu
thuẫn với giả thiết α < f (x).
(iii) → (i). Giả sử (xj, µj) ∈ epif và (xj, µj) → (x, µ).
Khi đó f (xj) ≤ µj với mọi j. Do (iii), suy ra lim inff (xj) ≥ f (x).
Vậy µ ≥ f (x). Suy ra (x, µ) ∈ epif do đó epif là tập đóng.
int(domf ), khi đó các điều kiện sau là tương đương.
Mệnh đề 1.2.7. Cho f là một hàm lồi chính thường trên Rn và x0 ∈
(i) f liên tục tại điểm x0.
(ii) f bị chặn trên trong lân cận của x0.
(iii) int(epif ) (cid:54)= ∅.
(iv) int(domf ) (cid:54)= ∅ và f liên tục trên tập int(domf ).
f liên tục tại mọi điểm x ∈ int(domf ). Nếu f nhận giá trị thực trên toàn
Mệnh đề 1.2.8. Giả sử f là một hàm lồi chính thường trên Rn. Khi đó
không gian, thì nó liên tục tại mọi điểm.
Hệ quả 1.2.9. Cho f là một hàm lồi chính thường trên Rn. Khi đó với mọi
tập com-pắc C ⊆ int(domf ), tập f (C) là com-pắc.
Định nghĩa 1.2.10. Một hàm f : Rn → R được gọi là Lipschitz địa phương
||f (x) − f (y)|| (cid:54) L||x − y|| ∀x, y ∈ U.
tại x với hằng số Lipschitz L nếu tồn tại một lân cận U của x sao cho
Hàm f được gọi là Lipschitz địa phương trên D nếu nó Lipschitz địa phương
9
tại mọi điểm thuộc D.
Hàm lồi còn có tính liên tục Lipschitz. Mệnh đề sau đây sẽ chỉ ra mối liên
hệ đó.
Mệnh đề 1.2.11. (Tính Lipschitz) Giả sử f là một hàm lồi chính thường
trên Rn và bị chặn trên trong một lân cận của một điểm nào đó thuộc một
tập mở D ⊆ domf . Khi đó f Lipschitz địa phương trên tập D.
(cid:15) > 0 và B là quả cầu mở đơn vị có tâm ở gốc.
Chứng minh. Giả sử 0 ∈ D và f (x) ≤ γ < ∞ với mọi x ∈ (cid:15)B, trong đó
1 ρ
Giả sử x ∈ D. Khi đó tồn tại ρ > 1 sao cho điểm y = ρx ∈ D, Với λ =
V := {v|v = (1 − λ)x(cid:48) + λy, x(cid:48) ∈ B},
tập hợp
(cid:15)B, nên với mọi v ∈ V, ta có:
là một lân cận của điểm x := λy. Do f lồi và bị chặn trên bởi γ trong tập
f (v) ≤ (1 − λ)f (x(cid:48)) + λf (y) ≤ (1 − λ)γ + λf (y).
(1.4)
Vậy f bị chặn trên trong lân cận V của x.
(z + z(cid:48)). Vì f
1 2
Hơn nữa với mọi z ∈ V , tồn tại z(cid:48) ∈ V sao cho x =
f (x) ≤
f (z) +
f (z(cid:48)).
1 2
1 2
là hàm lồi nên ta có:
f (z) ≥ 2f (x) − f (z(cid:48)) ≥ 2f (x) − (1 − λ)γ − λf (y).
Từ đây và (1.4), ta được
Vậy f bị chặn dưới trên V. Kết hợp lại ta có f bị chặn trong tập V. Do D
|f (u)| ≤ L0 < ∞ với mọi u ∈ B(x). Lấy x1, x2 ∈ x + δB, x1 (cid:54)= x2. Ký hiệu
α = ||x1 − x2|| và đặt
mở thuộc domf . Chọn δ > 0 sao cho quả cầu B(x) := x + 2δB ⊂ D và
(x2 − x1).
x3 = x2 +
δ α
10
(1.5)
x2 =
x1 +
x3
δ α + δ
α α + δ
Khi đó x3 ∈ B(x), bởi vì x2 ∈ x + δB. Theo (1.5) ta có:
f (x1) +
f (x3)
f (x2) ≤
δ α + δ
α α + δ
Do f lồi, nên
[f (x3) − f (x1)]
≤
|f (x3) − f (x1)| ≤
(|f (x1)| + |f (x3)|)
f (x2) − f (x1) ≤ α δ
α α + δ α δ
Suy ra
f (x2) − f (x1) ≤
(cid:107)x1 − x2(cid:107)
2L0 δ
Do |f (x1)| ≤ L0, |f (x3)| ≤ L0 và α = (cid:107)x1 − x2(cid:107) , nên ta có:
(cid:107)x1 − x2(cid:107)
f (x1) − f (x2) ≤
2L0 δ
Thay đổi vai trò của x1 và x2, ta có:
||x1 − x2|| ∀x1, x2 ∈ x + δB
|f (x1) − f (x2)| ≤
2L0 δ
Kết hợp lại
.
2L0 δ
Vậy f Lipschizt trong lân cận x + δB của x với hằng số là L =
Hệ quả 1.2.12. Nếu f : Rn → R lồi, thì f Lipschitz địa phương trên toàn
1.2.3 Dưới vi phân của hàm lồi
Rn (do đó liên tục).
Cho một hàm n biến. Khi cố định một hướng và xét hàm nhiều biến
trên hướng đó, thì ta có một hàm một biến. Giả sử y (cid:54)= 0 là một hướng cho
ζ(λ) := f (x0 + λy)
11
trước xuất phát từ điểm x0. Khi đó mọi điểm x thuộc đường thẳng đi qua x0 và có hướng y đều có dạng x = x0 + λy với λ ∈ R. Nếu đặt
suy ra ζ lồi trên R khi và chỉ khi f lồi trên Rn.
Định nghĩa 1.2.13. (Đạo hàm theo hướng)
lim x→0
f (x0 + λy) − f (x0) λ
Cho f : Rn → R ∪ {+∞} và x0 ∈ R sao cho f (x0) < +∞. Nếu với một véc tơ y ∈ Rn mà giới hạn
x0.
tồn tại (hữu hạn hay vô hạn), thì ta nói f có đạo hàm theo hướng y tại điểm
Ta sẽ ký hiệu giới hạn này là f (cid:48)(x0, y).
Định nghĩa 1.2.14. (Dưới vi phân)
Cho f : Rn → R ∪ {+∞} ta nói x∗ ∈ Rn là dưới đạo hàm của hàm f tại x
(cid:104)x∗, z − x(cid:105) + f (x) (cid:54) f (z) ∀z.
nếu
∂f (x) có thể bằng rỗng trong Rn. Khi ∂f (x) (cid:54)= ∅, thì ta nói hàm f khả dưới
Ký hiệu tập hợp tất cả các dưới đạo hàm của f tại x là ∂f (x). Tập
vi phân tại x. Theo định nghĩa trên, một điểm x∗ ∈ ∂f (x) khi và chỉ khi
nó thỏa mãn một hệ vô hạn các bất đẳng thức tuyến tính. Như vậy ∂f (x)
là giao của các nửa không gian đóng. Vậy ∂f (x) luôn là một tập lồi đóng.
Ví dụ 1.2.15. Cho hàm f (x) = ||x||, x ∈ Rn. Tại điểm x = 0 hàm này
∂f (0) = {x∗| (cid:104)x∗, x(cid:105) (cid:54) ||x||, ∀x} .
không khả vi, nhưng nó khả dưới vi phân và
Mệnh đề 1.2.16. Cho f : Rn → R ∪ {+∞} là hàm lồi, chính thường. Khi
đó ta có:
12
(i) x∗ ∈ ∂f (x) khi và chi khi f (cid:48)(x, y) ≥ (cid:104)x∗, y(cid:105) ∀y. Nếu x ∈ ri(domf ) thì
f (cid:48)(x, y) = supx∗∈∂f (x) (cid:104)x∗, y(cid:105) với mọi y. (ii) Nếu f là hàm lồi chính thường trên Rn thì với mọi x ∈ dom(∂f ), ta có: f (x) = ¯f (x) và ∂f (x) = ∂ ¯f (x).
Mệnh đề 1.2.17. Cho f : Rn → R ∪ {+∞} là hàm lồi, chính thường. Khi
đó
(i) Nếu x /∈ dom f thì ∂f (x) = ∅.
(ii) Nếu x ∈ int(domf ) thì ∂f (x) (cid:54)= ∅ và com-pắc. Ngược lại, nếu ∂f (x) (cid:54)=
∅, com-pắc thì x ∈ ri(domf ).
1.3 Hàm tựa lồi
Trong mục này chúng tôi trình bày định nghĩa về hàm tựa lồi, các
tính chất cơ bản của hàm lồi, ví dụ minh họa, đặc biệt đi sâu vào khái niệm,
1.3.1 Định nghĩa, ví dụ
tính chất cơ bản của dưới vi phân hàm tựa lồi.
Γ ⊂ Rn được gọi là tựa lồi (quasiconvex) tại x ∈ Γ nếu
Định nghĩa 1.3.1. Cho Γ là một tập con của Rn, một hàm θ xác định trên
x ∈ Γ
θ(x) ≤ θ(¯x)
⇒ θ[(1 − λ)¯x + λx] ≤ θ(¯x),
0 ≤ λ ≤ 1
(1 − λ)¯x + λx ∈ Γ
θ được gọi là tựa lồi trên Γ nếu nó là tựa lồi tại mỗi điểm x ∈ Γ.
13
Định nghĩa 1.3.2. Một hàm θ xác định trên Γ ⊂ Rn được gọi là tựa lồi
chặt (strictly quasiconvex) tại x ∈ Γ nếu
x ∈ Γ
θ(x) < θ(¯x)
⇒ θ[(1 − λ)¯x + λx] < θ(¯x),
0 < λ < 1
(1 − λ)¯x + λx ∈ Γ
θ được gọi là tựa lồi chặt trên Γ nếu nó là tựa lồi chặt tại mỗi điểm x ∈ Γ.
Theo định nghĩa trên một hàm θ xác định trên tập lồi Γ là tựa lồi chặt nếu
x1, x2 ∈ Γ
và chỉ nếu
⇒ θ[(1 − λ)x1 + λx2] < θ(x1).
θ(x2) < θ(x1)
0 < λ < 1
(cid:43)
Ví dụ 1.3.3. Cho hàm số y = x3 hàm số này được gọi là hàm tựa lồi hơn
1.3.2 Các tính chất cơ bản
nữa nó còn là hàm tựa lồi chặt.
Λα = {x | x ∈ Γ, θ(x) ≤ α}
Định lý 1.3.4. Cho θ là một hàm xác định trên tập lồi Γ ⊂ Rn, đặt
Khi đó θ là tựa lồi trên Γ ⇔ Λα là tập lồi với mỗi α ∈ R.
Chứng minh. “⇒” Chọn x1, x2 ∈ Γ, θ (cid:0)x2(cid:1) ≤ θ (cid:0)x1(cid:1) và 0 ≤ λ ≤ 1. Nếu ta đặt α = θ (cid:0)x1(cid:1) thì theo tính lồi của Λα khi đó ta có:
(cid:2)(1 − λ)x1 + λx2(cid:3) ≤ α = θ (cid:0)x1(cid:1) ,
và do đó θ là tựa lồi trên Γ.
14
“⇐” Đặt θ là tựa lồi trên Γ, α là một số thực và đặt x1, x2 lần lượt là các
điểm trên Λα. Không mất tính tổng quát ta đặt θ(x2) ≤ θ(x1).
Vì x1, x2 ∈ Λα nên θ(x2) ≤ θ(x1) ≤ α.
θ (cid:2)(1 − λ)x1 + λx2(cid:3) ≤ θ (cid:0)x1(cid:1) ≤ α.
Do θ là tựa lồi, Γ là tập lồi nên 0 ≤ λ ≤ 1 và
Do đó (1 − λ)x1 + λx2 ∈ Λα và Λα là tập lồi.
Định nghĩa 1.3.5. Cho θ là một hàm xác định trên Γ ⊂ Rn. Khi đó một
điểm x ∈ Γ được gọi là cực tiểu địa phương (local minimum) hay cực đại
địa phương (local maximum) của θ nếu tồn tại một hình cầu mở Bδ(¯x) xung
quanh x với bán kính δ > 0
x ∈ Bδ(¯x) ∩ Γ ⇒ θ(¯x) ≤ θ(x)
(local minimum),
x ∈ Bδ(¯x) ∩ Γ ⇒ θ(x) ≤ θ(¯x)
(local maximum).
Định lý 1.3.6. Cho θ là một hàm xác định trên tập lồi Γ ⊂ Rn, đặt x ∈ Γ
θ(x) sẽ là cực tiểu toàn cục (cực đại toàn cục) của θ trên Γ.
là cực tiểu địa phương (cực đại địa phương). Nếu θ là tựa lồi chặt tại x, thì
Chứng minh. Nếu x là cực tiểu địa phương (cực đại địa phương), thì tồn tại
x ∈ Bδ(x) ∩ Γ ⇒ θ(x) ≤ θ(x).
một hình cầu Bδ(x) sao cho
0 < λ < 1.
Giả sử tồn tại (cid:98)x ∈ Γ nhưng (cid:98)x /∈ Bδ(x) sao cho θ((cid:98)x) < θ(x). Theo tính tựa lồi chặt của θ tại x và tính lồi của Γ ta có:
θ[(1 − λ)x + λ(cid:98)x] < θ(x), δ ||(cid:98)x − x||
(1 − λ)x + λ(cid:98)x ∈ Bδ(x) ∩ Γ.
15
, nên ta có: Nhưng vì λ <
0 < λ <
.
θ(x) ≤ θ[(1 − λ)x + λ(cid:98)x],
δ ||(cid:98)x − x||
1.3.3 Đạo hàm và dưới vi phân của hàm tựa lồi
Và do đó
Định lý 1.3.7. Cho Γ là một tập mở trên R và đặt θ là một hàm khả vi
x1, x2 ∈ Γ
trên Γ. Khi đó
(cid:42) (cid:43)
θ là khả vi
và (cid:10)θ (cid:0)x2(cid:1) ≤ θ (cid:0)x1(cid:1) ⇒ ∇θ (cid:0)x1(cid:1) (cid:0)x2 − x1(cid:1) ≤ 0(cid:11)
Γ là lồi , θ là khả vi trên Γ
và tựa lồi tại x1
θ tựa lồi trên Γ ⇐
⇒ ∇θ (cid:0)x1(cid:1) (cid:0)x2 − x1(cid:1) ≤ 0
θ (cid:0)x2(cid:1) ≤ θ (cid:0)x1(cid:1)
(cid:42) (cid:43) (cid:43) (cid:42) x1, x2 ∈ Γ
Chứng minh. “⇒” Nếu x1 = x2 trường hợp này là tầm thường.
δ ||x2 − x1||
, ta có: Giả sử rằng x1 (cid:54)= x2. Do Γ là tập mở, khi đó tồn tại hình cầu mở Bδ(x1) quanh x1 ⊂ Γ. Thì với mỗi (cid:101)µ sao cho 0 < (cid:101)µ < 1 và (cid:101)µ <
(cid:101)x = x1 + (cid:101)µ(x2 − x1) = (1 − (cid:101)µ)x1 + (cid:101)µx2 ∈ Bδ(x1) ⊂ Γ
θ(x2) ≤ θ(x1) ⇒ θ((cid:101)x) ≤ θ(x1)
thì
⇒
(cid:43)
(cid:42) θ[(1 − λ)x1 + λ(cid:101)x] ≤ θ(x1) 0 < λ ≤ 1
λ∇θ(x1)((cid:101)x − x1) + α[x1, λ((cid:101)x − x1)]λ (cid:13)
⇒
0 < λ ≤ 1
α[x1, λ((cid:101)x − x1)] = 0
lim λ→0
16
(cid:13) ≤ 0 (cid:13)(cid:101)x − x1(cid:13) (cid:43) (cid:42)
⇒
0 < λ ≤ 1
⇒ ∇θ(x1)((cid:101)x − x1) ≤ 0, (λ → 0) ⇒ ∇θ(x1)(x2 − x1) ≤ 0, ((cid:101)µ > 0).
(cid:43) (cid:13) ≤ 0 (cid:42) ∇θ(x1)((cid:101)x − x1) + α[x1, λ((cid:101)x − x1)] (cid:13) (cid:13)(cid:101)x − x1(cid:13)
(x1, x2) = {x|x = (1 − λ)x1 + λx2, 0 < λ < 1}
“⇐” Đặt x1, x2 ∈ Γ và θ(x2) ≤ θ(x1) sao cho
Ω = {x|θ(x1) < θ(x), x ∈ (x1, x2)}.
và
Bây giờ ta sẽ chỉ ra tính tựa lồi của θ trên Γ bằng cách chỉ ra rằng Ω là tập
rỗng.
Thật vậy giả sử rằng tồn tại x ∈ Ω.
∇θ(x)(x1 − x) ≤ 0,
(x ∈ Ω)
Do θ(x2) ≤ θ(x1) < θ(x) với x ∈ Ω, theo giả thiết của định lý ta có:
∇θ(x)(x2 − x) ≤ 0,
(x ∈ Ω).
và
(x ∈ Ω).
Do 0 < λ < 1, điều đó kéo theo ∇θ(x)(x2 − x1) = 0,
Và do θ(x1) < θ(x) và θ là liên tục trên Γ suy ra Ω là tập mở đối với (x1, x2),
0 < µ ≤ 1, sao cho x3 là
nó chứa x do đó tồn tại x3 = (1 − µ)x + µx1,
0 < θ(x) − θ(x1) = θ(x) − θ(x3)∇θ((cid:101)x)(x − x3) = µ∇θ((cid:101)x)(x − x1).
điểm đóng của Ω, suy ra θ(x3) = θ(x1). Vậy với (cid:101)x ∈ Ω ta có:
x = (1 − λ)x1 + λx2 với mọi λ, 0 < λ < 1,
17
Hơn nữa
0 < µ∇θ((cid:98)x)(x − x1) = µλ∇θ((cid:98)x)(x2 − x1) với mọi λ > 0, µ > 0.
nên
∇θ(x)(x2 − x1) = 0, với mọi (x ∈ Ω).
Do (cid:98)x ∈ Ω, ta suy ra mâu thuẫn. Vậy
Định nghĩa 1.3.8. Cho θ là một hàm khả vi trên một tập mở Γ ⊂ Rn. θ
x ∈ Γ
được gọi là giả lồi tại x ∈ Γ nếu nó phân biệt tại x và thỏa mãn
⇒ θ(x) ≥ θ(x)
∇θ(x)(x − x) ≥ 0
θ được gọi là giả lồi trên Γ nếu nó là giả lồi tại mỗi điểm x ∈ Γ.
Định lý 1.3.9. Cho θ là một hàm khả vi trên tập mở Γ ⊂ Rn và x ∈ Γ.
Khi đó ta có:
θ(x) ⇒ ∇θ(x)(x − x) ≥ 0 với mọi x ∈ Γ,
θ(x) = min x∈Γ
θ(x) ⇒ ∇θ(x)(x − x) ≤ 0 với mọi x ∈ Γ.
θ(x) = max x∈Γ
(i) Nếu Γ là lồi, thì
θ(x) ⇐ ∇θ(x)(x − x) ≥ 0 với mọi x ∈ Γ,
θ(x) = min x∈Γ
θ(x) ⇐ ∇θ(x)(x − x) ≤ 0 với mọi x ∈ Γ.
θ(x) = max x∈Γ
(ii) Nếu θ là giả lồi tại x. Thì
(1 − λ)x + λx ∈ Γ với 0 ≤ λ ≤ 1.
18
Chứng minh. (i) Đặt x là một điểm thuộc Γ. Do Γ là lồi nên
0 < θ[(1 − λ)x + λx] − θ(x) = λ∇θ(x)(x − x) + α[x, λ(x − x)]λ||x − x||,
α[x, λ(x − x)] = 0.
, nên ta có: Hơn nữa θ là đạo hàm tại x và θ(x) = min x∈Γ
trong đó lim λ→0
Do đó ∇θ(x)(x − x) + α[x, λ(x − x)]||x − x|| ≥ 0 với 0 < λ ≤ 1.
∇θ(x)(x − x) ≥ 0.
Bằng cách cho giới hạn λ dần về 0, ta có:
θ(x) ⇒ ∇θ(x)(x − x) ≥ 0 với mọi x ∈ Γ,
θ(x) = min x∈Γ
θ(x) ⇒ ∇θ(x)(x − x) ≤ 0 với mọi x ∈ Γ.
θ(x) = max x∈Γ
Vậy
.
θ(x) = min x∈Γ
(ii) Với mỗi x thuộc Γ ta có: ∇θ(x)(x − x) ≥ 0, suy ra θ(x) ≥ θ(x) và
Định lý 1.3.10. Cho θ là một hàm khả vi trên tập mở Γ ⊂ Rn và x ∈ Γ.
Nếu θ là lồi tại x, thì θ là giả lồi tại x, điều ngược lại là chưa chắc đúng.
θ(x) − θ(x) ≥ ∇θ(x)(x − x) với mỗi x ∈ Γ.
Chứng minh. Đặt θ là lồi tại x, ta có:
x ∈ Γ
⇒ θ(x) ≥ θ(x).
∇θ(x)(x − x) ≤ 0
Do đó (cid:43)
Và do θ là giả lồi tại x. Điều đó không nhất thiết phải đúng, có thể chỉ ra
θ(x) = x + x3,
x ∈ R
θ không phải là hàm lồi trên R vì ∇2θ(x) < 0 với x < 0. Tuy nhiên, θ là
qua ví dụ sau
∇θ(x) = 1 + 3x2 > 0
19
giả lồi trên R bởi vì
∇θ(x)(x − x) ≥ 0 ⇒ x − x ≥ 0 ⇒ x3 ≥ (x)3.
và
Suy ra ⇒ θ(x) − θ(x) = x + x3 − x − (x)3 ≥ 0.
{+∞}. Khi đó dưới vi phân (subdifferential) theo Greenberg-Pierskalla của
Định nghĩa 1.3.11. Cho C là một tập mở trên Rn, hàm ϕ : Rn → R ∪
∂GP ϕ(x) := { g ∈ Rn : (cid:104)g, y − x(cid:105) ≥ 0 ⇒ ϕ(y) (cid:62) ϕ(x)} .
hàm tựa lồi ϕ được định nghĩa bởi:
Một biến thể khác của dưới vi phân-GP là dưới vi phân-sao (star-subdifferential)
được định nghĩa bởi:
∂∗ϕ(x) :=
{ g ∈ Rn : (cid:104)g, y − x(cid:105) > 0 ⇒ ϕ(y) ≥ ϕ(x)} nếu x /∈ D∗ Rn nếu x ∈ D∗,
trong đó D∗ là tập các điểm cực tiểu của ϕ trên Rn. Nếu ϕ là liên tục trên Rn thì ∂GP ϕ(x) = ∂∗ϕ(x).
Bổ đề 1.3.12. Nếu ϕ : Rn → R ∪ {+∞} là liên tục và tựa lồi trên domϕ,
∂GP ϕ(x) (cid:54)= ∅ ∀x ∈ domϕ
thì
∂∗ϕ(x) = ∂GP ϕ(x) ∪ {0}
và
0 ∈ ∂GP ϕ(x) ⇔ ∂GP ϕ(x) = Rn ⇔ x ∈ arg min
ϕ(y).
y∈Rn
và
a(x) b(y)
Bổ đề 1.3.13. Giả sử ϕ(x) = với mọi x ∈ domϕ, trong đó a là một
hàm lồi, b là hữu hạn dương trên domϕ, domϕ là lồi và một trong các điều
20
kiện sau được thỏa mãn
• b là affine.
• a là không âm trên domϕ và b là lõm.
α = ϕ(x), trong đó ∂ là dưới vi phân hiểu theo nghĩa giải tích lồi.
Khi đó ϕ là tựa lồi và ∂(a − αb)(x) là một tập con của ∂GP ϕ(x), với
Kết luận: Trong chương này chúng tôi đã trình bày các khái niệm về tập
lồi, hàm lồi và hàm tựa lồi cùng với các ví dụ minh họa cho các định nghĩa
trên. Phần cuối chương đi sâu vào trình bày về đạo hàm và dưới vi phân
21
của hàm lồi và hàm tựa lồi.
Chương 2
Bài toán cực tiểu hàm lồi và hàm
tựa lồi
Trong chương này, chúng tôi sẽ trình bày bài toán cực tiểu hàm lồi và
hàm tựa lồi, cùng với các ví dụ minh họa. Phần cuối của chương này đi sâu
trình bày hai thuật toán chiếu dưới đạo hàm. Các kiến thức trong chương
này được trích dẫn từ tài liệu số [2], [3], [4], [5] và [6].
2.1 Bài toán cực tiểu hàm lồi
Trong mục này chúng tôi trình bày về bài toán cực tiểu hàm lồi, ví
dụ minh họa và trình bày một thuật toán chiếu dưới đạo hàm, khảo sát sự
2.1.1 Phát biểu bài toán, ví dụ
hội tụ của thuật toán.
Định nghĩa 2.1.1. Cho C là một tập lồi đóng khác rỗng của Rn và f :
Rn → R. Một điểm x∗ ∈ C được gọi là cực tiểu địa phương của f trên C
f (x∗) ≤ f (x),
∀x ∈ U ∩ C.
22
nếu tồn tại một lân cận U của x∗ sao cho
f (x) ≤ f (x∗),
∀x ∈ U ∩ C.
Điểm x∗ ∈ C được gọi là cực đại địa phương nếu
f (x) ≥ f (x∗),
∀x ∈ C,
Nếu
thì x∗ được gọi là cực tiểu toàn cục hay cực tiểu tuyệt đối của f trên C và
f (x) ≤ f (x∗),
∀x ∈ C,
nếu
thì x∗ được gọi là cực đại toàn cục hay cực đại tuyệt đối của f trên C.
Mệnh đề dưới đây cho thấy mọi điểm cực tiểu địa phương của một
hàm lồi trên một tập lồi cũng chính là điểm cực tiểu tuyệt đối. Điều này rất
quan trọng vì nó cho phép sử dụng các công cụ mang tính địa phương như
phép tính vi phân trong việc xây dựng lý thuyết và các phương pháp giải
cho bài toán này.
Mệnh đề 2.1.2. Cho hàm f : Rn → R ∪ {+∞} lồi. Khi đó mọi điểm cực
tiểu địa phương của f trên một tập lồi đều là cực tiểu toàn cục. Hơn nữa
tập hợp các điểm cực tiểu của f là một tập lồi. Nếu f lồi chặt, thì điểm cực
tiểu, nếu tồn tại, sẽ duy nhất.
Chứng minh. Cho C là một tập lồi đóng khác rỗng của Rn. Giả sử x∗ là
điểm cực tiểu địa phương của f trên C. Khi đó tồn tại lân cận U của x∗
f (x) ≥ f (x∗),
∀x ∈ U ∩ C.
sao cho
xλ := (1 − λ)x∗ + λx ∈ C ∩ U khi λ đủ nhỏ. Do f (x∗) ≤ f (xλ) và f lồi,
Với mọi x ∈ C và 0 < λ < 1, do C lồi và U là lân cận của x∗ ∈ C nên điểm
f (x∗) ≤ f (xλ) ≤ (1 − λ)f (x∗) + λf (x).
23
ta có:
C.
Từ đây suy ra f (x∗) ≤ f (x). Chứng tỏ x∗ là cực tiểu toàn cục của f trên
f (y∗) ≤ f (x) với mọi x ∈ C. Lấy z∗ := λx∗ + (1 − λ)y∗ với 0 < λ < 1. Do
C lồi nên z∗ ∈ C và do f lồi nên
f (z∗) ≤ λf (x∗) + (1 − λ)f (y∗) ≤ f (x).
Giả sử x∗, y∗ ∈ C là các điểm cực tiểu của f trên C. Vậy f (x∗) =
Suy ra z∗ cũng là điểm cực tiểu của f trên C. Chứng tỏ tập các điểm cực
tiểu của f trên C là lồi. Dễ thấy rằng tập hợp này chỉ gồm nhiều nhất một
điểm khi f lồi chặt.
Mệnh đề trên mang tính chất định tính. Mệnh đề dưới đây mang
nhiều tính chất định lượng. Ta hãy xét bài toán tìm cực tiểu một hàm lồi
(OP )
trên một tập lồi có dạng sau:
min f (x) với các điều kiện gi(x) ≤ 0, i = 1, . . . , m hj(x) = 0, j = 1, . . . , k x ∈ X,
j=1 µjhj(x) = 0 với
trong đó X ⊆ Rn là một tập lồi đóng khác rỗng và f, gi(i = 1, . . . , m) là các hàm lồi hữu hạn trên X, còn hj(j = 1, . . . , k) là các hàm affine hữu hạn
trên tập affine của X. Ta sẽ luôn giả sử rằng X có điểm trong và các hàm affine hj(j = 1, . . . , k) độc lập tuyến tính trên X nếu (cid:80)k mọi x ∈ X thì µj = 0 với mọi j.
Bài toán (OP ) này được gọi là một bài toán quy hoạch lồi. Hàm f được
0, (j = 1, . . . , k) được gọi là các ràng buộc. Tập
D := {x ∈ X | gi(x) ≤ 0,
i = 1, . . . , m, hj(x) = 0, j = 1, . . . , k}
gọi là hàm mục tiêu. Các điều kiện x ∈ X, gi(x) ≤ 0(i = 1, . . . m), hj(x) =
được gọi là miền chấp nhận được. Một điểm x ∈ D được gọi là điểm chấp
24
nhận được của bài toán (OP ). Do X là tập lồi, các hàm gi(i = 1, . . . , m)
lồi trên X và hj(j = 1, . . . , k) affine nên D là một tập lồi. Điểm cực tiểu
của f trên D cũng được gọi là nghiệm tối ưu của bài toán (OP ). Ta xây
m (cid:88)
k (cid:88)
L(x, λ, µ) := λ0f (x) +
λigi(x) +
µjhj(x).
i=1
j=1
dựng hàm sau được gọi là hàm Lagrange, cho bài toán (OP ):
Định lý 2.1.3. (Karush-Kuhn-Tucker). Nếu x∗ là nghiệm của bài toán quy
(j = 1, . . . , k)
i ≥ 0 (i = 0, 1, . . . , m) và µ∗ j
hoạch lồi (OP ) thì tồn tại λ∗
L (x∗, λ∗, µ∗) = minx∈X L (x, λ∗, µ∗) (điều kiện đạo hàm triệt tiêu),
i gi (x∗) = 0 (i = 1, . . . , m) (điều kiện độ lệch bù). λ∗
không đồng thời bằng 0 sao cho
Hơn nữa nếu intX (cid:54)= ∅ và điều kiện Slater sau thoả mãn
∃x0 ∈ D : gi
(cid:0)x0(cid:1) < 0 (i = 1, . . . , m)
0 > 0 và hai điều kiện đạo hàm triệt tiêu và độ lệch bù ở trên, cũng là điều kiện đủ để điểm chấp nhận được x∗ là nghiệm tối ưu của bài toán
thì λ∗
(OP).
C := {(λ0, λ1, . . . , λm, µ1, . . . , µk) | (∃x ∈ X) :
f (x) − f (x∗) < λ0, gi(x) ≤ λi, i = 1, . . . , m, hj(x) = µjj = 1, . . . , k}
Chứng minh. Giả sử x∗ là nghiệm của (OP ). Đặt
Do X (cid:54)= ∅ lồi, f, gi lồi và hj affine hữu hạn trên X nên C là một tập lồi, khác rỗng trong Rm+k+1. Hơn nữa 0 /∈ C. Thật vậy, vì nếu ngược lại 0 ∈ C
thì tồn tại một điểm chấp nhận được x thoả mãn f (x) < f (x∗), điều này
25
mâu thuẫn với việc x∗ là nghiệm tối ưu của (OP ).
(j = 1, . . . , k) không đồng
(i = 0, 1, . . . , m), µ∗ j
Khi đó tồn tại λ∗ i
m (cid:88)
k (cid:88)
λ∗ i λi +
µ∗ jµj ≥ 0 ∀ (λ0, . . . , λm, µ1, . . . , µk) ∈ C.
i=0
j=1
thời bằng 0 sao cho
Chú ý rằng với mọi λ0, . . . , λm > 0, thì (λ0, . . . , λm, 0, . . . , 0) ∈ C, vì theo
định nghĩa của C ta chỉ lấy x = x∗. Từ chú ý này, ta suy ra ngay tất
0, λ∗
1, . . . , λ∗
m ≥ 0. Hơn nữa, với mọi (cid:15) > 0 và x ∈ X ta lấy λ0 = f (x) − f (x∗) + (cid:15), λi = gi(x)(i = 1, . . . , m), µj = hj(x) (i = 1, . . . , k) và cho
(cid:15) → 0, sẽ được
i gi(x) + (cid:80)k
i=1 µ∗
0f (x∗) + (cid:80)m λ∗
i=1 λ∗ i gi (x∗) + (cid:80)k
i hi(x) ≥ i hi (x∗) ∀x ∈ X.
0f (x) + (cid:80)m λ∗ i=1 λ∗
i=1 µ∗
cả λ∗
L (x∗, λ∗, µ∗) ≤ L (x, λ∗, µ∗) ∀x ∈ X.
Hay
Đây chính là điều kiện đạo hàm triệt tiêu.
Để chứng minh điều kiện độ lệch bù, ta chú ý rằng do x∗ chấp nhận
ξ < 0, thì với mọi (cid:15) > 0, ta có:
((cid:15), . . . , ξ, (cid:15), . . . , (cid:15), 0, . . . , 0) ∈ C(ξ ở vị trí thứ i + 1).
được, nên gi (x∗) ≤ 0 với mọi i. Nếu như tồn tại một i nào đó mà gi (x∗) =
i ξ ≥ 0. Nhưng ξ < 0, nên λ∗
i ≤ 0. Suy ra λ∗
i = 0. Điều
Cho (cid:15) → 0, ta thấy λ∗
kiện độ lệch bù do đó cũng được thoả mãn.
Để chứng minh điều kiện đủ, ta giả sử điều kiện Slater thoả mãn. Ta
0 > 0. Thật vậy, vì nếu λ∗
0 = 0, thì do điều kiện đạo hàm triệt tiêu và
có λ∗
m (cid:88)
k (cid:88)
m (cid:88)
k (cid:88)
0 =
i gi (x∗) + λ∗
jhj (x∗) ≤ µ∗
λ∗ i gi(x) +
µ∗ jhj(x)∀x ∈ X.
i=1
j=1
i=1
j=1
26
điều kiện độ lệch bù, ta có:
0 = 0, nên phải có hoặc λ∗
i > 0 với một i nào đó, hoặc nếu
j > 0 với một j nào đó. Trong trường hợp đầu,
i = 0 với mọi i, thì sẽ có µ∗ λ∗ thay x0 vào bất đẳng thức trên, sẽ được
m (cid:88)
k (cid:88)
m (cid:88)
k (cid:88)
0 =
Thế nhưng do λ∗
λ∗ i gi (x∗) +
jhj (x∗) ≤ µ∗
λ∗ i gi
µ∗ jhj
i=1
j=1
i=1
j=1
(cid:0)x0(cid:1) + (cid:0)x0(cid:1) < 0.
Mâu thuẫn.
k (cid:88)
k (cid:88)
0 =
jhj (x∗) ≤ µ∗
µ∗ jhj(x)∀x ∈ X.
j=0
j=0
jhj(x) =
j=0 µ∗
Trong trường hợp sau, ta có:
j = 0
Do intX (cid:54)= ∅ và hj affine với mọi j, nên từ đây suy ra (cid:80)k 0, ∀x ∈ X. Từ đây và do các hàm hj độc lập tuyên tính trên X, ta có µ∗
i và µ∗
j không
với mọi j. Điều này mâu thuẫn với việc tất cả các nhân tử λ∗
đồng thời bằng 0. Vậy λ∗
0 > 0, ta có thể coi hàm Lagrange
0 > 0. 0 > 0 nên bằng cách chia cho λ∗
Do λ∗
m (cid:88)
k (cid:88)
L(x, λ, µ) = f (x) +
λigi(x) +
µjhj(x).
i=1
j=1
là
Do điều kiện đạo hàm triệt tiêu và độ lệch bù nên với mọi x chấp nhận
i=1 λigi (x∗) + (cid:80)k
j=1 µjhj (x∗)
f (x∗) = f0 (x∗) + (cid:80)m ≤ f (x) + (cid:80)m
i=1 λigi(x) + (cid:80)k
j=1 µjhj(x) ≤ f (x).
được, ta có:
Chứng tỏ x∗ là lời giải tối ưu của (OP ).
Chú ý 2.1.4. Khi X là tập mở (nói riêng là toàn không gian) và mọi hàm
m (cid:88)
k (cid:88)
0 = λ∗
0∇f0 (x∗) +
j∇gj (x∗) + λ∗
i ∇hi (x∗) . µ∗
j=1
i=1
27
đều khả vi thì điều kiện đạo hàm triệt tiêu sẽ là
2.1.2 Một thuật toán chiếu dưới đạo hàm
Thuật toán
Chọn điểm x0 ∈ X và {βk} là dãy các số dương thỏa mãn
β2 j < +∞.
(cid:88)
xk+1 := PD
Tại mỗi bước lặp k(k = 0, 1, . . .) ta có xk ∈ X. Lấy gk ∈ ∂f (xk) và tính
(cid:0)xk − αkgk(cid:1) ,
(cid:13)gk(cid:13) (cid:9). (cid:13)
với γk := max (cid:8)1, (cid:13) trong đó αk := βk γk a) Nếu xk+1 = xk thì xk là nghiệm của bài toán (OP ).
b) Ngược lại, thay xk bằng xk+1 và tiếp tục bước lặp k với k := k + 1.
Chú ý rằng thuật toán này có thể áp dụng với D là một tập lồi đóng bất
kỳ.
Định lý 2.1.5. (Định lý hội tụ)
Giả sử hàm tựa lồi liên tục, khả dưới vi phân sao trên tập mở chứa tập D,
M inf (x) với x ∈ D,
và giả sử bài toán
có nghiệm.
Ngoài ra giả thiết thêm rằng dãy {xk} bị chặn. Khi đó nếu thuật toán kéo
dài vô hạn, thì dãy lặp {xk} sẽ hội tụ đến một nghiệm tối ưu của bài toán.
2.2 Bài toán cực tiểu hàm tựa lồi
Trong mục này chúng tôi trình bày bài toán cực tiểu hàm tựa lồi, ví
dụ minh họa và trình bày một thuật toán chiếu dưới đạo hàm, khỏa sát sự
28
hội tụ của thuật toán.
2.2.1 Phát biểu bài toán
Cho C là tập con lồi đóng khác rỗng của Rn. Khi đó bài toán cực tiểu
hàm tựa lồi được phát biểu như sau:
min {g(x) : x ∈ C} ,
(OP)
2.2.2 Một thuật toán chiếu dưới đạo hàm
trong đó g : Rn → R là một hàm tựa lồi trên C.
Thuật toán
αk > 0 ∀k ∈ N,
∞ (cid:88)
∞ (cid:88)
α2
αk = +∞ và
k < +∞.
k=1
k=1
Cho C là một tập lồi đóng của Rn, chọn một dãy thực {αk} thỏa mãn các điều kiện sau:
Bước 1:
Chọn một điểm x1 sao cho x1 ∈ C, k = 1.
Bước k: (k=1,2,...)
Lấy gk ∈ ∂∗g(xk).
Nếu gk = 0, thì ta dừng lại: xk là một nghiệm.
Nếu gk (cid:54)= 0, thì ta thực hiện chuẩn hóa ||gk|| = 1. Thật vậy ta tính xk+1 = PC(xk − αkgk). Nếu xk+1 = xk, tức là xk là một nghiệm thì ta dừng lại.
Trái lại cho k ← k + 1 và lặp lại bước k.
Nhận xét 2.2.1. (i) Vì dưới vi phân-sao là một hình nón, ta luôn có thể
chuẩn hóa các phần tử khác không của nó để lấy một véc tơ đơn vị trong
(ii) Nếu thuật toán tạo nên một dãy hữu hạn thì điểm cuối cùng phải là
29
dưới vi phân.
0 ∈ ∂GP g(x) ⇔ ∂GP g(x) = Rn ⇔ x ∈ arg min
g(y).
y∈Rn
nghiệm. Thật vậy nếu 0 ∈ ∂∗g(xk) thì theo Bổ đề 1.3.12
[g(y) − g(x∗)], tức là g(y) ≥ g(x∗), với mỗi y ∈ C.
y∈C
Ta có xk ∈ arg min
Nếu xk+1 = xk thì xk = PC(xk − αkgk). Do đó, theo tính chất của hình
chiếu vuông góc ta có:
(cid:10)−αkgk, y − xk(cid:11) (cid:54) 0 ∀y ∈ C,
hoặc
(cid:10)gk, y − xk(cid:11) (cid:62) 0 ∀y ∈ C.
Do đó gk ∈ ∂∗g(xk), ta có g(y) − g(xk) ≥ 0 với mọi y ∈ C. Suy ra x∗ là
nghiệm tối ưu.
Bổ đề 2.2.2. Ta luôn có bất đẳng thức sau đúng với mỗi k
||xk+1 − xk|| ≤ αk.
(3.1)
Chứng minh. Vì xk = PC(xk − αkgk),
(cid:10)xk+1 − xk + αkgk, y − xk+1(cid:11) (cid:62) 0 ∀y ∈ C.
≤ αk
Bằng cách đặt y = xk, ta được
≤ αk
(cid:13)xk+1 − xk(cid:13) (cid:13) 2 (cid:13)
= αk
(cid:13)xk+1 − xk(cid:13) (cid:13) (cid:13)
(cid:10)gk, xk − xk+1(cid:11) (cid:13)gk(cid:13) (cid:13) (cid:13) (cid:13)xk+1 − xk(cid:13) (cid:13) (cid:13) .
Vậy
30
(cid:13)xk+1 − xk(cid:13) (cid:13) (cid:13) ≤ αk.
Mệnh đề 2.2.3. Cho C là một tập lồi đóng của Rn, với xk là điểm lặp ở
bước k. Khi đó với mỗi z ∈ C ta luôn có bất đẳng thức sau:
≤ (cid:13)
+ 2αk
(3.2) (cid:13)xk+1 − z(cid:13) (cid:13) 2 (cid:13) (cid:13)xk − z(cid:13) 2 (cid:13) (cid:10)gk, z − xk(cid:11) + 2α2 k.
+ 2 (cid:10)xk − xk+1, z − xk+1(cid:11)
Chứng minh. Chọn z ∈ C, thì ta có:
= (cid:13) ≤ (cid:13)
(3.3) (cid:13)xk+1 − z(cid:13) (cid:13) 2 (cid:13) (cid:13)xk − z(cid:13) − (cid:13) (cid:13)xk+1 − xk(cid:13) 2 2 (cid:13) (cid:13) (cid:13)xk − z(cid:13) 2 + 2 (cid:10)xk − xk+1, z − xk+1(cid:11) . (cid:13)
Vì xk+1 = PC (cid:0)xk − αkgk(cid:1) và z ∈ C
(3.4) (cid:10)gk, z − xk+1(cid:11) . (cid:10)xk − xk+1, z − xk+1(cid:11) ≤ αk
Từ (3.3) và (3.4)
+ 2αk
≤ (cid:13) = (cid:13)
(cid:10)gk, z − xk+1(cid:11)
(cid:10)gk, z − xk(cid:11)
+ 2αk
(3.5) (cid:13)xk+1 − z(cid:13) (cid:13) 2 (cid:13) (cid:13)xk − z(cid:13) 2 (cid:13) (cid:13)xk − z(cid:13) 2 + 2αk (cid:13) (cid:10)gk, xk − xk+1(cid:11) .
Theo bất đẳng thức Cauchy-Schwarz và ||gk|| = 1, ta có:
(cid:10)gk, xk − xk+1(cid:11) (cid:54) (cid:13) (cid:13)xk − xk+1(cid:13) (cid:13) .
||xk+1 − z||2 ≤ ||xk − z||2 + 2αk
Do đó, theo Bổ đề 2.2.2, (cid:13) (cid:13)xk − xk+1(cid:13) (cid:13) (cid:54) αk, theo bất đẳng thức (3.5) ta có:
31
(cid:10)gk, z − xk(cid:11) + 2α2 k.
B(x, (cid:15)) ⊂ Lg(xk) với mỗi x ∈ Rn và (cid:15) > 0, thì
Bổ đề 2.2.4. (a) Đặt B(x, (cid:15)) là hình cầu đóng có tâm là x bán kính (cid:15). Nếu
inf (cid:10)gk, xk − x(cid:11) ≤ 0 ∀x ∈ C.
(b) lim k→∞
(cid:10)gk, xk − ¯x(cid:11) > (cid:15).
(cid:0)xk(cid:1). (cid:0)xk(cid:1) , thì ¯x + (cid:15)gk ∈ Lg
Chứng minh. (a) Nếu ¯B(¯x, (cid:15)) ⊂ Lg Vì gk ∈ ∂∗g (cid:0)xk(cid:1) , ta có:
(cid:10)gk, ¯x + (cid:15)gk − xk(cid:11) < 0.
Từ (cid:13) (cid:13)gk(cid:13) (cid:13) = 1, do đó nó kéo theo
(b) Giả sử tồn tại z ∈ C, ξ > 0 và k0 là một điểm sao cho k > k0,
(cid:10)gk, xk − ¯x(cid:11) > (cid:15).
(cid:10)gk, xk − z(cid:11) ≥ ξ > 0.
Theo Mệnh đề 2.2.3 ta có:
− (cid:13)
2αk
+ 2α2 k.
(cid:10)gk, xk − z(cid:11) ≤ (cid:13) (cid:13)xk − z(cid:13) 2 (cid:13) (cid:13)xk+1 − z(cid:13) 2 (cid:13)
∞ (cid:88)
∞ (cid:88)
Bằng cách lấy tổng các phần tử của αkξ, ta thu được
2
αk
αkξ ≤ 2
k=0
k=0
∞ (cid:88)
≤ (cid:13)
(cid:10)gk, xk − z(cid:11)
α2 k.
k=1
(cid:13)x0 − z(cid:13) 2 + 2 (cid:13)
k=1 α2 k
.
0 < ξ ≤
Vậy,
k=1 α2
k=0 αk = +∞.
32
Suy ra mâu thuẫn bởi vì (cid:80)∞ (cid:13)x0 − z(cid:13) (cid:13) 2 + 2 (cid:80)∞ (cid:13) 2 (cid:80)∞ k=0 αk k < +∞ và (cid:80)∞
Định lý 2.2.5. Giả sử rằng thuật toán trên không kết thúc. Gọi {xk} là
xkq ∈ S, ∀q. Khi đó ta có:
d(xk, S(OP )) = 0, với S là tập nghiệm
(a) Nếu dãy {xkq} là vô hạn thì lim k→∞
dãy vô hạn được tạo bởi thuật toán và {xkq} là dãy con của {xk} sao cho
(b) Nếu dãy {xkq} là hữu hạn thì {xk} hội tụ tới nghiệm của bài toán (OP ).
của bài toán (OP ),
(a) Dãy {xkq} là vô hạn. Theo Mệnh đề 2.2.3 ta có:
≤ (cid:13)
+ 2αk
Chứng minh. Chúng tôi xét hai trường hợp.
(cid:13)xk+1 − z(cid:13) (cid:13) 2 (cid:13) (cid:13)xk − z(cid:13) 2 (cid:13) (cid:10)gk, z − xk(cid:11) + 2α2 k.
Chọn z = xkq, ta có:
≤ (cid:13)
+ 2αk
(3.6) (cid:13)xk+1 − xkq(cid:13) (cid:13) 2 (cid:13) (cid:13)xk − xkq(cid:13) 2 (cid:13) (cid:10)gk, xkq − xk(cid:11) + 2α2 k.
Với mỗi k sao cho kq < k < Kq+1 không thuộc S. Khi đó với kq < k < Kq+1
suy ra g(xkq) − g(xk) < 0, tức là xkq ∈ Lg(xk). Do đó
(3.7) (cid:10)gk, xkq − xk(cid:11) < 0 ∀kq < k < Kq+1.
k (cid:88)
∞ (cid:88)
Từ (3.6) và (3.7), với kq < k < Kq+1, nó kéo theo
α2 i
α2 i .
i=kq
i=kq
α2
α2
i = 0. Vậy từ (3.8) ta suy ra
k < +∞, ta có lim q→∞
(3.8) (cid:54) 2 (cid:13)xk − xkq(cid:13) (cid:13) 2 (cid:54) 2 (cid:13)
∞ (cid:80) i=kq
d(xk, S) = 0.
lim k→∞
(b) Dãy {xkq} là hữu hạn. Khi đó tồn tại k0 sao cho k ≥ k0, ta có xk ∈
S(EP ). Thì g(x∗) − g(xk) < 0. Để chứng minh trong trường hợp này ta
33
Ngoài ra, vì xkq ∈ S, ta có d2(xk, S) ≤ ||xk − xkq||2, ngoài ra theo giả định ∞ (cid:80) k=1
chia làm bốn bước sau đây.
Bước 1: Dãy {||xk − x∗||} là hội tụ và do đó {xk} là bị chặn.
Thật vậy g(x∗) − g(xk) < 0 với k ≥ k0, tức là x∗ ∈ Lg(xk) với k ≥ k0. Do
đó
(3.9) (cid:10)gk, x∗ − xk(cid:11) < 0 ∀k (cid:62) k0.
Kết hợp điều này với (3.2) trong Mệnh đề 2.2.3 ta thu được
2 (cid:54) (cid:13) (cid:13)xk+1 − x∗(cid:13) (cid:13) (cid:13)
+ 2α2 k.
(3.10) (cid:13)xk − x∗(cid:13) 2 (cid:13)
k < +∞. Nên dãy {||xk − x∗||} là hội tụ và do đó {xk} là bị chặn. α2
∞ (cid:80) k=1
Do
inf (cid:10)gk, xk − x∗(cid:11) = 0. Thật vật theo Bổ đề 2.2.4 (b), ta có: Bước 2: lim k→∞
lim k→∞
(3.11) inf (cid:10)gk, xk − x∗(cid:11) ≤ 0.
Từ (3.9) và (3.11) suy ra
lim k→∞
inf (cid:10)gk, xk − x∗(cid:11) = 0.
Bước 3: Đặt {xki} là một dãy con của {xk} thỏa mãn
lim i→∞
(3.12) inf (cid:10)gk, xk − x∗(cid:11) = 0. (cid:10)gki, xki − x∗(cid:11) = lim k→∞
xki = x.
{xki}, không mất tính tổng quát, cho lim i→∞
Do {xk} là bị chặn kéo theo {xki} bị chặn. Đặt x là một điểm giới hạn của
C, ta có:
g(x∗) − g(x) ≤ 0.
Ta đi chứng minh g(x∗) − g(x) = 0. Thật vậy, do x∗ là cực tiểu của g trên
Hơn nữa, ta thấy rằng g(x∗) − g(x) = 0. Thực vậy, bằng phủ định, giả sử
34
như có a > 0 sao cho g(x∗) − g(x) ≤ −a.
Khi đó, do g(.) là liên tục trên C nên suy ra tồn tại (cid:15)1 > 0, (cid:15)2 > 0 sao cho
g(y) − g(x) ≤ −
.
a 2
xki = x, khi đó tồn tại i0 ≤ i sao cho xki thuộc B(x, (cid:15)1),
với mỗi x ∈ B(x, (cid:15)1), y ∈ B(x∗, (cid:15)2), ta có:
Mặt khác, vì lim i→∞
< 0,
g(y) − g(xkq) ≤ −
a 2
do y ∈ B(x∗, (cid:15)2) suy ra
nghĩa là B(x∗, (cid:15)2) ⊂ Lg(xki). Khi đó theo Bổ đề 2.2.4 (a), ta có:
(cid:10)gki, xki − x∗(cid:11) > (cid:15) ∀i (cid:62) i0.
Kết hợp với (3.12). Suy ra g(x∗) − g(x) = 0.Vậy x cũng là nghiệm.
Bước 4: Dãy {xk} hội tụ đến một nghiệm của bài toán (OP ).
x∗ ∈ S(OP ), nên g(x) − g(x∗) = 0.
Thật vậy ở Bước 3 ta có g(x∗) − g(x) = 0. Do g(x) − g(x∗) ≤ 0, mà
xki = x. Tức là toàn bộ dãy {xk} hội tụ về nghiệm
Vậy x cũng là nghiệm của bài toán (OP ). Từ bước 1 dãy {||xk − x||2} là
x của bài toán (OP ).
hội tụ, kết hợp với lim i→∞
Kết luận trong chương này trước hết chúng tôi đã trình bày về bài
toán cực tiểu hàm lồi và hàm tựa lồi. Tiếp theo ta giới thiệu chi tiết về hai
thuật toán chiếu dưới đạo hàm để giải bài cực tiểu hàm lồi và hàm tựa lồi
35
trên một tập lồi đóng.
Kết luận
Trong luận văn này chúng tôi đã giới thiệu những vẫn đề cụ thể sau:
1. Trình bày các kiến thức cơ sở và giới thiệu tổng quan về hàm lồi, hàm
tựa lồi trên tập lồi. Bao gồm các định nghĩa tập lồi, hàm lồi, hàm tựa lồi.
Các tính chất cơ bản và ví dụ minh họa cho các định nghĩa trên, đồng thời
đi sâu vào khái niệm, tính chất cơ bản dưới vi phân của hàm lồi và hàm tựa
lồi.
2. Trình bày về bài toán cực tiểu hàm lồi và hàm tựa lồi. Bằng việc phát
biểu bài toán cực tiểu hàm lồi, hàm tựa lồi sau đó chứng minh. Phần cuối
của luận văn chúng tôi trình bày về hai thuật toán chiếu dưới đạo hàm để
36
giải bài toán cực tiểu hàm lồi và hàm tựa lồi trên một tập đóng.
Tài liệu tham khảo
Tiếng Việt
[1] Lê Dũng Mưu, Nguyễn Văn Hiền, Nguyễn Hữu Điển, Nhập môn giải
tích lồi ứng dụng, NXB Đại học Quốc gia, Hà Nội, (2015).
[2] Lê Dũng Mưu, Giáo trình các phương pháp tối ưu, NXB KHKT, Hà
Tiếng Anh
Nội (1998).
[3] Hoang Tuy, Convex Analysis and Global Optimization, Springer (2015).
[4] Le Hai Yen and Le Dung Muu, A subgradient method for equilibrium
problems involving quasiconvex bifunctions, Operations Research Letter
48(2020) 579-583.
[5] Olvi L. Mangasarian, Nonlinear Programming, Society For Industrial
and Applied Mathematics (1994).
[6] Paulo Santos, Susana Scheimberg, An inexact subgradient algorithm for
37
Equilibrium Problems, Comput. Appl. Math. (2011) 91-107.
