Chương 2: Cơ sở qui hoạch lồi

Tham khảo tài liệu chương 2: cơ sở qui hoạch lồi, khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Chương 2: Cơ sở qui hoạch lồiLý thuyêt Qui hoach tuyên tinh ́ ̣ ́ ́CHƯƠNG II: CƠ SỞ QUI HOẠCH LỒI§ 1 Bài toán qui hoạch lồi cơ bản1.1 Trình bày bài toán qui hoạch lồi cơ bảnCho Γ⊆ Rn, lồi, f là hàm lồi xác định trên Γ, gi, i =1,2,…,m, là m hàm lõmcũng xác định trên Γ, bi , i = 1,2,…,m, là m số thực. Dễ thấy rằng, nếu tậphợp X = {x∈Rn/ gi(x) ≥ bi, i = 1,2,…,m; x∈Γ} (1.1)không rỗng thì nó là tập hợp lồi, đóng trong Rn (Bài tập 42). Để cho gọn, ký hiệu g(x) = (g1(x), g2(x), …, gm(x)) là vectơ m hàmsố, b = (b1, b2, …, bm) ∈ Rm. Khi đó tập tập X được viết dưới dạng X = { x∈Rn / g(x) ≥ b, x∈Γ} (1.2)trong đó ký hiệu g(x) ≥ b ⇔ gi(x) ≥ bi, i = 1,2, …, m. Bài toán cực trị sauđây được gọi là bài toán qui hoach lôi cơ bản. ̣ ̀ Tìm x0∈X, để cho f (x ) = minf (x) 0 x∈X (1.3) Lý thuyết và các phương pháp giải bài toán (1.3) được gọi là Lýthuyết qui hoạch lồi. Trong chương này chỉ trình bày phần lý thuyết làmcơ sở cho việc xây dựng các thuật toán. Các phương pháp để giải bài toán(1.3) sẽ được trình bày trong chuyên đề Qui hoạch phi tuyến ở học kỳ 7.1.2 Điều kiện chính quiĐn 1.1: Tập hợp X xác định theo (1.1) hoặc (1.2) được gọi là thỏa mãn điều kiện cính qui, nếu ∀i, 1≤ i ≤ m, ∃ xi: gi(xi) > bi (1.4) Ngoài ra, tập X cũng được coi là thoả mãn điều kiện chính qui Slater, nếu ∃ x0: gi(x0) > bi ∀i, 1≤ i ≤ m (1.5) Dễ thấy rằng hai điều kiện chính qui (1.4) và (1.5) là tương đươngnhau; tức là nếu X thỏa mãn điều kiện chính qui (1.4) thì cũng thỏa điềukiện chính qui (1.5) và ngược lại (Bài tập 43). Lê Văn Phi, Khoa Toan Thông kê, Trường Đai hoc Kinh tế Tp. Hồ Chí Minh ́ ́ ̣ ̣ 43Lý thuyêt Qui hoach tuyên tinh ́ ̣ ́ ́1.3 Hàm Lagrange Ứng với mọi x∈Γ, xét vectơ m chiều h(x) = b – g(x),tức là hi(x) = b – gi(x), i = 1,2,…,mTrên Γ× {y∈Rm/ y ≥ 0} ta định nghĩa hàm số m L(x,y) = f(x) + 〈y, h(x)〉 = f(x) + ∑ yi [bi − g i (x)] i =1 (1.6)Hàm L(x,y) được định nghĩa theo (1.6) được gọi là hàm Lagrange ứng với ̣ ̀bài toán qui hoach lôi (1.3).§ 2 Các điều kiện tối ưu của bài toán qui ho2.1 Điểm yên ngựa Cho S ⊆ Rn, T⊆ Rm và ϕ(s,t) là hàm số xác định trên S× T.Đn 2.1: Điểm (s*, t*) ∈ S× T được gọi là điểm yên ngựa (Hình ) của hàm ϕ (s, t) trên miền S× T, nếu ∀s∈S, ∀t∈T : ϕ(s*, t) ≤ ϕ(s*, t*) ≤ ϕ(s, t*)(2.1) ϕ S = T = [0;1], ϕ(s, t) = s + t ϕ(s, t*) ϕ ϕ(s*, t*) 2 ϕ(s*, t) (1;1) (0;1) t* (1;0) s* t (s*, t*) 1 t 1 s S ̀ Hinh 2.1 ̀ Hinh 2.2 Ở hình 2.1, điểm (s*, t*) = (0; 1) là điểm yên ngựa của hàm ϕ(s,t) = s + t. Vì,nếu giữ nguyên t* = 1 và thay đổi s (s chỉ có thể tăng từ 0 lên 1) thì giá trị hàm số sẽtăng từ 1 đến 2. Trong khi đó, nếu giữ nguyên s* = 0 và thay đổi t (t chỉ có thể giảmtừ 1 đến 0) thì giá trị hàm số giảm từ 1 đến 0. Trong khi điểm (1;0) không phải làđiểm yên ngựa. Ở ví dụ này cũng cho thấy rằng, điểm yên ngựa không phải là cực Lê Văn Phi, Khoa Toan Thông kê, Trường Đai hoc Kinh tế Tp. Hồ Chí Minh ́ ́ ̣ ̣ 44Lý thuyêt Qui hoach tuyên tinh ́ ̣ ́ ́trị của hàm Lagrange. (Giá trị cực tiểu của ϕ(s,t) = s + t là 0, tại (0;0), giá trị cực đạilà 2 tại điểm (1;1). Dễ dàng chứng minh được quan hệ sau đây: supinf φ ≤ inf supφ(s, t) (2.2) s∈S t∈T s∈S t∈TĐlí 2.1: Để cho hàm ϕ (s,t) có điểm yên ngựa trên miền S× T thì điều kiện cần và đủ là tồn tại các minmax maxinf φ(s, t) và min supφ(s, t) ; t∈T s∈S s∈S t∈T đồng thời chúng bằng nhau.Chứng minh:a) Điều kiện cần: Giả sử (s*,t*) là điểm yên ngựa của hàm ϕ(s,t) trênmiền S× T. Khi đó theo (2.1) supφ(s*, t) ≤ φ(s*, t*) và do đó t∈T inf supφ(s, t) ≤ φ(s*, t*) s∈S t∈TTương tự, φ(s*, t*) ≤ supinf φ(s, t) t∈T s∈SSuy ra bất đẵng thức kép inf supφ(s, t) ≤ supφ(s, t*) ≤ φ(s*, t*) ≤ inf φ(s, t*) ≤ supinf φ(s, t) s∈S t∈T t∈T s∈S t∈T s∈STừ (2.2) suy ra các dấu bất đẵng thức bên trong phải trở thành đẵng thức;tức là inf supφ(s, t) = su ...