BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
Nghiêm Thị Phượng
ĐỐI NGẪU MẠNH TRONG BÀI TOÁN
QUI HOẠCH TOÀN PHƯƠNG KHÔNG LỒI
LUẬN VĂN THẠC SĨ TOÁN HỌC
Hà Nội – Năm 2016
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
NGHIÊM THỊ PHƯỢNG
ĐỐI NGẪU MẠNH TRONG BÀI TOÁN
QUI HOẠCH TOÀN PHƯƠNG KHÔNG LỒI
Chuyên ngành: Toán giải tích
Mã số: 60 46 01 02
LUẬN VĂN THẠC SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS.TS. TẠ DUY PHƯỢNG
Hà Nội – Năm 2016
Lời cảm ơn
Trước khi trình bày nội dung chính của bản luận văn thạc sĩ chuyên
ngành, em xin bày tỏ lòng biết ơn sâu sắc tới PGS. TS. Tạ Duy Phượng
đã tận tình hướng dẫn để em có thể hoàn thành đề tài này.
Em cũng xin bày tỏ lòng biết ơn chân thành tới toàn thể các thầy cô
giáo trong khoa Toán, Trường Đại học Sư phạm Hà Nội 2 đã dạy bảo em
tận tình trong suốt quá trình học tập tại khoa.
Nhân dịp này em cũng xin được gửi lời cảm ơn chân thành tới gia đình,
bạn bè đã luôn bên em, động viên, giúp đỡ em trong suốt quá trình học
tập và thực hiện đề tài thực tập này.
Hà Nội, ngày 10 tháng 11 năm 2016
Tác giả
Nghiêm Thị Phượng
i
Lời cam đoan
Tôi xin cam đoan rằng số liệu và kết quả trình bày trong khóa luận là
trung thực và không trùng lặp với các luận văn khác. Tôi cũng xin cam
đoan rằng mọi sự giúp đỡ cho việc thực hiện khóa luận này đã được cảm
ơn và các thông tin thu trích dẫn trong khóa luận đã được chỉ rõ nguồn
gốc.
Hà Nội, ngày 10 tháng 11 năm 2016
Tác giả
Nghiêm Thị Phượng
ii
Mục lục
Mở đầu
ii
Danh mục các kí hiệu và chữ viết tắt
iv
1 Sơ lược về lý thuyết đối ngẫu
1
1.1
Một số định nghĩa
. . . . . . . . . . . . . . . . . . . . .
1
1.2
Một số mở rộng của định lý minimax cổ điển . . . . . . .
3
1.2.1
Định lý Sion . . . . . . . . . . . . . . . . . . . . .
3
1.2.2
Một số mở rộng của định lý minimax cổ điển
. .
3
1.3
Định lý minimax và các hệ quả . . . . . . . . . . . . . .
7
1.4
Định lý minimax cho hàm toàn phương . . . . . . . . . .
16
2 Bài toán tối ưu hàm toàn phương không lồi
22
2.1
Tối ưu hàm toàn phương với một hạn chế toàn phương .
22
2.2
Tối ưu hàm toàn phương với nhiều hạn chế toàn phương
34
2.2.1
Tối ưu hàm toàn phương với hai hạn chế toàn phương 34
2.2.2
Tối ưu hàm toàn phương với nhiều hạn chế toàn
phương . . . . . . . . . . . . . . . . . . . . . . . .
Tài liệu tham khảo
42
58
i
Mở đầu
1. Lý do chọn đề tài
Lý thuyết đối ngẫu đóng vai trò quan trọng trong nghiên cứu bài
toán tối ưu. Có thể xây dựng lý thuyết đối ngẫu dựa trên các định lý
minimax. Bài toán tối ưu hàm toàn phương như là một bước phát triển
tiếp theo của bài toán tối ưu tuyến tính.
Bài báo [7] đã nghiên cứu khá chi tiết bài toán tối ưu toàn phương
không lồi với các hạn chế toàn phương, trong đó các tác giả đã chứng
minh các định lý về đối ngẫu mạnh trong bài toán quy hoạch toàn
phương (không lồi) và áp dụng để nghiên cứu nhiều vấn đề của bài toán
tối ưu hàm toàn phương. Các kết quả của bài báo này liên quan và soi
sáng nhiều kết quả của bài toán tối ưu hàm toàn phương.
2. Mục đích nghiên cứu
Mục đích chính của Luận văn là trình bày các kết quả về đối ngẫu
mạnh và áp dụng trong bài toán qui hoạch toàn phương không lồi.
ii
Luận văn thạc sĩ Toán học
nghiêm thị phượng
3. Nhiệm vụ nghiên cứu
Nghiên cứu và trình bày các kết quả về đối ngẫu mạnh và áp dụng
trong bài toán qui hoạch toàn phương không lồi.
4. Đối tượng và phạm vi nghiên cứu
Đối tượng nghiên cứu: Các bài toán tối ưu hàm toàn phương.
Phạm vi nghiên cứu: Các kết quả về đối ngẫu mạnh và áp dụng trong
bài toán qui hoạch toàn phương không lồi.
5. Phương pháp nghiên cứu
Tổng hợp, phân tích, hệ thống các kiến thức trong các tài liệu về đối
ngẫu mạnh và áp dụng trong bài toán qui hoạch toàn phương không lồi.
6. Đóng góp của luận văn
Luận văn trình bày một cách hệ thống về đối ngẫu mạnh và áp dụng
trong bài toán qui hoạch toàn phương không lồi.
iii
Luận văn thạc sĩ Toán học
nghiêm thị phượng
Danh mục các kí hiệu và chữ viết tắt
R
tập số thực
Rn
không gian Euclid n chiều
∅
tập rỗng
x∈M
x thuộc tập M
x∈
/M
x không thuộc tập M
∀ x ∈ M với mọi x thuộc tập M
∃x
tồn tại x
|I|
số phần tử của tập I
[x1 , x2 ]
đoạn thẳng nối hai điểm x1 và x2
kxk
chuẩn của x
|x|
giá trị tuyệt đối của x
CT
ma trận chuyển vị của ma trận C
ha, xi
tích vô hướng của hai véc tơ a và x
iv
Chương 1
Sơ lược về lý thuyết đối ngẫu
1.1
Một số định nghĩa
Định nghĩa 1.1.1. Tập C ⊂ Rn được gọi là tập lồi nếu
tx1 + (1 − t) x2 ∈ C với mọi x1 , x2 ∈ C, mọi t ∈ [0; 1] .
Định nghĩa 1.1.2. Hàm f : C → R xác định trên tập lồi C ⊂ Rn .
Hàm f được gọi là hàm lồi trên C, nếu với mọi x1 , x2 ∈ C, mọi t ∈ [0; 1]
ta có
f tx1 + (1 − t) x2 ≤ tf x1 + (1 − t) f x2 .
Hàm f được gọi là lồi chặt trên C, nếu với mọi x1 , x2 ∈ C, mọi t ∈ [0; 1]
ta có
f tx1 + (1 − t) x2 < tf x1 + (1 − t) f x2 .
Hàm f được gọi là hàm tựa lồi trên C, nếu với mọi x1 , x2 ∈ C, mọi
t ∈ [0; 1] ta có
f tx1 + (1 − t) x2 ≤ max f x1 , f x2 .
1
Luận văn thạc sĩ Toán học
nghiêm thị phượng
Hàm f gọi là hàm lõm trên C nếu −f là hàm lồi trên C.
Hàm f được gọi là hàm tựa lõm trên C, nếu với mọi x1 , x2 ∈ C, mọi
t ∈ [0; 1] ta có
f tx1 + (1 − t) x2 ≥ min f x1 , f x2 .
Định nghĩa 1.1.3. Cho X là không gian tôpô.
f :X→R
Hàm f được gọi là nửa liên tục dưới (l.s.c) tại x0 nếu mọi số thực α ∈ R
mà f (x0 ) > α thì tồn tại lân cận mở U của x0 trong X sao cho f (x) > α
với mọi x ∈ U.
Hàm f được gọi là nửa liên tục trên (u.s.c) tại x0 nếu mọi số thực α ∈ R
mà f (x0 ) < α thì tồn tại lân cận mở V của x0 trong X sao cho f (x) < α
với mọi x ∈ V.
Định nghĩa 1.1.4. Hàm f : Rn → R được gọi là hàm toàn phương nếu
có dạng
1
1
f (x) = xT Ax + bT x + α = hx, Axi + hb, xi + α
2
2
n
n
n
X
1 XX
=
aij xi xj +
bi xi + α,
2 i=1 j=1
i=1
trong đó A là ma trận cấp n × n, b là một vectơ n chiều, α là một số.
Định nghĩa 1.1.5. Cho hàm thực f (x) trên tập con C ⊂ Rn .
Điểm x ∈ C được gọi là cực tiểu địa phương của f (x) trên C nếu tồn
tại hình cầu W tâm x sao cho f (x) ≤ f (x) ∀x ∈ W ∩ C. Điểm x ∈ C
2
Luận văn thạc sĩ Toán học
nghiêm thị phượng
được gọi là cực tiểu toàn cục của f (x) trên C nếu f (x) ≤ f (x) ∀x ∈ C.
Định nghĩa 1.1.6. Tập A ⊂ Rn được gọi là không liên thông nếu tồn
tại tập mở U, V sao cho U ∩ A 6= ∅, V ∩ A 6= ∅, U ∩ V ∩ A 6= ∅.
Ngược lại thì A được gọi là liên thông.
1.2
Một số mở rộng của định lý minimax cổ điển
Một trong những kết quả quan trọng của lý thuyết tối ưu có nhiều ứng
dụng trong các bài toán thực tế là định lý minimax. Mục này trình bày
một số kết quả của định lý minimax.
1.2.1
Định lý Sion
Định lý 1.2.1. (Sion, [9]) Cho X là tập con lồi compact của một không
gian tôpô tuyến tính và Y là tập con lồi của không gian tôpô tuyến tính.
Giả sử f là hàm nhận giá trị thực và xác định trên X × Y sao cho
(i)
f (x, .) là nửa liên tục trên và tựa lõm trên Y với mỗi x ∈ X;
(ii)
f (x, .) là nửa liên tục dưới và tựa lồi trên X với mỗi y ∈ Y.
Khi ấy
min sup f (x, y) = sup min f (x, y) .
x∈X y∈Y
1.2.2
y∈Y x∈X
Một số mở rộng của định lý minimax cổ điển
Định lý minimax cổ điển đã được Hoàng Tụy và các tác giả khác mở
rộng như sau:
Cho C, D là các tập con của hai không gian vectơ Hausdorff X, Y ;
F (x, y) là hàm nhận giá trị thực xác định trên X × Y.
3
Luận văn thạc sĩ Toán học
nghiêm thị phượng
Với α ∈ R và y ∈ D, Cα (y) := {x ∈ C |F (x, y) ≤ α} . Hàm F (x, y)
được gọi là α-liên thông trên C × D nếu
(H) Với mọi tập hữu hạn H ⊂ D tập CH :=
T
Cα (y) hoặc là rỗng
y∈H
hoặc là liên thông;
(T) Với mọi cặp a, b ∈ D tồn tại một ánh xạ liên tục u : [0, 1] → D sao
cho với mọi t ∈ [θ, θ0 ] ⊂ [0, 1]
u (0) = a, u (1) = b, Cα (u (t)) ⊂ Cα (u (θ)) ∪ Cα (u (θ0 )) .
Định lý 1.2.2. (H. Tụy, [6]) Giả thiết C là tập compact, hàm F (x, y)
là hàm nửa liên tục dưới theo x. Đẳng thức minimax
inf sup F (x, y) = sup inf F (x, y) .
x∈C y∈D
y∈D x∈C
đúng, nếu thêm vào đó, một trong hai điều kiện sau là thỏa mãn:
(i) F (x, y) là hàm nửa liên tục trên theo y và tồn tại dãy đơn điệu giảm
αk & η sao cho F (x, y) là αk -liên thông với mỗi k;
(ii) F (x, y) là hàm nửa liên tục dưới theo y và tồn tại dãy không giảm
αk → η sao cho F (x, y) là αk -liên thông với mỗi k.
Định lý 1.2.3. (Theorem 2, [8]) Cho C là tập compact và F (x, y) là
hàm nửa liên tục dưới theo x và liên tục theo y. Nếu D là tập con cực
đại sao cho với mọi a1 , ..., an ∈ D và mọi α ∈ R, tập
x ∈ C F x, ai ≤ α, i = 1, ..., n hoặc là rỗng hoặc là liên thông. Khi
4
Luận văn thạc sĩ Toán học
nghiêm thị phượng
đó đẳng thức minimax
inf sup F (x, y) = sup inf F (x, y) .
x∈C y∈D
y∈D x∈C
đúng cho hàm F (x, y) trên C × D.
..
Định lý 1.2.4. (Konig [3], [4]) Giả thiết C là tập compact, D là liên
thông và F (x, y) là hoặc hàm nửa liên tục dưới theo x, nửa liên tục trên
theo y hoặc là nửa liên tục dưới đồng thời theo (x, y).
Đặt η := sup inf F (x, y) , và Λ ⊂ (η; +∞) là tập khác rỗng sao cho
y∈D x∈C
inf Λ = η. Khi ấy đẳng thức minimax
inf sup F (x, y) = sup inf F (x, y) .
x∈X y∈Y
y∈Y x∈X
đúng nếu với mỗi α ∈ Λ, các giả thiết sau được thỏa mãn:
(H) Với mỗi tập khác rỗng hữu hạn H ⊂ D, tập
T
CH :=
{x ∈ C |F (x, y) ≤ α} là liên thông;
y∈H
T
(K) Với mỗi tập khác rỗng K ⊂ C, tập DK :=
{y ∈ D |F (x, y) > α}
x∈K
là liên thông.
Định lý 1.2.5. (Theorem 5.1, [5]) Cho C là tập con compact của không
gian vectơ topo Hausdorff X, D là một khoảng của R và F (x, y) : C ×
D → R xác định trên C × D là hàm nửa liên tục dưới theo x với mỗi
y ∈ D cố định. Giả sử tồn tại một số thực α∗ > η := sup inf F (x, y)
y∈D x∈C
∗
sao cho với mỗi α ∈ (η; α ) thì
T1
Với mỗi x ∈ C tập {y ∈ D |F (x, y) > α} là liên thông;
T2
Ít nhất một trong các điều kiện T 2a, T 2b, T 2c được thỏa mãn:
5
Luận văn thạc sĩ Toán học
nghiêm thị phượng
a) Với mỗi y ∈ D tập Cα (y) = {x ∈ C |F (x, y) ≤ α} là liên thông, trong
đó với mỗi x ∈ C hàm F (x, .) hoặc là nửa liên tục trên hoặc là nửa liên
tục dưới;
b) Với mỗi đoạn ∆ ⊂ D tồn tại ánh xạ ϕ : ∆ → C đa trị giá trị đóng
với tập giá trị ϕ (y) khác rỗng, đóng và liên thông thỏa mãn:
ϕ (y) ⊂ Cα (y)
∀y ∈ ∆;
c) Với mỗi x ∈ C hàm F (x, .) là liên tục và với mỗi y ∈ D mọi cực tiểu
địa phương của F (., y) trên C cũng là cực tiểu trên toàn C.
Khi đó ta có đẳng thức minimax
min sup F (x, y) = sup inf F (x, y) .
x∈C y∈D
y∈D x∈C
Định lý 1.2.6. (Theorem 5.4, [5]) Cho X, Y là hai không gian tôpô
Hausdorff, C là tập con copmpact khác rỗng của X, D là tập con đóng
khác rỗng của Y và F (x, y) : C × D → R là hàm thực nửa liên tục dưới
theo x. Giả thiết tồn tại một số thực α∗ > η := sup inf F (x, y) sao cho
y∈D x∈C
∗
với mỗi α ∈ (η; α ) các điều kiện sau đây được thỏa mãn:
(H) Với mỗi tập khác rỗng hữu hạn H ⊂ D, H , tập
T
{x ∈ C |F (x, y) ≤ α} hoặc là rỗng hoặc liên thông;
y∈H
b
(T ) Với mỗi cặp a, b ∈ D tồn tại ánh xạ uab (t) : [0, 1] → D sao cho hàm
F (x, uab (t)) hoặc là nửa liên tục dưới hoặc là nửa liên tục trên theo t và
uab (0) = a uab (1) = b trong đó
Cα (uab (t)) ⊂ Cα (uab (θ)) ∪ Cα (uab (θ0 )) ∀t ∈ [θ, θ0 ] ⊂ [0, 1] .
6
Luận văn thạc sĩ Toán học
nghiêm thị phượng
Khi ấy ta có đẳng thức minimax
inf sup F (x, y) = sup inf F (x, y) .
x∈C y∈D
y∈D x∈C
Mở rộng định lý minimax cổ điển bằng cách thêm các giả thiết lồi
tổng quát ta có
1.3
Định lý minimax và các hệ quả
Mục này trình bày một số định lý minimax gần đây của Hoàng Tụy,
Hoàng Đức Tuấn trong [7] và các hệ quả.
Định lý 1.3.1. (Theorem 1, [7]) Cho C là tập con đóng của Rn , D là
khoảng (đóng hoặc mở) của R và L (x, y) : Rn × R → R là một hàm liên
tục. Giả sử các điều kiện sau được thỏa mãn:
(i)
Với mỗi x ∈ Rn hàm L (x, .) là lõm;
(ii) Với mỗi điểm y ∈ D, cực tiểu địa phương của L (., y) trên C là cực
tiểu toàn cục của L (., y) trên C;
(iii) Tồn tại y ∗ ∈ D sao cho L (x, y ∗ ) → +∞ khi x ∈ C, kxk → +∞.
Khi đó ta có đẳng thức minimax:
inf sup L (x, y) = sup inf L (x, y) .
x∈C y∈D
(1.1)
y∈D x∈C
Ngoài ra, nếu inf sup L (x, y) < +∞ thì ∃x ∈ C thoả mãn
x∈C y∈D
sup L (x, y) = min sup L (x, y) .
y∈D
x∈C y∈D
7
(1.2)
Luận văn thạc sĩ Toán học
nghiêm thị phượng
Chứng minh. Chứng minh trực tiếp.
Đặt
γ := inf sup L (x, y), η := sup inf L (x, y).
x∈C y∈D
y∈D x∈C
Nếu η = +∞ thì đẳng thức (1.1) là hiển nhiên. Thật vậy, giả sử
η := sup inf L (x, y) = +∞. Khi đó tồn tại dãy yn ⊂ D sao cho
y∈D x∈C
inf L (x, yn ) → +∞ khi n → ∞, tức là với mọi x0 ∈ C ta có:
x∈C
L (x0 , yn ) ≥ inf L (x, yn ) → +∞.
x∈C
Suy ra với mọi x ∈ C ta có:
sup L (x, yn ) → +∞.
y∈D
Suy ra γ := inf sup L (x, yn ) = +∞ hay γ = η = +∞.
x∈C y∈D
Như vậy giả sử η < +∞. Lấy số thực α > η tùy ý và với mỗi y ∈ D cố
định, đặt Cα (y) := {x ∈ C| L (x, y) ≤ α}.
Đầu tiên chúng ta chứng minh với bất kì đoạn ∆ = [a, b] ⊂ D điều kiện
sau đây được thỏa mãn
\
Cα (y) 6= ∅.
(1.3)
y∈∆
Điều này cũng có thể giả thiết rằng y ∗ ∈ (a, b). Vì inf L (x, y ∗ ) ≤ η < α
x∈C
nên tồn tại x ∈ C thoả mãn L (x, y ∗ ) < α. Do L (., .) là hàm liên tục theo
biến y nên tồn tại u, v sao cho u < y ∗ < v và L (x, y) < α ∀y ∈ [u, v].
8
Luận văn thạc sĩ Toán học
nghiêm thị phượng
Do đó, đặt
)
(
s = sup
y ∈ [u, b]|
\
Cα (z) 6= ∅ .
(1.4)
u≤z≤y
Ta có s ≥ v. Theo định nghĩa của s, tồn tại một dãy yk % s, sao cho
T
C k :=
Cα (y) 6= ∅.
u≤y≤yk
Theo giả thiết (iii) Cα (y ∗ ) là compact, nên C k , k=1, 2,...tạo thành một
dãy các tập con đóng không rỗng của tập compact Cα (y ∗ ).
∞
T
Do đó ∃x0 ∈
C k , nghĩa là thoả mãn L x0 , y ≤ α ∀y ∈ [u, s).
k=1
Từ đó L x0 , y ≤ α ∀k, cho k → +∞ được L x0 , s ≤ α.
vì vậy L x0 , y ≤ α ∀y ∈ [u, s].
Ta khẳng định s = b. Thật vậy, nếu s < b ta không thể có L x0 , s < α,
do đó theo tính liên tục của hàm L (x, y) sẽ tồn tại q > s thoả mãn
L x0 , y < α ∀y ∈ [s, q), mâu thuẫn với (1.4). Do đó nếu s < b thì
nhất thiết L x0 , s = α. Ngoài ra, với bất kì hình cầu W tâm x0 ta
không thể có α = min L (x, s) vì khi ấy theo giả thiết (ii) ta suy ra
x∈C∩W
0
rằng α = L x , s = min L (x, s), mâu thuẫn với α > inf L (x, s).
x∈C
x∈C
k
k
0
k
Vì vậy tồn tại x ∈ C sao cho x → x và L x , s < α.
Nếu với y ∈ (s, b] và k nào đó ta đã có L xk , y > α, thì vì L xk , s < α
nên theo giả thiết (i) ta suy ra rằng L xk , z < α ∀z ∈ [u, s], ngoài ra
theo tính liên tục L xk , q < α ∀y ∈ [s, q] với q > s, mâu thuẫn
với (1.4).
Do đó, L xk , y ≤ α ∀k, vì vậy cho xk → x0 được L x0 , y ≤ α,
9
Luận văn thạc sĩ Toán học
nghiêm thị phượng
∀y ∈ (s, b]. Điều này chứng minh s = b cho nên
\
Cα (y) 6= ∅.
(1.5)
u≤y≤b
Tương tự, đặt
\
Cα (z) 6= ∅ ,
t = inf y ∈ [u, b]|
y≤z≤b
T
ta có thể chỉ ra rằng t = a, nghĩa là
Cα (y) 6= ∅. Khẳng định (1.3)
a≤y≤b
được chứng minh.
Bây giờ dễ dàng để hoàn thành chứng minh.
Từ giả thiết (iii) tập Cα (y ∗ ) là compact. Bởi vì mọi tập hữu hạn
E ⊂ D phải chứa trong một đoạn ∆ nào đó nên suy ra từ (1.3) rằng họ
Cα (y) ∩ Cα (y ∗ ), y ∈ D, có tính chất giao hữu hạn.
Do đó, tồn tại x ∈ C thoả mãn L (x, y) ≤ α ∀y ∈ D.
Lấy α = η + k1 thì với mỗi k = 1, 2, ... tồn tại xk ∈ C thoả mãn
L xk , y ≤ η + k1 ∀y ∈ D.
Từ đó
1
L xk , y ∗ ≤ η + < η + 1,
k
nghĩa là xk ∈ Cη+1 (y ∗ ) ∀k.
Vì tập hợp Cη+1 (y ∗ ) là compact nên dãy xk có điểm tụ x ∈ C thoả
mãn L (x, y) ≤ η ∀y ∈ D. Suy ra sup L (x, y) ≤ η và
y∈D
γ = inf sup L (x, y) ≤ sup L (x, y) ≤ η.
x∈C y∈D
y∈D
10
Luận văn thạc sĩ Toán học
nghiêm thị phượng
Vì L (x0 , y) ≥ sup L (x, y) với mọi x0 ∈ C nên sup L (x0 , y) ≥ sup L (x, y)
x∈C
y∈D
0
y∈D
0
với x ∈ C và do đó inf sup L (x , y) ≥ sup L (x, y) hay γ ≥ η.
x0 ∈C y∈D
y∈D
Vậy γ = η. Hệ thức (1.2) được chứng minh.
Nhận xét 1.3.1. Giả thiết (ii) là hiển nhiên thỏa mãn nếu L (., y) là
hàm lồi và C là tập hợp lồi (Định lý 1.3.1 trở về định lý minimax cổ
điển). Hơn nữa, sau này ta sẽ thấy, giả thiết (ii) thỏa mãn trong nhiều
trường hợp của bài toán tối ưu toàn phương.
Mở rộng cho trường hợp D ⊂ Rm với m ≥ 1 ta có
Hệ quả 1.3.1. (Corollary 1, [7]) Cho C là tập con đóng của Rn , D là
tập con lồi của Rm và L (x, y) : Rn × D → R là một hàm liên tục. Giả
thiết các điều kiện sau được thỏa mãn:
(i) ∀x ∈ Rn hàm L (x, .) là affine;
(ii) ∀y ∈ D bất kì cực tiểu địa phương của L (x, y) trên C là cực tiểu
toàn cục của L (x, y) trên C;
(iii∗ ) Tồn tại y ∗ ∈ D sao cho L (x, y ∗ ) → +∞ khi x ∈ C, kxk → +∞
và sao cho
inf L (x, y ∗ ) = max inf L (x, y)
x∈C
y∈D x∈C
&
L (x∗ , y ∗ ) = min L (x, y ∗ ) (1.6)
x∈C
với duy nhất x∗ ∈ C.
Khi ấy ta có đẳng thức minimax
min sup L (x, y) = max inf L (x, y) .
x∈C y∈D
y∈D x∈C
Chứng minh. Đặt η := sup inf L (x, y).
y∈D x∈C
11
(1.7)
Luận văn thạc sĩ Toán học
nghiêm thị phượng
Xét tùy ý α > η và với mỗi y ∈ D đặt
Cα (y) := {x ∈ C| L (x, y) ≤ α}
Theo giả thiết (iii∗ ) ta có inf L (x, y ∗ ) = η, do đó
x∈C
Cη (y ∗ ) = {x ∈ C| L (x, y ∗ ) = η} = {x∗ } .
Với mỗi y ∈ D đặt Dy := [y ∗ , y] = {(1 − t) y ∗ + ty| 0 ≤ t ≤ 1} ⊂ R và
Ly (x, t) := L (x, (1 − t) y ∗ + ty) là một hàm xác định trên C × Dy . Ta
có thể dễ dàng thử lại, các tập C, Dy và hàm Ly (x, t) thỏa mãn tất cả
các điều kiện của Định lý 1.3.1.
Vì α > η ≥ sup inf L (x, t) nên
t∈Dy x∈C
∅=
6 Cα (y ∗ ) ∩ Cα (y) ⊂ Cα (y ∗ ) ⊂ C.
Ngoài ra, vì giả thiết L (x, y ∗ ) → +∞ khi x ∈ C, kxk → +∞, tập Cα (y ∗ )
là compact cho nên là Cα (y ∗ ) ∩ Cα (y) vì Cα (y) là đóng.
Cho α → η + thì được
∅=
6 Cη (y ∗ ) ∩ Cη (y) ⊂ Cη (y ∗ ) = {x∗ } .
Do đó,
L (x∗ , y) ≤ η
∀y ∈ D.
Vì vậy,
inf sup L (x, y) ≤ η.
x∈C y∈D
12
- Xem thêm -