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.^[1]

Ví dụ

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

\min f(\mathbf {x} )=x_{1}^{2}+x_{2}^{4}

tùy thuộc vào

x_{1}\geq 1

và

x_{2}=1,

trong đó $\mathbf {x}$ biểu thị vector (x₁, x₂).

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 $f(\mathbf {x} )$ sẽ đạt giá trị nhỏ nhất khi $\mathbf {x} =(0,0)$ . 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à $\mathbf {x} =(1,1)$ , khi đó $f(\mathbf {x} )$ đạt giá trị nhỏ nhất với $\mathbf {x}$ 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

Beveridge, Gordon S. G.; Schechter, Robert S. (1970). “Essential Features in Optimization”. Optimization: Theory and Practice. New York: McGraw-Hill. tr. 5–8. ISBN 0-07-005128-3.