Nghiên cứu điều kiện tối ưu cấp hai trong bài toán tối ưu đa mục tiêu

Tổng hợp kiến thức Điều kiện tối ưu cấp hai trong bài toán tối ưu đa mục tiêu, tiếp cận khoa học, hỗ trợ học tập và nghiên cứu hiệu quả trong chuyên

• Tác giả: Nguyễn Ngọc Uyển Nhi
• Người hướng dẫn: PGS.TS Phan Nhật Tĩnh
• Trường học: Đại học Huế
• Chuyên ngành: Toán Giải Tích
• Đề tài: Điều Kiện Tối Ưu Cấp Hai Trong Bài Toán Tối Ưu Đa Mục Tiêu
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2017
• Địa điểm: Thừa Thiên Huế

Mục lục chi tiết

• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: CÁC KHÁI NIỆM CƠ BẢN CỦA LÝ THUYẾT TỐI ƯU ĐA MỤC TIÊU
• 1.1. Quan hệ thứ tự từng phần trong R
• 1.2. Nghiệm cực tiểu, nghiệm cực tiểu yếu, nghiệm cực tiểu địa phương của bài toán tối ưu đa mục tiêu
• 2. CHƯƠNG 2: ĐIỀU KIỆN CẦN TỐI ƯU CẤP HAI CỦA BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU
• 2.1. Tập tiếp xúc, Tập tuyến tính cấp 1 và cấp 2
• 2.2. Điều kiện cần tối ưu cấp hai của bài toán có ràng buộc tập hợp
• 2.3. Định lý Motzkin
• 2.4. Ứng dụng định lý Motzkin vào điều kiện cần của bài toán tối ưu cấp 2
• 3. CHƯƠNG 3: ĐIỀU KIỆN ĐỦ TỐI ƯU CẤP HAI CỦA BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU
• 3.1. Điều kiện đủ của bài toán tối ưu cấp hai
• 3.2. Trường hợp bài toán không ràng buộc tập hợp
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Các khái niệm cơ bản của lý thuyết tối ưu đa mục tiêu

Lý thuyết tối ưu đa mục tiêu đã phát triển mạnh mẽ với nhiều khái niệm quan trọng. Điều kiện tối ưu là một trong những khái niệm cốt lõi, giúp xác định các điểm tối ưu trong không gian nhiều chiều. Trong bối cảnh này, hàm mục tiêu và tập hợp ràng buộc đóng vai trò quan trọng. Các khái niệm như nghiệm cực tiểu, nghiệm cực tiểu yếu, và nghiệm cực tiểu địa phương được định nghĩa rõ ràng. Đặc biệt, quan hệ thứ tự từng phần trong không gian R^n giúp phân loại các điểm trong không gian tối ưu. Điều này cho phép xây dựng các thuật toán tối ưu hiệu quả hơn, từ đó nâng cao khả năng giải quyết các bài toán thực tiễn phức tạp.

1.1. Quan hệ thứ tự từng phần

Trong không gian R^n, một quan hệ hai ngôi được gọi là thứ tự từng phần nếu nó thỏa mãn các tính chất nhất định. Điều này cho phép xác định các điểm tối ưu trong không gian nhiều chiều. Tập hợp lồi và nón là những khái niệm quan trọng trong việc xác định các điểm cực tiểu. Các khái niệm này không chỉ có giá trị lý thuyết mà còn có ứng dụng thực tiễn trong việc tối ưu hóa các hệ thống phức tạp.

1.2. Nghiệm cực tiểu và các loại nghiệm

Nghiệm cực tiểu được định nghĩa là điểm mà tại đó hàm mục tiêu đạt giá trị nhỏ nhất trong một tập hợp nhất định. Nghiệm cực tiểu yếu và nghiệm cực tiểu địa phương là các khái niệm mở rộng, cho phép phân tích sâu hơn về tính chất của các nghiệm trong không gian tối ưu. Việc hiểu rõ các loại nghiệm này giúp các nhà nghiên cứu và thực hành tối ưu hóa có thể áp dụng các phương pháp phù hợp để tìm kiếm nghiệm tối ưu trong các bài toán thực tế.

II. Điều kiện cần tối ưu cấp hai của bài toán tối ưu đa mục tiêu

Điều kiện cần tối ưu cấp hai là một phần quan trọng trong lý thuyết tối ưu. Nó cho phép xác định các điểm mà tại đó hàm mục tiêu có thể đạt được giá trị tối ưu. Tập tiếp xúc và tập tuyến tính cấp 1 và cấp 2 là những khái niệm cơ bản trong việc xây dựng các điều kiện này. Các điều kiện cần tối ưu cấp hai không chỉ giúp kiểm tra tính tối ưu mà còn hỗ trợ trong việc thiết kế các thuật toán tối ưu hiệu quả. Việc áp dụng các điều kiện này vào các bài toán thực tế cho thấy giá trị thực tiễn của chúng trong việc tối ưu hóa các hệ thống phức tạp.

2.1. Tập tiếp xúc và các khái niệm liên quan

Tập tiếp xúc cấp hai là một khái niệm quan trọng trong việc xác định các điểm tối ưu. Nó cho phép phân tích sâu hơn về hình dạng của hàm mục tiêu tại các điểm cực tiểu. Điều kiện cần tối ưu cấp hai giúp xác định các điểm mà tại đó hàm mục tiêu có thể đạt được giá trị tối ưu. Việc hiểu rõ các khái niệm này là cần thiết để áp dụng vào các bài toán thực tế.

2.2. Điều kiện cần tối ưu cấp hai với ràng buộc tập hợp

Khi có ràng buộc tập hợp, điều kiện cần tối ưu cấp hai trở nên phức tạp hơn. Các nhà nghiên cứu cần phải xem xét các yếu tố như hàm mục tiêu và tập hợp ràng buộc để xác định các điểm tối ưu. Việc áp dụng các điều kiện này vào các bài toán thực tế cho thấy giá trị thực tiễn của chúng trong việc tối ưu hóa các hệ thống phức tạp.

III. Điều kiện đủ tối ưu cấp hai của bài toán tối ưu đa mục tiêu

Điều kiện đủ tối ưu cấp hai là một phần quan trọng trong lý thuyết tối ưu. Nó cho phép xác định các điểm mà tại đó hàm mục tiêu đạt được giá trị tối ưu. Các điều kiện này không chỉ giúp kiểm tra tính tối ưu mà còn hỗ trợ trong việc thiết kế các thuật toán tối ưu hiệu quả. Việc áp dụng các điều kiện này vào các bài toán thực tế cho thấy giá trị thực tiễn của chúng trong việc tối ưu hóa các hệ thống phức tạp.

3.1. Điều kiện đủ của bài toán tối ưu cấp hai

Điều kiện đủ tối ưu cấp hai giúp xác định các điểm mà tại đó hàm mục tiêu đạt được giá trị tối ưu. Việc áp dụng các điều kiện này vào các bài toán thực tế cho thấy giá trị thực tiễn của chúng trong việc tối ưu hóa các hệ thống phức tạp. Các nhà nghiên cứu cần phải xem xét các yếu tố như hàm mục tiêu và tập hợp ràng buộc để xác định các điểm tối ưu.

3.2. Trường hợp bài toán không ràng buộc tập hợp

Trong trường hợp không có ràng buộc tập hợp, điều kiện đủ tối ưu cấp hai trở nên đơn giản hơn. Các nhà nghiên cứu có thể áp dụng các phương pháp tối ưu hóa đơn giản hơn để tìm kiếm nghiệm tối ưu. Việc hiểu rõ các điều kiện này là cần thiết để áp dụng vào các bài toán thực tế.

Nội dung chính

Tổng quan nghiên cứu

Lý thuyết tối ưu đa mục tiêu là một lĩnh vực quan trọng trong toán học ứng dụng, đặc biệt trong các bài toán có nhiều tiêu chí cần được tối ưu đồng thời. Theo ước tính, các bài toán tối ưu đa mục tiêu xuất hiện phổ biến trong nhiều ngành như kinh tế, kỹ thuật, quản lý và khoa học máy tính. Tuy nhiên, việc xác định các điều kiện tối ưu, đặc biệt là điều kiện tối ưu cấp hai, vẫn còn nhiều thách thức do tính phức tạp và không lồi của bài toán. Luận văn tập trung nghiên cứu điều kiện tối ưu cấp hai của bài toán tối ưu đa mục tiêu, nhằm cung cấp các điều kiện cần và đủ để xác định nghiệm cực tiểu địa phương trong trường hợp hàm mục tiêu khả vi cấp hai và có ràng buộc tập hợp. Phạm vi nghiên cứu được giới hạn trong không gian tuyến tính hữu hạn chiều, với nón lồi, nhọn và phần trong không rỗng làm cơ sở cho việc sắp thứ tự các giá trị mục tiêu. Nghiên cứu có ý nghĩa quan trọng trong việc phát triển lý thuyết tối ưu đa mục tiêu, hỗ trợ thiết kế thuật toán tối ưu và phân tích tính nhạy cảm của nghiệm tối ưu trong các bài toán thực tế. Kết quả nghiên cứu cũng góp phần làm rõ các khái niệm cơ bản và các định lý liên quan đến điều kiện tối ưu cấp hai, từ đó nâng cao hiệu quả ứng dụng trong các lĩnh vực đa ngành.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên nền tảng lý thuyết tối ưu đa mục tiêu, trong đó có các khái niệm quan trọng như:

• Quan hệ thứ tự từng phần trên không gian tuyến tính: Được xác định thông qua nón lồi, nhọn và phần trong không rỗng, giúp định nghĩa các điểm cực tiểu theo nón thứ tự.
• Nghiệm cực tiểu, cực tiểu yếu và cực tiểu địa phương: Các khái niệm này phân biệt các loại nghiệm tối ưu trong bài toán đa mục tiêu, dựa trên tập giá trị hữu hiệu và các tính chất của nón thứ tự.
• Tập tiếp xúc cấp một và cấp hai, tập tuyến tính cấp một và cấp hai: Các tập này mô tả các hướng và biến đổi tại điểm nghiệm, là cơ sở để xây dựng điều kiện tối ưu cấp hai.
• Định lý Motzkin và các hệ quả: Định lý này được ứng dụng để chứng minh các điều kiện cần và đủ tối ưu cấp hai, đặc biệt trong việc xử lý các ràng buộc tập hợp và các nón lồi đa diện.
• Điều kiện cần và đủ tối ưu cấp hai: Bao gồm các mệnh đề và định lý chứng minh sự tồn tại của nghiệm cực tiểu địa phương dựa trên các điều kiện về đạo hàm cấp hai và các tập tiếp xúc.

Phương pháp nghiên cứu

Nghiên cứu sử dụng phương pháp phân tích lý thuyết toán học với các bước chính:

• Nguồn dữ liệu: Tài liệu tham khảo từ các công trình nghiên cứu, bài báo khoa học và sách chuyên khảo về tối ưu đa mục tiêu và điều kiện tối ưu cấp hai.
• Phương pháp phân tích: Áp dụng các kỹ thuật phân tích hàm khả vi cấp hai, lý thuyết nón lồi, tập tiếp xúc và định lý Motzkin để xây dựng và chứng minh các điều kiện tối ưu.
• Cỡ mẫu và chọn mẫu: Nghiên cứu tập trung trên không gian tuyến tính hữu hạn chiều với các hàm mục tiêu và ràng buộc cụ thể, không sử dụng dữ liệu thực nghiệm mà chủ yếu là phân tích lý thuyết.
• Timeline nghiên cứu: Quá trình nghiên cứu diễn ra trong năm 2017, bao gồm việc tổng hợp lý thuyết, xây dựng chứng minh và khảo sát các trường hợp đặc biệt của bài toán tối ưu đa mục tiêu.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Xác định các khái niệm cơ bản của lý thuyết tối ưu đa mục tiêu: Luận văn làm rõ các khái niệm về quan hệ thứ tự từng phần, điểm cực tiểu, cực tiểu yếu và cực tiểu địa phương, với hơn 10 định nghĩa và mệnh đề được trình bày chi tiết.

2. Điều kiện cần tối ưu cấp hai cho bài toán có ràng buộc tập hợp: Chứng minh rằng nếu một điểm là nghiệm cực tiểu yếu địa phương thì tồn tại các điều kiện liên quan đến tập tiếp xúc cấp hai và các nón lồi, với các bất đẳng thức đạo hàm cấp hai thỏa mãn. Ví dụ, với nón K lồi, nhọn và phần trong không rỗng, điều kiện cần được thể hiện qua các bất đẳng thức liên quan đến đạo hàm cấp hai của hàm mục tiêu.

3. Điều kiện đủ tối ưu cấp hai trong trường hợp không ràng buộc: Khi tập ràng buộc là toàn bộ không gian, luận văn chỉ ra rằng điều kiện đủ được thỏa mãn nếu với mọi hướng giảm, một bất đẳng thức liên quan đến đạo hàm cấp hai của hàm mục tiêu lớn hơn 0. Kết quả này được minh họa qua các ví dụ cụ thể với không gian R^n và nón K = R^m.

4. Ứng dụng định lý Motzkin vào điều kiện cần tối ưu cấp hai: Luận văn áp dụng định lý Motzkin để chứng minh các điều kiện cần tối ưu cấp hai trong trường hợp bài toán có ràng buộc tập hợp, đặc biệt khi tập ràng buộc là tập lồi đa diện. Điều này giúp mở rộng phạm vi áp dụng của các điều kiện tối ưu trong thực tế.

Thảo luận kết quả

Các kết quả nghiên cứu phù hợp với các công trình trước đây trong lĩnh vực tối ưu đa mục tiêu, đồng thời làm rõ hơn các điều kiện cấp hai trong trường hợp không có giả thiết lồi chặt chẽ. Việc sử dụng các tập tiếp xúc cấp hai và định lý Motzkin giúp giải quyết các khó khăn trong việc xác định nghiệm tối ưu khi bài toán có ràng buộc phức tạp. So với các nghiên cứu trước, luận văn tập trung sâu vào chứng minh chi tiết các mệnh đề và định lý, đảm bảo tính chặt chẽ và rõ ràng trong lý thuyết. Các biểu đồ minh họa tập giá trị hữu hiệu và các tập tiếp xúc có thể được sử dụng để trực quan hóa các khái niệm và điều kiện tối ưu, giúp người đọc dễ dàng hình dung cấu trúc bài toán. Tuy nhiên, luận văn cũng thừa nhận hạn chế về phạm vi nghiên cứu, chỉ khảo sát điều kiện đủ trong trường hợp nón K = R^m, và chưa phát hiện ra các điều kiện mới vượt trội so với lý thuyết hiện có. Điều này mở ra hướng nghiên cứu tiếp theo nhằm mở rộng và nâng cao các điều kiện tối ưu cấp hai cho các loại nón khác và bài toán phức tạp hơn.

Đề xuất và khuyến nghị

1. Mở rộng nghiên cứu điều kiện đủ tối ưu cấp hai cho các loại nón khác: Nghiên cứu nên được tiếp tục để khảo sát các trường hợp nón lồi không phải là R^m, nhằm tăng tính ứng dụng trong các bài toán đa mục tiêu phức tạp hơn. Thời gian thực hiện dự kiến trong 1-2 năm, do các nhóm nghiên cứu toán học ứng dụng đảm nhận.

2. Phát triển thuật toán tối ưu dựa trên điều kiện cấp hai: Áp dụng các điều kiện cần và đủ đã chứng minh để thiết kế thuật toán tối ưu đa mục tiêu hiệu quả hơn, đặc biệt trong các bài toán có ràng buộc phức tạp. Mục tiêu là cải thiện tốc độ hội tụ và độ chính xác nghiệm trong vòng 3 năm, do các nhóm nghiên cứu về tối ưu và khoa học máy tính thực hiện.

3. Khảo sát tính nhạy cảm của nghiệm tối ưu: Sử dụng điều kiện cấp hai làm cơ sở để phân tích ảnh hưởng của nhiễu và biến động dữ liệu đến nghiệm tối ưu, giúp nâng cao độ tin cậy của các mô hình tối ưu đa mục tiêu trong thực tế. Thời gian thực hiện khoảng 1 năm, do các nhà nghiên cứu toán ứng dụng và kỹ thuật đảm nhiệm.

4. Ứng dụng trong các lĩnh vực thực tiễn: Đề xuất áp dụng lý thuyết và điều kiện tối ưu cấp hai vào các bài toán trong kinh tế, kỹ thuật, quản lý dự án và khoa học dữ liệu để giải quyết các vấn đề đa tiêu chí phức tạp. Các tổ chức nghiên cứu và doanh nghiệp có thể phối hợp triển khai trong 2-3 năm tới.

Đối tượng nên tham khảo luận văn

1. Nghiên cứu sinh và học viên cao học ngành Toán học ứng dụng: Luận văn cung cấp nền tảng lý thuyết vững chắc về điều kiện tối ưu cấp hai trong tối ưu đa mục tiêu, hỗ trợ cho việc học tập và nghiên cứu chuyên sâu.

2. Giảng viên và nhà nghiên cứu trong lĩnh vực tối ưu và toán học công nghiệp: Tài liệu chi tiết về các định lý và chứng minh giúp mở rộng kiến thức và phát triển các công trình nghiên cứu mới.

3. Chuyên gia phát triển thuật toán tối ưu đa mục tiêu: Các điều kiện cần và đủ được trình bày rõ ràng giúp thiết kế và cải tiến thuật toán tối ưu, nâng cao hiệu quả xử lý bài toán thực tế.

4. Nhà quản lý và kỹ sư trong các lĩnh vực ứng dụng đa tiêu chí: Hiểu biết về lý thuyết tối ưu đa mục tiêu giúp áp dụng các mô hình toán học vào giải quyết các bài toán phức tạp trong kinh tế, kỹ thuật và quản lý dự án.

Câu hỏi thường gặp

1. Điều kiện tối ưu cấp hai khác gì so với điều kiện cấp một?
   Điều kiện cấp một chỉ đảm bảo điểm nghiệm là điểm dừng, còn điều kiện cấp hai cung cấp thêm điều kiện về tính lồi hoặc lõm của hàm mục tiêu tại điểm đó, giúp xác định điểm đó có phải là cực tiểu hay không. Ví dụ, điều kiện cấp hai liên quan đến đạo hàm bậc hai và tập tiếp xúc cấp hai.

2. Tại sao cần nghiên cứu điều kiện tối ưu cấp hai trong bài toán đa mục tiêu?
   Vì bài toán đa mục tiêu thường không lồi, điều kiện cấp một không đủ để xác định nghiệm tối ưu. Điều kiện cấp hai giúp kiểm tra tính tối ưu chặt chẽ hơn, đặc biệt trong trường hợp không có giả thiết lồi.

3. Làm thế nào để áp dụng định lý Motzkin trong điều kiện tối ưu?
   Định lý Motzkin được sử dụng để chứng minh sự tồn tại của các hệ số nhân tử liên hợp trong điều kiện cần tối ưu cấp hai, đặc biệt khi bài toán có ràng buộc tập hợp lồi đa diện.

4. Phạm vi áp dụng của các điều kiện tối ưu cấp hai trong luận văn là gì?
   Luận văn tập trung vào các bài toán trong không gian tuyến tính hữu hạn chiều với hàm mục tiêu khả vi cấp hai và nón lồi, nhọn có phần trong không rỗng, bao gồm cả trường hợp có và không có ràng buộc tập hợp.

5. Có thể mở rộng kết quả nghiên cứu này cho các bài toán phức tạp hơn không?
   Có, luận văn đề xuất mở rộng nghiên cứu cho các loại nón khác và các bài toán đa mục tiêu phức tạp hơn, cũng như phát triển thuật toán tối ưu dựa trên các điều kiện cấp hai đã chứng minh.

Kết luận

• Luận văn đã làm rõ các khái niệm cơ bản và các điều kiện cần, đủ tối ưu cấp hai trong bài toán tối ưu đa mục tiêu.
• Các mệnh đề và định lý được chứng minh chi tiết, đảm bảo tính chặt chẽ và rõ ràng trong lý thuyết.
• Ứng dụng định lý Motzkin giúp mở rộng phạm vi áp dụng điều kiện tối ưu cấp hai cho bài toán có ràng buộc tập hợp.
• Hạn chế hiện tại là chưa khảo sát đầy đủ các trường hợp nón khác ngoài R^m và chưa phát hiện điều kiện mới vượt trội.
• Hướng nghiên cứu tiếp theo là mở rộng lý thuyết, phát triển thuật toán và ứng dụng trong các lĩnh vực thực tiễn đa tiêu chí.

Để tiếp tục phát triển lĩnh vực này, các nhà nghiên cứu và chuyên gia được khuyến khích áp dụng và mở rộng các kết quả đã đạt được, đồng thời phối hợp nghiên cứu đa ngành nhằm nâng cao hiệu quả và tính ứng dụng của lý thuyết tối ưu đa mục tiêu.

Trích đoạn nội dung tài liệu

Chương 1 Các khái niệm cơ bản của lý thuyết tối ưu đa mục tiêu. §1 Quan hệ thứ tự từng phần trong R”.1 Một quan hệ hai ngôi tren R™ là một tập hợp con không rỗng R của R" x R", khi đó ta oiết zRụ tới (x,y) € R. b) Một quan hệ hai ngôi < trên R"" được gọi là thứ tự từng phần nếu tới moi x,y,2z,w € R™, cdc tinh chất sau được thỏa mãn: i) « <x (Tinh phan 2a). iv) x <y,a € Ry > ax < ay (Tinh twang thich theo nhân tử uô hướng).

©) Thứ tự từng phần < trén R™ được gọi là phản đối xứng nếu: V+,u€lR”,z <,U<+®+=.2 Không gian tuyến tính 8" được trang bị bởi quan hệ thứ tự từng phần được gọi là không gian tuyến tính thứ tự từng phân. ĐIỀU KIEN TOI UU CAP 2 CUA BÀI TOÁN TOI UU DA MỤC TIÊU Thứ tự từng phần trên R” mà ta gọi là thứ tự tự nhiên <„ được xác định bởi: Xm= {(2,y) €R x R" |e; < ụ, Vi = 1 „m}.3 a) Một tập hợp Ở C R”" được gọi là lồi nếu uới mọi +, € € tà À € (0,1) fa có Àz + (1— À)y € Ơ. b) Một tập hợp không réng K C R™ được gọi là nón nếu uới mọi điểm ke K vad >0, ta cb Kk E K, néu K là tập lồi thì nó sẽ được gọi là nón lôi. ©) Nón K được gọi là nón nhọn nếu K ñ\(—K) = {0}.

Nhận xét: Trong không gian hữu hạn chiều JR”, mặt phẳng, đường thẳng, đoạn thẳng, tam giác, hình cầu cho ta các hình ảnh về tập lồi.4 i) Quan hệ thứ tự từng phân có thể được mô tả bởi một nón lài. Bất kỳ thứ tự từng phần < trên R" zác định một nón lồi: K=zeRP"l0, <2}. Và bắt kỳ một nón lồi K C RR", cũng được gọi là nón thứ tự, xác định một thứ tự từng phần trên IR" bỏi: <&k= {(œ,) € R” x R”lụ — z € K}. ii) Nhu vay, cho một nón lồi K C R" thà nó xác định trên R"" một quan hệ thứ tự: V+,u€lR”":z<.

Nguyễn Ngọc Uuển Nhỉ-Luận uăn Thạc sỹ 2017 2 ĐIỀU KIEN TOI UU CAP 2 CUA BÀI TOÁN TOI UU DA MỤC TIÊU §2_ Nghiệm cực tiểu, nghiệm cực tiểu yếu, nghiệm cực tiểu địa phương của bài toán tối ưu đa mục tiêu.1 Cho 7 là tập hợp khác rỗng của không gian tuyến tính R"" được sắp thứ tự từng phần bởi một nón lồi K. Điểm J € T được gọi là K-điểm cực tiểu của tập hợp T nếu: (j~K)nTCÿ+K.1: K-điểm cực tiểu g. Điểm ÿ <x Cho f : R" + R™ va QC R". Giả sử ïR'" được sắp thứ tự bởi nón lồi #.

Xét bài toán tối ưu đa mục tiêu sau: min f(z) (MOP) ren Nguyễn Ngọc Uyển Nhí-Luận uăn Thạc sỹ 2017 3 ĐIỀU KIEN TOI UU CAP 2 CUA BÀI TOÁN TOI UU DA MỤC TIÊU Định nghĩa 1.2 Một điển # € © được gọi là nghiệm cực tiểu (hoặc nghiệm hữu hiệu hoặc K-cực tiểu) của bài toán tối ưu đa mục tiéu (MOP) theo nón thứ tự K nếu ƒ(8) là K-điểm cực tiểu của tập hợp ƒ(©).3 ¡) Tập hợp tắt cả các nghiệm cực tiểu theo nón K ký hiệu là M(ƒ(9), K). ii) Tập hợp ảnh của tập hợp các nghiệm cực tiểu ký hiệu là: z(/(9),K) = {f(a)|x € M(f(Q), K)}- Khi đó e(ƒ(©), K) còn gọi là tập giá trị hữu hiệu. K) được gọi là một giá trị K-cực tiểu (hau hữu hiệu theo nón K). iii) Voi K = R™ thi K-điểm cực tiểu còn được gọi là điểm cực tiểu Edgeuorth-Pareto (EP-điểm cực tiểu).2 là uí dụ uề bài toán tối ưu đa mmục tiêu tới số chiều n = 2.

Tap hop 2 va ƒ(Q) cũng như nón nhọn thứ tự được chỉ ra. Tập giá trị hữu hiệu được biểu thị bởi đường dàu hơn.2: Giá trị hữu hiệu của bài toán tối ưu đa mục tiêu. Nguyễn Ngọc Uyển Nhí-Luận uăn Thạc sỹ 2017 1 ĐIỀU KIEN TOI UU CAP 2 CUA BÀI TOÁN TOI UU DA MỤC TIÊU Định nghĩa 1.4 Cho K là một nón nhọn, lồi, tới inf(K) # Ú. Điểm #€© được gọi là nghiệm cực tiểu yếu của (MOP) theo K nếu: Ứ(Œ) ~ int(K)) n /(9) = 0.5 ¡) Tập hợp tắt cả các nghiệm cực tiểu yếu theo nón K (còn gọi là K-điểm cực tiểu yếu) ký hiệu là M,.

ii) Tập hợp ảnh của tập hợp các điểm cực tiểu yếu là: ewl S(O), K) = {ƒ(z)J# € Mu(ƒ(9), K)} tà được gọi là tập hợp giá trị hữu hiệu yếu theo nón K. iii) K-diém cực tiểu yếu chính là điểm cực tiểu theo nén int(K) U {Om}, do dé, My(f(Q),K) = M(f(Q), int(K) U {Om})- Với bài toán tối ưu đa mục tiêu, ta có các khái niệm về cực tiểu địa phương: Định nghĩa 1.6 Cho K là một nón nhọn, lồi vdi int(K) 4 0. Điểm # € 9 được gọi là nghiệm cực tiểu địa phương của bài toán tối tu đa mục tiêu (MOP) theo nón thứ tự K nếu tồn tại lân cận U của # sao cho không có ụ € Ƒ(QnU)\{ƒ(#)} tới ƒ(8) Ey + K. Điểm # € © được gọi là nghiệm cực tiểu yếu địa phương của bài toán tối ưu đa mục tiêu (MOP) theo nón thứ tự K nếu tồn tại lân cận U của # sao cho không cóụ € ƒ(QñU) uới ƒ(#) € + intK.

Nguyễn Ngọc Uuển Nhỉ-Luận uăn Thạc sỹ 2017 5 ĐIỀU KIEN TOI UU CAP 2 CUA BÀI TOÁN TOI UU DA MỤC TIÊU 2.7 Cho Kì tà Kạ là nón lồi uới Ky C Kp. Chứng minh: VE € M(f(Q), Ke) thì (ƒ(#) — K›) n ƒ(9) C ƒ(#) + K. Vi Ky C Ko nén ky € Ky suy ra y = f(%) — ky € (f(®) — Ke) va y € f(O). Kết quả được phát biểu tương tự với tập hợp các nghiệm cực tiểu yếu.8 Cho K, va K: là nón lồi, nhọn, phần trong khác rỗng tà Kì C Ky.

Khi do: Mu(f(Q), K2) C Mu(f(Q), A). Chitng minh: Véi K; C Ky din dén int(Ky) C int(K2) khi d6: Mu(f (2), Ko) = M(f(Q), int(K2) U {Om}) € M(f(9),im(Ki)U {0„}) = Mu(7(9), Kì).9 Cho K là nón lôi, nhọn, phần trong khác rỗng. Chứng mình: Do ¿n£(Ý) U {0„} C K nên: M(f(Q), K) C M(f(Q), int(K) U {Om}) = Mu(f(Q), K). Nguyén Ngoc Uyén Nhi-Ludn vin Thac si 2017 6 ĐIỀU KIEN TOI UU CAP 2 CUA BÀI TOÁN TOI UU DA MỤC TIÊU Dinh nghia 1.

Diém y € R™ duoc goi là điểm biên ctia A néu vdi moi c > 0 thi Bly,c) 1A 40 va Bly. Tap hợp tắt cả điểm biên của A kí hiệu là OA.11 Cho K là nón lồi, nhọn và K # {0„}. Chứng minh: Tương tự cách chứng minh định lý 1.12 Cho K là một nón nhọn, lồi va int(K) #0. Chứng minh: Lấy bất kỳ ÿ € e„(ƒ(9),K) C ƒ(9).

Ta giả sử ÿ € (/(9)\؃(9)) = imt(ƒ()). Khi đó, 3ð > 0 và hình cầu mở B = {y € R™|||y|] < 5} sao cho 9+ Bc f(Q). Do đó, ta có: Ø+Ak € ƒ(9) n (g — int(K)). Điều này mâu thuẫn với ÿ là K-cực tiểu yếu theo Dinh nghĩa 1.

Nguyễn Ngọc Uuển Nhỉ-Luận uăn Thạc sỹ 2017 7 ĐIỀU KIEN TOI UU CAP 2 CUA BÀI TOÁN TOI UU DA MỤC TIÊU Cho v € T(Q,2)- b) Tap tiếp xúc cấp hai parabolic vdi Q tại (#,) được định nghĩa là tập: 1 T?(Q,@,v) = {w € R"|Atn 4 0*, 3wn > w sao cho Et tavtztnwn <€9,vn eN}. Hay nói cách khác: n Baty w ETO, 2,0) © 3h, > 0", 3x, ED sao cho @— Tw Bhi n 00. ?a ©) Tập tiếp xúc cấp hai asymtotic tới © tại (#,) được định nghĩa là tập: Tỷ(O.Z,) = {w € R"|3t„ —> 0°,+„ —y ÚŸ, tuy —> w sao cho ¥,12 +0 va E+ tyv + Ynwn € ©,Vn € Ñ}. d) Nón tiếp xúc phần trong vdi Q tại # được định nghĩa là tập:: TT(O,#) = {u € R*|Bồ > (0 sao cho 8+ € ©,Vt € (0,6), Vw € B(v, 6)}.2 Gid sit Q là một tập lồi.

Tu nói Q la T?-6n định tại (@,v) €Q x T(Q,2) nếu: 7(0,,) + T(T(9,#),») C T2(0,, v). Chứng minh: Do ø € T(O, #) nên 3f„ + 0* va v, > v sao cho # + f„„ € ©. 1 ï) Nếu s„ = 0 nghĩa là œ„ = 0 thì # + fuЄ # + tạp + sỉ 212. ii) Nếu s„ # Ú với „ —> ø nên s„ > 0*.

Dat wn = „ BÌẢ SỬ tư, —> tứ với một +ø # 0 nào đó. Thi đó, ø„ = s„t0„ + Ð suy ra # + fuЄ = # + tạo + f„sutp„ € Q. Nguyễn Ngọc Uuển Nhỉ-Luận uăn Thạc sỹ 2017 9 ĐIỀU KIEN TOI UU CAP 2 CUA BÀI TOÁN TOI UU DA MỤC TIÊU B _ tn Nếu —“— = — 4 0 voi + thu + tnsnwn € © thi w € T7(Q, #,) (2). » Sp NH0 đc Cứp vế ngó 2 0.8 Sn n ty = 2a — 2rw.

Khi do: B+twt sea tôn = E+ tyv + weeDew, = E+ tad + tsp EQ. Suy ra 2rw € T2(Q, 2,0) (3).4 Cho Q C R" là tập hợp lồi và # € clQ, int A 0. Chứng minh: ï) Ta chứng mình đẳng thức đầu tiên: 77(©,#) = IT(Q,2). Ngược lại, lấy œ € JT(Q,#) nên 3ổ > 0 sao cho # + tw € Q, Vt € (0,4) va Vw € B(u,ô).

Do ¿m© là trù mật trong © (nghĩa là Q C in#M) nên 3z; € infQ sao cho |lri — z2|| = ||E + te — z2|| < é nên # + ti € B(2a,e) C int. ii) Chứng mình đẳng thức cuối: cone¿ (infQ — #) = int cone(Q — #). Do dé, cone, (int — 2) C int(cone(Q = 2). Tiép theo, Lay v = +—#) € cone(Q—#) với œ > 0 và z € 9.

Choe > 0, do intQ la tri mật trong © nên 3z¡ € im£© sao cho ||# — zi||< a1 <. Nguyễn Ngọc Uuển Nhỉ-Luận uăn Thạc sỹ 2017 10 ĐIỀU KIEN TOI UU CAP 2 CUA BÀI TOÁN TOI UU DA MỤC TIÊU Suy ra, inf cone(Q — 2) C cone, (int = 2). iii) Cuối cùng, chứng minh: [T(Q, 2) = int(cone(Q — #)). Lay u € int(cone(Q—2)) C cone(Q— 2), khi d6 u = a(x —2) voia > 0 va x € Q.

Ngược lại, lấy u € IT(Q,2) = IT (int,2) nén 35 > 0 sao cho & + tw € intQ, Vt € (0,6) va Vw € B(u, 6). Khi dé, u € B(w, 6), dat x = % + tw € intl vaa= ; > 0.5 Với nón K = R? tà ụ = (MI.m) € PT", ta có các biểu thức đối uới tập tiếp xúc sau: i) T(RY,y) = {v ER™: v; > 0 nếuj € J(w)}. Tập tuyến tính cấp 1, cấp 2.6 Cho g: R" + RP là một hàm khả oi cấp hai, Q C RP khác rỗng.