Sửa đổi Phân loại các bài toán quy hoạch toán học
Chú ý: Bạn chưa đăng nhập và địa chỉ IP của bạn sẽ hiển thị công khai khi lưu các sửa đổi.
Bạn có thể tham gia như người biên soạn chuyên nghiệp và lâu dài ở Bách khoa Toàn thư Việt Nam, bằng cách đăng ký và đăng nhập - IP của bạn sẽ không bị công khai và có thêm nhiều lợi ích khác.
Các sửa đổi có thể được lùi lại. Xin hãy kiểm tra phần so sánh bên dưới để xác nhận lại những gì bạn muốn làm, sau đó lưu thay đổi ở dưới để hoàn tất việc lùi lại sửa đổi.
Bản hiện tại | Nội dung bạn nhập | ||
Dòng 135: | Dòng 135: | ||
===Phần trong tương đối=== | ===Phần trong tương đối=== | ||
− | Tập con | + | Tập con M ⊂ Rn được gọi là một tập affine (a-phin) nếu tx + (1 − t)y ∈ M với mọi x ∈ M, y ∈ M và t ∈ R. Đối với một D ⊂ Rn, bao affine affD of D là tập affine nhỏ nhất chứa D. Phần trong tương đối của D được xác định bởi công thức |
− | + | riD := {x ∈ D : ∃δ > 0 sao cho B(x, δ) ∩ affD ⊂ D}. | |
Định lý sau đây mô tả mối quan hệ giữa đạo hàm theo hướng và dưới vi phân của các hàm lồi. | Định lý sau đây mô tả mối quan hệ giữa đạo hàm theo hướng và dưới vi phân của các hàm lồi. | ||
− | + | Định lý 0.0.3. (Xem Rockafellar (1970), Định lý 23.4) Cho f là một hàm lồi trên Rn. Nếu x /∈ domf, thì ∂f(x) là rỗng. Nếu x ∈ ri(domf), thì ∂f(x) là khác rỗng và | |
− | + | f0(x; v) = sup{hx ∗ , vi : x ∗ ∈ ∂f(x)}, ∀v ∈ Rn. | |
− | Ngoài ra, | + | Ngoài ra, ∂f(x) là tập khác rỗng và giới nội khi và chỉ khi |
− | + | x ∈ int(domf); | |
− | trong trường hợp đó, | + | trong trường hợp đó, f0(x; v) là hữu hạn với mỗi v ∈ Rn. |
Kết quả sau đây được gọi là Định lý Moreau-Rockafellar. | Kết quả sau đây được gọi là Định lý Moreau-Rockafellar. | ||
− | + | Định lý 0.0.4. (Xem Rockafellar (1970), Định lý 23.8) Cho f = f1 + · · · + fk, ở đó f1, . . . , fk là các hàm lồi, chính thường trên Rn. Nếu | |
− | + | ki=1 ri(domfi) 6= ∅, | |
thì | thì | ||
− | + | ∂f(x) = ∂f1(x) + · · · + ∂fk(x), ∀x ∈ Rn. | |
Điều kiện cần và đủ tối ưu cho các bài toán quy hoạch lồi được phát biểu như sau. | Điều kiện cần và đủ tối ưu cho các bài toán quy hoạch lồi được phát biểu như sau. | ||
− | + | Định lý 0.0.5. (Xem Rockafellar (1970), Định lý 27.4) Giả sử rằng f là một hàm lồi, chính thường trên Rn và D ⊂ Rn là một tập lồi. Nếu bao hàm thức | |
− | + | 0 ∈ ∂f(¯x) + ND(¯x) (6) | |
− | nghiệm đúng với | + | nghiệm đúng với x¯ ∈ Rn, thì x¯ là nghiệm của (P). Ngược lại, nếu |
− | + | ri(domf) ∩ riD 6= ∅, (7) | |
− | thì ( | + | thì (6) là điều kiện cần và đủ cho x¯ ∈ Rn là nghiệm của (P). Nói riêng ra, nếu D = Rn, thì x¯ là một nghiệm của (P) khi và chỉ khi 0 ∈ ∂f(¯x). |
− | Bao hàm thức ( | + | Bao hàm thức (6) có nghĩa là tồn tại x∗ ∈ ∂f(¯x) và u∗ ∈ ND(¯x) sao cho 0 = x∗ + u∗. Nhận xét rằng (7) là một điều kiện chính quy cho bài toán quy hạch lồi có dạng (P). |
Định lý 0.0.5 là công cụ hiệu quả để giải nhiều bài toán quy hoạch lồi. Chúng ta có thể minh họa điều đó bằng cách xét ví dụ sau đây. | Định lý 0.0.5 là công cụ hiệu quả để giải nhiều bài toán quy hoạch lồi. Chúng ta có thể minh họa điều đó bằng cách xét ví dụ sau đây. | ||
Dòng 179: | Dòng 179: | ||
===Điểm Fermat=== | ===Điểm Fermat=== | ||
− | Cho | + | Cho A, B, C là ba điểm trong không gian hai chiều R2 với các tọa độ tương ứng là |
− | + | a = (a1, a2), b = (b1, b2), c = (c1, c2). | |
− | Giả sử rằng không tồn tại đường thẳng nào chứa tất cả ba điểm đó. Bài toán đặt ra là tìm một điểm | + | Giả sử rằng không tồn tại đường thẳng nào chứa tất cả ba điểm đó. Bài toán đặt ra là tìm một điểm M trong R2 với các tọa độ x¯ = (¯x1, x¯2) sao cho tổng khoảng cách từ M tới A, B và C là tối thiểu. Điều đó có nghĩa rằng x¯ là một nghiệm của bài toán quy hoạch lồi không có ràng buộc sau: |
− | + | min{f(x) := kx − ak + kx − bk + kx − ck : x ∈ R2}. (8) | |
Sử dụng định lý Weierstrass và tính lồi chặt của <math>f(x)</math> trên <math>\mathbb{R}^2</math>, ta có thể chứng tỏ rằng ({{EquationNote|8}}) có duy nhất nghiệm; xem Lee, Tam, Yen (2005), tr. 11–13. Để ý rằng <math>f = f_1 + f_2 + f_3</math>, ở đó <math>f_1(x) = \lVert x - a \rVert, f_2(x) = \lVert x - b \rVert, f_3(x) = \lVert x - c \rVert</math>. Theo Định lý 0.0.5, <math>\bar{x}</math> là nghiệm của ({{EquationNote|8}}) khi và chỉ khi <math>0 \in \partial f(\bar{x})</math>. Vì <math>\text{dom} f_i = \mathbb{R}^2 (i = 1, 2 ,3)</math>, sử dụng Định lý 0.0.4 ta có thể viết bao hàm thức cuối dưới dạng | Sử dụng định lý Weierstrass và tính lồi chặt của <math>f(x)</math> trên <math>\mathbb{R}^2</math>, ta có thể chứng tỏ rằng ({{EquationNote|8}}) có duy nhất nghiệm; xem Lee, Tam, Yen (2005), tr. 11–13. Để ý rằng <math>f = f_1 + f_2 + f_3</math>, ở đó <math>f_1(x) = \lVert x - a \rVert, f_2(x) = \lVert x - b \rVert, f_3(x) = \lVert x - c \rVert</math>. Theo Định lý 0.0.5, <math>\bar{x}</math> là nghiệm của ({{EquationNote|8}}) khi và chỉ khi <math>0 \in \partial f(\bar{x})</math>. Vì <math>\text{dom} f_i = \mathbb{R}^2 (i = 1, 2 ,3)</math>, sử dụng Định lý 0.0.4 ta có thể viết bao hàm thức cuối dưới dạng |