Ở nghiệm nằm trên biên, gradient mục tiêu thường không bằng không. Ta không thể đi theo mọi hướng vì một số hướng rời miền khả thi. Điều kiện KKT mô tả cách các gradient ràng buộc cân bằng gradient mục tiêu tại nghiệm.

1. Chuẩn hóa bài toán và dấu nhân tử

Xét bài toán khả vi

$$\begin{array}{rl}& \underset{x}{min}f(x),\\ & f_i(x)\le 0,i=1,\dots ,m,\\ & h_j(x)=0,j=1,\dots ,p.\end{array}$$

Đưa mọi bất đẳng thức về dấu $\le 0$ trước khi lập Lagrangian. Ví dụ, $x_i\ge 0$ được viết thành $-x_i\le 0$. Nếu không thống nhất dấu từ đầu, dấu nhân tử và điều kiện dừng sẽ bị đảo.

Lagrangian bổ sung các ràng buộc vào mục tiêu với trọng số:

$$\begin{array}{rl}L(x,\mu ,\lambda )& =f(x)+{\mu }_1{f}_1(x)+\cdots +{\mu }_m{f}_m(x)+{\lambda }_1{h}_1(x)+\cdots +{\lambda }_p{h}_p(x)\\ & =f(x)+\sum _{i=1}^m{\mu }_i{f}_i(x)+\sum _{j=1}^p{\lambda }_j{h}_j(x).\end{array}$$

Nhân tử bất đẳng thức phải thỏa ${\mu }_i\ge 0$. Nhân tử đẳng thức ${\lambda }_j$ là số thực tự do. Tại một điểm khả thi, mọi số hạng ${\mu }_i{f}_i(x)$ không dương và các số hạng đẳng thức bằng không. Đây cũng là cơ sở của cận dưới đối ngẫu.

2. Ràng buộc chặt và điều kiện không suy biến

Một ràng buộc bất đẳng thức chặt tại $x$ nếu $f_i(x)=0$. Đặt

$$J(x)=\{i\in \{1,\dots ,m\}:f_i(x)=0\}.$$

Điều kiện độc lập tuyến tính của các gradient ràng buộc, gọi tắt là LICQ, yêu cầu họ vector

$$\begin{array}{rl}& \mathrm{\nabla }{h}_1(x),\dots ,\mathrm{\nabla }{h}_p(x),\\ & \{\mathrm{\nabla }{f}_i(x):i\in J(x)\}\end{array}$$

độc lập tuyến tính. Độc lập nghĩa là chỉ tổ hợp tuyến tính với mọi hệ số bằng không mới cho vector không.

LICQ là một điều kiện đủ về độ chính quy để suy ra KKT tại cực tiểu địa phương. Nó không phải điều kiện cần cho bản thân sự tồn tại nghiệm tối ưu. Nếu LICQ không thỏa, nghiệm vẫn có thể tồn tại và đôi khi vẫn thỏa KKT.

3. Bốn nhóm điều kiện KKT

Nếu $x^{\star }$ là cực tiểu địa phương và LICQ thỏa tại đó, tồn tại $\mu ,\lambda$ sao cho bốn nhóm sau cùng đúng.

Điều kiện dừng. Gradient theo biến gốc của Lagrangian bằng không:

$$\begin{array}{rl}0& ={\mathrm{\nabla }}_{x}L(x^{\star },\mu ,\lambda )\\ & =\mathrm{\nabla }f(x^{\star })+\sum _{i=1}^m{\mu }_i\mathrm{\nabla }{f}_i(x^{\star })+\sum _{j=1}^p{\lambda }_j\mathrm{\nabla }{h}_j(x^{\star }).\end{array}$$

Các tổng ở đây là tổng có trọng số của từng gradient, cùng cấu trúc đã khai triển trong Lagrangian. Với hai bất đẳng thức và một đẳng thức, chúng là ${\mu }_1\mathrm{\nabla }{f}_1+{\mu }_2\mathrm{\nabla }{f}_2+{\lambda }_1\mathrm{\nabla }{h}_1$.

Khả thi gốc. Điểm xét phải thỏa mọi $f_i(x^{\star })\le 0$ và $h_j(x^{\star })=0$.

Khả thi đối ngẫu. Mọi ${\mu }_i\ge 0$. Không đặt điều kiện dấu lên ${\lambda }_j$.

Bù trừ. Với từng $i=1,\dots ,m$,

$${\mu }_i{f}_i(x^{\star })=0.$$

Nếu ràng buộc không chặt thì $f_i(x^{\star })<0$, buộc ${\mu }_i=0$. Chiều ngược lại không đúng: Một ràng buộc chặt có thể có nhân tử bằng không. Chính điều này xảy ra tại ngưỡng $r=2$ trong bài KKT theo tham số.

4. Khi nào KKT đủ?

Giả sử mục tiêu $f$ và các $f_i$ lồi, các $h_j$ affine, mọi hàm khả vi trên miền mở lồi chung. Bất kỳ bộ $(x^{\star },\mu ,\lambda )$ thỏa KKT đều chứng nhận $x^{\star }$ là nghiệm tối ưu toàn cục.

Chứng minh: Từ điều kiện dừng đến cận dưới

Với $\mu \ge 0$, Lagrangian là hàm lồi theo $x$: Nó là tổng hàm lồi với các hệ số không âm và các hàm affine. Điều kiện dừng cho biết $x^{\star }$ cực tiểu hóa Lagrangian trên miền chung.

Cho $y$ khả thi bất kỳ. Ta có

$$\begin{array}{rl}f(y)& \ge L(y,\mu ,\lambda )\\ & \ge L(x^{\star },\mu ,\lambda )\\ & =f(x^{\star }).\end{array}$$

Dòng cuối dùng khả thi gốc và bù trừ. Vì $y$ tùy ý, kết luận là toàn cục.

Tính đủ này không cần LICQ. Vai trò của LICQ ở phần trước là giúp suy ra sự tồn tại nhân tử từ một cực tiểu địa phương. Trong bài toán phi lồi, bốn nhóm KKT nói chung chỉ là bộ điều kiện cần dưới giả thiết chính quy, chưa đủ cho tối ưu.

5. Bài tập tự luyện

Bài tập: Nhân tử nào phải bằng không?

Một ứng viên có $f_1(x)<0$, $f_2(x)=0$ và $h_1(x)=0$. Từ bù trừ suy ra được điều gì về ${\mu }_1$, ${\mu }_2$ và ${\lambda }_1$?

Lời giải

Phải có ${\mu }_1=0$. Nhân tử ${\mu }_2$ có thể bằng không hoặc dương, nhưng phải không âm. Nhân tử ${\lambda }_1$ không bị hạn chế dấu. Những giá trị cụ thể còn phải được xác định bằng điều kiện dừng.