MỞ ĐẦU
Do nhu cầu của kinh tế và kỹ thuật, lý thuyết tối ưu hoá đã phát triển mạnh mẽ và ngày càng thu được nhiều kết quả quan trọng. Lý thuyết các điều kiện tối ưu là một bộ phận quan trọng của lý thuyết tối ưu hoá. Các điều kiện tối ưu cấp cao được nghiên cứu bởi nhiều tác giả và dưới nhiều ngôn ngữ đạo hàm hoặc đạo hàm theo phương khác nhau ( xem chẳng hạn [2] – [10] ).
Năm 2002, I.Ginchev [5] đưa ra khái niệm đạo hàm theo phương cấp cao cho một hàm giá trị thực mở rộng và thiết lập các điều kiện tối ưu cấp cao cho bài toán tối ưu không trơn không ràng buộc. B.Jiménez ( [6] , 2002 ) đưa ra khái niệm cực tiểu Pareto địa phương chặt cấp m và cực tiểu Pareto địa phương chặt cho bài toán tối ưu đa mục tiêu. Sử dụng các khái niệm cực tiểu chặt của Jiménez [6], Đ.V.Lưu và P.T.Kiên [7] đã dẫn các điều kiện cần và đủ cho cực tiểu Pareto địa phương chặt cấp m và cực tiểu Pareto địa phương chặt của bài toán tối ưu đa mục tiêu không trơn với ràng buộc tập trong không gian định chuẩn, dưới ngôn ngữ đạo hàm theo phương cấp cao của Ginchev [5].
Luận văn tập trung trình bày các điều kiện tối ưu cấp cao dưới ngôn ngữ đạo hàm theo phương cấp cao của I.Ginchev trên và dưới cho bài toán tối ưu đơn mục tiêu không trơn không có ràng buộc và bài toán đa mục tiêu không trơn với ràng buộc tập.
Đề tài: VỀ ĐIỀU KIỆN TỐI ƯU CẤP CAO TRONG TỐI ƯU KHÔNG TRƠN
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.
Chương I trình bày các điều kiện tối ưu cấp cao của I.Ginchev [5] cho bài toán tối ưu đơn mục tiêu không trơn, không có ràng buộc trong không gian Banach. Kết quả chỉ ra rằng với các điểm cực tiểu cô lập, điều kiện đủ cũng là điều kiện cần, và như vậy ta nhận được một điều kiện đặc trưng cho cực tiểu cô lập.
Chương II trình bày các nghiên cứu về các điểm cực tiểu Pareto địa phương chặt cấp m và cực tiểu Pareto địa phương chặt của B.Jiménez [6] và các điều kiện cần và đủ cho các điểm cực tiểu yếu, cực tiểu Pareto địa phương chặt cấp m và cực tiểu Pareto địa phương chặt của Đ.V.Lưu và P.T.Kiên [7] cho bài toán tối ưu đa mục tiêu không trơn trong không gian định chuẩn với ràng buộc tập, dưới ngôn ngữ đạo hàm theo phương cấp cao của I.Ginchev [5].
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, tạo mọi điều kiện giúp đỡ tôi hoàn thành luận văn này. Tôi xin chân thành cảm ơn Ban chủ nhiệm Khoa Sau đại học, Ban chủ nhiệm Khoa Toán – Trường ĐH Sư phạm – ĐH Thái Nguyên cùng các thầy giáo, cô giáo đã tham gia giảng dạy khoá học, xin chân thành cảm ơn gia đình, bạn bè, đồng nghiệp và các bạn cùng lớp cao học Toán K15 đã luôn quan tâm, động viên và giúp đỡ tôi trong suốt thời gian học tập và làm luận văn.
59 trang |
Chia sẻ: lvcdongnoi | Lượt xem: 2747 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Về điều kiện tối ưu cấp cao trong tối ưu không trơn, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
heo
tôpô yếu và tôpô mạnh trên S là trùng nhau.
Lấy
> 0. Do c
l
2
nên tồn tại số nguyên dƣơng k sao cho
i
i k
c
.
Nếu
'u
S mà
'iu
= 0 với i < k thì
, 'c u
. Do đó,
(1) 0( , )f x u
= 0, nếu S
là tôpô phản rời rạc.
Ví dụ trên đã đặt ra câu hỏi sau đây:
Với một hàm bất kỳ
:f E
có x
0
là cực tiểu chặt, có luôn tồn tại
hay không một tôpô S sao cho mặt cầu đơn vị S là compact theo tôpô S và x0
là điểm cực tiểu chặt đƣợc nhận biết theo định lý 1.2 ( xác định các đạo hàm
của f theo S )?
Câu trả lời là phủ định ở trong mục 1.4. Kết quả khẳng định rằng nếu x0
là điểm cực tiểu theo tôpô S nào đó thì nó cũng là điểm cực tiểu theo tôpô
phản rời rạc. Một cách chính xác hơn, ta thấy rằng định lý 1.2 chỉ đặc trƣng
cho điểm cực tiểu cô lập.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 13
Ví dụ 1.3
Lấy E = và
( )
m
f x x
với m là số nguyên không âm nào đó và
0 <
< 1.
Hiển nhiên x0 = 0 là điểm cực tiểu chặt.
Các đạo hàm Dini dƣới là
1)
( ) ( )(0,1) (0, 1)i if f
= 0, i = 0, ..., m .
2)
( 1) ( 1)(0,1) (0, 1)m mf f
.
Do đó, x0 = 0 là điểm cực tiểu địa phƣơng chặt cấp m + 1 theo điều kiện đủ
của định lý 1.2.
1.2. XẤP XỈ ĐA THỨC VÀ ĐIỀU KIỆN ĐỦ TỐI ƢU
Trong mục này, ta mô tả đạo hàm theo phƣơng dƣới của hàm
:f E
dƣới ngôn ngữ của phép xấp xỉ đa thức địa phƣơng và dẫn các
điều kiện tối ƣu. Ký hiệu Pn , n = 0, 1, ... là tập các đa thức một biến bậc n
hoặc nhỏ hơn.
Với hai đa thức
,
, ta viết
( ) ( ) ( )nt t o t
khi
0t
(1.2)
nếu với mỗi số
> 0, tồn tại
> 0 sao cho
( ) ( ) nt t t
với 0 < t <
.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 14
Định lý 1.3
Các đa thức
0
( )
n
i
i
i
t a t
và
0
( )
n
i
i
i
t b t
thoả mãn
( ) ( ) ( )nt t o t
khi
0t
, nếu ai = bi, i = 0,...,n ( hay
), hoặc tồn tại số nguyên dương
k sao cho ai = bi, i = 0,...,k – 1, và ak bk .
Chứng minh
Giả sử
và ai = bi, i = 0,...,k – 1.
Chia hai vế bất đẳng thức (1.2) cho tk và qua giới hạn khi
0t
, ta
đƣợc ak bk. Từ đó ta suy ra điều phải chứng minh.
Ta nói đa thức
là cận dưới bậc n của
:f E
tại x0 theo phƣơng
u
S nếu với mỗi
> 0, tồn tại
> 0 và lân cận U = U(u) của u trong S sao
cho
0( ) ( ') nt f x tu t với 0 < t < , 'u U.
Tính chất này còn đƣợc viết dƣới dạng
0( ) ( ') ( )nt f x tu o t khi ( , ') ( 0, )t u u .
Ta kí hiệu
0( , , )nP f x u
là tập các đa thức
nP
là cận dƣới của f tại x0
theo phƣơng u.
Một đa thức
0( , , )nP f x u
đƣợc gọi là cận dưới đúng của f tại x0 theo
phƣơng u nếu
( ) ( ) ( )nt t o t
khi
0t
với mỗi
0( , , )nP f x u
.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 15
Định lý 1.4 ( [5] )
Đạo hàm dưới
( ) 0( , )nf x u
của hàm
:f E
tồn tại và là một phần tử
của khi và chỉ khi cận dưới đúng bậc n của f tại x0 theo phương u tồn tại
và khi đó cận này là đa thức Taylor dưới
0 ( ) 0
0
1
( , , , ) ( , )
!
n
n i i
i
T f x u t f x u t
i
.
Hàm
:f E
có đạo hàm dưới cấp n
( ) 0( , )nf x u
khi và chỉ khi cận
dưới đúng bậc n – 1 tồn tại ( và nó chính là đa thức Taylor dưới
1 0( , , , )nT f x u t
). Trong trường hợp đó ta có
, nếu
0( , , )nP f x u
rỗng,
, nếu
0( , , )nP f x u
khác rỗng,
nhưng f không có cận dưới đúng bậc n.
Sử dụng định lý 1.4, các điều kiện cần và đủ tối ƣu của mục 1.1 có thể
đƣợc biểu diễn dƣới ngôn ngữ của phép xấp xỉ đa thức. Ở đây, ta chỉ phát
biểu lại điều kiện đủ tối ƣu của định lý 1.2.
Định lý 1.5
Cho hàm
:f E
và 0x E . Giả sử S là tập compact đối với tôpô S.
Giả sử với mỗi u
S, tồn tại số nguyên không âm n = n(u) và cận dưới bậc n
0
( )
n
i
i
i
t a t
của f tại x0 theo phương u thoả mãn
0( ) , 0,
0 , 1,
i
f x i
a
i
( ) 0( , ) nf x u
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 16
và bất đẳng thức tương ứng với i = n là chặt. Khi đó, x0 là điểm cực tiểu địa
phương chặt của f.
Chứng minh
Trƣớc hết giả sử tất cả các đạo hàm dƣới
( ) 0( , )if x u
, i = 0,...,n tồn tại
và hữu hạn. Do đó,
0( ) ( , , , ) ( )n nt T f x u t o t
khi
0t
,
trong đó
0( , , , )n nT T f x u t
là đa thức Taylor dƣới duy nhất cấp n.
So sánh hệ số của
và
nT
ta thấy điều kiện
0( , )nS x u
đƣợc thoả
mãn.
Giả sử
( ) 0( , )kf x u
vô hạn với k nào đó. Đa thức
là một cận dƣới bậc
k – 1 và so sánh hệ số của nó với hệ số của đa thức Taylor dƣới cấp k – 1, ta
sẽ thu đƣợc điều kiện cần
0i ( , )N x u
, i = 0,..., k – 1.
Nếu một bất đẳng thức chặt nào đó trong số các điều kiện này đúng và
m là chỉ số i đầu tiên thoả mãn tính chất này thì điều kiện này thực chất chính
là
0( , )mS x u
.
Nếu không có bất đẳng thức chặt nào trong số các điều kiện này xuất
hiện thì
( ) 0( , )kf x u
và
0( , )kS x u
đúng.
Với mỗi trƣờng hợp đƣa ra, điều kiện đủ của định lý 1.2. đều thoả mãn.
Do đó, x0 là điểm cực tiểu địa phƣơng chặt.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 17
Ví dụ 1.4
Lấy E = và
( )
m
f x x
với m là số nguyên không âm nào đó và
0 <
1 ( so sánh với ví dụ 1.3.). Khi đó, đa thức
11( )
2
mt t
hiển nhiên là cận dƣới bậc m + 1 của f tại x0 = 0 theo cả hai phƣơng u = 1 và
u = – 1. Vậy
thoả mãn điều kiện đủ của định lý 1.5, do đó x0 = 0 là điểm
cực tiểu địa phƣơng chặt của f .
Ví dụ 1.5
Cho hàm
:f
xác định nhƣ sau
f (x) =
211 sin , 0,
0 , 0.
x x khi x
x
khi x
Hiển nhiên, x0 = 0 là điểm cực tiểu chặt nếu
> 0 ( không là cực tiểu
chặt nếu
= 0 ) và x
0
không là cực tiểu nếu
< 0.
Nếu
> 0 thì điểm cực tiểu chặt x0 = 0 có thể tìm đƣợc bằng cách áp
dụng định lý 1.5 khi lấy phƣơng u = 1, u = – 1 và đa thức
21( )
2
t t
.
Trƣờng hợp
< 0, ta có x
0
không phải là điểm cực tiểu.
Tiếp theo ta chỉ ra rằng đạo hàm theo phƣơng cấp cao có thể biểu diễn
dƣới ngôn ngữ hiệu chia.
Giả sử
:f E
. Ta nhắc lại: miền hữu hiệu của hàm f là tập
: ( ) dom f x E f x
.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 18
Lấy 0x E và u0, ..., un S là các phƣơng cho trƣớc. Giả sử t0, ..., tn là
các biến thực dƣơng khác nhau và
0' ,..., ' Snu u
là các biến phƣơng.
Ta định nghĩa hiệu chia cấp n
0
0 0( , ' ,..., ' , ,..., )
n n
n nf f x u u t t
nhƣ
sau:
0
0
0 0
0
1
( ' )
( , ' ,..., ' , ,..., )
( )
n
n i i
n n
i
n i
f x t u
f x u u t t
t
=
0
0
0
( ' )
( )
n
i i
n
i
i j
j
j i
f x t u
t t
Ở đây
1
0
( ) ( )
n
n j
j
t t t
và
1( )n t
là đạo hàm của
1( )n t
. Hơn nữa, ta đặt
0( ) 1t
.
Ta thừa nhận rằng : hiệu chia cấp n xác định khi và chỉ khi
0 ' i ix t u dom f
trừ ra nhiều nhất một số hạng. Nó hữu hạn khi và chỉ khi tất
cả các giá trị
0( ' )i if x t u
là hữu hạn.
Hiệu chia còn có thể đƣợc định nghĩa quy nạp nhƣ sau
0 0 0
0 0 0 0( , ' , ) ( ' )f x u t f x t u
,
và
0
0 0( , ' ,..., ' , ,..., )
n
n nf x u u t t
=
1 0 ' ' '0 2 0 2( , ,..., , , ,..., , )n n n n nf x u u u t t t
1 0 ' ' '0 2 1 0 2 1( , ,..., , , ,..., , )n n n n nf x u u u t t t 1n nt t
( Nếu
nằm trong số các giá trị của hàm f thì các chỉ số cần phải sắp xếp
lại).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 19
Tính chất sau đây là một trong số các tính chất chính của hiệu chia và
đƣợc sử dụng khi chứng minh biểu diễn lại đạo hàm theo phƣơng qua hiệu
chia.
0( ')f x tu
= 1
0
0 0
1
( , ' ,..., ' , ' ,..., ' ) ( )
n
i
i i i
i
f x u u t t t
+
0
0 1 0 1( , ' ,..., ' , ', ' ,..., ' , ) ( )
n
n n nf x u u u t t t t .
Ta giả thiết rằng
0 ' i ix t u dom f
, i = 0, ..., n – 1 và do đó cùng lắm
thì
0( ')f x tu
và hiệu chia cuối cùng trong vế phải có thể nhận giá trị vô hạn.
Mối quan hệ giữa đạo hàm theo phƣơng và hiệu chia đƣợc chỉ ra trong
định lý sau đây.
Định lý 1.6 ( [5] )
Đạo hàm theo phương
( ) 0( , )nf x u
, n = 0, 1,..., được biểu diễn quy nạp
dưới ngôn ngữ hiệu chia cùng với dãy các số A0, ..., An như sau
A0 : =
0 0
( , ') ( 0, )
( , ', )
t u u
lim inf f x u t
=
(0) 0( , )f x u
.
Đạo hàm
( ) 0( , )nf x u
, n
1, tồn tại khi và chỉ khi các số A0,..., An-1 xác
định và hữu hạn. Khi đó,
An :=
0
0 1 0 1
( , ') ( 0, )
( , ,..., , ', ,..., , )k s s s sn n
st u u
lim inf lim f x u u u t t t
= 1
!n
( ) 0( , )nf x u
,
trong đó
0 1 0 1( ,..., , ,..., )
s s s s
n nu u t t
là dãy tuỳ ý thoả mãn ba điều kiện sau:
1)
0sit
,
s
iu u
khi
s
, với i = 0, ..., n – 1,
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 20
2)
0 s si ix t u dom f
với i = 0, 1, ..., n – 1,
3) Ai =
0
0 0 ( , ,..., , ,..., )
i s s s s
i i
s
lim f x u u t t
với i = 0, 1, ..., n – 1.
1.3. ĐIỀU KIỆN TỐI ƢU CẤP HAI
Đạo hàm cấp một
(1) 0( , )f x u
của hàm
:f E
có thể biểu diễn nhƣ
sau
(1) 0( , )f x u
=
1
0 (0) 0
1
( , ' ) ( 0, )
1
( ' ) ( , )
u u
lim inf f x tu f x u
t
. (1.3)
Để tiện cho việc khai triển đạo hàm cấp hai, ta đƣa ra ký hiệu
0
2 1( , , , ' , ' , )f t x u u u
=
0
2
1
( ' )
1
f x tu
–
0
1
1
( ' )
(1 )
f x tu
+
(0) 01 ( , )f x u
. (1.4)
Ta xét khai triển dƣới đây với giả thiết rằng t > 0 là cố định, u
S, đạo
hàm dƣới cấp không
(0) 0( , )f x u
và đạo hàm dƣới cấp một
(1) 0( , )f x u
là hữu
hạn,
' '
1 2, Su u
và
là số thực dƣơng thoả mãn
0 '
1 x tu dom f
.
Với giả thiết
(0) 0( , )f x u
và
(1) 0( , )f x u
hữu hạn, ta nhận đƣợc biểu diễn
sau đây cho đạo hàm dƣới cấp hai
(2) 0( , )f x u
:
(2) 0( , )f x u
=
2
0 (0) 0 (1) 0
22
( , ' ) ( 0, )
2!
( ' ) ( , ) . ( , )
t u u
lim inf f x tu f x u t f x u
t
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 21
=
2
0 (0) 0
22
( , ' ) ( 0, )
2!
( ' ) ( , )
t u u
lim inf f x tu f x u
t
1
0 (0) 0
1
( , ' ) ( 0, )
1
( ' ) ( , )
u u
t lim inf f x tu f x u
t
=
2 1
0
22
( , ' ) ( 0, ) ( , ' ) ( 0, )
2(1 ) 1
( ' )
1t u u u u
lim inf lim sup f x tu
t
0 (0) 0
1
1 1
( ' ) ( , )
(1 )
f x tu f x u
=
2 1
0
2 12
( , ' ) ( 0, ) ( , ' ) ( 0, )
2
( , , , ' , ' , )f
t u u u u
lim inf lim sup t x u u u
t
. (1.5)
Trong các đẳng thức trên, sự hội tụ
1( , ' ) ( 0, )u u
chỉ theo những
giá trị
1( , ' )u
mà
0
1' x tu dom f
.
Để đơn giản, ta xét trƣờng hợp hàm f liên tục tại x0 . Khi đó ta có
(0) 0 0( , ) ( )f x u f x
và
2 0
0 1 2( , ' , ' , ' ,0, , )f x u u u t t
=
0
22
1 1
( ' )
1
f x tu
t
0 (0) 0
1
1 1
( ' ) ( , )
(1 )
f x tu f x u
.
Sử dụng phép biểu diễn này và định lý 1.6, ta có thể thu đƣợc sự biểu diễn
(1.5). Từ các định lý 1.1, 1.2 ta có định lý sau cho trƣờng hợp cấp hai.
Định lý 1.7 ( Điều kiện cấp hai )
Cho hàm
:f E
và 0 Ex .
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 22
(A) Điều kiện cần: Giả sử x0 là điểm cực tiểu địa phương của f, u
S.
Khi đó, một trong ba điều kiện sau đây được thoả mãn:
(a0) (0) 0 0( , ) ( )f x u f x ,
(a1) Nếu (0) 0 0( , ) ( )f x u f x thì (1) 0( , ) 0f x u ,
(a2) Nếu (0) 0 0( , ) ( )f x u f x và (1) 0( , ) 0f x u thì (2) 0( , ) 0f x u .
(B) Điều kiện đủ:Giả sử S compact đối với tôpô S. Giả sử với mỗi u
S,
một trong ba điều kiện sau được thoả mãn:
(b0) (0) 0 0( , ) ( )f x u f x ,
(b1) (0) 0 0( , ) ( )f x u f x và (1) 0( , ) 0f x u ,
(b2) (0) 0 0( , ) ( )f x u f x , (1) 0( , ) 0f x u và (2) 0( , ) 0f x u .
Khi đó x0 là điểm cực tiểu địa phương chặt của f.
Ở đây đạo hàm
(1) 0( , )f x u
và
(2) 0( , )f x u
được biểu diễn lần lượt bởi
(1.3) và (1.5).
Ví dụ 1.6
Lấy E = 2 và hàm
:f E
xác định bởi
2( ) 2 ( )f x r r r sin
,
trong đó
( , )r
là toạ độ cực của x , nghĩa là x = (x1, x2) =
( , )rcos rsin
.
Hiển nhiên x0 = (0,0) là điểm cực tiểu chặt của f(x). Ta có thể áp dụng
điều kiện đủ của định lý 1.7 để suy ra x0 là cực tiểu.
Chứng minh
Hàm f liên tục, do đó với phƣơng bất kỳ u =
( , )cos sin
ta có
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 23
(0) 0 0( , ) ( )f x u f x
= 0.
Nếu
0sin
thì
2( ) 2f x r r sin
,
0 r sin
,
và
(1) 0( , ) 2f x u sin
> 0.
Trong trƣờng hợp nếu u =
( 1, 0)
ta đƣợc
(1) 0( , ) 0f x u
và do đó
điều kiện cấp hai phải sử dụng để thiết lập tính tối ƣu của x0.
Xét trƣờng hợp u = (1, 0). Phƣơng đơn vị v =
( , )cos sin
với
0
đủ nhỏ gần u tuỳ ý. Các điểm tv và
tv
có toạ độ cực lần lƣợt là
( , )t
và
( , )t
. Do đó với
0 t sin
và
0 1
ta có
0 2( ) 2f x tv t tsin ,
và
0 2( ) ( ) 2f x tv t tsin .
Do đó
0
2
1
( , , , , , ) 1f t x v v u
t
.
Bây giờ ta chỉ ra rằng điều kiện cấp hai trong định lý 1.7 thoả mãn. Với
u = (1, 0) , ta lấy lân cận của các vectơ đơn vị
W =
w w w 2 = ( , ) :w cos sin
,
V =
v v v 1 = ( , ) :v cos sin
, trong đó
1 20
.
Chọn t <
2sin
và lấy 0 <
< 1. Nếu v
V , ta có
0( )f x tv
= 2 2 1
2 2
2 . , ( ) ,
3 2 . , 0 ( ),
v v
v v
t t sin arcsin t
t t sin arcsin t
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 24
và
0( )f x tv 2 2t
. Dấu bằng xảy ra khi
( )v arcsin t
.
Khi đó,
0
2
( , ) ( 0, )
2
( , , , , , )f
v u
lim sup t x w v u
t
=
0
2
( , ) ( 0, )
2 2
( )
(1 ) 1v u
lim sup f x tw
t
=
0
2
2
( )f x tw
t
.
Tƣơng tự, với w
W ,
0( )f x w
= 2 w w 2
2
w w
2 , ( ) ,
3 2 , 0 ( ),
t tsin arcsin t
t tsin arcsin t
và ƣớc lƣợng
0( )f x tw
2t
. Dấu bằng xảy ra khi
w ( )arcsin t
.
Do đó,
(2) 0( , )f x u
=
0
2
( , ) ( 0, )
2
( )
t w u
lim inf f x tw
t
= 2 > 0.
Do tính đối xứng nên ta cũng có đẳng thức nhƣ vậy với phƣơng
u = ( –1, 0 ). Do đó, các điều kiện đủ của định lý 1.7 thoả mãn. Nhƣ vậy, tính
tối ƣu của điểm x0 có thể suy ra từ định lý này.
Ta so sánh kết quả trên với một số kết quả khác.
Giả sử
:f E
với E là không gian hữu hạn chiều, f liên tục và tại
x
0
có các đạo hàm sau:
(1) 0( , )BZf x v
=
0 0
0
1
( ) ( )
t
lim f x tv f x
t
,
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 25
(2) 0( , , )BZf x v z
=
0 2 0 (1) 0
2
0
1
( ) ( ) ( , )BZ
t
lim f x tv t z f x tf x v
t
,
với v, z
S tuỳ ý. Đạo hàm
(1) 0( , )BZf x v
là đạo hàm theo phƣơng thông thƣờng
cấp một,
(2) 0( , , )BZf x v z
là đạo hàm parabolic cấp hai theo nghĩa BenTal –
Zowe [3].
Định lý sau đây cho ta các điều kiện cần dƣới ngôn ngữ các đạo hàm
parabolic.
Định lý 1.8 ( [3] )
Nếu x0 là điểm cực tiểu địa phương của hàm
:f E
thì
(BZ1) (1) 0( , ) 0BZf x v với mọi v S,
(BZ2) (1) 0( , ) 0BZf x v kéo theo (2) 0( , , ) 0BZf x v z với mọi z S.
Ta chỉ ra rằng với lớp các hàm đã xét, định lý 1.7 kéo theo định lý 1.8.
Thật vậy, giả sử các điều kiện trong định lý 1.7 thoả mãn.
Hiển nhiên ta có bất đẳng thức
(1) 0 (1) 0( , ) ( , ) 0BZf x v f x v
Nhƣ vậy điều kiện (BZ1) thoả mãn.
Bây giờ ta giả sử
(1) 0( , ) 0BZf x v
. Từ các bất đẳng thức
(1) 0 (1) 00 ( , ) ( , ) 0BZf x v f x v
ta suy ra
(1) 0( , ) 0f x v
. Do đó
(2) 0( , ) 0f x v
.
Theo định nghĩa của
(2) 0( , , )BZf x v z
,
(2) 0( , , )BZf x v z
=
0 0
2
0
1
( ( )) ( )
t
lim f x t v tz f x
t
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 26
0 (0) 0 (1) 0
2
( , ') ( 0, )
1 2
( ( )) ( , ) . ( , )
2 t v v
lim inf f x t v tz f x v t f x v
t
=
(2) 01 ( , )
2
f x v
.
Do đó, bất đẳng thức
(2) 0( , ) 0f x v
kéo theo
(2) 0( , , ) 0BZf x v z
, hay
điều kiện (BZ2) thoả mãn.
Ví dụ sau đây chỉ ra rằng các điều kiện cần (BZ1) và (BZ2) của định lý
1.8 không kéo theo các điều kiện cần (a0) – (a2) của định lý 1.7.
Ví dụ 1.7
Hàm
2:f
xác định bởi
f (x1, x2) =
3 3 3
2 1 1 1 2 1
3 3 3
1 2 1 1 2 1
1
2 , 0, ,
2
3
3 2 , 0, ,
2
0
x x x x x x
x x x x x x
Hiển nhiên, x0 = (0, 0) không là điểm cực tiểu.
Ta có
(1) 0 (2) 0( , ) ( , , ) 0BZ BZf x u f x u z
với mọi u
S, mọi z .
Với u0 = (1, 0) ta có
0 (1) 0 00 ( ) ( , )f x f x u
và
(2) 0 0( , ) f x u
Nhƣ vậy các điều kiện cần (BZ1) và (BZ2) của định lý 1.8 không kéo theo các
điều kiện cần (a0) – (a2) của định lý 1.7.
, trong các trƣờng hợp khác.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 27
1.4. CỰC TIỂU CÔ LẬP
Trong mục này, ta mô tả điểm cực tiểu thoả mãn các điều kiện đủ của
định lý 1.2 và trả lời câu hỏi đã đặt ra sau ví dụ 1.2.
Giả sử
:f E
và n0 là một số nguyên không âm.
Nhắc lại [10]: điểm cực tiểu x0
E của f gọi là cực tiểu địa phương cô
lập cấp n0 của f nếu tồn tại lân cận U của x
0
và hằng số
> 0 sao cho
00 0( ) ( )
n
f x f x x x
với mọi x
U 0x
. (1.6)
Ta nói x
0
là điểm cực tiểu địa phương cô lập của f có nghĩa là x0 là
điểm cực tiểu địa phƣơng cô lập cấp n0 của f với n0 là một số nguyên không
âm nào đó.
Trong trƣờng hợp n0 = 0, bất đẳng thức (1.6) trở thành
0( ) ( )f x f x
với mọi x
U 0x
. (1.7)
Do bất đẳng thức (1.6) là chặt nên
0( ) f x
tại điểm cực tiểu địa
phƣơng cô lập x0.
Định lý 1.9 ( Điều kiện cần )
Giả sử x0 là điểm cực tiểu địa phương cô lập cấp n0 của hàm
:f E
. Khi đó, với u
S bất kỳ, tồn tại số nguyên không âm n(u)
n0
sao cho điều kiện
0( ) ( , )n uS x u
thoả mãn.
Chứng minh
Giả sử có (1.6). Trƣớc hết ta chỉ ra rằng
(0) 0 0( , ) ( )f x u f x
,
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 28
và bất đẳng thức là chặt nếu x0 là điểm cực tiểu cô lập cấp 0.
Giả sử ngƣợc lại rằng
(0) 0 0( , ) ( )f x u f x
.
Theo định nghĩa đạo hàm dƣới cấp không thì tồn tại dãy
0kt
và
ku
S sao cho
0 0( ) ( ) ( )kk kf x t u f x f x
,trong đó
0 0k
k kx t u x
.
Bất đẳng thức này mâu thuẫn với bất đẳng thức (1.6).
Giả sử x0 là điểm cực tiểu địa phƣơng cô lập cấp 0. Bây giờ ta chứng
minh rằng
(0) 0 0 0( , ) ( ) ( )f x u f x f x .
Giả sử bất đẳng thức này không đúng. Khi đó tồn tại dãy
0kt
và
ku
S sao cho
0 0( ) ( ) ( )kk kf x t u f x f x , trong đó 0 0k k kx x t u x .
Bất đẳng thức này mâu thuẫn với bất đẳng thức (1.7).
Giả sử n
n0 là số nguyên dƣơng thoả mãn
(0) 0 0( , ) ( )f x u f x
,
(1) 0 ( 1) 0( , ) ... ( , ) 0nf x u f x u
.
Ta chứng minh rằng
( ) 0( , ) 0nf x u
và bất đẳng thức là chặt nếu x0 là
điểm cực tiểu địa phƣơng cô lập cấp n.
Giả sử ngƣợc lại rằng
( ) 0( , ) 0nf x u
. Theo định nghĩa đạo hàm theo
phƣơng dƣới cấp n thì tồn tại dãy
0kt
và
ku
S sao cho
1
0 ( ) 0
0
!
( ) ( , )
!
in
i
k kn
ik
n t
f x t u f x u
t i
=
0
0
!
( ) ( )k
n
k
n
f x f x
x x
< 0 ,
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 29
trong đó
0 0k
k kx x t u x
. Bất đẳng thức này mâu thuẫn với bất đẳng thức
(1.6).
Giả sử n = n0. Ta chứng minh rằng
( ) 0( , ) ! 0nf x u n
Giả sử ngƣợc lại rằng
( ) 0( , ) !nf x u n
. Khi đó, với dãy
0kt
và
ku
S,
tƣơng tự nhƣ trên ta có
0
0
!
( ) ( )k
n
k
n
f x f x
x x
<
!n
.
Từ đó suy ra
0 0( ) ( )
n
k kf x f x x x
với
0 0k
k kx x t u x
.
Bất đẳng thức này mâu thuẫn với bất đẳng thức (1.6).
Điều kiện đủ để điểm x0 là điểm cực tiểu cô lập cấp n0 đƣợc phát biểu
nhƣ sau:
Định lý 1.10 ( Điều kiện đủ )
Giả sử hàm
:f E
, x
0
E và S compact đối với tôpô S. Giả sử n0 là
một số nguyên không âm và với mỗi u
S, tồn tại số nguyên không âm
n = n(u)
n0 sao cho điều kiện
0nS ( , )x u
thoả mãn. Khi đó, x0 là điểm cực
tiểu địa phương cô lập cấp n0 của f.
Chứng minh
Bất đẳng thức cuối cùng trong phần chứng minh của bổ đề 1.1 chỉ ra
rằng tồn tại số
( )u
sao cho
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 30
0 0( ') ( ) ( ) nf x tu f x u t , với mọi 0 < t < ( )u và 'u U(u).
Sử dụng u1, ..., us và các ký hiệu sau đây nhƣ trong chứng minh định lý
1.2.
Đặt
0 1( ),..., ( ),1smin u u
,
1( ),..., ( )smin u u
,
1( ),..., ( )sn max n u n u
.
Khi đó nhƣ trong chứng minh định lý 1.2 ta đƣợc
0 0( ) ( )
n
f x f x x x
với mọi 0 <
0x x
<
0
.
Do đó x0 là điểm cực tiểu địa phƣơng cô lập cấp n, và vì thế cũng là điểm cực
tiểu địa phƣơng cô lập cấp n0 vì n n0.
Ví dụ 1.8
Lấy E = 2 , C =
0
, n0 1 là số nguyên và x
0
= (0, 0).
Hàm
:f E
xác định bởi
f (x1, x2) = 01 2
2
, 0,
0 , 0.
n
x x
x
Khi đó, x0 là điểm cực tiểu địa phƣơng cô lập cấp n0 của bài toán
( ), Cmin f x x
Chứng minh
Đặt g(x1, x2) = 01 2
2
, 0,
+ , 0.
n
x x
x
Hàm g khác hàm f tại những điểm không thuộc C, tại đó g bằng
+
.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 31
Ta nói rằng x0 là điểm cực tiểu địa phƣơng cô lập cấp n0 của bài toán
( ), Cmin f x x
nếu x0 là điểm cực tiểu địa phƣơng cô lập cấp n0 của hàm g.
Ta có
(0) 0( , ) g x u
, với ( u1, u2) S mà u2 0 .
Nếu u = (
1
, 0) thì ta có
0( 1)(0) 0 0( , ) ... ( , ) 0
n
g x u g x u
,
0( ) 0
0( , ) ( )!
n
g x u n
.
Do đó điều kiện đủ của định lý 1.10 cho ta x0 là điểm cực tiểu địa
phƣơng cô lập cấp n0.
Ví dụ 1.9
Xét hàm
2:f
xác định bởi f ( x1, x2) = x1.
Lấy x0 = (0, 0) và u = (
1, 0). Khi đó đạo hàm cấp hai Hadamard là
(2) 0( , ) f x u
còn đạo hàm cấp hai theo phƣơng cổ điển là
0''( , ) 0f x u
.
Chứng minh
Đạo hàm cấp hai Hadamard là
(2) 0( , )f x u
=
0 (0) 0 (1) 0
2
( , ') ( 0, )
2
( ') ( , ) ( , )
t u u
lim inf f x tu f x u t f x u
t
=
(0)12
( , ') ( 0, ) ( ', ') ( 0, )
2 1
' 0 (0 ') (0, )
't u u t u u
lim inf u t lim inf f tu f u
t t
=
12
( , ') ( 0, )
2
'
t u u
lim inf u t
t
=
Với đạo hàm theo phƣơng cổ điển ta có
0'( , )f x u
= 0 0
0
( ) ( )
t
f x tu f x
lim
t
1 2( , )u u u
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 32
=
1
0
0
t
tu
lim
t
=
1u
0''( , )f x u
= 0 0 0
2
0
( ) ( ) '( , )
2
t
f x tu f x t f x u
lim
t
=
1 1
2
0
0
2
t
tu tu
lim
t
= 0
Ví dụ 1.10
Hàm
:f
xác định bởi
f (x) = 2
1
( ), 0,
0 , 0.
exp x
x
x
Ta có f thuộc lớp
C
. Điểm x0 = 0 là cực tiểu địa phƣơng chặt, nhƣng không
là điểm cực tiểu địa phƣơng cô lập.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 33
Chƣơng II
ĐIỀU KIỆN TỐI ƢU CẤP CAO CHO BÀI TOÁN TỐI ƢU ĐA
MỤC TIÊU KHÔNG TRƠN CÓ RÀNG BUỘC TẬP
Chƣơng II trình bày một số tính chất của cực tiểu Pareto địa phƣơng
chặt cấp n và cực tiểu Pareto địa phƣơng chặt, và các điều kiện cần và đủ cho
hai loại cực tiểu đó của bài toán tối ƣu đa mục tiêu không trơn với ràng buộc
tập dƣới ngôn ngữ đạo hàm theo phƣơng cấp cao Ginchev. Các kết quả trình
bày trong chƣơng này là của Đ.V.Lƣu – P.T.Kiên [7] và B.Jiménez [6].
2.1. CÁC KHÁI NIỆM VÀ KẾT QUẢ BỔ TRỢ
Cho hàm f có giá trị thực mở rộng xác định trên không gian định
chuẩn X.
Nhắc lại [5]: đạo hàm theo phương dưới và trên cấp n,
( ) ( , )nf x d
và
( ) ( , )nf x d
, tại
x X
( n là số nguyên dƣơng ) theo phƣơng d đƣợc định nghĩa
lần lƣợt nhƣ sau:
(0) ( , )f x d
=
0
'
( ')
t
d d
lim inf f x td
, (2.1)
(0) ( , )f x d
=
0
'
( ')
t
d d
lim sup f x td
, (2.2)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 34
( ) ( , )nf x d
= 1
( )
0
0'
!
( ') ( , )
!
jn
j
n
t
jd d
n t
lim inf f x td f x d
t j
, (2.3)
( ) ( , )nf x d
= 1
( )
0
0'
!
( ') ( , )
!
jn
j
n
t
jd d
n t
lim sup f x td f x d
t j
, (2.4)
trong đó
0t
có nghĩa là
0t
.
Chú ý rằng trong các định nghĩa (2.1) – (2.4) của I.Ginchev đã thừa
nhận rằng
( ) ( , )nf x d
và
( ) ( , )nf x d
tồn tại và thuộc khi và chỉ khi tƣơng
ứng
( ) ( , )if x d
và
( ) ( , )if x d
( i = 0, 1,..., n – 1) tồn tại và thuộc .
Hơn nữa, đạo hàm cấp không của các hàm gián đoạn luôn tồn tại và
thuộc .
Trong trƣờng hợp f liên tục và n = 1, đạo hàm Ginchev trên và dƣới
chính là đạo hàm Dini theo phƣơng trên và dƣới [5].
Phù hợp với định nghĩa đạo hàm của Ginchev [5], ta định nghĩa đạo
hàm theo phương cấp n của ánh xạ f từ X vào không gian định chuẩn Y nhƣ
sau:
(0) ( , )f x d
=
0
'
( ')
t
d d
lim f x td
, (2.5)
( ) ( , )nf x d
= 1
( )
0
0'
!
( ') ( , )
!
jn
j
n
t
jd d
n t
lim f x td f x d
t j
, (2.6)
nếu các giới hạn đó tồn tại.
Nếu f khả vi Fréchet tại
x
với đạo hàm Fréchet là
'( )f x
thì
(1)( , )f x d
=
'( )f x d
.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 35
Trong trƣờng hợp Y = , sự tồn tại của
( ) ( , )nf x d
kéo theo sự tồn tại
của
( ) ( , )nf x d
và
( ) ( , )nf x d
, và chúng trùng nhau.
Ta nhắc lại nón tiếp liên của tập C tại
x clC
:
KC( x ) = {d X : tồn tại 0nt và nd d sao cho n nx t d C , n },
ở đây
clC
chỉ bao đóng của C.
Trong chƣơng này ta xét bài toán tối ƣu đa mục tiêu sau:
(P)
( ) :min f x x C
,
trong đó f là ánh xạ từ không gian định chuẩn X vào không gian định chuẩn
Y, C là một tập con của X .
Giả sử Q là nón lồi đóng trong Y. Nhắc lại: điểm
x C
gọi là điểm cực
tiểu địa phương yếu của bài toán (P) nếu tồn tại một lân cận U của
x
sao cho
( ) ( )f x f x intQ
x C U
Chú ý rằng với điểm cực tiểu địa phƣơng yếu, ta giả thiết rằng
intQ
.
Điểm
x
gọi là điểm cực tiểu Pareto địa phương của bài toán (P) nếu
tồn tại một lân cận U của
x
sao cho
( ) ( )f x f x Q {0}
x C U
.
Điểm
x
gọi là điểm cực tiểu Pareto địa phương chặt của bài toán (P)
nếu tồn tại một lân cận U của
x
sao cho
( ) ( )f x f x Q
x C U { }x
.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 36
Với một số nguyên m
1, ta nhắc lại [6] rằng
x
gọi là điểm cực tiểu
Pareto địa phƣơng chặt cấp m của bài toán (P) nếu tồn tại hằng số
> 0 và
lân cận U của
x
sao cho
( ) ( ), mf x Q B f x x x
x C U { }x
, (2.7)
trong đó
( , )B x
là hình cầu mở bán kính
, tâm
x
. Chú ý rằng hình cầu mở
( ), mB f x x x
trong (2.7) có thể đƣợc thay bằng hình cầu đóng
( ), mB f x x x
bán kính m
x x
, tâm
( )f x
, bởi vì với
1 (0, )
,
(2.7) kéo theo
1( ) ( ), mf x Q B f x x x
x C U { }x
.
Trƣờng hợp Y = và Q =
, (2.7) trở thành
( ) ( ), mf x B f x x x
x C U { }x
.
Điều đó tƣơng đƣơng với
( ) ( )
m
f x f x x x
x C U { }x
,
trong đó
là tập các số thực không âm. Điều này có nghĩa là
x
là cực tiểu
địa phƣơng chặt cấp m.
Chú ý rằng mọi điểm cực tiểu Pareto địa phƣơng chặt cấp m cũng là
điểm cực tiểu Pareto địa phƣơng chặt cấp k với mọi k
m. Với mỗi số
nguyên m
1, ta có mối quan hệ sau [6]:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 37
Cực tiểu Pareto địa phƣơng chặt cấp m
Cực tiểu Pareto địa phƣơng
chặt
Cực tiểu Pareto địa phƣơng
Cực tiểu địa phƣơng yếu.
Bây giờ, ta trình bày hai kết quả của B.Jiménez [6].
Mệnh đề 2.1
Giả sử
x C
. Điểm
x
không là điểm cực tiểu Pareto địa phương chặt
cấp m của bài toán (P) khi và chỉ khi tồn tại dãy
nx C { }x
,
nd Q
sao cho
nx x
và
( ) ( )
0n n
m
n
n
f x f x d
lim
x x
. (2.8)
Chứng minh
Bởi vì
nx x
và (2.8) đúng cho nên
0 00, ( )n n
sao cho
0n n
, ta có
,n nx C x x
và
( ) ( )
m
n n nf x f x d x x
.
Điều này có nghĩa là
( ) ( ), mn n nf x d B f x x x
.
Nếu nhƣ
x
là cực tiểu Pareto địa phƣơng chặt cấp m của bài toán (P)
thì tồn tại
,U B x
và
0
sao cho (2.7) đúng. Với
,min
, tồn
tại
0 0( )n n
sao cho với mỗi
0n n
ta có
,nx C B x
và
( ) ( ), ( ),m mn n n nf x d B f x x x B f x x x .
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 38
Điều này lại mâu thuẫn với (2.7). Vì vậy,
x
không là cực tiểu Pareto địa
phƣơng chặt cấp m của bài toán (P).
Theo giả thiết, với
0
và
0
,
,x C B x x
sao cho
( ) ( ), mf x Q B f x x x
.
Do đó, với 1
n
, 1
n
, tồn tại 1
,nx C B x
n
x
và
nd D
sao cho
1
( ) ( ),
m
n n nf x d B f x x x
n
.
Điều này có nghĩa là
( ) ( ) 1n n
m
n
f x d f x
nx x
.
Từ đó ta suy ra điều phải chứng minh.
Mệnh đề 2.2
Giả sử
x C
,Y = r và Q =
r
. Khi đó,
a)
x
là cực tiểu Pareto địa phương chặt cấp m của bài toán (P) khi và
chỉ khi tồn tại
0
và lân cận U của
x
và nhiều nhất r tập Vi , i I { 1, ...,r
} sao cho {Vi : i I } là một phủ của
C U { }x
và thoả mãn
( ) ( )
m
i if x f x x x
ix C x
, (2.9)
trong đó
i iC C U V x
.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 39
b)
x
là cực tiểu Pareto địa phương chặt của bài toán (P) khi và chỉ khi
tồn tại một lân cận U của
x
và nhiều nhất r tập Vi , i I { 1, ...,r } sao cho
{Vi : i I } là một phủ của
C U { }x
và thoả mãn
( ) ( )i if x f x
với mọi
ix C { }x
,
trong đó
{ }i iC C U V x
.
Chứng minh
a) Giả sử
x
là cực tiểu Pareto địa phƣơng chặt cấp m. Khi đó, tồn tại
0
và lân cận U của
x
sao cho
( ) ( ), mrf x B f x x x
x C U x
(2.10)
Lấy
2 r
. Với mỗi i
{ 1, ...,r } , ta đặt
: ( ) ( ) mi i iV x f x f x x x
. (2.11)
Ta sẽ chứng minh rằng
C U
1
r
i
i
x V
(2.12)
Lấy
x C U x
và giả sử với mọi i
{ 1, ...,r } ,
( ) ( )
m
i if x f x x x
.
Vì vậy,
( ) ( )f x f x r e
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 40
trong đó e = ( 1, 1, ..., 1) r và m
r x x
. Do đó, tồn tại
rd Q
sao cho
1( ) ( ), ( ),f x d B f x r B f x r
, (2.13)
trong đó
1B
là hình cấu đóng sau
1 0 ,B y
=
0:y y y
=
0
1
: i i
i r
y max y y
.
Do đó, từ (2.13) ta suy ra
( ) ( ),rf x B f x r
Điều này mâu thuẫn với (2.10). Vì vậy từ (2.11) ta suy ra (2.12).
Từ (2.12) ta suy ra
C U
1
r
i
i
x C U V
.
Đặt
i iC C U V x
. Khi đó,
1
r
i
i
C U C
,
và (2.9) đúng với
thay cho
.
Ngƣợc lại, giả sử lân cận U của
x
và
0
thoả mãn giả thiết. Ta
chứng minh (2.10) đúng.
Giả sử ngƣợc lại tồn tại
x C U x
sao cho
( ) ( ),rf x B f x r
.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 41
Từ đó suy ra tồn tại
rd
sao cho
( ) ( )f x d f x r
.
Vì vậy,
( ) ( )f x f x r e
.
Do đó, với mọi i
{ 1, ...,r } ,
( ) ( )
m
i if x f x x x
.
Điều này mâu thuẫn với (2.9). Vì vậy (2.10) đúng.
b) Chứng minh tƣơng tự.
Với các điểm không là cực tiểu Pareto địa phƣơng chặt của (P), ta có
mệnh đề sau đây:
Mệnh đề 2.3
Giả sử
x C
. Giả sử
x
không là điểm cực tiểu Pareto địa phương chặt
của (P). Khi đó với mỗi số nguyên m
1, tồn tại dãy
nx C { }x
,
nd Q
sao
cho
nx x
và
( ) ( )
0n n
m
n
n
f x f x d
lim
x x
. (2.14)
Chứng minh
Giả sử
x
không là điểm cực tiểu Pareto địa phƣơng chặt của (P). Khi
đó với mỗi số nguyên m
1,
x
không là điểm cực tiểu Pareto địa phƣơng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 42
chặt cấp m của (P). Theo mệnh đề 2.1, tồn tại dãy
nx C { }x
,
nd Q
sao cho
có (2.14).
2.2. ĐIỀU KIỆN CẦN CẤP CAO CHO CỰC TIỂU ĐỊA PHƢƠNG YẾU
Định lý sau đây chỉ ra một điều kiện cần dƣới ngôn ngữ đạo hàm theo
phƣơng cấp cao của Ginchev cho điểm cực tiểu địa phƣơng yếu, và do đó nó
đúng cho cực tiểu Pareto địa phƣơng chặt.
Định lý 2.1
Giả sử
intQ
và
x
là điểm cực tiểu địa phương yếu của bài toán
(P). Giả sử rằng với mỗi d
KC( x ), tồn tại các đạo hàm theo phương
( ) ( , )jf x d
( j = 0,...,n ) xác định bởi (2.5) và (2.6). Khi đó, các điều kiện tối
ưu sau đây đúng:
(i)
(0)( , ) ( )f x d f x intQ
, với mọi d
KC(x ).
(ii) Nếu với d
KC( x ) ta có
(0)( , ) ( )f x d f x
,
( )( , ) 0jf x d
( j = 1,...,n – 1)
thì
( )( , )nf x d intQ
.
Chứng minh
Vì
x
là điểm cực tiểu địa phƣơng yếu của (P) nên tồn tại lân cận U của
x
sao cho
( ) ( )f x f x intQ
với
x C U
.
Điều này tƣơng đƣơng với
( ) ( ) (f x f x Y )intQ
với
x C U
.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 43
Với d
KC( x ), tồn tại dãy 0mt và md d sao cho m mx t d C với
mọi m. Do vậy với m đủ lớn,
( )m mx t d C U
. Vì vậy,
( ) ( ) (m mf x t d f x Y )intQ
(2.15)
Do tính đóng của
Y intQ
, ta có điều sau
(0)( ) ( ) ( , ) ( ) (m m
m
lim f x t d f x f x d f x Y
)intQ
.
Do đó,
(0)( , ) ( )f x d f x intQ
.
Nhƣ vậy (i) đƣợc chứng minh.
Để chứng minh (ii), theo giả thiết với d
KC(x ), đạo hàm theo phƣơng
( ) ( , )jf x d
( j = 0, 1, ..., n ) tồn tại.
Giả sử
(0)( , ) ( )f x d f x
,
( ) ( , )jf x d
= 0 ( j = 1,..., n – 1), ta có
( ) ( , )nf x d
= 1
( )
0
0'
!
( ') ( , )
!
jn
j
n
t
jd d
n t
lim f x td f x d
t j
= 1
(0) ( )
1
!
( ) ( , ) ( , )
!
jn
jm
m mn
m
jm
n t
lim f x t d f x d f x d
t j
= !
( ) ( )m mn
m
m
n
lim f x t d f x
t
Vì
Y intQ
đóng nên từ điều trên và (2.15) suy ra
( ) ( , )nf x d Y intQ
.
Điều này có nghĩa là
( )( , )nf x d intQ
. Kết luận (ii) đƣợc chứng minh.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 44
2.3. ĐIỀU KIỆN ĐỦ CẤP CAO CHO CỰC TIỂU PARETO ĐỊA PHƢƠNG
CHẶT
Trong mục này, ta sẽ thiết lập điều kiện đủ cấp cao cho điểm cực tiểu
Pareto địa phƣơng chặt cấp n của bài toán (P) trong trƣờng hợp hữu hạn
chiều.
Định lý 2.2
Giả sử
dim X
. Giả sử rằng tồn tại số nguyên dương n sao cho
với mọi d
( )CK x {0}
, các đạo hàm theo phương
( ) ( , )jf x d
( j = 0, 1, ..., n )
tồn tại và một trong các điều kiện (Ak) ( k = 1, ..., n ) thoả mãn:
(Ak) (0) ( , ) ( )f x d f x ,
( )( , ) 0jf x d
( j = 1,...,k – 1),
( ) ( , )kf x d Q
.
Khi đó,
x
là điểm cực tiểu Pareto địa phương chặt cấp n của (P).
Chứng minh
Giả sử ngƣợc lại,
x
không là điểm cực tiểu Pareto địa phƣơng chặt cấp
n của (P).
Khi đó theo mệnh đề 2.1, tồn tại dãy
mx C
,
mx x
,
mx x
và
mb Q
sao cho
( ) ( )
0m m
n
m
m
f x f x b
lim
x x
. (2.16)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 45
Đặt
m mt x x
,
m
m
m
x x
d
x x
.
Khi đó
.m m mx x t d
,
mx C
.
Vì
dim X
nên dãy
{ }md
hội tụ tới d với
1d
. Không mất tính
tổng quát, ta có thể giả sử rằng
md d
.
Vì vậy d
( )CK x {0}
.
Hơn nữa theo (2.16) ta có
( ) ( )
0m m m
n
m
m
f x t d f x b
lim
t
. (2.17)
Vì
0mt
khi
m
nên (2.17) kéo theo với k = 1, ..., n thì
( ) ( )
0m m m
k
m
m
f x t d f x b
lim
t
. (2.18)
Mặt khác, theo giả thiết (Ak), ta có
(0)( , ) ( )f x d f x
,
( )( , ) 0jf x d
( j = 1,..., k – 1).
Vì
( ) ( , )kf x d
tồn tại nên ta có
( ) ( , )kf x d
= 1
(0) ( )
1
!
( ) ( , ) ( , )
!
jk
jm
m mk
m
jm
k t
lim f x t d f x d f x d
t j
= !
( ) ( )m mk
m
m
k
lim f x t d f x
t
.
Theo giả thiết
( ) ( , )kf x d
tồn tại ( k = 1, ..., n ), do đó các giới hạn sau
tồn tại
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 46
( ) ( )m m
k
m
m
f x t d f x
lim
t
( k = 1, ..., n ) . (2.19)
Sự tồn tại các giới hạn (2.18) và (2.19) dẫn đến sự tồn tại các giới hạn
sau
m
k
m
m
b
lim
t
( k = 1, ..., n ).
Vì Q đóng,
mb Q
và
0kmt
nên với k = 1, ..., n,
m
k
m
m
b
lim Q
t
.
Điều này cùng (2.18) dẫn đến với k = 1, ..., n thì
( ) ( , )kf x d Q
. Nhƣng điều
đó mâu thuẫn với điều kiện (Ak).
Ví dụ 2.1
Lấy X = k , Y = 2 , Q =
2
, C = [0, 1]
k–1
[–1, 0],
x
= ( 0, ..., 0), trong đó
k
là orthant không âm trong k ,
[0, 1]
k–1
= [0, 1]
...
[0, 1] ( k – 1 lần ).
Cho hàm f xác định bởi
1
1 1
1
( ,..., ) ,
k
k k
k i
i
f x x x x
,
trong đó k là số nguyên dƣơng chẵn.
Khi đó,
1( ) kCK x
, trong đó
và với
1( ,..., )kd d d ( )CK x {0}
,
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 47
( )(0, ) 0jf d
( j = 1,..., k – 1),
( ) 2
1
(0, ) ,0
k
kk
i
i
f d d
.
Theo định lý 2.2, điểm
0x
là điểm cực tiểu Pareto địa phƣơng chặt
cấp k của hàm f trên C theo nón
2
.
Sau đây ta đƣa ra điều kiện đủ cho điểm cực tiểu Pareto địa phƣơng
chặt.
Định lý 2.3
Giả sử
dim X
. Giả sử với mỗi
( )Cd K x {0}
, tồn tại số nguyên
dương n ( phụ thuộc vào d ) sao cho các đạo hàm theo phương
( ) ( , )jf x d
( j
= 0,..., n) tồn tại và một trong các điều kiện (A1), ..., (An) được thoả mãn. Khi
đó
x
là cực tiểu Pareto địa phương chặt của (P).
Chứng minh
Giả sử ngƣợc lại rằng
x
không là điểm cực tiểu Pareto địa phƣơng chặt
của (P).
Khi đó theo mệnh đề 2.3, với mỗi số nguyên
1s
, tồn tại một dãy
mx C
,
mx x
,
mx x
và
mb Q
sao cho
( ) ( )
0m m
s
m
m
f x f x b
lim
x x
.
Tƣơng tự trong chứng minh định lý 2.2, ta đặt
m mt x x
và
m
m
m
x x
d
x x
và nhận đƣợc
.m m mx x t d C
và
md d
với
1d
. Do đó,
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 48
d
( )CK x {0}
. Với phƣơng d, tồn tại số nguyên dƣơng n sao cho điều kiện
(Ak) thoả mãn với k nào đó
1,...,n
và (2.17) thoả mãn. Bằng lập luận đã
dùng trong chứng minh định lý 2.2, ta nhận đƣợc
( ) ( , )kf x d Q
, và điều này
mâu thuẫn với điều kiện (Ak).
2.4. TRƢỜNG HỢP Q =
r
Trong mục này, các điều kiện cần và đủ cấp cao khác cho cực tiểu
Pareto địa phƣơng chặt đƣợc thiết lập cho trƣờng hợp Y = r , Q =
r
,
1( ,..., )rf f f
. Cũng nhƣ trên, điều kiện đủ cho nghiệm hữu hiệu đƣợc thiết
lập trong không gian X hữu hạn chiều.
Định lý 2.4
Giả sử Q =
r
,
x
là cực tiểu Pareto địa phương chặt của bài toán
(P). Khi đó, với mọi
( )Cd K x
, tồn tại chỉ số
{1,...,r}i
sao cho các điều
kiện sau đây thoả mãn:
(a)
(0) ( , ) ( )i if x d f x
.
(b) Nếu
(0)
, ( , ) ( )i if x d f x
,
( )
, ( , ) 0
j
if x d
( j = 1,..., n – 1) thì
( )
, ( , ) 0
n
if x d
,
trong đó
( )
, ( , )
j
if x d
= 1
( )
,
0
0'
!
( ) ( , )
!
kj
k
i ij
t
kd d
j t
lim sup f x td f x d
t k
( j = 1,..., n),
(0)
, ( , )if x d
=
0
'
( ')i
t
d d
lim sup f x td
.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 49
Chứng minh
Giả sử
x
là cực tiểu Pareto địa phƣơng chặt của (P). Theo mệnh đề 2.2,
tồn tại lân cận U của
x
và các tập V1, ..., Vs ( s r ) sao cho
, 1,...,jV j s
là
một phủ của
C U { }x
và
( ) ( )j jf x f x
với mọi
jx C { }x
, (2.20)
với
{ }j jC C U V x
.
Ta có
1
s
j
j
C U C
(2.21)
Sử dụng một kết quả của Aubin – Frankowska [1], từ (2.21) suy ra
1
( ) ( ) ( )
j
s
C C U C
j
K x K x K x
. (2.22)
Lấy
( )Cd K x
, từ (2.22) ta suy ra tồn tại
{1,..., }i s
sao cho
( )
iC
d K x
. Do (2.20) ta nhận đƣợc
( ) ( )i if x f x
, với mọi
ix C { }x
. (2.23)
Vì
( )
iC
d K x
cho nên tồn tại dãy
0mt
và
md d
sao cho
m m ix t d C { }x
. Do đó, từ (2.23) ta suy ra
( ) ( )i m m if x t d f x
. (2.24)
Vì vậy
(0)
, ( , )if x d
=
0
'
( ') ( ) ( )i i m m i
t m
d d
lim sup f x td lim sup f x t d f x
.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 50
Kết luận (a) đƣợc chứng minh.
Để chứng minh (b), lấy
( )Cd K x
thoả mãn
(0)
, ( , ) ( )i if x d f x
,
( )
, ( , ) 0
j
if x d
( j = 1, ..., n – 1).
Khi đó từ (2.18) ta nhận đƣợc
( )
, ( , )
n
if x d
= 1
( )
,
0
0'
!
( ') ( , )
!
jn
j
i in
t
jd d
n t
lim sup f x td f x d
t j
1
( )
,
0
!
( ) ( , )
!
jn
jm
i m m in
m
jm
n t
lim sup f x t d f x d
t j
!
( ) ( ) 0i m m in
m
m
n
lim sup f x t d f x
t
Kết luận (b) đƣợc chứng minh.
Ví dụ sau đây minh họa cho định lý 2.4
Ví dụ 2.2
Cho X = Y = 2 , Q =
2
, C = [0, 1]
[–1, 0],
x
= (0, 0).
Trên 2 , xét hàm
1 2 2( ) , , kf x max x x x
với k là số nguyên
dƣơng.
Đặt
1 1 2( ) ,f x max x x
,
2 2( )
k
f x x
thì
1 2,f f f
.
Hiển nhiên,
( )CK x
và điểm
x
= (0, 0) là điểm cực tiểu
Pareto địa phƣơng chặt của f trên C theo nón
2
. Khi đó, với
1 2( , ) ( )Cd d d K x
,
(0)
2, 2(0, ) (0) 0f d f
,
( )
, (0, ) 0
jf d
( j = 1, ..., k – 1 ),
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 51
( )
2, 2(0, ) 0
kkf d d
.
Sau đây ta trình bày một điều kiện đủ cấp cao cho cực tiểu Pareto địa
phƣơng chặt cấp n dƣới ngôn ngữ đạo hàm theo phƣơng dƣới của Ginchev.
Định lý 2.5
Giả sử
dim X
, Y = r và Q =
r
, n là một số nguyên dương.
Giả sử tồn tại
0 1,...,i r
sao cho với mọi
( )Cd K x {0}
, một trong các
điều kiện (Bk) ( k = 1, ..., n ) thoả mãn:
(Bk)
0 0
(0)
, ( , ) ( )i if x d f x
,
0
( )
, ( , ) 0
j
if x d
( j = 1,..., k – 1),
0
( )
, ( , ) 0
k
if x d
.
Khi đó
x
là điểm cực tiểu Pareto địa phương chặt cấp n của bài toán
(P), trong đó
0
( )
, ( , )
j
if x d
=
0 0
1
( )
,
0
0'
!
( ') ( , )
!
kj
k
i ij
t
kd d
j t
lim inf f x td f x d
t k
(j = 1,...,n ),
0
(0)
, ( , )if x d
=
00
'
( ')i
t
d d
lim inf f x td
.
Chứng minh
Trƣớc hết ta chỉ ra
x
là điểm cực tiểu Pareto địa phƣơng chặt cấp n của
bài toán vô hƣớng sau:
0
( )iP
0
( ) :imin f x x C
,
trong đó
0i
f
là một thành phần của vectơ
1( ,..., )rf f f
đƣợc đề cập đến trong
định lý, C nhƣ trong bài toán (P).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 52
Giả sử điều kiện (Bk) thoả mãn, nhƣng x không là cực tiểu địa phƣơng
chặt cấp n của
0
( )iP
. Khi đó, với bất kỳ số nguyên
1m
, tồn tại
mx C
,
mx x
,
mx x
sao cho
0 0
1
( ) ( )
n
i m i mf x f x x x
m
. (2.25)
Đặt
m mt x x
và
m
m
m
x x
d
x x
.
Khi đó
m m mx x t d C
.
Vì
dim X
nên tồn tại một dãy con của
{ }md
hội tụ tới d với
1d
. Không mất tính tổng quát, ta có thể giả sử
md d
. Khi đó,
( )Cd K x {0}
.
Từ (2.25) ta có
0 0
( ) ( )
n
nm
i m m i
t
f x t d f x d
m
.
Vì
0mt
khi
m
nên với k = 1, ..., n , ta có
0 0
( ) ( )
k
nm
i m m i
t
f x t d f x d
m
. (2.26)
Do điều kiện (Bk), ta có
0 0
(0)
, ( , ) ( )i if x d f x
,
0
( )
, ( , ) 0
j
if x d
( j = 1,..., k – 1).
Kết hợp với (2.26) ta suy ra
0
( )
, ( , )
k
if x d
=
0 0
1
( )
,
0
0'
!
( ') ( , )
!
jk
j
i ik
t
jd d
k t
lim inf f x td f x d
t j
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 53
0 0
1
( )
,
0
!
( ' ) ( , )
!
jk
jm
i m m ik
m
jm
k t
lim inf f x t d f x d
t j
0 0
!
( ) ( )i m m ik
m
m
k
lim inf f x t d f x
t
!
0
k
nm
k
m
m
k t
lim inf d
t m
Nhƣng theo điều kiện (Bk), ta có
0
( )
, ( , ) 0
k
if x d
. Do vậy dẫn đến một mâu
thuẫn. Vậy
x
là điểm cực tiểu địa phƣơng chặt cấp n của
0
( )iP
.
Bây giờ ta phải chỉ ra rằng
x
là cực tiểu Pareto địa phƣơng chặt cấp n
của bài toán (P). Giả sử ngƣợc lại, khi đó theo mệnh đề 2.1, tồn tại dãy
mx C
,
mx x
và
1
( ,..., )
r
r
m m mb b b Q
sao cho
mx x
và
( ) ( )
0m m
n
m
m
f x f x b
lim
x x
.
Do đó,
( ) ( )
0i
i m i m
n
m
m
f x f x b
lim
x x
( i = 1, ..., r)
Nói riêng, ta có
0 0 0
( ) ( )
0
ii m i m
n
m
m
f x f x b
lim
x x
.
Ta lại sử dụng mệnh đề 2.1 để kết luận rằng
x
không là điểm cực tiểu
địa phƣơng chặt cấp n của
0
( )iP
và điều đó dẫn tới điều mâu thuẫn.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 54
Ví dụ 2.3
Lấy X = Y = 2 , Q =
2
, C = [–1, 0]
[0, 1],
x
= (0, 0).
Hàm f xác định bởi
2 2 22
1 1 2 1 2( ) ,( ) , ( , )
k
f x x x x x x x
,
trong đó k là số nguyên dƣơng.
Nhƣ vậy
1 2( , )f f f
với
1 1( )f x x
, 2 2 2
2 1 2( ) ( )
k
k
f x x x x
.
Ta có
( )CK x
và điểm
x
= (0, 0) là điểm cực tiểu địa phƣơng
chặt cấp k của hàm f2 trên C. Theo định lý 2.5, x là cực tiểu Pareto địa
phƣơng chặt cấp k của hàm f trên C theo nón
2
.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 55
KẾT LUẬN
Luận văn đã trình bày lý thuyết các điều kiện tối ƣu cấp cao cần và đủ
dƣới ngôn ngữ đạo hàm theo phƣơng cấp cao trên và dƣới Ginchev cho các
điểm cực tiểu, cực tiểu chặt của bài toán tối ƣu đơn mục tiêu không ràng
buộc, không trơn trong không gian Banach của I.Ginchev ( 2002 ), và cho các
điểm cực tiểu yếu, cực tiểu Pareto địa phƣơng chặt cấp m, cực tiểu Pareto địa
phƣơng chặt của bài toán tối ƣu đa mục tiêu không trơn với ràng buộc tập
trong không gian định chuẩn của Đ.V.Lƣu – P.T.Kiên ( 2007 ), cùng một số
tính chất của các điểm cực tiểu Pareto địa phƣơng chặt cấp m và cực tiểu
Pareto địa phƣơng chặt của B.Jiménez ( 2002 ). Các kết quả của luận văn cho
ta thấy rằng các khái niệm đạo hàm theo phƣơng cấp cao của I.Ginchev là
thích hợp trong việc dẫn các điều kiện tối ƣu cấp cao.
Việc nghiên cứu các điều kiện tối ƣu cấp cao dƣới ngôn ngữ đạo hàm
theo phƣơng cấp cao trên và dƣới của I.Ginchev cho các lớp bài toán tối ƣu đa
mục tiêu không trơn khác nhau cần đƣợc tiếp tục nghiên cứu và phát triển.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 56
TÀI LIỆU THAM KHẢO
[1] J.P.Aubin and H.Franknowska, Set – valued Analysis, Birkkhauser
Boston, 1990.
[2] A. Auslender, Stability in mathematical programming with
nondifferentiabledata, SIAM J. Control and Optimization, 22(1984),
239 – 254.
[3] A. Ben – Tal and J. Zowe, Derectional derivatives in nonsmooth
optimization, J. Optim Theory Appl., 47(1985), 483 – 490.
[4] L. Cromme, Strong uniqueness: A far reaching criterion for the
convergence of iterative procedures, Numer Math., 29(1978), 179 –
193.
[5] I. Ginchev, Higher order optimality conditions in nonsmooth
optimization, Optimization,51:1(2002), 47 – 72.
[6] B. Jimenez, Strict efficiency in vector optimization, J. Math. Anal.
Appl., 265(2002), 264 – 284.
[7] D. V. Luu and P. T. Kien , On higher – order conditions for strict
efficiency, Soochow Journal of Mathematics, 33(2007), 17 – 31.
[8] D. V. Luu and W. Oettli, Higher – order optimality conditions for a
minimax, Bull. Austral. Math. Soc., 54(1996), 509 – 516.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 57
[9] D. V. Luu, Higher – order necessary and sufficient conditions for strict
local Pareto minima interms of Studniarski’s derivatives, Optimization,
57(2008), 593 – 605.
[10] M. Studinarski, Necessary and sufficient conditions for isolated local
minima of nonsmooth functions, SIAM J. Control and Optimization,
24(1986), 1044 – 1049.
Các file đính kèm theo tài liệu này:
- Về điều kiện tối ưu cấp cao trong tối ưu không trơn.pdf