Ràng buộc (toán học)

Trong toán học, ràng buộc là một điều kiện của một vấn đề tối ưu hóa mà giải pháp phải đáp ứng. Có một số loại hạn chế — chủ yếu là ràng buộc bình đẳng, ràng buộc bất bình đẳng, và ràng buộc số nguyên. Tập hợp các giải pháp ứng viên thỏa mãn tất cả các ràng buộc được gọi là tập hợp khả thi.

Ví dụ 
Sau đây là một vấn đề tối ưu hóa đơn giản:

 

tùy thuộc vào

 

và

 

trong đó  biểu thị vector (x1, x2).

Trong ví dụ này, dòng đầu tiên định nghĩa một hàm cần được tối ưu hóa (được gọi là hàm mục tiêu (objective function) hay hàm mất mát (loss function)). Hai dòng tiếp theo định nghĩa hai ràng buộc, lần lượt là ràng buộc bất đẳng thức và ràng buộc đẳng thức. Những ràng buộc này còn được gọi là ràng buộc cứng, nghĩa là chúng bắt buộc phải được thỏa mãn; chúng định nghĩa một tập xác định các giá trị khả thi là giải pháp cho vấn đề.

Khi không có ràng buộc, hàm  sẽ đạt giá trị nhỏ nhất khi . Nhưng đáp số này không thỏa mãn các ràng buộc trên. Đáp số cho vấn đề tối ưu hóa có ràng buộc là , khi đó  đạt giá trị nhỏ nhất với  thỏa mãn cả hai ràng buộc.

Thuật ngữ 

 Tập khả thi là tập hợp các nghiệm của một vấn đề tối ưu hóa sao cho tất cả các ràng buộc được thỏa mãn.
 Điểm tối ưu là nghiệm tối ưu của một vấn đề tối ưu hóa sao cho tất cả các ràng buộc được thỏa mãn.
 Nếu điểm tối ưu khiến cho dấu "=" trong một ràng buộc bất đẳng thức xảy ra, ràng buộc đó được gọi là ràng buộc trói buộc (hiển nhiên, tất cả các ràng buộc đẳng thức đều là ràng buộc trói buộc)
 Nếu điểm tối ưu không khiến cho dấu "=" trong một ràng buộc bất đẳng thức xảy ra, ràng buộc đó được gọi là ràng buộc không trói buộc. Trong một số trường hợp, ví dụ như các vấn đề về tối ưu hóa lồi (convex optimization), nếu một ràng buộc là ràng buộc không trói buộc thì cho dù có ràng buộc đó hay không, điểm tối ưu vẫn không thay đổi.
 Nếu có một điểm không thỏa mãn một ràng buộc nào đó, điểm đó được gọi là điểm bất khả.

Xem thêm 

 Constraint algebra
 Constraint satisfaction problem
 Karush–Kuhn–Tucker conditions
 Lagrange multipliers
 Level set
 Linear programming
 Nonlinear programming
 Restriction

Tham khảo

Đọc thêm

Liên kết ngoài 

 Câu hỏi thường gặp về lập trình phi tuyến  
 Thuật ngữ lập trình toán học

Tối ưu hóa (toán học)
Lập trình ràng buộc