ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN NGUYỄN THỊ THẮM BÀI TOÁN QUY HOẠCH TỒN PHƯƠNG LỒI TRÊN KHƠNG GIAN HILBERT LUẬN VĂN THẠC SĨ KHOA HỌC Hà Nội - Năm 2017 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN NGUYỄN THỊ THẮM BÀI TỐN QUY HOẠCH TỒN PHƯƠNG LỒI TRÊN KHƠNG GIAN HILBERT Chun ngành: Tốn ứng dụng Mã số: 60460112 LUẬN VĂN THẠC SĨ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC PGS TS Nguyễn Năng Tâm Hà Nội - Năm 2017 Mục lục Lời cảm ơn Danh sách ký hiệu Lời nói đầu Chương Kiến thức chuẩn bị 1.1 Không gian Hilbert 1.2 Tập lồi, Hàm lồi 1.3 Dạng toàn phương 12 1.4 Dạng Legendre 15 1.5 Bài tốn quy hoạch tồn phương 16 Chương Sự tồn nghiệm tốn quy hoạch tồn phương lồi 19 2.1 Phát biểu toán 19 2.2 Sự tồn nghiệm 22 2.2.1 Trường hợp dạng toàn phương dạng Legendre 25 2.2.2 Trường hợp tốn tử có hạng hữu hạn 34 Kết luận 39 Tài liệu tham khảo 40 Lời cảm ơn Luận văn hoàn thành trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội với hướng dẫn bảo tận tình PGS TS Nguyễn Năng Tâm Em xin bày tỏ lòng biết ơn sâu sắc quan tâm, động viên bảo hướng dẫn thầy Qua đây, em xin gửi lời cảm ơn sâu sắc tới q thầy Khoa Tốn - Cơ Tin học, Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội, thầy cô tham gia giảng dạy khóa cao học 2015 - 2017, có cơng lao dạy dỗ em suốt q trình học tập Nhà trường Em xin cảm ơn gia đình, bạn bè bạn đồng nghiệp thân mến quan tâm, tạo điều kiện cổ vũ, động viên em để em hồn thành tốt nhiệm vụ Hà Nội, ngày 23 tháng 11 năm 2017 Học viên Nguyễn Thị Thắm Danh sách ký hiệu (QP) (CQP) Bài tốn quy hoạch tồn phương Bài tốn quy hoạch tồn phương lồi R Tập số thực Rn Khơng gian vectơ n chiều X Không gian Hilbert thực L(X, Y ) Tập hợp tốn tử tuyến tính liên tục từ X vào Y L2 [a, b] Không gian Hilbert hàm bình phương khả tích Khơng gian Hilbert dãy số thực bình phương khả tổng A Tốn tử tự liên hợp tuyến tính liên tục T (·) Dạng toàn phương dom f epi f D ·, · x 0+ X xn x v.đ.k Miền hữu hiệu hàm f Trên đồ thị hàm f Tập ràng buộc tốn quy hoạch Tích vơ hướng Chuẩn vectơ x Nón lùi xa tập lồi đóng khác rỗng X x hội tụ yếu tới x với điều kiện Lời nói đầu Bài tốn quy hoạch tồn phương (viết tắt tốn (QP)) tốn tìm nghiệm tối ưu hàm tồn phương tập hợp xác định số hữu hạn hàm toàn phương Quy hoạch toàn phương nghiên cứu khía cạnh định tính, định lượng, thuật tốn ứng dụng khác toán quy hoạch toàn phương Quy hoạch toàn phương lồi phận quan trọng quy hoạch toán học Sự tồn nghiệm tốn quy hoạch tồn phương (QP) lồi câu hỏi thú vị lý thuyết tối ưu Câu hỏi điều kiện hữu hạn chiều vô hạn chiều nghiên cứu rộng rãi số tác giả Có số điều kiện biết để đảm bảo tồn nghiệm tốn (QP) lồi Ví dụ, tập ràng buộc toán (QP) khác rỗng bị chặn, hàm mục tiêu nửa liên tục yếu bị chặn tập ràng buộc, tồn nghiệm suy từ tính compact Sự ràng buộc hàm mục tiêu giả thiết dùng nhiều để đảm bảo tồn nghiệm toán (QP) Tuy nhiên, ta muốn xác định xem nghiệm toán (QP) lồi có tồn trường hợp tổng qt khơng Ý tưởng sử dụng tích chất Legendre dạng toàn phương hàm mục tiêu để chứng minh tồn nghiệm toán quy hoạch tồn phương với ràng buộc tuyến tính khơng gian Hilbert Bonnans Shapiro Chúng muốn nhấn mạnh khái niệm dạng Legendre, mà có nguồn gốc từ giải tích biến phân, quan trọng định lý tồn nghiệm Trong Chương 2, chúng tơi xây dựng ví dụ để kết luận định lý sai bỏ qua giả thiết tính Legendre dạng tồn phương Bằng cách sử dụng tích chất Legendre dạng tồn phương tính chất hạng hữu hạn tốn tử tương ứng với dạng tồn phương, ta tồn nghiệm tốn quy hoạch tồn phương lồi với ràng buộc tồn phương khơng gian Hilbert mà khơng cần đòi hỏi hạn chế vào hàm mục tiêu tính compact tập ràng buộc Vì vậy, chúng tơi chọn đề tài nghiên cứu “Bài tốn quy hoạch tồn phương lồi không gian Hilbert” để làm luận văn cao học Mục tiêu luận văn trình bày lại kết báo [5] tồn nghiệm tốn (QP) lồi khơng gian Hilbert Các kết [5] mở rộng kết tồn nghiệm toán (QP) lồi từ không gian Euclide sang không gian Hilbert Trong luận văn này, ngồi phần Lời nói đầu, Kết luận, Tài liệu tham khảo, luận văn bao gồm hai chương Chương trình bày số khái niệm tính chất khơng gian Hilbert, tập lồi, hàm lồi, dạng toàn phương, hàm toàn phương, dạng Legendre tốn quy hoạch tồn phương Chương nghiên cứu tồn nghiệm tốn quy hoạch tồn phương lồi (CQP) Định lý 2.2.4 khẳng định tồn nghiệm tốn dạng tồn phương x, Ax dạng Legendre hàm mục tiêu f bị chặn tập ràng buộc khác rỗng Định lý 2.2.11 khẳng định toán tử tương ứng với dạng tồn phương có hạng hữu hạn, nửa xác định dương, hàm mục tiêu f bị chặn tập ràng buộc khác rỗng tốn có nghiệm Hà Nội, ngày 23 tháng 11 năm 2017 Học viên Nguyễn Thị Thắm Chương Kiến thức chuẩn bị Trong chương này, chúng tơi trình bày số khái niệm tính chất khơng gian Hilbert, tập lồi, hàm lồi, dạng toàn phương, hàm toàn phương, dạng Legendre phát biểu tốn quy hoạch tồn phương 1.1 Không gian Hilbert Định nghĩa 1.1.1 ([2]) Cho X không gian vectơ trường R, ánh xạ ϕ : X × X → R gọi dạng song tuyến tính đối xứng dương nếu, với x, y, z ∈ X λ ∈ R, tính chất sau thỏa mãn: a) ϕ(x, x) ≥ 0, b) ϕ(x, y) = ϕ(y, x), c) ϕ(x + y, z) = ϕ(x, z) + ϕ(y, z), d) ϕ(λx, y) = λϕ(x, y) Lúc đó, người ta thường ký hiệu vắn tắt x, y := ϕ(x, y) Mệnh đề 1.1.2 (Bất đẳng thức Cauchy-Schwarz) Với x, y ∈ X, ta có x, y ≤ x, x y, y Chứng minh Với y = bất đẳng thức Giả sử y = 0, với λ ∈ R ta có x + λy, x + λy ≥ suy x, x + λ y, x + λ x, y + λ2 y, y ≥ 0, hay q(λ) = y, y λ2 + x, y λ + x, x ≥ Do q(λ) đa thức bậc hai theo biến thực λ q(λ) ≥ với λ Điều xảy y, y > ∆ = x, y x, y 2 − y, y x, x ≤ Suy ≤ x, x y, y Nếu dạng song tuyến tính đối xứng dương ·, · X thỏa mãn thêm điều kiện x, x > 0, với x = 0, gọi tích vô hướng X (X, ·, · ) gọi khơng gian tiền Hilbert Lúc đó, dễ thấy x, x x = xác định chuẩn X Vậy, không gian tiền Hilbert không gian định chuẩn, khái niệm, kết thiết lập không gian định chuẩn áp dụng cho không gian tiền Hilbert Các kết chứng minh lý thuyết không gian metric Định nghĩa 1.1.3 ([2]) Dãy (xn ) ⊂ X gọi dãy Cauchy xm − xk −→ Tức m,k→∞ ∀ε > 0, ∃n0 , ∀m, k > n0 : xm − xk < ε Mệnh đề 1.1.4 ([2]) Nếu (xn ) dãy hội tụ, dãy Cauchy Mệnh đề 1.1.5 ([2]) Nếu (xn ) dãy Cauchy, bị chặn Tức tồn số dương M cho xn ≤ M, ∀n Định nghĩa 1.1.6 ([2]) Không gian metric X gọi đầy đủ dãy Cauchy X hội tụ X Định nghĩa 1.1.7 ([2]) Một không gian tiền Hilbert (với tư cách không gian định chuẩn) đầy đủ gọi không gian Hilbert Trong luận văn này, không xác định rõ, không gian Hilbert ký hiệu chung X Ví dụ 1.1.8 Tính vơ hướng thơng thường Rn xác định n x, y = xi yi , i=i x = (x1 , , xn ), y = (y1 , , yn ), với xi , yi ∈ R Khơng gian đầy đủ, khơng gian Hilbert Ví dụ 1.1.9 Ký hiệu L2 (R) khơng gian hàm bình phương khả tích R Khi L2 (R) khơng gian Hilbert với tích vơ hướng xác định f, g = f (x)g(x)dx R Ví dụ 1.1.10 Cho (X, Ω, µ) khơng gian độ đo bao gồm tập X, σ-đại số Ω tập X, µ độ đo cộng tính đếm xác định Ω Ký hiệu L2 (Ω) = {f : Ω → R : |f (x)|2 dµ < ∞} Ω Khi đó, L2 (Ω) khơng gian Hilbert với tích vơ hướng xác định f, g = f (x)g(x)dµ Ω 1.2 Tập lồi, Hàm lồi Định nghĩa 1.2.1 ([8]) Tập C X gọi lồi (1 − λ)x + λy ∈ C với x, y ∈ C < λ < Ví dụ 1.2.2 Các nửa khơng gian ví dụ quan trọng tập lồi Với b ∈ Rn β ∈ R, tập {x | x, b ≤ β}, {x | x, b ≥ β}, Từ bất đẳng thức ta suy v, Av = lim v k , Av k = k→∞ Vì A nửa xác định dương, từ ta suy Av = (2.16) Bởi tính nửa xác định dương A, từ (2.13) suy c, xk ≤ f ∗ + k (2.17) Chia hai vế bất đẳng thức cho xk , cho qua giới hạn k → ∞ ta đạt c, v ≤ Bây ta c, v = Giả sử c, v < Với k cố định với t > 0, ta có xk + tv ∈ F t2 v, Av + t Axk + c, v = f (xk ) + t c, v → −∞ t → +∞ f (xk + tv) = f (xk ) + Điều mâu thuẫn với f bị chặn X Do vậy, ta có c, v = (2.18) Kết hợp (2.16) với (2.18) ta thu (2.15) Bây ta xét ba trường hợp nhỏ: Trường hợp : ci , v = với i = 1, 2, , m Khi đó, Av = 0, c, v = 0, Ai v = 0, ∀i = 1, 2, , m Đặt y k (t) := xk − tv, t > Dễ kiểm tra y k (t) := xk − tv ∈ D với t > Vì Av = 0, c, v = 0, ta có f (y k (t)) = f (xk − tv) = k t2 x , Axk + c, xk + v, Av − t xk , Av − t c, v 2 27 = f (xk ) ≤ f ∗ + k Do vậy, y k (t) ∈ Sk với t > Mặt khác, ta có y k (t) 2 = xk − tv = xk − t xk , v + t v (2.19) Vì v, v = xk / xk , v → v, v , tồn k1 cho xk , v > ∀k ≥ k1 Do đó, với k ≥ k1 , theo (2.19) tồn γ > cho xk − tv < xk ∀t ∈ (0, γ) (2.20) Từ (2.20) suy xk − tv < xk Điều mâu thuẫn với xk phần tử có chuẩn nhỏ Sk , kéo theo trường hợp không xảy Trường hợp : ci , v < với i = 1, 2, , m Xét tốn quy hoạch tồn phương min{f (x) : x, Ax + c, x | x ∈ X } Nếu f (x) bị chặn không gian Hilbert X theo Định lý 2.2.1, tồn x ∈ X cho f (x) ≤ f ∗ Nếu f (x) không bị chặn không gian Hilbert X tồn xˆ ∈ X cho f (ˆ x) ≤ f ∗ Cho nên, hai trường hợp tồn x∗ ∈ X cho f (x∗ ) ≤ f ∗ Đặt t∗ = max{−gi (x∗ )/ ci , v , i = 1, 2, , m} Dễ kiểm tra x∗ + tv ∈ D với t ≥ t∗ Khi đó, ta có f (x∗ + t∗ v) = ∗ x , Ax∗ + c, x∗ ≤ f ∗ Điều x∗ + t∗ v nghiệm toán (CQP) Trường hợp : Tồn i j cho ci , v = cj , v < Đặt I = {1, 2, , n}, I1 = {i ∈ I | ci , v = 0} F1 = {x ∈ X | gi (x) ≤ 0, i ∈ I1 } Xét toán f (x) := x, Ax + c, x | x ∈ F1 28 Rõ ràng xk thuộc F1 với k Theo trường hợp bên trên, tồn x∗1 ∈ F1 cho f (x∗1 ) ≤ f ∗ Đặt t∗1 = max {−gi (x∗1 ) c − j, v , j ∈ H\I1 } Dễ kiểm tra x∗1 + tv ∈ D với t ≥ max{0, t∗1 } Khi đó, ta có f (x∗1 + t∗ v) = ∗ x1 , Ax∗1 + c, x∗1 ≤ f ∗ Suy x∗1 + t∗1 v nghiệm (CQP) Điều phải chứng minh Trong khơng gian Hilbert, tính bị chặn (CQP) nói chung khơng kéo theo tồn nghiệm không gian Euclide Rn Bây xây dựng ví dụ Ví dụ 2.2.5 Ký hiệu phương khả tổng, 2 khơng gian Hilbert tất dãy số thực bình ∞ n=1 xn = {x = (x1 , x2 , , xn , ) | 1, 2, } Tích vơ hướng chuẩn định nghĩa ∞ x, y = 1/2 ∞ xn yn , x2n x = n=1 Với x = (x1 , x2 , , xn , ) ∈ < ∞, xn ∈ R, n = n=1 Ax = x1 , , định nghĩa A : → xn x2 , , , 22 nn Dễ thấy A toán tử tự liên hợp tuyến tính liên tục A = Dạng toàn phương tương ứng với A ∞ T (x) = x, Ax = n=1 ∞ x2n n=1 nn Chúng cho T (x) = x, Ax = Thật vậy, lấy {ek } dãy x2n nn dạng Legendre , ek = (ek1 , ek2 , , ekn , ) cho ekn = với n = k, ekn = với n = k Dễ kiểm tra ek hội tụ yếu tới không hội tụ mạnh Ta có ek , Aek = → = 0, A0 kk k → ∞ Do đó, T (x) = x, Ax khơng dạng Legendre Vì T (x) = x, Ax = ∞ x2n n=1 nn ≥ với x ∈ 1.3.11, x, Ax nửa liên tục yếu lồi 29 , theo Mệnh đề 1.3.10 Bây ta xét toán quy hoạch (CQP) f (x) = x, Ax v.đ.k x ∈ : c1 , x + α1 ≤ 0, (2.21) ∞ x, Ax = n=1 x2n , c1 = nn 1 − 1, − , , − , n ∈ , α1 = Đặt ∞ D = {x ∈ | c1 , x + α1 ≤ 0} = x∈ |− n=1 xn +1≤0 n D khác rỗng Thật vậy, với số nguyên dương k, đặt xk = kek ∈ , ek véctơ nhắc đến Dễ kiểm tra c1 , xk + = −1 + = Cho nên xk ∈ F với k Vì x, Ax = ∞ n n=1 xn /n , x, Ax = x = Dễ thấy 0∈ / D, ta có 1 f (x) = x, Ax = 2 ∞ n=1 x2n > với x ∈ D nn (2.22) Mặt khác, k 1 x , Axk = → k → ∞ 2 k k−2 Điều với (2.22) cận f D Vì ∈ / D, bất f (xk ) = đẳng thức (2.22) tốn (2.21) khơng có nghiệm Ví dụ bên kết luận Định lý 2.2.4 không giả thiết tính Legendre dạng tồn phương bị bỏ qua Nhận xét 2.2.6 Trong trường hợp hữu hạn chiều, chứng minh Định lý 2.2.4 xem [3] Belousov Klatte [3] chứng minh tồn tồn quy hoạch tồn phương khơng lồi R3 với hai ràng buộc lồi bậc hai mà hàm mục tiêu bị chặn tập ràng buộc khác rỗng, mà khơng có nghiệm Do đó, chí trường hợp tốn quy hoạch tồn phương chiều, bỏ qua giả thiết A nửa xác định dương Định lý 2.2.4 30 Để áp dụng Định lý 2.2.4, ta phải tìm hàm mục tiêu f (x) (CQP) bị chặn D Đây nhiệm vụ khó Trong định lý sau mở rộng kết [6] cho không gian Hilbert mà đưa điều kiện cần đủ để tồn nghiệm (CQP) Định lý 2.2.7 (Định lý kiểu Eaves 2, [5]) Xét toán (CQP) D khác rỗng x, Ax dạng Legendre Các phát biểu sau đúng: (a) Nếu (CQP) có nghiệm (v ∈ 0+ D, Av = 0) ⇒ c, v ≥ (2.23) (b) Bài toán (CQP) có nghiệm điều kiện sau xảy ra: c = 0, (2.24) (v ∈ 0+ D\{0}, Av = 0) ⇒ c, v ≥ 0, (2.25) (v ∈ 0+ D, Av = 0) ⇒ ( c, v ≥ 0, ci , v = 0, ∀i ∈ I1 ), (2.26) I = {1, 2, , m} I1 = {i ∈ I | Ai = 0} Chứng minh (a) Giả sử (CQP) có nghiệm x Để thu (2.23), lấy v ∈ 0+ D cho Av = Vì x + v ∈ D Av = 0, ta có ≤ f (x + v) − f (x) = x + v, A(x + v) + c, x + v = c, v − x, Ax + c, v Ta chứng minh c, v ≥ với v ∈ 0+ D thỏa mãn Av = (b) Giả sử c = Để chứng minh (CQP) có nghiệm, theo Định lý 2.2.4 ta cần kiểm tra f bị chặn D Vì x, Ax ≥ với x ∈ X , ta f (x) = x, Ax + c, x chi f có cận D 31 ∀x ∈ X , Tiếp theo, giả sử (2.25) đúng, Ta chứng minh f cưỡng (coercive) Giả sử phản chứng f không cững D Khi đó, ta tìm a ∈ R dãy {xk } ⊂ D với xk → ∞ k → ∞ f (xk ) = k x , T xk + c, xk ≤ a ∀k Ta giả sử xk = với k, v k := xk −1 k x (2.27) v Theo Nhận xét 2.1.5, ta có v ∈ 0+ D Nhân bất đẳng thức xk , Axk + c, xk ≤ a (2.27) với xk −2 tính giới hạn k → ∞, ta thu v, Av ≤ lim inf v k , Av k ≤ lim inf v k , Av k ≤ k→∞ k→∞ (2.28) Kết hợp điều với tính nửa xác định dương A, ta suy lim v k , Av k = v, Av = 0, (2.29) Av = (2.30) k→∞ Vì x, Ax dạng Legendre v k v k → ∞, theo (2.29), v k hội tụ tới v Cho nên, ta có v = Do xk , Axk ≥ 0, từ (2.27) suy c, xk ≤ a Nhân bất đẳng thức với xk −1 (2.31) cho k → ∞, ta c, v ≤ (2.32) Mâu thuẫn với (2.25) Do f cưỡng D Theo [18, Định lý 6.2.4], (CQP) có nghiệm Cuối cùng, giả sử (2.26) Khi đó, tất giả thiết Định lý 3.3 [7] (CQP) có nghiệm Kết thúc chứng minh Cần phải nhấn mạnh điều kiện (2.23) cần không đủ để tồn nghiệm (2.23) Bây chúng tơi xây dựng ví dụ 32 Ví dụ 2.2.8 Cho X = , Ax = (0, 0, x3 , , xn , ), A1 x = (0, x2 , 0, 0, ) với x = (x1 , x2 , x3 , , xn , ) ∈ 2 , cho c = (0, −1, 0, 0, ), c1 = (1, 0, 0, ) ∈ , α1 = −1 Khi đó, (CQP) trở thành f (x) = (0x21 + 0x22 + x23 + x24 + · · · ) − x2 với ràng buộc x ∈ D, D = {x = (x1 , x2 , ) ∈ (2.33) | 21 x22 + x1 − ≤ 0} Vì x, Ax ≥ với x ∈ D, f (x) lồi Dễ kiểm tra x, Ax = x − (x21 + x22 ), nên dạng bậc hai x, Ax tổng dạng toàn phương elliptic dạng tồn phương có hạng hữu hạn Theo Mệnh đề 1.4.5 suy x, Ax dạng Legendre Theo (2.1), ta có 0+ D = {v ∈ F | A1 v = 0, c1 , v ≤ 0} = {(v1 , 0, v3 , v4 , ) ∈ | v1 ≤ 0} Chú ý v = (v1 , 0, v3 , v4 , ) ∈ 0+ D Av = c, v = −v2 = Do điều kiện (2.23) thỏa mãn Vì xk := − 12 k , k, 0, ∈ D với số nguyên k ≥ f (xk ) = −k, ta suy f không bị chặn F Cho nên, (2.33) khơng có nghiệm Nhận xét 2.2.9 Chú ý Ai = với i = 1, 2, , m ci = với i ∈ I1 , (2.23) điều kiện cần đủ để tồn nghiệm (CQP), miễn D = ∅ Ví dụ sau điều kiện (2.24), (2.25), (2.26) điều kiện đủ điều kiện cần để tồn nghiệm (CQP) Ví dụ 2.2.10 Xét toán quy hoạch x, Ax + c, x , v.đ.k x = (x1 , x2 , ) ∈ : x, Ti x + ci , x + αi ≤ 0, i = 1, 2 f (x) = (2.34) Ax = (0, x2 , x3 , x4 , ), c = (0, 1, 0, 0, ), A1 x = (0, x2 , x3 , ), c1 (0, 0, 0, ), α1 = 0, A2 x = (0, 0, x3 , 0, 0, ), c2 = (1, 0, 0, ), α2 = Vì x, Ax = ∞ n=1 xn ≥ với x ∈ 33 , x, T x lồi Dễ kiểm tra x, Ax = x − x21 , nên dạng toàn phương x, Ax tổng dạng toàn phương elliptic dạng tồn phương có hạng hữu hạn Theo Mệnh đề 1.4.5 suy x, Ax dạng Legendre Từ Bổ đề 2.1.3, suy 0+ D = D = {v = (v1 , 0, 0, ) ∈ | v1 ≤ 0}, {v ∈ 0+ F | Av = 0} = {v = (v1 , 0, 0, ) ∈ | v1 ≤ 0} Vì f (x) = D, tập nghiệm (2.34) trùng với D Ta thấy toán (2.34) có nghiệm c = (0, 1, 0, 0, ) = 0, c, v = c2 , v = 0, v := (−1, 0, , 0, ) Do đó, điều kiện (2.24), (2.25), (2.26) đủ không điều kiện cần để tồn nghiệm (CQP) 2.2.2 Trường hợp toán tử có hạng hữu hạn Trong phần lại mục chúng tơi trình bày kết tồn nghiệm (CQP) giả thiết tất toán tử tương ứng với dạng tồn phương có hạng hữu hạn Chú ý ràng giả thiết giới hạn việc sử dụng giả thiết ta nghiên cứu tồn nghiệm lớp tốn (CQP), dạng tồn phương hàm mục tiêu không dạng Legendre Định lý coi phần bù Định lý 2.2.4 Định lý 2.2.11 (Frank-Wolfe type Theorem 2, [5]) Xét tốn (CQP), A Ai (i = 1, 2, , m) toán tử hạng hữu hạn nửa xác định dương Giả sử hàm mục tiêu f bị chặn tập khác rỗng D Khi đó, (CQP) có nghiệm Chứng minh Ta chứng minh định lý quy nạp theo m - số phương trình bậc hai xác định tập ràng buộc D (CQP) Với m = 1: với k, xét tập Sk = {x ∈ D | f (x) ≤ f ∗ + k1 } Vì f ∗ > −∞, tồn {xk } ⊂ X cho k x , Axk + c, xk ≤ f ∗ + , k g(xk ) = xk , A1 xk + c1 , xk + α1 ≤ f (xk ) = 34 (2.35) Giả sử xk phần tử có chuẩn nhỏ Sk Nếu {xk } bị chặn {xk } có dãy hội tụ yếu Khơng tính tổng qt, ta giả sử xk hội tụ yếu tới x Do A A1 toán tử hạng hữu hạn, chúng compact Kéo theo f (x) g1 (x) liên tục yếu Do đó, lấy giới hạn (2.35) xk x ta thấy x nghiệm (CQP) Xét trường hợp {xk } không bị chặn Đặt v k := xk / xk , ta có v k = Khơng giảm tính tổng quát, ta giả sử v k := xk / xk v k → ∞ Vì A A1 nửa xác định dương, lập luận tương tự chứng minh Định lý 2.2.4 ta suy Av = 0, c, v = 0, A1 v = 0, c1 , v ≤ Bây ta chứng minh c1 , v < Giả sử ngược lại, c1 , v = Khi đó, Av = 0, c, v = 0, A1 v = 0, c1 , v = Đặt L1 = X ⊕ X ⊕ R2 , ⊕ ký hiệu tổng trực tiếp không gian Hilbert, ký hiệu ·, · L · L tương ứng tích vơ hướng chuẩn L Định nghĩa Q : X → L1 Qx = (Ax, A1 x, c, x , c1 , x ) Vì A A1 toán tử hạng hữu hạn, nên Q Với k, xét hệ tuyến tính Qx = Qxk (2.36) Vì Q tốn tử hạng hữu hạn, Q tốn tử compact với miền giá trị đóng Cho nên, tồn tựa nghịch đảo liên tục Q+ Q nghiệm xk (2.36) cho xk = Q+ Qxk Do đó, tồn ρ > 0, phụ thuộc A, cho xk ≤ ρ( Qxk L ) Kéo theo xk ≤ ρ( Axk + A1 xk + | c, xk | + | c1 , xk |) Theo (2.36), Qxk = Qxk , ta kiểm tra f (xk ) = f (xk ) ≤ f ∗ + k 35 Vì xk phần tử có chuẩn nhỏ Sk , ta có xk ≤ xk ≤ ρ( Axk + A1 xk + | c, xk | + | c1 , xk |) ∀k Theo giả thiết A A1 tốn tử có hạng hữu hạn, A A1 compact với miền giá trị đóng Chia hai vế bất đẳng thức cho xk , cho k → ∞ tính compact A A1 , ta có ≤ ρ( Av + A1 v + | c, v | + | c1 , v |) Điều mâu thuẫn với Av = 0, c, v = 0, A1 v = 0, c1 , v = Do c1 , v < Khẳng định chứng minh Xét toán quy hoạch toàn phương f (x) := x, Ax + c, x | x ∈ X Nếu f bị chặn không gian Hilbert X , theo Định lý 2.2.1, tồn x ∈ X cho f (x) ≤ f ∗ Nếu f (x) không bị chặn X , rõ ràng tồn xˆ ∈ X cho f (ˆ x) ≤ f ∗ Cho nên, hai trường hợp tồn x∗ ∈ X cho f (x∗ ) ≤ f ∗ Do c1 , v < 0, ta kiểm tra x∗ + tv ∈ D với t > đủ lớn Chọn t∗ > cho x∗ + t∗ v ∈ D, theo (2.35), ta có f (x∗ + t∗ v) = ∗ x , Ax∗ + c, x∗ ≤ f ∗ Điều x∗ + t∗ v nghiệm toán (CQP) Kết thúc chứng minh trường hợp m = Giả sử khẳng định với tất tập ràng buộc D xác định m − hàm bậc hai, cho D xác định m hàm bậc hai Đặt f ∗ = inf{f (x) | x ∈ D} > −∞ Đặt Sk = {x ∈ D | f (x) ≤ f ∗ + k1 } Vì f ∗ > −∞, Sk khác rỗng, lồi đóng Cho nên Sk có phần tử có chuẩn nhỏ Gọi xk phần tử có chuẩn nhỏ Sk , ta có k x , Axk + c, xk ≤ f ∗ + , k gi (xk ) = xk , Ai xk + ci , xk + αi ≤ 0, i = 1, 2, , m f (xk ) = 36 Nếu {xk } bị chặn thì {xk } có dãy hội tụ yếu Khơng giảm tính tổng qt, ta giả sử xk hội tụ yếu tới x Khi dễ kiểm tra x nghiệm (CQP) Xét trường hợp {xk } không bị chặn Đặt v k := xk / xk , ta có v k = Khơng giảm tính tổng qt, ta giả sử v k := xk / xk v k → ∞ Vì A Ai nửa xác định dương, lập luận tương tự trường hợp m = ta suy Av = 0, c, v = 0, Ai v = 0, ci , v ≤ 0, tồn j ∈ {1, 2, , m} cho cj , v < Khơng giảm tính tổng qt ta giả sử cm , v < Xét toán min{f (x) := x, Ax + c, x | x ∈ D1 } (P1 ) D1 := {x ∈ X : gi (x) ≤ 0, i = 1, 2, , m − 1} Đối với toán này, f bị chặn D1 không Nếu f bị chặn D1 theo giả thiết quy nạp, tốn (P1 ) có nghiệm Nên khơng hai trường hợp, tồn x ∈ D1 cho f (x) ≤ f ∗ Xét véctơ x(t) := x + tv, t ≥ Do c, v = 0, ta có f (x(t)) = f (x) + t c, v = f (x) ≤ f ∗ , ∀t > Vì gm (x(t)) = gm (x) + t cm , v , cm , v < 0, ta chọn t∗ > cho x(t∗ ) ∈ f f (x(t∗ )) ≤ f ∗ Điều chứng minh x(t∗ ) nghiệm (CQP) Suy điều phải chứng minh Nhận xét 2.2.12 Chú ý Ví dụ 2.2.5, A tốn tử compact có miền giá trị khơng đóng, nên A khơng có hạng hữu hạn Do đó, Định lý 2.2.11 khơng giả thiết A, Ai toán tử hạng hữu hạn bị thay A, Ai toán tử compact, i = 1, 2, , m 37 Trong trường hợp A = Ai = (i = 1, 2, , m), ta thu tồn nghiệm toán quy hoạch (LP) không gian Hilbert Hệ 2.2.13 ([5]) Xét tốn quy hoạch tuyến tính (LP) Giả sử f (x) bị chặn tập khác rỗng F Khi tốn (LP) có nghiệm Chứng minh Dễ thấy tốn tử khơng tốn tử có hạng hữu hạn Khẳng định hệ suy từ Định lý 2.2.11 Nhận xét 2.2.14 ([5]) Nếu X hữu hạn chiều tốn tử liên tục A X toán tử hạng hữu hạn x, Ax dạng Legendre Do đó, trường hợp hữu hạn chiều, Định lý 2.2.4 Định lý 2.2.11 giống 38 Kết luận Trong luận văn chúng tơi trình bày: Chương trình bày số khái niệm tính chất khơng gian Hilbert, tập lồi, hàm lồi, dạng toàn phương, hàm toàn phương, dạng Legendre tốn quy hoạch tồn phương Chương nghiên cứu tồn nghiệm tốn quy hoạch tồn phương lồi (CQP) Định lý 2.2.4 khẳng định tồn nghiệm toán dạng toàn phương x, Ax dạng Legendre hàm mục tiêu f bị chặn tập ràng buộc khác rỗng Ví dụ 2.2.5 tính Legendre dạng tồn phương khơng thể bỏ qua Định lý 2.2.11 khẳng định toán tử tương ứng với dạng tồn phương có hạng hữu hạn, nửa xác định dương, hàm mục tiêu f bị chặn tập ràng buộc khác rỗng tốn có nghiệm 39 Tài liệu tham khảo Tiếng Việt [1] Nguyễn Hữu Việt Hưng (2001), Đại số tuyến tính, NXB Đại học Quốc Gia Hà Nội [2] Huỳnh Thế Phùng (2005), Giáo trình giải tích hàm, Đại học Khoa học Huế Tiếng Anh [3] E.G Belousov and D Klatte (2002), “A Frank-Wolfe type theorem for convex polynomial programs”, Comput Optim Appl., Vol 22, No 1, pp 37–48 [4] J F Bonnans and A Shapiro (2000), Pertubation Analysis of Optimization Problems, Springer-Verlag, New York https://doi.org/10.1007/978-1-4612-1394-9 [5] Vu Van Dong and Nguyen Nang Tam (2016), “On the Solution Existence of Convex Quadratic Programming Problems in Hilbert Spaces”, Taiwanese Journal of Mathematics, Vol 20, No 6, pp 1417–1436 [6] D.S Kim, N.N Tam and N.D Yen (2012), “Solution existence and stability of quadratically constrained convex quadratic programs”, Optim Lett., Vol 6, No 2, pp 363–373 https://doi.org/10.1007/s11590-011-0300-8 40 [7] Hestenes (1951), “M R Applications of the theory of quadratic forms in Hilbert space to the calculus of variations”, Pacific J Math., 1, pp 525– 581 [8] R.T Rockafellar (1970), Convex analysis, Priceton University Press [9] Hoang Tuy (1998), Convex analysis and global optimization, Kluwer Academic Publishers 41 ... tính chất khơng gian Hilbert, tập lồi, hàm lồi, dạng toàn phương, hàm toàn phương, dạng Legendre tốn quy hoạch tồn phương Chương nghiên cứu tồn nghiệm toán quy hoạch toàn phương lồi (CQP) Định... chất khơng gian Hilbert, tập lồi, hàm lồi, dạng toàn phương, hàm toàn phương, dạng Legendre phát biểu toán quy hoạch tồn phương 1.1 Khơng gian Hilbert Định nghĩa 1.1.1 ([2]) Cho X không gian vectơ... Thị Thắm Danh sách ký hiệu (QP) (CQP) Bài tốn quy hoạch tồn phương Bài tốn quy hoạch toàn phương lồi R Tập số thực Rn Không gian vectơ n chiều X Không gian Hilbert thực L(X, Y ) Tập hợp tốn tử