Đối ngẫu là gì

Lý thuyết đối ngẫu là một trong chủ đề đặc biệt trong nghành nghề tối ưu. đôi khi ta giải câu hỏi đối ngẫu thay vì câu hỏi gốc. Xem xét việc đối ngẫu để xem được một số ý nghĩa đằng sau những ràng buộc, các biến.

Bạn đang xem: đối ngẫu là gì

Trong phần đầu tiên, linear program, tôi đã ra mắt bài toán đối ngẫu của một bái toán quy hoạch tuyến tính để bạn đọc có một cái nhìn qua quýt về lý thuyết đối ngẫu. Với câu hỏi LP tổng quát: <eginalignedmathrmmin.~ & c^Tx = c_1 x_1 + ldots + c_2 x_2 \mathrms.t.~ & a_j1x_1+ ldots + a_jnx_n geq b_j, j=1,ldots, m\& x_1, ldots, x_n geq 0.endaligned> vấn đề đối ngẫu tất cả dạng: <eginalignedmathrmmax.~ và b^T lambda = b_1 lambda_1 + ldots + b_m lambda_m \mathrms.t.~ và a_1jlambda_1+ ldots + a_njlambda_n leq c_j, j=1,ldots, m\& lambda_1, ldots, lambda_m geq 0.endaligned> con số biến của việc đối ngẫu bằng số lượng ràng buộc của vấn đề gốc và con số ràng buộc của câu hỏi đối ngẫu bằng với số lượng biến của câu hỏi gốc. Một tính chất quan trọng là nghiệm của việc LP đối ngẫu cũng trùng cùng với nghiệm của vấn đề LP gốc. Vị đó, thay vì giải vấn đề gốc, ta hoàn toàn có thể giải việc đối ngẫu.

Sau đây tôi đã đề cập về lý thuyết đối ngẫu cho một việc tối ưu dạng tổng quát. Những nội dung bao gồm hàm Lagrange, câu hỏi đối ngẫu, đk Karush-Kuhn-Tucker, và một số trong những phân tích liên quan đến đối ngẫu.

Hàm Lagrange

Xét việc tối ưu tổng quát: <eginalignedmathrmPrimal: ~min. Và f_0(x)\mathrms.t. Và f_i(x) leq 0, i = 1, ldots, m \& h_i(x) = 0, i = 1, ldots, p.labeloptProbendaligned> trong số đó (x in mathbbR^n), miền xác minh (mathcalD = cap_i=0^m mathbfdom f_i cap cap_i=1^p mathbfdom h_i) không giống rỗng. Gọi (p^*) là nghiệm của bài toán.

Hàm Lagrange (L: mathbbR^n imes mathbbR^m imes mathbbR^r), hay có cách gọi khác là Lagrangian, được quan niệm như sau: <eginalignedL(x, lambda, u) = f_0(x) + sum_i = 1^m lambda_i f_i(x) + sum_i = 1^p u_j h_j(x)endaligned> các biến (lambda in mathbbR^m, lambda geq 0) và ( u in mathbbR^p) được call là các toán tử Lagrange (Lagrange multiplier), hay biến đối ngẫu (dual variable). (lambda_i, i=1,…,m) khớp ứng với ràng buộc (f_i (x) leq 0) cùng ( u_j, j=1,…,r) tương ứng với ràng buộc (h_j(x) = 0).

Lagrangian là hàm kết hợp tuyến tính giữa kim chỉ nam và các ràng buộc. Nếu ta nhìn bài toán tối ưu là tìm (x) làm thế nào để cho công ty quản lý và vận hành với cực tiểu chi phí với các ràng buộc về nguồn lực (f_i) cùng (h_i). Như vậy hàm Lagrange có thể xem như hàm chi phí thêm vào đó với các chi phí phát sinh khi những nguồn lực bị quá quá. (lambda_i) có thể được xem như là giá (price) mang đến một đơn vị chức năng của nguồn lực (f_i) vượt vượt ngưỡng.

Ta luôn có Lagrangian là 1 trong những chặn bên dưới của hàm (f_0(x)) với tất cả (x) thuộc tập khả thi và (lambda geq 0). <eginalignedL(x, lambda, u) = f_0(x) + sum_i = 1^m lambda_i f_i(x) + sum_i = 1^p u_j h_j(x) leq f_0(x). qquad qquad (1)labeleq:lagrangian_lowerboundendaligned>

Hàm đối ngẫu

Định nghĩa hàm đối ngẫu (dual function) (g: mathbbR^m imes mathbbR^p ightarrow mathbbR) là cực tiểu của Lagrangian theo biến hóa (x) <eginalignedg(lambda, u) = min_x in mathcalD L(x, lambda, u) = min_x in mathcalD Big( f_0(x) + sum_i = 1^m lambda_i f_i(x) + sum_i = 1^p u_i h_i(x) Big)endaligned>

Từ đặc thù (1), ta tất cả hàm đối ngẫu là một trong chặn dưới của nghiệm (p^*) của việc tối ưu Primal: <eginalignedg(lambda, u) leq p^*, forall lambda geq 0, u.endaligned>

Sau đó là một vài lấy một ví dụ tính hàm đối ngẫu:

Ví dụ 1:

Xét bài toán:<eginalignedmathrmmin.~ & x^T x labelprob:quadratic\mathrms.t.~ và Ax = Bendaligned> trong các số ấy (A in mathbbR^p imes n).

Hàm Lagrange có dạng <eginalignedL(x, u) = x^T x + u^T(Ax – b).endaligned>

Hàm đối ngẫu được cho vì chưng công thức: <eginalignedg(v) = min_x L(x, v)endaligned> rất tiểu đạt tại ( abla_x L(x, u) = 2x + A^T u = 0). Giải phương trình ta được nghiệm (x = -(1/2) A^T u). Cố gắng (x) vào hàm Lagrange, ta được hàm đối ngẫu của câu hỏi Ví dụ 1 là: <eginalignedg( u) = -(1/4) u^T A A^T u – b^T uendaligned> Hàm đối ngẫu (g( u)) là 1 trong những hàm lõm do ma trận (AA^T) xác minh dương. đặc thù chặn dưới của hàm (f_0) có nghĩa rằng (g( u) leq min Ax = B\).

Ví dụ 2:

Xét việc quy hoạch đường tính <eginalignedmathrmmin~ & c^T x labelprob:lp\mathrms.t.~ và Ax = B \& x geq 0,endaligned> trong đó (x in mathbbR^n).

Trong việc trên, ràng buộc bất đẳng thức đó là (f_i(x) = – x_i leq 0, i = 1, ldots, n).

Lagrangian có dạng: <eginalignedL(x, lambda, u) = c^T x – sum_i = 1^n lambda_i x_i + u^T (Ax – b) = -b^T u + (c + A^T u – lambda)^T x.endaligned>

Hàm đối ngẫu của việc trên bao gồm dạng: <eginalignedg(lambda, u) &= min_x L(x, lambda, u) = -b^T u + min_x(c + A^T u – lambda)^T x \&= egincases -b^T u, ~ extrmnếu ~ c + A^T u – lambda = 0 \ -infty , ~ extrmnếu khôngendcasesendaligned> Để hàm (g(lambda, u)) là 1 chặn dưới có số lượng giới hạn của (f_0) ta buộc phải (lambda geq 0) cùng (c + A^T u – lambda = 0).

Liên phù hợp (đọc thêm)

Hàm đối ngẫu và phối hợp (conjugate) của hàm (f_0) gồm mối liên quan với nhau. Ta có thể tính hàm đối ngẫu từ liên hợp của (f_0). Một vài sách về về tối ưu hóa như sách Convex Optimization thường thường dùng liên hòa hợp của hàm để viết hàm đối ngẫu hay vấn đề đối ngẫu. Phần này được reviews giúp bạn đọc không cảm thấy ngạc nhiên khi đọc các tài liệu khác.

Cho hàm (f: mathbbR^n ightarrow mathbbR). Liên hợp (conjugate) của hàm (f), cam kết hiệu (f^*: mathbbR^n ightarrow mathbbR), được định nghĩa là hàm <eginalignedf^*(y) = max_x in mathbfdom f (y^Tx – f(x)).endaligned>

Ta tất cả (f^*) luôn là một hàm lồi bởi vì nó bao gồm dạng là cực lớn của những hàm affine theo (y).

Xem thêm: Nhóm Máu A Là Gì ? Đặc Điểm Và Cách Nhận Biết Nhóm Máu A Nhóm Máu Hiếm Và Những Điều Bạn Cần Biết

Một số ví dụ như về liên hợp:

(f(x) = ax + b): hàm (max_x in mathbfdom f (yx – ax – b)) có số lượng giới hạn khi và chỉ khi (y = a). Bởi đó, miền khẳng định của hàm liên hợp chỉ là 1 trong điểm (a\), cùng (f^*(a) = -b).(f(x) = -log x, x in mathbbR): hàm (max_x (xy + log x)) đạt cực đại tại (x = -1/y) (với (y ). Vày vậy <eginalignedf^*(y) = -log(-y) – 1, y(f(x) = x log x): (f^*(x) = max_x (xy – x log x)) đạt cực lớn tại (x = e^y-1). Do vậy, <eginalignedf^*(y) = e^y-1.endaligned>

Cho câu hỏi tối ưu <eginalignedmathrmmin~ và f_0(x) \mathrms.t.~ và Ax leq b \& Cx = d.endaligned> Hàm đối ngẫu cùng hàm phối hợp có liên quan với nhau như sau: <eginalignedg(lambda, u) &= min_x(f_0(x) + lambda^T(Ax – b) + u ^T(Cx – d)) \& = -b^T lambda – d^T u + min_x(f_0(x) + (A^T lambda + C^T u)^T x) \& = -b^T lambda – d^T u – f^*_0(- A^T lambda – C^T u).endaligned>

Ví dụ 3:

Ví dụ ta có thể tính hàm đối ngẫu trực tiếp từ phối hợp trong việc tìm rất tiểu hàm negative entropy: <eginalignedmathrmmin~ và f_0(x) = sum_i = 1^n x_i log x_i \mathrms.t.~ và Ax leq b \& 1^T x = 1,endaligned> trong đó (A) là ma trận (r imes n) Ta gồm <eginalignedg(lambda, u) = -b^Tlambda – u – f^*_0(A^T lambda – u)).endaligned> Ta gồm theo lấy ví dụ như phía trên, liên hợp của (f(x) = xlog x) là (f^*(y) = e^y-1), (y in mathbbR). Vày đó, (f_0^*(y) = sum_i=1^n e^y_i – 1). Do vậy, <eginalignedg(lambda, u) &= -b^Tlambda – u – sum_i = 1^r e^-a_:,i^T lambda – u – 1 = -b^Tlambda – u e^- u – 1sum_i = 1^r e^-a_:,i^T lambda,endaligned> trong các số đó (a_:,i) là cột trang bị (i) của ma trận (A).

Bài toán đối ngẫu

Như vẫn đề cập ở trên, hàm đối ngẫu là 1 chặn dưới của (p^*). Do vậy bài toán đối ngẫu sau <eginalignedmathrmDual: ~max. ~& g(lambda, u) \mathrms.t.~ & lambda geq 0.endaligned> sẽ mang đến một chặn dưới về tối ưu của việc Primal.

Điểm cực trị của vấn đề đối ngẫu ((lambda^*, u^*)) được hotline là điểm đối ngẫu tối ưu (dual optimal), giỏi toán tử Lagrange tối ưu.

Ví dụ 4:

Xét việc tối ưu: <eginalignedmathrmmin~ & x_1^2 + x_2^2 – 2x_1 labeleq:ex1_lp\mathrms.t.~ & 2x_1 + x_2 geq 5 onumber\& x_2 leq 7. onumberendaligned> Lagrangian được cho vị công thức: <eginalignedL(x_1, x_2, lambda_1, lambda_2) = & x_1^2 + x_2^2 – 2 x_1 \& + (-2x_1 – x_2 + 5)lambda_1 \& + (x_2 – 7) lambda_2.endaligned>

Hàm đối ngẫu <eginalignedg(lambda_1, lambda_2) = và min_x_1, x_2 L(x_1, x_2, lambda_1, lambda_2) \= & min_x_1 x_1^2 – 2(1 + lambda_1) x_1 \& + min_x_2 x_2^2 + (- lambda_1 + lambda_2) x_2\& + 5lambda_1 – 7 lambda_2. endaligned>

Cực tiểu của (L) theo (x_1, x_2) đạt tại: <eginalignedx_1 &= 1 + lambda_1\x_2 &= frac12 (lambda_1 – lambda_2).endaligned> cho nên vì thế hàm đối ngẫu tất cả dạng sau: <eginalignedg(lambda_1, lambda_2) &= – (1 + lambda_1)^2 – frac14 (lambda_1 – lambda_2)^2 + 5lambda_1 – 7 lambda_2.endaligned>

Ví dụ 5:

Xét vấn đề LP dạng bao quát <eginalignedmathrmmin~ và c^T x labeleq:ex2_lp\mathrms.t.~ & Ax = B \& x geq 0.endaligned>

Hàm đối ngẫu được đến bởi: <eginalignedg(lambda, u) &= min_x L(x, lambda, u) = -b^T u + min_x(c + A^T u – lambda)^T x \& = egincases -b^T u ~ extrmnếu ~ c + A^T u – lambda = 0 \ -infty , extrmnếu khôngendcasesendaligned>

(-infty) là 1 trong những chặn dưới dĩ nhiên của phần đông hàm số. Vì chưng đó, làm cho hàm đối ngẫu (g(lambda, u)) là 1 chặn dưới đích thực thì ta cần có (c + A^T u – lambda = 0)

Bài toán đối ngẫu của vấn đề LP trong lấy ví dụ này là việc tìm chặn dưới tối ưu độc nhất vô nhị <eginalignedmax và – b^T u \mathrms.t.~ và A^T u – lambda + c = 0 \& lambda geq 0.endaligned> tuyệt tương dương với <eginalignedmax & – b^T u \mathrms.t.~ & A^T u + c geq 0.endaligned>

Ví dụ 6:

Xét việc LP bao gồm ràng buộc dạng bất đẳng thức: <eginalignedmathrmmin~ và c^T x labeleq:ex3_lp\mathrms.t.~ và Ax geq bendaligned>

Hàm đối ngẫu được đến bởi: <eginalignedg(lambda) &= min_x L(x, lambda) = -b^T lambda + min_x(A^T lambda + c)^T x \& = egincases -b^T lambda ~ extrmnếu ~ A^T + c lambda = 0 \-infty , ~ extrmnếu~ A^T + c lambda eq 0 endcasesendaligned>

Do đó, vấn đề đối ngẫu của bài toán trong ví dụ này có dạng: <eginalignedmax & – b^T lambda \mathrms.t.~ và A^T lambda + c = 0 \& lambda geq 0.endaligned>

Tính chất đối ngẫu yếu và mạnh

Đối ngẫu yếu đuối (weak duality)

Gọi (p^*) cùng (d^*) là quý hiếm cực trị của bài toán gốc và việc đối ngẫu. Do tính chất hàm đối ngẫu luôn luôn là ngăn dưới của (p^*) đề xuất ta có bất đẳng thức: <eginalignedd^* leq p^*endaligned> luôn đúng. Bất đẳng thức bên trên được hotline là tính đối ngẫu yếu của vấn đề gốc Primal. Quý hiếm (p^* – d^*) được gọi là khoảng cách đối ngẫu buổi tối ưu (optimal duality gap) của vấn đề Primal.

Đối ngẫu mạnh dạn (strong duality)

Trong trường phù hợp (d^* = p^*), ta nói câu hỏi Primal có tính đối ngẫu mạnh (strong duality). Ta có đặc thù sau: Nếu vấn đề Primal lồi và điều kiện Slater thỏa mãn nhu cầu thì câu hỏi có tính đối ngẫu mạnh.

Điều khiếu nại Slater: mãi mãi một điểm vào (interior point) của tập khả thi của bài toán, tốt còn có nghĩa là tồn tại một điểm (x in mathbfrelint mathcalD) làm thế nào cho (f_i(x) cùng (Ax = b).

Các đk tại điểm cực trị

Complementary slackness

Một số tài liệu kinh tế tài chính dịch complementary slackness là định lý bù yếu. Giả sử việc tối ưu bao gồm tính đối ngẫu mạnh, có nghĩa là <eginalignedf_0(x^*) & = g(lambda^*, u^*)endaligned> tuy nhiên ta có: <eginalignedg(lambda^*, u^*) & = min_x Big( f_0(x) + sum_i = 1^m lambda_i^* f_i(x) + sum_i = 1^p u_i^* h_i(x) Big)\& leq f_0(x^*) + sum_i = 1^m lambda_i^* f_i(x^*) + sum_i = 1^p u_i^* h_i(x^*) \& leq f_0(x^*).endaligned>

Từ kia dẫn cho (sum_i = 1^m lambda_i^* f_i(x^*) = 0). Vì thế <eginalignedlambda_i^* f_i(x^*) =0, forall i = 1, ldots, m.endaligned>

Nếu (lambda_i^* > 0), thì (f_i(x^*) = 0) (ràng buộc (i) chặt trên (x^*)) và nếu (f_i(x^*) (ràng buộc (i) lỏng tại (x^*)), thì (lambda_i^* = 0).

Điều khiếu nại Karush-Kuhn-Tucker

Giả sử hàm kim chỉ nam và những hàm buộc ràng (f_0, ldots, f_m, h_1, ldots, h_p) khả vi. Gọi (x^*) và ((lambda^*, u^*)) lần lượt là những điểm cực trị của vấn đề chính và việc đối ngẫu. Nếu như ta gồm đối ngẫu bạo dạn thì các điều kiện Karush-Kuhn-Tucker (KKT) thỏa mãn: <eginalignedf_i(x^*) & leq 0, i = 1, ldots , m\h_i(x^*) & = 0, i = 1, ldots , phường \lambda_i^* và geq 0, i = 1, ldots , m \lambda_i^* f_i(x^*) & = 0, i = 1, ldots , m\ abla f_0(x^*) + sum_i = 1^m lambda_i^* abla f_i(x^*) + sum_i = 1^p u_i^* abla h_i(x^*) và = 0.endaligned>

Hai điều kiện thứ nhất là những điều kiện đến (x^*) là một điểm hợp lệ trong tập khả thi của vấn đề Primal. Điều khiếu nại thứ bố là điều kiện cho (lambda^*) là một trong điểm vừa lòng lệ trong tập khả thi của việc Dual. Điều khiếu nại thứ tứ là complementary slackness. Điều khiếu nại cuối cùng đó là ( abla_x L = 0).

Trong trường hợp bài toán chính là tối ưu lồi, các điều kiện KKT cũng là điều kiện đủ. Nếu như (( ildex, ildelambda, ilde u)) thỏa các điều kiện KKT sau: <eginalignedf_i( ildex) và leq 0, i = 1, ldots , m\h_i( ildex) và = 0, i = 1, ldots , p. \ ildelambda_i và geq 0, i = 1, ldots , m \ ildelambda_i f_i( ildex) & = 0, i = 1, ldots , m\ abla f_0( ildex) + sum_i = 1^m ildelambda_i abla f_i( ildex) + sum_i = 1^p ilde u_i abla h_i( ildex) & = 0.endaligned> thì ( ildex) với (( ildelambda, ilde u)) là các điểm rất trị của việc chính và câu hỏi đối ngẫu tương ứng.

Ta nhận biết điều khiếu nại KKT là đk tổng quát mang lại một việc tối ưu tất cả ràng buộc trên điểm rất trị.

Ví dụ 7: việc cực tiểu hàm toàn phương với ràng buộc đẳng thức

Xét việc <eginalignedmin ~ & (1/2) x^T Px + q^Tx + r \mathrms.t. ~ và Ax = b,endaligned> trong những số đó (P) là ma trận đối xứng khẳng định dương. Câu hỏi trên là một trong bài toán tối ưu lồi. Điều kiện KKT của việc trên bao gồm: <eginalignedA x^* = b, Px^* + q + A^T u^* = 0.endaligned>

<eginalignedeginbmatrix P và A^T \ A và 0 endbmatrix eginbmatrix x^* \ u^* endbmatrix = eginbmatrix -q \ b endbmatrix.endaligned>

Ví dụ 8: câu hỏi water-filling

Bài toán water-filling được vận dụng để cực to dung lượng kênh truyền vào viễn thông. Giả sử (x_i) là công suất truyền bên trên kênh sản phẩm (i). Dung dung lượng của kênh (i) tất cả dạng cách làm Shannon <eginalignedlog(alpha_i + x_i), endaligned> trong số đó (a_i) là 1 trong những hằng số được xem từ những tham số của kênh truyền như khoảng cách từ trạm phát mang lại đầu nhận, nhiễu ,… ví như trạm phát sẽ truyền bên trên (n) kênh, việc tối ưu đến trạm phân phát là cực đại tổng dung tích các kênh, tuy thế tổng hiệu suất phát ko đổi. <eginalignedmin ~ & -sum_i = 1^n log(alpha_i + x_i) \mathrms.t. ~ và x geq 0, 1^T x = 1,endaligned> trong đó (alpha_i > 0).

Điều khiếu nại KKT bao gồm: <eginalignedx^* geq 0, 1^T x^* = 1, lambda^* geq 0, lambda_i^* x_i^* =0, i = 1, ldots, n,\-1 / (alpha_i + x_i^*) – lambda_i^* + u^* = 0, i = 1, ldots, n.endaligned>

Do đó, ta tất cả (x_i^* = max 0, 1/ u^* – alpha_i \) và (sum_i = 1^n max 0, 1/ u^* – alpha_i = 1).

Xem thêm: Soạn Bài Phong Cách Ngôn Ngữ Hành Chính, Please Wait

Hình 1: Hình minh họa nghiệm của bài toán water filling.Ghi chú

Các thuật ngữ sử sử dụng trong phần này:

Thuật ngữ giờ Việt:	Thuật ngữ giờ Anh:
bài toán đối ngẫu	dual problem
hàm đối ngẫu	dual function
liên hợp	conjugate
đối ngẫu yếu	weak duality
đối ngẫu mạnh	strong duality
điều khiếu nại Slater	Slater condition

Tài liệu tham khảo:

Stephen p Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.Convex optimization lectures. Available at www.stat.cmu.edu/(sim)ryantibs/convexopt/.