Lập trình phi tuyến

Lập trình phi tuyến (NLP) — là một nhánh của lập trình toán học và nghiên cứu vận trù, chuyên giải quyết các bài toán tối ưu hóa trong đó hàm mục tiêu và/hoặc ít nhất một trong các ràng buộc là hàm phi tuyến theo các biến quyết định.

NLP là sự tổng quát hóa của lập trình tuyến tính và cho phép mô hình hóa một lớp rộng hơn các hệ thống và quá trình thực tế, trong đó các mối phụ thuộc giữa các biến không hoàn toàn tỷ lệ thuận (tức là được mô tả bằng đường cong, không phải đường thẳng).

Đối tượng và mục đích

Lập trình phi tuyến được sử dụng để tìm các giải pháp tối ưu trong các tình huống khi:

• Sự phụ thuộc của chỉ tiêu mục tiêu (lợi nhuận, chi phí, hiệu quả, v.v.) vào các tham số điều khiển là phi tuyến (ví dụ: lợi tức giảm dần theo quy mô, chi phí bậc hai).
• Các ràng buộc về tài nguyên hoặc quy trình công nghệ được mô tả bằng các quan hệ phi tuyến (ví dụ: phản ứng hóa học, định luật vật lý, các mối quan hệ kinh tế).

Các bài toán NLP xuất hiện trong nhiều lĩnh vực:

• Thiết kế kỹ thuật (tối ưu hóa kết cấu, quy trình).
• Kinh tế và tài chính (tối ưu hóa danh mục đầu tư có tính đến rủi ro, mô hình hóa thị trường).
• Công nghệ hóa học (tối ưu hóa chế độ vận hành lò phản ứng).
• Machine Learning (huấn luyện mạng Neural Network, phương pháp Support Vector Machine).
• Quản lý quy trình sản xuất. Logistics (có tính đến chi phí phi tuyến).

Công thức toán học của bài toán NLP

Bài toán lập trình phi tuyến tổng quát được phát biểu như sau:

Cần tìm tập giá trị của các biến quyết định sao cho cực đại hóa hoặc cực tiểu hóa hàm mục tiêu phi tuyến. Đồng thời, các giá trị của biến phải thỏa mãn hệ ràng buộc, có thể được biểu diễn dưới dạng bất đẳng thức (ví dụ: "đại lượng A phải nhỏ hơn hoặc bằng B"), cũng như dưới dạng đẳng thức (ví dụ: "đại lượng C phải bằng đúng D"). Điều quan trọng là ít nhất một trong các hàm mô tả mục tiêu hoặc ràng buộc là phi tuyến. Thông thường, các điều kiện không âm của biến cũng được bổ sung, tức là yêu cầu giá trị của chúng phải lớn hơn hoặc bằng không.

Tập hợp tất cả các bộ giá trị biến thỏa mãn các ràng buộc tạo thành miền chấp nhận được (feasible region).

Sự khác biệt so với lập trình tuyến tính

Lập trình phi tuyến khác biệt đáng kể so với lập trình tuyến tính (LP):

• Tính phi tuyến: Hàm mục tiêu hoặc các ràng buộc (hoặc cả hai) chứa các phụ thuộc phi tuyến.
• Tính chất của miền chấp nhận được: Miền chấp nhận được trong NLP có thể không lồi (khác với LP, nơi miền chấp nhận được luôn là đa diện lồi).
• Tính chất của điểm tối ưu: Nghiệm tối ưu trong NLP không nhất thiết nằm ở đỉnh của miền chấp nhận được, mà có thể nằm trên biên hoặc bên trong miền. Trong NLP có thể tồn tại các cực trị địa phương không phải là cực trị toàn cục.
• Độ phức tạp của việc giải: Các bài toán NLP, nói chung, phức tạp hơn đáng kể so với các bài toán LP. Không tồn tại một thuật toán đa năng duy nhất tương tự phương pháp đơn hình cho tất cả các bài toán NLP.

Những khó khăn và thách thức chính của NLP

Việc giải các bài toán lập trình phi tuyến đi kèm với một số khó khăn:

• Sự hiện diện của các cực trị địa phương: Hầu hết các phương pháp NLP chỉ đảm bảo tìm được cực trị địa phương (nghiệm tốt nhất trong một lân cận nhất định). Việc tìm kiếm cực trị toàn cục (nghiệm tốt nhất trong toàn bộ miền chấp nhận được) là bài toán khó, đặc biệt đối với các bài toán không lồi.
• Tính không lồi: Nếu bài toán không phải là lồi (hàm mục tiêu hoặc miền chấp nhận được không lồi), thì có thể tồn tại nhiều cực trị địa phương, và các phương pháp gradient thông thường có thể bị "kẹt" tại một trong số chúng.
• Độ phức tạp tính toán: Các thuật toán giải NLP thường đòi hỏi tài nguyên tính toán lớn hơn đáng kể so với LP.

Các lớp bài toán NLP quan trọng

Mặc dù có độ phức tạp chung, tồn tại các lớp con quan trọng của bài toán NLP mà các phương pháp giải hiệu quả đã được phát triển:

• Lập trình lồi: Bài toán cực tiểu hóa hàm lồi trên tập lồi của các nghiệm chấp nhận được (hoặc cực đại hóa hàm lõm). Tính chất chủ yếu: bất kỳ cực tiểu địa phương nào cũng đồng thời là cực tiểu toàn cục. Điều này đơn giản hóa đáng kể việc tìm kiếm nghiệm tối ưu.
• Lập trình bậc hai: Hàm mục tiêu là bậc hai, còn tất cả các ràng buộc đều tuyến tính.
• Lập trình tách biến: Hàm mục tiêu và các ràng buộc có thể được biểu diễn dưới dạng tổng các hàm, mỗi hàm chỉ phụ thuộc vào một biến.

Các phương pháp giải bài toán NLP

Các phương pháp giải bài toán lập trình phi tuyến (NLP)

I. Các phương pháp tối ưu hóa không ràng buộc (tối ưu hóa không có ràng buộc):

• Các phương pháp gradient (phương pháp hạ dốc nhanh nhất, phương pháp gradient liên hợp);
• Phương pháp Newton và các phương pháp quasi-Newton (ví dụ: BFGS);
• Các phương pháp sử dụng xấp xỉ Hessian.

II. Các phương pháp tối ưu hóa có ràng buộc (tối ưu hóa với ràng buộc):

• Các phương pháp biến đổi:
  • Phương pháp hàm phạt (penalty methods);
  • Phương pháp hàm rào cản (barrier methods).
• Các phương pháp tìm kiếm hướng trực tiếp:
  • Phương pháp các hướng khả thi.
• Các phương pháp dựa trên điều kiện tối ưu:
  • Các phương pháp Karush-Kuhn-Tucker (điều kiện KKT);
  • Phương pháp nhân tử Lagrange.
• Các phương pháp lặp:
  • Lập trình bậc hai tuần tự (SQP);
  • Các phương pháp điểm nội.

III. Các phương pháp tối ưu hóa toàn cục:

• Các phương pháp heuristic và metaheuristic:
  • Thuật toán di truyền;
  • Mô phỏng luyện kim (simulated annealing);
  • Tìm kiếm cấm (tabu search).
• Các phương pháp tất định:
  • Nhánh và cận (branch and bound);
  • Các thuật toán tối ưu hóa toàn cục cho bài toán có cấu trúc đặc biệt.

Tài liệu tham khảo

• Bazaraa M., Shetty C. Nonlinear Programming. Theory and Algorithms. — M.: Mir, 1982.
• Fiacco A., McCormick G. Nonlinear Programming: Sequential Unconstrained Minimization Techniques. — M.: Mir, 1972.
• Himmelblau D. Applied Nonlinear Programming. — M.: Mir, 1975.
• Nocedal, Jorge; Wright, Stephen J. Numerical Optimization. — Springer, 2006. (2nd ed.)

Xem thêm

• Nghiên cứu vận trù
• Tối ưu hóa
• Lập trình tuyến tính
• Lập trình lồi
• Hàm mục tiêu
• Ràng buộc
• Miền chấp nhận được