Bài 18: Duality Là Gì ? Nghĩa Của Từ Duality Principle Trong Tiếng Việt

2. Phương pháp nhân tử Lagrange 3. Hàm đối ngẫu Lagrange (The Lagrange dual function) 3.4. Ví dụ 4. Bài toán đối ngẫu Lagrange (The Lagrange dual problem) 5. Optimality conditions 5.2. KKT optimality conditions

Trong bài viết này, chúng ta giả sử rằng các đạo hàm tồn tại.

Đang xem: Duality là gì

Bài viết này chủ yếu được dịch lại từ Chương 5 của cuốn Convex Optimization trong tài liệu tham khảo.

Bạn đọc có thể xem bản pdf tại đây.

Nếu bạn gặp khó khăn trong việc hiểu đạo hàm trong bài viết này, bạn được khuyến khích đọc Đạo hàm của hàm nhiều biến. Ngoài ra, các kiến thức trong Bài 16 và Bài 17 là quan trọng để hiểu rõ hơn bài viết này.

1. Giới thiệu

Trong Bài 16, chúng ta đã làm quen với các khái niệm về tập hợp lồi và hàm số lồi. Tiếp theo đó, trong Bài 17, tôi cũng đã trình bày về các bài toán tối ưu lồi, cách nhận dạng và cách sử dụng thư viện để giải các bài toán lồi cơ bản. Trong bài này, chúng ta sẽ tiếp tục tiếp cận một cách sâu hơn: các điều kiện về nghiệm của các bài toán tối ưu, cả lồi và không lồi; bài toán đối ngẫu (dual problem) và điều kiện KKT.

Trước tiên, chúng ta lại bắt đầu bằng những kỹ thuật đơn giản cho các bài toán cơ bản. Kỹ thuật này có lẽ các bạn đã từng nghe đến: Phương pháp nhân tử Lagrange (method of Lagrange multipliers). Đây là một phương pháp giúp tìm các điểm cực trị của hàm mục tiêu trên feasible set của bài toán.

Nhắc lại rằng giá trị lớn nhất và nhỏ nhất (nếu có) của một hàm số (f_0(mathbf{x})) khả vi (và tập xác định là một tập mở) đạt được tại một trong các điểm cực trị của nó. Và điều kiện cần để một điểm là điểm cực trị là đạo hàm của hàm số tại điểm này (f_0’(x) = 0). Chú ý rằng một điểm thoả mãn (f_0’(mathbf{x})) = 0 thì được gọi là điểm dừng hay stationary point. Điểm cực trị là một điểm dừng nhưng không phải điểm dừng nào cũng là điểm cực trị. Ví dụ hàm (f(x) = x^3) có (0) là một điểm dừng nhưng không phải là điểm cực trị.

Với hàm nhiều biến, ta cũng có thể áp dụng quan sát này. Tức chúng ta cần đi tìm nghiệm của phương trình đạo hàm theo mỗi biến bằng 0. Tuy nhiên, đó là với các bài toán không ràng buộc (unconstrained optimization problems), với các bài toán có ràng buộc như chúng ta đã gặp trong Bài 17 thì sao?

Trước tiên chúng ta xét bài toán mà ràng buộc chỉ là một phương trình:<egin{eqnarray} mathbf{x}=& argmin_{mathbf{x}} f_0(mathbf{x}) ext{subject to:}~& f_1(mathbf{x}) = 0~~~~~~~~~(1)end{eqnarray}>

Bài toán này là bài toán tổng quát, không nhất thiết phải lồi. Tức hàm mục tiêu và hàm ràng buộc không nhất thiết phải lồi.

2. Phương pháp nhân tử Lagrange

Nếu chúng ta đưa được bài toán này về một bài toán không ràng buộc thì chúng ta có thể tìm được nghiệm bằng cách giải hệ phương trình đạo hàm theo từng thành phần bằng 0 (giả sử rằng việc giải hệ phương trình này là khả thi).

Điều này là động lực để nhà toán học Lagrange sử dụng hàm số: (mathcal{L}(mathbf{x}, lambda) = f_0(mathbf{x}) + lambda f_1(mathbf{x})). Chú ý rằng, trong hàm số này, chúng ta có thêm một biến nữa là (lambda), biến này được gọi là nhân tử Lagrange (Lagrange multiplier). Hàm số (mathcal{L}(mathbf{x}, lambda)) được gọi là hàm hỗ trợ (auxiliary function), hay the Lagrangian. Người ta đã chứng minh được rằng, điểm optimal value của bài toán ((1)) thoả mãn điều kiện (
abla_{mathbf{x}, lambda} mathcal{L}(mathbf{x}, lambda) = 0) (tôi xin được bỏ qua chứng minh của phần này). Điều này tương đương với:

<egin{eqnarray} abla_{mathbf{x}}f_0(mathbf{x}) + lambda abla_{mathbf{x}} f_1(mathbf{x}) &=& 0~~~~(2) f_1(mathbf{x}) & = & 0 ~~~~(3)end{eqnarray}>

Để ý rằng điều kiện thứ hai chính là (
abla_{lambda}mathcal{L}(mathbf{x}, lambda) = 0), và cũng chính là ràng buộc trong bài toán ((1)).

Việc giải hệ phương trình ((2) – (3)), trong nhiều trường hợp, đơn giản hơn việc trực tiếp đi tìm optimal value của bài toán ((1)).

Xét các ví dụ đơn giản sau đây.

Ví dụ

Ví dụ 1: Tìm giá trị lớn nhất và nhỏ nhất của hàm số (f_0(x, y) = x + y) thoả mãn điều kiện (f_1(x, y) = x^2 + y^2 = 2). Ta nhận thấy rằng đây không phải là một bài toán tối ưu lồi vì feasible set (x^2 + y^2 = 2) không phải là một tập lồi (nó chỉ là một đường tròn).

Lời giải:

Lagrangian của bài toán này là: (mathcal{L}(x, y, lambda) = x + y + lambda(x^2 + y^2 – 2)). Các điểm cực trị của hàm số Lagrange phải thoả mãn điều kiện:

< abla_{x, y, lambda} mathcal{L}(x, y, lambda) = 0 Leftrightarrowleft{egin{matrix} 1 + 2lambda x &= 0~~~ (4) 1 + 2lambda y &= 0~~~ (5) x^2 + y^2 &= 2 ~~~~(6)end{matrix} ight.>

Từ ((4)) và ((5)) ta suy ra (x = y = frac{-1}{2lambda}). Thay vào ((6)) ta sẽ có (lambda^2 = frac{1}{4} Rightarrow lambda = pm frac{1}{2}). Vậy ta được 2 cặp nghiệm ((x, y) in {(1, 1), (-1, -1)}). Bằng cách thay các giá trị này vào hàm mục tiêu, ta tìm được giá trị nhỏ nhất và lớn nhất của hàm số cần tìm.

Xem thêm: Md Là File .Md Là Gì ? Hướng Dẫn Sử Dụng Markdown

Ví dụ 2: Cross-entropy. Trong Bài 10 và Bài 13, chúng ta đã được biết đến hàm mất mát ở dạng cross entropy. Chúng ta cũng đã biết rằng hàm cross entropy được dùng để đo sự giống nhau của hai phân phối xác suất với giá trị của hàm số này càng nhỏ thì hai xác suất càng gần nhau. Chúng ta cũng đã phát biểu rằng giá trị nhỏ nhất của hàm cross entropy đạt được khi từng cặp xác suất là giống nhau. Bây giờ, tôi xin phát biểu lại và chứng minh nhận định trên.

Cho một phân bố xác xuất (mathbf{p} = ^T) với (p_i in <0, 1>) và (sum_{i=1}^n p_i = 1). Với một phân bố xác suất bất kỳ (mathbf{q} = ) và giả sử rằng (q_i
eq 0, forall i), hàm số cross entropy được định nghĩa là:Hãy tìm (mathbf{q}) để hàm cross entropy đạt giá trị nhỏ nhất.

Trong bài toán này, ta có ràng buộc là (sum_{i=1}^n q_i = 1). Lagrangian của bài toán là: Ta cần giải hệ phương trình:

< abla_{q_1, dots, q_n, lambda} mathcal{L}(q_1, dots, q_n, lambda) = 0 Leftrightarrowleft{egin{matrix} -frac{p_i}{q_i} + lambda &=& 0, ~~ i = 1, dots, n ~~~(7) q_1 + q_2 + dots + q_n &=& 1 ~~~~~~ (8)end{matrix} ight.>

Từ ((7)) ta có (p_i = lambda q_i). Vậy nên: ( 1 = sum_{i=1}^n p_i = lambdasum_{i=1}^n q_i = lambda Rightarrow lambda = 1 Rightarrow q_i = p_i, forall i).

Qua đây, chúng ta đã hiểu rằng vì sao hàm số cross entropy được dùng để ép hai xác suất gần nhau.

3. Hàm đối ngẫu Lagrange (The Lagrange dual function)

3.1. Lagrangian

Với bài toán tối ưu tổng quát:<egin{eqnarray}mathbf{x}^* &=& argmin_{mathbf{x}} f_0(mathbf{x}) \text{subject to:}~ && f_i(mathbf{x}) leq 0, ~~ i = 1, 2, dots, m ~~~(9)&& h_j(mathbf{x}) = 0, ~~ j = 1, 2, dots, pend{eqnarray}>với miền xác đinh (mathcal{D} = (cap_{i=0}^m ext{dom}f_i) cap (cap_{j=1}^p ext{dom}h_j)). Chú ý rằng, chúng ta đang không giả sử về tính chất lồi của hàm tối ưu hay các hàm ràng buộc ở đây. Giả sử duy nhất ở đây là (mathcal{D}
eq emptyset) (tập rỗng).

Lagrangian cũng được xây dựng tương tự với mỗi nhân tử Lagrange cho một (bất) phương trình ràng buộc:

với (lambda = ;
u = < u_1, u_2, dots, u_p>) (ký hiệu (
u) này không phải là chữ v mà là chữ nu trong tiếng Hy Lạp, đọc như từ new
) là các vectors và được gọi là dual variables (biến đối ngẫu) hoặc Lagrange multiplier vectors (vector nhân tử Lagrange). Lúc này nếu biến chính (mathbf{x} in mathbb{R}^n) thì tổng số biến của hàm số này sẽ là (n + m + p).

(Thông thường, tôi dùng các chữ cái viết thường in đậm để biểu diễn một vector, trong trường hợp này tôi không bôi đậm được (lambda) và (
u) do hạn chế của LaTeX khi viết cùng markdown. Tôi lưu ý điều này để hạn chế nhầm lẫn cho bạn đọc
)

3.2. Hàm đối ngẫu Lagrange

Hàm đối ngẫu Lagrange của bài toán tối ưu (hoặc gọn là hàm số đối ngẫu) ((9)) là một hàm của các biến đối ngẫu, được định nghĩa là giá trị nhỏ nhất theo (mathbf{x}) của Lagrangian:<egin{eqnarray}g(lambda, u) &=& inf_{mathbf{x} in mathcal{D}} mathcal{L}(mathbf{x}, lambda, u)&=& inf_{mathbf{x} in mathcal{D}}left( f_0(mathbf{x}) + sum_{i=1}^m lambda_if_i(mathbf{x}) + sum_{j=1}^p u_j h_j(mathbf{x}) ight)end{eqnarray}>

Nếu Lagrangian không bị chặn dưới, hàm đối ngẫu tại (lambda,
u) sẽ lấy giá trị (-infty).

Đặc biệt quan trọng:

(inf) được lấy trên miền (x in mathcal{D}), tức miền xác định của bài toán (là giao của miền xác định của mọi hàm trong bài toán). Miền xác định này khác với feasible set. Thông thường, feasible set là tập con của miền xác định (mathcal{D}).

3.3. Chặn dưới của giá trị tối ưu

Nếu (p^*) là optimal value (giá trị tối ưu) của bài toán ((9)), thì với các biến đối ngẫu (lambda_i geq 0, forall i) và (
u) bất kỳ, chúng ta sẽ có: Tính chất này có thể được chứng minh dễ dàng. Giả sử (mathbf{x}_0) là một điểm feasible bất kỳ của bài toán ((9)), tức thoả mãn các điều kiện ràng buộc (f_i(mathbf{x}_0) leq 0, forall i = 1, dots, m; h_j(mathbf{x}_0) = 0, forall j = 1, dots, p), ta sẽ có: Vì điều này đúng với mọi (mathbf{x}_0) feasible, ta sẽ có tính chất quan trọng sau đây:

Khi (mathbf{x}_0 = mathbf{x}^*), ta có bất đẳng thức ((10)).

3.4. Ví dụ

Ví dụ 1

Xét bài toán tối ưu sau:<egin{eqnarray} x=& argmin_{x} x^2 + 10sin(x) + 10 ext{subject to:}~& (x-2)^2 leq 4 end{eqnarray}>

Chú ý: Với bài toán này, miền xác định (mathcal{D} = mathbb{R}) nhưng feasible set là (0 leq x leq 4).

Với hàm mục tiêu là đường đậm màu xanh lam trong Hình 1 dưới đây. Ràng buộc thực ra (0 leq x leq 4), nhưng tôi viết ở dạng này để bài toán thêm phần thú vị. Hàm số ràng buộc (f_1(x) = (x-2)^2 – 4) được cho bởi đường nét đứt màu xanh lục. Optimal value của bài toán này có thể được nhận ra là điểm trên đồ thị có hoành độ bằng 0. Chú ý rằng hàm mục tiêu ở đây không phải là hàm lồi nên bài toán tối ưu này cũng không phải là lồi, mặc dù hàm bất phương trình ràng buộc (f_1(x)) là lồi.

Xem thêm: Data Driven Là Gì – Tầm Quan Trọng Trong Hoạt Động Kinh Doanh

Lagrangian của bài toàn này có dạng:Các đường dấu chấm màu đỏ trong Hình 1 là các đường ứng với các (lambda ) khác nhau. Vùng bị chặn giữa hai đường thẳng đứng màu đen thể hiện miền feasible của bài toán tối ưu.

Related Posts