Mục lục Lời mở đầu Bảng kí hiệu viết tắt Chương Kiến thức chuẩn bị 1.1 Định nghĩa kí hiệu 1.2 Tập lồi, hàm lồi 1.3 Quy hoạch toàn phương 11 1.3.1 Quy hoạch lồi 11 1.3.2 Quy hoạch tuyến tính 13 1.3.3 Quy hoạch toàn phương 14 Chương Các định lý tồn nghiệm toán quy hoạch toàn phương 20 2.1 Định lý Frank-Wolfe 20 2.2 Định lý Eaves 28 2.3 Các điều kiện tối ưu bậc bậc hai 38 Chương Một số ứng dụng khác định lý tồn nghiệm 42 3.1 Bất đẳng thức biến phân 42 3.2 Tính liên tục ánh xạ nghiệm quy hoạch toàn phương phụ thuộc tham số 49 Kết luận 53 Tài liệu tham khảo 54 Lời mở đầu Nhiều kiện sống dẫn loài người đễn việc phải lựa chọn "phương án" cho hành động mình, từ "phương án" đó, người ta có mong muốn tự nhiên chọn lấy "phương án" tối ưu Dần dần, người ta biết diễn đạt công việc mô hình toán học, cụ thể toán cực trị Trong lĩnh vực khác kinh tế, quản lí đặt yêu cầu nghiên cứu "lí thuyết tối ưu" Lý thuyết toán học tối ưu hình thành phát triển mạnh mẽ lĩnh vực khoa học từ kỉ 20 Có nhiều lĩnh vực với tên gọi khác lại gần lí thuyết như: tối ưu hóa, quy hoạch toán học, phép tính biến phân Bài toán quy hoạch toán học hiểu toán tìm cực trị hàm (hàm số hay hàm vectơ đa trị) điều kiện định Để đơn giản ta xét quy hoạch toán học có dạng (P ) min{f (x) : x ∈ ∆}, ∆ ⊂ X tập ràng buộc, X không gian đó, f : ∆ → R hàm mục tiêu Mỗi điểm x ∈ ∆ gọi phương án chấp nhận (lời giải chấp nhận được) toán (P ) Bài toán hiểu tìm điểm x∗ ∈ ∆ cho f (x∗ ) ≤ f (x) với x ∈ ∆ Nghĩa ta muốn tìm phương án tối ưu (xem [2, tr 38]) Bài toán có nhiều ứng dụng lĩnh vực khác Chẳng hạn, kinh tế toán xác định phương án sản xuất cho chi phí thấp nhất, hay toán đóng gói bố trí mặt Có nhiều cách phân loại quy hoạch toán học (xem [1, tr 3]) Khi X không gian hữu hạn chiều: quy hoạch tuyến tính; quy hoạch phi tuyến (quy hoạch lồi, không lồi; trơn, không trơn ) Trong luận văn này, tác giả tập trung nghiên cứu lớp quy hoạch phi tuyến quy hoạch toàn phương Khi đó, f hàm toàn phương ∆ tập lồi đa diện Rn Một vấn đề tự nhiên đặt quy hoạch toán học có hay không phương án tối ưu? Tất nhiên với quy hoạch toàn phương có câu hỏi tương tự Hai định lý: định lý Frank - Wolfe định lý Eaves giúp trả lời câu hỏi Đây phần nghiên cứu trọng tâm luận văn Luận văn chia làm chương với phần mở đầu, kết luận danh mục tài liệu tham khảo Chương 1: Trình bày khái niệm quy hoạch toán học, định nghĩa, kí hiệu dùng cho chương sau Chương 2: Trình bày, chứng minh định lý Frank - Wolfe định lý Eaves, đưa hệ số kết luận tồn nghiệm địa phương quy hoạch toàn phương Chương 3: Trình bày số ứng dụng khác định lý tồn nghiệm chứng minh tồn nghiệm toán bất đẳng thức biến phân xét tính liên tục quy hoạch toàn phương phụ thuộc tham số Luận văn hoàn thành hướng dẫn khoa học PGS TS Nguyễn Năng Tâm, trường Đại học Sư phạm Hà Nội Tác giả xin bày tỏ lòng kính trọng lòng biết ơn sâu sắc đến thầy giúp đỡ khoa học điều kiện thuận lợi mà thầy dành cho tác giả Nhân dịp này, tác giả gửi lời cảm ơn thầy phản biện, người đọc đóng góp ý kiến cho tác giả để luận văn hoàn thiện hơn, cảm ơn thầy cô giáo trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội tận tình hướng dẫn, giảng dạy suốt thời gian tác giả học tập trường Cuối cùng, tác giả xin cảm ơn gia đình Cơ quan công tác - trường THPT Thuận Thành số - Bắc Ninh, tạo điều kiện cho tác giả học hoàn thành khóa học Hà Nội, tháng năm 2011 Nguyễn Thanh Tâm Bảng kí hiệu viết tắt N tập hợp số nguyên dương R đường thẳng thực Rn+ tập vectơ không âm R = R ∪ {−∞} ∪ {+∞} đường thẳng thực mở rộng Rn không gian Euclid n-chiều Rm×n tập hợp ma trận cỡ m × n x chuẩn vectơ x ∅ tập rỗng AT ma trận chuyển vị A x, y tích vô hướng vectơ x vectơ y B(x, δ) hình cầu mở tâm x, bán kính δ B(x, δ) hình cầu đóng tâm x, bán kính δ Ω bao đóng Ω extr∆ tập hợp đỉnh ∆ 0+ ∆ nón lùi xa ∆ T∆ (x) nón tiếp xúc ∆ x C - hàm tập hàm f : Rn → R khả vi liên tục theo nghĩa Fréchet C - hàm tập hàm f : Rn → R khả vi liên tục cấp hai theo nghĩa Fréchet f (x) gradien f x ma trận Hessian f x f (x) Sol(P ) tập nghiệm toán (P ) loc(P ) tập nghiệm địa phương toán (P ) Chương Kiến thức chuẩn bị Chương trình bày số khái niệm quy hoạch toán học nói chung, quy hoạch toàn phương nói riêng 1.1 Định nghĩa kí hiệu Trong thực tế lý thuyết, có nhiều toán mô tả dạng (P ) minf (x) với x ∈ ∆, đó, f : Rn → R hàm cho trước, ∆ ⊂ Rn , tập cho trước (P ) gọi toán tối ưu, hay toán quy hoạch toán học (P ) kí hiệu ngắn gọn sau min{f (x) : x ∈ ∆} Định nghĩa 1.1 Ta gọi (P ) toán quy hoạch toán học, f hàm mục tiêu, ∆ tập ràng buộc (hay miền chấp nhận (P )) Các phần tử ∆ gọi vectơ chấp nhận (P ) Nếu ∆ = Rn ta nói (P ) toán ràng buộc, ngược lại, (P ) toán có ràng buộc Định nghĩa 1.2 Một vectơ chấp nhận x ∈ ∆ gọi nghiệm (toàn cục) (P ) f (x) = +∞ f (x) ≥ f (x) với x ∈ ∆ Ta nói x ∈ ∆ nghiệm địa phương (P ) f (x) = +∞ tồn lân cận U x cho f (x) ≥ f (x) với x ∈ ∆ ∩ U (1.1) Tập nghiệm (P ) kí hiệu Sol(P ), tập nghiệm địa phương kí hiệu loc(P ) Hai quy hoạch tương đương tập nghiệm chúng trùng Định nghĩa 1.3 Giá trị tối ưu υ(P ) (P ) xác định υ(P ) = inf {f (x) : x ∈ ∆} (1.2) Nếu ∆ = ∅ quy ước υ(P ) = +∞ Chú ý 1.4 Dễ thấy, Sol(P ) ⊂ loc(P ), Sol(P ) = {x ∈ ∆ : f (x) = +∞, f (x) = υ(P )} Chú ý 1.5 Có thể xảy trường hợp loc(P )\Sol(P ) = ∅ Chẳng hạn, chọn ∆ = [−1, +∞) f (x) = 4x3 − 6x2 x = nghiệm địa phương, nghiệm toàn cục (P ) Chú ý 1.6 Trong nhiều trường hợp, ta gặp toán giá trị lớn sau (P1 ) max f (x) với x ∈ ∆ Một điểm x gọi nghiệm (toàn cục) (P1 ) f (x) = −∞ f (x) ≤ f (x) với x ∈ ∆ Ta nói x nghiệm địa phương (P1 ) f (x) = −∞ tồn lân cận U x cho f (x) ≤ f (x) với x ∈ ∆ ∩ U Rõ ràng x nghiệm (tương ứng nghiệm địa phương) (P1 ) x nghiệm (tương ứng nghiệm địa phương) toán giá trị nhỏ sau {−f (x)} với x ∈ ∆ Do vậy, toán giá trị lớn dạng (P1 ) đưa toán giá trị nhỏ dạng (P ) Chú ý 1.7 (Xem [3, Remark 1.4]) Ngay trường hợp υ(P ) số thực hữu hạn, xảy khả Sol(P ) = ∅ Chẳng hạn, ∆ = [1, +∞) ⊂ R    với x = |x| f (x) =  +∞ với x = υ(P ) = Sol(P ) = ∅ 1.2 Tập lồi, hàm lồi Định nghĩa 1.8 Ta gọi ∆ ⊂ Rn tập lồi tx + (1 − t)y ∈ ∆ với x ∈ ∆, y ∈ ∆ t ∈ (0, 1) (1.3) Định nghĩa 1.9 Một hàm f : Rn → R gọi lồi đồ thị epif = {(x, α) ∈ Rn × R : f (x) ≤ α}, (1.4) tập lồi không gian tích Rn × R Một hàm f gọi hàm lồi thường f (x) < +∞ với x ∈ Rn f (x) > −∞ với x ∈ Rn Một hàm f gọi lõm hàm −f cho công thức: (−f )(x) = −f (x) lồi Hàm f gọi afin f vừa lồi, vừa lõm Chú ý hàm f : Rn → R ∪ {+∞} gọi lồi f (tx + (1 − t)y) ≤ tf (x) + (1 − t)f (y), ∀x, y ∈ Rn , ∀t ∈ (0, 1) (1.5) Thật vậy, theo định nghĩa f lồi tập đồ thị lồi, nghĩa t(x, α) + (1 − t)(y, β) ∈ epif, với t ∈ (0, 1) x, y ∈ Rn , α, β ∈ R thỏa mãn α ≥ f (x), β ≥ f (y) Điều tương đương với (1.5) Tổng quát hơn, hàm f : Rn → R ∪ {+∞} lồi f (λ1 x1 + +λk xk ) ≤ λ1 f (x1 )+ +λk f (xk ) (Bất đẳng thức Jensen), với x1 , , xk ∈ Rn λ1 ≥ 0, , λk ≥ 0, λ1 + + λk = (Xem [6,Theorem 4.3]) Định nghĩa 1.10 Cho hàm f : Rn −→ R, tập dom(f ) := {x ∈ Rn : f (x) < +∞}, (1.6) gọi miền hữu dụng f Với điểm x ∈ domf vectơ υ ∈ Rn , giới hạn f (x, υ) := lim t↓0 f (x + tυ) − f (x) t 10 (1.7) cặp vectơ (λ, µ) = (λ1 , , λm , µ1 , , µs ) ∈ Rm × Rs cho (i) hệ    Qx − AT λ − C T µ + c = 0,    Ax − b ≥ 0, Cx = d, λ ≥ 0,     λT (Ax − b) = (2.33) thỏa mãn, (ii) υ ∈ Rn \{0} thỏa mãn AI1 υ = 0, AI2 υ ≥ 0, Cυ = 0, I1 = {i : Ai x = bi , λi > 0}, I2 = {i : Ai x = bi , λi = 0}, (2.34) υ T Qυ ≥ Ta xét toán (2.27) tập ∆ = {x ∈ Rn : Ax ≥ b, Cx = d} Kí hiệu hàm mục tiêu toán (2.27) f (x), kí hiệu ( f (x))⊥ không gian tuyến tính Rn trực giao với ( f (x))⊥ = {υ ∈ Rn : f (x), nghĩa f (x), υ = 0} Chú ý rằng, định lý phát biểu dạng tương đương định lý sau Định lí 2.19 Điều kiện cần đủ để điểm x ∈ Rn nghiệm địa phương toán (2.27) hai điều kiện sau thỏa mãn: (i) f (x), υ = (Qx + c)T υ ≥ với υ ∈ T∆ (x) = {υ ∈ Rn : AI0 υ ≥ 0, Cυ = 0}, I0 = {i : Ai x = bi }; (ii) υ T Qυ = với T∆ (x) ∩ Rn : f (x)⊥ , f (x), υ = 0} 40 f (x)⊥ = {υ ∈ Chương trình bày hai định lý tồn nghiệm quy hoạch toàn phương định lý Frank - Wolfe định lý Eaves Ở đưa chứng minh chi tiết hai định lý với hệ chúng, đồng thời minh họa ứng dụng định lý để kiểm tra tồn nghiệm số quy hoạch toàn phương Phần cuối chương giới thiệu (không chứng minh) số định lý tồn nghiệm địa phương quy hoạch toàn phương 41 Chương Một số ứng dụng khác định lý tồn nghiệm Chương nghiên cứu vài ứng dụng khác định lý Frank-Wolfe định lý Eaves 3.1 Bất đẳng thức biến phân Xét f : Rn → R C - hàm ∆ ⊂ Rn tập lồi, đóng, khác rỗng Mệnh đề 3.1 Nếu x0 nghiệm địa phương toán tối ưu min{f (x) : x ∈ ∆} 42 (3.1) f (x0 ), y − x0 ≥ ∀y ∈ ∆ (3.2) Đặt  ∂f (x)  ∂x1   f (x) =    ∂f (x)        (3.3) Φ(x0 ), y − x0 ≥ ∀y ∈ ∆ (3.4) Φ(x) = ∂xn Khi đó, (3.2) viết lại sau Định nghĩa 3.2 Cho ∆ ∈ Rn tập lồi, đóng khác rỗng, Φ : ∆ → Rn toán tử cho trước Khi đó, toán tìm x0 ∈ ∆ thỏa mãn (3.4) gọi toán bất đẳng thức biến phân, hay ngắn gọn bất đẳng thức biến phân Nó kí hiệu V I(Φ, ∆) Tập hợp tất x0 thỏa mãn (3.4) gọi tập nghiệm V I(Φ, ∆), kí hiệu Sol(V I(Φ, ∆)) Định nghĩa 3.3 Cho M ∈ Rn×n , q ∈ Rn ∆ ⊂ Rn tập lồi đa diện Bài toán bất đẳng thức biến phân Tìm x0 ∈ ∆ cho M x0 + q, y − x0 ≥ ∀y ∈ ∆ (3.5) gọi toán bất đẳng thức biến phân afin kí hiệu AV I(M, q, ∆) Tập nghiệm kí hiệu Sol(AV I(M, q, ∆)) Xét toán (3.5) Vì ∆ tập lồi đa diện nên biểu diễn dạng ∆ = {x ∈ Rn : Ax ≥ b}, m, n ∈ N, A ∈ Rm×n b ∈ Rm 43 (3.6) Ta kiểm tra tồn nghiệm toán thông qua định lý quan trọng trình bày Việc chứng minh định lý ứng dụng khác định lý Frank-Wolfe Định lí 3.4 (Xem [7, p 432]) Nếu hai điều kiện sau thỏa mãn (i) tồn x0 ∈ ∆ cho (M x0 + q)T υ ≥ với υ ∈ 0+ ∆ (trong đó, 0+ ∆ = δ(A) = {υ ∈ Rn : Aυ ≥ 0}); (ii) (y − x)T M (y − x) ≥ với x ∈ ∆ y ∈ ∆; tập nghiệm Sol(AV I(M, q, ∆)) khác rỗng Đặt       x A b ˜ = z =   ∈ Rn+m : (M − AT )z = −q,  z ≥   ∆ λ E   x = z =   ∈ Rn+m : M x − AT λ + q = 0, Ax ≥ b, λ ≥ , λ đó, E ma trận đơn vị Rm×m Đặt  T q ˜ +M ˜ T )z +   z, f (z) = z T (M −b  M ˜ = M A   −A x  ∈ R(n+m)×(n+m) , z =   ∈ Rn+m λ T  Để chứng minh định lý (3.4) ta xét toán phụ sau ˜ min{f (z) : z ∈ ∆} (3.7) Với cách đặt nêu trên, dễ thấy (3.7) quy hoạch toàn phương Ta chứng minh định lý dựa vào bổ đề trình 44 bày Việc chứng minh bổ cho thấy ứng dụng khác Định lý Eaves Định lý Frank - Wolfe ˜ khác rỗng tồn x0 ∈ ∆ cho Bổ đề 3.5 Tập ∆ (M x0 + q)T υ ≥ với υ ∈ 0+ ∆ (Trong 0+ ∆ = δ(A) = {υ ∈ Rn : Aυ ≥ 0}) ˜ = ∅ tồn Chứng minh Điều kiện cần: Nếu ∆   x0 z0 =   ∈ Rn+m λ0 cho M x0 − AT λ0 + q = 0, Ax0 ≥ b, λ0 ≥ (3.8) Xét υ ∈ 0+ ∆, Aυ ≥ Từ (3.8) ta có = (M x0 − AT λ0 + q)T υ = (M x0 + q)T υ − λ0 T Aυ Do (M x0 + q)T υ = λ0 T Aυ ≥ Điều kiện đủ : Giả sử tồn x0 ∈ ∆ cho (M x0 + q)T υ ≥ với υ ∈ 0+ ∆ = δ(A) Xét quy hoạch tuyến tính sau min{cT y : y ∈ ∆}, (3.9) c := M x0 + q Theo giả thiết ∆ = ∅ (M x0 + q)T υ ≥ với υ ∈ Rn , Aυ ≥ Do đó, theo Định lý (2.7), toán (3.9) có nghiệm Theo Định lý (2.18), tồn λ0 ∈ Rm cho − AT λ0 + c = 0, λ0 ≥ (3.10) Mặt khác x0 ∈ ∆ nên Ax0 ≥ b Kết hợp điều với (3.10) suy ˜ Vậy ∆ ˜ = ∅ z0 ∈ ∆ 45 Bổ đề 3.6 Nếu tồn x0 ∈ ∆ cho (M x0 + q)T υ ≥ với υ ∈ 0+ ∆ toán phụ (3.7) có nghiệm ˜ = ∅ Chứng minh Theo Bổ đề (3.5) từ giả thiết bổ đề suy ∆ Với   x ˜ z =   ∈ ∆, λ ta có  f (z) = T q T ˜ ˜ T )z +   z z (M + M −b T    T      T T x x q M −A M −A   +    +  λ A λ −b A  T    x M + M T 0 x = + q T x − bT λ λ 0 λ  T x =   λ = T x (M + M T ) + q T x − bT λ = x T M x + q T x − bT λ = xT (M x + q) − bT λ = xT (AT λ) − bT λ = λT (Ax − b) ≥ ˜ Theo định lý Frank -Wolfe Từ suy f (z) bị chặn ∆ (Định lý (2.1)), toán (3.7) có nghiệm Bổ đề chứng minh Áp dụng hai bổ đề ta chứng minh Định lý (3.4) Dưới chứng minh chi tiết Chứng minh Từ giả thiết (i) định lý áp dụng Bổ đề (3.6), 46   x0 toán (3.7) có nghiệm z0 =   Do đó, tồn vô hướng λ0   θ1 Lagrange θ =   ∈ R2m µ ∈ Rn cho θ2     T      x0  A 0 θ1     T ˜ ˜  (M + M )   −         I θ2 λ0           q  T T  −(M − A ) µ +   = 0,    −b           A   x0   b        ≥   , θ ≥ 0,     λ0 I              A   x0   b    T   θ    −   =     I λ0 Hệ viết lại sau         T T  M −A  x0   M A  x0  AT       −     +     A λ0 −A λ0            T M  q − µ +   = 0,    −A −b        Ax0 ≥ b, λ0 ≥ 0, θ1 ≥ 0, θ2 ≥ 0,       T (θ ) (Ax0 − b) = 0, (θ2 )T λ0 =   0 θ1    I θ2 Biến đổi hệ ta thu (M x0 − AT λ0 + q) + M T x0 + AT λ0 − AT θ1 − M T µ = 0, Ax0 − Ax0 − θ2 + Aµ − b = 0, 47 (3.11) (3.12) Ax0 ≥ b, λ0 ≥ 0, θ1 ≥ 0, θ2 ≥ 0, (3.13) (θ1 )T (Ax0 − b) = 0, (θ2 )T λ0 =   x0 ˜ nên Từ (3.11) z0 =   ∈ ∆ λ0 (3.14) M T (x0 − µ) = AT (θ1 − λ0 ) (3.15) A(x0 − µ) = A0 − θ2 − b (3.16) Từ (3.12) ta có Sử dụng kết (3.14) - (3.16), ta có (x0 − µ)T M T (x0 − µ) =(x0 − µ)T AT (θ1 − λ0 ) =(θ1 − λ0 )T A(x0 − µ) =(θ1 − λ0 )T (Ax0 − θ2 − b) =(θ1 )T (Ax0 − b) − (θ1 )T θ2 + (θ2 )T λ0 − λ0 T (Ax0 − b) = − (θ1 )T θ2 − λ0 T (Ax0 − b) Do đó, theo (3.13), ta có (x0 − µ)T M T (x0 − µ) = −(θ1 )T θ2 − λ0 T (Ax0 − b) ≤ (3.17) Từ (3.12) suy Aµ − b = θ2 ≥ Vậy µ ∈ ∆ Vì x0 ∈ ∆ nên từ giả thiết (ii) suy (x0 − µ)T M T (x0 − µ) ≥ Kết hợp điều với (3.13) (3.17) ta λT0 (Ax0 −b) = x ˜ M x0 − AT λ0 + q = Do đó, ta Lại có, λ00 ∈ ∆,    M x0 − AT λ0 + q = 0,    Ax0 ≥ b, λ0 ≥ 0,     λT (Ax0 − b) = 0 48 Từ hệ suy x0 ∈ Sol(AV I(M, q, ∆)) (Xem [3, Theorem 5.3]) Ví dụ 3.7 (xem [3, Example 6.1]) Cho    ∈ R2×2 , q = (q1 , q2 ) ∈ R2 , M = −1 ∆ = {x = (x1 , x2 ) ∈ R2+ : x1 ≥ 0, x2 = 0} Không khó để kiểm tra M thỏa mãn điều kiện (ii) Định lý (3.4) Thật vậy, xét hai phần tử thuộc ∆: x = (x1 , x2 ) : x1 ≥ 0, x2 = 0; y = (y1 , y2 ) : y1 ≥ 0, y2 = 0, ta có (y − x)T M (y − x) = (y1 − x1 )2 ≥ 0, ∀x1 , y1 ∈ R Hơn nữa, với q1 < 0, chọn x0 = (−q1 , 0); với q1 ≥ 0, chọn x0 = (0, 0), (M x0 + q)T υ ≥ với υ ∈ 0+ ∆ Vậy điều kiện (i) Định lý (3.4) thỏa mãn Theo định lý này, Sol(A, V, I(M, q, ∆)) khác rỗng Có thể ra, Sol(A, V, I(M, q, ∆)) = {(−q1 , 0)} q1 < Sol(A, V, I(M, q, ∆)) = {(0, 0)} q1 ≥ 3.2 Tính liên tục ánh xạ nghiệm quy hoạch toàn phương phụ thuộc tham số Trong mục ta xét ứng dụng định lý Eaves để nghiên cứu tính chất nửa liên tục ánh xạ nghiệm quy hoạch toàn phương phụ thuộc tham số 49 Xét quy hoạch toàn phương   min f (x) := xT Qx + cT x  với x ∈ ∆(A, b) := {x ∈ Rn : Ax ≥ b} (3.18) phụ thuộc tham số ω = (c, b) ∈ Rn × Rm , Q ∈ Rn×n ,A ∈ S Rm×n đại lượng không đổi Tập nghiệm toán kí hiệu Sol(c, b) Định nghĩa 3.8 Hệ bất đẳng thức :Ax ≥ b gọi quy tồn x0 ∈ Rn cho Ax0 > b Định nghĩa 3.9 Cho X, Y hai không gian tôpô G : X → 2Y ánh xạ đa trị Ta nói G nửa liên tục a ∈ X G(a) = ∅ với hình cầu mở V ⊂ Y thỏa mãn G(a) ∩ V = ∅ tồn lân cận U a cho G(a ) ∩ V = ∅ với a ∈ U Xét ánh xạ nghiệm toán (3.18) nêu n Sol(.) : Rn × Rm → 2R , (c , b ) → Sol(c , b ) (3.19) Ta thừa nhận, không chứng minh kết (xem [3, Lemma 15.1, Lemma 15.2]) Bổ đề 3.10 Nếu ánh xạ đa trị (3.19) nửa liên tục (c, b), hệ Ax ≥ b quy tập Sol(c, b) khác rỗng, hữu hạn Bổ đề 3.11 Nếu ánh xạ đa trị (3.19) nửa liên tục (c, b) tập Sol(c, b) có phần tử Ta đến kết mục Định lí 3.12 (Xem [3, Theorem 15.2]) Ánh xạ đa trị (3.19) nửa liên tục (c, b) hệ Ax ≥ b quy 50 điều kiện sau thoả mãn: (i) vectơ khác không υ ∈ K := {υ ∈ Rn : Aυ ≥ 0, υ T Qυ = 0} thỏa mãn inf {υ T (Qx + c) : x ∈ Rn , Ax ≥ b} > 0, (ii) tập Sol(c, b) có phần tử Ở đây, ta không đưa chứng minh đầy đủ định lý này, chứng minh điều kiện đủ trình bày [3, p 266] Dưới chứng minh điều kiện cần Chứng minh sử dụng kết định lý Frank-Wolfe định lý Eaves Chứng minh Điều kiện cần: Nếu Sol(.) nửa liên tục (c, b) theo mệnh đề (3.2) (3.3) suy hệ Ax ≥ b quy, đồng thời điều kiện (ii) thỏa mãn Ta dùng phương pháp phản chứng Giả sử điều kiện (i) không thỏa mãn Tức là, ta tìm vectơ υ0 ∈ K = {υ ∈ Rn : Aυ ≥ 0, υ T Qυ = 0} cho inf {υ0T (Qx + c) : x ∈ Rn , Ax ≥ b} ≤ (3.20) Ta xét hai khả Nếu giá trị infimum vế trái (3.20) −∞ tồn x0 ∈ ∆(A, b) cho υ0T (Qx0 + c) < Nếu giá trị infimum hữu hạn, áp dụng định lý Frank-Wolfe cho quy hoạch tuyến tính υ0 T (Qx + c) với x ∈ Rn , Ax ≥ b, ta tìm x0 ∈ ∆(A, b) cho υ0T (Qx0 + c) = inf {υ0T (Qx + c) : x ∈ Rn , Ax ≥ b} ≤ Dễ thấy hai trường hợp ta tìm x0 ∈ ∆(A, b) cho υ0T (Qx0 + c) ≤ 51 (3.21) Với số nguyên dương k, đặt ck := c − υ0 Từ (3.21), ta có k υ0T (Qx0 + ck ) = υ0T (Qx0 + c) − T υ0 υ0 < k (3.22) đó, (Q, A, c, b) := (Q, A, ck , b) điều kiện (ii) định lý Eaves không thỏa mãn Vì vậy, theo định lý Sol(ck , b) = ∅ với k Lại có, ck → c k → ∞, suy ánh xạ đa trị (3.19) không thỏa mãn tính chất nửa liên tục (c, b) Điều mâu thuẫn với giả sử ban đầu Điều kiện cần định lý chứng minh Hai định lý tồn nghiệm trình bày đầu Chương có nhiều ứng dụng Nội dung Chương đưa vài ứng dụng khác hai định lý Cụ thể ứng dụng để chứng minh định lý tồn nghiệm toán bất đẳng thức biến phân afin chứng minh định lý tính chất liên tục quy hoạch toàn phương phụ thuộc tham số 52 Kết luận Luận văn nghiên cứu số định lý tồn nghiệm toán quy hoạch toàn phương Mục đích luận văn trình bày hai định lý tồn nghiệm quy hoạch toàn phương (định lý Frank - Wolfe định lý Eaves), thông qua chứng minh hai định lý này; đồng thời đưa số ứng dụng khác chúng Chương đầu luận văn trình bày số khái niệm quy hoạch toán học Trong Chương 2, việc trình bày chứng minh hai định lý tồn nghiệm hệ nó, tác giả đưa số ví dụ minh họa để làm rõ ứng dụng định lý Chương trình bày định lý tồn nghiệm toán bất đẳng thức biến phân định lý tính liên tục ánh xạ nghiệm quy hoạch toàn phương phụ thuộc tham số Chứng minh định lý cho thấy ứng dụng khác định lý Frank - Wolfe định lý Eaves Hướng nghiên cứu phát triển từ đề tài nghiên cứu kết hai định lý tồn nghiệm nêu trường hợp hàm mục tiêu không hàm toàn phương, tập ràng buộc không đa diện Do trình trình độ thời gian hạn chế, luận văn không tránh khỏi thiếu sót Tác giả mong nhận góp ý thầy cô bạn đồng nghiệp Xin chân thành cảm ơn! 53 Tài liệu tham khảo [1] Hoàng Tụy (2006): Lý thuyết tối ưu, giảng lớp cao học, Viện toán học Hà Nội [2] Lê Dũng Mưu Nguyễn Văn Hiền (2009): Nhập môn giải tích lồi ứng dụng, NXB Khoa học tự nhiên Công nghệ [3] Gue Myung Lee, Nguyen Nang Tam and Nguyen Dong Yen (2005): Quadratic Programming and Affine Variation Inequalities, Springer, New York [4] E Blum and W Oettli (1972): Direct proof of existence theorem for quadratic programming, Operation Research, 20, 165-167 [5] B C Eaves (1971): On quadratic programming, Management Science, 17, 698-711 [6] R T Rockafellar (1970): Convec Analysis, Princeton University Press, Princeton, New Jersey [7] M S Gowda and J.-S Pang (1994a): On the boundedness and stability of solutions to the affine variational inequality problem, SIAM Journal on Control and Optimization, 32, 421-441 54 [...]... lồi, hàm lồi, một số quy hoạch toán học (trong đó có các quy hoạch toàn phương) và đưa ra một số ví dụ minh họa Nội dung chính của luận văn được trình bày trong chương tiếp theo 19 Chương 2 Các định lý tồn tại nghiệm của bài toán quy hoạch toàn phương Trong chương này chúng ta sẽ nghiên cứu hai định lý tồn tại cơ bản của các bài toán quy hoạch toàn phương là định lý Frank- Wolfe và định lý Eaves Sau... Hệ quả (2.9) ta có kết luận của Hệ quả (2.11) Chú ý 2.12 Định lý Eaves cho phép kiểm tra sự tồn tại nghiệm của quy hoạch toàn phương dạng (2.1) thông qua phân tích tập các dữ liệu {Q, A, c, b} của nó Nếu một điều kiện nào đó trong ba điều kiện (i), (ii), (iii) không thỏa mãn thì bài toán sẽ vô nghiệm Trong định lý Eaves, quy hoạch toàn phương được cho dưới dạng chuẩn tắc, hai hệ quả dưới đây cho ta kết. .. hệ quả, Q là ma trận nửa xác định dương, nên υ T Qυ ≥ 0 với mọi υ ∈ Rn Do đó, điều kiện (ii) trong Định lý (2.7) (Định lý Eaves) thỏa mãn Từ giả thiết ∆(A, b) khác rỗng và từ (2.25) suy ra cả ba điều kiện của Định lý (2.7) đều thỏa mãn Áp dụng định lý này, hệ quả được chứng minh Hệ quả 2.9 Giả sử Q là một ma trận nửa xác định âm Khi đó bài toán (2.1) có nghiệm nếu và chỉ nếu ∆(A, b) khác rỗng và các. .. một vài điều kiện tồn tại nghiệm địa phương của các quy hoạch này 2.1 Định lý Frank- Wolfe Xét một quy hoạch toàn phương cho dưới dạng   min f (x) := 1 xT Qx + cT x 2 (P )  với x ∈ Rn , Ax ≥ b, 20 (2.1) ở đó Q ∈ RSn×n , c ∈ Rn và b ∈ Rn Ta kí hiệu tập ràng buộc và giá trị tối ưu của bài toán (2.1) lần lượt như sau ∆(A, b) = {x ∈ Rn : Ax ≥ b}, θ = inf {f (x) : x ∈ ∆(A, b)} Nếu ∆(A, b) = ∅ thì quy. .. trong biểu diễn của hàm toàn phương là Vì xT Qx = đối xứng Không gian các ma trận đối xứng cỡ n × n được kí hiệu là Rn×n S Định nghĩa 1.21 Bài toán (P ) được gọi là một bài toán quy hoạch toán học toàn phương (ngắn gọn là một quy hoạch toàn phương) nếu f là một hàm toàn phương và ∆ là một tập lồi đa diện Nhận xét 1.22 Trong (1.11), nếu Q là ma trận 0 thì f là một hàm afin Do đó lớp các quy hoạch tuyến... của bài toán đã cho Đây là một tính chất quan trọng của quy hoạch tuyến tính Rõ ràng, các quy hoạch tuyến tính là các quy hoạch lồi Do đó, chúng có đầy đủ các tính chất của các quy hoạch lồi Ngoài ra, các quy hoạch tuyến tính còn có nhiều tính chất đặc biệt khác Định lí 1.19 (Xem [3, Theorem 1.10]) Cho (P ) là một trong ba dạng quy hoạch tuyến tính đặc trưng Khi đó ta có các tính chất sau: (i) Nếu... c)T υ ≥ 0 Chứng minh Vì Q là ma trận nửa xác định âm nên υ T Qυ ≤ 0 với mọi υ ∈ Rn Do đó điều kiện (ii) trong Định lý (2.7) có thể viết dưới dạng tương đương như điều kiện (ii) trong Hệ quả (2.9) Mặt khác, theo (i), Aυ ≥ 0 kéo theo υ T Qυ = 0, nên điều kiện (iii) của Định lý (2.7) có thể viết lại như điều kiện (ii) của hệ quả nêu trên Ta có được kết luận của hệ quả suy ra từ Định lý (2.7) Hệ quả 2.10... Q là một ma trận xác định dương, thì bài toán (2.1) có nghiệm nếu và chỉ nếu ∆(A, b) khác rỗng Chứng minh Do Q là ma trận xác định dương nên từ υ T Qυ = 0 suy ra υ = 0 Do đó, điều kiện (2.25) thỏa mãn Từ Hệ quả 2.8, Hệ quả (2.10) được chứng minh 35 Hệ quả 2.11 Nếu Q một ma trận xác định âm, thì bài toán (2.1) có nghiệm khi và chỉ khi ∆(A, b) là khác rỗng và compact Chứng minh Ta sẽ sử dụng Hệ quả (2.9)... nghiệm của bài toán tối ưu này, mâu thuẫn xảy ra Định lý được chứng minh Sau đây là một vài hệ quả quan trọng của định lý Eaves (xem [3, p 4 1-4 3]) 34 Hệ quả 2.8 Giả sử Q là một ma trận nửa xác định dương Khi đó, bài toán (2.1) có nghiệm khi và chỉ khi ∆(A, b) khác rỗng và điều kiện sau đây được thỏa mãn: (υ ∈ Rn , x ∈ Rn , Aυ ≥ 0, υ T Qυ = 0, Ax ≥ b) ⇒ (Qx + c)T υ ≥ 0 (2.25) Chứng minh Theo giả thiết của. .. (P ) là một quy hoạch không lồi 11 Dưới đây là một tính chất quan trọng của quy hoạch lồi Mệnh đề 1.14 Nếu (P ) là một quy hoạch lồi thì Sol(P ) = loc(P ) Chứng minh Ta chỉ cần chứng minh rằng loc(P ) ⊂ Sol(P ) với quy hoạch lồi (P ) bất kỳ Lấy x0 ∈ loc(P ) và U là một lân cận của x0 thỏa mãn (1.1) Giả sử x0 ∈ / Sol(P ), khi đó tồn tại x ˆ ∈ ∆ sao cho f (ˆ x) < f (x0 ) Vì f (x0 ) = +∞ suy ra f (ˆ x)