Điều kiện hữu hiệu cho bài toán tối ưu không lồi thông qua đạo hàm trên

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST

Báo xấu

3
lượt xem 0
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết này nghiên cứu điều kiện hữu hiệu cần và điều kiện hữu hiệu đủ cho nghiệm cực tiểu toàn cục của bài toán tối ưu không lồi (P) có điều kiện bao gồm ràng buộc bất đẳng thức và ràng buộc tập thông qua các đạo hàm trên.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Điều kiện hữu hiệu cho bài toán tối ưu không lồi thông qua đạo hàm trên

38 Nguyễn Thị Hải Yến, Trần Hoàng Tiến Thành ĐIỀU KIỆN HỮU HIỆU CHO BÀI TOÁN TỐI ƯU KHÔNG LỒI THÔNG QUA ĐẠO HÀM TRÊN EFFICIENCY CONDITIONS FOR NONCONVEX OPTIMIZATION PROBLEMS VIA EPIDERIVATIVES Nguyễn Thị Hải Yến1*, Trần Hoàng Tiến Thành2 1 Trường Đại học Sư phạm - Đại học Đà Nẵng, Việt Nam 2 Học viên cao học, Khoa Toán, Trường Đại học Sư phạm - Đại học Đà Nẵng, Việt Nam *Tác giả liên hệ / Corresponding author: nthyen_kt@ ued.udn.vn (Nhận bài / Received: 19/9/2024; Sửa bài / Revised: 29/10/2024; Chấp nhận đăng / Accepted: 05/11/2024) Tóm tắt - Bài báo này nghiên cứu điều kiện hữu hiệu cần và điều Abstract - This paper is to study necessary efficiency condition kiện hữu hiệu đủ cho nghiệm cực tiểu toàn cục của bài toán tối ưu and sufficient efficiency condition for a nonconvex optimization không lồi (P) có điều kiện bao gồm ràng buộc bất đẳng thức và problem (P) with conditions involving inequality constraint and ràng buộc tập thông qua các đạo hàm trên. Một điều kiện chính set of constraints in terms of epiderivatives. A regularity quy được giới thiệu cho việc xây dựng điều kiện tối ưu kiểu Kuhn condition is introduced. Under this regularity condition Kuhn Tucker (KT). Ngoài ra, nhóm tác giả xây dựng mô hình đối ngẫu Tucker type (KT-type) optimality conditions are formulated. dạng max cho bài toán gốc (P) bằng cách sử dụng khái niệm đạo Moreover, the authors construct a dual model of the max type hàm trên. Bằng cách áp dụng các điều kiện hữu hiệu cần và đủ through the epiderivatives notion for the primal problem (P). cho nghiệm cực tiểu toàn cục của bài toán gốc (P), nhóm tác giả Using necessary efficiency condition and sufficient efficiency phân tích các định lí về tính đối ngẫu mạnh và tính đối ngẫu yếu condition for a nonconvex optimization problem (P), the authors của cặp bài toán gốc-đối ngẫu thông qua đạo hàm trên. Các ví dụ also explore weak duality theorem and strong duality theorem for minh họa cũng được đề xuất trong bài báo này. the dual-primal problem pair via the epiderivatives. Illustrative examples demonstrates the benefits of our findings. Từ khóa - Bài toán tối ưu không lồi; đối ngẫu; đạo hàm trên; điều Key words - Nonconvex optimization problems; duality; kiện chính quy; nghiệm tối ưu. epiderivatives; regularity condition; optimal solution. 1. Đặt vấn đề cạnh còn lại, vẫn có rất ít kết quả do đối tượng không lồi Đạo hàm trên là một trong những công cụ hiệu quả đòi hỏi phải có kiến thức hỗ trợ phù hợp. Đây là lý do để được áp dụng để nghiên cứu đặc trưng cơ bản cho lớp hàm nhóm tác giả tiến hành nghiên cứu điều kiện hữu hiệu cần không lồi và điều kiện tối ưu cho lớp các bài toán tối ưu và đủ cho bài toán tối ưu không lồi có điều kiện và áp dụng không lồi. Đạo hàm trên được giới thiệu trong tài liệu [1] trong công việc xây dựng mô hình toán đối ngẫu. và hiện nay đang được nhiều nhà khoa học trong nước và Xây dựng mô hình toán học dạng đối ngẫu là cần thiết quốc tế quan tâm áp dụng [2, 3, 4, 5]. Chẳng hạn, Jiménez đối với lý thuyết tối ưu hóa bởi vì tính đối ngẫu yếu cung và Novo [2] sử dụng đạo hàm trên để nghiên cứu đặc cấp cho chúng ta tính bị chặn của hàm mục tiêu. Ngoài ra, trưng của đạo hàm theo hướng đa trị không có cấu trúc và khi giải một bài toán tối ưu, nhiều khi bài toán gốc khó giải áp dụng chúng để thiết lập điều kiện tối ưu cho bài toán nhưng giải trực tiếp trên mô hình đối ngẫu lại khá dễ dàng. tối ưu véctơ tổng quát có điều kiện, Yalcin và Kasimbeyli Từ mối quan hệ mạnh và yếu về cặp bài toán gốc – đối [3] sử dụng đạo hàm trên để nghiên cứu đạo hàm trên ngẫu, việc tìm nghiệm bài toán này suy ra nghiệm bài toán Radial và điều kiện tối ưu cho lớp bài toán tối ưu không còn lại khá tiện lợi. Điều này được thể hiện khá rõ trong lý lồi. Tinh [4, 5] sử dụng đạo hàm trên để nghiên cứu đạo thuyết quy hoạch tuyến tính và tối ưu hóa. hàm trên Hadamard suy rộng và áp dụng trong việc xây Bài toán tối ưu mà hàm mục tiêu được định nghĩa là dựng điều kiện tối ưu cho lớp bài toán véctơ không trơn “max” của một số hữu hạn hàm cho trước có nguồn gốc từ và không lồi,… bài toán quy hoạch minimax [6] là đối tượng nghiên cứu Bài toán tối ưu đơn mục tiêu là đối tượng nghiên cứu trong bài báo này bởi tính ứng dụng của bài toán đối với lý lâu đời nhất bởi vì nó có nguồn gốc từ các nhu cầu thực tế thuyết tối ưu mạnh [7]. Sử dụng công cụ đạo hàm trên, liên quan đến tính hiệu quả của công việc, tính hiệu quả nhóm tác giả nghiên cứu điều kiện cần và đủ hữu hiệu của trong các mô hình sản xuất, kinh doanh, … và hiện nay bài bài toán này cùng với một vài áp dụng trong xây dựng mô toán này đang được quan tâm nghiên cứu trong cả hai khía hình đối ngẫu. cạnh đó là: hàm mục tiêu (hay ràng buộc) lồi và hàm mục Cho tập lồi 𝐶 ⊆ ℝ 𝑛 , 𝑓 = (𝑓1 , 𝑓2 , … , 𝑓𝑝 ): ℝ 𝑛 → ℝ 𝑝 và tiêu (hay ràng buộc) không lồi. Ở khía cạnh đầu tiên, hiện tại đã đạt được các kết quả gần như là hoàn thiện. Ở khía 𝑔 = (𝑔1 , 𝑔2 , … , 𝑔 𝑚 ): ℝ 𝑛 → ℝ 𝑚 . 1 The University of Danang – University of Science and Education, Vietnam (Nguyen Thi Hai Yen) 2 Master’s Student, Faculty of Mathematics, The University of Danang – University of Science and Education, Vietnam (Tran Hoang Tien Thanh)
ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ - ĐẠI HỌC ĐÀ NẴNG, VOL. 22, NO. 11A, 2024 39 𝑛 𝑛 Xét hàm số 𝐹: ℝ → ℝ được xác định bởi 𝐿: ℝ → ℝ ⋃{±∞}. Đạo hàm trên của L tại điểm (𝑥 𝑣) ̅, 𝐹(𝑥) = max {(𝑓1 (𝑥), 𝑓2 (𝑥), … , 𝑓𝑝 (𝑥)}, 𝑥 ∈ ℝ 𝑛 . được định nghĩa bởi ̅+𝑡𝑢)−𝐿(𝑥 𝐿(𝑥 ̅) Với mỗi véctơ 𝑥 ∈ ℝ 𝑛 và các tập chỉ số 𝑑𝐿(𝑥̅ , 𝑣) = liminf . (𝑡,𝑢)→(0+ ,𝒗) 𝑡 𝐼 𝑝 = {1, 2, … , 𝑝}, 𝐼 𝑚 = {1, 2, … , 𝑚}, ta định nghĩa Đạo hàm Hadamard của L tại điểm (𝒙 𝒗) được định ̅, 𝐼(𝑥) = {𝑖 ∈ 𝐼 𝑝 | 𝑓𝑖 (𝑥) = 𝐹(𝑥)} nghĩa bởi và 𝐽(𝑥) = {𝑗 ∈ 𝐼 𝑚 | 𝑔 𝑗 (𝑥) = 0}. 𝑑 𝐻 𝐿(𝑥̅ , 𝑣) = lim ̅+𝑡𝑢)−𝐿(𝑥 𝐿(𝑥 ̅) . (𝑡,𝑢)→(0+ ,𝒗) 𝑡 Hàm F được gọi là hàm max bởi vì giá trị của hàm số được mô tả thông qua giá trị lớn nhất của các thành Chú ý rằng nếu L là ổn định tại ̅ thì L có đạo hàm trên 𝑥 phần trong hàm f cho trước. hữu hạn (xem [2]). Xét bài toán tối ưu không lồi (P) có điều kiện sau: Định nghĩa 2.3. ([1]) Cho ̅ ∈ ℝ 𝑛 và hàm số thực mở 𝑥 rộng 𝐿: ℝ 𝑛 → ℝ ⋃{±∞}. Ta nói 𝐿 là hàm giả lồi tại điểm min 𝐹(𝑥) , (𝑃) 𝑥∈𝐾 ̅ nếu với bất kỳ điểm 𝑥 ∈ ℝ 𝑛 ta luôn có bất đẳng thức 𝑥 Trong đó, 𝐾 là tập các điểm chấp nhận được của bài 𝑑𝐿(𝑥 𝑥 − ̅) ≤ 𝐿(𝑥) − 𝐿(𝑥 ̅, 𝑥 ̅). toán (P) được mô tả như sau Ta nói 𝐿 là giả lồi trên 𝐶 nếu 𝐿 là giả lồi tại mọi điểm ̅ 𝑥 𝐾 ≔ {𝑥 ∈ 𝐶| 𝑔 𝑖 (𝑥) ≤ 0, 𝑖 ∈ 𝐼 𝑚 }. thuộc 𝐶. Bài toán tối ưu có điều kiện là các ràng buộc bất đẳng Chú ý rằng nếu L là hàm lồi trên C thì L là giả lồi trên thức với hàm mục tiêu là max của các thành phần trong C. Thật vậy, với bất kỳ 𝑥 ∈ 𝐶, 𝑡 > 0, ta luôn có hàm véctơ f thông qua khái niệm đạo hàm trên là đối tượng khá mới và hiện nay vẫn chưa được nghiên cứu. 𝐿(𝑥 + 𝑡(𝑥 − ̅)) − 𝐿(𝑥 ≤ 𝑡(𝐿(𝑥) − 𝐿(𝑥 ̅ 𝑥 ̅) ̅)). Với nhận xét này thì việc đưa ra điều kiện cần và đủ tối Chia 2 vế cho 𝑡 > 0 và sau đó dựa vào định nghĩa ưu cho bài toán (P) có ý nghĩa về mặt khoa học, có tính đạo hàm trên ta lấy liminf vế trái và suy ra thời sự và có tính ứng dụng để xây dựng mô hình toán 𝑑𝐿(𝑥 𝑥 − ̅) ≤ 𝐿(𝑥) − 𝐿(𝑥 ̅, 𝑥 ̅). trong tương lai. Tiếp theo nhóm tác giả đề xuất khái niệm chính quy sau: 2. Kiến thức phụ trợ Định nghĩa 2.4. (Điều kiện chính quy) Cho điểm Phần này cung cấp các khái niệm và một số ký hiệu cần ̅ ∈ 𝐾. Ta nói rằng điều kiện chính quy (RC) của bài 𝑥 thiết phục vụ cho nghiên cứu trong các tiểu mục tiếp theo. toán (P) được thỏa mãn tại điểm ̅ nếu quan hệ sau đúng: 𝑥 Không gian Euclide 𝑛-chiều với chuẩn Euclide thông ⋂ {𝑣 ∈ ℝ 𝑛 | 𝑑𝑔 𝑗 (𝑥 𝑣) < 0} ⋂(𝐶 − ̅) ≠ ∅. ̅, 𝑥 thường ‖. ‖, nghĩa là với mọi 𝑥 ∈ ℝ 𝑛 , ‖𝑥‖ = √𝑥 𝑇 𝑥, ̅) 𝑗∈𝐽(𝑥 trong đó 𝑥 𝑇 ký hiệu ma trận cột của x. Từ chỗ này trở đi, ta luôn giả thiết rằng với mọi chỉ Tập không chứa phần tử nào trong ℝ 𝑛 ký hiệu ∅. số 𝑗 ∉ 𝐽(𝑥 các hàm ràng buộc bất đẳng thức 𝑔 𝑗 là hàm ̅), Cho A là một tập lồi. Điểm 𝑎 ∈ 𝐴 được gọi là điểm số liên tục tại điểm ̅. 𝑥 trong tương đối nếu với mọi 𝑥 ∈ 𝐴 đều có một số 𝛼 > 0 Định lí 2.1 ([8, Theorem 21.1]) Cho 𝐶 là tập lồi và sao cho 𝑎 + 𝛼(𝑥 − 𝑎) ∈ 𝐴. Tâp các điểm trong tương 𝑓1 , 𝑓2 , … , 𝑓 𝑚 là các hàm lồi chính thường thỏa mãn đối của A được kí hiệu là riA, cũng là tập lồi. Vì tập C ri 𝐶 ⊂ dom 𝑓𝑖 . Khi đó, chỉ có một trong hai phát biểu sau đây lồi nên theo định nghĩa phần trong tương đối, 𝑟𝑖𝐶 ≠ ∅. đúng: Nhắc lại là miền hữu hiệu của hàm số thực mở rộng (a) Tồn tại 𝑥 ∈ 𝐶 sao cho 𝑓𝑖 (𝑥) < 0, ∀𝑖 = 1, 2, … , 𝑚. 𝑟 xác định trên tập con 𝐸 ⊆ ℝ 𝑛 được kí hiệu dom 𝑟 và (b) Tồn tại các số thực 𝜆1 , 𝜆2 , … , 𝜆 𝑚 không âm và được xác định bởi dom 𝑟 = {𝑥 ∈ 𝐸: 𝑟(𝑥) < +∞}. không đồng thời bằng 0 sao cho Định nghĩa 2.1. (Nghiệm tối ưu) Xét bài toán (P). 𝜆1 𝑓1 (𝑥) + 𝜆2 𝑓2 (𝑥) + ⋯ + 𝜆 𝑚 𝑓 𝑚 (𝑥) ≥ 0, ∀𝑥 ∈ 𝐶. (i) Điểm ̅ ∈ 𝐾 được gọi là nghiệm cực tiểu địa 𝑥 Định nghĩa 2.5 ([8]) phương của bài toán (P) nếu tồn tại lân cận 𝛮 của ̅ 𝑥 thỏa mãn (i) Hàm 𝑓 xác định trên ℝ 𝑛 được gọi là thuần nhất dương, nếu với mọi 𝑥, 𝑓(𝑡𝑥) = 𝑡𝑓(𝑥), 0 < 𝑡 < +∞. 𝐹(𝑥 ≤ 𝐹(𝑥), ∀𝑥 ∈ 𝐾⋂𝛮. ̅) (1) (ii) Hàm 𝑓 xác định trên ℝ 𝑛 được gọi là dưới cộng (ii) Nếu (1) thỏa mãn với mọi điểm 𝑥 ∈ 𝐾 thì ̅ ∈ 𝐾 𝑥 tính, nếu 𝑓(𝑥 + 𝑦) ≤ 𝑓(𝑥) + 𝑓(𝑦), với mọi 𝑥, 𝑦 ∈ ℝ 𝑛 . được gọi là nghiệm cực tiểu toàn cục của bài toán (P). Chú ý: Khái niệm nghiệm cực đại (hay cực đại địa 3. Điều kiện hữu hiệu cho bài toán (P) phương) được định nghĩa đối ngẫu. Phần này nghiên cứu điều kiện hữu hiệu cần và điều Nhắc lại rằng, hàm F được gọi là ổn định tại kiện hữu hiệu đủ cho nghiệm cực tiểu của bài toán (P) ̅ ∈ ℝ 𝒏 nếu tồn tại một lân cận U của ̅ và một số 𝑥 𝑥 thông qua khái niệm đạo hàm trên. thực dương T (gọi là hằng số ổn định) sao cho Điều kiện hữu hiệu cần cho nghiệm cực tiểu địa phươg |𝐹(𝑥) − 𝐹(𝑥 ≤ 𝑇‖𝑥 − ̅‖ với mọi 𝑥 ∈ 𝑈. ̅)| 𝑥 của bài toán (P) và hiển nhiên cũng đúng cho cả nghiệm Định nghĩa 2.2. ([1]) (Đạo hàm trên và đạo hàm cực tiểu toàn cục và được phát biểu như sau: Hadamard) Cho ̅, 𝑣 ∈ ℝ 𝒏 và hàm số thực mở rộng 𝑥 Định lí 3.1. Cho điểm ̅ ∈ 𝐾 là nghiệm cực tiểu địa 𝑥
40 Nguyễn Thị Hải Yến, Trần Hoàng Tiến Thành phương của bài toán (P). Giả sử rằng điều kiện chính tính của chúng, ta được 𝑑𝑓𝑗 (𝑥 𝑣), 𝑑 𝐻 𝑔 𝑖 (𝑥 𝑣) với ̅, ̅, quy (RC) trong Định nghĩa 2.4 được thỏa mãn tại ̅, các 𝑥 𝑗 ∈ 𝐼 𝑝 , 𝑖 ∈ 𝐽(𝑥 là các hàm lồi. Từ đó, do điều kiện ̅) đạo hàm trên của 𝑓𝑖 (𝑖 ∈ 𝐼 𝑝 ) và đạo hàm Hadamard của chính quy (RC) đúng tại điểm ̅ nên áp dụng Định lí 2.1, 𝑥 𝑔 𝑗 (𝑗 ∈ 𝐽(𝑥 hữu hạn và các hàm ràng buộc bất đẳng ̅)) tồn tại các nhân tử Lagrange 𝜆 = (𝜆1 , 𝜆2 , … , 𝜆 𝑝 ) ∈ ℝ+ , 𝑝 thức 𝑔 𝑗 (𝑗 ∉ 𝐽(𝑥 liên tục tại điểm ̅. Hơn nữa, ta giả sử ̅)) 𝑥 𝑝 trong đó 𝜆 𝑗 = 0, ∀𝑗 ∉ 𝐼(𝑥 thỏa mãn ∑ 𝑗=1 𝜆 𝑗 > 0 và ̅) rằng các 𝑑𝑓𝑗 (𝑥 𝑣), 𝑑 𝐻 𝑔 𝑖 (𝑥 𝑣) với 𝑗 ∈ 𝐼 𝑝 , 𝑖 ∈ 𝐽(𝑥 dưới ̅, ̅, ̅) 𝑚 𝜇 = (𝜇1 , 𝜇2 , … , 𝜇 𝑚 ) ∈ ℝ+ với 𝜇 𝑖 = 0, ∀𝑖 ∉ 𝐽(𝑥 sao cho ̅) cộng tính và thỏa mãn ri 𝐶 ⊂ dom 𝑑𝑓𝑗 , 𝑗 ∈ 𝐼 𝑝 , với mọi 𝑣 ∈ 𝐶 − ̅, bất đẳng thức sau đúng: 𝑥 ri 𝐶 ⊂ dom 𝑑 𝐻 𝑔 𝑖 , 𝑖 ∈ 𝐽(𝑥 Khi đó, tồn tại các nhân tử ̅). 𝑝 𝑚 𝑝 Lagrange 𝜆 = (𝜆1 , 𝜆2 , … , 𝜆 𝑝 ) ∈ ℝ+ , trong đó 𝜆 𝑗 = 0 với ∑ 𝜆 𝑗 𝑑𝑓𝑗 (𝑥 𝑣) + ∑ 𝜇 𝑖 𝑑 𝐻 𝑔 𝑖 (𝑥 𝑣) ≥ 0. ̅, ̅, (2) 𝑝 mọi 𝑗 ∉ 𝐼(𝑥 mà ∑ 𝑗=1 𝜆 𝑗 = 1 và 𝜇 = (𝜇1 , 𝜇2 , … , 𝜇 𝑚 ) ∈ ̅) 𝑗=1 𝑖=1 𝑚 ℝ+ , với 𝜇 𝑖 = 0 với mọi 𝑖 ∉ 𝐽(𝑥 sao cho ̅), 𝑝 𝑝 Do ∑ 𝑗=1 𝜆 𝑗 > 0 nên ta có thể chọn ∑ 𝑗=1 𝜆 𝑗 = 1. Từ 𝑝 𝑚 đây và bất đẳng thức (2) ta suy ra 𝑚𝑖𝑛 𝑣∈𝐶−𝑥 (∑ 𝜆 𝑗 𝑑𝑓𝑗 (𝑥 𝑣) + ∑ 𝜇 𝑖 𝑑𝑔 𝑖 (𝑥 𝑣) ) ≥ 0. ̅ ̅, ̅, 𝑝 𝑚 𝑗=1 𝑖=1 𝑚𝑖𝑛 𝑣∈𝐶−𝑥 (∑ 𝜆 𝑗 𝑑𝑓𝑗 (𝑥 𝑣) + ∑ 𝜇 𝑖 𝑑 𝐻 𝑔 𝑖 (𝑥 𝑣) ) ≥ 0. ̅ ̅, ̅, Chứng minh. Ta có đạo hàm trên của hàm mục tiêu 𝑗=1 𝑖=1 𝐹(𝑥) cũng nhận giá trị hữu hạn tại nghiệm cực tiểu địa Để ý là nếu hàm có đạo hàm Hadamard thì đạo hàm phương ̅ ∈ 𝐾 bởi vì các đạo hàm trên của 𝑓𝑖 (𝑖 ∈ 𝐼 𝑝 ) là 𝑥 trên trùng với đạo hàm Hadamard nên định lí được hữu hạn tại nghiệm này (xem [1, Section 6.1.4]). Để ý chứng minh. ∎ rằng hệ (H1) sau đây không có nghiệm 𝑣 ∈ 𝐶 − ̅: 𝑥 Chú ý có nhiều lớp hàm không lồi có đạo hàm trên 𝑑𝐹(𝑥 𝑣) < 0, ̅, thuần nhất, dưới cộng tính. Chẳng hạn, xét hàm số thực { f xác định bởi: 𝑑 𝐻 𝑔 𝑖 (𝑥 𝑣) < 0, 𝑖 ∈ 𝐽(𝑥 ̅, ̅). 2024 |𝑥|(2 − 𝑠𝑖𝑛 ), khi 𝑥 ≠ 0, 𝑓(𝑥) = { 𝑥 Thật vậy, giả sử ngược lại, hệ (H1) có nghiệm 0, khi 𝑥 = 0. 𝑣 ∈ 𝐶 − ̅. Theo định nghĩa đạo hàm trên của F tại điểm 𝑥 (𝑥 𝑣), ta có ̅, Chọn ̅ = 0 và bất kì 𝑣 ∈ ℝ, dùng định nghĩa đạo 𝑥 2024 𝐹(𝑥 + 𝑡𝑢) − 𝐹(𝑥 ̅ ̅) hàm trên và chú ý là 2 − 𝑠𝑖𝑛 ≥ 1 (𝑥 ≠ 0), ta tính 𝑥 𝑑𝐹(𝑥 𝑣) = liminf ̅, được 𝑑𝑓(𝑥 𝑣) = |𝑣|. Do đó, đạo hàm trên ̅, (𝑡,𝑢)→(0+ ,𝒗) 𝑡 𝐹(𝑥 + 𝑡 𝑛 𝑣 𝑛 ) − 𝐹(𝑥 ̅ ̅) 𝑑𝑓(𝑥 . ): ℝ → ℝ thuần nhất dương và dưới cộng tính. ̅, = lim ∃ (𝑡 𝑛 ,𝑣 𝑛 )→(0+ ,𝑣) thỏa mãn 𝑡𝑛 Một điều kiện hữu hiệu đủ cho nghiệm cực tiểu toàn ̅+𝑡 𝑛 𝑣 𝑛 ∈𝐶,𝑛∈∗ 𝑥 cục của bài toán (P) được phát biểu như sau:
ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ - ĐẠI HỌC ĐÀ NẴNG, VOL. 22, NO. 11A, 2024 41 định nghĩa 𝐾(𝐷) là tập sau: = ∑ 𝜆 𝑗 (max{𝑓 𝑗 (𝑥): 𝑗 = 1,2, … , 𝑝} − 𝐹(𝑥 ̅)) 𝑝 (𝑦 𝜆, 𝜇) ∈ 𝐶 × ℝ+ × ℝ+𝑚 ̅, ̅) 𝑗∈𝐼(𝑥 𝑝 𝑚 = ∑ 𝜆 𝑗 (𝐹(𝑥) − 𝐹(𝑥 = 𝐹(𝑥) − 𝐹(𝑥 ̅)) ̅). (3) ∑ 𝜆 𝑗 𝑑𝑓𝑗 (𝑦 𝑣) + ∑ 𝜇 𝑖 𝑑𝑔 𝑖 (𝑦 𝑣) ≥ 0, ̅, ̅, ̅) 𝑗∈𝐼(𝑥 𝑗=1 𝑖=1 𝑝 . Mặt khác, do các hàm ràng buộc 𝑔 𝑖 (𝑖 ∈ 𝐽(𝑥 giả lồi ̅)) tại ̅ và 𝜇 = 𝑥 (𝜇1 , 𝜇2 , … , 𝜇 𝑚 ) ∈ ℝ+𝑚 , với 𝜇 𝑖 = 0 với mọi ∀𝑣 ∈ 𝐶 − ̅, 𝜆 𝑗 = 0 với mọi 𝑗 ∉ 𝐼(𝑦 và ∑ 𝜆 𝑗 = 1 , 𝑦 ̅) 𝑖 ∉ 𝐽(𝑥 nên 𝑑𝑔 𝑖 (𝑥 𝑥 − ̅) ≤ 𝑔 𝑖 (𝑥) − 𝑔 𝑖 (𝑥 ∀𝑥 ∈ 𝐾. ̅) ̅, 𝑥 ̅), 𝑗=1 Vì vậy, với mọi 𝑥 ∈ 𝐾, ta có { 𝜇 𝑖 = 0 với mọi 𝑖 ∉ 𝐽(𝑦̅). } 𝑚 𝑚 Định nghĩa 4.1. Một véctơ (𝑦 𝜆, 𝜇) ∈ 𝐾(𝐷) được gọi ̅, ∑ 𝜇 𝑖 𝑑𝑔 𝑖 (𝑥 𝑥 − ̅) ≤ ∑ 𝜇 𝑖 (𝑔 𝑖 (𝑥) − 𝑔 𝑖 (𝑥 ̅, 𝑥 ̅)) là nghiệm cực đại toàn cục của bài toán đối ngẫu (D) nếu 𝑖=1 𝑖=1 𝐹(𝑦 ≥ 𝐹(𝑦), ∀ (𝑦, 𝜆, 𝜇) ∈ 𝐾(𝐷). ̅) = ∑ 𝜇 𝑖 (𝑔 𝑖 (𝑥) − 𝑔 𝑖 (𝑥 ≤ 0. ̅)) Định lí 4.1. (Đối ngẫu yếu) Cho các nghiệm chấp nhận ̅) 𝑖∈𝐽(𝑥 được ̅ ∈ 𝐾 và (𝑦 𝜆, 𝜇) ∈ 𝐾(𝐷). Giả sử rằng các hàm 𝑥 ̅, Cộng bất đẳng thức trên với bất đẳng thức (3) vế theo 𝑓𝑗 (𝑗 ∈ 𝐼(𝑦̅)), 𝑔 𝑖 (𝑖 ∈ 𝐽(𝑦 giả lồi tại điểm ̅ và các đạo ̅)) 𝑦 vế, ta được hàm trên của chúng hữu hạn tại điểm ̅. Khi đó, ta luôn có 𝑦 𝑝 𝑚 𝐹(𝑥 ≥ 𝐹(𝑦 ̅) ̅). 𝐹(𝑥) − 𝐹(𝑥 ≥ ∑ 𝜆 𝑗 𝑑𝑓𝑗 (𝑥 𝑥 − ̅) + ∑ 𝜇 𝑖 𝑑𝑔 𝑖 (𝑥 𝑥 − ̅). ̅) ̅, 𝑥 ̅, 𝑥 Chứng minh. Theo giả thiết, tập 𝐶 lồi và các hàm 𝑗=1 𝑖=1 𝑓𝑗 (𝑗 ∈ 𝐼(𝑦̅)), 𝑔 𝑖 (𝑖 ∈ 𝐽(𝑦 giả lồi tại ̅, do đó, ta có bất ̅)) 𝑦 Suy ra 𝐹(𝑥) − 𝐹(𝑥 ≥ 0, ∀𝑥 ∈ 𝐾. Vậy, điểm ̅) đẳng thức sau ̅ ∈ 𝐾 là nghiệm cực tiểu của bài toán (P). ∎ 𝑥 𝑑𝑓𝑗 (𝑦 ̅ − ̅) ≤ 𝑓𝑗 (𝑥 − 𝑓𝑗 (𝑦 ̅, 𝑥 𝑦 ̅) ̅). Ví dụ 3.3. Xét bài toán tối ưu (P), với 𝑛 = 1, 𝑝 = 𝑚 = 2, các hàm số thực mở rộng sau Suy ra 𝑝 𝑝 2024 𝑥 2 (|𝑠𝑖𝑛 | − 1), khi 𝑥 ≠ 0, ∑ 𝜆 𝑗 𝑑𝑓𝑗 (𝑦 ̅ − ̅) ≤ ∑ 𝜆 𝑗 (𝑓𝑗 (𝑥 − 𝑓𝑗 (𝑦 ̅, 𝑥 𝑦 ̅) ̅)) 𝑓1 (𝑥) = { 𝑥 0, khi 𝑥 = 0, 𝑗=1 𝑗=1 𝑓2 (𝑥) = |2024𝑥| − 𝑥 2 , 𝑔1 (𝑥) = 2024𝑥 2 + 𝑥 − 2025 = ∑ 𝜆 𝑗 (𝑓𝑗 (𝑥 − 𝑓𝑗 (𝑦 ̅) ̅)) và 𝑔2 (𝑥) = 2024(𝑥 2 − 𝑥) với mọi 𝑥 ∈ ℝ. Chọn điểm ̅) 𝑗∈𝐼(𝑦 ̅ = 0 và tập con lồi 𝐶 = [0, +∞). Ta có 𝐾 = {𝑥 ∈ 𝑥 ≤ ∑ 𝜆 𝑗 (𝑚𝑎𝑥{𝑓𝑗 (𝑥 𝑗 = 1,2, … , 𝑝} − 𝑓𝑗 (𝑦 ̅): ̅)) 𝐶: 2024𝑥 2 + 𝑥 − 2025 ≤ 0, 2024(𝑥 2 − 𝑥) ≤ 0}, hay ̅) 𝑗∈𝐼(𝑦 K= [0, 1], 𝐹(𝑥) = 𝑓2 (𝑥), do đó, 𝐼(𝑥 = 𝐽(𝑥 = {2}. Hơn ̅) ̅) nữa, ta cũng có 𝑑𝑓2 (𝑥 𝑥 − ̅) = |2024𝑥|, 𝑑 𝐻 𝑔2 (𝑥 𝑥 − ̅, 𝑥 ̅, = ∑ 𝜆 𝑗 (𝑚𝑎𝑥{𝑓𝑗 (𝑥 𝑗 = 1,2, … , 𝑝} − 𝐹(𝑦 ̅): ̅)) ̅) = −2024𝑥, với mọi 𝑥 ∈ 𝐾 và 𝑓1 (𝑥), 𝑓2 (𝑥), 𝑔2 (𝑥) giả 𝑥 ̅) 𝑗∈𝐼(𝑦 lồi tại ̅. 𝑥 = ∑ 𝜆 𝑗 (𝐹(𝑥 − 𝐹(𝑦 = 𝐹(𝑥 − 𝐹(𝑦 ̅) ̅)) ̅) ̅). (4) Chọn 𝜇 = (𝜇1 , 𝜇2 ) ≔ (0, 1) ∈ ℝ2 và 𝜆 = (𝜆1 , 𝜆2 ) ≔ + ̅) 𝑗∈𝐼(𝑦 (0, 1) ∈ ℝ2 , ta được + Tương tự như trên, ta có 𝑝 𝑚 𝑚 𝑚 𝑚𝑖𝑛 𝑣∈𝐾−𝑥 (∑ 𝜆 𝑗 𝑑𝑓𝑗 (𝑥 𝑣) + ∑ 𝜇 𝑖 𝑑 𝐻 𝑔 𝑖 (𝑥 𝑣) ) ̅ ̅, ̅, ∑ 𝜇 𝑖 𝑑𝑔 𝑖 (𝑦 ̅ − ̅) ≤ ∑ 𝜇 𝑖 (𝑔 𝑖 (𝑥 − 𝑔 𝑖 (𝑦 ̅, 𝑥 𝑦 ̅) ̅)) 𝑗=1 𝑖=1 𝑖=1 𝑖=1 = 𝑚𝑖𝑛 𝑣∈𝐾−𝑥 (|2024𝑣| − 2024𝑣) ≥ 0. = ∑ 𝜇 𝑖 (𝑔 𝑖 (𝑥 − 𝑔 𝑖 (𝑦 ≤ 0. (5) ̅) ̅)) ̅ ̅) 𝑖∈𝐽(𝑦 Áp dụng Định lí 3.2, điểm ̅ = 0 là nghiệm cực tiểu 𝑥 của bài toán (P). Thử lại bằng định nghĩa ta thấy thỏa mãn. Vì (𝑦 𝜆, 𝜇) ∈ 𝐾(𝐷) kéo theo ̅, 𝑝 𝑚 4. Ứng dụng trong mô hình đối ngẫu ∑ 𝜆 𝑗 𝑑𝑓𝑗 (𝑦 𝑣) + ∑ 𝜇 𝑖 𝑑𝑔 𝑖 (𝑦 𝑣) ≥ 0 ̅, ̅, Phần này trình bày mô hình đối ngẫu dạng max cho bài 𝑗=1 𝑖=1 toán gốc (P) và phân tích tính đối ngẫu mạnh và tính đối nên kết hợp điều này với việc cộng vế theo vế các bất đẳng ngẫu yếu cho cặp bài toán gốc (P) và đối ngẫu (D) (bài toán thức (4) và (5) ta được 𝐹(𝑥 − 𝐹(𝑦 ≥ 0. ∎ ̅) ̅) đối ngẫu của bài toán (P)). Định lí 4.2. (Đỗi ngẫu mạnh) Cho ̅ ∈ 𝐾 là nghiệm cực 𝑥 Bài toán đối ngẫu dạng max ký hiệu (D) cho bài toán tiểu toàn cục của bài toán gốc (P). Giả sử rằng các điều kiện tối ưu min gốc (P) được định nghĩa bởi: của Định lí 3.1 được thỏa mãn. Khi đó, tồn tại các nhân tử 𝑝 max 𝐹(𝑦) với điều kiện (𝑦, 𝜆, 𝜇) ∈ 𝐾(𝐷), (D) Lagrange 𝜆 = (𝜆1 , 𝜆2 , … , 𝜆 𝑝 ) ∈ ℝ+ , trong đó 𝜆 𝑗 = 0 𝑦∈𝐶 𝑝 với mọi 𝑗 ∉ 𝐼(𝑥̅) và ∑ 𝑗=1 𝜆 𝑗 = 1 và trong đó, 𝐹(𝑦) = max 𝑓𝑖 (𝑦) và 𝐾(𝐷) ký hiệu tập 𝑖=1,2,…,𝑝 𝜇 = (𝜇1 , 𝜇2 , … , 𝜇 𝑚 ) ∈ ℝ+𝑚 , với 𝜇 𝑖 = 0 với mọi 𝑖 ∉ 𝐽(𝑥 ̅) nghiệm chấp nhận được của bài toán đối ngẫu (D) và ta sao cho (𝑥 𝜆, 𝜇) ∈ 𝐾(𝐷). ̅,
42 Nguyễn Thị Hải Yến, Trần Hoàng Tiến Thành Hơn nữa, nếu ta thêm giả thiết là các hàm hay là ̅)), 𝑔 𝑖 (𝑖 ∈ 𝐽(𝑥 giả lồi tại điểm ̅ thì 𝑓𝑗 (𝑗 ∈ 𝐼(𝑥 ̅)) 𝑥 (𝑦 𝜆, 𝜇) ∈ 𝐶 × ℝ3 × ℝ2 ̅, + + (𝑥 𝜆, 𝜇) ∈ 𝐾(𝐷) là nghiệm cực đại toàn cục của bài toán ̅, 𝑑𝑓1 (𝑦 𝑣) + 𝜇1 𝑑𝑔1 (𝑦 𝑣) ̅, ̅, đối ngẫu (D). 𝐾(𝐷) = . +𝜇2 𝑑𝑔2 (𝑦 𝑣) ≥ 0, ̅, Chứng minh. Ta có tập 𝐶 lồi và điều kiện chính quy { ∀𝑣 ∈ 𝐶 − ̅. 𝑦 } (RC) của bài toán tối ưu gốc không lồi (P) thỏa mãn tại Với mọi nghiệm chấp nhận được ((𝑥, 𝑦), 𝜆, 𝜇) ∈ điểm ̅. Vì ̅ ∈ 𝐾 là nghiệm cực tiểu toàn cục của bài toán 𝑥 𝑥 𝐾(𝐷), theo Định lí 4.1 ta có 𝐹(𝑥 ≥ 𝐹(𝑦 hay là ̅) ̅), (P) nên áp dụng Định lí 3.1 tồn tại các nhân tử Lagrange 𝑝 |𝑥| + 𝑦 ≤ 𝑎 + |𝑎| = 2𝑎. 𝜆 = (𝜆1 , 𝜆2 , … , 𝜆 𝑝 ) ∈ ℝ+ , với 𝜆 𝑗 = 0 với mọi 𝑗 ∉ 𝐼(𝑥 và ̅) 𝑝 ∑ 𝑗=1 𝜆 𝑗 = 1 và 𝜇 = (𝜇1 , 𝜇2 , … , 𝜇 𝑚 ) ∈ ℝ+𝑚 với 𝜇 𝑖 = 0 với Vậy định lý đối ngẫu yếu cung cấp một bị chặn dưới cho hàm mục tiêu của bài toán gốc (P). mọi 𝑖 ∉ 𝐽(𝑥 sao cho ̅) 𝑝 𝑚 𝑚𝑖𝑛 𝑣∈𝐶−𝑥 (∑ 𝑗=1 𝜆 𝑗 𝑑𝑓𝑗 (𝑥 𝑣) + ∑ 𝑖=1 𝜇 𝑖 𝑑𝑔 𝑖 (𝑥 𝑣) ) ≥ 0. ̅ ̅, ̅, 5. Kết luận Trong bài báo này nhóm tác giả đã thiết lập được điều Theo định nghĩa, ta suy ra (𝑥 𝜆, 𝜇) ∈ 𝐾(𝐷). ̅, kiện hữu hiệu cần và đủ cho nghiệm cực tiểu toàn cục của Bây giờ, nếu ta thêm giả thiết rằng các hàm bài toán tối ưu không lồi (P) có các ràng buộc bất đẳng thức 𝑓𝑗 (𝑗 ∈ 𝐼(𝑥 ̅)), 𝑔 𝑖 (𝑖 ∈ 𝐽(𝑥 giả lồi tại ̅ thì áp dụng định ̅)) 𝑥 và ràng buộc tập với hàm mục tiêu là max của các thành lí đối ngẫu yếu, với mọi nghiệm chấp nhận được phần của hàm véctơ nào đó thông qua các đạo hàm trên. (𝑦, 𝜆′ , 𝜇′) ∈ 𝐾(𝐷), ta có 𝐹(𝑥 − 𝐹(𝑦) ≥ 0. Theo Định ̅) Nhóm tác giả cũng xây dựng mô hình đối ngẫu dạng max nghĩa 4.1, véctơ (𝑥 𝜆, 𝜇) ∈ 𝐾(𝐷) là nghiệm cực đại toàn ̅, cho bài toán tối ưu min (P) và đồng thời cũng cung cấp các cục của bài toán đối ngẫu (D). ∎ định lí về tính đối ngẫu mạnh và định lí về đối ngẫu yếu Ví dụ 4.3. Xét bài toán tối ưu (P), với 𝑛 = 2, của chúng. 𝑝 = 3, 𝑚 = 2, 𝐶 = ℝ2 và xét các hàm số thực sau Lời cảm ơn: Nghiên cứu này được tài trợ bởi Quỹ Phát 𝑓1 (𝑥, 𝑦) = |𝑥| + 𝑦, triển Khoa học và Công nghệ Đại học Đà Nẵng trong đề tài 𝑓2 (𝑥, 𝑦) = −|𝑥| + 𝑦 − 2024, có mã số B2023-DN03-08. 𝑓3 (𝑥, 𝑦) = |𝑥| + 𝑦 − 2025, TÀI LIỆU THAM KHẢO 𝑔1 (𝑥, 𝑦) = |𝑦| − 𝑥 [1] J. P. Aubin and H. Frankowska, Set-Valued Analysis, Birkhauser, và 𝑔2 (𝑥, 𝑦) = |𝑥| − 𝑦 với mọi 𝑥, 𝑦 ∈ ℝ. Suy ra Boston, 1990. 𝐹(𝑥, 𝑦) = |𝑥| + 𝑦 với mọi 𝑥, 𝑦 ∈ ℝ và 𝐼(𝑥, 𝑦) = {1}. [2] B. Jiménez and N. Novo, "First order optimality conditions in vector Khi đó tập chấp nhận được 𝐾 = {(𝑥, 𝑦) ∈ ℝ2 : 𝑥 = 𝑦}. + optimization involving stable functions", Optimization, vol. 57, no. 3, pp. 449-471, 2008. Chọn điểm ̅ = (𝑎, 𝑎) ∈ 𝐾 với mọi số thực a ≥ 0 và điểm 𝑥 [3] G. D. Yalcin, and R. Kasimbeyli, "Generalized derivatives and ̅ = (𝑥, 𝑦) ∈ ℝ2 . Dễ dàng kiểm tra bằng định nghĩa các 𝑦 optimality conditions in nonconvex optimization", Bull. Malays. hàm 𝑓1 , 𝑔1 𝑣à 𝑔2 giả lồi tại ̅ và các đạo hàm trên của 𝑦 Math. Sci. Soc., vol. 47, no. 81, pp. 1-30, 2024. chúng hữu hạn tại ̅.𝑦 [4] P. N. Tinh, "Optimality conditions for nonsmooth vector problems in normed spaces", Optimization, vol. 69, no. 6, pp. 1151-1186, Bài toán đối ngẫu (D) cho bài toán tối ưu min gốc (P) 2020. được xác định bởi: [5] P. N. Tinh, "On optimality conditions for nonsmooth vector max 𝐹(𝑦) với điều kiện (𝑦, 𝜆, 𝜇) ∈ 𝐾(𝐷), (D) problems in normed spaces via generalized Hadamard directional 𝑦∈𝐶 derivatives", Optimization, vol. 72, no. 4, pp. 1037-1068, 2023. trong đó, tập chấp nhận được đối ngẫu 𝐾(𝐷) có dạng: [6] T. D. Chuong, and D. S. Kim, "Nondifferentiable minimax programming problems with applications", Ann. Oper. Res., vol. (𝑦 𝜆, 𝜇) ∈ 𝐶 × ℝ3 × ℝ2 ̅, + + 251, no. 1-2, pp. 73-87, 2017. ∑ 𝑗=1 𝜆 𝑗 𝑑𝑓𝑗 (𝑦 𝑣) + ∑2 𝜇 𝑖 𝑑𝑔 𝑖 (𝑦 𝑣) ≥ 0, 3 ̅, 𝑖=1 ̅, [7] Z. Hong, K. D. Bae, and D. S. Kim, "Minimax programming as a tool for studying robust multi-objective optimization problems", ∀𝑣 ∈ 𝐶 − ̅, 𝜆 𝑗 = 0 với mọi 𝑗 ∉ 𝐼(𝑦 và ∑3 𝜆 𝑗 = 1 , 𝑦 ̅) 𝑗=1 Ann. Oper. Res. vol. 319, no. 2, pp. 1589-1606, 2022. { 𝜇 𝑖 = 0 với mọi 𝑖 ∉ 𝐽(𝑦 ̅) } [8] R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, 1970.