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 HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC SƯ PHẠM
o0o

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 L
L
U
U
Ậ
Ậ

O
O
Á
Á
N
NH
H
Ọ
Ọ
C
C
THÁI NGUYÊN - 2009

NV
V
Ă
Ă
N
NT
T
H
H
Ạ
Ạ
C
CS
S
Ĩ
ĨT
T
O

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ỤC LỤC Trang

Mục lục
Mở đầu
1
2
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

ƣ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,
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
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.
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

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, đ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
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
cấp 2.
Chƣơng 2: Trình bày các kết quả nghiên cứu của G. Bigi và
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
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ý
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à
Kuhn-Tucker.
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
Đỗ 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 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 thành

Y
là không gian Banach,
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ạ
ràng buộc
:G X Y
đƣợc giả thiết là khả vi liên tục hai lần. Kí hiệu
1
: ( )GK


là tập chấp nhận của bài toán
()P
.
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
p
Y  
và
 
0
pq
K






là nón của các hàm nhận giá trị không âm, tức là
 

   C ( ): C( ): ( ) 0,
     
.
Trong trƣờng hợp này, ràng buộc
G( x ) K
tƣơng ứng với
g( x, ) 0


với mọi


, trong đó
g( x,.): G( x )(.)
. Nếu tập

là vô
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
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

xX
ming( F( x )),

trong đó

K
I ( y ) 0
, nếu
yK
và bằng

nếu
yK
(xem [7]). Cho nên
hai cách tiếp cận là tƣơng đƣơng.
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

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.
Giả sử
(.)h
là hữu hạn tại điểm
yY
ta kí hiệu
'
h ( y,d )
là đạo hàm
theo phƣơng của nó tại điểm
y



.
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
chung, nếu
h
là lồi, có thể gián đoạn, thì bao đóng của trên đồ thị của
'
h( y,.)
trùng với trên đồ thị của
h ( y,.)






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

2'
''
t0
2
1
h( y td t ) h( y ) th ( y,d )
2
h ( y ;d, ): limsup
1
t
2




   


Ta nói rằng
h(.)
là khả vi theo phƣơng cấp hai tại y theo phƣơng d,
nếu








   


Chú ý rằng nếu
h(.)
là liên tục Lipschitz gần y, thì
''
h ( y ;d, ) h ( y ;d, )




. Nói riêng, điều này đúng, nếu
h(.)
lồi, hữu
hạn, và liên tục, và do đó là liên tục Lipschitz tại y.
Kí hiệu
*
Y
là không gian đối ngẫu của
Y
và
*

yT
( y ,T ): sup y ,y



.
Ký hiệu
 
dist .,T
là hàm khoảng cách
 
zT
dist y,T : inf y z


.
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

2
Df ( x),D f ( x)
tƣơng ứng là đạo hàm cấp một và đạo hàm cấp hai
của hàm
f ( x )
;
 
Y
B : y Y : y 1  
là hình cầu đơn vị trong
Y

Y(từ không gian định chuẩn X vào họ các tập con của Y) theo nghĩa
Painlevé - Kuratowski:
 
 
 
 
 
 


      
      


0
0
n 0 n n n
xx
n 0 n n n
xx
lim sup x y Y : x x sao cho y x ,y y ,
liminf x y Y : x x , y x , y y .

Theo định nghĩa của giới hạn tập hợp dƣới, ta có thể viết

 
K



, trong
đó
 
y
ký hiệu không gian tuyến tính sinh bởi vec tơ
y
và
cl
ký hiệu bao
đóng theo tôpô chuẩn của
Y
.
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

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
yK
theo phƣơng
d2
K
t0
2
K - y - td

K n n n n
1
T ( y,d ) Y: dist (y+td+ t , ) = o(t ),t 0 ,
2
1
O ( y,d ) : t 0 : dist (y+t d+ t ,K) = o(t ) .
2
  


  



  



Từ định nghĩa trên ta thấy rằng
22
KK
T ( y,d ) O ( y,d )
, và các tập tiếp
tuyến cấp hai này khác rỗng chỉ nếu
K
d T ( y )
. Cả hai tập
22
KK
T ( y,d ),O ( y,d )

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



( x) ( x),
(0 ) 0,



và với dãy đơn điệu giảm đến không x
k
nào đó, hàm
( x )

là tuyến tính
trên mỗi đoạn
 
2
k 1 k k k
x ,x , ( x ) x



và đƣờng thẳng đi qua các điểm
kk
( x , ( x ))

và
 



, và có
k
x0
.
Đặt
 
2
K : ( x,y ) : y ( x )

  R
. Khi đó với phƣơng
d : (1,0 )
ta có
 
 
2
K
T (0,d ) x,y : y 4
,
 
2
K
O (0,d ) ( x,y ): y 2
.
Với mỗi

R
,

K
được xác định như sau
 
K y Y :h( y) 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

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).
Khi đó,

 
2
K
O ( y,d ) : h ( y;d, ) 0


2
n n n
1
y t d t K
2

  
, và do đó,
2
n n n
1
h( y t d t ) 0
2

  
.
Khi đó,
2
n n n
n
2
n
1
h( y t d t )
2
h ( y ;d, ) liminf 0
1
t
2



  
.
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

Do đó,
2
n n n
1
h( y t d t ) 0
2

  
với
n
đủ lớn.
Vì vậy,
2
n n n
1
y t d t K
2

  
.
Từ đó suy ra
2
K
O ( y,d )



. Đặt
''
: ( y y )

  
  
. Do tính lồi của
h
, với
'
t0
đủ nhỏ ta có
2
'
1
1 t 0
2


và

 
    
2 2 2
' ' ' ' ' ' '
1 1 1
h( y t d t ) (1 t ) (t , ) t h y
2 2 2

t'
(1 1 2 t )



, và

2
''
n n n
1
(1 t )
2
  
.
Khi đó,
' ' 2 2
n n n n n n
1
(t , ) h( y t d t ) (t )
2
   
   
.
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

Bởi vì
''
nn

O ( y,d )
đóng, cho
0



ta nhận đƣợc
2
K
O ( y,d )


. Do đó (1.8) đƣợc chứng minh.
Nếu
h(.)
là lồi và liên tục tại
y
, thì các đạo hàm cấp hai
''
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

T ( y,d ) T ( d ) T ( y,d ) T (d )  
, (1.11)

KK
22
K T ( y ) K T ( y )
O ( y,d ) T (d ) O ( y,d ) T (d )  
. (1.12)
Nhắc lại [5] rằng tập
AX
lồi khác

đƣợc gọi là lùi xa theo
phƣơng
0d 
, nếu
 
0A d A

   
. Tập các vectơ
dX
thoả mãn

 
0A d A

   

và vectơ d = 0 đƣợc gọi là nón lùi xa của A.

0 T ( y,d )
thì ba tập này trùng nhau:
K
22
K K T ( y )
T ( y,d ) O ( y,d ) T (d )
.
Chú ý rằng
 
 
K
T ( y ) K
T ( d ) cl T ( y ) d
,
trong đó
 
K
d T y
;
K
T ( y )
T (d )
là rỗng, nếu
 
K
d T 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
1

T ( x ,h ) DG( x ) T (G( x ),DG( x )h ) D G( x )( h,h )





, (1.14)

2 1 2 2
0 0 K 0 0 0
O ( x ,h ) DG( x ) O (G( x ),DG( x )h ) D G( x )( h,h )





. (1.15)

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

1.3. ĐIỀU KIỆN CHÍNH QUY CẤP HAI VÀ ĐIỀU KIỆN TỐI ƢU CẤP HAI
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:
  
*


   
* * *
K
N ( y ): y Y : y ,z y 0,
với mọi

zK
là nón pháp
tuyến của
K
tại
y
. Kí hiệu
*
0
( x )

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
*
0
( x )

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 http://www.lrc-tnu.edu.vn

Khi tập
K
là một nón lồi và
yK
, nón pháp tuyến
K
N ( y )
có dạng:
 
0
**
K
N ( y ) y K : y ,y

  
,
trong đó
 
* * *
K : y Y : y ,y 0, y K

    

. 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ì
0
Df ( x )h 0
với mọi
hX

thỏa mãn
0 K 0
DG( x )h T (G( x ))
. Trong trƣờng hợp đó bất đẳng thức
0
Df ( x )h 0
, trong định nghĩa của nón tới hạn có thể thay bởi đẳng thức
0
Df ( x )h 0
. Điều đó là tƣơng đƣơng với
0
,DG( x )h 0

 
với mọi
0

0
h 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ì
(.,


2
0
0 ( x ,h)



, trong đó:
1
: G ( K )



. Vì thế ta
có thể tìm đƣợc dãy

k
t0
sao cho
   
22
k 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 http://www.lrc-tnu.edu.vn

Dãy

h C( x )
, ta nhận đƣợc
2
00
Df ( 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)

K0
T (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 0
T(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
00
X
MinDf( x ) +D f( x )(h,h)

x 0 xx 0
L( , )=D L( x , ) +D L( x , )(h,h)
    
.
Bởi vì với bất kỳ
z T( h )
, ta có
K0
z T (G( x )) T(h),
cho nên
( ,T( h))

 
với mỗi
 
K 0 K 0
T (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 0
DG( x )X T (G( x )) Y
.

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 http://www.lrc-tnu.edu.vn

2
K 0 0
T (G( x )),DG( x )h
. Nói chung, tập T (h) có thể lấy lớn hơn
2
K 0 0
T (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 0
0 O (G( x ),DG( x )h)
với mọi
0
h C( x )
, nói riêng nếu tập K
là một đa diện, thì
K0
2
K 0 0 T ( G( x )) 0
O (G( x ),DG( x )h ) T ( DG( x )h)
,

2,s 2 2
Kn
1
T ( y,d ): :dist(y+t d t ,K)= (t )
2
  




.
Với bất kỳ
s

, tập
2,s
K
T (y,d)
là lồi và đóng. Rõ ràng giao của
2,s
K
T ( y,d )
theo tất cả
s

là
2
K
T (y,d)
, và hợp của


, (1.24)
T
(h)
21
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

trong đó
O(h)
kí hiệu tập tất cả các tập con lồi của
2
K 0 0
O (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
O (G( x ), DG( x )h)
thì điều kiện (1.24) kéo theo điều kiện cần
dƣới đây

 
2
0
K 0 0
2
xx 0
( x )
y O ( G( x ),DG( x )h )
inf sup D L( x , )(h,h) ,y 0

là tập các điểm chấp nhận được của bài toán
( P )

thoả mãn
0
f ( x ) f
với mỗi
xS
. 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ố
c0
và lân cận
N
của S sao cho

 

2
0
f ( x ) f c dist(x,S)
với mọi
xN


. (1.27)
Nói riêng, nếu
 

0
Sx

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
(1.19). Để đánh giá ƣớc lƣợng dƣới, và do đó để nhận đƣợc điều kiện đủ
cấp 2 ta đƣa vào khái niệm sau.
Định nghĩa 1.2
Giả sử
K
y K,d T ( y )
và xét ánh xạ tuyến tính liên tục
M : X Y
. Ta
nói rằng tập đóng
K,M
A ( y,d ) Y
là xấp xỉ trên cấp 2 của K tại
y
theo
phương
d
và theo
M
, nếu với bất kỳ dãy
k
yK
có dạng
2
k k k k
1
y : y t d t r

k K,M
k
limdist(r ,A ( y,d )) 0


. (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
  
2
k k k
1
y t d t r K
2

sao cho
kk
t r 0
, thì ta bỏ qua
M
và nói rằng tập
K
A ( y,d )
là tập xấp xỉ
trên cấp hai của
K

2


tiến đến
K
A ( y,d )
khi
t0
.
Chú ý rằng số dƣ
r(t)
và dãy

kk
r r(t )
có thể không bị chặn.
Xấp xỉ trên cấp hai
K
A ( y,d )
không duy nhất. Rõ ràng, nếu
K
A ( y,d ) B
, thì
B
cũng là xấp xỉ trên cấp hai. Nếu
K
y K,d T ( y )
và
y d K


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
0
h C( x )
tương
ứng với một tập xấp xỉ trên cấp hai trên
K ,M 0
(h ): ( y ,d )


của tập
K

tại điểm
00
y : G( x )
theo phương
0
d : DG( x )h
và theo ánh xạ tuyến tính
0
M : DG( x )
. Giả sử rằng điều kiện cấp hai dưới đây thỏa mãn:

 
*
0
2*



, hội tụ tới
0
x
và sao cho