VỀ ĐIỀU KIỆN CHÍNH QUY CẤP HAI VÀ ĐIỀU KIỆN TỐI ƯU CẤP HAI
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (902.4 KB, 27 trang )
ĐẠI HỌC THÁI NGUYÊN
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC SƯ PHẠM
TRƯỜNG ĐẠI HỌC SƯ PHẠM
-----------------o0o------------------
-----------------o0o------------------
NGUYỄN THỊ LAN ANH
NGUYỄN THỊ LAN ANH
VỀ ĐIỀU KIỆN CHÍNH QUY CẤP HAI
VÀ ĐIỀU KIỆN TỐI ƯU CẤP HAI
VỀ ĐIỀU KIỆN CHÍNH QUY CẤP HAI
VÀ ĐIỀU KIỆN TỐI ƯU CẤP HAI
Chuyên ngành: TOÁN GIẢI TÍCH
Mã số: 60.46.01
LUẬN VĂN THẠC SĨ TOÁN HỌC
LUẬN VĂN THẠC SĨ TOÁN HỌC
Người hướng dẫn khoa học:
PGS.TS Đỗ Văn Lưu
THÁI NGUYÊN - 2009
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
THÁI NGUYÊN - 2009
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
MỤC LỤC
MỞ ĐẦU
Trang
Lý thuyết các điều kiện tối ƣu trong tối ƣu đơn mục tiêu và đa mục tiêu
Mục lục..................................................................................................
1
trơn và không trơn phát triển rất mạnh mẽ và thu đƣợc nhiều kết quả đẹp đẽ
Mở đầu...................................................................................................
2
và phong phú. Lý thuyết các điều kiện tối ƣu cấp 2 là một bộ phận quan trọng
của lý thuyết các điều kiện tối ƣu.
Chƣơng 1
Từ các điều kiện cần ta có đƣợc tập các điểm dừng mà trong đó bao
ĐIỀU KIỆN TỐI ƢU CẤP HAI CHO BÀI TOÁN TỐI ƢU ĐƠN
hàm các nghiệm của bài toán tối ƣu. Các điều kiện đủ tối ƣu cấp 2 cho phép ta
tìm ra nghiệm của bài toán đó. Thông thƣờng ngƣời ta đƣa vào các tập tiếp
MỤC TIÊU
tuyến cấp 2, các tập tuyến tính hoá cấp 2 và các điều kiện chính quy cấp 2 và
1.1. Các khái niệm và định nghĩa..........................................................
4
1.2. Các tập tiếp tuyến cấp một và cấp hai..............................................
8
J. F. Bonnans, R. Cominetti và A. Shapiro [3] đã nghiên cứu các tập
1.3. Điều kiện chính quy cấp hai và điều kiện tối ƣu cấp hai..................
15
tiếp tuyến cấp 2 trong và ngoài, tập xấp xỉ cấp 2 trên, các khái niệm chính quy
từ đó dẫn tới các điều kiện tối ƣu cấp 2 kiểu Fritz John và Kuhn-Tucker.
cấp 2 và chính quy cấp 2 ngoài. Từ đó, các tác giả đã thiết lập các điều kiện
Chƣơng 2
cần tối ƣu cấp 2 với điều kiện chính quy Robinson, và các điều kiện đủ tối ƣu
ĐIỀU KIỆN CẦN TỐI ƢU CẤP HAI CHO BÀI TOÁN TỐI ƢU ĐA
cấp 2 cho bài toán tối ƣu đơn mục tiêu không trơn với ràng buộc nón. G. Bigi
MỤC TIÊU
và M.Castellani [4] đã nghiên cứu tập các phƣơng giảm cấp 2. Tập các
phƣơng chấp nhận đƣợc cấp 2 tập tiếp liên cấp 2 và các điều kiện chính quy
2.1. Kiến thức chuẩn bị...........................................................................
33
2.2. Điều kiện cần tối ƣu cho bài toán đa mục tiêu với ràng buộc tập...
37
ƣu Fritz John cấp 2 trên cơ sở phát triển một định lý luân phiên kiểu Motzkin,
2.3. Điều kiện cần tối ƣu Fritz John.......................................................
41
và các điều kiện cần tối ƣu Kuhn-Tucker cấp 2 với các điều kiện chính quy
2.4. Điều kiện tối ƣu Kuhn-Tucker.......................................................
45
KẾT LUẬN.............................................................................................
50
TÀI LIỆU THAM KHẢO......................................................................
51
cấp 2 kiểu Abadie và Guignard. Từ đó, các tác giả dẫn các điều kiện cần tối
cấp 2 kiểu Abadie và Guignard.
Luận văn tập trung trình bày các điều kiện chính quy cấp 2 và các điều
kiện tối ƣu cấp 2 dƣới ngôn ngữ tập tiếp tuyến cấp 2, tập tiếp liên cấp 2, tập
tuyến tính hoá cấp 2 và các đạo hàm theo phƣơng cấp 2.
Luận văn bao gồm phần mở đầu, hai chƣơng, kết luận và danh mục các
tài liệu tham khảo.
1
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
2
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Chƣơng 1
Chƣơng 1: Trình bày các nghiên cứu của J. F. Bonnans, R. Cominetti
và A. Shapiro [3] về các tập tiếp tuyến cấp 2 trong và ngoài, tập xấp xỉ cấp 2
ĐIỀU KIỆN TỐI ƢU CẤP HAI CHO BÀI TOÁN
trên, điều kiện chính quy cấp 2 và điều kiện chính quy cấp 2 ngoài. Với điều
TỐI ƢU ĐƠN MỤC TIÊU
kiện chính quy Robinson, các điều kiện cần tối ƣu cấp 2 cho bài toán tối ƣu
với ràng buộc nón không trơn đƣợc trình bày cùng với các điều kiện đủ tối ƣu
Chƣơng 1 trình bày các nghiên cứu của J.F.Bonnans, R.Cominetti và
A.Shapiro [3] về các tập tiếp tuyến cấp 2 trong và ngoài, tập xấp xỉ cấp 2 trên,
cấp 2.
Chƣơng 2: Trình bày các kết quả nghiên cứu của G. Bigi và
điều kiện chính quy cấp 2 ngoài và điều kiện chính quy cấp 2 cùng với các điều
M.Castellani [4] về điều kiện cần tối ƣu cấp 2 cho cực tiểu yếu địa phƣơng
kiện cần và đủ tối ƣu cấp 2 cho bài toán tối ƣu với ràng buộc nón.
của bài toán tối ƣu đa mục tiêu có ràng buộc trên cơ sở phát triển một định lý
1.1. CÁC KHÁI NIỆM VÀ ĐỊNH NGHĨA
luân phiên Motzkin không thuần nhất. Các nghiên cứu về tập tiếp liên cấp 2,
tập tuyến tính hoá cấp 2, các điều kiện chính quy cấp 2 kiểu Abadie và
Guignard đƣợc trình bày cùng với các điều kiện cần cấp 2 Fritz John và
1.1.1. Bài toán
Ta xét bài toán tối ƣu có dạng
Kuhn-Tucker.
min f(x),
(P)
Nhân dịp này tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo PGS.TS
x X
G(x) K,
Đỗ Văn Lƣu, ngƣời đã tận tình hƣớng dẫn, giúp đỡ tôi hoàn thành bản luận
trong đó X là không gian hữu hạn chiều, Y là không gian Banach,
văn này.
Tôi xin chân thành cảm ơn Ban chủ nhiệm khoa Toán trƣờng Đại học
K là một tập con lồi đóng của Y , hàm mục tiêu f : X R và ánh xạ
sƣ phạm - Đại học Thái Nguyên cùng các thầy cô giáo đã tham gia giảng dạy
ràng buộc G : X Y đƣợc giả thiết là khả vi liên tục hai lần. Kí hiệu
khoá học, xin chân thành cảm ơn gia đình, bạn bè đồng nghiệp và các thành
: G1 ( K ) là tập chấp nhận của bài toán ( P) .
viên trong lớp Cao học Toán K15 đã luôn quan tâm, động viên, giúp đỡ tôi
Một số bài toán tối ƣu có thể phát biểu dƣới dạng bài toán ( P) . Khi
trong suốt thời gian học tập và quá trình làm luận văn.
Y
Thái Nguyên, tháng 9 năm 2009
Nguyễn Thị Lan Anh
p
và K 0 R p q . Tập chấp nhận đƣợc của ( P) đƣợc xác định bởi
một số hữu hạn ràng buộc đẳng thức và bất đẳng thức, và ( P) trở thành
bài toán quy hoạch phi tuyến.
Ví dụ khác, ta xét không gian Y C () gồm các hàm liên tục : ¡
xác định trên không gian metric compăc trang bị chuẩn sup.
3
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
4
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
: sup ( ) .
1.1.2. Các khái niệm và định nghĩa
Giả sử h :Y R là hàm giá trị thực mở rộng.
Lấy K : C ( ) là nón của các hàm nhận giá trị không âm, tức là
Giả sử h(.) là hữu hạn tại điểm y Y ta kí hiệu h' ( y,d ) là đạo hàm
C ( ): C( ): ( ) 0, .
Trong trƣờng hợp này, ràng buộc G( x ) K
tƣơng ứng với
theo phƣơng của nó tại điểm y theo phƣơng d Y
g( x, ) 0 với mọi , trong đó g( x,.) : G( x )(.) . Nếu tập là vô
h' ( y;d ) : lim
t 0
hạn, ta nhận đƣợc một số vô hạn các ràng buộc, và (P) trở thành bài toán
h( y td ) h( y )
.
t
Nhắc lại [5] rằng nếu h(.) lồi, giá trị hữu hạn tại y, chính thƣờng trên
quy hoạch bán vô hạn.
Một cách tiếp cận khác để nghiên cứu điều kiện tối ƣu là xét các bài
toán tối ƣu có dạng
Y, y dom h thì h' ( y;d ) tồn tại và hữu hạn.
Ta cũng sử dụng đạo hàm theo phƣơng dƣới sau:
min g( F( x )),
(1.1)
xX
h ( y;d ) liminf
t 0
trong đó g : Y R là hàm lồi chính thƣờng nửa liên tục dƣới và
F : X Y . Bài toán này tƣơng đƣơng với bài toán tối ƣu sau (xem [7]):
min c,
(1.2)
( x ,c )X R
d ' d
h( y td') h( y )
.
t
Chú ý rằng trên đồ thị của h ( y,.) đóng và h ( y,.) là hàm nửa liên
tục dƣới. Nếu h(.) là lồi, nhận giá trị hữu hạn và liên tục tại y và do đó là
liên tục Lipschitz trong một lân cận của y , thì h ( y,.) h' ( y,.) . Nói
( F( x ),c ) epi( g ),
chung, nếu h là lồi, có thể gián đoạn, thì bao đóng của trên đồ thị của
trong đó epi( g ) : ( y,c ) Y R : g( y ) c là trên đồ thị của g và do đó
nó đƣợc xét nhƣ một trƣờng hợp riêng của bài toán (P). Điều ngƣợc lại
cũng đúng, có nghĩa là bài toán (P) có thể biểu diễn dƣới dạng (1.1) bằng
cách lấy
g( r, y ) r I K ( y ) và F( x ) ( f ( x ),G( x )) ,
trong đó I K ( y ) 0 , nếu y K và bằng nếu y K (xem [7]). Cho nên
hai cách tiếp cận là tƣơng đƣơng.
5
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
h' ( y,.) trùng với trên đồ thị của h ( y,.) .
Khi h' ( y,d ) tồn tại và là hữu hạn, ta kí hiệu h'' ( y ;d , ) và
h'' ( y ;d , ) là đạo hàm parabolic cấp hai trên và dƣới [3], tƣơng ứng của
h tức là
h'' ( y ;d , ) : liminf
t 0
1
h( y td t 2 ) - h( y ) - th' ( y,d )
2
1 2
t
2
6
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Df ( x ),D2 f ( x ) tƣơng ứng là đạo hàm cấp một và đạo hàm cấp hai
1
h( y td t 2 ) h( y ) th' ( y,d )
2
h ( y ;d , ) : lim sup
t 0
1 2
t
2
của hàm
Ta nói rằng h(.) là khả vi theo phƣơng cấp hai tại y theo phƣơng d,
y 0).
''
f ( x ) ; BY : y Y : y 1 là hình cầu đơn vị trong Y ;
y : ty : t R là không gian tuyến tính sinh bởi vec tơ y (một chiều nếu
nếu h'' ( y ;d , ) = h+'' ( y ;d , ) và hữu hạn với mọi Y . Trong trƣờng
hợp này, giá trị chung đó đƣợc ký hiệu h ( y ;d , ) . Khi h( y ) và
1.2. CÁC TẬP TIẾP TUYẾN CẤP MỘT VÀ CẤP HAI
''
h ( y,d ) hữu hạn, đạo hàm parabolic cấp hai dƣới đƣợc định nghĩa nhƣ sau
TK ( y ) : h Y : dist(y + th, K) = o(t), t 0.
1
h( y td t 2' ) h( y ) th ( y,d )
2
1 2
t 0 , '
t
2
h ( y ;d , ) : liminf
Chú
ý
rằng
nếu
h(.)
là
liên
tục
Lipschitz
gần
(từ không gian định chuẩn X vào họ các tập con của Y) theo nghĩa
y,
thì
''
hàm tuyến tính y* Y * tại y Y . Với ánh xạ tuyến tính liên tục
A* : Y * X *
lim sup x y Y : x n x 0 sao cho yn x n , yn y,
liminf x y Y : x n x 0 , yn x n , yn y.
Kí hiệu Y * là không gian đối ngẫu của Y và y* , y giá trị y* ( y ) của
ta kí hiệu
Painlevé - Kuratowski:
x x0
hạn, và liên tục, và do đó là liên tục Lipschitz tại y.
A: X Y
là ánh xạ liên hợp, tức là,
x x0
Theo định nghĩa của giới hạn tập hợp dƣới, ta có thể viết
*
*
*
Ky
.
t
TK y liminf
t 0
A y ,x y ,Ax , với mọi x X ,y Y . Với tập T Y kí hiệu (.,T ) là
*
(1.3)
Nhắc lại [2] các khái niệm giới hạn trên và dƣới của hàm đa trị : X 2Y
h ( y ;d , ) h ( y ;d , ) . Nói riêng, điều này đúng, nếu h(.) lồi, hữu
Giả sử K là tập con đóng của không gian Banach Y . Nón tiếp tuyến
cấp 1 của K tại điểm y K đƣợc định nghĩa nhƣ sau:
*
(1.4)
Ta biết rằng khi K là lồi thì cũng có
hàm tựa của T, tức là
( y* ,T ) : sup y* , y
TK ( y ) lim sup
.
t 0
yT
( 1.5)
Chú ý rằng nếu K là nón lồi và y K , thì TK ( y ) cl K y , trong
Ký hiệu dist .,T là hàm khoảng cách
đó y ký hiệu không gian tuyến tính sinh bởi vec tơ y và cl ký hiệu bao
dist y,T : inf y z .
zT
đóng theo tôpô chuẩn của Y .
7
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Ky
.
t
8
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
( x ) ( x ),
( 0 ) 0,
Tƣơng tự (1.4) và (1.5), ta xét biến phân cấp hai của tập K tại điểm
y K theo phƣơng d
TK2 ( y,d ) : liminf
t 0
và với dãy đơn điệu giảm đến không xk nào đó, hàm ( x ) là tuyến tính
K - y - td
,
1 2
t
2
(1.6)
(1.7)
Ta gọi T ( y,d ),O ( y,d ) tƣơng ứng là các tập tiếp tuyến cấp hai
trong và ngoài. Các tập tiếp tuyến này có thể viết dƣới dạng sau:
1
T ( y,d ) Y: dist (y+td+ t 2 , ) = o(t 2 ),t 0 ,
2
1 2
2
2
OK ( y,d ) : tn 0 : dist (y+tn d+ tn ,K) = o(tn ) .
2
2
K
Nhƣ vậy với điểm xk 0 , xét đƣờng thẳng đi qua điểm ( xk ,xk2 ) và
y x2 tại điểm xk 1 rõ ràng xk xk 1 0 , và có
xk 0 .
Đặt K : ( x, y ) R 2 : y ( x ) . Khi đó với phƣơng d : ( 1,0 ) ta có
TK2 ( 0,d ) x, y : y 4 ,
OK2 ( 0,d ) ( x, y ) : y 2 .
Từ định nghĩa trên ta thấy rằng TK2 ( y,d ) OK2 ( y,d ) , và các tập tiếp
d TK ( y ) . Cả hai tập
T ( y,d ),O ( y,d ) đóng. Nếu K lồi, thì tập T ( y,d ) lồi; Tập tiếp tuyến
2
K
2
K
và đƣờng thẳng đi qua các điểm
tiếp xúc với đƣờng cong y 2x2 . Đƣờng thẳng này giao với đƣờng cong
2
K
tuyến cấp hai này khác rỗng chỉ nếu
xk 1 ,xk ,( xk ) xk2
( xk ,( xk )) và xk 1 , xk 1 là tiếp xúc với đƣờng cong y 2x2 .
K y td
OK2 ( y,d ) : lim sup
.
t 0
1 2
t
2
2
K
trên mỗi đoạn
2
K
cấp hai ngoài OK2 ( y,d ) có thể không lồi.
Với mỗi R , '' ( 0;1, )=2
và +'' ( 0;1, )=4 và do đó (.) là
không khả vi theo phƣơng cấp hai tại điểm 0 .
Ta nói rằng tập K là khả vi theo phƣơng cấp hai tại y K theo
Ví dụ dƣới đây chứng minh rằng không giống nhƣ các nón tiếp tuyến
phƣơng d , nếu
cấp một, các tập tiếp tuyến cấp hai trong và ngoài có thể khác nhau.
Ví dụ 1.1
TK2 ( y,d ) OK2 ( y,d ) .
Mệnh đề 1.1
Ta xây dựng một hàm tuyến tính từng khúc lồi y ( x ),x R , dao
động giữa hai parabol y x2 và y 2x2 . Ta xây dựng ( x ) thoả mãn:
9
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Giả sử tập K được xác định như sau
K y Y : h( y ) 0 ,
10
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
trong đó h :Y R là hàm lồi chính thường. Giả sử h( y ) 0 ,
h y,d 0 , và giả sử rằng tồn tại y sao cho h( y ) 0 (điều kiện Slater).
1
Do đó, h( y tn d tn2n ) 0 với n đủ lớn.
2
Vì vậy,
Khi đó,
OK2 ( y,d ) : h ( y;d , ) 0 .
1
y tn d tn2n K .
2
(1.8)
Từ đó suy ra OK2 ( y,d ) .
Nếu giả thiết thêm h(.) là liên tục tại y, thì
TK2 ( y,d ) : h+'' ( y;d , ) 0 .
Bây giờ giả sử h ( y;d , )=0 , và do đó tồn tại tn 0 và n
(1.9)
sao cho
Chứng minh
1
h( y tn d tn2n ) o( tn2 ) .
2
Ta chỉ chứng minh (1.8) đúng, còn chứng minh (1.9) là tƣơng tự.
Xét OK2 ( y,d ) và chọn dãy tn 0 ,n sao cho
1
y tn d tn2 n K , và do đó,
2
Lấy 0,' Y . Đặt ' : ' ( y y ) . Do tính lồi của h , với
1 2
t ' 0 đủ nhỏ ta có 1 t' 0 và
2
1
h( y tn d tn2n ) 0 .
2
1 2
1 2
1 2
h( y t' d t' ' ) ( 1 t' ) ( t ' ,' ) t ' h y ,
2
2
2
(1.10)
trong đó
Khi đó,
1
h( y tn d tn2n )
2
h ( y ;d , ) liminf
0.
n
1 2
tn
2
1
2
( t' ,' ) : h( y t' ( 1 t' ) 1 d
Ngƣợc lại, giả sử h ( y ;d , )<0 . Khi đó, với tn 0 và n
nào đó, ta có
1
1
h( y tn d tn2n ) tn2 h ( y ;d , ) + o(tn2 ) .
2
2
11
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
2
1 '2
1 2
t ( 1 t' ) 1 .)
2
2
Đặt:
1 2
1 2
2tn
t' ( 1 t' )1 t , tức là t'n
, và ( 1 tn' )n' n .
2
n
n
2
2 n
( 1 1 2 tn )
Khi đó,
1
2
( tn' ,n' ) h( y tn d tn2n ) ( tn2 ) .
12
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Bởi vì tn' 0 ,n' ( y y ) và h( y ) 0 , từ (1.10) ta suy ra
với mọi 0 ,
Từ mệnh đề trên ta suy ra TTK ( y ) ( d ) là nón lùi xa của TK2 ( y,d ) và
OK2 y,d khi mà các tập hợp này khác rỗng.
h ( y;d , ) h( y ) 0 .
Hơn nữa,
Vì vậy, OK2 ( y,d ) . Vì OK2 ( y,d ) đóng, cho 0 ta nhận đƣợc
nếu
OK2 ( y,d ) TTK ( y )( d )
và khi
0 TK2 ( y,d ) thì ba tập này trùng nhau:
OK2 ( y,d ) . Do đó (1.8) đƣợc chứng minh.
TK2 ( y,d ) OK2 ( y,d ) TTK ( y )( d ) .
Nếu h(.) là lồi và liên tục tại y , thì các đạo hàm cấp hai
0 OK2 ( y,d ) , thì
Chú ý rằng
h ( y,d ,.),h ( y,d ,.) là nhƣ nhau. Khi đó, từ mệnh đề trên, với điều kiện
''
Slater, ta suy ra K là khả vi theo phƣơng cấp hai tại điểm y theo phƣơng
d khi và chỉ khi các tập mức : h'' ( y ;d , ) 0 và : h'' ( y ;d , ) 0
trùng nhau. Đặc biệt, K là khả vi theo phƣơng cấp hai nếu h(.) là khả vi
TTK ( y ) ( d ) cl TK ( y ) d ,
trong đó d TK y ; TTK ( y )( d ) là rỗng, nếu d TK y .
Theo công thức (1.14) và (1.15) dƣới đây cho ta một quy tắc để tính
các xấp xỉ tiếp tuyến cấp hai của tập chấp nhận đƣợc : G1( K ) của
theo hƣớng cấp hai.
( P ) dƣới ngôn ngữ xấp xỉ tiếp tuyến cấp hai của K . Công thức này đúng
Mệnh đề 1.2
với điều kiện chính quy Robinson:
Với mọi y K ,d TK ( y ) , ta có
0 int G(x0 ) DG( x0 )X K .
TK2 ( y,d ) TTK ( y )( d ) TK2 ( y,d ) TT
K
( d ),
(y)
OK2 ( y,d ) TTK ( y )( d ) OK2 ( y,d ) TTK ( y )( d ) .
(1.11)
(1.12)
Nhắc lại [5] rằng tập A X lồi khác đƣợc gọi là lùi xa theo
phƣơng d 0 , nếu A d A 0 . Tập các vectơ d X thoả mãn
A d A 0
(1.13)
Mệnh đề 1.3 ([3])
Lấy x0 : G 1( K ) và giả sử điều kiện chính quy Robinson
(1.13) đúng. Khi đó, với mọi h X ,
2
T2 ( x0 ,h ) DG( x0 )1 TK2 ( G( x0 ),DG( 0x )h ) D
G( 0x )( h,h ),
(1.14)
O2 ( x0 ,h ) DG( x0 )1 OK2 ( G( x0 ),DG( 0x )h ) D2 G( 0x )( h,h ).
(1.15)
và vectơ d = 0 đƣợc gọi là nón lùi xa của A.
13
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
14
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
1.3. ĐIỀU KIỆN CHÍNH QUY CẤP HAI VÀ ĐIỀU KIỆN TỐI ƢU CẤP HAI
Khi tập K là một nón lồi và y K , nón pháp tuyến N K ( y ) có dạng:
Phần này trình bày các điều kiện tối ƣu cấp hai cần và đủ cho bài
toán ( P ) . Với bài toán ( P ) , ta định nghĩa hàm Lagrange nhƣ sau:
trong đó
L( x, ) : f ( x ) ,G( x ) , Y * .
K : y* Y * : y* , y 0,y K
Hàm Lagrangian suy rộng đƣợc định nghĩa nhƣ sau:
là nón cực của nón K (đối ngẫu âm). Trong trƣờng hợp đó, điều kiện
L* ( x, , ) : f ( x ) ,G( x ) , ( , ) R Y * .
N K ( G( x0 )) trở thành
Giả sử x0 là nghiệm tối ƣu địa phƣơng của bài toán ( P ) . Khi đó, các
K và ,G( x0 ) 0 .
điều kiện tối ƣu kiểu cấp một Fritz John có dạng: tồn tại
Nhắc lại rằng: nón
( , ) R Y * ,( , ) (0,0 ) sao cho
Dx L* ( x0 , , ) 0, 0, N K ( G( x0 )).
(1.16)
Ở đây N K ( y ) : y* Y * : y* ,z y 0 , với mọi z K là nón pháp
tuyến của K tại y . Kí hiệu * ( x0 ) là tập hợp các nhân tử Lagrang suy
rộng ( , ) ( 0,0 ) thỏa mãn điều kiện (1.16). Chú ý rằng với không gian
Banach Y tập hợp * ( x0 ) có thể rỗng. Điều kiện tối ƣu Fritz John ở trên
là điều kiện cần cho nghiệm tối ƣu địa phƣơng, tức là * ( x0 ) . Ta chú
ý hai trƣờng hợp quan trọng. Cụ thể là khi Y là không gian hữu hạn chiều,
hoặc khi K có phần trong khác rỗng.
Nếu nhân tử trong (1.16) khác không thì ta có thể lấy 1 , và vì
vậy điều kiện cần cấp 1 trở thành
Dx L( x0 , ) 0, N K ( G( x0 )) .
(1.17)
Với điều kiện chính quy Robinson (1.13), tập hợp ( x0 ) các nhân tử
Lagrange thỏa mãn (1.17) là khác rỗng và bị chặn (xem [8]).
15
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
N K ( y ) y* K : y* , y 0 ,
C( x0 ): h X : DG( x0 )h TK ( G( x0 )),Df ( x0 )h 0
(1.18)
đƣợc gọi là nón tới hạn (critical cone) của bài toán ( P ) tại điểm x0 . Nón
này biểu diễn các phƣơng tuyến tính hóa cấp một của ( P ) . Chú ý rằng khi
tập ( x0 ) các nhân tử Lagrange khác rỗng thì Df ( x0 )h 0 với mọi h X
thỏa mãn DG( x0 )h TK ( G( x0 )) . Trong trƣờng hợp đó bất đẳng thức
Df ( x0 )h 0 , trong định nghĩa của nón tới hạn có thể thay bởi đẳng thức
Df ( x0 )h 0 . Điều đó là tƣơng đƣơng với ,DG( x0 )h 0 với mọi
( x0 ) .
Bây giờ ta có thể phát biểu điều kiện cần tối ƣu cấp hai dựa trên sự
phân tích đƣờng cong chấp nhận đƣợc parabol có dạng
1
x(t) = x0 th t 2 + o(t 2 ) ,
2
(1.19)
trong đó t 0 . Điều kiện cần này kết hợp với điều kiện đủ trong định lý
1.2 dẫn tới khái niệm chính quy cấp hai.
16
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Định lý 1.1
Dãy xk là chấp nhận đƣợc của bài toán ( P ) và hội tụ đến cực tiểu địa
Giả sử x0 là nghiệm tối ưu địa phương của bài toán ( P ) . Giả sử
rằng điều kiện chính quy Robinson (1.13) đúng. Khi đó, với mọi h C( x0 )
và tập lồi bất kỳ T ( h ) OK2 ( G( x0 ),DG( x0 )h ) ,
phƣơng x0 . Do đó, f ( xk ) f ( x0 ) với mọi k đủ lớn. Sử dụng khai triển
Taylor cấp hai ta có
1
f ( x0 ) f ( xk ) f ( x0 ) tk Df ( x0 )h t k2 Df ( x0 )+D 2 f ( x0 )( h,h ) ( t k2 ) .
2
Sup Dxx2 L( x0 , )( h,h ) ( , T (h)) 0 .
Bởi vì Df ( x0 )h 0 , với bất kỳ h C( x0 ) , ta nhận đƣợc
( x0 )
Df ( x0 )+D2 f ( x0 )( h,h ) 0 .
(1.20)
Chứng minh
Nhƣ vậy, giá trị tối ƣu của bài toán (1.21) không âm. Bây giờ ta xét
Chú ý rằng nếu T (h)= thì (., T (h)) = và (1.20) đúng một
tập T(h) := cl {T (h) TK ( G( x0 )) . Tập này là bao đóng tôpô của tổng
hai tập lồi và vì thế là lồi. Hơn nữa, từ bao hàm thức (1.12) và sự kiện:
cách tầm thƣờng.
các tập tiếp tuyến ngoài cấp hai đóng, ta suy ra
Ta giả sử T (h) và do đó tập OK2 ( G( x0 ),DG( x0 )h ) khác rỗng.
T( h ) OK2 ( G( x0 ),DG( x0 )h ) .
Ta khẳng định rằng giá trị tối ƣu của bài toán:
Rõ ràng nếu ta thay đổi các tập tiếp tuyến cấp hai ngoài trong (1.21)
Min Df ( x0 )+D2 f ( x0 )( h,h ) ,
(1.21)
X
DG( x 0 )+D2G( x0 )( h,h ) OK2 ( G( x0 ),DG( x0 )h )
bằng tập con T( h ) của nó thì giá trị tối ƣu của bài toán tối ƣu sẽ lớn hơn
hay bằng giá trị tối ƣu của (1.21). Do đó, giá trị tối ƣu của bài toán:
Min Df ( x0 )+D2 f ( x0 )( h,h ) ,
(1.22)
X
là không âm.
DG( x0 )+D2G( x0 )( h,h ) T( h )
Thật vậy, nếu là điểm chấp nhận đƣợc của bài toán này, sử dụng
mệnh đề 1.3 ta nhận đƣợc 02 ( x0 ,h ) , trong đó: : G1( K ) . Vì thế ta
là không âm.
1
có thể tìm đƣợc dãy tk 0 sao cho xk : x0 tk h tk2 + o(t 2 ) .
2
Bài toán tối ƣu (1.22) lồi và đối ngẫu (tham số) của nó là:
Max Dxx2 L( x0 , )( h,h ) ( ,T( h ))
(x0 )
(1.23)
Thật vậy, hàm Lagrange của (1.22) là
17
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
18
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
L( , )=Dx L( x0 , )+Dxx2 L( x0 , )( h,h ) .
Bởi vì với bất kỳ z T( h ) , ta có z TK ( G( x0 )) T( h ), cho nên
( ,T( h )) với mỗi TK ( G( x0 )) N K ( G( x0 )) .
Vì thế miền hữu hiệu của đối ngẫu tham số của (1.22) là nằm trong
TK2 ( G( x0 )),DG( x0 )h . Nói chung, tập T
(h) có thể lấy lớn hơn
T ( G( x0 ),DG( x0 )d ) và do đó định lý 1.1 là mạnh hơn.
2
K
(ii) Chú ý rằng trong điều kiện cần tối ƣu cấp hai, giá trị tối ƣu của bài
toán (1.21) là không âm.
( x0 ) . Khi đó ta suy ra tính đối ngẫu. Hơn nữa, điều kiện chính quy
(iii) Nếu 0 OK2 ( G( x0 ),DG( x0 )h ) với mọi h C( x0 ) , nói riêng nếu tập K
Robinson (1.13) kéo theo
là một đa diện, thì
OK2 ( G( x0 ),DG( x0 )h ) TTK ( G( x0 )) ( DG( x0 )h ) ,
DG( x0 )X TK ( G( x0 )) Y .
Bởi vì với bất kỳ z T( h ) thì z TK ( G( x0 )) T( h ) , ta có
và ( , T (h)) = 0 với mỗi ( x0 ) , và
T (h) : OK2 ( G( x0 ),DG( x0 )h ) .
z DG( x0 )X T( h ) Y .
Do đó (1.22) có một nghiệm chấp nhận đƣợc và điều kiện chính quy
(iv) Giả sử là tập hợp của các dãy tn các số dƣơng hội tụ tới 0. Với
Robinson cho bài toán (1.22) cũng đúng. Do đó, không có lỗ hổng đối
bất kỳ s=tn , y K , và d TK ( y ) ta có thể đƣa vào tập tiếp tuyến
ngẫu giữa (1.22) và đối ngẫu (1.23) (xem [3]).
cấp hai dƣới đây:
Ta nhận đƣợc giá trị tối ƣu của (1.23) không âm. Bởi vì T
1
TK2,s ( y,d ) : :dist(y+tn d t 2 ,K)= (t 2 ) .
2
(h) T( h ) , ta có ( , T (h)) ( ,T( h )) . Vì vậy ta suy ra (1.20) và định
lý đƣợc chứng minh.
Với bất kỳ s , tập TK2,s (y,d) là lồi và đóng. Rõ ràng giao của
TK2,s ( y,d ) theo tất cả s là TK2 (y,d) , và hợp của TK2,s ( y,d ) lấy theo
Nhận xét
(i)
Nhƣ chúng ta đã đề cập ở phần trƣớc, tập tiếp tuyến cấp hai ngoài
kỳ s .
OK2 ( G( x0 )),DG( x0 )h )
có thể không lồi. Tuy nhiên khi nó lồi ta có thể sử dụng tập này ở trong
điều kiện cấp hai (1.20), và ta nhận đƣợc một điều kiện cần tốt hơn. Trong
bất kỳ trƣờng hợp nào có thể lấy T (h) là tập tiếp tuyến cấp hai trong
19
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
s là OK2 ( y,d ) . Một cách chọn T (h) là TK2,s ( G( x0 ),DG( x0 )h ) với bất
(v)
Ta có thể phát biểu điều kiện cần cấp hai (1.20) dƣới dạng
inf sup Dxx2 L( x0 , )( h,h ) ( ,T( h )) 0 ,
T O(h) ( x0 )
(h)
(1.24)
20
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
trong
đó
O(h)
kí
hiệu
tập
tất
cả
các
tập
con
lồi
của
OK2 ( G( x0 ), DG( x0 )h ) . Nói riêng, nếu ta lấy tất cả các tập con một phần
tử của OK2 ( G( x0 ), DG( x0 )h ) thì điều kiện (1.24) kéo theo điều kiện cần
dƣới đây
thế điều kiện cần cấp hai (1.20) trở thành bất đẳng thức chặt với mọi
h C( x0 ) khác không.
Điều kiện cần cấp hai (1.20) đƣợc dựa trên đánh giá ƣớc lƣợng trên
của hàm mục tiêu dọc theo đƣờng cong parabol chấp nhận đƣợc có dạng
inf
sup D L( x0 , )( h,h ) , y 0 .
yOK2 ( G( x0 ),DG( x0 )h ) ( x0 )
2
xx
(1.25)
Nếu ( x0 ) là tập một phần tử, chẳng hạn ( x0 ) 0 , thì điều kiện
(1.25) trở thành
Dxx2 L( x0 ,0 )( h,h ) ( 0 ,OK2 ( G( x0 ),DG( x0 )h )) 0 .
Giả sử S là tập các điểm chấp nhận được của bài toán ( P )
thoả mãn f ( x ) f0 với mỗi x S . Ta nói rằng điều kiện tăng trưởng cấp
hai đúng tại S nếu tồn tại hằng số c 0 và lân cận N của S sao cho
2
với mọi x N .
nói rằng tập đóng AK,M ( y,d ) Y là xấp xỉ trên cấp 2 của K tại y theo
1
phương d và theo M , nếu với bất kỳ dãy yk K có dạng yk : y tk d tk2 rk ,
2
trong đó tk 0 và rk M k ak với
k X
ak
là dãy hội tụ trong Y và
thỏa mãn tkk 0 , điều kiện dưới đây đúng:
lim dist( rk ,AK ,M ( y,d )) 0 .
(1.27) sẽ có dạng
f ( x ) f ( x0 ) c x x0
Định nghĩa 1.2
k
(1.27)
Nói riêng, nếu S x0 là tập một phần tử, điều kiện tăng trƣởng cấp hai
2
cấp 2 ta đƣa vào khái niệm sau.
Giả sử y K ,d TK ( y ) và xét ánh xạ tuyến tính liên tục M : X Y . Ta
(1.26)
Định nghĩa 1.1
f ( x ) f0 c dist(x,S) với mọi x N .
(1.19). Để đánh giá ƣớc lƣợng dƣới, và do đó để nhận đƣợc điều kiện đủ
(1.28)
Điều này rõ ràng kéo theo x0 là một nghiệm tối ƣu địa phƣơng của
(1.29)
Nếu điều kiện trên đúng với bất kỳ X và M , tức là (1.29) thỏa mãn
với bất kỳ dãy
1
y tk d tk2 rk K
2
sao cho tk rk 0 , thì ta bỏ qua M và nói rằng tập AK ( y,d ) là tập xấp xỉ
trên cấp hai của K tại điểm y theo phương d .
( P ) . Hơn nữa, với giả thiết điều kiện Ronbinson (1.13) đúng, khi đó với
bất kỳ h C( x0 ) giá trị tối ƣu của (1.21) là lớn hơn hay bằng 2c h . Vì
2
21
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Định nghĩa trên nhằm mục đích cho ta tập đủ lớn AK ( y,d ) sao cho
nếu y td ( t ) là đƣờng cong trong K mà tiếp xúc với d với
22
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
( t ) ( t ) , thì số dƣ cấp hai r( t ) :
( t )
1 2
t
2
f ( xk ) f ( x0 ) o( tk2 ) ,
tiến đến AK ( y,d ) khi t 0 .
trong đó tk : xk x0 . Bởi vì không gian X là hữu hạn chiều, các tập con
Chú ý rằng số dƣ r(t) và dãy rk r( tk ) có thể không bị chặn.
đóng bị chặn trong X là compact. Vì vậy ta có thể giả sử rằng
Xấp xỉ trên cấp hai AK ( y,d ) không duy nhất. Rõ ràng, nếu
AK ( y,d ) B , thì B cũng là xấp xỉ trên cấp hai. Nếu y K ,d TK ( y ) và
y d K thì d+ TK ( y ) . Vì vậy, TTK ( y )( d ) . Do đó, TTK ( y )( d ) là
tập xấp xỉ trên cấp hai. Từ định nghĩa suy ra tập tiếp tuyến cấp hai ngoài
hk :
xk x0
hội tụ đến một vectơ h X .
tk
Rõ ràng h 1, và vì vậy h 0 . Sử dụng khai triển Taylor cấp một,
do G( xk ) K , ta nhận đƣợc
DG(x0 )h TK ( G( x0 )) .
OK2 ( y,d ) nằm trong các tập xấp xỉ trên cấp hai K ( y,d ) .
Từ (1.31) ta có
Định lý 1.2
Df ( x0 )h 0 .
Giả sử x0 là điểm chấp nhận được của bài toán ( P ) thỏa mãn điều
kiện tối ưu cấp một ( kiểu Fritz John) (1.16). Giả sử mỗi h C( x0 ) tương
ứng với một tập xấp xỉ trên cấp hai trên ( h ) : K ,M ( y0 ,d ) của tập K
tại điểm y0 : G( x0 ) theo phương d : DG( x0 )h và theo ánh xạ tuyến tính
M : DG( x0 ) . Giả sử rằng điều kiện cấp hai dưới đây thỏa mãn:
sup
( , )* ( x0 )
(1.31)
D
L ( x0 , , )( h,h ) ( , ( h )) 0
2 *
xx
Vì vậy h C( x0 ) .
Khai triển Taylor cấp hai của G( xk ) tại x0 , ta có
1
G( xk ) y0 tk d tk2 ( DG( x0 )k D 2G( x0 )( h,h ) o( t k2 ) ,
2
(1.30)
với mọi h C( x0 )\ 0 . Khi đó, điều kiện tăng trưởng cấp hai (1.28) đúng
tại x0 , và vì vậy x0 là nghiệm tối ưu địa phương chặt của ( P ) .
Chứng minh
2
trong đó y0 : G( x0 ),d : DG( x0 )h và k : 2tk xk x0 tk h .
Chú ý rằng xk x0 tk h o( tk ) , và vì thế tkk 0 . Từ định nghĩa
xấp xỉ trên cấp hai ta suy ra
DG(x0 )k D2G( x0 )( h,h ) ( h ) o(1)BY .
Ta chứng minh phản chứng. Giả sử rằng điều kiện tăng trƣởng cấp
hai là không đúng tại x0 . Khi đó tồn tại dãy điểm chấp nhận đƣợc
xk ,xk x0 , hội tụ tới x0 và sao cho
23
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
(1.32)
Ta cũng có
1
f(xk ) f ( x0 ) tk Df ( x0 )h tk2 ( Df ( x0 )k D 2 f ( x0 )( h,h )) o( t k2 ) .
2
24
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
sup Dxx2 L( x0 , )( h,h ) ( ,A( h ) 0 , với mọi h C( x0 )\ 0
Vì vậy, sử dụng (1.31) và (1.32) ta tìm đƣợc dãy k 0 sao cho
2tk1 Df ( x0 )h ( Df ( x0 )k D 2 f ( x0 )( h,h ) k ,
2
DG( x0 )k D G( x0 )( h,h ) ( h ) k BY .
( x0 )
Nhƣ đã nói ở trên, tập (h):=TTK ( G( x0 ))( DG( x0 )h ) luôn là tập xấp xỉ
(1.33)
trên cấp hai. Hơn nữa,
Từ (1.30) suy ra tồn tại ( , ) * x0 sao cho
0,
( , (h))
D L ( x0 , , )( h,h ) ( ,( h )) ,
2 *
xx
(1.35)
+ ,
(1.34)
với 0 nào đó. Từ điều kiện thứ hai trong (1.33) ta suy ra
TK ( G( x0 )), ,DG( x0 )h 0 ,
trong trƣờng hợp ngƣợc lại.
Vì thế với cách chọn tập xấp xỉ trên cấp hai đó, điều kiện đủ cấp hai
(1.30) có dạng
,DG( x0 )k D 2G( x0 )( h,h ) , h k Y
sup
( , ( h ) k k .
( , )* ( x0 )
Dxx2 L* ( x0 , , )( h,h ) 0 , với mọi h C( x0 )\ 0 .
(1.36)
Ta nhận đƣợc kết quả sau đây
Ta cũng có 0 , và nếu 0 thì
Hệ quả 1.2.1
Df ( x0 )h 0 .
Trong trƣờng hợp bất kỳ Df ( x0 )h 0 , và vì vậy từ (1.33) và (1.34)
ta nhận đƣợc
0 ( 2tk1 Df ( x0 )h Df ( x0 )k D 2 f ( x0 )( h,h ) k )
Giả sử x0 là điểm chấp nhận được của bài toán ( P ) thỏa mãn điều
kiện tối ưu cấp một (kiểu Fritz John) (1.16). Giả sử điều kiện đủ cấp hai
(1.36) thỏa mãn. Khi đó điều kiện tăng trưởng (1.28) đúng tại x0 .
Nếu tập các nhân tử Lagrange ( x0 ) là khác rỗng, thì có thể thay thế
,DG( x0 )k D 2G( x0 )( h,h ) ( ,A( h )) k
Dxx2 L* ( x0 , , )( h,h ) ( , ( h )) k ( )
k ( ).
( x0 ) trong (1.36) bằng ( x0 ) .
*
Định nghĩa 1.3
Bởi vì k 0 cho nên dẫn tới một mâu thuẫn, và định lý đƣợc chứng minh.
Chú ý tính hữu hạn chiều của X đƣợc sử dụng để dẫn điều kiện đủ
cấp hai còn điều kiện cần cấp hai không đòi hỏi giả thiết này.
Nếu tập ( x0 ) của các nhân tử Lagrange khác rỗng thì điều kiện đủ
(1.30) là tƣơng đƣơng với:
Ta nói tập K là chính quy cấp hai ngoài tại điểm y K theo phương
d TK ( y ) và theo ánh xạ tuyến tính M : X Y nếu với bất kỳ dãy
1
yn K có dạng yn : y tn d tn2 rn , trong đó tn 0,rn M n an , với
2
an
là dãy hội tụ trong Y và n là dãy trong X thỏa mãn tnn 0 ,
điều kiện dưới đây đúng
25
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
26
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
lim dist( rn ,OK2 ( y,d )) 0 .
(1.37)
n
Nếu K là chính quy cấp hai ngoài tại y K theo mọi phương
d TK ( y ) và theo bất kỳ X và M thì ta nói rằng K là chính quy cấp hai
ngoài tại y . Nếu thêm vào OK2 ( y,d ) TK2 ( y,d ) với mọi d TK ( y ), ta nói
Suy luận (1.35) (1.28) suy từ định lý 1.2. Điều ngƣợc lại là hệ
quả của định lý 1.1 và phần nhận xét về (1.28).
Nhắc lại rằng các tập tiếp tuyến cấp hai trong luôn luôn lồi, và do đó
trong trƣờng hợp OK2 ( G( x0 ),DG( x0 )h ) TK2( G( x0 ),DG( x0 )h ) , tập tiếp
tuyến cấp hai ngoài cũng lồi.
rằng K là chính quy cấp hai tại y .
Chính quy cấp hai ngoài có nghĩa là tập tiếp tuyến cấp hai ngoài
OK2 ( y,d ) cho ta một xấp xỉ cấp hai trên của K tại y theo phƣơng d . Nếu
các tập tiếp tuyến cấp hai trong và ngoài trùng nhau, ta gọi đơn giản là
chính quy cấp hai. Tính chính quy cấp hai có nghĩa là nếu y td+ (t) là
đƣờng cong trong K tiếp xúc với d với ( t ) o( t ) , thì r( t ) :
( t )
1 2
t
2
là
Sau đây ta sẽ thấy rằng nghịch ảnh của các ánh xạ khả vi liên tục hai
lần thỏa mãn điều kiện chính quy Robinson là chính quy cấp 2.
Mệnh đề 1.4
Giả sử K là tập con lồi đóng của Y và G : X Y là ánh xạ khả vi
liên tục hai lần. Nếu điều kiện chính quy Robinson (1.13) đúng và K là
chính quy cấp hai ngoài tại G( x0 ) theo phương DG( x0 )h và ánh xạ
tuyến tính M : DG( x0 ) , thì tập G 1( K ) là chính quy cấp hai ngoài tại
gần tùy ý với TK2 ( y,d ) khi t 0 .
x0 theo phương h .
Định lý 1.3
Giả sử x0 là điểm chấp nhận được của ( P ) thỏa mãn điều kiện cần
cấp một (1.17). Giả sử điều kiện chính quy Robinson (1.13) đúng và với
mọi h C( x0 ) thì tập K là chính quy cấp hai ngoài tại G( x0 ) theo
phương DG( x0 )h và theo M : DG( x0 ) , và tập tiếp tuyến cấp hai ngoài
O G( x0 ),DG( x0 )h là lồi. Khi đó, điều kiện tăng trưởng cấp hai (1.28)
2
K
đúng khi và chỉ khi điều kiện đủ cấp hai (1.35) thỏa mãn với
2
K
A(h)=O ( G( x0 ),DG( x0 )h ) .
Chứng minh
1
Giả sử x k : x0 tk h tk2rk G 1 ( K ) sao cho tk 0,tk rk 0 . Theo
2
mệnh đề 1.3 và định lý ổn định Robinson - Ursescu, tồn tại hằng số L sao
cho mọi k đủ lớn ta có
dist(rk ,OG2 1 ( K )( x0 ,h ))
dist rk ,DG( x0 )1 OK2 ( G( x0 ),DG( x0 )h ) D 2G( x0 )( h,h )
Ldist(DG(x0 )rk D 2G( x0 )( h,h ),OK2 ( G( x0 ),DG( x0 )h )).
Chứng minh
Bây giờ khai triển cấp hai G( xk ) ta nhận đƣợc
27
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
28
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
1
G( xk ) G( x0 ) tk DG( x0 )h tk2 ( DG( x0 )rk D 2G( x0 )( h,h ) o( t k2 ) .
2
Bởi vì G( xk ) K , tính chính quy cấp hai ngoài của K kéo theo
u1 ,...,un BY , lấy y y un , ta có ki : y ui y 2 BY Ki với mọi
i 1,...,n 1 . Vì thế nếu đặt kn : y K n , ta có ui y ki y Ki ,i 1,...,n
và do đó BY G(Y ) K . Điều đó chứng tỏ rằng điều kiện chính quy
n
dist(DG(x0 )rk D2G( x0 )( h,h ),OK2 ( G( x0 ),DG( x0 )h )) 0 .
Robinson thoả mãn.
Vì thế dist(rk ,OG2 1 ( K ) x0 ,h ) 0 . Do đó, G -1 (K) chính quy cấp 2 ngoài tại
x 0 theo phƣơng h.
Trở lại trƣờng hợp các tập đƣợc xác định bởi ràng buộc bất đẳng
thức ta sẽ thấy rằng khi các hàm ràng buộc là lồi, ta có thể giảm nhẹ đƣợc
giả thiết khả vi.
Mệnh đề 1.5
Xét tập
F : x X : gi ( x ) 0,i 1,..., p;h j ( x ) 0, j 1,...,q
Giả sử K : y : h( y ) 0 , trong đó h(.) là hàm lồi liên tục tại điểm
đƣợc xác định bởi một số hữu hạn ràng buộc. Giả sử hàm g i và h j là khả
y0 . Giả sử điều kiện Slate đúng và h( y0 ) 0 . Khi đó, K là chính quy cấp
vi liên tục hai lần. Từ mệnh đề 1.4 và sự kiện: các tập đa diện là chính
hai ngoài tại y0 khi và chỉ khi với bất kỳ d TK ( y0 ) thỏa mãn h' ( y0 ,d ) 0 và
quy cấp hai, ta suy ra tập F là chính quy cấp hai tại mọi điểm x0 F thỏa
bất kỳ đường cong y( t ) K
mãn điều kiện chính quy Mangasarian-Fromovitz.
1
có dạng y( t ) y0 td+ t 2 r( t ),t 0
2
với
tr( t ) 0 khi t 0 , thì bất đẳng thức sau đúng
Hệ quả 1.4.1
limsup h'' ( y0 ;d ,r( t )) 0 .
Giả sử K1 ,...,Kn là các tập lồi đóng chính quy cấp hai tại điểm
y0 K1 ... Kn theo phương d TK1 ( y0 ) ... TKn ( y0 ) . Nếu tồn tại một
điểm trong K n mà thuộc phần trong của K i, i 1,...,n 1, thì tương giao
K1 ... Kn chính quy cấp hai tại y0 theo phương d .
t 0
(1.38)
Chứng minh
Vì h là lồi và liên tục tại y0 , nên h là khả vi theo phƣơng tại y0 . Xét
1
phƣơng d TK ( y0 ) và dãy yk : y tk d tk2 rk K với tk 0 và tk rk 0 .
2
Chứng minh
Ta áp dụng mệnh đề 1.4 cho hàm G : Y Y n đƣợc cho bởi
Do d TK ( y0 ) ta suy ra h' ( y0 ,d ) 0 .
G( y ) ( y,...,y ),K K1 ... K n . Ta có K là chính quy cấp hai tại ( y0 ,..., y0 )
Bởi vì h' ( y0 ,d ) 0 kéo theo OK2 ( y0 ,d ) Y , cho nên ta chỉ cần xét
theo phƣơng ( d ,...,d ) . Để kiểm tra điều kiện chính quy Robinson, ta lấy
trƣờng hợp h' ( y0 ,d ) 0 . Do điều kiện Slater, tồn tại điểm y Y sao cho
y Y , 0
sao
cho
y Kn
và
y 2 BY K1 ... K n1 .
Nếu
29
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
h( y ) 0 . Bởi h(.) lồi, ta có h( y0 t( y y0 )) 0 , với mỗi t ( 0;1 ) . Do
30
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
1
y0 d 2 rk o 2 K .
2
đó, điểm y thoả mãn h( y ) 0 có thể chọn gần y0 tùy ý. Vì thế ta có thể
giả sử h(.) là liên tục tại y .
Do đó,
Giả sử (1.38) đúng. Với 0 , đặt : rk ( y y0 ) . Do tính lồi,
1
1
y0 d 2 rk K k 2 BY .
2
2
với mọi t 0 đủ nhỏ, ta có
1
1
1
1
1
h y0 td+ t 2 1 t 2 h y0 td+ t 2 rk t 2 h y td+ t 2 rk .
2
2
2
2
2
Bởi vì h y0 0 và h' y0 ,d 0 , chia cho
1 2
t và cho t 0 , ta rút ra
2
h'' y0 ;d , h'' y0 ,d ,rk h y .
Do (1.38) ta suy ra h'' y0 ;d ,rk y y0
Khi đó, với mọi 0 và : rk y y0 ta có
1
1
1
1
1
y0 d 2 1 2 y0 d 2 rk 2 y d 2 rk
2
2
2
2
2
1
1 2
1
1
2
2
2
1 K k BY y d rk
2
2
2
2
1
1
1
1
1 2 K 2 y d 2 rk 1 2 k BY .
2
2
2
2
1
Bởi vì y 2 k 1 BY K ta suy ra y0 d 2k K .
2
0 , với mọi k đủ lớn.
Mệnh đề 1.1 kéo theo rk y y0 OK2 y0 ,d , và do đó
Theo mệnh đề 1.1, h'' y0 ,d , 0 . Bởi vì h là liên tục tại y0 , cho
lim sup dist rk ,OK2 y0 ,d y y0 .
nên nó là liên tục Lipschitz địa phƣơng.
k
Vì là nhỏ tùy ý, nên K là chính quy cấp hai.
Do đó h'' y0 ,d ,. là liên tục Lipschitz toàn cục với cùng một hằng số
Ngƣợc lại, giả sử K là chính quy cấp hai. Giả sử tk 0 là dãy mà
chẳng hạn là L, và
giới hạn trên (1.38) là một giới hạn. Đặt rk : r tk ,
h'' y0 ,d ,rk L rk L y y0 .
k : dist rk ,OK2 y0 ,d .
1
k
Vì vậy, lim sup h'' y0 ,d ,r( t ) lim h'' 0y ,d ,rk L y 0y .
t 0
Ta có k 0 . Chọn r k OK2 ( y0 ,d ) sao cho rk rk k . Bởi vì k 0
không mất tính tổng quát ta giả sử rằng với mọi
k
k
Bởi vì nhỏ tùy ý cho nên ta suy ra kết luận.
ta có
y 2 k BY K . Chọn dãy 0 sao cho
1
31
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
32
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
x int y y x int .
Để nhận đƣợc quy tắc nhân tử Lagrange, ta cần dạng không thuần
nhất của định lý luân phiên Motzkin (xem [6]) sau.
Bổ đề 2.1 (Định lý Motzkin không thuần nhất)
Giả sử a j ,bi ,ci n và j ,i , i với j J ,i I , và i I 0 (các
tập chỉ số hữu hạn). Khi đó, hệ sau ( x
Chƣơng 2
TỐI ƢU ĐA MỤC TIÊU
địa phƣơng của bài toán tối ƣu đa mục tiêu trên cơ sở phát triển định lý
và Guignard. Các kết quả chƣơng này là của G.Bigi và M.Castellani [4].
Trong chƣơng này, ta đƣa vào một số kí hiệu và định nghĩa mà ta sẽ
(2.2)
Hơn nữa, nếu các hàng của (2.1) là độc lập tuyến tính thì tất cả các
là không gian ơclit l-chiều;
2.1. KIẾN THỨC CHUẨN BỊ
: x
ja j
ibi
i ci 0 ,
jJ
iI
iI 0
i i
i i 0 ,
i j
jJ
iI
iI 0
0 j 0 ,
jJ
j 0, j J 0 ,i 0,i I .
Tucker đƣợc dẫn khi đƣa vào các điều kiện chính quy cấp 2 kiểu Abadie
(2.1)
không tương thích khi và chỉ khi hệ sau (các ẩn j ,i , i ) tương thích
luân phiên Motzkin không thuần nhất. Các điều kiện cấp 2 kiểu Kuhn-
sử dụng. Giả sử
là ẩn số):
a j x j 0, j J ,
bi x i 0,i I ,
0
ci x i 0,i I ,
ĐIỀU KIỆN CẦN TỐI ƢU CẤP HAI CHO BÀI TOÁN
Chƣơng 2 trình bày các điều kiện cần tối ƣu cấp 2 cho cực tiểu yếu
n
nghiệm của (2.2) có 0 0 .
: x i 0,i 1,...,
Chứng minh
là orthant dƣơng.
Với mỗi tập A , int A , cl A và conv A kí hiệu tƣơng ứng là phần
trong tôpô, bao đóng tôpô và bao lồi của A . Với hai vectơ bất kỳ x, y
Do tính không tƣơng thích của (2.1) là tƣơng đƣơng với tính không
tƣơng tích của hệ tuyến tính thuần nhất
ta sử dụng kí hiệu sau đây
33
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
34
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Với mỗi phƣơng d
a j x j z 0, j J ,
0x z 0,
bi x i z 0,i I ,
c x z 0,i I 0 ,
i
i
n
ta đặt
J( x,d ): { j J( x ): j ( x )d 0 } .
Ta đƣa vào các định nghĩa:
cho nên ta nhận đƣợc kết quả bằng cách áp dụng định lý luân phiên
Motzkin.
Nhận xét 2.1
Tập các phƣơng giảm chặt cấp 2 của tại x theo phƣơng d
tính tƣơng thích của hệ sau:
Giả sử ( 1 ,...,l ):
n
là
D2 ( ,x,d ): { n : j ( x ) 2 j ( x )( d ,d ) 0,j J( x,d )};
Tập các phƣơng đạt đƣợc cấp 2 của tại x theo phƣơng d
i a j
ibi
i ci 0,
jJ
iI
iI 0
i i
i i 0,\
i j
jJ
iI
iI 0
j
i
i2 0 ,
jJ
iI
iI 0
j 0, j J ,i 0,i I .
là
D2 ( ,x,d ): { n : j ( x ) 2 j ( x )( d ,d ) 0,j J( x,d )};
Tập các phƣơng giảm cấp 2 của tại x theo phƣơng d
Từ bổ đề 2.1 ta suy ra rằng tính không tƣơng thích của (2.1) kéo theo
n
n
là
D2 ( ,x,d ): { n : j ( x ) 2 j ( x )( d ,d ) 0,j J( x,d )},
(2.3)
trong đó kí hiệu chỉ đạo hàm cấp 1, 2 chỉ đạo hàm cấp 2.
Lấy f ( f1 ,..., f l ): n
là hàm khả vi hai lần, J : {1,.....,l} và
S . Xét bài toán đa mục tiêu dƣới đây:
n
n
là hàm khả vi hai lần, J : { 1,..., }
min int f ( x ),
là tập chỉ số mà nó ứng với các thành phần của và x n . Ta đặt
J( x ): { j J : j ( x ) 0 } .
xS,
(2.4)
trong đó min int là cực tiểu vectơ theo nón int : x S là cực tiểu vectơ
Ta đƣa vào các định nghĩa sau:
địa phƣơng của (2.4) nếu tồn tại một lân cận N của x , sao cho không tồn
tại x S N thỏa mãn
Tập các phƣơng giảm của tại x là
D ( ,x ): { d n : j ( x )d 0,j J( x )};
Tập các phƣơng đạt đƣợc của tại x là
f ( x ) int f ( x ) .
Điểm cực tiểu địa phƣơng loại này cũng đƣợc gọi là cực tiểu yếu địa phƣơng.
D ( ,x ): { d n : j ( x )d 0,j J( x )};
35
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
36
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
f j ( x ) 2 f j ( x )( d ,d ) 0, j J( x,d ) .
Để đơn giản, ta sẽ viết D ( f ,x ) thay cho D ( f f ( x ),x ) và kí hiệu
tƣơng tự cho các tập khác.
(2.6)
Chứng minh
Định nghĩa 2.1
Cho S n . Tập tiếp liên cấp 2 của S tại x clS theo phương
Ngƣợc lại, giả sử d D ( f ,x ) cho trƣớc và T 2 ( S ,x,d ) là nghiệm
của (2.6).
d n là
T 2 ( S ,x,d ) : { n : { n } ,{tn } 0 sao cho x t nd 2 1t n2n S }.
Tập tiếp liên cấp 2 là một mở rộng của nón tiếp tuyến Bouligand T( S ,x ) và nó có
Theo định nghĩa của tập tiếp liên cấp hai tồn tại {tn } 0 và { n }
sao cho
xn x tn d 21 tn2n S ,n N .
một số tính chất. Chẳng hạn, nó là đóng và isotone, tức là
Nếu S1 S2và x clS1 thì T 2 ( S1 ,x,d ) T 2 ( S 2 ,x,d ) .
Do f j khả vi hai lần, ta có
Hơn nữa, ta có
f j ( xn ) - f j ( x ) t n [ f j ( x )( d 2-1 tnn )
T 2 ( S ,x,0 ) T( S ,x ) .
2-1 tn2 f j ( x )( d 2-1 tnn ,d 2-1 tnn ) tn n ] ,
và d T( S ,x ) T 2 ( S ,x,d ) .
(2.5)
Về các tính chất khác của loại xấp xỉ này, có thể xem trong [2].
2.2. ĐIỀU KIỆN CẦN TỐI ƢU CHO BÀI TOÁN ĐA MỤC TIÊU VỚI
RÀNG BUỘC TẬP
trong đó n 0 khi n .
Ta xét hai trƣờng hợp sau đây
Nếu j J( x,d ) , ta có f j ( x )( d 21 tn2n ) 0 , và do đó với n đủ
lớn ta có
Bằng kĩ thuật tuyến tính hoá với độ chính xác cấp hai ta có kết quả
f j ( xn ) f j ( x )
dƣới đây.
Nếu j J( x,d ) , ta có
Định lí 2.1
Nếu x S là cực tiểu yếu địa phương của (2.4) thì với mỗi phương
giảm d D ( f ,x ) hệ sau đây không có nghiệm T 2 ( S ,x,d ) :
37
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
lim f j ( x )n 2 f j ( x )( d 2 1 tnn ,d 2 1 tnn ) n
n
f j ( x )+2 f j ( x )( d ,d ) 0 .
38
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Cho nên với n đủ lớn ta có
Ta có x ( 0,0 ) là một điểm cực tiểu yếu.
f j ( xn ) f j ( x ) 21 tn2 [ f j ( x )n
Hơn nữa, với phƣơng d ( 1,0 ) D ( f ,x ) , tập tiếp liên cấp hai là
2 f j ( x )( d 21 tnn ,d 21 tnn ) n ]<0 .
T 2 ( S ,x,d ) { 2 : 2 2 4 } .
Hệ (2.6) trở thành 2 2 . Do đó, nó không có nghiệm T 2 ( S ,x,d )
Do đó, n N , sao cho f ( xn ) int f ( x ), n n .
theo định lý 2.1. Nhƣng (2.6) có một nghiệm cl convT 2 (S,x,d ) bởi vì
Điều này mâu thuẫn với giả thiết.
cl convT 2 (S,x,d ) { 2 : 2 4 } .
Ta chú ý rằng, khi 1, định lí 2.1 quy về điều kiện cần tối ƣu cấp
hai trong [7]. Trong trƣờng hợp d 0 , ta có kết quả sau.
Để
nhận
đƣợc
tính
không
tƣơng
thích
của
hệ
(2.6)
với
cl convT 2 (S,x,d ) ta có thể xét dạng lồi suy rộng sau đây của bài toán (2.4).
Hệ quả 2.1.1
Định nghĩa 2.2
Nếu x S là vectơ cực tiểu yếu địa phương của (2.4) thì hệ sau đây
Cho tập S n , hàm f : S là subconvexlike trên S nếu mọi
x1 ,x2 S , t 0,1 và int 0 , x3 S sao cho
không có nghiệm T( S ,x ) :
f j ( x )<0, j J .
tf ( x1 ) ( 1 t ) f ( x2 ) f ( x3 ) 0.
(2.7)
int Rl
Khi thay T 2 (S, x,d) bằng cl convT 2 (S, x,d) thì tính tƣơng thích của hệ
(2.6) không đúng nữa nhƣ trong ví dụ sau đây.
Định lý 2.2
Giả sử f là subconvexlike trên S. Nếu x S là cực tiểu yếu địa
Ví dụ 2.1
phương của (2.4) thì với mỗi phương giảm d D ( f ,x ) hệ (2.6) không có
Xét bài toán đa mục tiêu (2.4)với
nghiệm cl convT 2 (S,x,d ) .
f ( x1 ,x2 ) : ( x x2 ,x2 x ) ,
2
1
2
1
Chứng minh
và cho tập chấp nhận đƣợc cho bởi
Giả sử ngƣợc lại tồn tại d D ( f ,x ) và cl convT 2 (S,x,d ) sao cho
S : {x 2 : x14 x22 4x14 } .
(2.6) đúng. Từ (2.5) suy ra d T( S ,x ) .Theo định lý 3.1 [9], tồn tại số
39
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
40
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
khác không
sao cho x là cực tiểu địa phƣơng của bài toán vô
Tập các phương giảm tại x của bài toán (2.4):
hƣớng sau
D( x ) : D ( f ,x ) D ( g,x ) D ( h,x ) ;
min ( x ): j f j ( x ),
jJ
Tập tuyến tính hóa cấp hai yếu của S tại x theo phương d n :
x S.
L2 ( x,d ) : D 2 ( g,x,d ) D 2 ( h,x,d );
Theo hệ quả 3.1 [7], ta có
( x )d 0,d T( X ,x ) ;
Tập tuyến tính hóa cấp hai của S tại x theo phương d n :
(2.8)
Và nếu ( x )d 0 , thì
L2 ( x,d ) : D 2 ( g,x,d ) D 2 ( h,x,d ) .
Để nhận đƣợc điều kiện cần tối ƣu cấp hai của bài toán (2.4), ta trình
( x )+ ( x )( d ,d ) 0, cl convT ( S ,x,d ) .
2
2
(2.9)
Chọn d d , (2.8) kéo theo j 0 với mỗi j T( x,d ) . Khi đó mâu
thuẫn với (2.9).
bày kết quả liên hệ các tập tuyến tính hóa cấp hai của S và tập tiếp liên
cấp hai của S.
Bổ đề 2.2
Giả sử x S và d D ( g,x ) D ( h,x ) . Khi đó,
2.3. ĐIỀU KIỆN CẦN TỐI ƢU FRITZ JOHN
T 2 ( S ,x,d ) L2 ( x,d ) .
Phần này chúng ta xét tập chấp nhận đƣợc S đƣợc xác định bởi các
ràng buộc bất đẳng thức và đẳng thức.
Nếu { hi ( x )}iI là độc lập tuyến tính thì
Giả sử g ( g1 ,...,g p ) : và h ( h1 ,...,hq ) :
n
p
(2.10)
n
q
là hàm khả
L2 ( x,d ) T 2 ( S ,x,d ) .
vi hai lần, và lấy I : {1,..., p } và I : {1,...,q } là các tập chỉ số tƣơng ứng.
0
Giả sử rằng miền chấp nhận đƣợc của bài toán (2.4) đƣợc xác định
(2.11)
Chứng minh
Cho T 2 ( S ,x,d ) , tồn tại {tn } 0 và { n } sao cho
bởi S : S g Sh , trong đó
xn x tn d 21 tn2n S ,n N .
S g : {x n : g i ( x ) 0,i I } ,
Bởi vì g i và hi là khả vi hai lần, ta có
Sh : {x n : hi ( x ) 0,i I 0 } .
0 gi ( xn ) gi ( x ) tngi ( x )( d 2 1tnn )
Ta đƣa vào các tập hợp sau:
41
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
42
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
21 tn2 2 gi ( x )( d 2 1 tn n ,d 2 1 tn n ) tn2 n , i I ;
lim gi ( x )n 2 gi ( x )( d 2 1 tnn ,d 2 1 tnn ) =
(2.12)
n
0=hi ( xn ) hi ( x ) tnhi ( x )( d 2 1 tnn )
21 tn2 2 hi ( x )( d 2 1 tn n ,d 2 1 tn n ) tn2 n , i I0.
gi ( x )+2 gi ( x )( d ,d ) 0 .
(2.13)
Do đó, với mỗi i I ( x,d ) , chia (3.12) cho 21 tn2 , ta có
0 gi ( x )n 2 gi ( x )( d 2 1 tnn ,d 2 1 tnn ) 2 n .
Với mỗi i I 0 , chia (2.13) cho tn và qua giới hạn, ta nhận đƣợc
Do đó, (2.11) thỏa mãn.
Giả sử { hi ( x )}iI 0 là độc lập tuyến tính. Nếu x S là cực tiểu yếu
địa phương của (2.4) thì với mỗi phương d D( x ) ,hệ sau đây là không
hi ( x )d 0 . Bây giờ chia cho 21 tn ta nhận đƣợc
0=hi ( x )n hi ( x )( d 2 tnn ,d 2 tnn ) 2 n .
1
gi ( xn ) 21 tn2[gi ( x)n 2 gi ( x)(d 21tnn , d 21tnn ) n ]<0 .
Định lý 2.3
Cho n , ta nhận đƣợc D 2 ( g ,x,d ) .
2
Vì vậy,
1
tương thích (ẩn số n ):
f j ( x )+2 f j ( x )( d ,d ) 0, j J( x,d ),
2
gi ( x )+ gi ( x )( d ,d ) 0, i I ( x,d ),
2
0
hi ( x )+ hi ( x )( d ,d ) 0, i I .
Cho n ta nhận đƣợc D ( h,x,d ) . Vì vậy ta suy ra (2.10).
2
Chứng minh phần thứ hai: Theo định lý 3.5 [10], D 2 ( h,x,d ) T 2 ( S h ,x,d ) .
Do đó, với mỗi L2 ( x,d ) tồn tại {tn } 0 và { n } sao cho
(2.14)
Chứng minh
Định lý đƣợc suy ra từ định lý 2.1 và bổ đề 2.2.
xn : x tn d 21tn2n Sh , n N .
Định lý 2.4
Ta chỉ cần chỉ rằng xn Sg với mọi n đủ lớn.
Nếu x S là cực tiểu yếu địa phương của (2.4), thì với mỗi phương
Với mỗi i I( x ) , tính liên tục của g i kéo theo gi ( xn ) 0 .
giảm d D( x ) tồn tại , p và q , không đồng thời bằng
Với mỗi i I( x )\ I ( x,d ) , ta có
không, sao cho
gi ( xn ) tn [ gi ( x )( d 2 1 tnn ) n ]<0 .
(i) j f j ( x ) igi ( x ) ihi ( x ) 0 ;
jJ
iI
iI 0
(ii) j 2 f j ( x ) i 2 gi ( x ) i 2 hi ( x ) ( d ,d ) 0 ;
0
iI
iI
jJ
Với mỗi i I ( x,d ) , ta có
43
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
44
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
(iii) i gi ( x ) 0 với mỗi i I ;
L2 ( x,d ) T 2 ( S ,x,d ) ;
(iv) jf j ( x )d 0 với mỗi j J và igi ( x )d 0 với mỗi i I .
Điều kiện chính quy cấp hai Guignard (GSOCQ) đúng tại
x theo phương d n nếu:
Chứng minh
Nếu { hi ( x )}iI 0 là phụ thuộc tuyến tính, ta chọn j i 0 và i
không đồng thời bằng không sao cho
h ( x ) 0 .
i
L2 ( x,d ) clconvT 2 ( S ,x,d ) .
Chú ý rằng (ASOCQ) và (GSOCQ) trở thành các điều kiện chính
i
iI 0
Điều kiện (i), (iii) và (iv) thỏa mãn tầm thƣờng. Nếu (ii) không đúng,
thì ta chỉ cần thay i i .
Trƣờng hợp hi (x)iI 0 là độc lập tuyến tính, ta áp dụng bổ đề 2.1
cho hệ (2.14) và lấy j i 0 với mọi j J( x,d ) và i I ( x,d ) .
Chú ý rằng các định lý 2.3 và 2.4 bao hàm đƣợc điều kiện tối ƣu cấp 1
quy Abadie và Guignard đã biết khi lấy d 0 . Hiển nhiên là nếu
(ASOCQ) đúng thì (GSOCQ) cũng đúng. Chiều ngƣợc lại không đúng
nhƣ đã biết với d=0.
Kết quả dƣới đây suy ra trực tiếp từ định lý 2.1.
Định lý 2.5
Giả sử (ASOCQ) đúng tại x S theo phương giảm d D( x ) . Nếu
bằng cách lấy d 0 .
x là cực tiểu yếu địa phương của (2.4) thì hệ sau đây (ẩn số R n )
2.4. ĐIỀU KIỆN TỐI ƢU KUHN - TUCKER
không tương thích:
Quy tắc nhân tử Lagrange trong định lý 2.4 không đảm bảo ít nhất
f j ( x ) 2 f j ( x )( d ,d ) 0,
2
gi ( x ) gi ( x )( d ,d ) 0,
2
hi ( x )+ hi ( x )( d ,d ) 0,
một nhân tử Lagrange ứng với hàm mục tiêu là khác không. Hiển nhiên là
khi tất cả các nhân tử Lagrange tƣơng ứng với hàm mục tiêu bằng không,
hàm mục tiêu không đóng vai trò gì trong điều kiện tối ƣu. Để khắc phục
j J( x,d ),
i I ( x,d ),
(2.15)
i I0.
Ví dụ 2.2
điều đó ta đƣa vào các giả thiết chính quy.
Xét bài toán đa mục tiêu với
Định nghĩa 2.3
Cho điểm chấp nhận được x n .
Điều kiện chính quy cấp hai Abadie(ASOCQ) đúng tại x theo
phương d n nếu:
f ( x1 ,x2 ,x3 ) : ( x1 ,x2 ,x3 x12 x22 ),
g( x1 ,x2 ,x3 ) : x1 x2 x3 x3 ,
h( x ,x ,x ) : x x .
1 2
1 2 3
Ta có x ( 0,0,0 ) là cực tiểu yếu. Tập các phƣơng giảm là
45
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
46
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
D( x ) d R 3 : d1 0,d 2 0,d 3 0
Chứng minh
Định lý trên đƣợc suy trực tiếp từ bổ đề 2.1 và định lý 2.2.
Với các phƣơng d nhƣ vậy ta có
Trong các định lý trƣớc, các điều kiện chính quy kéo theo nhân tử
nếu d1d 2 0,
,
L2 ( x,d )
3
R : 3 0 , nếu d1d 2 0;
Lagrange 0 . Bây giờ ta nghiên cứu điều kiện chính quy đảm bảo tất cả
các nhân tử Lagrange ứng với các thành phần của hàm mục tiêu là dƣơng.
nÕ u d1d 2 0,
,
T 2 ( S ,x,d )
3
R : i 0,3 0 , nÕ u di 0,i 1,2.
Ta đƣa vào tập các phƣơng giảm cấp hai tại x của bài toán (2.4) theo
d Rn :
Nhƣ vậy (ASOCQ) chỉ đúng với các phƣơng giảm d mà d1d2 0 , và
D 2 ( x,d ) : D 2 ( f ,x,d ) D 2 ( g,x,d ) D 2 ( h,x,d ) .
nhƣ vậy định lý 3.1 trong [1] không thể áp dụng đƣợc. Với các phƣơng
Ta có D2 ( x,0 ) D( x ) .
giảm d 0 khác thì hệ (2.15) có nghiệm =(-1,-1,0) .
Định nghĩa 2.4
Từ định lý 2.5 ta nhận đƣợc quy tắc nhân tử Kuhn-Tucker sau đây.
Cho điểm chấp nhận được x S . Điều kiện chính quy cấp hai
Định lý 2.6
Giả sử (ASOCQ) đúng tại x S theo phương giảm d D( x ) . Nếu x
(GSORC) đúng tại x theo phương d R n nếu
D 2 ( x,d ) clconvT 2 ( S s ,x,d ) ,
là cực tiểu yếu địa phương của (2.4) thì tồn tại R , Rp , Rq với
0 sao cho ( i ) ( iv) của định lý 2.4 đúng.
s 1
trong đó S s : x S : f j ( x ) f j ( x ) 0,j J \ s x .
Chứng minh
Định lý đƣợc suy ra trực tiếp từ bổ đề 2.1 áp dụng cho hệ (2.15) với
j 0 và i 0 với mọi j J( x,d ) và i I ( x,d ) .
Định lý 2.8
Giả sử (GSORC) đúng tại x S theo phương giảm d D( x ) . Nếu x
là cực tiểu yếu địa phương của (2.4), thì với mỗi s J( x,d ) , hệ tuyến tính
Định lý 2.7
sau đây (ẩn số R n ):
Giả sử (GSOCQ) đúng tại x S theo phương giảm d D( x ) và f là
subconvexlike trên S. Nếu x là cực tiểu yếu địa phương của (2.4), thì tồn tại
R , R và ¡
q
với 0 sao cho ( i ) ( iv ) của định lý 2.4 đúng.
47
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
48
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
