Trong bài trước ta đã nói về tối ưu không ràng buộc. Theo đó cho bài toán tối ưu

và gọi  là lời giải của bài toán này. Ta có thể chứng minh rằng  thỏa:

• Điều kiện bậc nhất: đạo hàm tại  bằng 0

• và điều kiện bậc hai: ma trận Hessian tại  

 là positive definite.

Trong bài này, ta xét bài toán tối ưu ràng buộc có dạng sau:

với  . Nghĩa là ta tối ưu hàm f(x) với m ràng buộc đẳng thức (có dấu =) và p ràng buộc bất đẳng thức (có dấu  ). Để bài toán không bị over-constrained (quá ràng buộc?) thì m nên nhỏ hơn n, nhưng p thì có thể lớn hơn n.

1. Các khái niệm

Feasible point: Một điểm  gọi là feasible nếu nó thỏa tất cả các ràng buộc: .

Tại feasible point, các ràng buộc bất đẳng thức được chia làm 2 phần:

Active set: tại feasible point , tập các ràng buộc đẳng thức  và  được gọi là active set tại . Gọi active set tại x là .

Tangent plane: tại một điểm  bất kì, tập các vector y trực giao với  được gọi là tangent plane. Kí  hiệu Tagent plane là T:

Một cách nôm na, tangent plane là siêu phẳng trực giao với gradient của active set.

2. Điều kiện cho bài toán tối ưu với ràng buộc đẳng thức

Cho bài toán:

với   chỉ là các ràng buộc đẳng thức.

Hàm Lagrangian (Lagrangian function) của f(x) là:

Trong đó  gọi là toán tử  Lagrange.

Điều kiện bậc nhất là:

nghĩa là đạo hàm bậc nhất theo x của hàm  Lagrangian bằng 0. Khi đó cả  và  được mang đi kiểm tra điều kiện bậc 2.

Điều kiện bậc 2 là ma trận:

 là positive definite.

trong đó

là đạo hàm bậc 2 của hàm  Lagrangian, và  Z là một cơ sở của tangent plane.

Một cách nôm na, điều kiện bậc 2 là ma trận Hessian của hàm Lagrangian là positive definite trên không gian tangent plane(mặc dù bản thân ma trận Hessian đó có thể là indefinite trong ).

Nhắc lại rằng tangent plane là không gian tạo bởi các vector y trực giao với đạo hàm bậc nhất của active set. Trong trường hợp này active set là toàn bộ các ràng buộc trong . Do  nên , và tangent plane cũng chỉ cón-m vector độc lập tuyến tính (vì m < n). Do đó .

Do tất cả các ràng buộc đẳng thức trong  đều là active set và là không đổi nên tangent plane là cố định, do đó cơ sở Z cũng không đổi. Nghĩa là ta chỉ cần tính Z một lần cho toàn bộ thuật toán tối ưu. Đây là điểm khác biệt của bài toán tối ưu với ràng buộc đẳng thức.

3. Điều kiện cho bài toán tối ưu với ràng buộc đẳng thức và bất đẳng thức

Cho bài toán:

Nhắc lại rằng các ràng buộc có dấu   có thể dễ dàng chuyển thành dạng .

Hàm Lagrangian (Lagrangian function) của f(x) là:

Trong đó .

Điều kiện bậc nhất là:

nghĩa là đạo hàm bậc nhất theo x của hàm  Lagrangian bằng 0, cùng với 2 điều kiện khác cho  và g(x). Khi đó cả  được mang đi kiểm tra điều kiện bậc 2.

Điều kiện bậc 2 là ma trận:

 là positive definite.

trong đó

là đạo hàm bậc 2 của hàm  Lagrangian, và  Z là một cơ sở của tangent plane. Tuy nhiên lưu ý rằng tangent plane trong trường hợp này là

tức là tập các vector y trực giao với đạo hàm bậc nhất của active set. Vấn đề là active set thay đổi theo x (tại các vị trí khác nhau thì các ràng buộc trong active set là khác nhau), do đó cơ sở Z cũng thay đổi tùy theo x.