tailieunhanh - Bài giảng Tối ưu hóa nâng cao: Chương 2 - Hoàng Nam Dũng

Bài giảng "Tối ưu hóa nâng cao - Chương 2: Các kiến thức cơ sở" cung cấp cho người học các kiến thức: Tập lồi, tổ hợp lồi và bao lồi, hàm lồi ngặt và hàm lồi mạnh, đặc trung hàm lồi, biến đổi giữa các dạng bài toán tối ưu,. . | Bài giảng Tối ưu hóa nâng cao: Chương 2 - Hoàng Nam Dũng Các kiến thức cơ sở Hoàng Nam Dũng Khoa Toán - Cơ - Tin học, Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội Tập lồi Định nghĩa Tập hợp S ⊆ Rn là một tập lồi nếu λx + (1 − λ)y ∈ S, ∀λ ∈ [0, 1], x, y ∈ S. Nói một cách khác đoạn thẳng nối hai điểm hoàn toàn nằm trong tập hợp nếu hai đầu mút cũng thuộc tập hợp. 1 Tập lồi Định nghĩa Tập hợp S ⊆ Rn là một tập lồi nếu λx + (1 − λ)y ∈ S, ∀λ ∈ [0, 1], x, y ∈ S. Nói một cách khác đoạn thẳng nối hai điểm hoàn toàn nằm trong tập hợp nếu hai đầu mút cũng thuộc tập hợp. Tập lồi Tập không lồi 1 Ví dụ tập lồi I Tập rỗng, điểm, đường thẳng, toàn bộ không gian Rn . I Hình cầu {x ∈ Rn | kxk ≤ r } với chuẩn k · k và bán kín r cho trước. I Siêu phẳng (hyperplane) {x ∈ Rn | aT x = b} với a ∈ Rn , b ∈ R cho trước. I Nửa không gian (halfspace) {x ∈ Rn | aT x ≤ b} với a ∈ Rn , b ∈ R cho trước. I {x ∈ Rn | Ax = b} với A ∈ Rm×n , b ∈ Rm cho trước. I Đa diện {x ∈ Rn | Ax ≤ b} với A ∈ Rm×n , b ∈ Rm cho trước. I . 2 Tổ hợp lồi và bao lồi Định nghĩa Một tổ hợp lồi của x1 , x2 , . . . , xk ∈ Rn là một tổ hợp tuyến tính λ1 x1 + λ2 x2 + · · · + λk xk với các hệ số λ1 , λ2 , . . . , λk ≥ 0 thỏa mãn λ1 + λ2 + · · · + λk = 1. 3 Tổ hợp lồi và bao lồi Định nghĩa Một tổ hợp lồi của x1 , x2 , . . . , xk ∈ Rn là một tổ hợp tuyến tính λ1 x1 + λ2 x2 + · · · + λk xk với các hệ số λ1 , λ2 , . . . , λk ≥ 0 thỏa mãn λ1 + λ2 + · · · + λk = 1. Định nghĩa Bao lồi của một tập hợp S, conv(S), là tập hợp của tất cả các tổ hợp lồi của các phần tử thuộc S. 3 Tổ hợp lồi và bao lồi Định nghĩa Một tổ hợp lồi của x1 , x2 , . . . , xk ∈ Rn là một tổ hợp tuyến tính λ1 x1 + λ2 x2 + · · · + λk xk với các hệ số λ1 , λ2 , . . . , λk ≥ 0 thỏa mãn λ1 + λ2 + · · · + λk = 1. Định nghĩa Bao lồi của một tập hợp S, conv(S), là tập hợp của tất cả các tổ hợp lồi của các phần tử thuộc S. conv(S) là một tập