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 49: | Dòng 49: | ||
{{NumBlk|:|<math>f((1 - t)x + ty) \le (1 - t)f(x) + tf(y), \forall x, y \in \mathbb{R}^n, \forall t \in (0, 1).</math>|{{EquationRef|2}}}} | {{NumBlk|:|<math>f((1 - t)x + ty) \le (1 - t)f(x) + tf(y), \forall x, y \in \mathbb{R}^n, \forall t \in (0, 1).</math>|{{EquationRef|2}}}} | ||
− | Tổng quát hơn, một hàm | + | Tổng quát hơn, một hàm f : Rn → R ∪ {+∞} là lồi khi và chỉ khi |
− | + | f(λ1x1 + · · · + λkxk) ≤ λ1f(x1) + · · · + λkf(xk) (bất đẳng thức Jensen) | |
− | với mọi | + | với mọi x1, . . . , xk ∈ Rn và λ1 ≥ 0, . . . , λk ≥ 0, λ1 + · · · + λk = 1. (Xem Rockafellar (1970), Định lý 4.3.) |
===Hàm lồi chặt=== | ===Hàm lồi chặt=== | ||
− | Giả sử rằng | + | Giả sử rằng D ⊂ Rn là một tập lồi. Nếu bất đẳng thức trong (2) đúng với mọi x, y ∈ D và với mọi t ∈ (0, 1), thì ta nói f là lồi trên D. Nếu bất đẳng thức trong (2) nghiệm đúng như một bất đẳng thức chặt với mọi x, y ∈ D mà x 6= y và với mọi t ∈ (0, 1), thì ta nói f là lồi chặt trên D. |
===Bài toán quy hoạch lồi=== | ===Bài toán quy hoạch lồi=== | ||
− | Ta nói rằng | + | Ta nói rằng (P) là bài toán quy hoạch lồi nếu D là tập lồi và f là hàm lồi. Nếu (P) bài toán quy hoạch lồi, thì |
− | + | Sol(P) = loc(P). (3) | |
===Bài toán quy hoạch không lồi=== | ===Bài toán quy hoạch không lồi=== | ||
− | Nếu | + | Nếu D là tập không lồi hoặc f là hàm không lồi, thì ta nói (P) là bài toán quy |
+ | hoạch không lồi. | ||
Xét bài toán | Xét bài toán | ||
− | + | min{f(x) = (x1 − c1)2 + (x2 − c2)2: x ∈ D}, (4) | |
− | ở đó | + | ở đó D = {x = (x1, x2) ∈ R2 : x1 ≥ 0} ∪ {x = (x1, x2) : x2 ≥ 0} và c = (c1, c2) = (−2, −1). Nhận xét rằng f là lồi, trong khi D là không lồi. Rõ ràng rằng (4) là tương đương với bài toán sau đây: |
− | + | min{kx − ck : x ∈ D}. (5) | |
− | Có thể thấy rằng tập nghiệm của ( | + | Có thể thấy rằng tập nghiệm của (4) và (5) chỉ gồm một điểm (−2, 0), còn tập nghiệm địa phương gồm hai điểm: (−2, 0) và (0, −1). Điều này chứng tỏ rằng đẳng thức (3) nói chung không đúng với các bài toán quy hoạch không lồi. |
− | Đặt | + | Đặt f1(x) = −x + 2, f2(x) = x + 32 với mọi x ∈ R. Định nghĩa f(x) = min{f1(x), f2(x)} và chọn D = [0, 2] ⊂ R. Với hàm f và tập D đó, chúng ta có |
− | + | Sol(P) = {2}, loc(P) = {0, 2}; | |
− | tức là đẳng thức ( | + | tức là đẳng thức (3) không đúng cho bài toán trong ví dụ này. Ở đây, f là hàm không lồi và D là tập lồi. |
Các hàm lồi có nhiều tính chất thú vị. Chẳng hạn, hàm lồi là liên tục tại mỗi điểm trong của miền hữu hiệu của nó và nó là khả vi theo hướng tại mỗi điểm thuộc miền đó. | Các hàm lồi có nhiều tính chất thú vị. Chẳng hạn, hàm lồi là liên tục tại mỗi điểm trong của miền hữu hiệu của nó và nó là khả vi theo hướng tại mỗi điểm thuộc miền đó. | ||
Dòng 89: | Dòng 90: | ||
===Miền hữu hiệu=== | ===Miền hữu hiệu=== | ||
− | Đối với mỗi hàm số | + | Đối với mỗi hàm số f : Rn → R, tập hợp |
− | + | domf := {x ∈ Rn: −∞ < f(x) < +∞} | |
− | được gọi là | + | được gọi là miền hữu hiệu của f. |
===Đạo hàm theo hướng=== | ===Đạo hàm theo hướng=== | ||
− | Đối với một điểm | + | Đối với một điểm x¯ ∈ domf và một véctơ v ∈ Rn, nếu giới hạn |
− | + | f0(¯x; v) := limt↓0f(¯x + tv) − f(¯x)t | |
− | (có thể nhận các giá trị | + | (có thể nhận các giá trị +∞ và −∞) tồn tại, thì f được gọi là khả vi theo hướng tại x¯ theo hướng v và giá trị f0 (¯x; v) được gọi là đạo hàm theo hướng của f tại x¯ theo hướng v. Nếu f0(¯x; v) tồn tại với mọi v ∈ Rn, thì f được gọi là khả vi theo hướng tại x¯. |
− | Trong hai định lý tiếp theo đây, | + | Trong hai định lý tiếp theo đây, f : Rn → R ∪ {+∞} là một hàm lồi và chính thường. |
− | + | Định lý 0.0.1. (Xem Rockafellar (1970), Định lý 10.1) Nếu x¯ ∈ Rn và δ > 0 là điểm và số thực sao cho hình cầu mở B(¯x, δ) chứa trong domf, thì phần hạn chế của f trên B(¯x, δ) là một hàm số thực liên tục. | |
− | + | Định lý 0.0.2. (Xem Rockafellar (1970), Định lý 23.1) Nếu x¯ ∈ domf, thì với mỗi v ∈ Rn giới hạn | |
− | + | f0(¯x; v) := limt↓0f(¯x + tv) − f(¯x)t | |
tồn tại, và ta có | tồn tại, và ta có | ||
− | + | f0(¯x; v) = inft>0f(¯x + tv) − f(¯x)t. | |
===Nón pháp tuyến=== | ===Nón pháp tuyến=== | ||
− | + | Nón pháp tuyến ND(¯x) của tập lồi D ⊂ R | |
+ | n tại một điểm x¯ ∈ Rn được cho bởi công thức | ||
− | + | ND(¯x) = | |
− | + | {x∗ ∈ Rn: hx∗, x − x¯i ≤ 0 với mọi x ∈ D} nếu x¯ ∈ D | |
− | + | ∅ nếu x / ¯ ∈ D. | |
− | |||
− | |||
− | |||
− | |||
===Dưới vi phân=== | ===Dưới vi phân=== | ||
− | Dưới vi phân | + | Dưới vi phân ∂f(¯x) của một hàm lồi f : Rn → R tại một điểm x¯ ∈ Rn được định nghĩa bằng công thức |
− | + | ∂f(¯x) = {x∗ ∈ Rn: f(¯x) + hx∗, x − x¯i ≤ f(x) với mọi x ∈ Rn}. | |
===Phần trong tương đối=== | ===Phần trong tương đối=== |