ĐIỀU KIỆN TỐI ƯU VÀ ĐỐI NGẪU CHO BÀI TOÁN TỐI ƯU ĐA TRỊ SỬ DỤNG ĐẠO HÀM ĐA TRỊ CLARKE THEO HƯỚNG NÓN

DOI:10.22144/ctu.jsi.2020.089

ĐIỀU KIỆN TỐI ƯU VÀ ĐỐI NGẪU CHO BÀI TOÁN TỐI ƯU ĐA TRỊ SỬ DỤNG ĐẠO HÀM ĐA TRỊ CLARKE THEO HƯỚNG NÓN

Lê Thanh Tùng¹, Trần Thiện Khải^2*, Phạm Thanh Hùng³ và Phạm Lê Bạch Ngọc³

1Khoa Khoa học Tự nhiên, Trường Đại học Cần Thơ

2Trung tâm Đào tạo và Hợp tác Doanh nghiệp, Trường Đại học Trà Vinh

3Khoa Sư phạm và Xã hội Nhân văn, Trường Đại học Kiên Giang

*Người chịu trách nhiệm về bài viết: Trần Thiện Khải (email: khai@tvu.edu.vn) Thông tin chung:

Ngày nhận bài: 04/03/2020 Ngày nhận bài sửa: 19/03/2020 Ngày duyệt đăng: 29/06/2020

Title:

Optimality conditions and duality for set-valued optimization in terms of cone-directed Clarke derivatives Từ khóa:

Bài toán tối ưu đa trị, các điều kiện tối ưu, đạo hàm Clarke theo hướng nón, đối ngẫu Mond-Weir, đối ngẫu Wolfe

Keywords:

Cone-directed Clarke derivatives, Mond-Weir duality, Optimality conditions, Set-valued optimization, Wolfe duality

ABSTRACT

This paper is to deal with Mond-Weir duality and Wolfe duality for constrained set-valued optimization problems in terms of cone- directed Clarke derivatives. Firstly, necessary and sufficient optimality conditions for constrained set-valued optimizations in terms of cone-directed Clarke derivatives for the cone-semilocally convex like maps are investigated. Then, the Mond-Weir duality and Wolfe duality for a constrained set-valued optimization and their weak duality, strong duality and converse duality are considered.

TÓM TẮT

Bài báo này khảo sát bài toán đối ngẫu dạng Mond-Weir và Wolfe cho bài toán tối ưu đa trị có ràng buộc sử dụng đạo hàm đa trị Clarke theo hướng nón. Trước hết, điều kiện tối ưu cần và đủ cho bài toán tối ưu đa trị có ràng buộc sử dụng đạo hàm đa trị Clarke theo hướng nón cho lớp hàm tựa lồi nửa địa phương được khảo sát. Sau đó, bài toán đối ngẫu dạng Mond-Weir và Wolfe cho bài toán tối ưu đa trị có ràng buộc và các tính chất về đối ngẫu mạnh, đối ngẫu yếu và đối ngẫu ngược được trình bày.

Trích dẫn: Lê Thanh Tùng, Trần Thiện Khải, Phạm Thanh Hùng và Phạm Lê Bạch Ngọc, 2020. Điều kiện tối ưu và đối ngẫu cho bài toán tối ưu đa trị sử dụng đạo hàm đa trị Clarke theo hướng nón. Tạp chí Khoa học Trường Đại học Cần Thơ. 56(Số chuyên đề: Khoa học tự nhiên)(1): 17-27.

1 MỞ ĐẦU

Việc xét bài toán đối ngẫu của các dạng bài toán tối ưu khác nhau và các liên hệ giữa các dạng nghiệm của chúng là một trong các chủ đề quan trọng trong lý thuyết tối ưu và được nhiều tác giả quan tâm nghiên cứu trong thời gian gần đây, chẳng hạn Sach and Craven (1991), Chen et al. (2009), Tung (2017), Tung et al. (2019). Khi xét bài toán

đối ngẫu cho các bài toán tối ưu đa trị, nhiều loại đạo hàm đa trị khác nhau đã được sử dụng. Trong công trình của Anh (2016), epi-đạo hàm theo tia cấp cao được sử dụng để khảo sát bài toán đối ngẫu hỗn hợp của bài toán tối ưu đa trị. Đạo hàm contingent cấp cao được sử dụng trong công trình của Li et al.

(2008) để khảo sát bài toán đối ngẫu dạng Mond- Weir cấp cao của bài toán tối ưu đa trị. Đạo hàm contingent cấp cao yếu được sử dụng để khảo sát bài

toán đối ngẫu dạng Mond-Weir và Wolfe cấp cao của bài toán tối ưu đa trị trong công trình của Chen et al. (2009). Bài báo của Yu and Kong (2016) sử dụng đạo hàm theo tia cấp cao để xét bài toán đối ngẫu dạng Mond-Weir và dạng Wolfe.

Nón tiếp tuyến Clarke (Clarke, 1983), mặc dù chứa trong nón contingent và nón theo tia radial, nhưng là một nón lồi nên có thể áp dụng để xây dựng các điều kiện tối ưu dạng đối ngẫu trong đó có sử dụng Định lý tách tập lồi như trong các công trình của Corley (1988), Lalitha and Arora (2008), Lalitha and Arora (2009). Qua tham khảo các tài liệu liên quan về chủ đề đối ngẫu có thể thấy rằng chưa có bài báo nào sử dụng các dạng đạo hàm đa trị Clarke để khảo sát bài toán đối ngẫu của bài toán tối ưu đa trị. Từ những quan sát trên, trong bài báo này đạo hàm đa trị Clarke đã được sử dụng theo hướng nón để khảo sát bài toán đối ngẫu dạng Mond-Weir và bài toán đối ngẫu dạng Wolfe của bài toán tối ưu đa trị.

2 KIẾN THỨC CHUẨN BỊ

Trong bài báo này nếu không giả thiết gì thêm, xét X Y Z, , là các không gian định chuẩn thực,

,

KY DZ là các nón lồi đóng có đỉnh với phần trong khác rỗng. Với AX, int , cl ,A A A kí hiệu tương ứng cho phần trong, bao đóng, biên của A.

*

X là không gian đối ngẫu của X và x x*, là giá trị của ánh xạ tuyến tính liên tục *

x 

X* tại

x

X và B_X,B_Y là hình cầu đơn vị đóng trong ,

X Y. Với x0X,

( )

x0 là tập các lân cận của x₀ . Với AX u, X, các nón sau thường được dùng

 

coneA:=   a 0,aA ,

 

cone₊A:=   a 0,aA ,

( )

^cone

( )

A u = A u+ . Ký hiệu

 

: * *| *, 0,

K⁺ = k Y k y   y K ,

 

: * *| *, 0,

D⁺ = d Z d z   z D lần lượt là nón đối ngẫu của ^K và D.

Với AY, nón contingent ^{T A y}

(

^,

)

của ^A tại yclA được định nghĩa như sau:

( )

 

, :

| 0, : ,

=

    →_{n n} + _{n n}  T A

h Y t h h t h A

y

y n

Dễ dàng kiểm tra được, định nghĩa trên tương đương với

( )

 

, :

| 0, : , ( ) .

=

    _{n n n}→ _{n n}− → T A

h Y y y

y

y y

y A h

Nón tiếp tuyến Clarke T^C( , )A y của A tại cl

y A được cho như sau:

( )



^

, :

| , 0, : , .

=

  →    → +  

C

n n n n n n

T A

h Y y t h h h

y

A

y y t n

Nhận xét 2.1. (Khan et al, 2016, trang 127) (i) ^TC

( )

^{A,y T A}

( )

^{,y .}

(ii) ^TC

( )

^{A y,} là nón lồi và ^0TC

( )

^{A,y .}

Định nghĩa 2.1. Cho a A Y.

(i) a được gọi là điểm cực tiểu địa phương (Pareto) của ^A đối với K, và ký hiệu là

Min_K

a A nếu và chỉ nếu tồn tại ^U

( )

^a sao cho

(

^{A U −a}

)

^{ −}

(

^{K\ 0}

  )

^{= }_.

(ii) a được gọi là điểm cực tiểu địa phương yếu của ^A đối với ^K , và ký hiệu là aWMinK A nếu và chỉ nếu tồn tại U

( )

a sao cho

(

^A −^{U a}

) (

 −^intK

)

=  .

(iii) a được gọi là điểm cực đại địa phương (Pareto) của A đối với K, và ký hiệu là

Max_K

a A, nếu và chỉ nếu tồn tại ^U

( )

^{a sao}

cho

(

^{A −U a}

)

^

(

^{K\ 0}

  )

^{= }

.

(iv) a được gọi là điểm cực đại địa phương yếu của A đối với K , và ký hiệu là aWMax_K A nếu và chỉ nếu tồn tại ^U

( )

^{a sao cho}

(

^A −^{U a}

)

^intK=  .

Nếu U=Y, cụm từ “địa phương” sẽ được lược bỏ, nghĩa là khái niệm toàn cục tương ứng được khảo sát.

Với ánh xạ đa trị H X: →2^Y, tập xác định, đồ thị, trên đồ thị của H được định nghĩa như sau:

 ( ) 

( ) ( )

 

dom : | ,

gr : , | ,

H x X H x

H x y X Y y H x

=   

=   

( ) ( )

 

epiH:= x y,  X Y y| H x +K . Ánh xạ profile của H , kí hiệu H₊, định nghĩa bởi ^H+

( )

^{x :}=^{H x}

( )

+^K.

Định nghĩa 2.2. Cho H X: →2^Y là ánh xạ đa trị,

(

^{x y,}

)

^{grH .}

(i) (Aubin and Frankowska, 1990) Đạo hàm contingent ^{DH x y}

(

^,

)

^{của H tại}

(

^{x y,}

)

^{grH là}

ánh xạ đa trị từ X vào Y thỏa

( ) ( ( ) )

grDH x y, =T grH x y, , , nghĩa là

(

^,

)( )

^:

 ( )

^,

(

^{gr ,}

(

^,

) ) 

^,

DH x y u = vY u v T H x y với mọi uX.

(ii) (Jahn, 2009) Đạo hàm contingent của H theo hướng nón K là đạo hàm contingent của H+K tại

(

^{x y,}

)

^{grH epiH}, nghĩa là ánh xạ đa trị từ X vào Y thỏa

( ) ( ( ) ) ( ( ) )

grDH₊ x y, =T grH ,₊ x y, =T epiH x y, , , hay

(

^,

)( )

^:

 ( )

^,

(

^{epi ,}

(

^,

) ) 

^,

DH₊ x y u = vY u v T H x y với mọi uX.

Định nghĩa 2.3. Cho H X: →2^Y là ánh xạ đa trị,

(

^{x y,}

)

^grH .

(i) (Aubin and Frankowska, 1990) Đạo hàm Clarke ^{D H x yC}

(

^,

)

của ^H tại

(

^{x y,}

)

^grH là ánh

xạ đa trị từ ^X vào ^Y thỏa

( ) ( ( ) )

grDH x y, =T^C grH x y, , , nghĩa là

(

^,

)( )

^:

 ( )

^,

(

^{gr ,}

(

^,

) ) 

^,

C C

D H x y u = vY u v T H x y với mọi uX.

(ii) (Sach and Craven, 1991) Đạo hàm Clarke của H theo hướng nón K là đạo hàm Clarke của

H+K tại

(

^{x y,}

)

^grH ^epiH, nghĩa là ánh xạ đa trị từ ^X vào ^Y thỏa

( ) ( ( ) )

( ( ) )

gr , gr , ,

epi , , ,

+ = +

=

C C

C

D H x y T H x y

T H x y

hay

( )( )

( ) ( ( ) )

 

, :

, epi , , ,

+ =

 

C

C

D H x y u

v Y u v T H x y

với mọi uX.

3 ĐIỀU KIỆN TỐI ƯU SỬ DỤNG ĐẠO HÀM THEO HƯỚNG NÓN CLARKE

Cho X Y Z, , là các không gian định chuẩn thực, KY D, Z là các nón lồi đóng có đỉnh với phần trong khác rỗng và F X: →2 ,^Y G X: →2^Z là 2 ánh xạ đa trị.

Xét bài toán tối ưu đa trị dạng tổng quát như sau:

( ) ( )

( ) ( )

WSOP WMin^K F x

G x D

  −  



nghĩa là tìm tất cả các giá trị x₀A mà tồn tại

( )

0 0

y F x sao cho y0WMin_KF

( )

A , trong đó

( ) ( )

 

:

A= x X G x  −D   .

Tập các điểm chấp nhận được của bài toán (WSOP) ký hiệu là

( ) ( )

 

: x y, X Y x A y, F x .

 =    

Điểm

(

x0,y0

)

  là nghiệm địa phương của bài toán (WSOP) nếu tồn tại một lân cận U của x₀ sao cho

(

F A U

(



)

−y0

)

 −

(

intK

)

= . Trong phần này, để đơn giản trong cách trình bày, giả sử rằng dom D ^C( , )F G₊

(

x0, y0,z0

)

 = X.

Mệnh đề 3.1. (Điều kiện cần dạng Fritz-John) Nếu

(

x0, y0

)

là một nghiệm của (WSOP) thì tồn tại

(

k*,d*

)

K⁺D⁺\

 (

0_Y*,0_Z*

) 

sao cho với mọi

(

y z,

)

D^C

(

F G,

) (

₊ x0, y0,z0

)( )

X ,

*, *, 0 k y + d z 

và ^{d*,z0 =0}.

Chứng minh. Lấy z0G x

( )

0  −D, ta đặt

( ) (

0 0 0

)( ) (

0

)

: ^C , , , 0 ,_Y .

x X

B D F G ₊ x y z x z



 

= +

 

Trước hết, chứng minh rằng B là tập lồi bằng cách chứng minh B1= −B

(

0 ,_Y z0

)

lồi. Lấy

(

y1,z1

) (

, y2,z2

)

B1. Khi đó, tồn tại x x₁, ₂

sao cho

(

yi,zi

)

D^C

(

F G,

) (

₊ x0,y0,z0

)( )

xi , i=1, 2, nghĩa là

(

x y z_i, _i, _i

)

T^C

(

epi

(

F G,

) (

, x0, y0,z0

) )

, i=1, 2.

Nhưng do T^C

(

epi

(

F G,

) (

, x0, y0,z0

) )

là nón lồi, tham khảo sách chuyên khảo của Aubin and Frankowska (1990), ta có

(

x y z1, 1, 1

) (

1

)(

x2,y2, z2

)

T^C

(

epi

(

F G,

) (

, x0, y0, z0

) )

 + − 

với mọi  

 

0, 1 . Nên

( ) ( )

( )

( ) ( ) ( ( ) )

1 , 1

1 2 1 2

, 0, 0, 0 1 1 2 ,

y y z z

DC F G x y z x x

 + −   + − 

 +  + − 

với mọi  

 

0, 1 . Do đó,

(

1, 1

)

(1 )

(

2, 2

)

1

 y z + − y z B , nên B₁ và B lồi.

Tiếp theo, chứng minh



^{int int}



⁼

B − K − D . Giả thiết phản chứng tồn tại

(

^{x y zˆ ˆ ˆ, ,}

)

sao cho

( ) ( ) ( )( ) ( )

 

0 0 0 0 0

ˆ, ˆ , , ˆ

int int ,

, 0 ,

C

y z z D F G x y z x Y

K

z D

+

 − 



−

+  +

(1)

nghĩa là,

( ) ( ) ( )

( ) ( )

0 0 0

0 0 0

ˆ ˆ ˆ, , epi , , , ,

epi , , , ,

  

  

x y z TC F G x y z

T F G x y z

Khi đó, tồn tại dãy ⁽x y zn^, n^, n⁾^epi

(

F G^,

)

, nghĩa là x_nX, y_nF x( )_n +K, z_nG x( )_n +D,

0 0 0

( ,x y z_{n n}, )_n →( ,x y z, )

và dãy  _n 0 sao cho

0 0 0 ˆ ˆ ˆ

( , , ) ( , , )

n xn x yn y zn z x y z

 − − − → .

Từ (1), ta có yˆ−intK. Do (y y0) yˆ intK

n n

 − →  − mở, tồn tại N₁ sao cho

( 0) int

n yn y K

 − − _{, với} nN₁

, và do  _n 0 và ^K là một nón nên

0 int

yn− −y K, với nN₁. (2) Tương tự, do D là một nón, z z+ −₀ intD và

0 0 ˆ 0

( )

n zn z z z z

 − + → + , suy ra tồn tại N₂ _n(z_n−z₀)+ −z₀ intD với mọi nN₂. (3) Hơn nữa, tồn tại Nmax

(

N1,N2

)

sao cho

N 1

  . Nếu ngược lại, nghĩa là  _n 1 với mọi n

đủ lớn, thì do y_n →y₀ và

(

0

)

0

0 | _n y_n−y | | y_n−y | nên

(

0

)

0

n yn y Y

 − → , mâu thuẫn với yˆ−intK. Từ (3) ta có

0 0 0

( ) [ _N (1 1/ ) ] int ,

N zN z z N z − N z D

 − + =  −  −

và do đó z_N− − (1 1/ _N)z₀−intD. Nhưng

0−

z D và 1 1/−  _N 0, vì  _N 1 nên (1 1/− _N)z0−D. Do đó,

(

(1 1 / ) 0

)

(1 1 / ) 0

int int .

N N N N

z z z z

D D D

= − −  + − 

 − −  − (4)

Mặt khác, do y_NF x( _N)+K, z_NG x( _N)+D, tồn tạiyˆ_NF x( _N), k_NK, zˆ_NG x( _N) và d_ND sao cho y_N =yˆ_N+k_N, z_N = +zˆ_N d_N. Từ (2) và (4), ta có

0 0

ˆ_N ( _N ) _N int int ,

y − =y y −y − −k K K−  − K

ˆ_{N N N} int int .

z =z −d − D D−  − D

Do đó, chúng ta chỉ ra sự tồn tại ˆ ˆ

, ( ) , ( )

N N N N N

x X z G x −D y F x sao cho ˆ_N 0 int

y − −y K . Điều này dẫn đến mâu thuẫn với giả thiết ( ,x₀ y₀) là một nghiệm của (WSOP). Do đó, B −[ intK−int ]D = .

Tiếp theo, sử dụng Định lý tách để tách B và intK intD

− − . Theo định lý tách Eidelhei, tham khảo trang 74 sách chuyên khảo của Jahn (2009), tồn tại k*Y d*, *Z* không đồng thời là hàm không, và số thực  sao cho:

*, *, , ( , ) ,

k y + d z    y z B

*, *, , ( , ) int int .

k y + d z    y z  − K − D (5)

Nhưng do ( , )y z −intK−intD có thể được lấy tùy ý gần với (0 , 0 )_{Y Z} và tính liên tục của

*, *

k d từ (5) thì  0.

Tuy nhiên, nếu giả sử rằng

*, 0

*,

k y d z

  +  với một

( , )y z −intK−intD.

Khi đó, k*,y + d*,  z , với

* 0

, *,

k y + d z

    đủ lớn, trong khi

(  −y, z) intK−intD, mâu thuẫn với (5). Điều này cho thấy rằng  phải bằng 0, nghĩa là

*, *, 0, ( , ) ,

k y + d z   y z B (6)

*, *, 0, ( , ) int int .

k y + d z   y z  − K − D (7)

Từ (7), bằng cách lấy y−intK tùy ý gần với 0_Y, theo tính liên tục của k*, dẫn đến kết luận

*, 0, int .

d z   z D Do đó,

*, 0, cl(int )

d z   z D D, nênd*D⁺. Tương tự có thể chứng minh được k*K⁺.

Để chứng minh d*,z0 =0, trước hết ta có

*, 0 0

d z  ; từ (6) và (0 , )_Y z₀ B theo Nhận xét 2.1. Nhưng z₀−D và d*D⁺ nên d*,z₀ 0. Do vậy, d*,z₀ =0.

Cuối cùng, mệnh đề k*,y + d*,z 0 với mọi xX thỏa. Thật vậy, với xX , do

(

,

)

( ,0 0, 0)( )+(0 ,_Y 0) ,

DC F G ₊ x y z x z B từ (6),

*, *, 0 0

k y + d z+z  . Nhưng do d*,z0 =0 dẫn đến k*,y + d*,z 0.

Tiếp theo, điều kiện cần tối ưu dạng KKT cho bài toán (WSOP) được thiết lập sử dụng định tính ràng buộc Slater và điều kiện tính tựa lồi nửa địa phương.

Định nghĩa 3.1. (i) Tập SX được gọi là dạng hình sao địa phương tại điểm x₀S nếu với bất kỳ xS, tồn tại một số thực dương a x( , )x₀ 1 sao cho (1−)x₀+xS với 0  a x x( , ₀). Nếu S có dạng hình sao địa phương tại mỗi xS ,S được gọi là tập hình sao địa phương.

(ii) Nếu S là tập hình sao địa phương, khi đó ánh xạ đa trị H S: X→2^Y được gọi là K -tựa lồi nửa địa phương, tham khảo trong công trình của Arora and Lalitha (2005), tại điểm x₀S nếu với mọi xS y, H x( ) và y₀H x( )₀ thì tồn tại một số thực dương d x y(( , ),( ,x y_{0 0}))a x x( , ₀) sao cho

(1−)y0+  y H S( )+K với

0 0

0  d x y(( , ),( ,x y )) .

Ánh xạ

H

được gọi là

K

-tựa lồi nửa địa phương trên

S

nếu

H

là

K

-tựa lồi nửa địa phương tại mỗi

x S  .

Nếu

H

là

K

-tựa lồi nửa địa phương trên

S

với a x( ,x₀)=1 và

0 0

(( , ), ( , )) 1

d x y x y = với mọi

0, , ( )

x xS yH x và y₀H x( ₀) ,

H

_là

K

_-

lồi trên

S .

Ví dụ 3.1. Tập S=]0, 2[]3,5[ là tập hình sao địa phương trên nhưng không phải là tập lồi trên

.

Ví dụ 3.2. (Lalitha and Arora, 2008) Nếu K= 2₊ thì ánh xạ đa trị H S: →2^Ylà

K

-tựa lồi nửa địa phương trên

S

, trong đó S=[0, 1] và

2

1 2 1 2

2

1 2 2

{( , ) | 1}, khi [0,

( ) 1[

{( , ) | 2} , khi 1.

x x

y y y y

H x

y y y

  +  

= 

 

 =

Tuy nhiên,

H

không là

K

-lồi, vì với x=0,

0 1,

x = 4 4

3 3,

y  

=  

 , 0

( )

0

4 7,

y = − 3 3H x

  và

1

 =2, (1 ) ₀ 0,¹¹ ( ) y y  6 H S K

−  +  =  +

  .

Mệnh đề 3.2. Cho H S: X →2^Ylà ánh xạ

đa trị (x₀,y₀)grH. Nếu H là K-tựa lồi nửa địa phương xác định trên tập hình sao S và

0 0

( , )( )

C x y

D H₊ x tồn tại với mỗi

x S 

thì

0 0 0 0

( ) ^C ( , )( ), .

H x −y D H+ x y x−x  x S

Chứng minh. Với

x S 

_{và yH x( ), cần}

chứng minh y−y₀D H^C ₊(x₀,y₀)(x−x₀), nghĩa là (x−x₀, y−y₀)T^C(epiH,(x₀, y₀)).

Lấy ^{(xn,yn)→(x0, y0)} với ^{(xn, yn)epiH} và tn→ 

với ^{tn 0}. Do

S

là tập hình sao địa phương nên tồn tại một số thực ^{a x( , xn)1} sao cho

(1− )x_n+  x X

với ^{0  a x x( , n)}. Rõ ràng là

) ( )

(

yH x H S +K và

( ) ( )

n n

y H x +KH S +K

do (x_n,y_n)epiH. Tập H S( )+K là tập hình sao địa phương vì

H

là ánh xạ đa trị

K

-tựa lồi nửa địa phương, và do đó tồn tại một số thực dương

( , _n) 1

b y y  sao cho (1−)y_n+  y H S( )+K với 0  b y y( , _n). Với mỗi n xác định

( , , _n, _n) min{ ( , _n), ( , _n)}

c x y x y = a x x b y y . Không mất tính tổng quát, có thể giả sử rằng

0 1/ t_n c x y x( , , _n, y_n) với mỗi n. Đặt (1 1/ ) (1/ )

n n n n

x = − t x + t x

và y_n= −(1 1/t_n)y_n+(1/t_n)y,

với 0 1/ t_n c x y x( , , _n, y_n). Do đó, với mỗi n

, ta có x_nS y, _nH x( _n)+K, { }x_n →x₀, { }y_n →y0. Điều này kéo theo (x_n,y_n)epiH,

0 0)

(x y, )→(x y, và

0 0

( , ) ( , ) ( , )

{ − }→ − −

n n n n n

t x y x y x x y y .

Định nghĩa 3.2. (Lalitha and Arora, 2008) Bài toán (WSOP) thỏa mãn định tính ràng buộc Slater dạng tổng quát nếu tồn tại

x '  X

sao cho

( ') ( int ) G x  − D  .

Mệnh đề 3.3. (Điều kiện cần dạng Karush- Kuhn-Tucker)

Giả sử ( ,F G) :X →2^Y2^Z là ánh xạ đa trị (KD)-tựa lồi nửa địa phương xác định trên tập

hình sao S, trong đó

{ | ( ) ( ) }

A= x X G x  −D   S và S là tập con

của X và (WSOP) thỏa định tính ràng buộc Slater dạng tổng quát. Nếu (x₀, y₀) là một nghiệm địa phương của (WSOP) thì tồn tại k*K⁺\ {0_Y*} và

*

d D⁺ sao cho với mọi

0 0 0

( , )y z D^C( ,F G) (₊ x,y,z )(X),

*, *, 0

k y + d z  và d*,z₀ =0. Chứng minh. Do (x₀, y₀) là nghiệm của (WSOP), nên theo Mệnh đề 3.1, tồn tại

* *

( *, *) \ {(0 , 0 )}

Y Z

k d K⁺D⁺ sao cho với mọi

0 0 0

( , )y z D^C( ,F G) (₊ x,y,z )(X),

*, *, 0

k y + d z  và d*,z₀ =0. Áp dụng Mệnh đề 3.2 cho ánh xạ đa trị ( , )F G , với mỗi ( , ) ( ) ( )

x X

y z F x G x





 , thì

0 0 0 0 0 0

( , )y z −(y ,z )D^C( ,F G) (₊ x,y, z )(x−x ). Điều này dẫn đến ^{k*,y−y0 + d*,z−z0 0}, và do đó ^{k*,y−y0 + d*,z 0}.

Giả thiết phản chứng * 0*

k = Y thì * 0 *

d  Z và do đó

.

*, 0, ( )





 

x X

d z z G x (7)

Do (WSOP) thỏa mãn định tính ràng buộc Slater dạng tổng quát nên tồn tại

x '  X

sao cho

( ') ( int )

G x  − D  , nghĩa là tồn tại ' ( ') ( int )

z G x  − D . Do z' −( intD) nên ta có

*, ' 0

d z  với ' ( ') ( )

x X

z G x G x



  , mâu thuẫn

với (7). Do đó, ta có * 0*

k  Y dẫn đến điều phải chứng minh.

Mệnh đề 3.4. (Điều kiện đủ dạng KKT) Cho ( ,F G) :X →2^Y2^Z là ánh xạ đa trị (KD)-tựa lồi nửa địa phương xác định trên tập

hình sao S, trong đó

{ : ( ) ( ) }

=   −   

A x X G x D S và S là tập con của X. Nếu x₀A y, ₀F x( ₀), z₀G x( )₀  −( D),

( *,k d*)K⁺\ {0_Y*}D⁺ thỏa

*, + *, 0

k y d z và d*,z₀ =0 (8) với mọi ( , )y z D^C( ,F G) (₊ x₀,y₀,z₀)(X), thì

0 0

(x , y ) là một nghiệm của (WSOP).

Chứng minh. Giả sử (x₀, y₀) không là một nghiệm của (WSOP). Khi đó, tồn tại

x  A

sao cho

(F x( )−y0) −( intK) .

Do đó, tồn tại yF x( ) và zG x( ) −( D) sao cho^{y−y0 −intK}.

Lưu ý rằng do k*K⁺\{ }0 , nên

*, 0 0

k y−y 

Theo Mệnh đề 3.2 ta có:

0 0 ( , 0 0 0 0

( ,F G x)( )−(y,z )D^C FG)₊(x,y ,z )(x−x ).

Điều này cùng với (8) suy ra rằng

0 0

*, *, 0.

k y−y + d z−z 

Do d*,z₀ =0 và

z − D

, nên

0 0

*, *, *, 0,

k y−y  − d z−z = − d z 

dẫn đến mâu thuẫn.

Định nghĩa 3.3. (Jahn and Khan, 2002; Jahn, 2009) Ánh xạ đa trị F X: →2^Y được gọi là



-tựa lồi tại điểm (x0,y0) nếu sự tồn tại điểm

x  A

, với xx0 và

(

F x( )−

 

y0

)

   _{dẫn đến}

( 0, 0)( 0)

D FC ₊ x y x−x    .

Mệnh đề 3.5. (Điều kiện đủ dạng KKT) Giả sử A−x0X với ( ,x y z_{0 0}, ₀)gr( , )F G . Nếu tồn tại

* \ {0 }*

k K⁺ Y và d*D⁺ sao cho d*,z₀ =0

và điều kiện sau thỏa:

*, *, 0

k y + d z  , với mọi

0 0 0 0

( , )y z D^C( ,F G) (₊ x,y,z )(x−x), (9) với mọi

x  A

_.

Khi đó, điểm (x₀, y₀) là điểm cực tiểu nếu ánh xạ ( , )F G là



-tựa lồi tại (x₀, y₀,z₀) với

( ) ( 0 0 )

: K\ {0 }_Y D cone(z ) cone(z )

 = −  − + − .

Chứng minh. Đặt

( )

 0 0 

: x A |G x( ) D cone(z) cone(z)

 =   − + −  

Đề chứng minh Mệnh đề cần kiểm tra điểm

0 0

(x , y ) là điểm cực tiểu của

F

_trên



_{và do}

A  

_nên (x₀, y₀) cũng là điểm cực tiểu của bài

toán (WSOP). Trước hết, kiểm tra khẳng định với mỗi

x  A

, điều kiện sau đây thỏa:

0 0 0 0

( , ) ( , , )( )

DC F G ₊ x y z x−x   = .

Thật vậy, nếu khẳng định nêu trên không thỏa, thì tồn tại

x  A

và

0 0 0 0

( , )y z D^C( ,F G) (₊ x ,y ,z )(x−x )  và hơn nữa suy ra y −K\ {0 }_Y và

( cone( 0) cone( 0))

z − +D z − z .

Bởi vì * \ {0 } k K *

Y

 + và d*,z0 =0, nên

*, *, 0

k y + d z  ,mâu thuẫn với (9).

Do đó D^C( ,F G) (₊ x₀,y₀, z₀)(x−x₀)  =  và khẳng định này cùng với tính



-tựa lồi của

( , )F G dẫn đến

(F,G)( )x −{(y0,z0)}  = , với mọi

x  A

. Điều này suy ra không tồn tại

x  A

sao cho (F( )x −{y0}) ( −K\ {0_Y}) 

và (G x( )−z0) ( − +D cone(z0)−cone(z0)) . Từ đây, suy ra rằng (x₀, y₀) cũng là điểm cực tiểu của bài toán (WSOP).

4 BÀI TOÁN ĐỐI NGẪU MOND-WEIR Trong phần này, luôn giả sử là ( ', ')x y gr ,F ' ( ')

z G x  −D và

domD^C( ,F G)₊( ',x y', 'z)=X . Bài toán đối ngẫu Mond-Weir (Mond and Weir, 1981) của (WSOP) sử dụng đạo hàm đa trị Clarke ký hiệu là (MWDP) xác định bởi

WMax ( ', ', ', *, *) ',

s.c. *, *, 0,

( , ) ( ', ', ')( ),

*, ' 0,

( *, *) ( \ { ) . ( , )

0}

K

x X C

h x y z k d y

k y d z

D

y z F G x y z x

d z

k d K D



+ +

+

 =

 + 

  



 

  



Tập các điểm chấp nhận được của bài toán (MWDP) ký hiệu và xác định bởi

: {( ', ', ', *, *) ( \ {0}) |

MW x y z k d X Y Z K⁺ D⁺

 =     

*, ' 0, *, *, 0 , ( , )

( ', ', ')( ) .

( , )

}

x X

DC

d z k y d z y

F G

z x y z x

+



 +  



Điểm

(

x y z k d', ', ', *, *

)

_MWlà nghiệm của bài toán (MWDP) nếu, với mọi y'F x( ') với

( ', ', ', *, *)x y z k d _MW, ta có

(

h x y z k d( ', ', ', *, *)−h x y z k d( ', ', ', *, *)

)

int K=  Mệnh đề 4.1. (Đối ngẫu yếu)

Giả sử ( ,F G) :X →2^Y2^Z là ánh xạ đa trị (KD)-tựa lồi nửa địa phương xác định trên tập

hình sao S, trong đó

{ : ( ) ( ) }

A= xX G x  −D   S và S là tập con của X. Nếu ( , )x y , ( ', ', ', *, *)x y z k d _MW thì

( ', ', ', *, *) int y−h x y z k d  − K. Chứng minh. Giả thiết phản chứng

( ', ', ', *, *) int

y−h x y z k d  − K, nghĩa là ' int

y− −y K.

Khi đó, vì k*K⁺\ {0 }_Y* nên

*, ' 0

k y−y  . (10)

Do ( , )x y , nên G x( ) −  ( D) và ( )

yF x . Theo Mệnh đề 3.2,

', ' ( , )

( ,F G)( )x −(y z)D^C F G ₊(x y z', ', ')(x−x' .) Bởi vì G x( ) −( D) , nên tồn tại

( ) ( D)

zGx  − và từ d*D⁺, d*,z 0.

Do ( ', ', ', *, *)x y z k d _MW, nên d*,z' 0, dẫn đến d*, z−z' = d*,z − d*,z' 0.

Hơn nữa, từ ( ', ', ', *, *)x y z k d _MW và ( ', ') ( , )( ) ( ', ')

( , ) ( ', ', ')( '),

C

y z

D F G x y z x y y z z F G x

+ x

− −  −

 −

dẫn đến

*, ' *, ' 0

k y−y + d z−z  . Khi đó, suy ra được

*, ' *, ' 0,

k y−y  − d z−z 

mâu thuẫn với (10).

Mệnh đề 4.2. (Đối ngẫu mạnh)

Giả sử ( ,F G) :X →2^Y2^Z là ánh xạ đa trị (KD)-tựa lồi nửa địa phương xác định trên tập

hình sao S, trong đó

{ : ( ) ( ) }

A= xX G x  −D   S và S là tập con của X và (WSOP) thỏa định tính ràng buộc Slater dạng tổng quát. Nếu (x y₀, ₀) là nghiệm địa phương của bài toán (WSOP) thì tồn tại

( *, *)k d K⁺\ {0 }_Y* D⁺ sao cho (x₀,y₀,z₀, *, *)k d

là nghiệm của (MWDP).

Chứng minh. Theo Mệnh đề 3.3, tồn tại

( *, *)k d K⁺\ {0 }_Y* D⁺

sao cho với mọi

0 0 0

( , )y z D^C( ,F G) (₊ x,y,z )(X),

*, *, 0

k y + d z  và d*,z₀ =0, và do đó ^{(x0,y0,z0, *, *)k d  MW}.

Mệnh đề thỏa nếu chứng minh được

0 0 0

(x,y,z , *, *)k d là nghiệm của (MWDP). Giả thiết phản chứng (x₀,y₀,z₀, *, *)k d không là nghiệm của (MWDP), nghĩa là tồn tại y'F x( ')với

( ', ', ', *, *)x y z k d _MWsao cho

(

h x y z k d( ', ', ', *, *)−h x y z k d( ,^{0 0}, ⁰, *, *)

)

int K=  Khi đó, tồn tại y'F x( ')với ( ', ', ', *, *)x y z k d _MWsao cho y'− y₀ intK.

Do đó, tồn tại (x y₀, ₀) và ( ', ', ', *, *)x y z k d _MWsao cho y0−  −y' int ,K mâu thuẫn với Mệnh đề 4.1.

Mệnh đề 4.3. (Đối ngẫu ngược) Cho( ', ')x y gr ,F z'G x( ') −Dvà ( ', ', ', *, *)x y z k d _MW. Nếu ( ,F G) :X →2^Y2^Z là ánh xạ đa trị (KD)-tựa lồi nửa địa phương xác định trên tập hình sao S và (WSOP) thỏa định tính ràng buộc Slater dạng tổng quát thì

( ', ') x y

_là

nghiệm của bài toán (WSOP).

Chứng minh. Vì ( ', ')x y gr ,F ' ( ') −

z G x Dvà ( ', ', ', *, *)x y z k d _MWnên ( *, *)k d K⁺\ {0 }_Y* D⁺ và k*,y + d*,z 