Mục lục
Lời mở đầu
1
1 Cơ sở giải tích lồi
3
1.1
Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.2
Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.3
Hàm liên hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.4
Dưới vi phân . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
1.5
Đặc trưng hàm lồi
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
1.6
Một số ứng dụng vào bài toán tối ưu . . . . . . . . . . . . . . . . . . .
21
2 Hàm véctơ lồi và ứng dụng
34
2.1
Các khái niệm cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
2.2
Tính liên tục, liên tục theo nón . . . . . . . . . . . . . . . . . . . . . .
41
2.3
Dưới vi phân của hàm véctơ lồi . . . . . . . . . . . . . . . . . . . . . .
47
2.4
Hàm liên hợp của hàm véctơ lồi . . . . . . . . . . . . . . . . . . . . . .
52
2.5
Các đặc trưng của hàm véctơ lồi . . . . . . . . . . . . . . . . . . . . . .
56
2.6
Một số ứng dụng vào bài toán tối ưu véctơ . . . . . . . . . . . . . . . .
70
Kết luận
75
Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
i
76
Lời mở đầu
Rất nhiều bài toán trong thực tế có thể đưa được về dạng: Tìm x ∈ D sao cho
f (x) ≤ f (x), ∀x ∈ D, trong đó, D là tập con của một tập nào đó và f : D → R là hàm
số thực. Ta kí hiệu bài toán này là
f (x) = min f (x)
x∈D
(1)
và gọi nó là bài toán tối ưu. Bài toán này đóng vai trò trọng tâm trong lý thuyết tối
ưu và có những bài toán liên quan như bài toán bất đẳng thức biến phân, bài toán cân
bằng, bài toán minimax, bài toán điểm yên ngựa,... Trong trường hợp f là một hàm
số khả vi thì bài toán (1) được gọi là tối ưu khả vi hay tối ưu trơn. Trong trường hợp
ngược lại, bài toán (1) được gọi là tối ưu không trơn. Đối với tối ưu trơn ta đã có được
những điều kiện cần và đủ cấp 1 và cấp 2, có phương pháp giải bằng phương pháp
Newton và nhiều phương pháp khác.
Trong mấy chục năm qua rất nhiều nhà toán học trên thế giới quan tâm nghiên cứu,
tìm ra những phương pháp giải bài toán tối ưu không trơn. Năm 1947, nhà toán học
người Mỹ, Danzig, đã tìm ra phương pháp đơn hình để giải bài toán quy hoạch tuyến
tính: f là hàm tuyến tính, D là một đa diện lồi. Năm 1960 đến 1970, hai nhà toán học
Mỹ là Jean Jacques Moreau và R. T. Ralph Tyrrell Rockafellar, đã đưa ra khái niệm
dưới vi phân hàm lồi và từ đó đã hình thành môn Giải tích lồi để giải quy hoạch nói
trên. Những năm 1980 nhà toán học Mỹ, Clarke, đưa ra khái niệm dưới vi phân của
hàm Lipschitz địa phương và xây dựng nên môn Giải tích Lipschitz. Nhiều nhà toán
học khác như J. P. Penot, Urruty, Mordukhovich, Nguyễn Văn Hiền, Strodiot,... cũng
đưa ra những khái niệm về dưới vi phân để giải bài toán (1) trong những trường hợp
khác. Đặc biệt, Đinh Thế Lục và Jeykumar, năm 1990-2010, đã đưa ra những khái
niệm Jacobian xấp xỉ để giải bài toán trong trường hợp tổng quát: f là hàm liên tục
và D là tập đóng. Tiếp theo người ta cần phát triển bài toán (1) trong trường hợp f
từ tập D vào không gian véctơ khác. Để phát triển được bài toán tối ưu, người ta cần
một quan hệ thứ tự, tương đương với điều kiện có một nón trên không gian. Từ thứ
tự đó người ta đã phát biểu được các bài toán tối ưu khác nhau như tối ưu lý tưởng,
tối ưu Pareto, tối ưu thực sự, tối ưu yếu. Từ đó hình thành nên môn học mới: Tối
1
ưu véctơ, là công cụ để giải quyết những bài toán tối ưu véctơ. Hơn thế, người ta còn
nghiên cứu bài toán trên trong trường hợp f là ánh xạ đa trị, đề tài này rất phong
phú và hấp dẫn và có nhiều ứng dụng trong thực tế. Chính vì vậy, tôi chọn đề tài cho
luận văn thạc sĩ của mình là: "Dưới vi phân hàm véctơ lồi và ứng dụng."
Ngoài phần mở đầu, phần kết luận và danh mục tài liệu tham khảo, luận văn gồm
hai chương:
Chương 1. Giải tích lồi trình bày một số khái niệm và kết quả trong tài liệu [2]
về các tính chất cơ bản của giải tích lồi như tập lồi, hàm lồi, các tính chất liên tục,
tính Lipschitz, hàm liên hợp, tính khả dưới vi phân hàm lồi và ứng dụng trong các bài
toán tối ưu lồi vô hướng.
Chương 2. Dưới vi phân hàm véctơ lồi và ứng dụng là nội dung chính của
luận văn, trình bày những mở rộng cho các tính chất, kết quả của hàm lồi vô hướng
cho hàm véctơ lồi theo nón như các khái niệm về nón, điểm hữu hiệu, tính liên tục
theo nón, tính lồi, dưới vi phân, hàm liên hợp, các đặc trưng và một số ứng dụng của
dưới vi phân vào bài toán tối ưu véctơ lồi.
Luận văn được hoàn thành tại Viện Toán học thuộc Viện Hàn Lâm Khoa Học và
Công Nghệ Việt Nam, dưới sự hướng dẫn tận tình của GS. TSKH. Nguyễn Xuân Tấn.
Tôi muốn gửi tới Thầy lời biết ơn sâu sắc nhất. Tôi cũng xin gửi lời cảm ơn chân thành
tới các Thầy, Cô và các cán bộ, nhân viên của Viện Toán Học, các bạn lớp Cao học
K21 và các bạn lớp Cao học quốc tế K8 đã tạo điều kiện thuận lợi cho tôi trong quá
trình học cao học và thực hiện bản luận văn này.
Hà Nội, ngày 26/08/2015
Tác giả luận văn
Nguyễn Thị Phương
2
Chương 1
Cơ sở giải tích lồi
Chương này dành cho những kiến thức cơ bản của giải tích lồi cần dùng cho các
bài toán tối ưu không trơn. Khi muốn xét sự tồn tại nghiệm hay tìm thuật toán để giải
bài toán tối ưu, ta phải trang bị cho tập ràng buộc cũng như những hàm số những cấu
trúc đại số và tôpô để mô tả những tính chất đặc thù của từng loại bài toán, từ đó
tìm ra phương pháp giải. Ta bắt đầu bằng việc giới thiệu các cấu trúc ấy trên tập hợp.
Để khỏi phải nhắc lại nhiều lần, ta giới hạn chỉ trình bày một số kiến thức cơ bản về
giải tích lồi như: Tập lồi, hàm lồi, dưới vi phân,... Các kết quả về lý thuyết, về thuật
toán, để giải bài toán (1) vẫn đúng cho trường hợp không gian tôpô tuyến tính lồi địa
phương Hausdorff. Nhưng để cho người đọc thấy trực quan, trong luận văn này ta chỉ
trình bày các vấn đề đó trong không gian hữu hạn chiều.
1.1
Tập lồi
Ta kí hiệu R = R ∪ {±∞} là tập số thực mở rộng, h., .i là tích vô hướng trong Rn .
Định nghĩa 1.1.1. Đường thẳng nối hai điểm (hai véctơ) a, b trong Rn là tập tất cả
các véctơ x ∈ Rn có dạng
x = αa + βb, α, β ∈ R, α + β = 1.
Đoạn thẳng nối hai điểm a và b trong Rn là tập
{x ∈ Rn |x = αa + βb, α ≥ 0, β ≥ 0, α + β = 1}.
3
Tương tự ta có các kí hiệu [a, b) , (a, b], (a, b)...
Định nghĩa 1.1.2. Tập C ⊆ Rn đượ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.
Dưới đây là một số ví dụ về tập lồi thường gặp
Định nghĩa 1.1.3. Cho f ∈ Rn , α là một số thực cố định.
H = {x ∈ Rn : hf, xi = α} được gọi là siêu phẳng,
H + = {x ∈ Rn : hf, xi ≥ α} được gọi là nửa không gian trên,
H − = {x ∈ Rn : hf, xi ≤ α} được gọi là nửa không gian dưới.
Ta dễ dàng thấy H, H + , H − đều là các tập lồi xác định bởi f và α.
Tiếp theo, ta nhắc lại một số khái niêm liên quan đến tập lồi.
Định nghĩa 1.1.4. Cho A ⊂ Rn .
i) Bao lồi của A là giao của tất các tập lồi chứa A, kí hiệu là coA;
ii) Bao lồi đóng của tập A là giao của tất cả các tập lồi đóng chứa A, kí hiệu là coA.
Định nghĩa 1.1.5. Tập hợp con C ⊂ Rn được gọi là nón có đỉnh tại gốc, nếu tx ∈ C,
với mọi x ∈ C và t ≥ 0. Tập C ⊂ Rn được gọi là nón có đỉnh tại x0 , nếu tập C − {x0 }
là nón có đỉnh tại gốc.
Định nghĩa 1.1.6. i) Nón C được gọi là nón nhọn, nếu l(C) := C ∩ (−C) = {0}.
ii) Nón cực của một nón C được định nghĩa là tập
C 0 := {ξ ∈ L(Rn , R) : ξ(x) ≥ 0, ∀x ∈ C}.
Khái niệm nón cho ta một quan hệ thứ tự mới trên không gian Rn .
Định nghĩa 1.1.7. Với nón lồi C cho trước, ta định nghĩa quan hệ thứ tự từng
phần C trên Rn như sau:
x, y ∈ Rn , x C y, nếu x − y ∈ C.
4
Nếu không có sự nhầm lẫn, ta có thể viết đơn giản x y.
Cho x, y ∈ Rn , ta kí hiệu x y, nếu x − y ∈ C \ lC và x y, nếu x − y ∈ intC.
Trong lý thuyết tối ưu ta sẽ thấy có những kết quả liên quan tới việc tách các
tập lồi, chúng làm nền tảng cho những điều kiện cần và đủ để tồn tại nghiệm của bài
toán tối ưu có ràng buộc. Sau đây, ta đưa ra một số khái niệm liên quan tới tách các
tập lồi.
Định nghĩa 1.1.8. Cho các tập A, B ⊂ Rn . Ta nói phiếm hàm tuyến tính liên tục
f 6= 0 tách A và B, nếu tồn tại một số α sao cho
hf, yi ≤ α ≤ hf, xi , ∀x ∈ A, ∀y ∈ B.
(1.1)
Nếu các bất đẳng thức ở (1.1) là thực sự, tức là, hf, yi < α < hf, xi , ∀x ∈ A, ∀y ∈ B,
thì ta nói f tách chặt A và B.
Siêu phẳng H = {x ∈ Rn : hf, xi = α} gọi là siêu phẳng tách A và B. Các tập A, B gọi
là tách được.
Phần chứng minh của những kết quả sau đây có thể tìm thấy trong [2].
Định lý 1.1.9. (Định lý tách thứ nhất). Cho A và B là các tập lồi trong Rn , A∩B = ∅.
Khi đó, tồn tại phiếm hàm tuyến tính liên tục f 6= 0, f ∈ Rn tách A và B.
Hệ quả 1.1.10. Cho A, B là các tập lồi trong Rn . Khi đó, A, B tách được khi và chỉ
khi (intA) ∩ B = ∅.
Định lý 1.1.11. Giả sử A là tập lồi đóng trong không gian Rn và x0 ∈
/ A. Khi đó, tồn
tại f ∈ Rn , f 6= 0 tách chặt A và x0 .
Hệ quả sau đây được suy ra trực tiếp Định lý 1.1.11.
Hệ quả 1.1.12. Cho A ⊂ Rn . Ta có
i) coA trùng với giao của tất cả các nửa không gian chứa A;
ii) Nếu A là tập lồi khi đó A đóng khi và chỉ khi A đóng.
Định lý 1.1.13. (Định lý tách thứ hai). Cho A, B là hai tập lồi đóng khác rỗng sao
cho A ∩ B = ∅. Giả sử có ít một trong hai tập là compact. Khi đó, hai tập này có thể
tách mạnh được bởi một siêu phẳng.
5
1.2
Hàm lồi
Trong mục này ta đưa ra một số tính chất của hàm số liên quan tới cấu trúc đại số và
cấu trúc tôpô.
Định nghĩa 1.2.1. Cho C ⊆ Rn là một tập lồi và f : C → R ∪ {±∞}. Ta kí hiệu
domf := {x ∈ C|f (x) < ∞}.
Tập domf được gọi là miền hữu hiệu của f. Tập
epif := {(x, µ) ∈ C × R|f (x) ≤ µ}
được gọi là trên đồ thị của hàm f. Tập
lev (f, α) = {x ∈ C : f (x) ≤ α}
được gọi là tập mức của f tại α ∈ R.
Định nghĩa 1.2.2. 1) Hàm f được gọi là hàm lồi, nếu epif là tập lồi trong không
gian tích C × R;
2) Hàm f gọi là hàm chính thường nếu domf 6= ∅ và f (x) > −∞, với mọi x ∈ C.
Trong luận văn, để khỏi phải nhắc lại nhiều lần, ta luôn giả thiết hàm lồi là chính
thường.
Mệnh đề 1.2.3. ([2]). Hàm f : C → R xác định trên tập lồi C ⊆ Rn được gọi là
1. Hàm lồi khi và chỉ khi
∀x1 , x2 ∈ C, ∀λ ∈ [0, 1] ta có f (λx1 + (1 − λ)x2 ) ≤ λf (x1 ) + (1 − λ)f (x2 );
2. Hàm lồi chặt, nếu
∀x1 , x2 ∈ Rn , ∀λ ∈ (0, 1) ta có f (λx1 + (1 − λ)x2 ) < λf (x1 ) + (1 − λ)f (x2 );
3. Hàm lồi mạnh, với hệ số β > 0 nếu ∀x1 , x2 ∈ C, ∀λ ∈ (0, 1), ta có
1
f (λx1 + (1 − λ)x2 ) ≤ λf (x1 ) + (1 − λ)f (x2 ) − λ (1 − λ) βkx1 − x2 k2 ;
2
6
4. Hàm lõm (lõm chặt), nếu −f là hàm lồi (lồi chặt);
5. Hàm f tựa lồi nếu và chỉ nếu
lev (f + g, α) là tập lồi ∀g, α ∈ R, trong đó (f + g) (x) = f (x) + g (x) .
Chú ý 1.2.4. 1) Nếu f là hàm lồi thì domf là tập lồi;
2) Nếu f là hàm lồi thì {x : f (x) < α} , {x : f (x) ≤ α} là các tập lồi ∀α ∈ [−∞, +∞] .
1.2.1
Tính liên tục
Tính chất lồi của một hàm kéo theo nhiều tính chất tôpô quan trọng, mặc dù trong
định nghĩa hàm lồi ta không đòi hỏi một cách trực tiếp đến bất kỳ tính chất tôpô nào.
Trước hết, ta nhắc lại rằng hàm f : D ⊂ Rn → R được gọi là nửa liên tục dưới
tại điểm x ∈ D, nếu như với mọi dãy {xk } ⊂ D, xk → x ta có liminf f (xk ) ≥ f (x).
k→∞
Hàm f được gọi là nửa liên tục trên tại điểm x ∈ D nếu −f nửa liên tục dưới tại x.
Hay là với mọi dãy {xk } ⊂ D, xk → x ta có limsup(xk ) ≤ f (x). Hàm f được gọi là
k→∞
nửa liên tục 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 tại x. Hàm f
được gọi là nửa liên tục dưới, nếu nó nửa liên tục dưới tại mọi điểm thuộc D. Tương
tự, ta cũng nói như vậy với hàm nửa liên tục trên và hàm liên tục.
Các kết quả sau có thể tìm thấy chứng minh trong tài liệu [2].
Định nghĩa 1.2.5. i) Bao đóng của hàm f là một hàm, kí hiệu clf, có trên đồ thị
epi cl f = epif ;
ii) Bao lồi đóng của hàm f là một hàm, kí hiệu cof, có trên đồ thị
epi(cof ) = co(epif );
iii) Hàm f được gọi là đóng nếu epif là tập đóng trong Rn × R.
Chú ý 1.2.6. Các khẳng định sau đây là đúng.
i) Hàm f là lồi thì clf cũng là lồi;
7
ii) Hàm f là đóng khi và chỉ khi f = clf .
Mệnh đề 1.2.7. Hàm f là đóng khi và chỉ khi lev (f, α) = {x : f (x) ≤ α} là tập đóng
với α ∈ R.
Mệnh đề 1.2.8. Hàm f là đóng khi và chỉ khi f là nửa liên tục dưới.
Định lý sau cho ta các điều kiện để hàm lồi liên tục.
Định lý 1.2.9. ([2]). Cho f là hàm lồi chính thường trên Rn khi đó các khẳng định
sau là tương đương.
i) f bị chặn trên tại lân cận của x0 ∈ Rn ;
ii) f liên tục tại x0 ;
iii) int(epif ) 6= ∅;
vi) int(domf ) 6= ∅ và f liên tục trên int(domf ).
1.2.2
Tính Lipschitz
Tính Lipschitz của hàm đóng vai trò quan trọng trong việc nghiên cứu những bài toán
tối ưu. Trước tiên, ta đưa ra một số khái niệm cơ bản sau
Định nghĩa 1.2.10. Hàm f : D ⊂ Rn → R được gọi là Lipschitz trên D nếu tồn tại
hằng số L ≥ 0 sao cho
|f (x) − f (y)| ≤ Lkx − yk, ∀x, y ∈ D.
L được gọi là hằng số Lipschitz.
Hàm f được gọi là Lipschitz địa phương tại điểm x̄ ∈ D nếu tồn tại lân cận U của x̄
để f Lipschitz trên U ∩ D.
Hàm f được gọi là Lipschitz địa phương trên tập D ⊂ Rn nếu nó Lipschitz địa phương
tại mọi điểm thuộc D.
Định lý 1.2.11. ([2]). Giả sử f là 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.
Hệ quả 1.2.12. ([2]). Giả sử f : D → R là hàm lồi liên tục tại x0 thuộc tập lồi mở
D. Khi đó, f Lipschitz địa phương trên D.
8
1.3
Hàm liên hợp
Hàm liên hợp có một vai trò quan trọng trong lý thuyết tối ưu, đặc biệt là trong lý
thuyết đối ngẫu. Trong phần này, trước hết chúng ta sẽ giới thiệu định nghĩa và đưa
ra ví dụ minh họa cho hàm liên hợp. Tiếp đến sẽ khảo sát một số tính chất và quy tắc
cơ bản cho việc tính toán với hàm liên hợp.
1.3.1
Phép biến đổi Young - Fenchel
Ta có thể cho tương ứng hàm cho trước với một hàm lồi như sau:
Định nghĩa 1.3.1. Phép biến đổi Young - Fenchel của hàm f : D ⊂ Rn → R hay
hàm liên hợp của hàm f là hàm f ∗ : D∗ ⊂ Rn → R được xác định:
f ∗ (x∗ ) = sup {hx∗ , xi − f (x)} .
(1.2)
x∈D
Mệnh đề 1.3.2. f ∗ là hàm lồi đóng.
Chứng minh. Với x cố định, hàm g (x∗ ) := hx∗ , xi − f (x) là hàm tuyến tính trên Rn .
Do đó, g (x∗ ) lồi đóng.
Trên đồ thị của f ∗ (x∗ ) là giao của trên đồ thị các hàm g (x∗ ), tức là, giao của các tập
lồi đóng . Vì vậy, epif ∗ lồi đóng .
Nhận xét. Từ Định nghĩa 1.3.1 ta có
f (x) + f ∗ (x∗ ) ≥ hx∗ , xi , ∀x, x∗ ∈ Rn .
Bất đẳng thức (1.3) gọi là bất đẳng thức Young - Fenchel.
Ví dụ 1.3.3. Cho hàm f (x) = hx0 ∗ , xi + α, ∀x, x∗ ∈ Rn .
∗
∗
∗
∗
⇒ f (x ) = sup hx − x0 , xi − α
x
9
=
−α,
khi x∗ = x0 ∗ ,
∞,
khi x∗ 6= x0 ∗ .
(1.3)
1.3.2
Tính chất của hàm liên hợp
Từ Định nghĩa 1.3.1, suy ra
f ∗∗ (x) = (f ∗ )∗ (x) = sup {hx∗ , xi − f ∗ (x∗ )} .
(1.4)
x∗
Mệnh đề 1.3.4. Với hàm bất kỳ ta có f ∗∗ ≤ f .
Chứng minh.
f ∗∗ (x) = sup {hx∗ , xi − f ∗ (x∗ )}
x∗
∗
∗
= sup hx , xi − sup {hx , xi − f (x)}
x∗
= sup
x∗
x
hx∗ , xi + inf {f (x) − hx∗ , xi}
x
≤ sup {hx∗ , xi + f (x) − hx∗ , xi}
x∗
= f (x) .
Định lý 1.3.5. Giả sử f là hàm lồi chính thường đóng trên Rn . Khi đó, f ∗ là hàm lồi
chính thường.
Chứng minh. Theo Mệnh đề 1.3.2, f ∗ là hàm lồi. Ta chứng minh f ∗ là hàm chính
thường.
Lấy x0 ∈ domf ta có f ∗ (x∗ ) ≥ hx0 ∗ , x0 i − f (x0 ) > −∞, ∀x∗ ∈ Rn .
Hơn nữa, (x0 , f (x0 ) − 1) ∈
/ epif, theo Định lý tách thứ hai tồn tại (y0 ∗ , β0 ) sao cho
sup
{hy0 ∗ , x0 i + βo α} < hy0 ∗ , x0 i + βo (f (x0 ) − 1) .
(1.5)
(x,α)∈epif
Rõ ràng βo 6= 0 và βo không thể là số dương vì nếu βo > 0 thì cận trên của vế trái
bằng +∞. Chia hai vế của (1.5) cho |βo | , ta có
sup
|β0 |−1 y0 ∗ , x − f (x) = f ∗ |β0 |−1 y0 ∗ < |β0 |−1 y0 ∗ , x0 + 1 − f (x0 ) < ∞.
x∈domf
Suy ra điều cần chứng minh.
10
Định lý 1.3.6. Cho A : Rn → Rm là phép đồng phôi tuyến tính, g là hàm xác định
trên Rm . Đặt f (x) = λg (Ax + y0 ) + hx0 ∗ , xi + γ0 trong đó, y0 ∈ Rm , x0 ∗ ∈ Rn ,
∗
γ0 ∈ R, λ > 0. Khi đó, f ∗ (x∗ ) = λg λ−1 A−1 (x∗ − x0 ∗ ) − hx∗ − x0 ∗ , A−1 y0 i − γ0 .
Chứng minh. f ∗ (x∗ ) = sup {hx∗ , xi − λg (Ax + y0 ) − hx0 ∗ , xi − γ0 } .
x
Đặt y = Ax + y0 ta được
∗
f ∗ (x∗ ) = λ sup λ−1 A−1 (x∗ − x0 ∗ ) , y − g (y) − x∗ − x0 ∗ , A−1 y0 − γ0
y
∗
= λg ∗ λ−1 A−1 (x∗ − x0 ∗ ) − x∗ − x0 ∗ , A−1 y0 − γ0 .
Hệ quả 1.3.7. i) f (x) = g (x + x0 ) ⇒ f ∗ (x∗ ) = g ∗ (x∗ ) − hx∗ , x0 i ;
ii) f (x) = g (x) + hx0 ∗ , xi ⇒ f ∗ (x∗ ) = g ∗ (x∗ − x0 ∗ ) ;
iii) f (x) = λg (x) , λ > 0 ⇒ f ∗ (x∗ ) = λg ∗ (λ−1 x∗ ) ;
iv) f (x) = λg (λ−1 x) , λ > 0 ⇒ f ∗ (x∗ ) = λg ∗ (x∗ ) ;
v) f (x) = g (λx) , λ > 0 ⇒ f ∗ (x∗ ) = g ∗ (λ−1 x∗ ) .
Định lý 1.3.8. (Định lý Fenchel - Moreau). Cho f : Rn → (−∞, +∞], khi đó
f = f ∗∗ ⇔ f lồi đóng.
Chứng minh. Theo Hệ quả 1.1.12, A là tập lồi.
⇒) Giả sử f = f ∗∗ theo Mệnh đề 1.3.2, f ∗∗ là hàm lồi đóng. Vậy, f ∗∗ lồi đóng.
⇐) Giả sử f lồi đóng.
+) Nếu f (x) = +∞ thì hiển nhiên f = f ∗∗ .
+) Nếu f (x) < +∞ theo Mệnh đề 1.3.4 f ∗∗ ≤ f.
Vì vậy, ta cần chứng minh, nếu f là hàm lồi chính thường, đóng thì f ≤ f ∗∗ .
Thật vậy, giả sử ∃x0 ∈ domf ∗∗ sao cho f (x0 ) > f ∗∗ (x0 ) . Ta có epif là tập lồi đóng,
epif 6= ∅ và (x0 , f ∗∗ (x0 )) ∈
/ epif . Theo Định lý tách thứ hai, tồn tại (y ∗ , β) ∈ Rn × R
tách chặt (x0 , f ∗∗ (x0 )) và epif tức là
sup
{hy ∗ , yi + βα} < hy ∗ , x0 i + βf ∗∗ (x0 ) .
(y,α)∈epif
11
(1.6)
Khi đó, β ≤ 0 và nếu β > 0 thì cận trên phải bằng +∞. Mặt khác, theo Định lý 1.3.5,
f ∗ là hàm lồi chính thường, như vậy domf ∗ 6= ∅.
Nếu β = 0, lấy y1 ∗ ∈ domf ∗ , với t > 0 ta có
f ∗ (y1 ∗ + ty ∗ ) = sup {hy1 ∗ + ty ∗ , yi − f (y)}
y∈domf
≤ sup {hy1 ∗ , yi − f (y)} + t sup hy ∗ , yi
y∈domf
y∈domf
= f ∗ (y1 ∗ ) + t sup hy ∗ , yi .
(1.7)
y∈domf
Từ (1.6), với β = 0 suy ra
hy ∗ , xi > sup hy ∗ , yi .
y∈domf
Vì vậy, từ (1.7) ta có
f ∗∗ (x0 ) ≥ hy1 ∗ + ty ∗ , x0 i − f ∗ (y1 ∗ + ty ∗ )
∗
∗
∗
∗
∗
≥ hy1 , x0 i − f (y1 ) + t hy , x0 i − sup hy , yi .
y∈domf
Cho t → +∞, ta suy ra f ∗∗ (x0 ) = +∞ và như vậy x0 ∈
/ domf ∗∗ mâu thuẫn với
x0 ∈ domf ∗∗ ở trên. Từ đó ta có thể kết luận trường hợp β = 0 không xảy ra.
Vậy, β < 0. Chia cả hai vế của (1.6) cho |β| và đặt x∗ = |β|−1 y ∗ ta được
hx∗ , x0 i − f ∗∗ (x0 ) >
sup
{hx∗ , yi − α}
(y,α)∈epif
≥ sup {hx∗ , yi − f (y)} = f ∗ (x∗ )
y∈domf
⇒ hx∗ , x0 i > f ∗∗ (x0 ) + f ∗ (x∗ ) .
Điều này mâu thuẫn với bất đẳng thức Young - Fenchel. Định lý được chứng minh.
Hệ quả 1.3.9. Giả sử f là hàm lồi chính thường đóng trên Rn . Khi đó,
f (x) = sup h (x) : h − affine liên tục, h ≤ f } .
Chứng minh. Theo Định lý Fenchel - Moreau, f = f ∗∗ . Do đó, f (x) là lân cận trên
12
của các hàm affine có dạng
x → hx∗ , xi − f ∗ (x∗ ) , (x∗ ∈ domf ∗ ) .
Như vậy,
f (x) = sup {hx∗ , xi − f ∗ (x∗ )}
x
≤ f (x) = sup h (x) : h − affine liên tục, h ≤ f } ≤ f (x).
Vì vậy f (x) = sup h (x) : h − affine liên tục, h ≤ f } .
Hệ quả 1.3.10. Giả sử cof là hàm chính thường. Khi đó, f ∗∗ = cof.
Chứng minh. Ta có epif ∗∗ là tập lồi đóng. Do f ≥ f ∗∗ nên epif ∗∗ ⊂ epif. Do đó,
epif ⊆ co (epif ) ⊆ epif f ∗∗
⇒ f ≥ cof ≥ f ∗∗ .
(1.8)
Chú ý rằng, nếu f1 ≤ f2 thì f1 ∗ ≥ f2 ∗ . Vì vậy, f ∗ ≤ (cof )∗
⇒ f ∗∗ ≥ (cof )∗∗ ≥ cof.
(1.9)
Từ (1.8) và (1.9) suy ra f ∗∗ = cof.
Hệ quả 1.3.11. Giả sử cof là hàm chính thường, khi đó f ∗ = (cof )∗ .
Chứng minh. Theo Hệ quả 1.3.10, f ∗∗ = cof ⇒ (f ∗ )∗∗ = (cof )∗ . Theo Mệnh đề 1.3.2,
f ∗ là hàm lồi đóng nên theo Định lý 1.3.8 thì (f ∗ )∗∗ = f ∗ . Vậy ta có f ∗ = (cof )∗ .
1.4
Dưới vi phân
Tính khả vi phân của hàm lồi đóng vai trò quan trọng trong các bài toán tối ưu, trong
các phương pháp tối ưu. Cho D ⊂ Rn , f : D → R̄, |f (x)| < +∞.
Ta biết rằng trong trường hợp f khả vi tại x0 ∈ domf, thì tại lân cận của x0 , f được
xấp xỉ một cách khá tốt bởi đạo hàm của nó. Hàm lồi, nói chung không khả vi, ta phải
tìm cách tiếp cận khác.
13
Định nghĩa 1.4.1. Đạo hàm của f theo phương d tại x0 ∈ Rn , kí hiệu f 0 (x0 , d), được
định nghĩa
f (x0 + λd) − f (x0 )
,
λ→0
λ
f 0 (x0 , d) = lim
nếu giới hạn này tồn tại (có thể hữu hạn hoặc bằng ±∞).
Định nghĩa 1.4.2. Cho f : Rn → R là một hàm lồi. Một véctơ ξ ∈ Rn là dưới gradient
của f tại x ∈ Rn nếu
f (y) − f (x) > ξ(y − x), ∀y ∈ Rn .
Định nghĩa 1.4.3. Tập tất cả các dưới gradient của f tại x được gọi là dưới vi phân
của hàm f tại x, kí hiệu là ∂f (x), tức là,
∂f (x) = {ξ : f (y) − f (x) > ξ(y − x), ∀y ∈ Rn .
Định nghĩa 1.4.4. Cho D là một tập lồi không rỗng của Rn và x0 ∈ D. Hướng d
được gọi là hướng chấp nhận được của D tại x0 nếu tồn tại một số λ > 0 sao cho
x0 + λd ∈ D.
Tập hợp tất cả các hướng chấp nhận được của D tại x0 được kí hiệu là T (D, x0 ).
Chú ý 1.4.5. Nếu f là hàm lồi chính thường trên Rn thì
i) f 0 (x0 , .) là hàm thuần nhất dương trên Rn , tức là với mọi
λ > 0, f 0 (x0 , λd) = λf 0 (x0 , d) ;
ii) Với mọi x ∈ domf thì f 0 (x0 , .) là dưới tuyến tính.
Mệnh đề 1.4.6. ([2]). Cho hàm f : Rn → R̄ là hàm lồi chính thường trên Rn . Khi đó,
f có đạo hàm theo phương tại mọi điểm x ∈ domf đồng thời
f 0 (x0 , d) = inf
λ>0
f (x0 + λd) − f (x0 )
.
λ
Định nghĩa 1.4.7. i) Tập K ⊂ Rn được gọi là nón có đỉnh tại 0 nếu ∀x ∈ K,
∀λ > 0 thì λx ∈ K;
ii) Tập K được gọi là nón có đỉnh tại x0 nếu K − x0 là nón có đỉnh tại 0;
iii) Nón K có đỉnh tại 0 được gọi là nón lồi nếu ∀x, y ∈ K, ∀α, β > 0 : αx + βy ∈ K;
14
iv) Nếu K là lồi đóng thì nó được gọi là nón lồi đóng;
v) Giao của tất cả các nón lồi có đỉnh tại 0 chứa tập A và điểm 0 là một nón lồi và
được gọi là nón lồi sinh bởi A kí hiệu là KA .
Mệnh đề 1.4.8. Giả sử f là hàm thuần nhất dương trên Rn , khi đó:
i) Nếu f liên tục tại mọi điểm của U ⊂ Rn thì f liên tục tại mọi điểm của nón KU
sinh bởi điểm U có thể trừ điểm 0;
ii) Nếu f liên tục trong một lân cận của 0 thì f liên tục trên Rn .
Chứng minh. i) Lấy x0 6= 0, x0 ∈ KU , khi đó tồn tại λ > 0 : λx0 ∈ U. Do f liên tục tại
điểm λx0 nên ∀ε > 0, tồn tại lân cận V của λx0 sao cho
|f (x) − f (x0 )| < λε ∀x ∈ V ;
Như vậy λ1 V là một lân cận của x0 và với mọi x ∈ λ1 V , ta có
|f (x) − f (x0 )| =
1
|f (λx) − f (λx0 )| < ε.
λ
Vậy f liên tục tại x0 .
ii) Giả sử f liên tục tại lân cận W của 0, theo i) f liên tục tại mọi điểm của nón
KW sinh bởi tập W (có thể trừ điểm 0). Ta có KW = Rn và tại điểm 0 ta đã giả thiết
f liên tục. Vậy, f liên tục trên Rn .
Phần chứng minh của các kết quả dưới đây có thể xem trong [2].
Định lý 1.4.9. Cho f : Rn → R̄ là một hàm lồi chính thường trên Rn liên tục tại các
điểm của tập U ⊂ Rn . Khi đó:
i) Nếu tại d0 ∈ Rn thoả mãn x + d0 ∈ U mà f 0 (x, d0 ) hữu hạn thì hàm f (x, .) liên tục
tại mọi điểm của nón KU −x sinh bởi tập U − x (có thể trừ điểm 0);
ii) Nếu f liên tục tại x thì f 0 (x, .) hữu hạn và liên tục trên Rn .
Mệnh đề 1.4.10. Tại mỗi x ∈ D ta có T (D, x) là một nón lồi.
Mệnh đề 1.4.11. Cho f là một hàm lồi từ một tập con lồi không rỗng D ⊆ Rn vào
R̄ và x ∈ D, d ∈ T (D, Rn ), khi đó:
15
i) f có đạo hàm theo hướng d khi và chỉ khi tập
f (x + λd) − f (x)
, λ > 0, x + λd ∈ D
λ
bị chặn dưới và
0
f (x, d) = inf
f (x + λd) − f (x)
, λ > 0, x + λd ∈ D ;
λ
ii) f 0 (x, .) là hàm thuần nhất dương, lồi khi domf 0 (x, .) lồi.
Hệ quả 1.4.12. f (x, .) là hàm thuần nhất dương lớn nhất xác định trên domf 0 (x, .)
có tính chất
f (x + λd) − f (x) ≥ f 0 (x, λd) , ∀d ∈ domf 0 (x, .) , λ > 0; x + λd ∈ D.
Mệnh đề 1.4.13. Cho hàm f lồi chính thường trên Rn và x ∈ domf. Khi đó các khẳng
định sau đây là tương đương:
i) x∗ ∈ ∂f (x0 );
ii) f (x0 ) + f ∗ (x∗ ) = hx∗ , x0 i ;
iii) f 0 (x0 , d) ≥ hx∗ , di , ∀d ∈ X.
Định lý 1.4.14. (Định lý Moreau-Rockafellar)
i) Cho f1 , f2 là các hàm lồi chính thường trên Rn . Khi đó,
∂f1 (x) + ∂f2 (x) ⊆ ∂f (f1 + f2 ) (x) , ∀x ∈ Rn ;
ii) Nếu tại x0 ∈ domf1 ∩ domf2 một trong hai hàm liên tục thì
∂f1 (x) + ∂f2 (x) = ∂f (f1 + f2 ) (x) , ∀x ∈ Rn .
Chú ý 1.4.15. Bằng phương pháp quy nạp ta có thể chứng minh Định lý 1.4.14 trong
trường hợp tổng quát. Cho f1 , f2 , ..., fm là các hàm lồi chính thường trên Rn . Khi đó,
i) Với mọi x ∈ Rn ,
∂f1 (x) + ∂f2 (x) + ... + ∂fm (x) ⊆ ∂f (f1 + f2 + ... + fm ) (x) ;
16
ii) Nếu tại x ∈
m
T
domfi tất cả các hàm fi
i = 1, m liên tục (có thể trừ một hàm)
i=1
thì
∂f1 (x) + ∂f2 (x) + ... + ∂fm (x) = ∂f (f1 + f2 + ... + fm ) (x) .
Mệnh đề 1.4.16. Cho hàm lồi f từ một tập khác rỗng D ⊂ Rn vào R̄ và x ∈ D. Nếu
f khả vi dưới vi phân tại x thì domf (x, .) = T (D, x).
Mệnh đề 1.4.17. Cho f là một hàm lồi từ tập con lồi không rỗng D ⊆ Rn vào R̄ và
x ∈ D, ξ ∈ L x, R . Khi đó,
ξ ∈ ∂f (x) ⇔ ξ (d) ≤ f 0 (x, d) , ∀d ∈ T (D, x) .
Định lý 1.4.18. (Định lý giá trị trung bình). Cho [x, y] là một đoạn thẳng trong tập
mở mà hàm f là hàm lồi. Khi đó, tồn tại u ∈ (x, y) sao cho
f (y) − f (x) ∈ {ξ(y − x) | ξ ∈ ∂f (u)}.
Mệnh đề dưới đây cho ta một định nghĩa khác tương đương với định nghĩa của dưới vi
phân.
Mệnh đề 1.4.19. ([1], Chương 11, Mệnh đề 11.2). Cho f : Rn → R ∪ {+∞} lồi, chính
thường.
i) x∗ ∈ ∂f (x) khi và chỉ khi f 0 (x, y) ≥ hx∗ , yi, ∀y.
Nếu x ∈ ri(domf ) thì f 0 (x, y) =
sup hx∗ , yi, ∀y.
x∗ ∈∂f (x)
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.4.20. ([1], Chương 11, Mệnh đề 11.3). Cho f : Rn → R ∪ {+∞} lồi, chính
thường. Khi đó:
i) Nếu x ∈ domf thì ∂f (x) 6= ∅;
ii) Nếu x ∈ int(domf ) thì ∂f (x) 6= ∅ và compact. Ngược lại, nếu ∂f (x) 6= ∅, compact
thì x ∈ ri(domf ).
17
Ví dụ sau đây cho thấy nếu x ∈
/ int(domf ) thì tập ∂f (x) có thể bằng rỗng.
Cho hàm một biến
f (x) =
−2x1\2 , x ≥ 0,
+∞,
x < 0.
Khi đó, ∂f (0) = ∅.
Mệnh đề 1.4.21. Cho f là một hàm lồi chính thường trên Rn . Khi đó,
i) Với mọi tập bị chặn C ⊂ ri(domf ), ∪ ∂f (x) bị chặn, với riA là phần trong tương
x∈C
đối của A với tôpô sinh cảm sinh từ không gian affin nhỏ nhất chứa A;
ii) Nếu có thêm f đóng thì có đẳng thức Fenchel sau:
f ∗ (x∗ ) + f (x) = hx∗ , xi ⇔ x∗ ∈ ∂f (x), x ∈ ∂f ∗ (x∗ ).
Mệnh đề 1.4.22. Giả sử f : Rn → R ∪ {+∞} lồi, chính thường và x ∈ domf . Khi
đó, f khả vi tại x khi và chỉ khi tồn tại x∗ ∈ Rn sao cho f 0 (x, y) = hx∗ , yi, ∀y. Ngoài
ra, x ∈ int(domf ) và ∇f (x) = x∗ .
1.5
Đặc trưng hàm lồi
Trước khi đưa ra đặc trưng của hàm lồi ta cần nhắc lại một số khái niệm liên quan
đến ánh xạ đơn điệu và Hessian suy rộng của hàm lồi.
Định nghĩa 1.5.1. Ánh xạ F : C → Rn được gọi là đơn điệu trên C, nếu
hF (x) − F (y), x − yi ≥ 0, ∀x, y ∈ DomF.
Ánh xạ F được gọi là đơn điệu mạnh trên C với hệ số β > 0, nếu
hF (x) − F (y), x − yi ≥ βkx − yk2 , ∀x, y ∈ DomF.
Ta có thể mở rộng khái niệm này cho trường hợp ánh xạ đa trị.
n
Định nghĩa 1.5.2. ([1]). Ánh xạ đa trị T : Rn → 2R được gọi là đơn điệu trên
18
C ⊆ domT, nếu với mọi cặp (x1 , y 1 ), (x2 , y 2 ) ∈ G(T ), xi ∈ C, (i = 0, ..., m), ta có
hy 2 − y 1 , x2 − x1 i ≥ 0, ∀y 1 ∈ T (x1 ), ∀y 2 ∈ T (x2 ).
(1.10)
Sau đây là đặc trưng của hàm lồi cho trường hợp khả vi.
Mệnh đề 1.5.3. ([1]). Cho f : Rn → R ∪ {+∞} khả vi và C ⊂ Rn . Các điều kiện sau
là tương đương:
i) f lồi, chính thường trên C;
ii) hf 0 (y) − f 0 (x), y − xi ≥ 0, ∀x, y ∈ domf.
Kết quả này được mở rộng cho trường hợp không khả vi như sau.
Mệnh đề 1.5.4. Giả sử S là một toán tử từ Rn vào Rn . Điều kiện cần và đủ để tồn
tại một hàm lồi, đóng, chính thường f trên Rn sao cho S(x) ⊆ ∂f (x), ∀x ∈ ∂f (x), là
toán tử S đơn điệu.
Hệ quả trực tiếp của mệnh đề này là đặc trưng cấp 1 của hàm lồi chính thường
không khả vi.
Hệ quả 1.5.5. Điều kiện cần và đủ để hàm f : C ⊂ Rn → R lồi đóng chính thường là
n
ánh xạ dưới vi phân ∂f (.) : C → 2R là toán tử đơn điệu.
Tiếp theo ta nhắc lại một số khái niệm liên quan đến tính liên tục của ánh xạ đa trị
n
Định nghĩa 1.5.6. Ánh xạ T : Rn → 2R được gọi là đóng tại x, nếu với mọi dãy
xk → x, mọi y k ∈ T (xk ) và y k → y, thì y ∈ T (x).
n
Định nghĩa 1.5.7. Ánh xạ T : Rn → 2R được gọi là nửa liên tục trên (dưới) tại x,
nếu với mọi tập mở G chứa T (x)(G ∩ T (x) 6= ∅) tồn tại một lân cận mở U của x sao
cho
T (z) ⊆ G (tương tự, (T (z) ∩ G 6= ∅), ∀z ∈ U ).
Ta nói ánh xạ T là đóng, nửa liên tục trên (dưới) trên tập C nếu nó đóng, nửa liên tục
trên (dưới) tại mọi điểm thuộc C.
Mệnh đề sau khẳng định tính nửa liên tục trên của ánh xạ ∂f .
19
- Xem thêm -