Điều kiện chính quy cho bài toán tối ưu DC với ràng buộc hệ bất phương trình lồi và tập lồi
Trong bài báo này, chúng tôi xây dựng điều kiện chính quy cần và đủ để có điều kiện tối ưu cho
bài toán tối ưu DC với ràng buộc hệ bất phương trình lồi và một tập lồi. Đồng thời, chúng tôi cũng
thiết lập điều kiện chính quy cần và đủ để có điều kiện tối ưu cho bài toán tối ưu phân thức và bài
toán tối ưu lồi yếu với ràng buộc hệ bất phương trình lồi và một tập lồi
Trang 1
Trang 2
Trang 3
Trang 4
Trang 5
Trang 6
Bạn đang xem tài liệu "Điều kiện chính quy cho bài toán tối ưu DC với ràng buộc hệ bất phương trình lồi và tập lồi", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
Tóm tắt nội dung tài liệu: Điều kiện chính quy cho bài toán tối ưu DC với ràng buộc hệ bất phương trình lồi và tập lồi
kết quả này để chứng minh điều kiện qualification). BCQ lần đầu được giới thiệu bởi cần và đủ để có điều kiện tối ưu cho bài toán tối Hiriart-Urruty và Lemaréchal [5]. Sau đó khái ưu phân thức và bài toán tối ưu lồi yếu với ràng niệm này đã được mở rộng nghiên cứu bởi các tác buộc hệ bất phương trình lồi và tập lồi. giả [3], [4]. Li và các cộng sự [6] đã nghiên cứu Một điều cần lưu ý ở đây rằng, trong trường điều kiện chính quy BCQ cho bài toán tối ưu với hợp tổng quát, bài toán (1.2) không thể đưa về ràng buộc hệ bất phương trình lồi và đã chứng tỏ bài toán (1.1) do tập A không cần đóng. BCQ là điều kiện chính quy cần và đủ để có điều Tương tự trong [9], bài báo thiết lập và kiện tối ưu toàn cục của lớp bài toán này. chứng minh rằng BCQ tương ứng với tập tại Năm 2011, Saeki và các cộng sự [9] đã xét một điểm là điều kiện chính quy cần và đủ để có bài toán tối ưu DC như sau điều kiện tối ưu của bài toán tối ưu DC (1.2). min f ( x ) g ( x ), Đồng thời, chúng tôi cũng thiết lập điều kiện (1.1) chính quy cần và đủ để có điều kiện tối ưu cho (x ) 0, i I , i bài toán tối ưu phân thức và bài toán tối ưu lồi trong đó f,i : X { }, i I , là các hàm yếu với ràng buộc hệ bất phương trình lồi và lồi, chính thường, nửa liên tục dưới và một tập lồi. Cuối cùng chúng tôi đưa ra một ví gX:{} là hàm lồi, nửa liên tục dưới, dụ cho kết quả đạt được. Trước tiên, chúng tôi trình bày một số khái X là không gian vectơ tôpô Hausdorff lồi địa phương, I là tập chỉ số bất kỳ. Các tác giả đã niệm và tính chất quan trọng trong tối ưu lồi mà chứng tỏ được BCQ là điều kiện chính quy cần và chúng tôi sử dụng trong bài báo này (xem [5], đủ để có điều kiện tối ưu cho bài toán tối ưu DC [6], [8]). (1.1). Đồng thời, họ cũng áp dụng kết quả đạt 1. Mở đầu được để nghiên cứu bài toán tối ưu phân thức và Cho X là không gian vectơ tôpô Hausdorff * bài toán tối ưu lồi yếu, hai bài toán này sẽ được lồi địa phương và X là không gian đối ngẫu của * ** chúng tôi trình bày chi tiết trong các mục sau. X. Kí hiệu xx, chỉ giá trị của hàm xX tại xX . (*) Trường Đại học Đồng Tháp. 64 TRÖÔØNG ÑAÏI HOÏC ÑOÀNG THAÙP Taïp chí Khoa hoïc soá 37 (04-2019) Giả sử KX , tích của tập và tập K (2) Lớp các hàm {,}i iI thỏa mãn BCQ được xác định bởi tương ứng tập A tại x S A nếu ** K { ta : t , a K }. N( S A ,)coneco x () x N (,) A x Qui ước K {0} nếu K . i i I() x Hàm chỉ của tập K, kí hiệu K , được định trong đó I( x ) { i I ,i ( x ) 0}. nghĩa như sau Nhận xét 1.5 ([6]). Vì 0, xK , ()x K N( S A ,)coneco x () x N (,) A x , xK . i i I() x Định nghĩa 1.1 ([8]). Cho tập con lồi nên lớp các hàm {:} iI thỏa mãn BCQ tương của X và x . Khi đó nón pháp tuyến của tập i tại x, kí hiệu N( ,x ), được định nghĩa ứng A tại x S A nếu và chỉ nếu như sau N( S A , x ) coneco ( x ) N ( A , x ). *** i N(,):{ x x X |, x x x 0, x }. i I() x Định nghĩa 1.2 ([8]). Cho hàm Kí hiệu: ()I : X { }. Khi đó { ( i ) i I | i 0 i I ,card{ i I | i 0} }. (1) Miền hữu hiệu của hàm , kí hiệu Saeki và các cộng sự [9] đã xây dựng điều kiện dom , được định nghĩa như sau cần và đủ để có điều kiện tối ưu cho bài toán tối dom {x X | ( x ) }. ưu DC (1.1) như sau. Định lí 1.6 ([9]). Giả sử {,} iI là lớp các (2) Hàm được gọi là chính thường nếu i hàm lồi, chính thường, nửa liên tục dưới từ X dom . tới {} và xS . Khi đó các mệnh đề sau (3) Tập hợp trên đồ thị của , kí hiệu đây là tương đương: epi , được định nghĩa như sau (1) Lớp các hàm {,}i iI thỏa mãn điều epi {(x , ) X | x dom , ( x ) }. kiện BCQ tại x. (4) Hàm liên hợp của , kí hiệu: (2) Giả sử f là hàm lồi, chính thường, nửa **:X { }, được xác định như sau liên tục dưới từ X tới {} sao cho *** ** ** (x ) sup{ x , x ( x ), x X }, xX . dom fS và epif epiS đóng yếu* và Định nghĩa 1.3 ([8]). Cho hàm giả sử gX: là hàm lồi, nửa liên tục dưới. : X {} là hàm lồi, chính thường và Khi đó nếu x là nghiệm địa phương của fg x dom . Dưới vi phân của tại x, kí hiệu trong S thì với mỗi v g() x tồn tại (x ), được xác định bởi () ()I sao cho (x ) 0 với mỗi iI và i i I ii (){x x*** X |, x x x ()()}. x x v f( x ) ii ( x ). Trong bài toán (1.2), gọi iI S: { x X | ( x ) 0, i I } và giả sử SA . Điều kiện cần cho nghiệm địa phương của i bài toán tối ưu DC không ràng buộc được giới Các tác giả trong [3], [6] đã giới thiệu khái niệm thiệu bởi Hiriart-Urruty [6] như sau. BCQ và BCQ tương ứng một tập như sau. Định lí 1.7 ([5]). Giả sử fX:{} Định nghĩa 1.4 ([3]). (1) Lớp các hàm là hàm lồi, chính thường, nửa liên tục dưới và {,}i iI thỏa mãn BCQ tại xS nếu gX: là hàm lồi, nửa liên tục dưới. Nếu N( S , x ) cone co ( x ) . xX là nghiệm địa phương của fg trong i i I() x X thì g( x ) f ( x ). 65 TRÖÔØNG ÑAÏI HOÏC ÑOÀNG THAÙP Taïp chí Khoa hoïc soá 37 (04-2019) Sử dụng các lập luận trong [6, page 14], nghiệm địa phương của ()fg SA trong X. chúng tôi có bổ đề sau. Bổ đề này được sử dụng Theo Định lí 1.7, ta có trong chứng minh kết quả chính của chúng tôi. g( x ) ( f )( x ). Bổ đề 1.8 ([6]). Giả sử fX:{} SA Theo Bổ đề 1.8, ta có là hàm lồi, chính thường, nửa liên tục dưới, A là (()()()f ) x f x x một tập lồi sao cho dom fA và SASA f()(,) x N S A x ** epif epi A đóng yếu*. Khi đó với mỗi f()(,) x N S A x x dom f A , ta có f( x ) coneco ( x ) N ( A , x ) (f ) ( x ) f ( x ) ( x ). i AA i I() x 2. Kết quả chính f()()(,) x ii x N A x . Trong định lí sau đây, chúng tôi thiết lập và i I() x chứng minh rằng BCQ tương ứng với tập A tại Đặt i 0 nếu i I I( x ), khi đó một điểm là điều kiện chính quy cần và đủ để có fx() i i ()(,) xNAxfx () i i ()(,). xNAx điều kiện tối ưu của bài toán tối ưu DC (1.2). i I() x i I Định lí 2.1. Giả sử {,}i iI là lớp các hàm Do đó (2) thỏa mãn. lồi, chính thường, nửa liên tục dưới từ X tới (2) (1). Giả sử (2) thỏa mãn và lấy * * {} và x S A. Khi đó các mệnh đề x N( S A , x ). Khi đó x, x x 0, sau đây là tương đương: ** x S A. Tương đương, x( x ) x ( x ), (1) Lớp các hàm {,}i iI thỏa mãn điều x S A. Khi đó x là nghiệm địa phương của kiện BCQ tương ứng tập A tại x. x* trong SA . Đặt fx * và g 0, khi đó (2) Giả sử f hàm lồi, chính thường, nửa x là nghiệm địa phương của fg trong liên tục dưới từ X tới {} sao cho ()I SA . Do đó tồn tại ()i i I sao cho ** dom f S A và epif epiSA đóng ii(x ) 0 với mọi iI và yếu* và giả sử gX: là hàm lồi, nửa liên * 0 x ii ( x ) N ( A , x ). tục dưới. Khi đó nếu x là nghiệm địa phương iI của fg trong SA thì với mỗi v g() x Do đó ()I x* () xNAx (,) () xNAx (,)coneco () xNAx (,), tồn tại ()i i I sao cho ii(x ) 0 với mỗi i i i i i i I i I() x i I() x iI và nên ta có v f( x ) ii ( x ) N ( A , x ). iI N( S A , x ) coneco ( x ) N ( A , x ). i Chứng minh. (1) (2). Giả sử {,}i iI i I() x thỏa mãn điều kiện BCQ tương ứng tập A tại x, Do đó, lớp các hàm {,}i iI thỏa mãn điều kiện nghĩa là BCQ tương ứng tập A tại x. Vậy (1) thỏa mãn. Tiếp theo chúng tôi sẽ áp dụng kết quả của N( S A , x ) coneco ( x ) N ( A , x ). i Định lý 2.1 để thiết lập điều kiện cần và đủ để i I() x có điều kiện tối ưu cho bài toán tối ưu phân Giả sử fX:{} sao cho thức với ràng buộc hệ bất phương trình lồi và ** tập lồi như sau dom f S A và epif epiSA là đóng fx() yếu*, gX: là hàm lồi, nửa liên tục dưới. min , gx() Vì x là nghiệm địa phương của của fg trong SA nên x là nghiệm địa phương của i (x ) 0, i I , ()fg SA trong X và do đó x cũng là xA , 66 TRÖÔØNG ÑAÏI HOÏC ÑOÀNG THAÙP Taïp chí Khoa hoïc soá 37 (04-2019) trong đó fX:{} là hàm lồi, chính phương của f(), x x* x x trong SA , thường, nửa liên tục dưới, không âm trên SA suy ra 0 f ( x ) x**, x x,,. x x S A và gX: là hàm lồi, dương trên SA . Do đó, x* N(,) S A x và theo giả thiết (2), Định lí 2.2. Giả sử {,}i iI là lớp các tồn tại () ()I sao cho (x ) 0 và hàm lồi, chính thường, nửa liên tục dưới từ X i i I ii Do đó 0 x* ( x ) N ( A , x ), nên tới {} và x S A. Khi đó các mệnh đề ii sau đây là tương đương: iI (1) Lớp các hàm {,} iI thỏa mãn điều i x* coneco ( x ) N ( A , x ). i kiện BCQ tương ứng tập A tại x. i I() x (2) Giả sử f là hàm lồi, chính thường, nửa Tiếp theo, chúng tôi áp dụng Định lí 2.1 cho liên tục dưới từ X tới {} sao cho bài toán tối ưu lồi yếu với ràng buộc hệ bất dom f S A và epif ** epi đóng phương trình lồi và tập lồi trong không gian SA Banach thực, trơn. Trước hết, chúng tôi trình bày yếu*, f không âm trên SA và gX: là một số khái niệm sử dụng trong mục này. một hàm lồi, nửa liên tục dưới và dương trên Cho X là không gian Banach thực với SA . Khi đó nếu x là nghiệm địa phương của chuẩn .. Để tiện lợi, chúng tôi cũng kí hiệu fx() * * trong SA thì tồn tại 0 0 sao cho với chuẩn trong X là .. Ánh xạ đa trị JXX: gx() ()I định nghĩa như sau mỗi v 0 g() x tồn tại ()i i I sao cho 2 J( x ) { x**** X | x , x x2 x }, x X . ii(x ) 0 với mỗi iI và Gọi BX(Xx ) { |x 1} là hình cầu v f( x ) ii ( x ) N ( A , x ). iI đơn vị trong X. Khi đó X được gọi là trơn nếu fx() Chứng minh. (1) (2). Đặt . x ty x 0 gx() giới hạn lim tồn tại với mỗi t 0 t fx() x, y B ( X ). Trong trường hợp này, vì ánh xạ Khi đó, với mỗi x S A, ta có 0 . gx() đối ngẫu J của X là đơn trị nên tập Jx() được Suy ra xác định chỉ một phần tử Jx() với mỗi xX . 0 g ( x ) f ( x ) Một hàm g được gọi là lồi yếu nếu nó có 0 g()()()() x f x f x f x 2 thể được viết dưới dạng gh . với h là 00g( x ) g ( x ) f ( x ) f ( x ). 2 một hàm lồi và 0. Chúng ta xét bài toán lồi Do đó (f 00 g )( x ) ( f g )( x ), x S A . yếu sau đây Suy ra x là nghiệm địa phương của fg 0 2 trong SA . Theo Định lí 2.1, với mỗi minf ( x ) x , ()I 2 v g() x tồn tại () sao cho 0 i i I (x ) 0, i I , (x ) 0 với mỗi iI và i ii xA , v f( x ) ( x ) N ( A , x ). ii trong đó fX:{} là hàm lồi, chính iI (2) (1). Đặt f(), x x* x x và thường, nửa liên tục dưới, 0. Chúng tôi có kết quả sau đây trong không gx( ) 1, x S A. Khi đó, vì x là nghiệm gian Banach trơn. fx() địa phương của , ta có x là nghiệm địa Định lí 2.3. Giả sử {,}i iI là lớp các hàm gx() lồi, chính thường, nửa liên tục dưới từ X tới 67 TRÖÔØNG ÑAÏI HOÏC ÑOÀNG THAÙP Taïp chí Khoa hoïc soá 37 (04-2019) {} , X trơn và x S A. Khi đó các Theo Định lí 2.1, ta có {,}i iI thỏa mãn mệnh đề sau đây là tương đương: điều kiện BCQ tương ứng A tại x. (1) Lớp các hàm {,}i iI thỏa mãn điều Ví dụ 2.4. Xét bài toán tối ưu DC sau đây 11 kiện BCQ tương ứng tập A tại x. min |x |32 | x | x , (2) Giả sử f hàm lồi, chính thường, nửa 32 liên tục dưới từ tới {} sao cho max{0, x } 0, ** x [ 1,1). dom f S A và epif epiSA đóng 1 yếu* và 0. Khi đó nếu x là nghiệm địa Ta có X , I 1, f ( x ) | x |3 | x |, 2 3 phương của f() x x trong SA thì tồn tại 2 1, 1(xx ) max{0, }, S [0, ), A [ 1,1). ()I ()i i I sao cho ii(x ) 0 với mỗi iI và Khi đó f và 1 là các hàm lồi, liên tục và {} thỏa mãn BCQ tại mọi điểm của SA . Giả J( x ) f ( x ) ii ( x ) N ( A , x ). 1 iI 1 sử x là nghiệm của f() x x2. Theo Định lí Chứng minh. Từ X là không gian Banach 2 trơn, suy ra J là hàm đơn trị. Đặt 2.3, tồn tại 1 0 sao cho x f()()(,) x 11 x N A x 2 g()xx , x SA . Khi đó, ta có và (x ) 0. Khi x 0, từ f( x ) x 2 {1} 2 11 và (x ) {0} và N( A , x ) {0}, ta có g( x ) J ( x ). Theo Định lí 2.1, ta có 1 xx 2 {1}, x là nghiệm của phương trình J( x ) f ( x ) ii ( x ) N ( A , x ). 2 iI xx 1 0, phương trình này vô nghiệm trên 2 2 Ngược lại, lại đặt g()xx , x SA . . Khi x 0, từ 1(xx ) [ 1,1] và 2 (x ) [ 1,0] và N( A , x ) {0}, ta có Theo giả thiết (2), ta có 1 0 [ 1,1] 11 [ 1,0] [ 1 ,1] và 0 là nghiệm J( x ) f ( x ) ii ( x ) N ( A , x ). iI toàn cục của bài toán./. Tài liệu tham khảo [1]. L. T. H. An, P. D. Tao, and D. N. Hao (2003), “Solving an inverse problem for an elliptic equation by DC programming”, J. Glob. Optim., (25), pp. 407-423. [2]. L. T. H. An and P. D. Tao (2005), “The DC (difference of convex functions) programming and DCA revisited with DC models of real world non-convex optimization problems”, Ann. Oper. Res., (133), pp. 23-46. [3]. H. Bauschke, J. Borwein, and W. Li (1999), “Strong conical hull intersection property, bounded linear regularity, Jameson’s property (G), and error bounds in convex optimization”, Math. Program., (86), pp. 135-160. [4]. H. H. Bauschke, J. M. Borwein, and W. Li (2002), “Nonlinearly constrained best approximation in Hilbert space: The strong chip and the basic constraint qualification”, SIAM J. Optim., (13), pp. 228-239. [5]. J. B. Hiriart-Urruty and C. Lemaréchal (1993), Convex analysis and minimization algorithmsi, Springer-Verlag, Berlin, Heidelberg, Germany. [6]. C. Li, K. F. Ng, and T. K. Pong (2008), “Constraint qualifications for convex inequality systems with applications in constrained optimization”, SIAM J. Optim., (19), pp. 163-187. [7]. V. Jeyakumar, A. Rubinov, B.M. Glover, and Y. Ishizuka (1996), “Inequality systems and global optimization”, J. Math. Anal. Appl., (202), pp. 900-919. 68 TRÖÔØNG ÑAÏI HOÏC ÑOÀNG THAÙP Taïp chí Khoa hoïc soá 37 (04-2019) [8]. J. Peypouquet, Convex optimization in normed spaces: Theory, methods and examples (2015), Springer, Cham. [9]. Y. Saeki, S. Suzuki and D. Kuroiwa (2011), “A necessary and sufficient constraint qualification for DC programming problems with convex inequality constraints”, Scientiae Mathematicae Japonicae, pp. 169-174. [10]. M. V. Ramana, L. Tucel, and H. Wolewicz (1997), “Strong duality for semi-definite grogramming”, SIAMJ. Optim., (7), pp. 644-662. THE CONSTRAINT QUALIFICATION FOR DC PROGRAMMING PROBLEMS WITH CONVEX SET CONSTRAINTS Summary In this paper, we provide a necessary and sufficient constraint qualification for optimal conditions in DC programming problems with constraints of convex inequality systems and a convex set. We also set up necessary and sufficient qualifications for optimal conditions in fractional and weakly convex programming problems with constraints of convex inequality systems and a convex set. Keywords: BCQ, convex inequality and convex set, weakly convex, fractional, necessary and sufficient qualification. Ngày nhận bài: 21/02/2019; Ngày nhận lại: 16/4/2019; Ngày duyệt đăng: 19/4/2019. 69
File đính kèm:
- dieu_kien_chinh_quy_cho_bai_toan_toi_uu_dc_voi_rang_buoc_he.pdf