Quy hoạch phi tuyến

Quy hoạch phi tuyến tối ưu hóa một hàm mục tiêu phi tuyến trơn chịu các ràng buộc phi tuyến, bao gồm cả lý thuyết về tính tối ưu và các thuật toán tính toán nghiệm.

Definition

Một bài toán quy hoạch phi tuyến nhằm mục tiêu tối thiểu hóa một hàm mục tiêu có thể phi tuyến trên một tập hợp khả thi được xác định bởi các ràng buộc đẳng thức và bất đẳng thức phi tuyến; không giống như các bài toán lồi, nó có thể có nhiều điểm tối ưu cục bộ, vì vậy hầu hết các phương pháp tìm kiếm các điểm thỏa mãn các điều kiện tối ưu cần thiết.

Scope

Chủ đề này bao gồm tối thiểu hóa không ràng buộc, các chiến lược tìm kiếm theo đường và vùng tin cậy, các phương pháp gradient, Newton và quasi-Newton, các điều kiện tối ưu bậc nhất và bậc hai, các điều kiện Karush-Kuhn-Tucker và các điều kiện ràng buộc, cũng như các phương pháp có ràng buộc như phạt, Lagrangian tăng cường và quy hoạch bậc hai tuần tự.

Core questions

• Những điều kiện nào đặc trưng cho một điểm tối ưu cục bộ của một bài toán phi tuyến có ràng buộc?
• Các phương pháp giảm dần tìm điểm dừng của một bài toán không ràng buộc như thế nào?
• Các ràng buộc được tích hợp vào các thuật toán lặp như thế nào?
• Khi nào một điểm tối ưu cục bộ được tính toán có thể được tin cậy là tối ưu toàn cục?

Key theories

Các điều kiện tối ưu

Các điều kiện Karush-Kuhn-Tucker bậc nhất và các điều kiện độ cong bậc hai đặc trưng cho các điểm tối ưu cục bộ của các bài toán có ràng buộc dưới các điều kiện ràng buộc thích hợp.

Các phương pháp giảm dần và kiểu Newton

Các phương pháp gradient, Newton và quasi-Newton tạo ra các hướng giảm dần và sử dụng tìm kiếm theo đường hoặc vùng tin cậy để hội tụ đến các điểm dừng, với các cập nhật quasi-Newton xấp xỉ độ cong với chi phí thấp.

Các thuật toán tối ưu hóa có ràng buộc

Các phương pháp phạt, Lagrangian tăng cường và quy hoạch bậc hai tuần tự chuyển đổi các bài toán có ràng buộc thành một chuỗi các bài toán đơn giản hơn, xử lý các ràng buộc đẳng thức và bất đẳng thức một cách có hệ thống.

Clinical relevance

Quy hoạch phi tuyến được sử dụng ở những nơi mà các mục tiêu hoặc ràng buộc không tuyến tính, bao gồm việc điều chỉnh mô hình và huấn luyện các mô hình thống kê và học máy, thiết kế kỹ thuật, điều khiển tối ưu và ước lượng tham số trong các ngành khoa học.

History

Các điều kiện Karush-Kuhn-Tucker, được thiết lập vào năm 1951 và được Karush dự đoán vào năm 1939, đã tổng quát hóa các nhân tử Lagrange cho các ràng buộc bất đẳng thức và đặt nền móng cho lý thuyết phi tuyến có ràng buộc. Các phương pháp quasi-Newton, Lagrangian tăng cường và quy hoạch bậc hai tuần tự đã phát triển trong suốt nửa sau thế kỷ XX thành bộ công cụ tính toán tiêu chuẩn.

Key figures

• Harold Kuhn
• Albert Tucker
• Isaac Newton
• Magnus Hestenes

Seminal works

• nocedal2006
• bertsekas1999

Frequently asked questions

Tại sao quy hoạch phi tuyến khó hơn quy hoạch tuyến tính?

Các bài toán phi tuyến có thể có các vùng khả thi cong và nhiều điểm tối ưu cục bộ, vì vậy nhìn chung không có gì đảm bảo rằng một nghiệm được tính toán là tốt nhất toàn cục, và các điểm tối ưu không nhất thiết phải nằm ở các đỉnh. Các thuật toán phải dựa vào thông tin cục bộ như gradient và độ cong.

Phương pháp quasi-Newton là gì?

Đây là một phương pháp lặp xấp xỉ bước Newton mà không cần tính toán ma trận đạo hàm bậc hai đầy đủ, xây dựng thông tin độ cong từ các gradient liên tiếp. Các phương pháp như BFGS đạt được sự hội tụ nhanh với chi phí thấp hơn nhiều so với các bước Newton chính xác.