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

Chia sẻ: Lê Văn Phi | Ngày: | Loại File: DOC | Số trang:13

Thêm vào BST

Báo xấu

177
lượt xem 67
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

Lý 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ản 1.1 Trình bày bài toán qui hoạch lồi cơ bản Cho Γ⊆ Rn, lồi, f là hàm lồi xác định trên Γ, gi, i =1,2,…,m, là m hàm lõm cũng xác định trên Γ, bi , i = 1,2,…,m, là m số thực. Dễ thấy rằng, nếu tập hợ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àm số, 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àm cơ 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 đương nhau; 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ều kiệ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ồ Chí Minh ́ ́ ̣ ̣ 43
Lý 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,…,m Trê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 ho 2.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ảm từ 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ồ Chí Minh ́ ́ ̣ ̣ 44
Lý 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 đại là 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ên miề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∈T Tương tự, φ(s*, t*) ≤ supinf φ(s, t) t∈T s∈S Suy 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∈S Từ (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) = supφ(s*, t) = φ(s*, t*) và s∈S t∈T t∈T supinf φ(s, t) = inf φ(s, t*) = φ(s*, t*) s∈S t∈T s∈S Hay maxinf φ(s, t) = φ(s*, t*) và min supφ(s, t*) = φ(s*, t*) t∈T s∈S s∈S t∈T b) Điều kiện đủ: Giả sử các giá trị minmax trong định lý tồn tại và bằng nhau, tức là ∃ s*∈S, t*∈T, sao cho maxinf φ(s, t) = inf φ(s, t*) và min supφ(s, t*) = supφ(s*, t) t∈T s∈S s∈S s∈S t∈T t∈T Suy ra inf φ(s, t*) ≤ φ(s*, t*) ≤ supφ(s*, t) . Theo giả thiết các minmax bằng s∈S t∈T nhau, nên các bất đẵng thức phải trở thành đẵng thức. Tức là inf φ(s, t*) = φ(s*, t*) = supφ(s*, t) s∈S t∈T Từ đây suy ra ∀s∈S, ∀t∈T: ϕ(s*,t) ≤ ϕ(s*,t*) ≤ ϕ(s,t*). Tức là cặp (s*,t*) là điểm yên ngựa củ hàm ϕ(s,t) trên miền S× T. ª1 1 Trong chứng minh trên các biến s, t biến thiên độc lập, nên nếu (s*,t*) và (s’,t’) là những điểm yên ngựa của ϕ(s,t) thì các cặp (s*,t’) và (s’,t*) cũng là điểm yên ngựa. Lê Văn Phi, Khoa Toan Thông kê, Trường Đai hoc Kinh tế Tp. Hồ Chí Minh ́ ́ ̣ ̣ 45
Lý thuyêt Qui hoach tuyên tinh ́ ̣ ́ ́ 2.2 Điểm yên ngựa của hàm Lagrange L(x,y) và điều kiện tối ưu Theo phần 1.3, hàm Lagrange của bài toán qui hoach lôi cơ bản (1.3) ̣ ̀ xác định trên miền Γ× {y∈Rm/ y ≥ 0} có dạng m L(x,y) = f(x) + 〈y, h(x)〉 = f(x) + ∑ yi [bi − g i (x)] (1.6) i =1 Theo Đn 2.1, thì cặp (x*, y*) là điểm yên ngựa của L(x,y) trên miền Γ× {y∈Rm/ y ≥ 0} khi ∀x∈Γ, ∀y≥ 0: L(x*,y) ≤ L(x*,y*) ≤ L(x,y*) (2.3) Do L(x,y) lồi theo x và tuyến tính theo y, đồng thời các tập Γ và {y∈Rm/ y ≥ 0} là những tập đóng, nên Đlí 2.2 trở thành: Để cho hàm Lagrange L(x,y) có điểm yên ngựa trên miền Γ× {y∈Rm/ y ≥ 0} thì điều kiện cần và đủ là các minmax maxminL(x, y) min maxL(x, y) (2.4) y≥0 x∈Γ x∈Γ y≥0 tồn tại và bằng nhau. Quan hệ giữa điểm yên ngựa của hàm L(x,y) và lời giải của bài toán qui hoach lồi cơ bản (1.3) được cho bởi định lý sau đây. ̣ Đlí 2.2: Nếu (x*, y*) là điểm yên ngựa của hàm L(x,y) trên miền Γ× {y∈Rm, y ≥ 0} thì x* là lời giải của bài toán (1.3). Chứng minh: Giả sử (x*, y*) là điểm yên ngựa của hàm L(x,y) trên miền Γ× {y∈Rm, y ≥ 0}. Tức là ∀x∈Γ, ∀ y ≥ 0 : f(x*) + 〈y, h(x*)〉 ≤ f(x*) + 〈y*, h(x*)〉 ≤ f(x) + 〈y*, h(x)〉 (2.5) Từ đây suy ra: a) ∀ y ≥ 0 : 〈y, h(x*)〉 ≤ 〈y*, h(x*)〉 (2.6) Dễ thấy rằng điều ày chỉ xãy ra khi h( x*) ≤ 0. Tức là b – g(x*) ≤ 0; hay g(x*) ≥ b. Kết hợp với giả thiết x*∈Γ, suy ra x*∈X. b) Do (2.6) đúng với mọi y ≥ 0 nên cũng đúng khi y = 0. Từ (2.6) suy ra 〈y*, h(x*)〉 ≥ 0. Mặt khác, do h(x*) ≤ 0, nên ta cũng có bất đẵng thức ngược lại. Suy ra 〈y*, h(x*)〉 = 0. c) Từ đây và từ (2.5) suy ra ∀x∈Γ : f(x*) ≤ f(x) + 〈y*, h(x)〉 . Đặc biệt khi x∈X, thì h(x) ≤ 0, nên 〈y*, h(x)〉 ≤ 0. Do đó f(x*) ≤ f(x), ∀x∈X. Tức là x* là lời giải của bài toán (1.3).ª Lê Văn Phi, Khoa Toan Thông kê, Trường Đai hoc Kinh tế Tp. Hồ Chí Minh ́ ́ ̣ ̣ 46
Lý thuyêt Qui hoach tuyên tinh ́ ̣ ́ ́ Định lý 2.2 cho biết điều kiện đủ để một vectơ x* là lời giải của bài toán QH lồi cơ bản (1.3). Từ định lý này suy ra, để giải bài toán (1.3) chỉ cần tìm một điểm yên ngựa của hàm Lagrange tương ứng L(x,y). 2.3 Định lý Kuhn- Tucker Đlý 2.3: Giả sử rằng tập X thỏa mãn điều kiện chính qui. Khi đó để cho điểm x* ∈Γ là lời giải của bài toán QH lồi cơ bản (1.3) thì điều kiện cần và đủ là tồn tại điểm y* ≥ 0 để cho cặp (x*, y*) là điểm yên ngựa của hàm Lagrange L(x,y) trên miền Γ× {y∈Rm, y ≥ 0}. Chứng minh: Điều kiện đủ suy từ định lý 2.2 mà không cần có điều kiện chính qui. Ta chứng minh điều kiện cần. Giả sử x* là lời giải của bài toán QH lồi cơ bản (1.3). 1) Xét tâp P = {(z0, z) ∈R (m+1)/ z0 ≤ f(x*), z ≤ 0}. Với x∈Γ, đặt S(x) = {(z0, z) ∈R (m+1)/ z0 ≥ f(x), z ≥ b – g(x)} Và đặt S = xUS(x) . Rõ ràng P, S đều là tập lồi trong R (m+1). ∈Γ 2) Đặt P0 = {(z0, z) ∈R (m+1)/ z0 < f(x*), z < 0}. Khi ấy P0 = intP và do đó P0 cũng là tập lồi. Giả sử P0 ∩ S ≠ ∅. Tức là có thể tìm thấy (z’0, z’) ∈ P0 ∩ S với z’0 < f(x*), z’ < 0 và z’0 ≥ f(x’), z’ ≥ b – g(x’) ứng với ít nhất một x’∈Γ. Như vậy, x’∈ X và f(x’) < f(x*). Điều này trái với giả thiết rằng x* là lời giải của (1.3). 3) Do P, S lồi và intP∩ S = ∅, nên theo định lý tách 3 chương I, sẽ tồi tại một siêu phẳng Hα tách P với S. Tức là tồn tại (u0,u)∈R (m+1), (u0,u) ≠ 0, để cho ∀(z0, z)∈S và ∀(w0, w) ∈P: u0z0 + 〈u, z〉 ≥ u0w0 + 〈u, w〉 , Hay u0 (z0 - w0) + 〈u, z - w〉 ≥ 0. (2.7) Do ∀(z0, z)∈S và ∀(w0, w) ∈P0 thì z0 ≥ f(x) ≥ f(x*) > w0, nên z0–w0 > 0. Từ đây dễ dàng suy ra rằng, để (2.7) đúng ∀(z0, z)∈S và ∀(w0, w) ∈P0 thì u0 ≥ 0. Tương tự, cũng suy ra rằng ui ≥ 0, i = 1,2,…,m (bài tập…). 4) Chọn x∈Γ tùy ý, z0 = f(x), z = b – g(x) và w0 = f(x*), w = 0. Từ (2.7) suy ra: ∀ x∈Γ: u0 f(x) + 〈u, b – g(x)〉 ≥ u0 f(x*). (2.8) Nếu u0 = 0, ta có ∀ x∈Γ: 〈u, b – g(x)〉 ≥ 0. (2.9) Do u ≥ 0, b – g(x) ≤ 0, ∀x∈X, nên trên X: 〈u, b – g(x)〉 = 0. Hay m ∑ u i (bi − g i (x)) = 0 , ∀ x∈X i =1 Hay ∀i = 1,2,….,m: ui(bi – gi (x)) = 0, ∀ x∈X. (2.10) Lê Văn Phi, Khoa Toan Thông kê, Trường Đai hoc Kinh tế Tp. Hồ Chí Minh ́ ́ ̣ ̣ 47
Lý thuyêt Qui hoach tuyên tinh ́ ̣ ́ ́ Vì (u0,u) ≠ 0, nên để (2.10) thỏa mãn phải tồn tại ít nhất một u i’> 0 và do đó ứng với i’ như vậy ∀ x∈X: (bi’ – gi’(x)) = 0. Điều này trái với giả thiết rằng X phải thỏa mãn điều kiện chính qui. Vậy u0 > 0. 5) Đặt y* = (1/ u0)u ≥ 0. Chia hai vế ở (2.8) cho u0 > 0, ta có bất đẵng thức ∀x∈Γ: f(x) + 〈y*, b – g(x)〉 ≥ f(x*). (2.11) Đặc biệt khi x = x* thì từ đây suy ra 〈y*, b – g(x*)〉 ≥ 0. Nhưng, do x*∈X, nên (b – g(x*)) ≤ 0 và ta có bất đẵng thức ngược lại. Suy ra 〈y*, b–g(x*)〉 = 0. Do đó bất đẵng thức (2.11) tương với L(x,y*) ≥ L(x*,y*) (2.12) Mặt khác, do ∀y≥ 0, thì f(x*) ≥ f(x*) + 〈y, b – g(x*)〉 Từ đây cũng suy ra L(x*,y*) ≥ L(x*,y) (2.13) Kết hợp (2.12) với (2.13), cặp (x*,y*) là điểm yên ngựa của L(x,y) trên miền Γ× {y/ y ≥ 0}.ª Chú ý: Khi gi(x) là những hàm tuyến tính thì có thể bỏ qua điều kiện chính qui (xem phần 2.5). Nhưng khi gi(x) là phi tuyến thì điều kiện chính qui là cần thiết. Có thể thấy rõ điều này thông qua phản ví dụ sau đây: Cho n =1, f(x) = -x, g1(x) = g(x) = -x2; b1 = b = 0; Γ = {x / x ≥ 0} ⊆ R1 Bài toán qui hoạch lồi có dạng min{-x / x∈X} với X = {x∈R / -x2 ≥ 0, x ≥ 0} = {0} Tập X như vậy không thỏa mãn điều kiện chính qui. Lời giải của bài toán này rõ ràng là x* = 0 và fmin = f(x*) = 0. Hàm Lagrange tương ứng có dạng: L(x,y) = -x + 1 yx2 xác định trên miền x ≥ 0, y ≥ 0. Do đó max min (-x + yx ) = max ( − 2 ) y≥0 x ≥0 y≥0 4y không tồn tại. Vì vậy hàm L(x,y) không có điểm yên ngựa. 2.4. Định lý Kuhn – Tucker cho trường hợp f(x), gi(x) là những hàm khả vi và Γ = R + n Cho Γ = R + và f(x), gi(x) là những hàm khả vi trên Γ, i = 1,2,…,m; tức n là tồn tại các gradient f’(x) và gi’(x), i = 1,2,…,m. Đlí 2.4: Để cho cặp (x*, y*) là điểm yên ngựa của hàm Lagrange L(x,y) trên miền {x/ x ≥ 0}× {y/ y ≥ 0} thì điều kiện cần và đủ là chúng thỏa mãn hệ bất đẵng thức sau đây (gọi là hệ bất đẵng thức Kuhn-Tucker): Lê Văn Phi, Khoa Toan Thông kê, Trường Đai hoc Kinh tế Tp. Hồ Chí Minh ́ ́ ̣ ̣ 48
Lý thuyêt Qui hoach tuyên tinh ́ ̣ ́ ́  ∂L*  ∂L*  ∂x ≥ 0  ∂y ≥ 0  j  i  * ∂L*   * ∂L*  j = 1,2,…,n:  x j . = 0 ; (2.14) i = 1,2,…,m:  yi . = 0 , (2.15)  ∂x j  ∂yi  x* ≥ 0  y* ≥ 0  j  i     ∂L* ∂L(x*, y*) ∂L* ∂L(x*, y*) Trong đó = ; j = 1, 2,..., n và = ;i = 1, 2,..., m ∂x j ∂x j ∂yi ∂yi Chứng minh: a) Điều kiện cần: Giả sử (x*,y*) là điểm yên ngựa của hàm Lagrange L(x,y) với x ≥ 0, y ≥ 0; tức là L(x*,y) ≤ L(x*,y*) ≤ L(x,y*), ∀ x≥ 0,∀y≥ 0. Đặt x(j) = (x*1,…, x*j-1, xj, x*j+1,…,x*n), 1≤ j ≤ n. Khi đó hàm % L(x j ) = L(x(j),y*) là hàm một biến lồi xác định trong khoảng [0, ∞), có cực tiểu tại x*j. Khi đó có hai trường hợp xãy ra: % dL(x *j ) i) x*j = 0; tức là % L(x j ) tăng trên [0, ∞), hay ≥ 0 và hiễn dx j % * nhiên điều kiện x*j.(∂L(x*,y*)/∂xj) = x*j.( dL(x ) / dx ) = 0 j j ii) % Khi x*j > 0. Do x*j là điểm trong nên dL(x *j ) / dx j = 0. Do đó (∂L(x*,y*)/∂xj) = 0. ∂L* Mặt khác, vì = bi − g i (x*); i = 1, 2,..., m , nên chứng minh tương tự ∂yi như trên ta cũng thấy rằng để cho hàm tuyến tính L (yi) = L(x*, y(i)) đạt cực đại tại y = y* thì điều kiện cần thiết là ∂L* = bi − g i (x*) ≤ 0; ∀i và hoặc là yi* = 0 hoặc là, khi yi* > 0 thì L (yi ∂yi ) = const. Do đó (d L (yi*)/dyi) = ∂L(x*,y*)/∂yi = 0. Trong đó y(i) = (y1*, …, y i-1*, yi, yj+1*,…, y n*). b) Điều kiện đủ: Do f(x) lồi, gi(x) lõm trên Γ = {x/ x ≥ 0}, nên L(x, y) lồi theo x. Đặt ϕ(x) = L(x, y*). Khi ấy ϕ(x) lồi và khả vi. Theo Đlí 6.2, ∂φ(x*) ∂L(x*, y*) Chương I, 〈ϕ’(x*), x – x*〉 ≤ ϕ(x) - ϕ(x*). Do = ∂x j ∂x j Lê Văn Phi, Khoa Toan Thông kê, Trường Đai hoc Kinh tế Tp. Hồ Chí Minh ́ ́ ̣ ̣ 49
Lý thuyêt Qui hoach tuyên tinh ́ ̣ ́ ́ nên theo (2.14) thì n ∂L(x*, y*) 0≤∑ .(x j − x *j ) ≤ L(x, y*) − L(x*, y*), ∀x ≥ 0 . Suy ra: j =1 ∂x j ∀ x ≥ 0: L(x, y*) ≥ L(x*, y*) (2.16) Mặt khác, từ (2.15) suy ra: ∀y ≥ 0: L(x*, y) = f(x*) +〈y, b – g(x*)〉 ≤ f(x*) = f(x*) +〈y*, b –g(x*)〉 = L(x*, y*) Kết hợp với (2.16), (x*,y*) là điểm yên ngựa của hàm Lagrange trên miền {x/ x ≥ 0)}× {y/ y ≥ 0)}.ª Các bất đẵng thức (2.14) – (2.15) gọi là các Bất đẵng thức Kuhn- Tucker, được các tác giả công bố lần đầu tiên năm 1951. Từ đây thấy rằng, việc giải bài toán QH lồi cơ bản trong trường hợp f(x), g i(x) khả vi trên miền {x/ x ≥ 0)} trở thành việc giải các bất đẵng thức Kuhn-Tucker. Cũng từ chứng minh ở Đlí 2.4 dễ thấy rằng, nếu Γ = Rn, các bất đẵng thức Kuhn-Tucker sẽ có dạng:  ∂L*  ∂y ≥ 0  i ∂L *  * ∂L* = 0, j = 1, 2,..., n; và  yi .  = 0 , i = 1, 2,…,m. ∂x j  ∂yi  y* ≥ 0  i   2.5 Dạng hình học của Định lý Kuhn-Tucker Để trình bày dạng hình học của định lý Kuhn-Tucker, ứng với x∈X bất kỳ trước hết ta ký hiệu: I(x) = {i / bi = gi(x)} ⊆ {1, 2, …, m} và J(x) = {j / xj = 0}⊆ {1, 2, …, n}; gradgi(x) = g’i(x); gradf(x) = f’(x). Khi ấy I(x), J(x) là tập hợp các mặt biên của X chứa x; -gi(x), i = 1, 2, …, m,(tương ứng -f(x) gọi là đối gradien của gi (x) (tương ứng f(x)). -g’i(x*) x* gi(x*) = bi ̀ Hinh 2.3 Lê Văn Phi, Khoa Toan Thông kê, Trường Đai hoc Kinh tế Tp. Hồ Chí Minh ́ ́ ̣ ̣ 50
Lý thuyêt Qui hoach tuyên tinh ́ ̣ ́ ́ Đlí 2.5: Trong trường hợp tập X thỏa mãn điều kiện chính qui và giả sử f(x), g(x) khả vi trên miền Γ ={x/ x ≥ 0)} thì điều kiện cần và đủ để x*∈X* là lời giải của bài toán QH lồi (1.3) là tại x = x* đối gradien của f(x) phải nằm trong nón lồi sinh bởi các đối gradien của các mặt biên của X chứa x*. Chứng minh: Nếu X thỏa mãn điều kiện chính qui thì từ các định lý 2.2, 2.3 và 2.4 suy ra các bất đẵng thức Kuhn-Tucker là điều kiện cần và đủ để x* là lời giải của bài toán QH lồi (1.3). Để chứng minh Đlí 2.5 chỉ cần chứng tỏ rằng nếu (x*, y*) thỏa mãn các bất đẵng thức Kuhn-Tucker thì tại x = x* đối gradien của f(x) sẽ nằm trong nón lồi sinh bởi các đối gradien của gi(x), - g’i(x), i∈I(x*) và pj(x) = 〈ej, x〉 = xj, - ej, j∈J(x*), với ej = (0,…, 0, 1, 0,…,0) là vectơ đơn vị thứ j và ngược lại. Giả sử (x*, y*) thỏa mãn các bất Kuhn-Tucker. Ta xét 2 trường hợp: a) I(x*)∪ J(x*) ≠ ∅. Khi ấy x* nằm trên mặt biên của X. Theo (2.15) thì ∂L * ∂f * m * ∂g i * ∂L * ∀j = 1, 2,..., n : v*j = = + ∑ yi ≥ 0; x *j = x *j .v*j = 0 ∂x j ∂x j i =1 ∂x j ∂x j ∂f * m * ∂g* Suy ra − = ∑ yi ( − i ) + (−1)v*j , j = 1,2,…,n (2.17) ∂x j i =1 ∂x j Tuy nhiên, với j∉J(x*) thì xj* > 0, nên vj* = 0. Do đó (2.17) trở thành ∂f * m * ∂g* − = ∑ yi ( − i ); j ∉ J(x*) (2.18) ∂x j i =1 ∂x j Kết hợp (2.18) và (2.17) có thể viết lại thành: ∂f * m * ∂g* − = ∑ yi ( − i ) + ∑ (−1)v* ; j = 1, 2,..., n (2.19) ∂x j i =1 ∂x j k∈J ( x *) k Mặt khác, khi i∉I(x*), tức là gi(x*) > bi thì theo (2.15), yi* = 0. Khi đó (2.19) trở thành ∂f * ∂g* (− ) = ∑ y* (− i ) + ∑ ( −1)v* ; j = 1, 2,..., n ∂x j ∂x j k∈J ( x*) i k i∈I( x *) Tức là [−f '(x*)] = ∑ y* [ −g i '(x*)] + ∑ ( −e j )v*j i (2.20) i∈I ( x*) j∈J ( x*) Kết hợp với điều kiện yi* ≥ 0, vj* ≥ 0, i = 1,2,…, m; j = 1,2,….,n, (2.20) chứng tỏ [-f’(x*)] nằm trong nón lồi sinh bởi các [-gi’(x*)], i∈I(x*) và (-ej), j ∈I(x*), tức là các mặt biên chứa x*. b) Khi I(x*)∪J(x*) = ∅, thì x* ∈intX, và nếu các bất dẵng thức ở (2.15), (2.16) thỏa mãn thì vj* = 0 và yi* = 0, j =1,2,…,n; i =1,2,…, m. Do f(x) khả vi và nhận cực tiểu tại x* nên diều kiện cần thiết là (∂f(x*)/∂xj) = 0; tức là (-∂f(x*)/∂xj) = 0, j =1,2….,n. Hay [-f’(x*)] = 0. Như vậy (2.20) cũng thỏa mãn. Lê Văn Phi, Khoa Toan Thông kê, Trường Đai hoc Kinh tế Tp. Hồ Chí Minh ́ ́ ̣ ̣ 51
Lý thuyêt Qui hoach tuyên tinh ́ ̣ ́ ́ Chứng minh điều kiện đủ: Giả sử có (2.20), tức là [-f’(x*)] nằm trong nón lồi sinh bởi các đối gradien của các mặt biên của X chứa x*. Chỉ cần thêm vj* = 0, j∉J(x*) và yi* = 0, i∉I(x*) ta có m n [−f '(x*)] = ∑ y* [−g i '(x*)] + ∑ ( −e j )v*j i i =1 j =1 ∂f * m * ∂g * Tức là − = ∑ yi (− ) + (−1)v*j ; i j = 1, 2,..., n ∂x j i =1 ∂x j Hay ∂L * ∂f * m * ∂g* v*j = = + ∑ yi ( i ) ≥ 0 ; j = 1, 2,..., n ∂x j ∂x j i =1 ∂x j Vậy vj* = (∂L*/∂xj) ≥ 0 và do j ∈J(x*) thì xj* = 0, nên xj*.v j* = 0 ; j = 1,2,…,n Mặt khác, do x*∈X, nên (∂L*/∂yi) = bi – gi (x*) ≤ 0, i = 1,2,…, m và khi i∈I(x*) thì bi – gi (x*) = 0, nên yi*.(∂L*/∂yi) = 0, i = 1,2,…,m. Tức là (x*,y*) thỏa mãn các bất đẵng thức Kuhn-Tucker. Do đó cặp (x*,y*) là điểm yên ngựa của hàm Lagrange L(x,y). Theo định ly 2.3 thì x* là lời giải của bài toán QH lồi (1.3).ª 2.6 Bài toán qui hoạch lồi với các ràng buộc tuyến tính Bài toán Qui hoạch toàn phương n Xét bài toán QH lồi (1.3) trong đó gi (x) = ∑ a ij x j j =1 , i = 1,2,…, m. j =1,2,...,n Trong đó A = ((a ij ))i =1,2,..,m là ma trận thực m hàng, n cột cho trước. Khi đó bài toán QH lồi (1.3) trở thành bài toán: Tìm x* sao cho f (x*) = min f (x) x∈X { n với X = x ∈ R / ∑ a ij x , ≥ bi ,i = 1, 2,..., m; x j ≥ 0, j = 1, 2,..., n n j =1 } (2.21) Ở dạng ma trận X được viết thành: X = {x∈Rn/ Ax ≥ b} (2.22) Dễ thấy rằng các ràng buộc xác định X có dạng tuyến tính (các hàm gi(x) là các hàm tuyến tính, i = 1,2,…,m) nên bài toán (2.21) gọi là bài toán QH lồi với các ràng buộc tyến tính. Lê Văn Phi, Khoa Toan Thông kê, Trường Đai hoc Kinh tế Tp. Hồ Chí Minh ́ ́ ̣ ̣ 52
Lý thuyêt Qui hoach tuyên tinh ́ ̣ ́ ́ Đặc biệt khi hàm f(x) có dạng toàn phương, tức là có dạng f(x) = 〈p, x〉 + 〈x, Qx〉 ; (2.23) trong đó Q là ma trận vuông đối xứng cấp n, xác định không âm2. Bài toán (2.21) được gọi là bài toán Qui hoạch toàn phương. { n } Với x*∈X bất kỳ, đặt I(x*) = i / ∑ a ij x j = bi ; J(x) = {j / x*j = 0}; tức j =1 * là I(x*), J(x*) là tập hợp các mặt biên của X chứa x*. Nếu I(x*)∪J(x*) = ∅ thì x* là điểm trong của X, nên mọi hướng s đều chấp nhận được tại x*. Giả sử I(x*)∪J(x*) ≠ ∅. Khi ấy bạn đọc sẽ chứng minh trong bài tập rằng hướng s là chấp nhận được tại x* khi và chỉ khi  ∑ a s ≥ 0, i ∈ I(x*) n  j=1 ij j  (2.24)   s j ≥ 0; j ∈ J(x*) Hàm Lagrange ứng với bài toán (2.21) có dạng L(x,y) = f(x) + 〈y, b - Ax〉 m n Hay L(x, y) = f (x) + ∑ yi (bi − ∑ a ij x j ) (2.25) i =1 j =1 Ứng với bài toán (2.21) định lý Kuhn-Tucker vẫn đúng mà không cần có điều kiện chính qui. Đlí 2.6: Giả sử f(x) khả vi trên X, xác định theo (2.21) hoặc (2.22). Khi đó, để cho x*∈X là lời giải của bài toán QH lồi (2.21) thì điều kiện ắt có và đủ là tồn tại y* ≥ 0, để cho cặp (x*, y*) là điểm yên ngựa của hàm Lagrange (2.25). Chứng minh: Do bài toán (2.21) chỉ là trường hợp đặc biệt của bài toán (1.3), nên điều kiện đủ đã được chứng minh ở định lý 2.2. Ta chứng minh điều kiện cần như sau: Giả sử x* là lời giải của bài toán (2.21), tức là điểm cực tiểu của hàm lồi f(x) trên X. Khi ấy theo định lý 4.3 chương I: (∂f(x*)/∂s) ≥ 0, ∀s là hướng chấp nhận được tại x*. Do f khả vi tại x* nên //s//.(∂f(x*)/∂s) = 〈f’(x*), s〉 . Do đó với mọi hướng s chấp nhận được tại x* 〈f’(x*), s〉 ≥ 0 (2.26) 2 Q là ma trận vuông, đối xứng cấp n gọi là xác định không âm khi ∀x∈Rn: 〈x, Qx〉 ≥ 0. Tương tự, Q được gọi là xác định dương, nếu ∀x∈ Rn, x≠ 0:〈x, Qx〉 > 0; Q là xác định âm, nếu ∀x∈ Rn, x≠ 0:〈x, Qx〉 < 0. Lê Văn Phi, Khoa Toan Thông kê, Trường Đai hoc Kinh tế Tp. Hồ Chí Minh ́ ́ ̣ ̣ 53
Lý thuyêt Qui hoach tuyên tinh ́ ̣ ́ ́ Tuy nhiên, nếu s là chấp nhận được tại x* ta có (2.24). Không giảm tính tổng quát, giả sử I(x*) = {1, 2, …, k}, k≤ m; J(x*) ={1, 2, …, l}, l ≤ m. Tức là 〈Ai., x〉 = bi, i =1,2,…, k; 〈ej, x〉 = 0, j = 1, 2, …, l . Trong đó A i. là các vectơ hàng của A. Đặt  A1.   a11 ... a1l a1(l +1) ... a1n   s1         ...   ... ... ... ... ... ...   ...   A k.   a k1 ... a kl a k ( l +1) ... a kn   sk  B =  = ; s= .  e1   1 ... 0 0 ... 0   s k +1   ...   ... ... ... ... ... ...   ...    e   0     s    l   ... 1 0 ... 0    n  Khi đó (2.24) trở thành Bs ≥ 0 (2.27) Như vậy, ∀s thỏa mãn (2.27) luôn luôn xãy ra (2.26). Theo định lí Farkas sẽ tồn tại các u ≥ 0, để cho f’(x*) = BTu; tức là f’(x*) nằm trong nón lồi sinh bởi các Ai., i∈I(x*) và ej, j∈J(x*). Đây là các gradien của các mặt biên của X chứa x*. Từ định lý 2.5 suy ra điều phải chứng minh. ª Điều kiện Kuhn-Tucker cho bài toán Qui hoạch lồi với ràng buộc tuyến tính (bài toán (2.21)): Kết hợp các định lý 2.4 và 2.6, ta có điều kiện cần và đủ để cho x*∈Rn là lời giải tối ưu của bài toán (2.21) là tồn tại các y* ∈Rm, v*∈Rn, u*∈Rm thỏa mãn các bất đẵng thức và đẵng thức sau đây, gọi là các bất đẵng thức Kuhn-Tucker (X không cần thiết phải thỏa mãn điều kiện chính qui): Lê Văn Phi, Khoa Toan Thông kê, Trường Đai hoc Kinh tế Tp. Hồ Chí Minh ́ ́ ̣ ̣ 54
Lý thuyêt Qui hoach tuyên tinh ́ ̣ ́ ́  ∂f (x*) m  ∂x − ∑ a ij yi − v j = 0 * * i =1  j   x *j .v*j = 0 j = 1, 2,..., n ;  x j ≥ 0, v j ≥ 0 * *    b − ∑ a x * + u * = 0 n  i j =1 ij j i   yi .u i = 0 * * i = 1, 2,..., m  y* ≥ 0, u * ≥ 0  i i  Đặc biệt khi f(x) có dạng toàn phương (2.23) thì ∂f (x) n = p j + ∑ q jk x k ; j = 1, 2,..., n ∂x j k =1 Do vậy điều kiện Kuhn-Tucker ứng với bài toán Qui hoạch toàn phương dưới dạng ma trận như sau: P + Qx - ATy – v = 0 (2.28) Ax – b – u = 0 〈x, v〉 + 〈y, u〉 =0 x ≥ 0; v ≥ 0; y ≥ 0; u ≥ 0 Khi ấy việc giải bài toán Qui hoạch toàn phương trở thành việc tìm lời giải của hệ phương trình và bất phương trình phi tuyến Kuhn – Tucker (2.28). Để biết được các phương pháp hữu hiệu giải hệ phương trình và bất phương trình (2.28) đề nghị bạn đọc tham khảo các tài liệu viết về qui hoạch phi tuyến. ./. Lê Văn Phi, Khoa Toan Thông kê, Trường Đai hoc Kinh tế Tp. Hồ Chí Minh ́ ́ ̣ ̣ 55