DUALITY LÀ GÌ

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

Trong nội dung bài viết này, họ giả sử rằng những đạo hàm tồn tại.

Bạn đ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ư liệu tham khảo.

Bạn đọc hoàn toàn có thể xem bạn dạng pdf trên đây.

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

1. Giới thiệu

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

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

Nhắc lại rằng giá chỉ trị lớn nhất và nhỏ nhất (nếu có) của một hàm số (f_0(mathbfx)) khả vi (và tập xác minh là một tập mở) có được tại một trong số đ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). để ý rằng một điểm hài lòng (f_0’(mathbfx)) = 0 thì được gọi là điểm dừng hay stationary point. Điểm rất 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) gồm (0) là 1 điểm dừng cơ mà không phải là điểm cực trị.

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

Trước tiên họ xét bài toán mà buộc ràng chỉ là một trong những phương trình:<egineqnarray mathbfx=& argmin_mathbfx f_0(mathbfx) extsubject to:~& f_1(mathbfx) = 0~~~~~~~~~(1)endeqnarray>

Bài toán này là việc tổng quát, không nhất thiết đề xuất lồi. Tức hàm kim chỉ nam và hàm buộc ràng không nhất thiết đề xuất lồi.

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

Nếu họ đưa được việc này về một vấn đề không buộc ràng thì bạn 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ởi 0 (giả sử rằng câu hỏi 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 tập Lagrange sử dụng hàm số: (mathcalL(mathbfx, lambda) = f_0(mathbfx) + lambda f_1(mathbfx)). để ý rằng, vào hàm số này, chúng ta có thêm một biến hóa nữa là (lambda), đổi mới này được gọi là nhân tử Lagrange (Lagrange multiplier). Hàm số (mathcalL(mathbfx, lambda)) được điện thoại tư vấn là hàm hỗ trợ (auxiliary function), xuất xắc the Lagrangian. Bạn ta đã chứng tỏ được rằng, điểm optimal value của việc ((1)) thoả mãn điều kiện ( abla_mathbfx, lambda mathcalL(mathbfx, lambda) = 0) (tôi xin được bỏ qua minh chứng của phần này). Điều này tương đương với:

<egineqnarray abla_mathbfxf_0(mathbfx) + lambda abla_mathbfx f_1(mathbfx) &=& 0~~~~(2) f_1(mathbfx) & = & 0 ~~~~(3)endeqnarray>

Để ý rằng điều kiện thứ hai đó là ( abla_lambdamathcalL(mathbfx, lambda) = 0), và cũng đó là ràng buộc trong việc ((1)).

Việc giải hệ phương trình ((2) - (3)), trong tương đối nhiều trường hợp, dễ dàng hơn việc trực tiếp đi tìm kiếm optimal value của vấn đề ((1)).

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

Ví dụ

Ví dụ 1: Tìm giá bán trị lớn nhất và nhỏ dại 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ày feasible set (x^2 + y^2 = 2) ko phải là 1 tập lồi (nó chỉ là một trong những đường tròn).

Lời giải:

Lagrangian của bài toán này là: (mathcalL(x, y, lambda) = x + y + lambda(x^2 + y^2 - 2)). Những điểm cực trị của hàm số Lagrange buộc phải thoả mãn điều kiện:

< abla_x, y, lambda mathcalL(x, y, lambda) = 0 Leftrightarrowleft{eginmatrix 1 + 2lambda x &= 0~~~ (4) 1 + 2lambda y &= 0~~~ (5) x^2 + y^2 &= 2 ~~~~(6)endmatrix ight.>

Từ ((4)) cùng ((5)) ta suy ra (x = y = frac-12lambda). Thay vào ((6)) ta sẽ có được (lambda^2 = frac14 Rightarrow lambda = pm frac12). Vậy ta được 2 cặp nghiệm ((x, y) in (1, 1), (-1, -1)\). Bằng phương pháp thay những giá trị này vào hàm mục tiêu, ta tìm được giá trị bé dại nhất và lớn số 1 của hàm số bắt buộc tìm.

Xem thêm: Hệ Điều Hành Đa Nhiệm Là Gì, Sự Khác Biệt Giữa Đa Chương Trình Và Đa Nhiệm

Ví dụ 2: Cross-entropy. Trong bài xích 10 và bài 13, chúng ta đã được nghe biết hàm mất mát sinh hoạt dạng cross entropy. Bọn họ cũng đã hiểu được hàm cross entropy được dùng để làm đo sự như là nhau của nhị phân phối tỷ lệ với quý hiếm của hàm số này càng nhỏ dại thì hai phần trăm càng sát nhau. Họ cũng đang phát biểu rằng giá trị nhỏ dại nhất của hàm cross entropy dành được khi từng cặp tỷ lệ là như thể nhau. Bây giờ, tôi xin tuyên bố lại và chứng tỏ nhận định trên.

Cho một phân bổ xác xuất (mathbfp = ^T) với (p_i in <0, 1>) cùng (sum_i=1^n p_i = 1). Cùng với một phân bổ xác suất ngẫu nhiên (mathbfq = ) với giả sử rằng (q_i eq 0, forall i), hàm số cross entropy được quan niệm là:Hãy tìm (mathbfq) nhằm hàm cross entropy đạt giá trị nhỏ dại nhất.

Trong việc này, ta tất cả ràng buộc là (sum_i=1^n q_i = 1). Lagrangian của việc là: Ta phải giải hệ phương trình:

< abla_q_1, dots, q_n, lambda mathcalL(q_1, dots, q_n, lambda) = 0 Leftrightarrowleft{eginmatrix -fracp_iq_i + lambda &=& 0, ~~ i = 1, dots, n ~~~(7) q_1 + q_2 + dots + q_n &=& 1 ~~~~~~ (8)endmatrix ight.>

Từ ((7)) ta tất 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õ rằng vì sao hàm số cross entropy được dùng để ép hai phần trăm gần nhau.

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

3.1. Lagrangian

Với vấn đề tối ưu tổng quát:<egineqnarraymathbfx^* &=& argmin_mathbfx f_0(mathbfx) \textsubject to:~ && f_i(mathbfx) leq 0, ~~ i = 1, 2, dots, m ~~~(9)&& h_j(mathbfx) = 0, ~~ j = 1, 2, dots, pendeqnarray>với miền xác đinh (mathcalD = (cap_i=0^m extdomf_i) cap (cap_j=1^p extdomh_j)). Chú ý rằng, họ đang không trả sử về đặc điểm lồi của hàm về tối ưu hay các hàm ràng buộc ngơi nghỉ đây. đưa sử tốt nhất ở đấy là (mathcalD eq emptyset) (tập rỗng).

Lagrangian cũng được xây dựng tương tự với từng 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 chưa hẳn là chữ v nhưng mà là chữ nu trong giờ Hy Lạp, phát âm như từ new) là các vectors cùng được hotline là dual variables (biến đối ngẫu) hoặc Lagrange multiplier vectors (vector nhân tử Lagrange). Từ bây giờ nếu biến thiết yếu (mathbfx in mathbbR^n) thì tổng số đổi thay của hàm số này đang là (n + m + p).

(Thông thường, tôi dùng các chữ chiếc viết thường xuyên in đậm để trình diễn một vector, vào trường vừa lòng này tôi ko bôi đậm được (lambda) cùng ( u) do tiêu giảm của LaTeX lúc viết cùng markdown. Tôi lưu ý điều này để tránh nhầm lẫn cho bạn đọc)

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

Hàm đối ngẫu Lagrange của việc tối ưu (hoặc gọn là hàm số đối ngẫu) ((9)) là 1 trong hàm của các biến đối ngẫu, được khái niệm là giá chỉ trị bé dại nhất theo (mathbfx) của Lagrangian:<egineqnarrayg(lambda, u) &=& inf_mathbfx in mathcalD mathcalL(mathbfx, lambda, u)&=& inf_mathbfx in mathcalDleft( f_0(mathbfx) + sum_i=1^m lambda_if_i(mathbfx) + sum_j=1^p u_j h_j(mathbfx) ight)endeqnarray>

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

Đặc biệt quan trọng:

(inf) được lấy trên miền (x in mathcalD), tức miền xác định của câu hỏi (là giao của miền khẳng định của phần lớn hàm trong bài xích toán). Miền xác minh này không giống với feasible set. Thông thường, feasible set là tập bé của miền xác định (mathcalD).

3.3. Ngăn dưới của giá trị về tối ưu

Nếu (p^*) là optimal value (giá trị buổi tối ưu) của việc ((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 hoàn toàn có thể được chứng tỏ dễ dàng. Mang sử (mathbfx_0) là một trong những điểm feasible ngẫu nhiên của việc ((9)), tức thoả mãn các điều khiếu nại ràng buộc (f_i(mathbfx_0) leq 0, forall i = 1, dots, m; h_j(mathbfx_0) = 0, forall j = 1, dots, p), ta đang có: Vì điều này đúng với mọi (mathbfx_0) feasible, ta sẽ có tính chất đặc trưng sau đây:

Khi (mathbfx_0 = mathbfx^*), ta bao gồm bất đẳng thức ((10)).

3.4. Ví dụ

Ví dụ 1

Xét việc tối ưu sau:<egineqnarray x=& argmin_x x^2 + 10sin(x) + 10 extsubject to:~& (x-2)^2 leq 4 endeqnarray>

Chú ý: Với câu hỏi này, miền xác minh (mathcalD = mathbbR) tuy thế feasible set là (0 leq x leq 4).

Với hàm mục tiêu là mặt đường đậm greed color lam trong Hình 1 bên dưới đây. Ràng buộc thực tế (0 leq x leq 4), nhưng tôi viết sinh hoạt dạng này để vấn đề thêm phần thú vị. Hàm số buộc ràng (f_1(x) = (x-2)^2 - 4) được cho vì đường nét đứt màu xanh lá cây lục. Optimal value của bài toán này có thể được thừa nhận ra là vấn đề trên đồ dùng thị gồm hoành độ bởi 0. Chăm chú rằng hàm kim chỉ nam ở đây không phải là hàm lồi nên việc tối ưu này cũng chưa 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: Cách Chơi Game Kỳ Lưng Cá Sấu Mới Nhất Miễn Phí, Tải Game Kỳ Lưng Cá Sấu

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