MỤC LỤC
Trang
Mục lục . 1
Mở đầu . 2
Chương 1
ĐỊNH LÍ DUBOVITSTKII-MILYUTIN
1.1. Các kiến thức bổ trợ 4
1.2. Định lý Dubovitskii-Milyutin . 7
Chương 2
TỔNG QUÁT HOÁ ĐỊNH LÍ DUBOVITSTKII-MILYUTIN
2.1. Các xấp xỉ nón 18
2.2. Các tổng quát hoá của định lý Dubovitskii-Milyutin . 25
Chương 3
ĐIỀU KIỆN CẦN CHO NGHIỆM HỮU HIỆU CỦA
BÀI TOÁN ĐA MỤC TIÊU
3.1. Các khái niệm 32
3.2. Định lý luân hồi kiểu Tucker 36
3.3. Điều kiện chính quy 43
3.4. Điều kiện cần Kuhn-Tucker 48
KẾT LUẬN 54
TÀI LIỆU THAM KHẢO 55
MỞ ĐẦU
Lý thuyết các điều kiện tối ưu đóng một vai trò quan trọng trong lý
thuyết tối ưu hóa. Năm 1965, A. Ya. Dubovitskii và A. A. Milyutin [1] đã đưa
ra lý thuyết các điều kiện cần tối ưu dưới ngôn ngữ giải tích hàm và cho ta
phương pháp giải tích hàm hiệu quả để nghiên cứu các bài toán tối ưu và điều
khiển. Công trình nổi tiếng của Dubovitskii-Milyutin [1] đánh dấu một bước
phát triển quan trọng của lý thuyết tối ưu hóa.
I. Lasiecka [4] đã tổng quát hóa các kết quả của Dubovitskii-Milyutin
trên cơ sở chứng minh một mở rộng của định lý tách. Chú ý rằng các điều
kiện tối ưu của định lý Dubovitskii-Milyutin dựa trên việc tách một nón chấp
nhận được và một nón tiếp tuyến, trong đó nón chấp nhận được là xấp xỉ nón
của tập ràng buộc bất đẳng thức và tập mức của hàm mục tiêu. Còn kết quả
của Lasiecka [4] lại dựa trên tách một nón trong và một nón ngoài.
Sử dụng định lý Dubovitskii-Milyutin, Đ. V. Lưu và N. M. Hùng [5] đã
thiết lập một định lý luân hồi kiểu Tucker cho hệ bao gồm các bất đẳng thức,
đẳng thức và một bao hàm thức. Từ đó Lưu-Hùng [5] đã chứng minh các điều
kiện cần Kuhn-Tucker với các nhân tử Lagrange dương ứng với các thành
phần của hàm mục tiêu cho nghiệm hữu hiệu của bài toán tối ưu đa mục tiêu
với các ràng buộc bất đẳng thức, đẳng thức và ràng buộc tập trong không gian
định chuẩn.
Luận văn trình bày các định lý Dubovitskii-Milyutin, các mở rộng của
chúng và ứng dụng để dẫn các điều kiện cần Kuhn-Tucker cho nghiệm hữu
hiệu của bài toán tối ưu đa mục tiêu với các ràng buộc bất đẳng thức, đẳng
thức và ràng buộc tập trong không gian định chuẩn.
Luận văn bao gồm phần mở đầu, ba chương, kết luận và danh mục các
tài liệu tham khảo.
Chương 1 trình bày các định lý của Dubovitskii-Milyutin về điều kiện tối
ưu tổng quát và một số kết quả có liên quan.
Chương 2 trình bày các kết quả của Lasiecka [4] về các tổng quát hóa
các điều kiện tối ưu của Dubovitskii-Milyutin trên cơ sở chứng minh một
định lý tách cho một nón trong và một nón ngoài không tương giao.
Chương 3 trình bày một ứng dụng của định lý Dubovitskii-Milyutin để
thiết lập một định lý luân hồi kiểu Tucker cho hệ các bất đẳng thức, đẳng
thức, bao hàm thức và dẫn các điều kiện cần cho nghiệm hữu hiệu của bài
toán tối ưu đa mục tiêu với các ràng buộc bất đẳng thức, đẳng thức và ràng
buộc tập. Chú ý rằng các nhân tử Lagrange ứng với tất cả các thành phần hàm
mục tiêu ở đây là dương.
56 trang |
Chia sẻ: maiphuongtl | Lượt xem: 1747 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Luận văn Về định lí Dubovitstkii - Milyutin và điều kiện tối ưu, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
, cho nên
.L K
Bây giờ ta lấy
1
.
n
i
i
x K
Ta sẽ chứng minh
1
.
n
i
i
x K
Đặt
, , ,x x x
trong đó
, , , .x X x x x L
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
9
Khi đó,
là một phiếm hàm tuyến tính trên
L . Ta có
, 0 ,x x L K
bởi vì
, , .x x x L K
1
.
, , 0.
n
i
i
x K
x x x
Áp dụng định lý 1.1, tồn tại
X
sao cho
, 0 , (1.3)
, , . (1.4)
x x K
x x x L
Giả sử
1, , .n
Khi đó, với mọi
,x X
thì
, ,x x x L
và từ
(1.4) ta có
1
1
, , = , = , .
.
n
i
i
n
i
i
x x x x x
x
Từ (1.3), ta suy ra
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
10
1
, 0 , 1, , .
, 0 .
1, , .
n
i i i i
i
i i i i
i
x x K i n
x x K
K i n
1
11
.
.
n
i
i
n n
i i
ii
x K
K K
Mặt khác, theo mệnh đề 1.3,
1 1
.
nn
i i
i i
K K
Do đó, định lý được chứng minh.
Định lý 1.3 (Dubovitskii-Milyutin)
Giả sử
1 2 1, , , ,n nK K K K
là các nón lồi đỉnh tại 0; Các nón
1 2, , ,K K
nK
mở. Khi đó,
1
1
1, , 1
n
i i i
i
K x K i n
không đồng thời bằng
0, sao cho
1 1 0. (1.5)
n nx x x
Chứng minh
a
Điều kiện cần. Giả sử 1
1
.
n
i
i
K
Trường hợp 1 :
1
.
n
i
i
K
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
11
Đặt
1
: .
n
i
i
K K
Khi đó,
,K
mở và
1 .nK K
Theo mệnh đề 1.2,
tồn tại
, 0x X x
sao cho
1, , , .nx y x x x K y K
Bởi vì K là nón có đỉnh tại 0, cho nên từ mệnh đề 1.1 ta suy ra
1, 0 , , .nx y x x x K y K
(1.6)
Từ đó,
1
.
n
i
i
x K K
Áp dụng định lý 1.2 ta nhận được
1
, 1, , .
n
i i i
i
x x x K i n
Đặt
1nx x
. Khi đó, từ (1.6) suy ra
1 1n nx K
. Hơn nữa
1 0nx
và
1 1 0.n nx x x
Trường hợp 2 :
1
.
n
i
i
K
Khi đó, tồn tại
: 1s s n
sao cho
1
1 1
, .
s s
i i
i i
K K K
Áp dụng trường hợp 1 (với s đóng vai trò là n) ta nhận được
1 1, , 1 , 0i i sx K i s x
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
12
sao cho
1 1 0.s sx x x
Chọn
2 1 0s nx x
ta nhận được (1.5).
b
Điều kiện đủ. Giả sử tồn tại
1, , 1ix i n
không đồng thời bằng
0 sao cho
1 1 0,n nx x x
nhưng 1
1
.
n
i
i
K
Do đó, tồn tại
0 1, , 1ix K i n
. Đồng thời, tồn tại chỉ số
: j
1 j n
sao cho
0jx
, bởi vì nếu không thì
1
1
0
n
n i
i
x x
, vì thế
1 ,x
1, nx
đồng thời bằng 0.
Ta có
0, > 0jx x
( bởi vì
jK
mở, nếu
0, = 0,jx x
thì tồn tại
1 jx K
sao cho
1, < 0 (!)jx x
). Do đó,
1 1 0 00 , , 0 :n n jx x x x x x
vô lí (!).
Định nghĩa 1.1
Véc tơ v được gọi là phương giảm của hàm
f x
tại
0x
, nếu tồn tại lân
cận U của v, số
0
và số
0 0
sao cho
00, , ,u U
ta có
0 0 (1.7) f x u f x
Các phương giảm của f tại
0x
lập thành nón mở có đỉnh tại 0.
Hàm f được gọi là giảm đều, nếu nón các phương giảm của f tại
0x
là lồi.
Định nghĩa 1.2
Véc tơ v được gọi là phương chấp nhận được của tập Q tại
0x
, nếu tồn
tại lân cận U của v, số
0 0
sao cho
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
13
0 00, , : u U x u Q
Tập các phương chấp nhận được lập thành một nón ta gọi là nón chấp
nhận được của Q tại
0x
.
Các phương chấp nhận được của tập Q tại
0x
lập thành nón mở với đỉnh
tại 0.
Ta gọi hạn chế Q loại bất đẳng thức là đều tại
0,x
nếu nón các phương
chấp nhận được tại
0x
là lồi.
Đối với các hạn chế loại đẳng thức, tức là không có điểm trong, nón các
phương chấp nhận được (theo định nghĩa 1.2) bằng
.
Định nghĩa 1.3
Véc tơ v được gọi là phương tiếp xúc với Q tại
0x
, nếu
0 00, 0, , x Q
sao cho
0 ,x x v r
trong đó
r X
sao cho với bất kì lân cận U của 0: r
U
với mọi
0
đủ nhỏ.
Tập các phương tiếp xúc với Q tại
0x
lập thành một nón ta gọi là nón tiếp
tuyến của Q tại
0x
.
v là phương chấp nhận được của Q tại
0x
v là phương tiếp xúc của Q
tại
0x
.
Các phương tiếp xúc với Q tại
0x
lập thành một nón có đỉnh tại 0. Nón
các phương tiếp xúc không đóng cũng không mở. Trong nhiều trường hợp
nón đó là một không gian con.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
14
Ta nói hạn chế Q loại đẳng thức là đều tại
0x
, nếu nón các phương tiếp
xúc với Q tại
0x
là lồi.
Định lí 1.4 (Dubovitskii-Milyutin)
Giả thiết:
i
Hàm
f x
đạt cực tiểu địa phương trên 1
1
:
n
i
i
Q Q
tại
;x Q
ii
f x
giảm đều tại
,x
với các nón phương giảm
0;K
iii
Hạn chế loại bất đẳng thức
1, ,iQ i n
là đều tại
,x
với nón
các phương chấp nhận được
;iK
iv
Hạn chế loại đẳng thức
1nQ
là đều tại
,x
với nón các phương tiếp
xúc
1.nK
Khi đó, tồn tại
0,1, , 1i ix K i n
không đồng thời bằng 0 thỏa mãn
phương trình Euler - Lagrange:
0 1 1 0 (1.8)
n nx x x x
Chứng minh
Trước hết ta chứng minh rằng từ giả thiết
i
ta phải có 1
0
.
n
i
i
K
Điều
này có nghĩa là một phương giảm không là phương tiếp xúc theo tất cả các
hạn chế (Chú ý : một phương chấp nhận được cũng là phương tiếp xúc).
Phản chứng: 1
0
,
n
i
i
K
tức là tồn tại
1, , 1 .iv K i n
Theo định
nghĩa của
1, , ,iK i n
tồn tại
0 0
, lân cận U của v và số
0
sao cho
00, , :u U
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
15
1
, (1.9)
. (1.10)
n
i
i
x x u Q
f x u f x
Bởi vì v là phương tiếp xúc của
1nQ
tại
,x
cho nên
1 10, 0, ,
1nx Q
sao cho
1 (1.11) nx x v r Q
Chọn
2
để với mọi
20,
ta có
,
r
U v
hay là
(1.12)
r
u v U
Đặt
3 0 1 2, ,min
. Từ (1.11) và (1.12) suy ra
1 3 0,nx x u Q .
Từ (1.9) - (1.12) ta nhận được
1
3
1
0,
n
i
i
x Q
.
Từ (1.10), (1.12) ta có
3 0, . f x u f x f x
Như vậy,
x
không phải là cực tiểu địa phương của f trên Q : Mâu thuẫn với
giả thiết
i
(!). Do đó,
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
16
1
0
.
n
i
i
K
Từ các giả thiết
,ii iii
ta nhận được
0 1, , , nK K K
là các nón lồi mở
đỉnh tại 0. Theo giả thiết
1, niv K
là nón lồi đỉnh tại 0. Áp dụng định lí 1.3,
tồn tại
0,1, , 1i ix K i n
không đồng thời bằng 0 thỏa mãn (1.8).
Từ chứng minh định lý 1.4 ta suy ra 1
0
0
0.
n
i
i
K x
Mệnh đề 1.4 ([6])
Giả sử
1 2 3; : , 0 ; : , 0 ; : , 0 .X K x x K x x K x x
Khi đó,
1
2
,
3
,2
: ;
: 0 ;
0 ;
0.
nÕu
nÕu
a K
b K
X
c K
K
Định lý 1.5 (Fakas-Minkovskii)
Giả sử
: , 0, , 1, , ;m i i mK x a x a i n
Khi đó,
1
: 0, 1, , .
n
i
i i
i
K a y y i n
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
17
Chứng minh
Kí hiệu
: : , 0 .iiQ x a x
Khi đó,
1
n
i
i
K Q
. Theo mệnh đề 1.4,
: 0 .ii i iQ a y y
Xét tập :
1 1
: 0, 1, , .
n n
i
i i i
i i
Q a y y i n
Ta có
1
: 0, 1, ,
n
i
i i
i
a y y i n
là tập đóng trong
.m Bởi vì trong m tất cả các tôpô là trùng nhau, cho
nên
1
n
i
i
Q
là đóng * yếu trong
.m Theo [6, hệ quả 1.12.1],
11
,
n n
i i
ii
Q Q
tức là
1
: 0, 1, , .
n
i
i i
i
K a y y i n
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
18
Chương 2
TỔNG QUÁT HOÁ ĐỊNH LÍ DUBOVITSTKII-MILYUTIN
Chương 2 trình bày các tổng quát hóa các điều kiện tối ưu của Dubovitskii-
Milyutin. Các kết quả trong chương này là của I. Lasiecka [4].
2.1. CÁC XẤP XỈ NÓN
Trong chương này ta kí hiệu E là một không gian tôpô tuyến tính lồi địa
phương; A là một tập hợp trong E; 0x là điểm thuộc A;
U x
là lân cận của x
trong E;
OC x
là nón mở chứa x với đỉnh tại 0; S là một đơn hình trong E; I
là ánh xạ đồng nhất. Phát biểu
/ 0r U
được hiểu theo nghĩa sau:
10 , 0U
sao cho,
1(0, ), / 0r U
.
Hơn nữa,
1
, 1 .
n
n n
i
i
p
0'P x
kí hiệu đạo hàm Fréchet của toán tử P tại 0.x
Các định nghĩa về xấp xỉ nón cũng như là mối quan hệ của chúng được
trình bày trong mục này. Các định nghĩa của nón trong và xấp xỉ lồi cấp một
được cho bởi Neustadt [9].
Định nghĩa 2.1
Nón trong
0,IC A x
của A tại 0x là nón lồi không tầm thường (nghĩa là
nón chứa các điểm khác với đỉnh) thoả mãn các điều kiện sau:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
19
0 0 , , ,i x IC A x OC x IC A x
sao cho
0 ii U x
thỏa mãn
0 0 0\x OC x U x x A
.
Định nghĩa 2.2
Xấp xỉ lồi cấp một
CAI A
của A là một tập lồi thoả mãn các điều kiện
sau:
;i O CAI A
ii CAI A
chứa ít nhất một điểm khác O;
1 2 0 , , , , 0 , , 0n iiii x x x CAI A U x n sao cho
0, , : np E 0
thỏa mãn
1
0 ;
n
i i
i
x U A
iv
là ánh xạ liên tục.
Các định nghĩa của nón chấp nhận được và nón tiếp tuyến của A được
cho bởi Dubovitskii-Milyutin [1].
Nhắc lại rằng nón chấp nhận được của A tại 0x được xác định bởi
0 1, | 0, { AC A x x E U x
sao cho
010, , , .}x U x x x A
Nhắc lại rằng nón tiếp tuyến của A tại 0x được xác định bởi
0 1, | 0{ TC A x x E
sao cho
10, , r E
thỏa mãn
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
20
0x x r A
, trong đó
/ 0 .} r U
Một nón chấp nhận được hoặc nón tiếp tuyến được gọi là chính quy, và
được kí hiệu tương ứng bởi
0,RAC A x
hoặc
0, ,RTC A x
nếu nó là nón lồi.
Sự tồn tại của nón trong kéo theo sự tồn tại của xấp xỉ lồi cấp một. Thật vậy,
ta chỉ cần đặt:
I
trong định nghĩa 2.2 là được.
Hơn nữa, một kết luận trực tiếp của hai định nghĩa nhắc lại ở trên là
0 0, , .AC A x TC A x
Các quan hệ của
0 0, , ,IC A x CAI A x
và
0 0, , ,AC A x TC A x
được trình bày trong các bổ đề sau.
Bổ đề 2.1
Mọi
0,IC A x
được chứa trong
0, 0AC A x
và mọi nón lồi mở nằm
trong
0, 0AC A x
là một nón trong.
Chứng minh
Ta sẽ chỉ ra rằng mọi nón trong được chứa trong một nón chấp nhận
được. Thật vậy, giả sử
0x
sao cho
0,x IC A x
và
0,x AC A x
.
Khi đó,
0 0, ,OC x IC A x U x
sao cho
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
21
0 0 0\ ,x OC x U x x A
(2.1)
1 10, , 0, ,U x x U x sao cho
0 .x x A
(2.2)
Kí hiệu
\ 0 .U x OC x
Ta chọn
1
sao cho
0 010, , .x x U x
Như vậy,
0 0 010, , .x x x OC x U x
Vì thế , (2.1) kéo theo
0 .x x A
Điều này mâu thuẫn với (2.2).
Để chứng minh phần hai của bổ đề 2.1 giả sử OC là nón lồi mở bất kì
nằm trong
0, 0AC A x
và
0 .x OC
Theo định nghĩa nón chấp nhận
được, ta có
1 0, U x
sao cho
010, , , x U x x x A
. (2.3)
Giả sử
1U x
là lân cận bất kì của
x
nằm trong
OC
. Đặt
0 1
0
,
: , 0 .
U x U x U x
OC x x x U x
Giả sử
0U x
là lân cận bất kì của 0x với tính chất sau: nếu
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
22
0x U x
và
0 0x x U x
thì
1.
Bây giờ việc kiểm tra
OC x
và
0U x
thoả mãn tất cả các điều kiện của định
nghĩa 2.1 là đơn giản. Thật vậy,
0 0 ,x x OC x U x
ta có
0 ,x x x
trong đó
0x U x
và
1.
Vì thế, (2.3) kéo theo
x A
, điều này kết thúc việc chứng minh
OC
là một
nón trong.
Từ bổ đề 2.1 ta nhận được hệ quả sau.
Hệ quả 2.1
0 , 0RAC A x
là nón trong của A tại 0.x
Bổ đề 2.2
Mọi nón lồi nằm trong
0\CAI A x
thì nằm trong
0, .TC A x
Chứng minh
Giả sử C là một nón lồi nằm trong
0\CAI A x
và
x C
. Khi đó, tồn
tại một đơn hình
S C
với các đỉnh
0 10, , , nx x x
sao cho
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
23
0
.
n
i i
i
x x
Điều này suy ra từ tính lồi của C. Từ định nghĩa 2.2 ta suy ra
0 ,U
0 0
sao cho
00, , : ,
np E
(2.4)
thỏa mãn
0
1
0 \ , 0 0 .
n
i i
i
x u A x u U
Đặt
0 ,r u
trong đó
0 0u U
.
Khi đó, (2.4) kéo theo
0 .x x r A
Vì vậy,
0, x TC A x
.
Định nghĩa 2.3
Nón ngoài
0,EC A x
của A tại 0x là nón lồi không tầm thường thỏa mãn
các điều kiện sau:
0 01, , , x EC A x OC x U x
sao cho với mọi
0 01 ,U x U x
0 0x OC x A U x
.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
24
Bổ đề trình bày ở dưới chỉ ra rằng nón ngoài là một loại xấp xỉ yếu hơn
nón tiếp tuyến; nón ngoài thực chất là một loại xấp xỉ yếu nhất.
Bổ đề 2.3
Mọi nón lồi nằm trong nón tiếp tuyến là một nón ngoài.
Chứng minh
Giả sử C là một nón lồi nằm trong
0,TC A x
và
x C
. Khi đó,
1 > 0,
10, , 0 r U
sao cho
0 .x x r A
(2.5)
Giả sử
OC x
là một nón mở bất kì chứa x. Khi đó
0 0
sao cho
00, ,
0 0/ .x x r x OC x
(2.6)
Kí hiệu
2 0 1
0
2
, ,
/ , 0, .
min
x x x r
Khi đó, (2.5) và (2.6) kéo theo
020, , .x x OC x A
Vì vậy,
0 3 2, 0,U x
sao cho
0 03 3/x x r U x
.
Từ đó, ta nhận được
0 03, , , ,x C OC x U x x x
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
25
sao cho
0 03x x OC x U x A
. (2.7)
Từ (2.7) ta suy ra
0 0 0 0, \ ;U x x OC x U x x
Do đó, C là một nón ngoài của A tại 0x theo định nghĩa 2.3.
Từ bổ đề 2.3 ta nhận được hệ quả sau.
Hệ quả 2.2
0,RTC A x
là một nón ngoài của A tại 0.x
Nhận xét 2.1
Không phải mọi nón ngoài đều là nón tiếp tuyến. Chẳng hạn một dãy vô
hạn các điểm mà nó không có nón tiếp tuyến mặc dù nó có nón ngoài là
1 0, 2 , 0,1,2, , 0.nA x x n x
Ở đây,
là nón ngoài của A tại 0x nhưng nón tiếp tuyến của A không
tồn tại. Từ các kết quả trên ta có quan hệ thứ tự giữa các xấp xỉ nón như sau:
RAC IC CAI TC EC
trong đó
A B
có nghĩa là nếu A tồn tại thì B tồn tại.
2.2. CÁC TỔNG QUÁT HÓA CỦA ĐỊNH LÝ DUBOVITSKII-MILYUTIN
Điều kiện cần tối ưu được cho bởi Dubovitskii-Milyutin dựa trên việc
tách một nón chấp nhận được và một nón tiếp tuyến, trong đó nón chấp nhận
được là một xấp xỉ nón của tập hợp được mô tả bởi các ràng buộc bất đẳng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
26
thức và tập mức của hàm mục tiêu, còn nón tiếp tuyến là xấp xỉ của tập được
mô tả bởi các ràng buộc đẳng thức. Neustadt sử dụng việc tách một nón trong
và một xấp xỉ cấp một.
Một định lý được phát biểu dưới đây chỉ ra rằng với giả thiết nào đó, các
nón trong và ngoài có thể tách được. Những xấp xỉ này yếu hơn những xấp xỉ
đã được sử dụng bởi Dubovitskii-Milyutin và Neustadt vì
CAI EC
và
TC EC
.
Định lý 2.1 (Định lý tách).
Giả sử các điều kiện sau thoả mãn:
0 , , ; ;i A B E int A x A B
0 ii U x
sao cho
0 ;int A B U x
iii
Tồn tại
0,IC A x
và
0, .EC B x
Khi đó,
0,IC A x
và
0,EC B x
tách được.
Chứng minh
Ta cần chỉ ra rằng
0 0, , \ 0 .IC A x EC B x
Giả sử điều này không đúng. Khi đó, tồn tại
0x
sao cho
0 0, , .x IC A x EC B x
Từ định nghĩa 2.1, suy ra
0 00, ,OC x IC A x U x
sao cho
0 0 00 \ .x OC x U x x A
(2.8)
Bởi vì
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
27
0,x EC B x
,
cho nên
01U x
sao cho
0 01 ,U x U x
0 0 0\ .x OC x U x B x
(2.9)
Kí hiệu
0 0 02 1 0: ;U x U x U x
Từ (2.8) và (2.9) ta suy ra
0 0 0
2
0 0 0
2
\ ,
\ . (2.10)
x OC x U x x A
x OC x U x B x
Như vậy, tồn tại 0x x sao cho
0 02 . (2.11) x x OC x U x A B
Hơn nữa, từ (2.10) và (2.11) kéo theo x là một điểm trong của A. Từ (2.11),
ta có
0 .x int A B U x
Điều này mâu thuẫn với giả thiết
ii
.
Dựa trên định lý 2.1, định lý tiếp theo chỉ ra rằng điều kiện tối ưu
Dubovitskii-Milyutin có thể suy rộng được.
Định lý 2.2 ( Định lý Dubovitskii-Milyutin suy rộng )
Giả sử
00 1
0
, , , ; ; ;
n
n i
i
i A A A E B E x A B
ii
Tồn tại
0, , 0, ,iIC A x i n
và
0, ;EC B x
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
28
01 iii U x
sao cho
0 01 ,U x U x
0 0
0
\ .
n
i
i
int A B U x x
Khi đó, tồn tại các phiếm hàm tuyến tính liên tục
0 01, , 0, , , , ,i i nf IC A x i n f EC B x
không đồng thời bằng 0 sao cho
1
0
0.
n
i
i
f
Chứng minh
Trước hết, ta giả sử rằng
0
0
, 0 .
n
i
i
IC A x
Khi đó,
0
0
,
n
i
i
IC A x
là nón trong của
0
.
n
i
i
A
Định lý 2.1 có thể áp dụng cho các tập
0
n
i
i
A
và B.
Do đó, tồn tại một phiếm hàm tuyến tính liên tục
f E
sao cho
0
0
0
0, , , (2.12)
0, , . (2.13)
n
i
i
f x x IC A x
f x x EC B x
Từ định lý 1.2 ta suy ra
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
29
0
,
n
i
i
f f
trong đó
0, .i if IC A x
(định lý 1.2 có thể áp dụng được vì
0,iIC A x
là các nón lồi mở và có giao
khác rỗng). Kí hiệu
1nf f
.
Như vậy, (2.13) kéo theo
01 ,nf EC B x
và 1
0
0.
n
i
i
f
Điều đó kết thúc chứng minh của định lý trong trường hợp
0
0
, 0 .
n
i
i
IC A x
Nếu
0
0
, 0 ,
n
i
i
IC A x
thì tồn tại
0 s n
sao cho
0
0
, 0 .
n
i
i
IC A x
Dùng lập luận tương tự, ta nhận được
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
30
1
0
0,
n
i
i
f
trong đó
2 1 0s nf f
Chú ý rằng các điều kiện cần tối ưu Dubovitskii-Milyutin có thể phát
biểu như là hệ quả đơn giản của định lý 2.2, bởi vì nón tiếp tuyến là một loại
xấp xỉ mạnh hơn nón ngoài.
Một phát biểu khác của điều kiện tối ưu Dubovitskii-Milyutin được gọi
là định lý Dubovitskii-Milyutin đối ngẫu .
Trong định lý đối ngẫu ta xấp xỉ tập ràng buộc bất đẳng thức bởi nón
chấp nhận được và tập mức của phiếm hàm bởi một nón ngoài (các ràng buộc
đẳng thức được loại bỏ hoặc diễn đạt bởi hai ràng buộc bất đẳng thức).
Cho
:F E
và
0 0 0| .A x E F x F x x
Định lý 2.3 (Định lý đối ngẫu).
Giả sử
00 1
0
, , , ; ;
n
n i
i
i A A A E x A
ii
Tồn tại
0, , 1, ,iRAC A x i n
và
00 ;EC A x
iii F x
đạt giá trị cực tiểu địa phương tại 0x trên tập
0
.
n
i
i
A
Khi đó, tồn tại các phiếm hàm tuyến tính liên tục
0 00 0, , 1, , , , ,i if RAC A x i n f EC A x
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
31
không đồng thời bằng 0 sao cho
0
0.
n
i
i
f
Chứng minh suy trực tiếp từ định lý 2.2. Thật vậy, ta đặt
0.B A
Bởi vì 0x là cực tiểu địa phương của
F x
trên
0
,
n
i
i
A
cho nên
0 0
1
\ .
n
i
i
int A B U x x
Chú ý rằng
0, 0iRAC A x
là một nón trong của A (hệ quả 2.1). Khi đó, tất cả các giả thiết của định lý 2.2
thoả mãn , và do đó ta nhận được định lý 2.3.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
32
Chương 3
ĐIỀU KIỆN CẦN CHO NGHIỆM HỮU HIỆU CỦA
BÀI TOÁN ĐA MỤC TIÊU
Chương 3 trình bày các tổng quát hóa của định lý luân hồi Tucker cho hệ
các bất đẳng thức, đẳng thức và bao hàm thức trên cơ sở các định lý
Dubovitskii-Milyutin đã trình bày trong chương 1, và các điều kiện cần Kuhn-
Tucker với tất cả các nhân tử Lagrange dương ứng với các thành phần của
hàm mục tiêu, cho nghiệm hữu hiệu của bài toán tối ưu đa mục tiêu với các
ràng buộc bất đẳng thức, đẳng thức và ràng buộc tập trong không gian định
chuẩn. Các kết quả của chương này là của Đ. V. Lưu - N. M. Hùng [5].
3.1. CÁC KHÁI NIỆM
Giả sử X là một không gian tuyến tính định chuẩn và A là một tập con
khác rỗng của X. Cho f, g và h là các ánh xạ từ X tương ứng vào
, p q
và
.
r Chú ý f, g, h có thể viết như sau:
1 2 1 2 1 2 , , , , , , , , , , , , p q rf f f f g g g g h h h h
trong đó
, , : 1, , ; 1, , ; 1, , .k j lf g h X k p j q l r
Trong chương này ta nghiên cứu bài toán quy hoạch đa mục tiêu sau đây:
,
0, 1, , ;
0, 1, , ;
.
VP
j
l
min f x
g x j q
h x l r
x A
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
33
Kí hiệu M là tập chấp nhận được của bài toán
VP
: 0, 0, 1, , ; 1, , .j lM x A g x h x j q l r
Nhắc lại rằng một điểm
x M
được gọi là nghiệm hữu hiệu địa phương
của bài toán
VP
nếu tồn tại số
0
sao cho
; ,x M B x
\ 0 ,pf x f x
trong đó
p
là orthant không âm của
, ;p B x
kí hiệu hình cầu mở tâm
x
bán kính
. Điều này có nghĩa
x M
là một nghiệm hữu hiệu địa phương
của bài toán
VP
nếu tồn tại số
0
sao cho không tồn tại
;x M B x
thỏa mãn
, 1, , ,k kf x f x k p
i if x f x
với một
1, ,i p
nào đó.
Nhắc lại nón tiếp liên của A tại
x A
là tập sau:
; : , 0 sao cho , .n n n nCC A x v X v v t x t v A n
Nón các phương tiếp tuyến dãy (hoặc nón radian dãy) của A tại
x A
là
tập sau:
; : 0 sao cho , .n nZC A x v X t x t v A n
Chú ý cả hai nón trên là khác rỗng. Nón
;CC A x
là đóng và nó có thể
không lồi;
; ; .ZC A x CC A x
Giả sử
f
là hàm thực xác định trên X. Các đạo hàm theo phương sẽ được
sử dụng sau đây:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
34
Đạo hàm Dini dưới của hàm
f
tại
x X
theo phương
v X
là
0
; ;
t
f x tv f x
Df x v lim inf
t
Đạo hàm Dini trên của hàm
f
tại
x X
theo phương
v X
là
0
; ;
t
f x tv f x
Df x v lim sup
t
Đạo hàm Hadamard dưới của hàm
f
tại
x X
theo phương
v X
là
, 0 ,
; ;
t u v
f x tu f x
df x v lim inf
t
Đạo hàm Hadamard trên của hàm
f
tại
x X
theo phương
v X
là
, 0 ,
; ;
t u v
f x tu f x
df x v lim sup
t
Nếu
; ; ,Df x v Df x v
thì ta kí hiệu giá trị chung của chúng là
; .Df x v
Đó là đạo hàm theo phương thông thường của
f
tại
x X
theo
phương
v X
. Trong trường hợp
;.Df x
là ánh xạ tuyến tính liên tục thì
f
gọi là khả vi Gâteaux tại
x
và
; , ,GDf x v f x v
trong đó
G f x
kí hiệu là đạo hàm Gâteaux của
f
tại
x
và
,G f x v
là giá trị của phiếm hàm tuyến tính
G f x
tại điểm v. Như vậy, nếu
f
khả
vi Fréchet tại
x
với đạo hàm Fréchet
f x
thì
; ,Df x v f x v
.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
35
Tương tự, nếu
; ;df x v df x v
thì ta kí hiệu giá trị chung của chúng là
; .df x v
Đó là đạo hàm Hadamard của
f
tại
x
theo phương v. Chú ý nếu
;df x v
tồn tại thì
;Df x v
cũng tồn tại và chúng bằng nhau.
Đặt
1, , : 0 ;
: , 0, 0,
1, , ; 1, , ; 1, ,
: , 0, 0,
1, , , ; 1, , ; 1, , 1, , .
;
j
k k j l
i
k k j l
I x j q g x
Q x A f x f x g x h x
k p j q l r
Q x A f x f x g x h x
k p k i j q l r i p
Nếu với mỗi một
;v ZC A x
mà
; 1, ,lDh x v l r
tồn tại, thì ta đặt
; ; : ; 0, 1, , ,
; 0, ,
; 0, 1, , .
D k
j
l
C Q v ZC A x Df x v k p
Dg x v j I x
Dh x v l r
Nếu với mỗi một
;v CC A x
mà
; 1, ,ldh x v l r
tồn tại, thì đặt
; ; : ; 0, 1, , ,
; 0, ,
; 0, 1, , .
d k
j
l
C Q v CC A x df x v k p
dg x v j I x
dh x v l r
Do tính thuần nhất dương của các đạo hàm theo phương Dini và Hadamard
dưới nên
;DC Q x
và
;dC Q x
là các nón đỉnh tại 0.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
36
3.2. ĐỊNH LÝ LUÂN HỒI KIỂU TUCKER
Để dẫn điều kiện cần Kuhn-Tucker cho nghiệm hữu hiệu. Trong mục
này, ta nghiên cứu các định lý luân hồi cho một hệ gồm các bất đẳng thức, các
đẳng thức và một bao hàm thức.
Giả sử X là một không gian tuyến tính định chuẩn với không gian liên
hợp
.X
Giả sử
, ,k j la b c
là các véc tơ thuộc
1, , ; 1, , ; 1,X k p j q l
,r
và A là một tập con khác rỗng của X. Với
1,...,i p
, ta đặt
: , 0 1, , ; ,
: , 0 ,
: , 0 1, , ,
: , 0 1, , .
k k
i i
j j
l l
A v X a v k p k i
A v X a v
B v X b v j s
C v X c v l r
Chú ý
kA
và
1, , ; ; 1, ,jB k p k i j s
là các nón lồi đóng có đỉnh tại 0,
iA
là nón lồi mở có đỉnh tại 0 và
1, ,lC l r
là các không gian con tuyến
tính đóng của X.
Định lý 3.1
Giả sử
a
K là một nón con lồi khác rỗng bất kì của
;CC A x
có đỉnh tại 0 và
K đóng;
b
Với mỗi
1, , ,i p
tập hợp:
1 1 1
p s r
k j l
k j l
k i
A B C K
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
37
đóng yếu trong
.X
Khi đó, hai phát biểu sau là tương đương:
i
Với mỗi
1, , ,i p
hệ sau
, 0, 1, , ; ; (3.1)
, 0, (3.2)
, 0, 1, , , (3.3)
, 0,
k
i
j
l
a v k p k i
a v
b v j s
c v
1, , , (3.4)
, (3.5)
l r
v K
không có nghiệm
v X
.
ii
Tồn tại
0 1, , , 0 1, , 1, , k j lk p j s và l r
sao cho
1 1 1
, , , 0 .
p s r
k k j j l l
k j l
a v b v c v v K
(3.6)
Nhận xét 3.1
(1) Nếu giả thiết
a
được thay bởi K là một nón con lồi khác rỗng của
;ZC A x
và K là đóng thì định lý 3.1 vẫn đúng bởi vì
; ; .ZC A x CC A x
(2) Trong trường hợp
,K X
bất đẳng thức (3.6) tương đương với
1 1 1
0.
p s r
k k j j l l
k j l
a b c
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
38
Chứng minh định lý 3.1
i ii
Ta chỉ cần xét trường hợp tất cả
0 1, , ka k p
bởi vì trong
trường hợp tồn tại
0
0ka
thì ta lấy
0
1k
là được. Với mỗi
1, , ,i p
giả
sử hệ
(3.1)-(3.5)
không có nghiệm
v X
. Đặt
1 1 1
,
p s r
i k j l
k j l
k i
D A B C K
ta thấy rằng
iD
là một nón lồi đóng khác rỗng trong X có đỉnh tại 0 và
.i iA D
Chú ý
iA
là một nón lồi khác rỗng có đỉnh tại 0, bởi vì
0.ia
Từ định lí 1.3
suy ra tồn tại
i iA
và
i iD
không đồng thời bằng 0 sao cho
0 i i
(3.7)
Từ
3.7
suy ra ngay rằng
0i
(cũng như
0i
). Bởi vì các nón lồi
, ,k jA B
1, , ; ; 1, , ; 1, ,lC k p k i j s l r
và K là đóng cho nên nó là đóng yếu.
Vì thế các giả thiết của định lý 1.2 là thoả mãn. Sử dụng định lý 1.2, ta có
1 1 1
.
p s r
i k j l
k j l
k i
D A B C K
(3.8)
Mặt khác, do mệnh đề 1.4 ta có
: 0 , 1, , ; ; k kA a k p k i
: 0 i iA a
(cũng như
0ia
);
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
39
: 0 , 1, , ;
: , 1, , .
j j
l l
B b j s
C vc v l r
Bởi vì , 0ii iA cho nên i i ia với 0i . Do (3.8), tồn tại
0, 1, , ; , 0 1, , , 1, ,ik ij ilk p k i j s l r
và
i K
sao cho
1 1 1
.
p s r
i ik k ij j il l i
k j l
k i
a b c
Đặt
1, , ; , ,
1, , , 1, , ,
ik ik ii i
ij ij il il
k p k i
j s l r
ta có
0 1, , ; , 0, 0 1, ,ik ii ijk p k i j s và 1, , .il l r
Từ (3.7) suy ra
1 1 1
.
p s r
ik k ij j il l i
k j l
a b c K
Do đó,
1 1 1
, , , 0 .
p s r
ik k ij j il l
k j l
a v b v c v v K
(3.9i)
Chú ý rằng với mỗi
1, , ,i p
ta nhận được bất đẳng thức (3.9i). Cộng hai
vế của (3.9i) ,
1, ,i p
và đặt
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
40
1 1
,
p p
k ik j ij
i i
và
1
p
l il
i
,
ta nhận được
0, 0, 1, , ; 1, , ; 1, ,k j l k p j s l r
và
1 1 1
, , , 0 .
p s r
k k j j l l
k j l
a v b v c v v K
ii i
Giả sử tồn tại
0, 0k j
và
1, , ; 1, , ; l k p j s
1, , l r
thoả mãn
3.6
. Nếu
i
là sai thì phải tồn tại
1, ,i p
sao cho
hệ từ
3.1 - 3.5
có một nghiệm
0v X
. Từ đó suy ra
0 0 0
1 1 1
, , , 0.
p s r
k k j j l l
k j l
a v b v c v
Điều này mâu thuẫn với
3.6
. Định lý được chứng minh.
Hệ quả 3.1
Giả sử A là một tập lồi và với mỗi
1, , ,i p
tập hợp:
1 1 1
;
p s r
k j l
k j l
k i
A B C CC A x
đóng yếu trong X .
Khi đó, hai phát biểu sau là tương đương:
i
Với mỗi
1, , ,i p
hệ
3.1 - 3.5
mà K được thay bởi
;CC A x
không có nghiệm
.v X
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
41
ii
Tồn tại
0, 0, 1, , ; 1, , ; 1, , k j l k p j s l rsao cho
1 1 1
, , , 0 ; .
p s r
k k j j l l
k j l
a v b v c v v CC A x
Nhận xét 3.2
Trong trường hợp
; ,CC A x X
bất đẳng thức trên tương đương với
đẳng thức sau
1 1 1
0.
p s r
k k j j l l
k j l
a b c
Chứng minh hệ quả 3.1
Bởi vì A là lồi khác rỗng, cho nên
;CC A x
là một nón lồi đóng khác
rỗng. Áp dụng định lý 3.1 cho
;K CC A x
, ta nhận được hệ quả 3.1.
Với mỗi
1, , , i p
ta đặt
1 1 1
.
p s r
i k j l
k j l
k i
E A B C
Rõ ràng
1, ,iE i p
là một nón đóng khác rỗng có đỉnh tại 0.
Trong trường hợp
dim X
, do định lý Farkas-Minkowski, điều kiện
b
trong định lý 3.1 sẽ được thay bởi một điều kiện làm yếu hơn như trong
định lý sau.
Định lý 3.2
Giả sử
,dim X
K là một nón con lồi khác rỗng của
;CC A x
với
đỉnh tại 0 và K đóng. Giả thiết với mỗi
1, , ,i p
tập
iE K
đóng. Khi
đó, hai phát biểu sau là tương đương:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
42
i
Với mỗi
1, , ,i p
hệ
3.1 - 3.5
không có nghiệm
v X
.
ii
Tồn tại
0, 0k j
và
1, , ; 1, , ; 1, ,l k p j s l r sao
cho
3.6
đúng.
Chứng minh
Bởi vì
dim X
cho nên
*dim X = dim X
và vì thế các tô pô mạnh,
yếu, yếu trong X là trùng nhau. Do định lí 1.5 ta rút ra rằng với mỗi
1, ,i p
,
1 1 1
: 0, 0, ,
1, , , ; 1, , ; 1, , .
{
}
p s r
i ik k ij j il l ik ij il
k j l
k i
E a b c
k p k i j s l r
Do đó,
1 1 1
1, , .
p s r
i k j l
k j l
k i
E A B C i p
Vì vậy, theo giả thiết, tập hợp:
1 1 1
p s r
k j l
k j l
k i
A B C K
là đóng, và do đó nó đóng yếu. Như vậy tất cả các giả thiết của định lý 3.1
đúng và từ định lý 3.1 ta suy ra kết luận.
Trong trường hợp
dim X
và
A X
từ định lý 3.2 ta có thể nhận
được định lý luân hồi Tucker cổ điển như là một trường hợp đặc biệt.
Hệ quả 3.2
Giả sử
dim X
. Khi đó, hai phát biểu sau là tương đương:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
43
i
Với mỗi
1, ,i p
, hệ
3.1 - 3.4
không có nghiệm
.v X
ii
Tồn tại
0, 0, 1, , ; 1, , ; 1, ,k j l k p j s l r sao
cho
1 1 1
0.
p s r
k k j j l l
k j l
a b c
(3.10)
Chứng minh
Với
A X
thì
;CC A x X
và vì thế
; 0CC A x
. Hơn nữa, bởi
vì
,dim X
cho nên với mỗi
1, , ,i p iE
là một nón lồi đóng khác
rỗng trong X và
0 iE
. Vì vậy,
; ,i iE CC A x E
và do đó
;iE CC A x
là đóng trong
.X
Bây giờ ta áp dụng định lý 3.2
cho
A X
và suy ra
i
là tương đương với tồn tại
0, 0, 1, , ; 1, , ; 1, , k j l k p j s l r
sao cho
1 1 1
, , , 0 ; ,
p s r
k k j j l l
k j l
a v b v c v v CC X x X
bất đẳng thức trên tương đương với (3.10).
3.3. ĐIỀU KIỆN CHÍNH QUY
Bây giờ ta trở lại bài toán
VP
. Dưới đây chúng ta sẽ đưa vào hai điều
kiện chính quy kiểu Abadie dưới ngôn ngữ các đạo hàm theo phương Dini,
Hadamard và dẫn các điều kiện cần cho nghiệm hữu hiệu.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
44
Mệnh đề 3.1
Giả sử
.x M
a
Nếu với mỗi
;v CC A x
các đạo hàm theo phương Hadamard
1 ; , , ;rdh x v dh x v
tồn tại thì
1
; ; .
p
i
d
i
CC Q x C Q x
3.11
b
Nếu với mỗi
;v ZC A x
các đạo hàm theo phương Dini
1 ; ,Dh x v
, ;rDh x v
tồn tại thì
1
; ; .
p
i
D
i
ZC Q x C Q x
3.12
Chứng minh
Ta chỉ chứng minh
3.11
còn
3.12
được chứng minh tương tự. Trước
hết ta chỉ ra rằng với mỗi
1, ,i p
thì
; ; ,i idCC Q x C Q x
3.13
trong đó
; ; : ; 0, 1, , , ,
; 0, ,
; 0, 1, , .
i
d k
j
l
C Q x v CC A x d f x v k p k i
dg x v j I x
dh x v l r
Với
1, ,i p
, khi lấy
;iv CC Q x
thì sẽ tồn tại
0nt
và
nv v
sao
cho
in nx t v Q n
. Khi đó
n nx t v A n
, và do đó
;v CC A x
.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
45
Hơn nữa, với
1, ,i p
bởi vì
i
n nx t v Q
cho nên
, 1, , ; ;
0 , ;
0 , 1, , .
k n n k
j n n j
l n n l
f x t v f x k p k i
g x t v g x j I x
h x t v h x l r
Vì vậy,
; 0, 1, , ; ;
; 0, ;
; 0, 1, , .
k n n k
k
n n
j n n j
j
n n
l n n l
l
n n
f x t v f x
d f x v lim inf k p k i
t
g x t v g x
dg x v lim inf j I x
t
h x t v h x
dh x v lim l r
t
Do đó,
;idv C Q x
. Như vậy ta đã nhận được
3.13
. Từ
3.13
suy ra
1 1
; ; ; .
p p
i i
d d
i i
CC Q x C Q x C Q x
Chú ý rằng bao hàm thức ngược lại của (3.11) và (3.12) nói chung không
đúng. Vì thế, để dẫn đến các điều kiện cần cho nghiệm hữu hiệu của bài toán
VP
thì ta sẽ đưa vào điều kiện chính quy tại
x
kiểu Abadie sau đây:
1
1
; ; , (3.14)
; ; . (3.15)
p
i
d
i
p
i
D
i
C Q x CC Q x
C Q x ZC Q x
Các điều kiện đó là tổng quát hoá của các điều kiện chính quy Abadie suy
rộng trong
3 , 8 , 10
.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
46
Nếu với mỗi
;v CC A x
các đạo hàm theo phương Hadamard
;kdf x v
và
; 1, , ; 1, ,ldh x v k p l r
tồn tại thì với mỗi
1, ,i p
đặt
; ; : ; 0, ; 0, 1, , ; ,
; ; : ; 0, ,
; 0, 1, , ,
i
d i k
d j
l
L f x v CC A x df x v df x v k p k i
L M x v CC A x dg x v j I x
dh x v l r
trong đó M kí hiệu là tập chấp nhận được của bài toán
VP
.
Một điều kiện cần cho nghiệm hữu hiệu có thể phát biểu như sau.
Định lý 3.3
Cho
x
là một nghiệm hữu hiệu địa phương của bài toán (VP). Giả sử
jg j I x
là liên tục tại
x
và với mỗi
;v CC A x
các đạo hàm theo
phương Hadamard
; , ; 1, , ; 1, ,k ldf x v dh x v k p l r
tồn tại. Giả thiết
rằng điều kiện chính quy (3.14) đúng tại
x
. Khi đó, với mỗi
1, , , i p
; ;id dL f x L M x
(3.16)
Chứng minh
Giả sử ngược lại, tồn tại
0 1, ,i p
sao cho
0 ; ; .i ddL f x L M x
Điều đó kéo theo tồn tại
00 ; ; .
i
ddv L f x L M x
Bởi vì
00 ; ,
i
dv L f x
cho nên
0 0
0 0
; 0,
; 0, 1, , ; . (3.17)
i
k
df x v
df x v k p k i
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
47
Rõ ràng
0 ;dv C Q x
. Sử dụng điều kiện chính quy (3.14), ta có
0
1
; ,
p
i
i
v CC Q x
suy ra
00 ;iv CC Q x
. Bởi vậy, tồn tại
0nt
và
0nv v
sao cho
0in nx t v Q n
.
Vì thế
n nx t v A
, và
0 , 1, , ; ;
0, ;
0, 1, , .
k n n k
j n n
l n n
f x t v f x k p k i
g x t v j I x
h x t v l r
Hơn nữa, với
j I x
ta có
0.jg x
Do tính liên tục của
,jg j I x
tồn tại một số tự nhiên
1N
sao cho
1,n N
0 j n ng x t v j I x
.
Mặt khác, bởi vì
x
là một nghiệm hữu hiệu địa phương của bài toán
VP
cho nên tồn tại một số
0
sao cho không tồn tại
;x M B x
thoả mãn
, 1, , ,k kf x f x k p
i if x f x
với một
1, ,i p
nào đó.
Từ chứng minh trên suy ra tồn tại một số tự nhiên
1N N
sao cho
,n N
; .n nx t v M B x
Do đó,
, n N
0 0
. i n n if x t v f x
Điều đó dẫn đến
0 0
; 0.idf x v
Điều này mâu thuẫn với (3.17).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
48
Vì thế với mỗi
1,...,i p
thì (3.16) đúng.
Nhận xét 3.3
Định lý 3.3 là tổng quát của định lý 3.1 trong [8].
Nếu với mỗi
; ,v ZC A x
đạo hàm theo phương Dini
;kDf x v
và
; 1, , ; 1, , lDh x v k p l r
tồn tại thì với
1,..., ,i p
ta đặt
D
D
; ; : ; 0, ; 0, 1, , ; ,
; ; : ; 0, ,
; 0, 1, , .
i
i k
j
l
L f x v ZC A x Df x v Df x v k p k i
L M x v ZC A x Dg x v j I x
Dh x v l r
Chứng minh tương tự định lý 3.3 ta nhận được định lý sau.
Định lý 3.4
Cho
x
là một nghiệm hữu hiệu địa phương của bài toán (VP). Giả sử
jg j I x
là liên tục tại
x
và với mỗi
;v ZC A x
các đạo hàm theo
phương Dini
; , ; 1, , ; 1, ,k lDf x v Dh x v k p l r
tồn tại. Giả thiết
rằng điều kiện chính quy (3.15) đúng tại
x
. Khi đó, với mỗi
1, , ,i p
D D; ; .
iL f x L M x
3.4. ĐIỀU KIỆN CẦN KUHN-TUCKER
Trong mục này, ta giả sử các hàm
,k jf g
và
lh
trong bài toán
VP
khả
vi Gâteaux tại
x
với các đạo hàm Gâteaux
, và G k G j G lf x g x h x
1, , ; 1, , ; 1, , k p j q l r
và các hàm
jg j I x
là liên tục. Khi
đó, với mỗi
,v X
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
49
; ; , 1, , ,
; ; , 1, , ,
; ; , 1, , ,
k k G k
j j G j
l l G l
df x v Df x v f x v k p
dg x v Dg x v g x v j q
dh x v Dh x v h x v l r
và
; ; : , 0,
, 0, ,
, 0, 1, , .
d G k
G j
G l
C Q x v CC A x f x v k =1,…, p,
g x v j I x
h x v l r
Chú ý nếu các hàm
jg j I x
chỉ là khả vi Gâteaux tại
x
thì chúng
không nhất thiết liên tục tại
x
. Dùng các kí hiệu
, , ,k i j lA A B C
trong phần 3.2
và lấy
, ,
1, , ; ; 1, , ,
k G k j G j l G la f x b g x c h x
k p j I x l r
ta sẽ nhận được điều kiện cần Kuhn-Tucker cho nghiệm hữu hiệu của bài toán
VP
với các nhân tử Lagrange ứng với thành phần của hàm mục tiêu là
dương.
Định lý 3.5
Giả sử
x
là một nghiệm hữu hiệu địa phương của bài toán (VP); K là
một nón con lồi khác rỗng bất kì của
;CC A x
với đỉnh tại 0 và K là đóng.
Giả sử với mỗi
1, , ,i p
tập hợp:
1 1
p r
k j l
k j I x l
k i
A B C K
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
50
là đóng yếu trong
.X
Giả thiết rằng điều kiện chính quy (3.14) đúng tại
x
. Khi
đó, tồn tại
0, 0 k j
và
1, , ; 1, , ; 1, ,l k p j q l r
sao cho
1 1 1
, , , 0 ,
(3.18)
p q r
k G k j G j l G l
k j l
f x v g x v h x v v K
0 1, , . (3.19) j jg x j q
Chứng minh
Sử dụng định lý 3.3 ta rút ra với mỗi
1, , ,i p
hệ sau:
, 0, 1, , , ; (3.20)
, 0, (3.21)
, 0, , (3.22)
, = 0,
G k
G i
G j
G l
f x v k p k i
f x v
g x v j I x
h x v 1, , , (3.23)
, (3.24)
l r
v K
không có nghiệm
v X
.
Áp dụng định lý 3.1 với
, ,
1, , ; ; 1, ,
k G k j G j l G la f x b g x c h x
k p j I x l r
thì tồn tại
0, 0 k j
và
1, , ; ; 1, ,l k p j I x l r
thoả mãn
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
51
1 1
, , , 0
.
p r
k G k j G j l G l
k j I x l
f x v g x v h x v
v K
Với
j I x
ta lấy
0j
và ta thu được (3.18). Hơn nữa, ta cũng có (3.19),
bởi vì với
j I x
thì
0jg x
và với
j I x
thì
0.j
Hệ quả 3.3
Giả sử
x
là một nghiệm hữu hiệu địa phương của bài toán (VP) và A lồi.
Giả sử với mỗi
1, , ,i p
tập hợp:
1 1
;
p r
k j l
k j I x l
k i
A B C CC A x
là đóng yếu trong X . Giả thiết điều kiện chính quy (3.14) đúng tại x .
Khi đó, tồn tại
0, 0 1, , ; 1, , ; 1, ,k j lvà k p j q l r
sao cho (3.18) và (3.19) đúng, trong đó K được thay bởi
;CC A x
.
Chứng minh
Vì A là lồi khác rỗng nên
;CC A x
là một nón lồi đóng khác rỗng của
X. Áp dụng định lý 3.5 cho
;K CC A x
ta suy ra hệ quả 3.3.
Trong trường hợp X là hữu hạn chiều, ta nhận được điều kiện cần Kuhn-
Tucker cho nghiệm hữu hiệu sau đây.
Định lý 3.6
Giả sử
dim X và x
l một nghiệm hữu hiệu địa phương của bài
toán (VP); K là một nón con lồi khác rỗng bất kì của
;CC A x
với đỉnh tại 0
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
52
và K đóng. Giả sử với mỗi
1, , ,i p
tập
iE K
là đóng trong
,X
trong
đó
1 1
p r
i k j l
k j I x l
k i
E A B C
với
, , ,
1, , ; ; 1, , .
k G k j G j l G la f x b g x c h x
k p j I x l r
Giả thiết rằng điều kiện chính quy (3.14) đúng tại
x
. Khi đó, tồn tại
0, 0 k j
và
1, , ; 1, , ; 1, ,l k p j q l r
sao cho (3.18) và (3.19) đúng.
Chứng minh
Sử dụng định lý 3.3 ta suy ra với mỗi
1, ,i p
thì hệ
3.20 - 3.24
không có nghiệm
.v X
Phần còn lại của chứng minh này làm tương tự
như trong chứng minh định lý 3.5 bằng sử dụng định lý 3.2 thay thế cho
định lý 3.1.
Trong trường hợp
A X
kết quả sau đây chỉ ra rằng điều kiện
;iE CC A x
là đóng có thể bỏ qua được.
Hệ quả 3.4
Giả sử
, dim X A X
và
x
là một nghiệm hữu hiệu địa phương
của bài toán (VP). Giả thiết rằng điều kiện chính quy (3.14) đúng tại
x
. Khi
đó, tồn tại
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
53
0, 0 k j
và
1, , ; 1, , ; 1, ,l k p j q l r
sao cho
1 1 1
0, (3.25)
0 1, , . (3.26)
p q r
k G k j G j l G l
k j l
j j
f x g x h x
g x j q
Chứng minh
Cũng như trong chứng minh của hệ quả 3.2 với
A X
thì
;CC A x X
và
;i iE CC A x E
. Vì vậy,
;i CC A x
là đóng trong
.X
Áp dụng
định lý 3.6 với
A X
, suy ra tồn tại
0, 0 k j
và
1, , ; 1, , ; 1, ,l k p j q l r
sao cho (3.26) đúng và
1 1 1
, , , 0
; .
p q r
k G k j G j l G l
k j l
f x v g x v h x v
v CC A x X
Từ đó suy ra
1 1 1
0.
p q r
k G k j G j l G l
k j l
f x g x h x
Nhận xét 3.3
(a) Từ hệ quả 3.4 ta nhận được định lý 3.3 trong [8] như là một trường
hợp đặc biệt.
(b) Nếu nón
,CC A x
thay bởi nón
;ZC A x
thì định lý 3.5 và 3.6 vẫn
đúng.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
54
KẾT LUẬN
Luận văn đã trình bày các định lý Dubovitskii-Milyutin về điều kiện tối
ưu dưới ngôn ngữ giải tích hàm và một số kết quả liên quan, các tổng quát
hóa của các định lý Dubovitskii-Milyutin của Lasiecka [4], và ứng dụng của
các định lý Dubovitskii-Milyutin trong tối ưu đa mục tiêu không trơn. Phạm
vi áp dụng của các định lý Dubovitskii-Milyutin là rất rộng rãi. Nó cho ta
phương pháp giải tích hàm hữu hiệu để nghiên cứu các bài toán cực trị. Sau
công trình của Dubovitskii-Milyutin [1], hàng loạt các công trình khác về điều
kiện tối ưu tổng quát ra đời và đã mang lại những kết quả sâu sắc.
Việc phát triển và ứng dụng các định lý Dubovitskii-Milyutin trong lý
thuyết tối ưu không trơn là đề tài được nhiều tác giả quan tâm nghiên cứu.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
55
TÀI LIỆU THAM KHẢO
[1]. A. Ya. Dubovitskii, and A. A. Milyutin, Extremum Problems in presence
of constraints, Z. Vychisl. Mat. i Mat. Fiz. 5(1965), 395 - 453.
[2]. I. V. Girsanov, Lectures on Mathematical Theory of Extremum Problems,
Beclin- Heigenberg, Spring - Verlag, 1972.
[3]. G. Giorgi, B. Jiménnes and V. Novo, On constraint qualifications in
directionally differentiable multiobjective optimization problems, RAIRO
Oper. Res. 38 (2004), 255 - 274.
[4]. I. Lasiecka, Generalization of the Dubovitskii-Milyutin optimality
condition, Journal of Optimization Theory and Appl. 24 (1978), 421 - 436
[5]. D. V. Luu and N. M. Hung, On alternative theorems and necessary
condition for efficiency, Optimization (nhận đăng); Online DOI:
10.1080/0233193070 1761433 (2008).
[6]. D. V. Lưu, Lý thuyết các điều kiện tối ưu, Nhà xuất bản Khoa học và Kỹ
thuật 1999.
[7]. D. V. Lưu, Giải tích lồi, Nhà xuất bản Khoa học và Kỹ thuật, Hà Nội, 2000.
[8]. T. Maeda, Constraint qualifications in multiobjective optimization
problems: Differentiable case, J.Optim.Theory Appl. 80(1994), 483 - 500.
[9]. L. W. Neustadt, An abstract variational theory with applications to a
broad class of optimization problems, I, General theory, SIAM Journal
on Control, 4(1966), No 3, 505 - 527.
[10]. V. Preda and I. Chitescu, On Constraint qualifications in multiobjective
optimization problems: Semidifferentiable case, J. Optim. Theory Appl.
100 (1999), 417 - 433.
Các file đính kèm theo tài liệu này:
- doc569.pdf