Ðiều kiện tối ưu cho hầu tựa ε-nghiệm của bài toán tối ưu không lồi với vô hạn ràng buộc

Tạp chí ðại học Thủ Dầu Một, số 5 (24) – 2015 
 17
ðIỀU KIỆN TỐI ƯU CHO HẦU TỰA ε -NGHIỆM CỦA 
BÀI TỐN TỐI ƯU KHƠNG LỒI VỚI VƠ HẠN RÀNG BUỘC 
Trần Văn Thạch 
Trường ðại học Thủ Dầu Một 
TĨM TẮT 
Sử dụng điều kiện Karush-Kuhn-Tucker suy rộng chính xác đến ε và dựa trên tính chất 
ε -giả lồi áp dụng cho các hàm Lipschitz địa phương cĩ trong bài tốn, chúng tơi thiết lập 
một số điều kiện đủ tối ưu cho các hầu tựa ε-nghiệm của bài tốn tối ưu khơng lồi cĩ vơ 
hạn ràng buộc. 
Từ khĩa: điều kiện Karush-Kuhn-Tucker suy rộng chính xác đến ε , hầu tựa ε -nghiệm 
1. GIỚI THIỆU 
Trong bài báo này, chúng tơi thiết lập một số điều kiện tối ưu xấp xỉ cho bài tốn tối ưu 
khơng lồi. Chủ đề này đã được quan tâm bởi nhiều tác giả trong những năm gần đây như: 
[2], [3], [4], [5], [6], [7]. 
Trong tối ưu, việc tìm hiểu các nghiệm xấp xỉ của bài tốn là vấn đề cần thiết. Ngồi 
khái niệm ε -nghiệm cĩ tính chất tồn cục, cịn cĩ các khái niệm nghiệm xấp xỉ mang tính 
địa phương như: tựa ε -nghiệm, hầu tựa ε -nghiệm. Nếu như các nghiệm tối ưu của bài tốn 
lồi cĩ tính tồn cục thì đối với bài tốn khơng lồi, việc nghiên cứu về nghiệm địa phương tỏ 
ra thích hợp hơn. 
Chúng tơi xét điều kiện tối ưu cho các hầu tựa ε -nghiệm đối với bài tốn tối ưu khơng 
lồi cĩ dạng sau đây: 
t
(P) Minimize f(x)
 subject to g (x) 0, t T,
 x C,
≤ ∈
∈
trong đĩ tf ,g : X , t T→ ∈R , là các hàm Lipschit địa phương trên khơng gian Banach X, T 
là tập chỉ số cĩ thể vơ hạn, C là tập lồi đĩng trong X. Kết quả của chúng tơi được phát triển 
từ bài báo [6] và [7], ở đĩ điều kiện đủ tối ưu được thiết lập dựa trên điều kiện Karush-
Kuhn-Tucker (KKT) cùng với tính chất chính quy, tính tựa lồi và tính giả lồi áp dụng cho 
các hàm số trong bài tốn. 
2. KIẾN THỨC CƠ BẢN 
Trong bài báo này, X là khơng gian Banach, T là khơng gian tơ-pơ compact, C là tập 
lồi đĩng trong X, và f : X → R là hàm Lipschitz địa phương trên X. Giả sử rằng các hàm 
ràng buộc tg : X → R , là các hàm Lipschitz địa phương theo x đều theo t, tức là, với mỗi 
x X∈ , tồn tại lân cận U của x và hằng số K 0> sao cho 
t tg (z) g (z ') K || z z ' ||, z, z ' U, t T− ≤ − ∀ ∈ ∀ ∈ . 
Journal of Thu Dau Mot University, No 5 (24) – 2015 
 18
Các khái niệm sau đây dễ dàng tìm được trong tài liệu Clarke [1]. 
Cho f : X → R là hàm Lipschitz địa phương. 
ðạo hàm theo hướng của f tại z X∈ theo hướng d X∈ , ký hiệu f '(z;d) , được định 
nghĩa bởi 
t 0
f (z td) f (z)f '(z;d) lim
t+→
+ −
=
nếu giới hạn trên tồn tại. 
ðạo hàm Clarke theo hướng suy rộng của f tại z X∈ theo hướng d X∈ , ký hiệu 
of (z;d) , được định nghĩa o
h 0
t 0
f (z h td) f (z h)f (z;d) lim sup
t
+
→
→
+ + − +
= và dưới vi phân 
Clarke của f tại z X∈ , ký hiệu cf (z)∂ , được định nghĩa bởi 
{ }c * of (z) u X | u(d) f (z;d), d X∂ = ∈ ≤ ∀ ∈ , trong đĩ *X là khơng gian đối ngẫu của X. 
Hàm Lipschitz địa phương f được gọi là chính quy (tựa khả vi) tại z X∈ nếu f '(z;d) 
tồn tại và of (z;d) f '(z;d)= với mọi d X∈ . 
Cho C là tập con đĩng trong X và khác rỗng. Nĩn tiếp tuyến của C tại z, ký hiệu 
CT (z) được định nghĩa { }oC CT (z) x X | d (z;x) 0= ∈ = , trong đĩ Cd là hàm khoảng cách. 
Nĩn pháp tuyến của z C∈ , ký hiệu CN (z) , được định nghĩa bởi 
{ }*C CN (z) u X | u(x) 0, x T (z)= ∈ ≤ ∀ ∈ . 
Khi C là tập lồi thì CN (z) trùng với nĩn pháp tuyến thơng thường trong giải tích lồi 
{ }*CN (z) u X | u(x z) 0, x C= ∈ − ≤ ∀ ∈ . 
ðịnh nghĩa 2.1. Cho C X⊂ và f : X → R là hàm Lipschitz địa phương. 
(i). Hàm f được gọi là giả lồi tại z C∈ nếu 
c
x C : f (x) f (z), u f (z) u(x z) 0∀ ∈ < ∀ ∈∂ ⇒ − < . 
(ii). Hàm f được gọi là tựa lồi tại z C∈ nếu 
c
x C : f (x) f (z), u f (z) u(x z) 0∀ ∈ ≤ ∀ ∈∂ ⇒ − ≤ . 
ðịnh nghĩa 2.2. Cho C X⊂ và 0ε ≥ . Một hàm f : X → R gọi là ε -giả lồi tại z C∈ 
nếu thỏa mãn 2 điều kiện sau: 
(i). f là hàm Lipschitz địa phương tại z; 
(ii). od X : z d C, f (z;d) d 0 f (z d) d f (z)∀ ∈ + ∈ + ε ≥ ⇒ + + ε ≥ . 
ðịnh nghĩa 2.3. Cho C là tập con trong X và 0ε ≥ . Một hàm f : X → R được gọi là 
ε -nửa lồi tại z C∈ nếu thỏa mãn 2 điều kiện sau: 
(i). f chính quy tại z, 
(ii). od X : z d C, f (z;d) d 0 f (z d) d f (z)∀ ∈ + ∈ + ε ≥ ⇒ + + ε ≥ . 
Khi 0ε = thì hàm f trong định nghĩa trên, được gọi là hàm nửa lồi tại z. 
Chúng tơi sử dụng khơng gian tuyến tính (T)R , là tập hợp các dãy suy rộng 
t t T( ) ∈λ = λ , trong đĩ những t 0λ ≠ nhiều lắm là hữu hạn. Với (T)t( )λ = λ ∈ R , giá của λ 
được ký hiệu T( )λ , là tập hợp được xác định bởi { }tT( ) t T | 0λ = ∈ λ ≠ . 
Tạp chí ðại học Thủ Dầu Một, số 5 (24) – 2015 
 19
Hiển nhiên T( )λ là tập con hữu hạn của T. Nĩn khơng âm trong (T)R , ký hiệu (T)+R 
được xác định bởi { }(T) (T)t t( ) | 0, t T+ = λ ∈ λ ≥ ∀ ∈R R . 
Dễ thấy rằng tập hợp (T)+R là một nĩn lồi trong 
(T)R . Khơng gian (T)R được trang bị 
chuẩn 1 . , xác định như sau: 
(T)
t t1
t T t T( )
: , 
∈ ∈ λ
λ = λ = λ ∀λ ∈∑ ∑ R . 
Với (T)λ ∈ R và tg , t T∈ , là những hàm Lipschitz địa phương trên X, chúng ta quy 
ước: 
t t
t T( )t t
t T
g khi T( ) ,
g :
0 khi T( ) .
∈ λ
∈
 λ λ ≠ ∅
λ = 
 λ = ∅
∑
∑ 
Với bài tốn (P), ký hiệu A là tập chấp nhận của (P), được xác định bởi 
{ }tA x X | g (x) 0, t T= ∈ ≤ ∀ ∈ . 
Cho 0ε ≥ , tập ε -chấp nhận của bài tốn (P), ký hiệu Aε , được xác định bởi 
{ }tA x X | g (x) , t Tε = ∈ ≤ ε ∀ ∈ . 
ðịnh nghĩa 2.4. Cho 0ε ≥ . Phần tử z Aε∈ được gọi là: 
(i). một hầu ε -nghiệm của bài tốn (P) nếu f (z) f (x) , x A≤ + ε ∀ ∈ ; 
(ii). một hầu tựa ε -nghiệm của bài tốn (P) nếu f (z) f (x) x z , x A≤ + ε − ∀ ∈ . 
3. MỘT SỐ KẾT QUẢ 
ðể thiết lập các điều kiện đủ cho hầu tựa ε -nghiệm của bài tốn (P), chúng tơi nhắc lại 
một vài kết quả trong [6]. Chúng ta ký hiệu ( )A là điều kiện mà nĩ thỏa mãn ít nhất một 
trong hai điều kiện sau: 
(a1). X tách được; 
(a2). X mêtric hĩa được và c tg (x)∂ là “nửa liên tục trên” theo t T∈ với x X∈ . 
Mệnh đề 3.1 [6, Theorem 4.1]. Cho 0ε ≥ và z Aε ∈ là ε -tựa nghiệm của (P). Giả 
thiết rằng điều kiện ( )A được thỏa mãn. Nếu điều kiện sau đây được thỏa mãn 
{ }oC t td T (z ) : g (z ;d) 0, t I(z ) t T | g (z ) 0ε ε ε ε∃ ∈ < ∀ ∈ = ∈ = , 
và bao lồi của tập { }c t Cg (x) | t T (z )ε∪∂ ∈ là đĩng yế *u , thì tồn tại (T)+λ ∈ R sao cho 
c c *
t t C t
t T
0 f (z ) g (z ) N (z ) B , g (z ) 0, t T( )ε ε ε ε
∈
∈∂ + λ ∂ + + ε = ∀ ∈ λ∑ , (3.1) 
trong đĩ *B là hình cầu đơn vị đĩng trong *X . 
Nếu cặp (z , )ε λ thỏa mãn điều kiện (3.1) thì nĩ được gọi là cặp Karush-Kuhn-Tucker 
(KKT) chính xác đến ε . Mở rộng khái niệm này, ta cĩ định nghĩa sau đây. 
ðịnh nghĩa 3.1. Cho 0ε ≥ . Cặp (T)(z , ) Aε ε +λ ∈ × R được gọi là thỏa điều kiện KKT 
suy rộng chính xác đến ε nếu 
Journal of Thu Dau Mot University, No 5 (24) – 2015 
 20
c c *
t t C t
t T
0 f (z ) g (z ) N (z ) B , g (z ) 0, t T( )ε ε ε ε
∈
∈ ∂ + λ ∂ + + ε ≥ ∀ ∈ λ∑ , trong đĩ *B 
là hình cầu đơn vị đĩng trong *X . Khi đĩ cặp (z , )ε λ được gọi là cặp KKT suy rộng chính 
xác đến ε . Nĩ được gọi là chặt nếu tg (z ) 0, t T( )ε > ∀ ∈ λ . 
Sự hợp lý của định nghĩa cặp KKT suy rộng này dựa trên một định lý đã được giới 
thiệu trong bài báo [6], ở đĩ đã chỉ ra sự tồn tại của điều kiện 
c c *
t t C
t T
0 f (z ) g (z ) N (z ) Bε ε ε
∈
∈ ∂ + λ ∂ + + ε∑ nếu zε là một hầu tựa ε -nghiệm của 
(P). Từ đĩ cặp KKT suy rộng chính xác đến ε được dùng để khảo sát nghiệm tối ưu xấp xỉ 
của bài tốn (P). 
ðịnh lý 3.1 [6, Theorem 4.3]. Với bài tốn (P), giả thiết rằng C là tập con lồi trong X 
và tg , t T∈ , là các hàm lồi. Cho 0ε ≥ và 
(T)(z , ) Aε ε +λ ∈ × R là cặp KKT suy rộng chính 
xác đến ε . Nếu f là hàm ε -nửa lồi tại zε tương ứng với C, thì 
f (z ) f (x) x z , x Cε ε≤ + ε − ∀ ∈ sao cho t tg (x) g (z ), t T( )ε≤ ∀ ∈ λ . 
ðặc biệt, zε là một hầu tựa ε -nghiệm của bài tốn (P). 
ðầu tiên chúng tơi làm yếu giả thiết trong ðịnh lý 3.1, bằng cách mở rộng hàm mục 
tiêu từ ε -nửa lồi thành ε -giả lồi; đồng thời thay các hàm ràng buộc từ các hàm lồi bởi các 
hàm chính quy và tựa lồi. 
ðịnh lý 3.2. Với bài tốn (P), cho 0ε ≥
và (T)(z , ) Aε ε +λ ∈ × R , là cặp KKT suy rộng 
chính xác đến ε . Giả sử rằng C là tập lồi trong X, f là hàm ε -giả lồi tại zε và tg , t T∈ , là 
các hàm chính quy và tựa lồi tại zε . Khi đĩ f (z ) f (x) x z , x Cε ε≤ + ε − ∀ ∈
sao cho 
t tg (x) g (z ), t T( )ε≤ ∀ ∈ λ . 
ðặc biệt, zε là một hầu tựa ε -nghiệm của bài tốn (P). 
Chứng minh. 
Giả sử (T)(z , ) Aε ε +λ ∈ × R là cặp KKT suy rộng chính xác đến ε . Ta cĩ 
c c *
t t C t
t T
0 f (z ) g (z ) N (z ) B , g (z ) 0, t T( )ε ε ε ε
∈
∈ ∂ + λ ∂ + + ε ≥ ∀ ∈ λ∑ . 
Khi đĩ, tồn tại c c *t t Cu f (z ); v g (z ), t T; w N (z ); s Bε ε ε∈ ∂ ∈ ∂ ∈ ∈ ∈ , 
sao cho t t
t T
u v w .s 0
∈
+ λ + + ε =∑ . 
Vì { }* *s B v X | v(x) x , x X∈ = ∈ ≤ ∀ ∈ nên s(x z ) x z , x Cε ε− ≤ − ∀ ∈ . 
Vì { }*Cw N (z ) v X | v(x z ) 0, x Cε ε∈ = ∈ − ≤ ∀ ∈ nên w(x z ) 0, x Cε− ≤ ∀ ∈ . 
Kết hợp các bất đẳng thức trên ta được 
t t
t T
u(x z ) v (x z ) . x z 0, x Cε ε ε
∈
− + λ − + ε − ≥ ∀ ∈∑ . (3.2) 
Lấy x C∈ sao cho t tg (x) g (z ), t T( )ε≤ ∀ ∈ λ . 
Vì ct tv g (z ), t Tε∈ ∂ ∀ ∈ và tg , t T∈ , là những hàm tựa lồi tại zε , 
Tạp chí ðại học Thủ Dầu Một, số 5 (24) – 2015 
 21
nên theo ðịnh nghĩa 2.1, ta cĩ tv (x z ) 0, t T( )ε− ≤ ∀ ∈ λ . (3.3) 
Mặt khác, vì cu f (z )ε∈ ∂ nên ou(x z ) f (z ;x z )ε ε ε− ≤ − . (3.4) 
Kết hợp các kết quả (3.2), (3.3) và (3.4), ta được 
of (z ;x z ) x z 0ε ε ε− + ε − ≥ . 
Do f là hàm ε -giả lồi tại zε ,
nên theo ðịnh nghĩa 2.2, ta cĩ 
f (x) x z f (z )ε ε+ ε − ≥ . 
Vậy f (z ) f (x) x z , x Cε ε≤ + ε − ∀ ∈ (3.5) 
thỏa mãn t tg (x) g (z ), t T( )ε≤ ∀ ∈ λ . 
Vì A C⊂ nên bất đẳng thức (3.5) cũng đúng với mọi x A∈ . 
Vậy, theo ðịnh nghĩa 2.4, zε là một hầu tựa ε -nghiệm của bài tốn (P). 
Nhận xét. Một hàm lồi cũng là một hàm chính quy và tựa lồi. Một hàm ε -nửa lồi 
cũng là một hàm ε -giả lồi. Nên ðịnh lý 3.1 được xem là một hệ quả của ðịnh lý 3.2. 
Sau đây, chúng tơi nhắc lại khái niệm hàm Lagrange, nhằm vận dụng vào định lý sau. 
Hàm Lagrange L(., )λ tương ứng với bài tốn (P) được định nghĩa bởi 
(T)
t t
t T
(T)
f (x) g (x), khi (x, ) C
L(x, )
, khi (x, ) C .
+
∈
+
 + λ λ ∈ ×
λ = 
+∞ λ ∉ ×
∑ R
R
Bây giờ chúng tơi giảm nhẹ giả thiết trong ðịnh lý 3.1, cho các hàm ràng buộc, đồng 
thời trang bị thêm hàm Lagrange thỏa mãn tính ε -giả lồi, khi đĩ chúng tơi cũng đưa ra điều 
kiện đủ cho sự tồn tại nghiệm tối ưu cĩ tính địa phương. 
ðịnh lý 3.3. Với bài tốn (P), cho 0ε ≥ và (T)(z , ) Aε ε +λ ∈ × R là cặp KKT suy rộng 
chính xác đến ε . Giả sử rằng C là tập lồi trong X và f , tg , t T∈ , là các hàm chính quy tại 
zε . Nếu hàm L(., )λ là ε -giả lồi tại zε thì 
f (z ) f (x) x z , x Cε ε≤ + ε − ∀ ∈
sao cho t tg (x) g (z ), t T( )ε≤ ∀ ∈ λ . 
ðặc biệt, zε là một hầu tựa ε -nghiệm của bài tốn (P). 
Chứng minh. 
Giả sử (T)(z , ) Aε ε +λ ∈ × R là cặp KKT suy rộng chính xác đến ε . Lập luận như trong 
chứng minh (phần đầu) của ðịnh lý 3.2, tồn tại 
c c *
t t Cu f (z ); v g (z ), t T; w N (z ); s Bε ε ε∈ ∂ ∈ ∂ ∈ ∈ ∈ , thỏa mãn 
t t
t T
u ( x z ) v ( x z ) . x z 0 , x Cε ε ε
∈
− + λ − + ε − ≥ ∀ ∈∑ . 
Lấy x C∈ sao cho t tg (x) g (z ), t T( )ε≤ ∀ ∈ λ . 
Vì cu f (z )ε∈ ∂ và ct tv g (z ), t Tε∈ ∂ ∀ ∈ , nên 
ou(x z ) f (z ;x z )ε ε ε− ≤ − và ot tv (x z ) g (z ;x z ), t Tε ε ε− ≤ − ∀ ∈ . 
Kết hợp các tính chất trên, ta được 
o o
t t
t T
f (z ;x z ) g (z ;x z ) x z 0ε ε ε ε ε
∈
− + λ − + ε − ≥∑ . 
Journal of Thu Dau Mot University, No 5 (24) – 2015 
 22
Hay oL (., )(z ;x z ) x z 0ε ε ελ − + ε − ≥ . 
Vì L(., )λ là hàm ε -giả lồi tại zε , nên ta nhận được 
L(., )(x) x z L(., )(z )ε ελ + ε − ≥ λ . 
Hay 
t t t t
t T( ) t T( )
f (x) g (x) x z f (z ) g (z )ε ε ε
∈ λ ∈ λ
+ λ + ε − ≥ + λ∑ ∑ . 
Vì t tg (x) g (z ), t T( )ε≤ ∀ ∈ λ , nên suy ra f (x) x z f (z )ε ε+ ε − ≥ . 
Vậy, f (z ) f (x) x z , x Cε ε≤ + ε − ∀ ∈
thỏa mãn t tg (x) g (z ), t T( )ε≤ ∀ ∈ λ . 
Vì A C⊂ nên bất đẳng thức nêu trên cũng đúng với mọi x A∈ . 
Do đĩ, zε là một hầu tựa ε -nghiệm của bài tốn (P). 
Nhận xét. Vì một hàm ε -nửa lồi cũng là một hàm ε -giả lồi, nên hệ quả sau đây được 
suy ra trực tiếp từ ðịnh lý 3.3. 
Hệ quả 3.1. Với bài tốn (P), cho 0ε ≥ và (T)(z , ) Aε ε +λ ∈ × R là cặp KKT suy rộng 
chính xác đến ε . Giả sử rằng C là tập lồi trong X và f , tg , t T∈ , là các hàm chính quy tại 
zε . Nếu hàm L(., )λ là ε -nửa lồi tại zε thì 
f (z ) f (x) x z , x Cε ε≤ + ε − ∀ ∈
sao cho t tg (x) g (z ), t T( )ε≤ ∀ ∈ λ . 
ðặc biệt, zε là một hầu tựa ε -nghiệm của bài tốn (P). 
Chú ý. Ngồi cách áp dụng ðịnh lý 3.3, để suy ra Hệ quả 3.1, chúng tơi cịn phát biểu 
và chứng minh trực tiếp (kết quả này), trong bài báo [7] (Theorem 3.3), năm 2012. 
OPTIMALITY CONDITIONS FOR ALMOST ε -QUASISOLUTIONS OF 
A NONCONVEX OPTIMIZATION PROBLEM WITH AN INFINITE NUMBERS 
OF CONSTRAINTS 
Tran Van Thach 
Thu Dau Mot University 
ABSTRACT 
Using a condition of generalized Karush-Kuhn-Tucker pair up to ε and based on a 
property of ε-pseudoconvex applied for locally Lipschitz functions involved, we established 
some sufficient optimality conditions for almost ε-quasisolutions of a nonconvex 
optimization problem which has an infinite numbers of constraints. 
TÀI LIỆU THAM KHẢO 
[1] Clarke F.H., Optimization and non smooth analysis, Willey-Interscience, New York (1983). 
[2] Dinh N. and Son T.Q., Approximate optimality condition and duality for convex infinite 
programming problems, J. Science and Technology Development, Vol. 10, pp. 29-38, 2007. 
[3] Loridan P., Necessary conditions for ε -optimality, Math. Program. Study, Vol. 19, pp. 140-
152, 1982. 
[4] Strodiot J.J., Nguyen V.H., and Heukemes N., ε -Optimal Solutions in Nondifferentiable Convex 
Programming and Some Related Questions, Math. Programming, Vol. 25, pp. 307-328, 1983. 
Tạp chí ðại học Thủ Dầu Một, số 5 (24) – 2015 
 23
[5] Son T.Q., Dinh N., Characterizations of Optimal Solution Sets of Convex Infinite Programs, 
TOP, 16, pp. 147-163, 2008. 
[6] Son T.Q., Strodiot J.J., Nguyen V.H., ε -Optimality and ε -Lagrangian duality for a 
nonconvex programming problem with an infinite number of constraints, J. Optim. Theory 
Appl., Vol. 141, pp. 389-409, 2009. 
[7] Thach T.V. and Son T.Q., Almost ε -quasisolutions of nonconvex problem with an infinte 
number of constraints, J. Science & Technology Development, Vol. 15, pp. 57-68, 2012.