Mở đầu 2
Chương 1. Các khái niệm cơ bản 4
1.1. Tập lồi . 4
1.1.1 Tổ hợp lồi . . . . 4
1.1.2 Tập a-phin, tập lồi đa diện . 6
1.1.3 Nón lồi . . 11
1.2. Hàm lồi . . . 15
Chương 2. Định lý tách các tập lồi. 21
2.1. Định lý tách 1 . 21
2.2. Định lý tách 2 . 26
Chương 3. Một số ứng dụng của định lý tách. 27
3.1. Điều kiện tối ưu . 32
3.2. Hệ bất đẳng thức lồi . . 36
3.3. Xấp xỉ tuyến tính của hàm lồi . .41
3.4. Sự tồn tại dưới vi phân của hàm lồi . 43
3.5. Ứng dụng trong phép vô hướng hóa bài toán véctơ . 46
Kết luận 51
Tài liệu tham khảo 52
52 trang |
Chia sẻ: mimhthuy20 | Lượt xem: 598 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Luận văn Phần chính của Luận văn, trong chương này tác giả trình bày nội dung hai định lý tách và hệ quả (Bổ đề Farkas), để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
.
1.2 Hàm lồi
Trong chương trình Toán phổ thông, chúng ta đã làm quen với khái niệm hàm lồi
một cách cơ bản. Mục này, chúng tôi trình bày khái niệm tổng quát về hàm lồi và
một số tính chất của nó.
Định nghĩa 1.14.
Cho tập nC R và :f C R . Ta sẽ ký hiệu
dom : |f x C f x ,
epi : , | f x C R f x .
Các tập dom f , epi f lần lượt được gọi là miền hữu dụng và trên đồ thị của hàm f .
Bằng cách cho f x nếu x C , ta có thể coi f được xác định trên toàn
không gian và
ndom : R |f x f x ,
16
epi : , | nf x R R f x .
Quy ước nếu 0 thì 0f x với mọi x .
Định nghĩa 1.15
Cho nC R lồi và :f C R . Ta nói f là hàm lồi trên C nếu epif là
một tập lồi trong 1nR . 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 .
Sau đây chủ yếu ta xét hàm : nf R R . Dễ thấy định nghĩa trên
tương đương với:
1 1 , , 0;1f x y f x f y x y C
Định nghĩa 1.16
Hàm : nf R R được gọi là lồi chặt trên C nếu
1 1 , , 0;1f x y f x f y x y C
Hàm : nf R R được gọi là lồi mạnh trên C với hệ số 0 nếu
211 1 - 1 - , , 0;1
2
f x y f x f y x y x y C
Nhận xét 1.4
Dễ dàng kiểm tra rằng hàm f lồi mạnh trên C với hệ số 0 khi và chỉ khi
hàm
2. : . .
2
h f
lồi trên C .
Sau đây ta sẽ đề cập đến một bất đẳng thức quen thuộc trong chương trình
phổ thông. Đây là bất đẳng thức tương đối tổng quát trong các bất đẳng thức về hàm
17
lồi. Các bất đẳng thức giữa trung bình cộng và trung bình nhân, Holder là những
trường hợp riêng của bất đẳng thức này.
Bất đẳng thức Jensen
Nếu f là hàm lồi và nhận giá trị hữu hạn trên tập lồi C thì
* 1 2, , ,..., mm N x x x C và 0j thỏa mãn
1
1
m
j
j
, ta có:
1 1
m m
j j
j j
j j
f x f x
.
Mệnh đề 1.8 (xem [2], mệnh đề 8.1)
Một hàm :f C R là lồi trên C khi và chỉ khi
, , , , 0;1 1 1 x y C f x f y f x y
Chứng minh
Điều kiện cần: Giả sử f lồi, chọn , , ,x y như đã nêu trong mệnh đề.
Chọn ' ,f x và ' ,f y . Vậy , ' , , ' epi x y f . Do epi f lồi nên
1 , 1 ' ' epi x y f .
1 1 ' ' 1f x y .
Điều kiện đủ: Chọn , , , epi x y f và 0,1 .Với mọi 0 , ta có
,f x f y .
Do đó nên
1 ' ' 1 1f .
1 , , epi x y f .
Vậy hàm f lồi.
18
Dưới đây là một định nghĩa khác, tương đương về hàm lồi, lồi mạnh dựa vào
khái niệm hệ số lồi.
Định nghĩa 1.17
Hàm : nf R R (không nhất thiết lồi), nC R 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 mọi
0,1 , mọi ,x y thuộc C , ta có
211 1 1
2
f x y f x f y x y .
Hiển nhiên, nếu 0 thì f lồi trên C . Nếu f có hệ số lồi trên C là 0 ,
thì f lồi mạnh trên C vớih hệ số lồi .
Định nghĩa 1.18
Một hàm f được gọi là chính thường nếu dom f và f x với mọi
x .
Hàm f được gọi là đóng nếu epi f là một tập đóng trong 1nR .
Nhận xét 1.5
a) Từ định nghĩa của epi f , ta thấy rằng một hàm lồi hoàn toàn được xác
định nếu biết epi f .
b) Nếu f là một hàm lồi trên một tập lồi C thì có thể thác triển f lên toàn
không gian bằng cách đặt
,
:
.e
f x x C
f x
x C
Hiển nhiên ef x f x với mọi x C và ef x lồi trên nR . Hơn nữa ef x là
chính thường khi và chỉ khi f chính thường. Tương tự, ef x đóng khi và chỉ khi
f đóng.
nếu
nếu
19
c) Nếu f là một hàm lồi trên nR thì dom f là một tập lồi, vì dom f chính là
hình chiếu trên nR của epi f , tức là:
dom | : , epi f x R x f .
Ví dụ 1.4 Một số hàm lồi
1. Hàm a-phin: ,f x a x , trong đó ,na R R . Dễ dàng kiểm tra
được rằng f là hàm vừa lồi vừa lõm trên toàn không gian.
Khi 0 thì hàm này được gọi là hàm tuyến tính.
2. Hàm chỉ:
Cho C là một tập lồi. Đặt
0 ,
:
.C
x C
x
x C
Ta nói C là hàm chỉ của C . Do C lồi nên C là một hàm lồi.
3. Hàm mặt cầu.
Cho : | x 1nS x R là một mặt cầu và :h S R là một hàm bất kỳ.
Định nghĩa hàm f như sau:
0 1,
: 1,
+ 1.
x
f x h x x
x
Hàm này được gọi là hàm mặt cầu. Dễ thấy rằng f là một hàm lồi trên nR .
4. Hàm tựa.
Hàm dưới đây được gọi là hàm tựa của C
( ) : sup ,C
x C
s y y x
.
5. Hàm khoảng cách.
nếu
nếu
nếu
nếu
nếu
20
Cho C lồi đóng, hàm khoảng cách đến tập C được định nghĩa bởi
: min .C y Cd x x y
6. Hàm chuẩn.
Giả sử 1,..., nx x x .
1: : max iif x x x
Hoặc
1
2 2 2
1: : ... nf x x x x .
21
Chương 2
ĐỊNH LÝ TÁCH CÁC TẬP LỒI
Trong giải tích lồi và nhiều lĩnh vực khác như giải tích hàm, giải tích không
trơn và giải tích phi tuyến, các định lý tách hai tập lồi có một vai trò trung tâm.
Về bản chất, định lý tách trả lời câu hỏi rằng một phần tử có thuộc một tập lồi
không, và nếu không thuộc thì nó sẽ có tính chất gì? Ví dụ tập lồi là nghiệm của hệ
phương trình đại số, hay vi tích phân, tập các điểm bất động của một ánh xạ, hay là
tập nghiệm của một bài toán tối ưu Nếu điểm thuộc tập lồi đó thì vấn đề được
giải quyết, trái lại, nếu không thì sẽ xảy ra điều gì? Điều này giải thích vì sao các
định lý tách thuộc loại các định lý chọn và là công cụ rất mạnh, thường được dùng
để chứng minh sự tồn tại của một đối tượng trong nhiều vấn đề thuộc những lĩnh
vực khác nhau. Một mệnh đề thường được dùng làm nền tảng lý thuyết tối ưu hiện
đại là định lý tách các tập lồi, mà một dạng tương đương của nó trong giải tích hàm
là định lý Hahn – Banach rất quen thuộc trong giải tích hàm.
2.1. Định lý tách 1
Định nghĩa 2.1
Cho , nC C R (không nhất thiết lồi) và y là véc tơ bất kỳ, đặt
: inf .C x Cd y x y
Ta nói Cd y là khoảng cách từ y đến C . Nếu tồn tại C sao cho
Cd y y , thì ta nói là hình chiếu (vuông góc) của y trên C . Ký hiệu
Cp y .
Mệnh đề 2.1 (xem [2], mệnh đề 5.1)
Cho C là một tập lồi đóng khác rỗng trong nR . Khi đó:
(i) Với mọi , ny R C hai tính chất sau là tương đương:
22
a) Cp y ,
b) ( )Cy N .
(ii) Với mọi ny R , hình chiếu ( )Cp y của y trên C luôn tồn tại và duy nhất.
(iii) Nếu y C , thì , 0C Cp y y x p y là siêu pẳng tựa của C tại ( )Cp y
và tách hẳn y khỏi C , tức là
, 0,C Cp y y x p y x C ,
và
, 0C Cp y y y p y .
Chứng minh
(i) Giả sử có a). Lấy x C và 0,1 . Đặt
: 1x x .
Do ,x C và C lồi, nên x C . Hơn nữa do là hình chiếu của y , nên
y y x . Hay
22y x y .
Khai triển vế phải, ước lược và chia hai vế cho 0 , ta có
2 2 , 0x x y .
Điều này đúng với mọi x C và 0,1 . Do đó khi cho tiến đến 0 ta được
, 0 y x x C .
Vậy Cy N .
Bây giờ giả sử có b). Với mọi x C , có
23
2
0
= .
T T
T
y x y x y y
y y x y
Từ đây và b), dùng bất đẳng thức Cauchy – Scharz ta có:
2 Ty y y x y y x .
Suy ra y y x x C , và do đó ( )p y .
ii) Do ( ) infC x Cd y x y , nên theo định nghĩa của cận dưới đúng (infimum), tồn
tại một dãy kx C sao cho
lim ( )k Ck x y d y .
Vậy dãy kx bị chặn, do đó nó có một dãy con kjx hội tụ đến một điểm nào
đó. Do C đóng nên C . Vậy
lim limkj k Cj ky x y x y d y .
Chứng tỏ là hình chiếu của y trên C .
Bây giờ ta chỉ ra tính duy nhất của hình chiếu. Thật vậy, nếu tồn tại hai điểm và
1 đều là hình chiếu của y trên C , thì
1 1, C Cy N y N .
Tức là
1, 0y
và
1 1, 0y
Cộng hai bất đẳng thức này ta suy ra 1 0 , và do đó 1 .
iii) Do Cy N , nên
24
, 0 y x x C .
Vậy , ,y x y là một siêu phẳng tựa của C tại . Siêu phẳng này
tách y khỏi C vì y , nên
2, 0y y y .
Mệnh đề 2.2 (xem [2], mệnh đề 5.4)
Cho C là một tập lồi khác rỗng và 0x riC . Khi đó tồn tại siêu phẳng tựa
của C tại hình chiếu của 0x trên C .
Chứng minh
Gọi hình chiếu của 0x trên C là 0( )p x
Trước hết xét trường hợp int C . Vậy 0 intx C . Phân biệt trường hợp:
a) 0x C . Do C lồi, đóng, nên theo (iii) của mệnh đề 2.1, siêu phẳng
0 0 0 0 0( ) , ( ) , ( )p x x x p x x p x
là siêu phẳng tựa của C tại 0( )p x tách hẳn C và 0x .
b) 0x C . Khi đó do 0 intx C , nên 0 \nx R C . Vậy tồn tại dãy 0kx x
với kx C với mọi k . Do C lồi, đóng, nên lại áp dụng (iii) của Mệnh đề 2.1, tồn tại
siêu phẳng tựa của C tại ( )kp x . Tức là tồn tại 0k , thỏa mãn:
, , ( ) k k kx p x x C .
Bằng cách chuẩn hóa k , ta có thể coi 1k , và do đó có thể giả sử 0k .
Do ánh xạ chiếu liên tục, nên từ bất đẳng thức trên, qua giới hạn và chú ý là
0 0( )p x x (Vì 0x C ), ta có:
0 0 0 0 0, , ( ) = , x p x x x C .
Vậy 0 0 0, = , x x x C là siêu phẳng tựa của C tại 0x .
25
Định nghĩa 2.2
Cho hai tập C và D khác rỗng, ta nói siêu phẳng Ta x tách C và D nếu
, , T Ta x a y x C y D .
Ta nói siêu phẳng Ta x tách chật C và D nếu
, , T Ta x a y x C y D .
Ta nói siêu phẳng Ta x tách mạnh C và D nếu
y D
sup inf , , T T
x C
a x a y x C y D
.
Bổ đề 2.1
Cho nC R là một tập lồi khác rỗng. Giả sử 0x C . Khi đó tồn tại
, 0nt R t thỏa mãn
0, ,t x t x .
Chứng minh
Do 0x riC , nên sự tồn tại siêu phẳng tách trong bổ đề được suy ra từ mệnh đề 2.2.
Định lý 2.1 (Định lý tách 1) (xem [2], định lý 6.1)
Cho C và D là hai tập lồi khác rỗng trong nR sao cho C D . Khi đó
có một siêu phẳng tách C và D .
Chứng minh
Do C và D là lồi, nên C D cũng lồi. Hơn nữa, 0 C D , vì C D .
Theo bổ đề 2.1 áp dụng với 0 0x , tồn tại véc tơ , 0nt R t sao cho , 0t z với
mọi z C D . Vì z x y , với , x C y D , nên ta có
, , , t x t y x C y D .
Lấy : sup , ,
y D
t y
26
khi đó siêu phẳng ,t x tách C và D .
2.2 Định lý tách 2
Bổ đề 2.2 (xem [2], bổ đề 6.2)
Cho nC R là một tập lồi đóng khác rỗng sao cho 0 C . Khi đó tồn tại một
véc-tơ , 0nt R t và 0 sao cho
, 0, t x x C .
Chứng minh
Do C đóng và 0 C , nên tồn tại quả cầu B tâm ở gốc, bán kính 0r sao
cho C B . Áp dụng định lý tách 1 cho hai tập C và B , ta có \ 0nt R và
R , sao cho
, , , t x t y x C y B .
Bằng chuẩn hóa ta có thể xem 1t và do đó khoảng cách từ gốc đến siêu phẳng ít
nhất là bằng r . Vậy thì
, 0t x r .
Nhận xét 2.1
Theo bổ đề này thì C và điểm gốc tọa độ có thể tách mạnh, ví dụ bởi siêu
phẳng ,
2
t x .
Định lý 2.2 (Định lý tách 2) (xem [2], định lý 6.2)
Cho C và D là hai tập lồi đóng khác rỗng sao cho C D . Giả sử có ít
nhất một tập là com-pắc. Khi đó hai tập này có thể tách mạnh được bởi một siêu
phẳng.
Chứng minh
Giả sử C là tập Compact. Ta chỉ ra tập C D đóng.
27
Thật vậy, giả sử kz C D và kz z . Ta có k k kz x y với , k kx C y D . Vì
C compact, nên có một dãy con jkx x khi j . Vậy
j j jk k ky x z x z D . Vậy z x y C D . Chứng tỏ C D là tập đóng.
Do 0 C D nên theo bổ đề 2.2, tồn tại 0t sao cho , 0t x y với mọi
,x C y D . Vậy
inf , sup ,
2 2x C y D
t x t y
.
Chứng tỏ C và D có thể tách mạnh.
Nhận xét 2.2
Điều kiện một trong hai tập là com-pắc trong định lý là không thể bỏ được
Ví dụ 2.1
Cho hai tập hợp:
2
2
: , | 0, 0 ,
1: , | , 0, 0
C x t R x t
D x t R t t x
x
.
Rõ ràng hai tập này lồi, đóng, không có điểm chung, nhưng chúng không thể tách
mạnh được.
Hình 1.
. . . . . .
. . . . . . . .
. . . . . . .
. . . . . . . .
. . . . . . .
. . . . D . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . .
. . . .
C O
28
Từ định nghĩa ta thấy rằng, nếu hai tập nằm trong cùng một siêu phẳng, thì
chúng vẫn tách được, ví dụ chính bằng siêu phẳng đó. Để tránh trường hợp này
người ta đưa ra khái niệm tách đúng sau:
Định nghĩa 2.3
Hai tập C và D được gọi là tách đúng bởi siêu phẳng Ta x nếu
, , T Ta x a y x C y D
và cả hai tập này không cùng nằm trọn trong siêu phẳng tách.
Mệnh đề 2.3 (xem [2], mệnh đề 6.1)
Cho hai tập lồi khác rỗng A và B . Điều kiện cần và đủ để hai tập này tách
đúng là ri riA B .
Chứng minh
Điều kiện cần
Giả sử có siêu phẳng Tt x tách A và B , tức là
' ' , , T Tt x t y x A y B .
Giả sử siêu phẳng này không chứa B , khi đó , riTt y y B . Suy ra
ri riA B .
Điều kiện đủ
Giả sử ri riA B . Khi đó, 0 ri ri riA B A B . Xét hai trường hợp:
i) Trường hợp int A B .
Khi đó 0 int A B . Vậy tồn tại 0t và , int , intT Tt x t y x A y B . Đặt
inf | int , sup | intT Tt y y B t x x A , thì . Lấy . Khi đó siêu
phẳng Tt x sẽ tách A và B , nhưng không thể đồng thời chứa cả A và B .
ii) Trường hợp int A B .
29
Đặt C A B và F là không gian con song song với bao a-phin của C .
Khi đó, áp dụng lập luận ở phần trên cho không gian F , sẽ tồn tại một siêu phẳng
'H (trong F ) tách đúng A và B . Gọi 't là phiếm hàm tuyến tính từ F R xác
định siêu phẳng 'H . Gọi F là không gian vuông góc với F . Với mỗi nx R đặt
t x là hàm hợp giữa 't và p , trong đó p là ánh xạ chiếu xuống không gian con
F . Do p là tuyến tính, nên dễ thấy t và 't cũng là tuyến tính và là siêu phẳng tách
đúng hai tập A và B .
Nhận xét 2.3
Nếu A và B là hai tập lồi mà ri riA B , thì hai tập này vẫn có thể tách
được.
Ví dụ 2.2
A và B là hai đường chéo của một hình chữ nhật trong mặt phẳng 2-chiều.
Rõ ràng A và B là hai tập lồi mà ri riA B , chúng vẫn tách được bằng chính
mặt phẳng nhưng chúng không tách đúng được.
Một hệ quả rất quan trọng của định lý tách là bổ đề chọn mang tên nhà toán
học Hungary Farkas, được chứng minh từ năm 1892 dưới dạng một định lý hình
học. Bổ đề này rất trực quan, dễ áp dụng trong nhiều lĩnh vực như tối ưu, điều
khiển, lý thuyết toán tử
Hệ quả 2.1 (Bổ đề Farkas) (xem [2], hệ quả 6.1)
Cho A là một ma trận thực cấp m n và na R . Khi đó trong hai hệ dưới
đây có một hệ và chỉ duy nhất một hệ có nghiệm:
0, 0TAx a x với một nx R , (2.1)
, 0TA y a y với một my R . (2.2)
Một cách phát biểu tương đương dưới ngôn ngữ hình học là:
30
Nửa không gian | 0Tx a x chứa nón | 0x Ax khi và chỉ khi véc tơ a
nằm trong nón sinh bởi các hàng của ma trận A tức là
0 0T TA x a x khi và chỉ khi , 0TA y a y
Tính chất hình học của bổ đề này rất rõ. Nó nói rằng nón lồi, đóng
| 0x Ax nằm trong nửa không gian | 0Tx a x khi và chỉ khi véc tơ pháp tuyến
a ở trong nón sinh bởi các hàng của ma trận A .
Hình 2
Chứng minh
Giả sử (2.2) có một nghiệm y nào đó. Nếu như 0Ax , thì từ TA y a , nhân
tích vô hướng với x , và do 0, 0Ax y , ta có 0T Ta x y Ax . Vậy (2.1) không thể
có nghiệm.
Giả sử hệ (2.2) không có nghiệm. Lấy tập
| 0 : TC x y A y x
Hiển nhiên C là tập lồi đóng và 0 C .
0Ax
. . . . . . .
. . . . . .
. . . . . . .
. . . . . . .
. . . . a . . . .
. . . .
. . . .
31
Do (2.2) không có nghiệm nên a C . Theo định lý tách 2, tồn tại 0p và một số
R sao cho T Tp a p x với mọi x C . Do 0 C nên 0 .Thay Tx A y , với
0y , ta viết được T T Tp A y y Ap .
Bên cạnh đó, nếu x C thì x C với mọi 0 . Vì từ Tx A y , có
Tx A y . Vậy các tọa độ của y có thể lớn tùy ý, nên từ bất đẳng thức
T T Tp A y y Ap , suy ra 0Ap .
Vậy, ta đã chỉ ra sự tồn tại của một véc tơ p sao cho 0Ap và 0Ta p . Chứng tỏ
rằng (2.1) có nghiệm.
32
CHƯƠNG 3
ỨNG DỤNG CỦA ĐỊNH LÝ TÁCH
3.1. Điều kiện tối ưu.
Định nghĩa 3.1.
Cho nC R khác rỗng và : nf R R .
Một điểm *x C được gọi là điểm cực tiểu địa phương của f trên C 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à điểm cực đại địa phương nếu 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 .
Nếu
* f x f x x C
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à nếu
* f x f x x C
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.
Bài toán OP: Tìm cực tiểu của một hàm lồi trên một tập lồi có dạng sau
min f x với các điều kiện
0, 1,...,ig x i m ,
0, 1,...,jh x j k
x X
33
Trong đó nX R là một tập lồi đóng khác rỗng và , 1,...,if g i m là các hàm lồi
hữu hạn trên X , còn 1,...,jh j k là các hàm a-phin hữu hạn trên tập a-phin của
X . Ta sẽ luôn giả sử rằng X có điểm trong và các hàm aphin 1,...,jh j k độc
lập tuyến tính trên X , theo nghĩa, nếu
1
0
k
j j
j
h x
với mọi x X , thì 0j với
mọi j .
Bài toán (OP) này được gọi là một quy hoạch lồi. Hàm f được gọi là hàm mục
tiêu. Các điều kiện , 0 1,...,ix X g x i m , 0, 1,...,jh x j k được gọi là
ràng buộc. Tập
: | 0 1,..., , 0, 1,...,i jD x X g x i m h x j k .
đượ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 nhận
được của bài toán (OP). Do X là tập lồi, các hàm 1,...,ig i m lồi trên X và
1,...,jh k aphin, 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 dựng hàm sau, được gọi là hàm
Lagrange, cho bài toán (OP):
0
1 1
, , :
m k
i i j j
i j
L x f x g x h x
.
Dựa vào hàm Lagrange, ta có kết quả sau:
Định lý 3.1 (Karush – Kuhn - Tucker) (xem [2], Định lý 9.1)
Nếu *x là nghiệm của bài toán quy hoạch lồi (OP) thì tồn tại
* 0 0,1,...,i i m và * 1,...,j j k không đồng thời bằng 0 sao cho
* * * * *, , min , ,
x X
L x L x
(điều kiện đạo hàm triệt tiêu)
* * 0 1,..,i ig x i m (điều kiện độ lệch bù)
Hơn nữa nếu int X và điều kiện Slater sau thỏa mãn
34
0 0: 0 1,...,ix D g x i m
thì *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 (OP).
Chứng minh
Giả sử *x là nghiệm của (OP).
Đặt
*0 1 1 0: , ,..., , ,..., | : , , 1,..., , , 1,...,m k i i j JC x X f x f x g x i m h x j k
Do X lồi, , if g lồi và jh a-phin hữu hạn trên X nên C là một tập lồi
khác trống trong 1m kR . Hơn nữa 0 C . Thật vậy, vì nếu trái lại 0 C , thì tồn tại
một điểm chấp nhận được x thỏa mãn *f x f x . Điều này mâu thuẫn với việc
*x là nghiệm tối ưu của (OP).
Khi đó theo định lý tách 1, tồn tại * *0,1,..., , 1,...,i ji m j k không đồng
thời bằng 0 sao cho
* * 0 1 1
0 1
0 , ,..., , ,...,
m k
i i i i m k
i j
C
. (3.1)
Chú ý rằng với mọi 0 ,..., 0m , thì 0 1,..., , ,...,m k 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 cả * * *0 1, ,..., 0m . Hơn nữa,
với mọi 0 và x X , ta lấy
*0 , 1,..., , 1,...,i i j jf x f x g x i m h x j k ,
thì 0 ,..., , 0,...,0m C . Thay vào (3.1) và cho 0 , sẽ được
* * * * * * * * *0 0
1 1 1 1
m k m k
i i i i i i i i
i i i i
f x g x h x f x g x h x x X
.
Hay
* * * * *, , , , L x L x x X .
35
Đây chính là điều kiện đạo hàm triệt tiêu.
Để chứng minh độ lệch bù, ta chú ý rằng do *x chấp nhận được, nên
* 0 ig x i . Nếu như tồn tại một i nào đó mà *ig x , thì với mọi 0 , ta có
,..., , ,..., , 0,...,0 C ( ở vị trí thứ 1i )
Thay vào (*) và cho 0 , ta thấy * 0i . Nhưng 0 , nên * 0i . Suy ra * 0i .
Điều kiện độ lệch bù do đó cũng được thỏa mãn.
Để chứng minh điều kiện đủ, ta giả sử điều kiện Staler thỏa mãn. Ta có
*
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à điều kiện độ
lệch bù, ta có
* * * * * *
1 1 1 1
0
m k m k
i i j j i i j j
i j i j
g x h x g x h x x X
.
Thế nhưng do *0 0 , nên phải có hoặc * 0i với một i nào đó, hoặc nếu * 0i với
mọi i , thì sẽ có * 0j với một j nào đó.
Trong trường hợp đầu, thay 0x vào bất đẳng thức trên sẽ được
* * * * * 0 * 0
1 1 1 1
0 <0
m k m k
i i j j i i j j
i j i j
g x h x g x h x
.
Mâu thuẫn.
Trong trường hợp sau, ta có:
* * *
1 1
0
k k
j j j j
j j
h x h x x X
Do int X và jh aphin với mọi j , nên từ đây suy ra
0
0
k
j
j
h x x X
. Từ đây
và do các hàm jh độc lập tuyến tính trên X , ta có * 0 j j . Điều này mâu thuẫn
với việc tất cả các nhân tử *i và
*
j không đồng thời bằng 0. Vậy *0 0 .
Do *0 0 , nên bằng cách chia cho *0 0 , ta có thể coi hàm Lagrange là
36
1 1
, ,
m k
i i j j
i j
L x f x g x h x
.
Từ đ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 được, ta có:
* * * *0
1 1 1 1
m k m k
i i j j i i j j
i j i j
f x f x g x h x g x h x f x
.
Chứng tỏ *x là lời giải tối ưu của (OP).
Nhận xét 3.1
Khi X là tập mở (nói riêng là toàn không gian) và mọi hàm đều khả vi, thì
điều kiện đạo hàm triệt tiêu sẽ là
* * * * * *0 0
1 1
0
m k
j j i i
j i
f x g x h x
.
Như vậy, bài toán trên cho ta thấy một cách định lượng khi xét một bài toán
tìm cực tiểu của một hàm lồi trên một tập lồi. Người ta cũng đã chứng minh một
cách định tính được rằng 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 (xem [2] chương 9,mệnh đề 9.1).
Tính chất trên không thể áp dụng cho cực đại của hàm lồi: Cực đại địa
phương của một hàm lồi không nhất thiết là cực đại tuyệt đối.
Ví dụ 3.1
Xét hàm số 2( )f x x trên đoạn 1, 2 .
Hàm số 2( )f x x đạt cực đại địa phương trên đoạn 1, 2 là 1x , nhưng
điểm cực đại tuyệt đối lại là 2x .
3.2. Hệ bất đẳng thức lồi
Trong phần này chúng ta sử dụng định lý tách để tìm điều kiện cần và đủ để
hệ bất đẳng thức lồi có nghiệm.
Định nghĩa 3.2
37
Cho nD R là một tập lồi và 1,..., mf f là các hàm lồi trên
nR . Hệ bất đẳng thức
, 0,ix D f x i I
Được gọi là hệ bất đẳng thức lồi, trong đó I là tập chỉ số và ký hiệu có thể hiểu
là hoặc .
Hệ bất đẳng thức lồi xuất hiện trong nhiều ứng dụng. Do tính chất của hàm
lồi, tập nghiệm của một hệ bất đẳng thức lồi luôn là một tập lồi. Dựa vào các định lý
tách, ta có thể đưa ra những điều kiện cần và đủ về sự tồn tại nghiệm của một hệ bất
đẳng thức lồi.
Mệnh đề 3.1 (xem [2], mệnh đề 9.5)
Giả sử 0 1, ,..., mf f f là các hàm lồi hữu hạn trên tập lồi D . Khi đó, hệ
, 0, 0,1,...,ix D f x i m (3.2)
không có nghiệm, khi và chỉ khi tồn tại các số 0 0,1,...,i i m không đồng thời
bằng 0 sao cho
0
0
m
i i
i
f x x D
.
Ngoài ra, nếu có điều kiện chính quy Slater: tồn tại 0 0, 0ix D f x với mọi
1,...,i m thì 0 0 .
Chứng minh
Điều kiện đủ là hiển nhiên, nên ta chỉ cần chứng minh điều kiện cần.
Giả sử hệ (3.2) không có nghiệm. Đặt
10 1: , ,..., | , , 0,...,mm i iC y y y y R x D f x y i m .
Do D và if lồi 0,...,i m nên C lồi. Theo giả thiết hệ (9.4) không có nghiệm nên
0 C . Áp dụng định lý tách, tồn tại 0 1, ,..., 0m sao cho
38
0
0
m
i i
i
y y C
.
Chú ý rằng theo định nghĩa của C , với mọi x D và 0 , ta có
0 ,..., mf x f x C .
Vậy
0
0
m
i i
i
f x x D
.
Điều này đúng với mọi 0 , nên suy ra
0
0
m
i i
i
f x x D
. (3.3)
Ta sẽ chứng tỏ 0 i i . Thật vậy, nếu trái
Các file đính kèm theo tài liệu này:
- luanvanthacsi_chuaphanloai_175_3648_1870038.pdf