ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC SƯ PHẠM
- - - - - -- - - - - -
NGÔ THỊ THU THUỶ
VỀ ĐỊNH LÍ DUBOVITSTKII-MILYUTIN
VÀ ĐIỀU KIỆN TỐI ƯU
LUẬN VĂN THẠC SĨ TOÁN HỌC
THÁI NGUYÊN - 2008
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
1
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
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
2
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
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.
Cuối cùng tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo PGS. TS. Đỗ
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 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 sư
phạm-Đại học Thái Nguyên cùng các thầy giáo cô giáo đã tham gia giảng dạy
khóa học, xin chân thành cảm ơn gia đình, bạn bè đồng nghiệp và các thành
viên trong lớp Cao học Toán K14 đã luôn quan tâm, động viên, giúp đỡ tôi
trong suốt thời gian học tập và quá trình làm luận văn.
Thái nguyên, tháng 9 năm 2008
3
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
Ngô Thị Thu Thủy
Chương 1
ĐỊNH LÍ DUBOVITSTKII-MILYUTIN
Chương 1 trình bày định lý Dubovitskii-Milyutin (1965, [1]) và một số
kết quả có liên quan trong giải tích không trơn.
1.1. CÁC KIẾN THỨC BỔ TRỢ
Giả sử X là không gian tôpô tuyến tính, X là không gian liên hợp của
X, K là một nón trong X có đỉnh tại 0, tức là K K ( 0). Khi đó nón
liên hợp K của K được định nghĩa như sau:
K x X : x , x 0, x K .
Mệnh đề 1.1 ([6])
Giả sử K là nón có đỉnh tại x0 , x là một phiếm hàm tuyến tính và
x , x
x K .
Khi đó,
x , x x , x0
x K .
Mệnh đề 1.2 ([6])
Hai tập lồi khác rỗng bất kì không tương giao trong không gian tôpô
tuyến tính, một tập có điểm trong thì tách được.
4
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
Định lí 1.1
Giả sử K là một nón lồi có đỉnh tại 0, int K , L là một không gian
con, int K L . Giả sử x là một phiếm hàm tuyến tính liên tục trên L
thỏa mãn
x , x 0 x K L .
Khi đó, tồn tại phiếm hàm tuyến tính liên tục x trên X sao cho
x , x x , x
x , x 0
x L ,
x K .
Chứng minh
(a) Nếu x 0 trên L , thì ta chọn x 0.
(b) Nếu x 0 , ta đặt
Q1 : x L : x , x 0 .
Khi đó, Q1 lồi và khác (bởi vì 0 Q1 ). Đồng thời
Q1 intK .
Thật vậy, nếu
Q1 int K .
x0 Q1 int K .
x0 L, x , x0 0.
5
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
Bởi vì x0 L intK , cho nên trong lân cận của điểm x0 ta tìm được điểm
x1 L K mà x , x1 0. Điều đó mâu thuẫn với tính không âm của x , x
trên L K . Vì vậy,
Q1 intK .
Do đó, tồn tại siêu phẳng tách Q1 và int K , tức là tồn tại phiếm hàm
tuyến tính liên tục X sao cho
, x 0 x intK ,
(1.1)
, x 0 x Q1 .
(1.2)
Để chứng minh tiếp định lý, ta cần bổ đề sau:
Bổ đề 1.1
Giả sử 1, 2 X ,
Q1 : x : 1, x 0 ,
Q2 : x : 2 , x 0 ,
và Q1 Q2 . Khi đó, hoặc 2 0 ( tức là Q2 X ) hoặc 1=2 , 0 (tức là
Q1 Q2 ).
Bây giờ trên không gian con L ta xét hai phiếm hàm tuyến tính liên tục
x và . Xét các tập hợp:
Q1 : x L :
x , x 0 ,
Q2 : x L : , x 0 .
Ta có Q1 Q2 (do (1.2)). Áp dụng bổ đề 1.1, ta nhận được hai trường hợp:
6
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
(i) Hoặc Q1 Q2 ,
(ii) Hoặc Q2 L.
Trường hợp (ii) không thể xảy ra, bởi vì từ (1.1) ta có , x 0, nếu
x L int K .
Vì vậy, theo bổ đề 1.1
x , x , x
0
trên L. Bởi vì x , x và , x cùng dấu trên K L, cho nên 0. Khi đó,
x là thác triển cần tìm của x .
Mệnh đề 1.3 ([6])
K K .
I
I
1.2. ĐỊNH LÝ DUBOVITSKII-MILYUTIN
Định lý 1.2.
n
Giả sử K1, K2 ,, Kn là các nón lồi mở (đỉnh tại 0),
Ki . Khi đó,
i 1
n
n
K
i Ki .
i 1 i 1
Chứng minh
Xét không gian tích X X X X n . Mỗi điểm x X có dạng:
x x1,, xn , xi X ;
7
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
X X X ; X có dạng:
1,, n , i X ;
n
, x i , xi .
i 1
Đặt
K : x x1,, xn : xi Ki , i 1,, n .
Ta có K là một nón lồi mở trong X , bởi vì K là tích của các nón lồi mở K i .
Đặt
L : x x,, x : x X .
Ta có L là không gian con tuyến tính của X . Bởi vì
n
Ki , cho nên
i 1
L K .
n
Bây giờ ta lấy x Ki . Ta sẽ chứng minh
i 1
n
x Ki.
i 1
Đặt
, x x , x ,
trong đó
x X , x x,, x L.
8
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
Khi đó, là một phiếm hàm tuyến tính trên L . Ta có
, x 0 x L K ,
bởi vì
x x,, x L K .
n
x Ki .
i 1
, x x , x 0.
Áp dụng định lý 1.1, tồn tại X sao cho
, x 0 x K ,
, x , x
(1.3)
x L .
(1.4)
Giả sử 1,, n . Khi đó, với mọi x X , thì x x,, x L và từ
(1.4) ta có
n
, x i , x = , x = x , x .
i 1
n
x i .
i 1
Từ (1.3), ta suy ra
9
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
n
0 xi Ki , i 1,, n .
i , xi
i 1
i , xi 0 xi Ki .
Ki i 1,, n .
n
x Ki.
i 1
n
n
Ki Ki .
i 1
i 1
Mặt khác, theo mệnh đề 1.3,
n
Ki
i 1
n
Ki .
i 1
Do đó, định lý được chứng minh.
Định lý 1.3 (Dubovitskii-Milyutin)
Giả sử K1, K2 ,, Kn , Kn1 là các nón lồi đỉnh tại 0; Các nón K1, K2 ,,
n 1
Kn mở. Khi đó,
Ki xi Ki i 1,, n 1 không đồng thời bằng
i 1
0, sao cho
x1 xn xn1 0.
(1.5)
Chứng minh
a Điều kiện cần. Giả sử
Trường hợp 1 :
n 1
Ki .
i 1
n
Ki .
i 1
10
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
n
Đặt K : K i . Khi đó, K , mở và K Kn1 . Theo mệnh đề 1.2,
i 1
tồn tại x X , x 0 sao cho
x K , y Kn1 .
x , y x , x
Bởi vì K là nón có đỉnh tại 0, cho nên từ mệnh đề 1.1 ta suy ra
x K , y K n1 .
x , y 0 x , x
(1.6)
Từ đó,
n
x K K i .
i 1
Áp dụng định lý 1.2 ta nhận được
n
x xi , xi Ki i 1,, n .
i 1
Đặt xn1 x . Khi đó, từ (1.6) suy ra xn 1 K n1 . Hơn nữa xn 1 0 và
x1 xn xn 1 0.
Trường hợp 2 :
n
Ki .
i 1
Khi đó, tồn tại s : 1 s n sao cho
s
s 1
i 1
i 1
K K i ,
Ki .
Áp dụng trường hợp 1 (với s đóng vai trò là n) ta nhận được
xi Ki i 1,, s 1 , xs1 0
11
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
sao cho
x1 xs xs1 0.
Chọn xs 2 xn1 0 ta nhận được (1.5).
b Điều kiện đủ. Giả sử tồn tại
0 sao cho
x1
xn
xn 1
xi i 1,, n 1 không đồng thời bằng
0, nhưng
n 1
Ki .
i 1
Do đó, tồn tại x0 Ki i 1,, n 1 . Đồng thời, tồn tại chỉ số j :
1 j n sao cho
,
xn 1
xj
0 , bởi vì nếu không thì
xn1
n
xi 0 , vì thế
i 1
x1 ,
đồng thời bằng 0.
Ta có xj , x0 > 0 ( bởi vì K j mở, nếu xj , x0 = 0, thì tồn tại x1 K j
sao cho xj , x1 < 0 (!) ). Do đó,
0 x1 xn xn1, x0 xj , x0 0 : 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 x0 , nếu tồn tại lân
cận U của v, số 0 và số 0 0 sao cho 0, 0 , u U , ta có
f x0 u f x0
(1.7)
Các phương giảm của f tại x0 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 x0 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 x0 , nếu tồn
tại lân cận U của v, số 0 0 sao cho
12
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
0, 0 , u U : x0 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 x0 .
Các phương chấp nhận được của tập Q tại x0 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 x0 , nếu nón các phương
chấp nhận được tại x0 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 x0 , nếu
0 0, 0, 0 , x Q sao cho
x x0 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 x0 lập thành một nón ta gọi là nón tiếp
tuyến của Q tại x0 .
v là phương chấp nhận được của Q tại x0 v là phương tiếp xúc của Q
tại x0 .
Các phương tiếp xúc với Q tại x0 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.
13
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
Ta nói hạn chế Q loại đẳng thức là đều tại x0 , nếu nón các phương tiếp
xúc với Q tại x0 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 Q :
ii f x giảm đều tại
iii
n 1
Qi
tại x Q;
i 1
x , với các nón phương giảm K0 ;
Hạn chế loại bất đẳng thức Qi i 1,, n là đều tại x , với nón
các phương chấp nhận được Ki ;
iv Hạn chế loại đẳng thức Qn1 là đều tại
x , với nón các phương tiếp
xúc Kn 1.
Khi đó, tồn tại xi Ki i 0,1,, n 1 không đồng thời bằng 0 thỏa mãn
phương trình Euler - Lagrange:
x0 x1 xn xn1 0
(1.8)
Chứng minh
Trước hết ta chứng minh rằng từ giả thiết i ta phải có
n 1
Ki . Điều
i 0
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).
n 1
Phản chứng:
K i ,
i 0
tức là tồn tại v Ki i 1,, n 1. Theo định
nghĩa của Ki i 1,, n , tồn tại 0 0 , lân cận U của v và số 0 sao cho
0, 0 , u U :
14
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
n
x x u Qi ,
(1.9)
i 1
f x u f x .
(1.10)
Bởi vì v là phương tiếp xúc của Qn 1 tại x , cho nên 1 0, 0, 1 ,
x Qn1 sao cho
x x v r Qn1
(1.11)
Chọn 2 để với mọi 0, 2 ta có
r
U v,
hay là
u v
r
U
(1.12)
Đặt 3 min 0 , 1, 2 . Từ (1.11) và (1.12) suy ra
x x u Qn 1
0, 3 .
Từ (1.9) - (1.12) ta nhận được
x
n 1
Qi 0, 3 .
i 1
Từ (1.10), (1.12) ta có
f x u f x f x
0, 3 .
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 đó,
15
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
n 1
Ki .
i 0
Từ các giả thiết ii , iii ta nhận được K0 , K1,, Kn là các nón lồi mở
đỉnh tại 0. Theo giả thiết iv , Kn1 là nón lồi đỉnh tại 0. Áp dụng định lí 1.3,
tồn tại xi Ki i 0,1,, n 1 không đồng thời bằng 0 thỏa mãn (1.8).
n 1
Từ chứng minh định lý 1.4 ta suy ra
Ki
i 0
x0 0.
Mệnh đề 1.4 ([6])
Giả sử
X ; K1 x : , x 0; K 2 x : , x 0; K3 x : , x 0.
Khi đó,
a
K1 : ;
b
K 2 : 0 ;
c
K3
X , nÕu 0 ;
K 2 , nÕu 0.
Định lý 1.5 (Fakas-Minkovskii)
Giả sử
K x m : ai , x 0, ai m , i 1,, n ;
Khi đó,
K
n
i 1
ai yi : yi 0, i 1,, n .
16
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
Chứng minh
Kí hiệu
Qi : x : ai , x 0 .
n
Khi đó, K Qi . Theo mệnh đề 1.4,
i 1
Qi ai yi : yi 0 .
Xét tập :
Qi
i 1
n
n
i 1
ai yi : yi 0, i 1,, n .
Ta có
n i
a yi : yi 0, i 1,, n
i 1
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
n
Qi
là đóng * yếu trong m . Theo [6, hệ quả 1.12.1],
i 1
n
n
Qi Qi ,
i 1 i 1
tức là
K
n
i 1
ai yi : yi 0, i 1,, n .
17
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
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 DubovitskiiMilyutin. 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; x 0 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 r / U 0 được hiểu theo nghĩa sau:
U 0 , 1 0 sao cho, (0, 1), r / U 0 .
Hơn nữa,
pn n ,
n
i 1
i 1 .
P ' x0 kí hiệu đạo hàm Fréchet của toán tử P tại x 0 .
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 IC A, x0 của A tại x 0 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:
18
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
i x IC A, x0 , OC x IC A, x0
sao cho
ii U x0 thỏa mãn
x0 OC x U x0 \ x0 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;
iii
x1, x2 ,, xn CAI A , U 0 , 0 xi , n 0 sao cho
0,0 , : p n E thỏa mãn
n
i xi U 0 A;
i 1
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 x 0 được xác định bởi
AC A, x 0 { x E | 1 0, U x sao cho
0, 1 , x U x , x0 x A}.
Nhắc lại rằng nón tiếp tuyến của A tại x 0 được xác định bởi
TC A, x 0 { x E | 1 0 sao cho 0, 1 , r E thỏa mãn
19
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
- Xem thêm -