BÀI TẬP TỐI ƯU HÓA CÓ LỜI GIẢI

  -  
Giới thiệu việc tối ưu

Một câu hỏi tối ưu có dạng chủ yếu tắc như sau: <eginalignedmathrmmin.~ & f_0(x) labeleq:convexprob_obj &qquad qquad qquad (1)\mathrms.t.~ & f_i(x) leq 0, i = 1, ldots, m &qquad qquad qquad (2)labeleq:convexprob_ineqcon\& h_i(x) = 0, i = 1, ldots, p, &qquad qquad qquad (3)labeleq:convexprob_eqcon endaligned> vào đó, (x in mathbfR^n) là biến của việc tối ưu, (f_0) là hàm mục tiêu,(2) và (3) là những ràng buộc.

Bạn đang xem: Bài tập tối ưu hóa có lời giải

(p^*) được call là nghiệm tối ưu trường hợp (p^* = min f_i(x) leq 0, i = 1,ldots,m, h_i(x) = 0, i = 1, ldots, p\).

Miền xác minh của vấn đề được tư tưởng là giao của các miền xác định của tất cả các hàm trong câu hỏi <eginalignedmathcalD = (cap_i=0^m mdom f_i) cap (cap_i=1^p mdom h_i).endaligned> Miền khả thi của vấn đề được khái niệm là tập hợp các điểm vừa lòng các buộc ràng <eginalignedleftlbrace x | x in mathcalD; f_i(x) leq 0, i = 1, ldots, m; h_i(x) = 0, i = 1, ldots, p. ight braceendaligned>

Nếu bài toán không tồn tại chặn dưới thì (p^* = -infty) với nếu miền nghiệm là trống rỗng thì bài toán vô nghiệm ((p^* = infty)).

(x^*) được gọi là điểm cực trị (hay vector cực trị) ví như (x^*) trực thuộc miền khả thi với (f_0(x^*) = p^*). Tập thích hợp tất các các điểm rất trị của câu hỏi thì được điện thoại tư vấn là tập rất trị <eginalignedX_opt = x endaligned>

Một vector (x^*) được gọi là vector cực trị cục bộ giả dụ tồn tại một vài thực (R) dương đủ nhỏ sao mang lại (f_0(x)) đạt rất tiểu trong kề bên của (x^*) bán kính (R) <eginalignedf_0(x^*) = & min z – x^* ,endaligned>

Một số thay đổi bài toán tương đương

Hai việc tối ưu được call là tương đương nếu ta có thể suy ra thuận tiện nghiệm của một vấn đề nếu bao gồm nghiệm của việc kia.

Ví dụ có một trong những bài toán tối ưu nhưng ràng buộc dạng chận trên với chận dưới dễ dàng và đơn giản như sau <eginalignedmathrmmin.~ và f_0(x)\mathrms.t.~ và l_i leq x_i leq u_i, i = 1, ldots, n.endaligned> Ta hoàn toàn có thể chuyển câu hỏi trên thành bài toán tối ưu dạng chính tắc như sau: <eginalignedmathrmmin.~ và f_0(x)\mathrms.t.~ và l_i- x_i leq 0, i = 1, ldots, n\& x_i – u_i leq 0, i = 1, ldots, n.endaligned>

Bài toán tìm cực đại

Đối với việc tìm cực đại <eginalignedmathrmmax. ~ & f_0(x)\mathrms.t. ~ & f_i(x) leq 0, i = 1, ldots, m \& h_i(x) = 0, i = 1, ldots, p.endaligned> ta rất có thể chuyển vấn đề trên về thành tìm rất tiểu (- f_0(x)).

Biến đổi các hàm mục tiêu và ràng buộc

Một vấn đề có hàm kim chỉ nam và các ràng buộc được nhân với các hằng số cũng là bài bác toán tương tự với việc gốc <eginalignedmathrmmin. ~ và ildef(x) = alpha_0 f_0(x)\mathrms.t ~ và ildef_i (x) = alpha_i f_i(x) leq 0, i = 1, ldots, m \& ildeh_i(x) = eta_i h_i(x) = 0, i = 1, ldots, p,endaligned> trong những số đó (alpha_i > 0, i=0, ldots, m) và (eta_i eq 0, i=1, ldots, p).

Ta cũng rất có thể đổi thay đổi (x = phi(z)) để biến đổi bài toán tương đương miễn phép đổi trở nên (phi) là ánh xạ một – một: <eginaligned ildef_i(z) = f_i(phi(z)), i = 0, ldots, m, quad ildeh_i(z) = h_i(phi(z)), i = 0, ldots, p.endaligned> cho nên bài toán tương đương dành được là: <eginalignedmathrmmin.~ & ildef_0 (z) \mathrmst.~ và ildef_i (z) leq 0, i = 1, ldots, m \& ildeh_i(z) = 0, i = 1, ldots, pendaligned>

Ta cũng đều có thể đổi khác tương đương những hàm phương châm và buộc ràng bằng các hàm riêng biệt rẽ. Mang đến (psi_0: mathbbR^n ightarrow mathbbR^n) là hàm 1-1 điệu tăng, (psi_1, ldots, psi_m: mathbbR ightarrow mathbbR) thỏa mãn (psi_i(u) leq 0) nếu còn chỉ nếu (u leq 0), và (xi_1, ldots, xi_p: mathbbR ightarrow mathbbR) nhất trí (xi_i(u) = 0) nếu và chỉ còn nếu (u = 0). Định nghĩa những hàm số sau: <eginaligned ildef_i(x) &= psi_i(f_i(x)), i = 0, ldots, m, \ ildeh_i(x) &= xi_i(h_i(x)), i = 0, ldots, p.endaligned> Ta có bài toán sau tương được với câu hỏi gốc (1)-(3) <eginalignedmathrmmin.~ & ildef_0 (x) \mathrms.t.~ và ildef_i (x) leq 0, i = 1, ldots, m \& ildeh_i(x) = 0, i = 1, ldots, p.endaligned>

Ví dụ những bài toán rất tiểu norm và rất tiểu norm bình phương là tương đương. Thay vày giải việc gốc <eginalignedmin ~ | Ax – b |_2.endaligned> ko khả vi tại một số trong những điểm, ta hoàn toàn có thể giải bài bác toán tương tự khả vi tại số đông điểm <eginalignedmin ~ | Ax – b |_2^2 = (Ax – b)^T(Ax – b).endaligned>

Biến phụ

Biến đổi việc tương đương có thể thực hiện bằng phương pháp thêm vào biến phụ. Ví dụ vấn đề sau tương được với câu hỏi gốc (1)-(3) bằng cách thêm biến chuyển (s_i, i = 1, ldots, m) <eginalignedmathrmmin.~ & f_0(x)\mathrms.t.~ và s_i geq 0, i = 1, ldots, m \& f_i(x) + s_i = 0, i = 1, ldots, m \& h_i(x) = 0, i = 1, ldots, p.endaligned>

Lược giảm và thêm ràng buộc đẳng thức

Ta cũng rất có thể lược bớt ràng buộc đẳng thức nếu có hàm số (phi) làm thế nào để cho (h_i(x) = 0, i = 1, ldots, p) nếu còn chỉ nếu (x = phi(z)), thì ta có câu hỏi sau tương tự với vấn đề gốc (1)-(3). <eginalignedmathrmminimization~ & ildef(z) = f_0(phi(z)) \mathrmsubject ~ to~ và ildef_i (z) = f_i(phi(z)) leq 0, i = 1, ldots, m.endaligned>

Thêm buộc ràng đẳng thức Hai bài toán sau là tương đương: <eginalignedmathrmmin.~ & f_0(A_0 x + b_0)\mathrms.t.~ và f_i(A_i x + b_i) leq 0, i = 1, ldots, m \& h_i(x) = 0, i = 1, ldots, p.endaligned> với <eginalignedmathrmmin.~ & f_0(y_0)\mathrms.t.~ và f_i(y_i) leq 0, i = 1, ldots, m \& y_i = A_i x + b_i, i = 0, ldots, m \& h_i(x) = 0, i = 1, ldots, p.endaligned>

Tối ưu trên một vài ba biến

Ta cũng hoàn toàn có thể thực hiện tối ưu trên một vài ba biến đối với một số việc dạng đăc biệt. Ví như bài toán bao gồm hai nhóm ràng buộc độc lập giữa (x_1) với (x_2) sau <eginalignedmathrmmin.~ & f_0(x_1, x_2)\mathrms.t.~ và f_i(x_1) leq 0, i = 1, ldots, m_1\& g_i(x_2) leq 0, i = 1, ldots, m_2endaligned> sẽ tương đương với việc <eginalignedmathrmmin.~ và ildef_0(x_1)\mathrms.t.~ và f_i(x_1) leq 0, i = 1, ldots, m_1,endaligned> trong số đó <eginaligned ildef_0(x_1) = min_x_2 f_0(x_1, x_2).endaligned>

Biến thay đổi dạng epigraph

Bài toán dạng epigraph sau là tương tự với vấn đề gốc <eginalignedmathrmmin.~ và t\mathrms.t.~ và f_0(x) – t leq 0 \& f_i(y_i) leq 0, quad i = 1, ldots, m \& h_i(x) = 0, quad i = 1, ldots, p.endaligned> ((x^*, t^*)) là cực tiểu của việc dạng epigraph nếu và chỉ nếu (x^*) là điểm cực đái của việc gốc và đồng thời (t^* = f_0(x^*)).

Bài toán tối ưu lồi

Bài toán buổi tối ưu lồi bao gồm dạng như sau <eginalignedmathrmmin.~ & f_0(x)\mathrms.t.~ và f_i(x) leq 0, quad i = 1, ldots, m \& a_i^T x = b_i, quad i = 1, ldots, p.endaligned> vào đó, các hàm kim chỉ nam và buộc ràng bất đăng thức (f_i, i=1, ldots, m) đa số là hàm lồi. Buộc ràng dạng đẳng thức phải ở dạng tuyến đường tính.

Từ tính chất giao các tập lồi là tập lồi với epigraph của một hàm lồi là một tập lồi, ta có miền khả thi của một câu hỏi tối ưu lồi là một tập lồi.

Bài toán tìm cực đại hàm lõm

Bài toán tìm cực đại <eginalignedmathrmmax.~ và f_0(x) labeleq:convprob_obj\mathrms.t.~ và f_i(x) leq 0, quad i = 1, ldots, m labeleq:convprob_incon\& a_i^T x = b_i, quad i = 1, ldots, p, labeleq:convprob_affconendaligned> trong đó trong kia (f_0) là hàm lõm và các hàm (f_i, i=1,…,m) lồi cũng được coi là bài toán về tối ưu lồi.

Xem thêm: Số Lượng Hãng Hàng Không Lớn Ở Hoa Kỳ, Tổng Hợp Các Sân Bay Quốc Tế Ở Mỹ

Điểm cực trị

Trong bài toán tối ưu lồi, điểm cực trị toàn thể cũng là vấn đề cực trị toàn cục.

Giả sử miền khả thi của câu hỏi là là (X = f_i(x) leq 0, i=1, ldots, m, h_i(x) = 0, i = 1, ldots, p. \). Trong trường vừa lòng hàm (f_0) khả vi, (x^*) là vấn đề cực trị nếu và chỉ còn nếu (x^* in X) và <eginaligned abla f_0(x^*)^T (y – x^*) geq 0, quad forall y in X.endaligned>

Đặc biệt nếu bài toán tối ưu không có ràng buộc thì điều kiện cần và đủ để (x^*) cực trị là <eginaligned abla f_0(x) = 0endaligned>

Một số lấy ví dụ về việc tối ưu lồi

Bài toán quy hoạch đường tính mà lại ta đã làm quen ở Chương một là một việc tối ưu lồi. <eginalignedmathrmmin.~ & c^T x + d \mathrms.t.~ & Gx preceq h \& A x = b,endaligned> trong đó (G in mathbbR^m imes n) cùng (A in mathbbR^p imes n).

Các biến đổi tương đương sau vẫn bảo toàn tính lồi bến việc gốc là lồi.

Dạng epigraph của một việc lồi cũng là một trong bài toán lồi.Thêm trở thành phụ (s_i) khớp ứng với buộc ràng (f_i(x) leq 0) để vươn lên là ràng buộc này thành buộc ràng dạng đẳng thức.Bài toán tối ưu trên một số biến vào trường hợp bài toán gốc có các ràng buộc chủ quyền theo các biến vẫn luôn là bài toán lồi (xem phần 3.2).

Bài toán tối ưu hàm toàn phương

Bài toán buổi tối ưu hàm toàn phương có dạng sau <eginalignedmathrmmin.~ & (1/2) x^T p. X + q^T x + r \mathrms.t.~ và Gx leq h \& A x = b,endaligned> trong những số đó (P in mathbbR^n imes n, p. succeq 0), (G in mathbbR^m imes n) và (A in mathbbR^p imes n). Bài toán trên là một trong bài toán tối ưu lồi.

Bài toán tối ưu vào hồi quy tuyến đường tính (linear regression hay còn được gọi là least square) chính là một bài toán tối ưu hàm toàn phương <eginaligned| Ax – b|^2_2 = x^T A^T A x – 2b^T A x + b^T b.endaligned> Nghiệm của vấn đề tối ưu trên là (x^* = A^dagger b), trong số ấy (A^dagger = (A^T A)^-1 A^T) là ma trận nghịch hòn đảo giả (Moore-Penrose pseudo-inverse) của ma trận A, được coi là dạng tổng quát của phép nghịch hòn đảo ma trận vào trường hợp ma trận ko vuông hay không khả nghịch.

Geometric programming

Bài toán về tối ưu geometric programming lộ diện trong một số nghành trong kỹ thuật, tởm tế, công nghệ quản lý,… các bài toán maximum likelihood vào học sản phẩm thường thuộc đội này. Ta hoàn toàn có thể đưa câu hỏi geometric programming thành vấn đề lồi tương đương.

Ta có một trong những định nghĩa trước khi định nghĩa việc geometric programming như sau: Hàm 1-1 thức (monomial) được có mang là (f(x) = c x_1^a_1 x_2^a_2 ldots x_n^a_n), trong số đó (c > 0, a_i in mathbbR). Hàm đa thức (posynomial) là hàm gồm dạng như sau (f(x) = sum_k = 1^K c x_1^a_1k x_2^a_2k ldots x_n^a_nk) trong số ấy (c_k > 0).

Bài toán về tối ưu gồm dạng <eginalignedmathrmmin.~ và f_0(x)\mathrms.t.~ và f_i(x) leq 1, quad i = 1, ldots, m \& h_i(x) = 1, quad i = 1, ldots, p,endaligned> trong những số ấy (f_0, ldots, f_m) gần như là posynomial, (h_i) là monomial được hotline là bài toán tối ưu dạng geometric programming.

Xem thêm: Unit A Reading - Reading: Match Words With Their Definition

Bằng phương pháp thay biến đổi (y_i = log x_i) và lấy logarit các hàm, ta có

đơn thức (f(x) = c x_1^a_1 x_2^a_2 ldots x_n^a_n) phát triển thành <eginalignedlog f(e^y_1, ldots, e^y_n)= a^T y + bendaligned> trong số ấy (b = log c),posynomial (f(x) = sum_k = 1^K c x_1^a_1k x_2^a_2k ldots x_n^a_nk) biến <eginalignedlog f(e^y_1, ldots, e^y_n)= logBig(sum_i=1^K e^a_ik^T + b_ikBig),endaligned> trong các số ấy (b_k = log c_k),

Do đó, geometric programming tương tự với việc tối ưu lồi sau <eginalignedmathrmmax.~ và logBig(sum_i=1^K e^a_0k^T + b_0kBig)\mathrms.t.~ & logBig(sum_i=1^K e^a_ik^T + b_ikBig) leq 1, quad i = 1, ldots, m \& Gy + d = 0, quad i = 1, ldots, p.endaligned>

Tài liệu tham khảo:

Stephen p Boyd & Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.