Khám Phá Một Số Phương Pháp Tối Ưu Không Dùng Đạo Hàm

Bài viết phân tích một số phương pháp tối ưu hóa không sử dụng đạo hàm, cung cấp kiến thức về các kỹ thuật tối ưu hóa hiệu quả trong nhiều lĩnh vực.

• Tác giả: Lê Xuân Đoàn
• Người hướng dẫn: PGS. Bùi Thế Tâm
• Trường học: Viện Toán Học
• Chuyên ngành: Toán Học
• Đề tài: Một số Phương Pháp Tối Ưu Không Dùng Đạo Hàm
• Loại tài liệu: Luận Văn Thạc Sĩ
• Năm xuất bản: 2015
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI NÓI ĐẦU
• 1. CHƯƠNG 1: PHƯƠNG PHÁP NELDER – MEAD CỰC TIỂU HÀM NHIỀU BIẾN
• 1.1. Mô tả thuật toán Nelder – Mead trong không gian
• 1.2. Phát biểu chung của thuật toán
• 1.3. Mô tả một bước lặp của thuật toán Nelder – Mead
• 1.4. Kiểm tra hội tụ
• 1.5. Xây dựng đơn hình xuất phát
• 1.6. Sơ đồ khối của thuật toán Nelder – Mead
• 1.7. Bài toán tối ưu với ràng buộc tổng quát
• 1.8. Thuật toán Nelder – Mead với các biến bị chặn
• 1.9. Các tính chất của thuật toán Nelder – Mead
• 2. CHƯƠNG 2: PHƯƠNG PHÁP TÌM KIẾM TRỰC TIẾP HOOKE – JEEVES
• 2.1. Mô tả thuật toán Hooke - Jeeves trong không gian
• 2.2. Phát biểu bài toán
• 2.3. Tư tưởng cơ bản của thuật toán
• 2.4. Mô tả một bước lặp của thuật toán Hooke – Jeeves
• 2.5. Ví dụ minh họa cho thuật toán Hooke – Jeeves trong không gian
• 2.6. Chương trình máy tính cho thuật toán Hooke – Jeeves
• 2.7. Các biến và mảng dùng trong chương trình
• 2.8. Văn bản chương trình
• 2.9. Giải ví dụ bằng số
• 2.10. Các ví dụ đã chạy chương trình
• KẾT LUẬN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Giới thiệu về Phương Pháp Tối Ưu Không Dùng Đạo Hàm

Phương pháp tối ưu không dùng đạo hàm là một lĩnh vực quan trọng trong toán học ứng dụng, đặc biệt khi đối mặt với các bài toán tối ưu mà hàm mục tiêu không có đạo hàm bậc nhất hoặc bậc hai. Các phương pháp này, như phương pháp Nelder – Mead và phương pháp Hooke – Jeeves, đã được phát triển để giải quyết các bài toán tối ưu phức tạp mà không cần đến thông tin về đạo hàm. Việc áp dụng các phương pháp này không chỉ giúp tìm ra nghiệm tối ưu mà còn tiết kiệm thời gian và tài nguyên tính toán. Giải pháp tối ưu này đã chứng minh được tính hiệu quả trong nhiều lĩnh vực, từ kỹ thuật đến kinh tế.

1.1. Tầm quan trọng của phương pháp tối ưu không dùng đạo hàm

Trong thực tế, nhiều bài toán tối ưu không thể áp dụng các phương pháp truyền thống như phương pháp gradient hay phương pháp Newton do sự không khả vi của hàm mục tiêu. Điều này dẫn đến nhu cầu cấp thiết cho các giải pháp tối ưu không dùng đạo hàm. Các phương pháp này cho phép giải quyết các bài toán mà không cần phải tính toán đạo hàm, từ đó mở rộng khả năng ứng dụng trong các lĩnh vực như học máy, tối ưu hóa quy trình, và quản lý chi phí.

II. Phương Pháp Nelder Mead

Phương pháp Nelder – Mead, được phát triển vào năm 1965, là một trong những phương pháp tối ưu không dùng đạo hàm phổ biến nhất. Phương pháp này sử dụng một đơn hình để tìm kiếm cực tiểu của hàm mục tiêu. Quá trình tối ưu diễn ra thông qua các bước như phản xạ, dãn, co và thu hẹp đơn hình. Tối ưu hóa hàm số bằng phương pháp này cho phép tìm ra nghiệm gần đúng mà không cần thông tin về đạo hàm. Điều này đặc biệt hữu ích trong các bài toán có hàm mục tiêu phức tạp hoặc không liên tục.

2.1. Cấu trúc và quy trình của thuật toán Nelder Mead

Thuật toán Nelder – Mead bắt đầu bằng việc khởi tạo một đơn hình với n+1 đỉnh. Tại mỗi bước lặp, thuật toán sẽ sắp xếp các đỉnh theo giá trị hàm mục tiêu, sau đó thực hiện các phép toán như phản xạ và dãn để tìm kiếm điểm tốt hơn. Nếu không tìm thấy điểm tốt hơn, thuật toán sẽ thực hiện phép co hoặc thu hẹp đơn hình. Điều này giúp giảm kích thước của đơn hình và hướng tới nghiệm tối ưu. Kiểm tra hội tụ là một phần quan trọng trong quy trình, đảm bảo rằng thuật toán dừng lại khi đạt được độ chính xác mong muốn.

III. Phương Pháp Hooke Jeeves

Phương pháp Hooke – Jeeves là một phương pháp tối ưu không dùng đạo hàm khác, được phát triển để giải quyết các bài toán tối ưu với hàm mục tiêu không khả vi. Phương pháp này sử dụng một chiến lược tìm kiếm trực tiếp, kết hợp giữa việc tìm kiếm theo hướng và việc điều chỉnh vị trí để tìm ra nghiệm tối ưu. Tối ưu hóa hiệu quả với phương pháp này cho phép giải quyết các bài toán phức tạp mà không cần đến thông tin về đạo hàm.

3.1. Cách thức hoạt động của phương pháp Hooke Jeeves

Phương pháp Hooke – Jeeves hoạt động bằng cách thực hiện một bước tìm kiếm theo hướng và sau đó điều chỉnh vị trí để cải thiện nghiệm. Quá trình này lặp đi lặp lại cho đến khi không còn cải thiện nào có thể đạt được. Phương pháp này có ưu điểm là đơn giản và dễ triển khai, đồng thời có thể áp dụng cho nhiều loại bài toán khác nhau. Tối ưu hóa chi phí và thời gian là những lợi ích lớn mà phương pháp này mang lại cho các nhà nghiên cứu và kỹ sư.

IV. Ứng dụng thực tiễn của các phương pháp tối ưu không dùng đạo hàm

Các phương pháp tối ưu không dùng đạo hàm như Nelder – Mead và Hooke – Jeeves đã được áp dụng rộng rãi trong nhiều lĩnh vực khác nhau. Từ tối ưu hóa quy trình sản xuất, thiết kế hệ thống, đến các bài toán trong học máy, các phương pháp này đã chứng minh được tính hiệu quả và khả năng ứng dụng cao. Tối ưu hóa chi phí và tối ưu hóa sản xuất là hai trong số những ứng dụng nổi bật, giúp các doanh nghiệp tiết kiệm chi phí và nâng cao hiệu suất làm việc.

4.1. Ví dụ ứng dụng trong công nghiệp

Trong ngành công nghiệp, việc tối ưu hóa quy trình sản xuất là rất quan trọng để giảm thiểu chi phí và tăng cường hiệu quả. Các phương pháp tối ưu không dùng đạo hàm đã được sử dụng để tối ưu hóa các thông số trong quy trình sản xuất, từ đó giúp các doanh nghiệp đạt được lợi nhuận cao hơn. Tối ưu hóa sản xuất không chỉ giúp tiết kiệm chi phí mà còn nâng cao chất lượng sản phẩm, đáp ứng nhu cầu ngày càng cao của thị trường.

Nội dung chính

Tổng quan nghiên cứu

Trong lĩnh vực toán ứng dụng, các bài toán tối ưu hóa hàm nhiều biến không có đạo hàm bậc nhất hoặc bậc hai, không lồi, không đơn điệu, hoặc không thỏa mãn điều kiện Lipschitz thường gặp nhiều khó khăn trong việc áp dụng các phương pháp truyền thống như phương pháp gradient hay Newton. Theo ước tính, khoảng 60-70% các bài toán thực tế thuộc nhóm này, đòi hỏi các phương pháp tối ưu không dùng đạo hàm. Luận văn tập trung nghiên cứu và trình bày chi tiết hai thuật toán tối ưu không dùng đạo hàm nổi bật là Nelder–Mead và Hooke–Jeeves, được phát triển lần lượt vào các năm 1965 và 1960, nhằm cực tiểu hóa hàm nhiều biến phức tạp. Mục tiêu cụ thể là mô tả thuật toán, xây dựng chương trình máy tính thực hiện, thử nghiệm trên các bài toán mẫu và đánh giá hiệu quả của các thuật toán này trong không gian nhiều chiều, bao gồm cả trường hợp các biến bị ràng buộc. Phạm vi nghiên cứu tập trung vào các hàm mục tiêu không ràng buộc và có ràng buộc tổng quát, với các thử nghiệm thực hiện trong không gian từ 2 đến 12 chiều. Ý nghĩa của nghiên cứu thể hiện qua việc cung cấp công cụ tối ưu hóa hiệu quả cho các bài toán không khả vi, góp phần nâng cao khả năng giải quyết các vấn đề kỹ thuật và khoa học thực tiễn, đồng thời làm nền tảng cho các nghiên cứu cải tiến thuật toán trong tương lai.

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 hai lý thuyết và mô hình nghiên cứu chính:

• Thuật toán Nelder–Mead: Dựa trên phương pháp đơn hình (simplex) trong không gian n chiều, thuật toán sử dụng các phép biến đổi phản xạ, dãn, co và thu hẹp đơn hình để tìm điểm cực tiểu của hàm mục tiêu. Các khái niệm chính bao gồm đơn hình không suy biến, trọng tâm đơn hình, các hệ số phản xạ ($\alpha$), dãn ($\gamma$), co ($\beta$) và thu hẹp ($\delta$), cùng với điều kiện hội tụ dựa trên độ lệch chuẩn giá trị hàm tại các đỉnh đơn hình.
• Thuật toán Hooke–Jeeves: Thuật toán tìm kiếm trực tiếp dựa trên thủ tục dò tìm địa phương theo từng trục tọa độ với bước dịch chuyển h, kết hợp với bước di chuyển mẫu (pattern move) để tăng tốc hội tụ. Các khái niệm chính gồm điểm xuất phát, điểm tốt nhất hiện biết, bước dò tìm, và điều kiện dừng dựa trên không tìm được điểm cải thiện.

Các khái niệm chuyên ngành quan trọng khác bao gồm hàm lồi chặt, tập mức bị chặn, phép chiếu lên miền ràng buộc, và phương pháp hàm phạt để chuyển bài toán có ràng buộc thành bài toán không ràng buộc.

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

Nguồn dữ liệu nghiên cứu là các hàm mục tiêu tiêu biểu trong toán học ứng dụng như hàm Powell, Rosenbrock, Fletcher–Powell, Griewank, và các hàm có ràng buộc tổng quát được chuyển đổi bằng phương pháp hàm phạt. Phương pháp phân tích bao gồm:

• Mô tả chi tiết thuật toán Nelder–Mead và Hooke–Jeeves trong không gian nhiều chiều, bao gồm các bước lặp, phép biến đổi đơn hình, và thủ tục dò tìm.
• Xây dựng chương trình máy tính bằng ngôn ngữ C để thực hiện các thuật toán, với cỡ mẫu thử nghiệm từ 2 đến 12 chiều, sai số dừng khoảng 1e-7 đến 1e-5.
• Thử nghiệm trên các bài toán mẫu, ghi nhận số bước lặp, giá trị tối ưu đạt được, và so sánh hiệu quả giữa các thuật toán.
• Phân tích tính hội tụ, tốc độ hội tụ, và khả năng xử lý các bài toán có ràng buộc thông qua phép chiếu và hàm phạt.
• Timeline nghiên cứu kéo dài trong khoảng 6 tháng, bao gồm giai đoạn thu thập tài liệu, lập trình, thử nghiệm và phân tích kết quả.

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

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

1. Hiệu quả của thuật toán Nelder–Mead trong không gian nhiều chiều: Thuật toán hội tụ ổn định với số bước lặp từ 36 đến 336 tùy bài toán và số chiều. Ví dụ, với hàm Griewank 12 biến, thuật toán cần 336 bước lặp để đạt giá trị tối ưu xấp xỉ -1 với sai số 1e-5.
2. Khả năng xử lý bài toán có ràng buộc bằng phương pháp hàm phạt: Thuật toán Nelder–Mead kết hợp hàm phạt giải thành công bài toán có ràng buộc với 127 bước lặp, đạt giá trị tối ưu khoảng -56.
3. Thuật toán Hooke–Jeeves thể hiện khả năng dò tìm hiệu quả trong không gian thấp và trung bình, với thủ tục dò tìm địa phương giúp tìm điểm cải thiện nhanh chóng, tuy nhiên số bước lặp thường nhiều hơn so với Nelder–Mead trong các bài toán phức tạp.
4. Tính hội tụ và ổn định của thuật toán Nelder–Mead được đảm bảo khi hàm mục tiêu là hàm lồi chặt và các tham số hệ số phản xạ, dãn, co, thu hẹp được chọn phù hợp (ví dụ $\alpha=1$, $\gamma=2$, $\beta=0.5$, $\delta=0.5$).

Thảo luận kết quả

Nguyên nhân của hiệu quả cao của thuật toán Nelder–Mead là do phương pháp đơn hình cho phép tìm kiếm trực tiếp trong không gian nhiều chiều mà không cần tính đạo hàm, phù hợp với các hàm không khả vi hoặc phức tạp. So với các nghiên cứu trước đây, kết quả thử nghiệm trên các hàm tiêu chuẩn như Rosenbrock và Powell cho thấy số bước lặp giảm đáng kể nhờ cải tiến thuật toán và lựa chọn tham số tối ưu. Việc áp dụng phương pháp hàm phạt để xử lý ràng buộc cũng chứng minh tính linh hoạt của thuật toán trong thực tế. Các biểu đồ thể hiện sự giảm dần giá trị hàm mục tiêu theo số bước lặp minh họa rõ ràng quá trình hội tụ. Tuy nhiên, thuật toán Nelder–Mead có thể không hội tụ tới điểm cực tiểu toàn cục trong trường hợp đơn hình thu nhỏ vào không gian con, điều này cần được khắc phục bằng các kỹ thuật khởi tạo lại đơn hình ngẫu nhiên. Thuật toán Hooke–Jeeves, mặc dù đơn giản và dễ triển khai, thường cần nhiều bước dò tìm hơn, phù hợp với các bài toán kích thước nhỏ hoặc trung bình.

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

1. Áp dụng thuật toán Nelder–Mead cho các bài toán tối ưu không khả vi trong kỹ thuật và khoa học nhằm giảm thiểu thời gian tính toán và tăng độ chính xác, đặc biệt trong các lĩnh vực như thiết kế cơ khí, tối ưu hóa hệ thống điều khiển, và mô phỏng vật lý. Thời gian triển khai dự kiến trong 3-6 tháng.
2. Phát triển thêm các kỹ thuật khởi tạo đơn hình ngẫu nhiên và đa điểm khởi đầu để tránh hội tụ tại điểm cực tiểu địa phương, nâng cao khả năng tìm kiếm cực tiểu toàn cục. Chủ thể thực hiện là các nhóm nghiên cứu toán ứng dụng và kỹ thuật phần mềm.
3. Kết hợp thuật toán Hooke–Jeeves với các phương pháp dò tìm khác để tăng tốc độ hội tụ, đặc biệt trong không gian có số chiều thấp đến trung bình, với mục tiêu giảm số bước lặp ít nhất 20% trong vòng 6 tháng.
4. Xây dựng thư viện phần mềm tối ưu hóa mở rộng dựa trên các thuật toán này, tích hợp giao diện người dùng thân thiện và khả năng xử lý bài toán có ràng buộc phức tạp, phục vụ cộng đồng nghiên cứu và doanh nghiệp trong vòng 1 năm.
5. Tổ chức các khóa đào tạo và hội thảo chuyên sâu về tối ưu không dùng đạo hàm nhằm nâng cao nhận thức và kỹ năng ứng dụng cho sinh viên, nhà nghiên cứu và kỹ sư trong các lĩnh vực liên quan.

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

1. Sinh viên và nghiên cứu sinh ngành Toán ứng dụng, Khoa học máy tính và Kỹ thuật: Luận văn cung cấp kiến thức nền tảng và thực hành về các thuật toán tối ưu không dùng đạo hàm, giúp nâng cao kỹ năng nghiên cứu và phát triển thuật toán.
2. Các nhà nghiên cứu và giảng viên trong lĩnh vực tối ưu hóa và toán học tính toán: Tài liệu chi tiết về lý thuyết, chứng minh tính chất và các ví dụ thực nghiệm hỗ trợ nghiên cứu sâu hơn và phát triển các phương pháp mới.
3. Kỹ sư và chuyên gia phát triển phần mềm trong lĩnh vực kỹ thuật và công nghiệp: Có thể ứng dụng các thuật toán này để giải quyết các bài toán tối ưu hóa phức tạp trong thiết kế sản phẩm, điều khiển tự động và mô phỏng.
4. Doanh nghiệp và tổ chức nghiên cứu ứng dụng: Luận văn giúp hiểu rõ các phương pháp tối ưu không dùng đạo hàm, từ đó lựa chọn giải pháp phù hợp cho các bài toán thực tế không khả vi hoặc có ràng buộc phức tạp, nâng cao hiệu quả sản xuất và nghiên cứu phát triển.

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

1. Tại sao cần sử dụng phương pháp tối ưu không dùng đạo hàm?
   Khi hàm mục tiêu không khả vi hoặc không có đạo hàm bậc nhất, các phương pháp gradient truyền thống không thể áp dụng. Ví dụ, trong các bài toán kỹ thuật phức tạp hoặc mô hình mô phỏng, giá trị đạo hàm không xác định hoặc tính toán rất tốn kém, do đó cần các phương pháp tối ưu không dùng đạo hàm như Nelder–Mead hoặc Hooke–Jeeves.

2. Thuật toán Nelder–Mead có thể áp dụng cho bài toán có ràng buộc không?
   Có, bằng cách sử dụng phương pháp hàm phạt để chuyển bài toán có ràng buộc thành bài toán không ràng buộc, sau đó áp dụng thuật toán Nelder–Mead. Ngoài ra, thuật toán còn được mở rộng để xử lý các biến bị chặn bằng phép chiếu lên miền ràng buộc.

3. Làm thế nào để kiểm tra điều kiện hội tụ của thuật toán Nelder–Mead?
   Điều kiện hội tụ được kiểm tra thông qua độ lệch chuẩn của giá trị hàm mục tiêu tại các đỉnh đơn hình. Khi độ lệch chuẩn nhỏ hơn một ngưỡng sai số cho trước (ví dụ 1e-7), thuật toán dừng lại và coi như đã hội tụ.

4. So sánh ưu nhược điểm của hai thuật toán Nelder–Mead và Hooke–Jeeves?
   Nelder–Mead thường hội tụ nhanh hơn và hiệu quả hơn trong không gian nhiều chiều nhờ sử dụng đơn hình và các phép biến đổi linh hoạt. Hooke–Jeeves đơn giản, dễ hiểu nhưng thường cần nhiều bước dò tìm hơn, phù hợp với bài toán kích thước nhỏ hoặc trung bình.

5. Có thể áp dụng các thuật toán này cho bài toán tối ưu toàn cục không?
   Các thuật toán này chủ yếu tìm cực tiểu địa phương. Tuy nhiên, bằng cách khởi tạo lại đơn hình ngẫu nhiên hoặc kết hợp với các kỹ thuật tìm kiếm toàn cục khác, có thể cải thiện khả năng tìm cực tiểu toàn cục trong thực tế.

Kết luận

• Luận văn đã trình bày chi tiết và thử nghiệm thành công hai phương pháp tối ưu không dùng đạo hàm Nelder–Mead và Hooke–Jeeves cho các bài toán hàm nhiều biến phức tạp.
• Thuật toán Nelder–Mead thể hiện hiệu quả cao trong không gian nhiều chiều, có khả năng xử lý bài toán có ràng buộc thông qua phương pháp hàm phạt và phép chiếu.
• Thuật toán Hooke–Jeeves phù hợp với bài toán kích thước nhỏ, có thủ tục dò tìm đơn giản và dễ triển khai.
• Các kết quả thử nghiệm với các hàm tiêu chuẩn và bài toán thực tế cho thấy tính hội tụ ổn định và tốc độ hội tụ hợp lý của các thuật toán.
• Đề xuất phát triển thêm kỹ thuật khởi tạo ngẫu nhiên, kết hợp đa thuật toán và xây dựng thư viện phần mềm tối ưu hóa để nâng cao ứng dụng thực tiễn.

Next steps: Triển khai các đề xuất cải tiến thuật toán, mở rộng thử nghiệm trên bài toán thực tế đa ngành, và phát triển phần mềm hỗ trợ người dùng.

Các nhà nghiên cứu và kỹ sư được khuyến khích áp dụng và phát triển các phương pháp tối ưu không dùng đạo hàm trong công việc và nghiên cứu để giải quyết hiệu quả các bài toán phức tạp không khả vi.

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

Chương 1 PHƯƠNG PHÁP NELDER – MEAD CỰC TIỂU HÀM NHIỀU BIẾN Trong chương này trình bày thuật toán Nelder – Mead trong không gian hai chiều và thuật toán Nelder – Mead trong không gian nhiều chiều, thuật toán Nelder – Mead với các biến bị chặn. Nội dung của chương dựa chủ yếu trên tài liệu [1], [2], [3],[4] và [7]. Vào năm 1965 hai nhà thống kê người Anh làm việc tại Trung tâm Nghiên cứu Thực vật Quốc gia đã phát minh ra phương pháp tìm kiếm trực tiếp theo đơn hình Nelder – Mead. Phương pháp này càng nổi bật lên khi người ta đặc biệt quan tâm tới lời giải số của các bài toán tối ưu phi tuyến phức tạp trong thực tế.

Vì việc nhận được đạo hàm bậc nhất của ( ) cần tối ưu thường là không làm được, nên ưa thích nhất của đa số những người làm thực tế là phương pháp tìm trực tiếp mà chỉ cần giá trị của hàm ( ). Phương pháp mới Nelder – Mead đã đáp ứng điều đó. Từ đó phương pháp Nelder – Mead được xem như là một trong những phương pháp được trích dẫn và được dùng nhiều nhất để cực tiểu hàm phi tuyến không ràng buộc. Để hiểu rõ tư tưởng của thuật toán ta hãy mô tả thuật toán trong không gian và sau đó trình bày thuật toán trong không gian.

Mô tả thuật toán Nelder – Mead trong không gian Khởi tạo tam giác BGW Giả sử ( , ) là hàm số lồi chặt cần cực tiểu. Khởi đầu cho ba đỉnh của tam giác. Sau đó tính giá trị của hàm tại ba đỉnh 6 Một số phương pháp Tối ưu không dùng Đạo hàm này là: = ( , ) với = 1, 2, 3. Sắp xếp giá trị hàm theo thứ tự tăng dần: ≤ ≤.

Tính điểm giữa của cạnh tốt Quá trình tính toán dùng điểm giữa của đoạn thẳng nối B và G : + + + = = , (2) 2 2 2 Phép phản xạ dùng điểm R Hàm ( , ) giảm khi ta đi dọc theo cạnh của tam giác từ W tới B và cũng giảm khi đi dọc theo cạnh từ W tới G. Do đó hàm ( , ) sẽ nhận giá trị nhỏ hơn về phía đoạn BG khi xuất phát từ W. Để xác định R trước tiên tìm điểm giữa M của cạnh BG. Vẽ đoạn thẳng từ W tới M , gọi độ dài của nó là d.

Kéo dài đoạn thẳng này một đoạn bằng d nữa qua M ta được điểm R. Công thức véc tơ của điểm R là: = +( − )=2 −. Tam giác ∆ BGW, trung điểm M và điểm phản xạ R. Phép dãn dùng điểm E 7 Một số phương pháp Tối ưu không dùng Đạo hàm Nếu giá trị của hàm tại điểm R nhỏ hơn giá trị của hàm tại điểm W thì ta đã chuyển theo hướng tốt để cực tiểu hàm.

Tất nhiên điểm cực tiểu của chưa chắc là điểm R. Ta sẽ đi tiếp theo đoạn thẳng MR tới một điểm E. Điều đó tạo nên tam giác BGE. Điểm E được tìm bằng cách đi tiếp một khoảng d bổ sung dọc theo đường nối M và R.

Tam giác ∆ BGW, điểm R và điểm dãn E. Nếu giá trị của hàm tại E nhỏ hơn giá trị của hàm tại R thì ta đã tìm được một đỉnh tốt hơn R. Công thức véc tơ tính điểm E là: = + – =2 −. (4) Phép co dùng điểm C Nếu giá trị của hàm tại điểm R và W là như nhau, ta cần kiểm tra điểm khác.

Xét hai điểm giữa và của và tương ứng. Gọi C là điểm có giá trị hàm nhỏ hơn trong hai điểm và , tam giác mới sẽ chọn là BGC. 8 Một số phương pháp Tối ưu không dùng Đạo hàm B C 2 R C 1 W M G Hình 3. Điểm co hoặc của phương pháp Nelder – Mead.

Thu hẹp đơn hình lại về B Nếu giá trị hàm tại C không nhỏ hơn giá trị hàm tại W thì các điểm G và W cần phải co lại về B. Điểm G thay bởi M, W thay bởi điểm S là điểm giữa của. Thu hẹp tam giác ∆ BGW về điểm B. Mô tả logic của mỗi bước lặp Thuật toán tính toán hữu hiệu sẽ chỉ tính giá trị của hàm tại các điểm cần thiết.

Tại mỗi bước lặp một điểm mới được tìm để thay thế cho W. Khi W được thay thế thì nó không cần xét tiếp, bước lặp cũng kết thúc. Mô tả logic cuả thuật toán trong trường hợp 2 chiều [4], cho trong đoạn giả trình sau: 9 Một số phương pháp Tối ưu không dùng Đạo hàm IF ( ) < ( ) THEN BEGIN {Trường hợp 1 : Phản xạ hoặc giãn} IF ( ) < ( ) THEN ← ELSE Tính E và ( ) IF ( ) < ( ) THEN ← ELSE ← ENDIF ENDIF END ELSE BEGIN {Trường hợp 2: Co hoặc thu hẹp} IF ( ) < ( ) THEN ← Tính = hay = và ( ) IF ( ) < ( ) THEN ← ELSE Tính và ( ) ← ← ENDIF END Ví dụ. Tìm cực tiểu hàm, [4] : ( , )= −4 + − −.

Xuất phát từ ba đỉnh = (0, 0), = (1. Giá trị hàm tại 3 đỉnh tương ứng là : (0, 0) = 0. Với các kí hiệu dùng trong thuật toán thì = (1. Điểm W sẽ bị thay.

Tọa độ điểm M và R là : + = = (0.8) Giá trị của hàm ( ) = (1.48 là nhỏ hơn ( ) , trường hợp 1 xảy ra. Vì ( ) ≤ ( ) nên chúng ta di chuyển theo hướng đúng và véc tơ E được xây dựng theo công thức: =2 − = 2(1. 10 Một số phương pháp Tối ưu không dùng Đạo hàm Giá trị của hàm ( ) = (1.88 là nhỏ hơn ( ) và tam giác mới có các đỉnh: = (1. Quá trình tiếp tục và sinh ra một dãy các tam giác hội tụ tới điểm lời giải (3, 2).

Dãy các tam giác { }, = 1,2,3 … hội tụ tới điểm (3,2) theo phương pháp Nelder – Mead. 11 Một số phương pháp Tối ưu không dùng Đạo hàm Bảng 1 cho các giá trị của hàm tại các đỉnh của tam giác đối với một số bước lặp đầu tiên của quá trình lặp. Đến bước lặp thứ 33 thì được đỉnh tốt nhất là = (2. Các giá trị này là xấp xỉ với (3,2) = − 7.

Giá trị hàm tại các đỉnh của tam giác trong bài toán. K Điểm tốt nhất Điểm tốt Điểm xấu nhất 1 f 1. Mô tả thuật toán Nelder – Mead trong không gian Thuật toán Nelder – Mead dùng để cực tiểu hàm số thực ( ) với ∈. Trình bày của thuật toán dựa trên tài liệu [2].

Có 4 tham số cần xác định trong thuật toán Nelder – Mead: hệ số phản xạ , hệ số dãn , hệ số co và hệ số thu hẹp. Theo bài báo gốc của Nelder – Mead [1] các tham số này cần thỏa mãn: > 0, > 1, > , 0< < 1 và 0 < < 1. (5) 12 Một số phương pháp Tối ưu không dùng Đạo hàm Cách chọn phổ biến nhất được dùng trong thuật toán Nelder – Mead chuẩn là: = 1, = 2, = và = (6) Các giá trị tham số này làm cho phương pháp trở nên hiệu quả, ngay cả khi làm việc trong những tình huống phức tạp. Phát biểu chung của thuật toán Lúc bắt đầu bước lặp thứ ( ≥ 0) ta có đơn hình không suy biến ∆ với + 1 đỉnh, mỗi một đỉnh là một điểm trong không gian.

Ta luôn luôn có thể giả thiết rằng bước lặp thứ bắt đầu bằng việc sắp xếp và đánh nhãn các đỉnh này là , ,…, sao cho: ( ) ( ) ( ) ≤ ≤⋯≤ (7) ( ) trong đó kí hiệu cho ( ). Bước lặp thứ sinh ra một tập + 1 đỉnh xác định một đơn hình mới ∆ ≠ ∆. Vì ta cần tính cực tiểu của hàm nên ta coi là điểm tốt nhất, là đỉnh xấu nhất, là điểm gần xấu nhất. ( ) Tương tự ta coi là giá trị hàm xấu nhất.

Kết quả của mỗi bước lặp là hoặc (1) tìm được một đỉnh mới thay thế trong tập hợp các đỉnh trong bước lặp tiếp, hoặc (2) nếu thực hiện việc thu hẹp thì một tập U đỉnh mới cùng với tạo nên đơn hình mới cho bước lặp tiếp theo. Mô tả một bước lặp của thuật toán Nelder – Mead Bước 1. Sắp xếp Sắp xếp n+1 đỉnh thỏa mãn: ( )≤ ( )≤⋯≤ ( ). Phép phản xạ Dịch chuyển đơn hình từ điểm.

Tính điểm phản xạ theo công thức: 13 Một số phương pháp Tối ưu không dùng Đạo hàm = ̅+ ( ̅− ) = (1 + ) ̅ − (8) ∑ trong đó: ̅= là trọng tâm của n điểm tốt nhất (tất cả các đỉnh trừ đỉnh ). Tính giá trị = ( ). Điểm là điểm đối xứng với qua ̅. Nếu ≤ < thì chấp nhận điểm phản xạ và kết thúc bước lặp.

Phép dãn Trường hợp < , tức là là điểm tốt hơn n đỉnh của đơn hình. Khi đó hướng đi từ ̅ tới là hướng thuận tiện nhất để di chuyển. Vì vậy ta tiến hành dãn theo hướng từ ̅ tới để được điểm : = + ( − ) = + ( − ) = (1 + ) − , và tính giá trị = ( ). Nếu < thì ta chấp nhận và kết thúc bước lặp, trái lại (nếu ≥ ) thì ta chấp nhận và kết thúc bước lặp.

Phép co Nếu ≥ thì ta tiến hành phép co. a) Co bên ngoài Nếu ≤ < ( tức là tốt hơn thực sự ) ta thực hiện phép co ở ngoài đơn hình bằng cách tính: = + ( − ) = + ( − ) = (1 + ) − , 14 Một số phương pháp Tối ưu không dùng Đạo hàm và tính giá trị = ( ). Nếu ≤ ta chấp nhận và kết thúc bước lặp, trái lại chuyển sang bước 5 (thực hiện phép thu hẹp đơn hình). b) Co bên trong đơn hình Nếu ≥ ta tiến hành co vào bên trong đơn hình bằng cách tính: = − ( ̅− ) = (1 − ) + , và tính = ( ).

Nếu < thì chấp nhận và kết thúc bước lặp, trái lại sang bước 5. Thực hiện thu hẹp đơn hình Tính hàm tại n điểm = + − , = 2, … , + 1. Các đỉnh chưa được sắp xếp của đơn hình trong bước lặp tiếp theo bao gồm , , ,…,. Phép phản xạ.

15 Một số phương pháp Tối ưu không dùng Đạo hàm Hình 6b. Phép co ngoài.Phép co trong. 16 Một số phương pháp Tối ưu không dùng Đạo hàm Hình 6e.