Về điều kiện chính quy cấp hai và điều kiện tối ưu cấp hai

[motvongtraibong]

Download miễn phí Luận văn Về điều kiện chính quy cấp hai và điều kiện tối ưu cấp hai

MỤC LỤC
Trang
Mục lục.
Mở đầu.
Chương 1
ĐIỀU KIỆN TỐI ưU CẤP HAI CHO BÀI TOÁN TỐI ưU ĐƠN MỤC TIÊU
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
1.3. Điều kiện chính quy cấp hai và điều kiện tối ưu cấp hai. 15
Chương 2
ĐIỀU KIỆN CẦN TỐI ưU CẤP HAI CHO BÀI TOÁN TỐI ưU ĐA MỤC TIÊU
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
2.3. Điều kiện cần tối ưu Fritz John. 41
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


http://cloud.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2014-01-01-luan_van_ve_dieu_kien_chinh_quy_cap_hai_va_dieu_ki.Wx1VCzuQH5.swf /tai-lieu/de-tai-ung-dung-tren-liketly-53158/
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí

Tóm tắt nội dung tài liệu:

g 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
*
0( x )
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à
*
0( x ) 
. 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,
hay 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
 x 0 K 0D L( x , ) 0, N (G( x )) . (1.17)
Với điều kiện chính quy Robinson (1.13), tập hợp
0( x )
các nhân tử
Lagrange thỏa mãn (1.17) là khác rỗng và bị chặn (xem [8]).
16
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Khi tập
K
là một nón lồi và
y K
, nón pháp tuyến
KN ( y )
có dạng:
 0* *KN ( y ) y K : y ,y  
,
trong đó
 * * *K : y Y : y ,y 0, y K     
là nón cực của nón
K
(đối ngẫu âm). Trong trƣờng hợp đó, điều kiện
K 0N (G( x ))
trở thành
K 
và
0,G( x ) 0 
.
Nhắc lại rằng: nón
 0 0 K 0 0C( x ): h X : DG( x )h T (G( x )),Df ( x )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
0x
. 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
0( x )
các nhân tử Lagrange khác rỗng thì
0Df ( x )h 0
với mọi
h X
thỏa mãn
0 K 0DG( x )h T (G( x ))
. Trong trƣờng hợp đó bất đẳng thức
0Df ( x )h 0
, trong định nghĩa của nón tới hạn có thể thay bởi đẳng thức
0Df ( x )h 0
. Điều đó là tƣơng đƣơng với
0,DG( x )h 0 
với mọi
0( x ) 
.
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
2 2
0
1
x(t) = x th t + o(t )
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.
17
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Định lý 1.1
Giả sử
0x
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
0h C( x )
và tập lồi bất kỳ T
2
K 0 0( h ) O (G( x ),DG( x )h )
,

0
2
xx 0
( x )
Sup D L( x , )( h,h ) ( ,

  


T
( )) 0h 
.
(1.20)
Chứng minh
Chú ý rằng nếu T (h)=

thì
(.,
T (h)) =
 
và (1.20) đúng một
cách tầm thƣờng.
Ta giả sử T (h) và do đó tập
2
K 0 0O (G( x ),DG( x )h )
khác rỗng.
Ta khẳng định rằng giá trị tối ƣu của bài toán:
2
0 0
X
MinDf ( x ) +D f ( x )( h,h ) 
, (1.21)
2 2
0 0 K 0 0DG( x ) +D G( x )( h,h ) O (G( x ),DG( x )h ) 
là không âm.
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
2
00 ( x ,h )
, trong đó:
1: G ( K ) 
. Vì thế ta
có thể tìm đƣợc dãy
kt 0
sao cho
   2 2k 0 k k
1
x : x t h t + o(t )
2
 .
18
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Dãy
kx
là chấp nhận đƣợc của bài toán
( P )
và hội tụ đến cực tiểu địa
phƣơng
0x
. Do đó,
k 0f ( x ) f ( x )
với mọi
k
đủ lớn. Sử dụng khai triển
Taylor cấp hai ta có
2 2 2
0 k 0 k 0 k 0 0 k
1
f ( x ) f ( x ) f ( x ) t Df ( x )h t Df ( x ) +D f ( x )( h,h ) ( t )
2
       .
Bởi vì
0Df ( x )h 0
, với bất kỳ
0h C( x )
, ta nhận đƣợc
2
0 0Df ( x ) +D f ( x )( h,h ) 0 .
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
tập T(h) := cl {T (h)
K 0T (G( x ))
. 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ác tập tiếp tuyến ngoài cấp hai đóng, ta suy ra
2
K 0 0T( h ) O (G( x ),DG( x )h )
.
Rõ ràng nếu ta thay đổi các tập tiếp tuyến cấp hai ngoài trong (1.21)
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:
2
0 0
X
MinDf ( x ) +D f ( x )( h,h ) 
, (1.22)
2
0 0DG( x ) +D G( x )( h,h ) T( h ) 
là không âm.
Bài toán tối ƣu (1.22) lồi và đối ngẫu (tham số) của nó là:
 
0
2
xx 0
(x )
Max D L( x , )( h,h ) ( ,T( h ))     
(1.23)
Thật vậy, hàm Lagrange của (1.22) là
19
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
2
x 0 xx 0L( , )=D L( x , ) +D L( x , )( h,h )   .
Bởi vì với bất kỳ
z T( h )
, ta có
K 0z T (G( x )) T( h ), 
cho nên
( ,T( h ))   
với mỗi
 K 0 K 0T (G( x )) N (G( x ))  .
Vì thế miền hữu hiệu của đối ngẫu tham số của (1.22) là nằm trong
0( x )
. Khi đó ta suy ra tính đối ngẫu. Hơn nữa, điều kiện chính quy
Robinson (1.13) kéo theo
0 K 0DG( x )X T (G( x )) Y 
.
Bởi vì với bất kỳ
z T( h )
thì
K 0z T (G( x )) T( h ) 
, ta có
0z DG( x )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
Robinson cho bài toán (1.22) cũng đúng. Do đó, không có lỗ hổng đối
ngẫu giữa (1.22) và đối ngẫu (1.23) (xem [3]).
Ta nhận đƣợc giá trị tối ƣu của (1.23) không âm. Bởi vì T
(h)
T( h )
, ta có
( , 
T (h))
( ,T( h )) 
. Vì vậy ta suy ra (1.20) và định
lý đƣợc chứng minh.
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
2
K 0 0O (G( x )),DG( x )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
20
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
2
K 0 0T (G( x )),DG( x )h
. Nói chung, tập T (h) có thể lấy lớn hơn
2
K 0 0T (G( x ),DG( x )d )
và do đó định lý 1.1 là mạnh hơn.
(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.
(iii) Nếu
2
K 0 00 O (G( x ),DG( x )h )
với mọi
0h C( x )
, nói riêng nếu tập K
là một đa diện, thì
K 0
2
K 0 0 T ( G( x )) 0O ( G( x ),DG( x )h ) T ( DG( x )h )
,
và
( , 
T (h)) = 0 với mỗi
0( x ) 
, và
T (h)
2
K 0 0: O (G( x ),DG( x )h )
.
(iv) Giả sử  là tập hợp của các dãy
 nt
các số dƣơng hội tụ tới 0. Với
bất kỳ
 ns= t
 ,
y K
, và
Kd T ( y )
ta có thể đƣa vào tập tiếp tuyến
cấp hai dƣới đây:
2,s 2 2
K n
1
T ( y,d ) : :dist(y+t d t ,K)= (t )
2
     
 
.
Với bất kỳ
s 
, tập
2,s
KT (y,d)
là lồi và đóng. Rõ ràng giao của
2,s
KT ( y,d )
theo tất cả
s 
là
2
KT (y,d)
, và hợp của
2,s
KT ( y,d )
lấy theo
s 
là
2
KO ( y,d )
. Một cách chọn T (h) là
2,s
K 0 0T (G( x ),DG( x )h )
với bất
kỳ
s 
.
(v) Ta có thể phát biểu điều kiện cần cấp hai (1.20) dƣới dạng
 
0
2
xx 0
O(h) ( x )
inf sup D L( x , )( h,h ) ( ,T( h )) 0
 
  
 
 
, (1.24)
T
(h)
21
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
2
K 0 0O (G( x ), DG( x )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
2
K 0 0...