Tài liệu Luận văn thạc sĩ phép chiếu xuống tập lồi và ứng dụng

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC KHOA HỌC - ĐẠI HỌC THÁI NGUYÊN VŨ ÁNH TUYẾT PHÉP CHIẾU XUỐNG TẬP LỒI VÀ MỘT SỐ ỨNG DỤNG LUẬN VĂN THẠC SỸ Chuyên ngành : TOÁN ỨNG DỤNG Mã số : 60 46 0112 Giáo viên hướng dẫn: GS.TSKH LÊ DŨNG MƯU THÁI NGUYÊN, 2012 1Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Lời cảm ơn Luận văn này được hoàn thành tại trường Đại Học Khoa Học - Đại Học Thái Nguyên. Tác giả xin bầy tỏ lòng biết ơn chân thành và sâu sắc tới thầy GS.TSKH Lê Dũng Mưu (Viện Toán học), thầy đã trực tiếp hướng dẫn tận tình và động viên tác giả trong suốt thời gian nghiên cứu và viết luận văn vừa qua. Tác giả xin chân thành cảm ơn các thầy cô giáo trong khoa Toán - Tin, Phòng Đào tạo khoa học và Quan hệ quốc tế, các bạn học viên lớp cao học Toán K4 trường Đại Học Khoa Học - Đại Học Thái Nguyên đã tạo điều kiện thuận lợi, động viên tác giả trong quá trình học tập và nghiên cứu tại trường. Tác giả cũng xin bầy tỏ lòng biết ơn sâu sắc tới gia đình và người thân đã luôn khuyến khích và động viên tác giả trong suốt quá trình học cao học và viết luận văn. Mặc dù có nhiều cố gắng nhưng luận văn khó tránh khỏi những thiếu sót và hạn chế. Tác giả mong nhận được những ý kiến đóng góp của các thầy cô và bạn đọc để luận văn được hoàn thiện hơn. Xin chân thành cảm ơn. Thái nguyên, ngày 10 tháng 10 năm 2012. Tác giả Vũ Ánh Tuyết 2 2Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Mục lục Lời cảm ơn 2 Một số ký hiệu và chữ viết tắt 4 Mở đầu 5 1 Một số kiến thức cơ bản 1.1 Kiến thức cơ bản về không gian Hilbert . . . . . 1.1.1 Không gian Hilbert thực . . . . . . . . . 1.1.2 Khai triển trực giao và hệ trực chuẩn . . 1.1.3 Phiếm hàm tuyến tính và song tuyến tính 1.1.4 Toán tử đối xứng hoàn toàn liên tục . . . 1.2 Kiến thức cơ bản về tập lồi . . . . . . . . . . . . 1.2.1 Các tính chất cơ bản về tập lồi . . . . . . 1.2.2 Các tính chất cơ bản về hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Phép chiếu xuống tập lồi đóng 2.1 Kiến thức cơ bản về phép chiếu xuống tập lồi . . . . . . . . 2.1.1 Phép chiếu xuống tập lồi . . . . . . . . . . . . . . . 2.1.2 Tính chất . . . . . . . . . . . . . . . . . . . . . . . 2.1.3 Hình chiếu của một điểm xuống một số tập quen thuộc 2.2 Một số ứng dụng của phép chiếu . . . . . . . . . . . . . . . 2.2.1 Định lý tách tập lồi . . . . . . . . . . . . . . . . . . 2.2.2 Sự tồn tại dưới vi phân . . . . . . . . . . . . . . . . 2.2.3 Giải bài toán bất đẳng thức biến phân . . . . . . . . 6 6 6 8 11 12 13 14 17 25 25 25 26 28 31 31 34 39 Kết luận 48 Tài liệu tham khảo 49 3 3Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Một số ký hiệu và chữ viết tắt R: không gian thực x := y : x được định nghĩa bằng y ∀x : với mọi x ∃x : tồn tại x kxk : chuẩn của vectơ x T hx, yi = x y : tích vô hướng của hai vectơ x và y A: bao đóng của A. coA : bao lồi của A. coA : bao lồi đóng của A. coneA : bao nón lồi của A. coneA : bao nón lồi đóng của A. af f (A) : bao affine của tập A. ri(A) : tập điểm trong tương đối của tập A. V (A) : tập các điểm cực biên (đỉnh) của A. re(A) : nón lùi xa của A. intA : tập hợp các điểm trong của A. domf : tập hữu dụng của f . ∗ f : hàm liên hợp của f . epif : trên đồ thị của f . ∂f (x): dưới vi phân của f tại x. 0 f (x, d) : đạo hàm theo hướng d của f tại x. A⊂B : tập A là tập con thực sự của tập B . A⊆B : tập A là tập con của tập B . A∪B : A hợp với B A∩B : A giao với B A×B : tích Đề - các của hai tập A và B T A : ma trận chuyển vị của ma trận A k x →x: dãy xk hội tụ mạnh đến x xk *x : dãy xk hội tụ yếu đến x 4 4Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Mở đầu Giải tích lồi là bộ môn cơ bản của giải tích hiện đại, nghiên cứu về tập lồi và hàm lồi cùng những vấn đề liên quan. Bộ môn này có vai trò quan trọng trong nhiều lĩnh vực khác nhau của toán học ứng dụng, đặc biệt là trong tối ưu hóa, bất đẳng thức biến phân, các bài toán cân bằng,... Một trong những vấn đề quan trọng của giải tích lồi đó là phép chiếu lên một tập lồi đóng. Đây là một công cụ sắc bén và khá đơn giản để chứng minh nhiều định lý quan trọng như định lý tách, định lý xấp xỉ tập lồi, định lý về sự tồn tại nghiệm của bất đẳng thức biến phân,... Những cách chứng minh dựa vào phép chiếu thường mang tính chất kiến thiết, gợi mở đến nhiều vấn đề khác. Trong luận văn này, tác giả tập trung vào việc trình bầy định nghĩa, tính chất cùng những ứng dụng quan trọng của phép chiếu. Luận văn bao gồm 2 chương. Trong chương 1, trình bầy một số kiến thức cơ sở về không gian Hilbert, về tập lồi và hàm lồi. Chúng là những công cụ cơ bản nhất cho những nghiên cứu được trình bầy trong luận văn. Chương 2 là chương chính của luận văn. Trong chương này, tác giả trình bầy về khái niệm, tính chất cơ bản của phép chiếu. Trong quá trình nghiên cứu chúng ta biết rằng hình chiếu vuông góc của một điểm lên tập lồi đóng, khác rỗng trong không gian Hilbert luôn tồn tại và duy nhất. Dựa vào đó, tác giả đề cập đến những ứng dụng của nó, cụ thể là chứng minh định lý tách, chứng minh sự tồn tại dưới vi phân của hàm lồi, giải bài toán bất đẳng thức biến phân trong không gian Hilbert. 5 5Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Chương 1 Một số kiến thức cơ bản Trong chương này, ta sẽ trình bày những kiến thức cơ bản về không gian Hilbert, tập lồi và hàm lồi. Các kiến thức này được lấy từ các tài liệu [1,2,4,5]. 1.1 Kiến thức cơ bản về không gian Hilbert Trong phần này ta sẽ xét X là một không gian Hilbert thực. Sau đây ta nhắc lại một số kiến thức liên quan. 1.1.1 Không gian Hilbert thực Định nghĩa 1.1. Cho X là một không gian tuyến tính trên trường số thực R. Một tích vô hướng trong X là một ánh xạ được kí hiệu h., .i : X × X → R thỏa mãn các điều kiện sau đây: 1) hx, xi ≥ 0∀x ∈ X; hx, xi = 0 ⇔ x = 0; 2) hx, yi = hy, xi ∀x, y ∈ X; 3) hx1 + x2 , yi = hx1 , yi + hx2 , yi ∀x1 , x2 , y ∈ X; 4) hαx, yi = α hx, yi ∀x, y ∈ X, α ∈ R. Khi đó, không gian tuyến tính X h., .i được gọi là không gian tiền Hilbert. Ví dụ 1.1. Không gian C[a,b] gồm tất cả các hàm liên tục trên đoạn [a, b] 6 6Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn với các phép toán thông thường và với tích vô hướng cho bởi: hx, yi = Zb x(t)y(t)dt a là một không gian tiền Hilbert. Định nghĩa 1.2. Không gian đầy đủ là không gian mà mọi dãy Cauchy đều hội tụ. Ví dụ 1.2. i) Không gian C[a,b] với chuẩn kxk1 = max |x(t)| là không gian đầy đủ. !1/ 2 b R 2 không là không ii) Không gian C[a,b] với chuẩn kxk2 = |x(t)| dt a gian đầy đủ. Định nghĩa 1.3. Không gian tiền Hilbert đầy đủ được gọi là không gian Hilbert. !1/ 2 b R 2 2 |x(t)| dt là một Ví dụ 1.3. i) Không gian L[a,b] với chuẩn kxk2 = a không gian Hilbert. ii) Không gian l2 với chuẩn kxk =  ∞ P 2 |ξn | 1/ 2 < +∞, x = (ξ1 , ..., ξn ) n=1 là một không gian Hilbert. Nhận xét 1.1. i) Không gian tiền Hilbert là không gian định chuẩn với 1 chuẩn kxk = hx, xi /2 . ii) Không gian tiền Hilbert luôn có bất đẳng thức Schwars: khx, yik ≤ kxk . kyk iii) Không gian tiền Hilbert luôn thỏa mãn điều kiện bình hành:   2 2 2 2 kx + yk + kx − yk = 2 kxk + kyk iv) Tích vô hướng (x, y) là một hàm số liên tục đối với biến x và y . 7 7Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1.1.2 Khai triển trực giao và hệ trực chuẩn Định nghĩa 1.4. i) Hai vectơ x và y của một không gian Hilbert X được gọi là trực giao với nhau nếu hx, yi = 0 và được kí hiệu là x⊥y . ii) Phần tử x của không gian Hilbert X được gọi là trực giao với một tập M nếu x trực giao với tất cả các phần tử của M . iii) Tập tất cả các vectơ trực giao với tập M làm thành một không gian con đóng của X . Kí hiệu: M ⊥ = {x ∈ X |x⊥M } và được gọi là phần bù trực giao của M . Từ định nghĩa trên ta có thể suy ra một số tính chất đơn giản sau: Tính chất 1.1. Nếu x⊥y thì y⊥x. Ta có x⊥x khi và chỉ khi x = 0. Vectơ 0 trực giao với mọi vectơ x. Chứng minh. Thật vậy, x⊥y ⇔ hx, yi = 0. Suy ra: hy, xi = 0 ⇔ y⊥x. +) x⊥x ⇔ hx, xi = 0 ⇔ x = 0∀x ∈ X . +) Ta có: h0, xi = 0 ⇔ 0⊥x∀x ∈ X . Tính chất 1.2. Nếu x⊥y1 , x⊥y2 , ..., x⊥yn thì x trực giao với một tổ hợp tuyến tính của y , tức là x⊥(α1 y1 + α2 y2 + ... + αn yn )∀αi ∈ R. Chứng minh. Thật vậy, xét: hx, α1 y1 + α2 y2 + ... + αn yn i = (x, α1 y1 ) + (x, α2 y2 ) + ... (x, αn yn ) = α1 (x, y1 ) + α2 (x, y2 ) + ... + αn (x, yn ) = 0 Do đó, x⊥(α1 y1 + α2 y2 + ... + αn yn )∀αi ∈ R. Tính chất 1.3. Nếu x⊥yn , lim yn = y thì x⊥y . n→∞ Chứng minh. Ta có: x⊥yn ⇔ (x, yn ) = 0 ⇔ lim (x, yn ) = 0. Do X là n→∞ không gian Hilbert nên tích vô hướng là một hàm liên tục hai biến. Do đó, (x, y) = lim (x, yn ) = 0 nên x⊥y . n→∞ Tính chất 1.4. Nếu x⊥y thì kx + yk2 = kxk2 + kyk2 (định lý Pytago). Chứng minh. Thật vậy, do x⊥y nên (x, y) = 0. Do đó, kx + yk2 = (x + y, x + y) = (x, x) + 2 (x, y) + (y, y) = kxk2 + kyk2 . Bằng quy nạp ta chứng minh tổng quát hơn, nếu các vectơ x1 , x2 , ..., xn n n P P 2 đôi một trực giao với nhau và x = xi thì kxk = kxi k2 . i=1 8 8Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên i=1 http://www.lrc-tnu.edu.vn Tính chất 1.5. Nếu {xn } là một hệ trực giao (nghĩa là các vectơ trực ∞ ∞ P P giao từng đôi một) thì chuỗi xn hội tụ khi và chỉ khi chuỗi số kxn k2 n=1 n=1 hội tụ. Chứng minh. Thật vậy, cho Sn = n P 0 xk , Sn = k=1 n P kxk k2 k=1 Với mọi n > m đủ lớn, theo định lý Pytago ta có:  0  0  kSn − Sm k = kxm+1 + ... + xn k = kxm+1 k + ... + kxn k = Sn − Sm  2 2 2 2 Vì không gian Hilbert là không n 0 ogian đủ nên từ kSn − Sm k → 0 ta suy ra {Sn } hội tụ khi và chỉ khi Sn hội tụ. Định lý 1.1. Cho M là một không gian con đóng của một không gian Hilbert X . Bất kỳ phần tử x nào của X cũng có thể biểu diễn một cách duy nhất dưới dạng x = y + z, y ∈ M, z ∈ M ⊥ (1.1) trong đó y là phần tử của M gần x nhất tức là kx − yk ≤ kx − uk với mọi u ∈ M. Chứng minh. Có thể thấy ngay rằng phân tích (1.1) nếu có phải là duy nhất vì nếu x = y + z = y 0 + z 0 với y, y 0 ∈ M ; z, z 0 ∈ M ⊥ thì y − y 0 = z 0 − z mà M, M ⊥ đều là không gian con nên y − y 0 ∈ M ; z 0 − z ∈ M ⊥ tức là (y 0 − y)⊥(z 0 − z), do đó y − y 0 = z 0 − z = 0. Thành thử vấn đề chủ yếu là sự tồn tại của phân tích (1.1). Ta nhận xét rằng: Trong trường hợp riêng X = R2 và M là một đường thẳng thì định lý nói lên một sự kiện quen thuộc. Trong trường hợp tổng quát ta đặt: d = inf kx − uk u∈M Theo định nghĩa cận dưới đúng, tồn tại một dãy un ∈ M sao cho kx − un k → d(n → ∞). Áp dụng đẳng thức bình hành cho x − un và x − um ta có: k2x − (un + um )k2 + kum − un k2 = 2kx − un k2 + 2kx − um k2 . 2 Khi n,um+u→ 2 ∞ thì2 vế 1 phải dần tới 4d còn phần đầu vế trái bằng 4 x − n 2 m ≥ 4d vì 2 (un + um ) ∈ M . 9 9Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Vậy, khi n, m → ∞ thì kun − um k → 0, do đó un dần tới một giới hạn y nào đó. Ta có y ∈ M vì M đóng và kx − yk = lim kx − un k = d. n→∞ Bây giờ ta đặt z = x − y và tìm cách chứng minh z ∈ M ⊥ . Muốn thế, xét một phần tử u bất kỳ của M . Ta có, với mọi số thực α: (z − αu, z − αu) = kzk2 − 2α (z, α) + α2 kuk2 Mà y+αu ∈ M nên (z − αu, z − αu) = kz − αuk2 = −kx − (y + αu)k2 ≥ d2 . Mặt khác, kzk2 = kx − yk2 = d2 , do đó với mọi số thực α: −2α (z, α) + α2 kuk2 ≥ d2 − d2 = 0 Điều này chỉ có thể xảy ra nếu (z, u) = 0 tức là z⊥u. Vậy, z ∈ M ⊥ (đpcm). Vectơ y trong phân tích (1.1) gọi là hình chiếu của x lên không gian con M . Đó là khoảng cách nhỏ nhất từ M tới x. Đặt P x = y , ta xác đinh một toán tử P gọi là toán tử chiếu lên M : P :X→M x7→P x=y Rõ ràng, P là một toán tử tuyến tính liên tục vì kP xk ≤ kxk. Định nghĩa 1.5. Một hệ {en } các phần tử của không gian Hilbert X được gọi là hệ trực chuẩn nếu (ei , ej ) = δij trong đó δij = 1 nếu i = j và δij = 0 nếu i khác j. Như vậy một hệ trực chuẩn là một hệ trực giao và chuẩn hóa ke i k = 1∀i. Khi {en } là một hệ trực chuẩn thì với mọi x ∈ X , số ζi = (x, ei ) được gọi ∞ P là hệ số Fourier của x đối với ei và chuỗi ζi ei được gọi là chuỗi Fourier i=1 của x theo hệ {en }. Ta có các tính chất sau: ∞ P i) ζi 2 ≤ kxk2 (Bất đẳng thức Besel). i=1 ii) Chuỗi ∞ P i=1 ζi ei hội tụ và (x − ∞ P ζi ei )⊥en . i=1 Một hệ trực chuẩn {en } gọi là đầy đủ khi chỉ có vectơ 0 mới trực giao với tất cả các phần tử của hệ x⊥en (n = 1, 2, ...). Suy ra x = 0. Định lý 1.2. Cho {en } là một hệ trực chuẩn, ζn = (x, en ) là các hệ số Fourier của x đối với en . Các mệnh đề sau là tương đương: 10 10Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1) {en } là một hệ trực chuẩn đầy đủ. ∞ P ζi ei ∀x ∈ X . 2) x = i=1 ∞ P 2 3) kxk = ζi 2 ∀x ∈ X . i=1 ∞ P 4) (x, y) = ζi ηi , ∀x, y ∈ X trong đó ηn = (y, en ) là các hệ số Fourier i=1 của y đối với en . 5) Hệ {en } tuyến tính trù mật trong X , nghĩa là họ các tổ hợp tuyến tính của các en ( bao tuyến tính của hệ {en }) là trù mật trong X . Định lý 1.3. ( Riesz - Fischer) Cho {en } là một hệ trực chuẩn trong không ∞ P gian Hilbert X . Nếu một dãy số {ζn } thỏa mãn điều kiện ζi ≤ ∞ thì i=1 sẽ có duy nhất một vectơ x ∈ X nhận các ζi làm các hệ số Fourier và x= ∞ X ζi ei ∀x ∈ X i=1 2 kxk = ∞ X ζi 2 ∀x ∈ X i=1 . 1.1.3 Phiếm hàm tuyến tính và song tuyến tính Ta có dạng tổng quát của phiếm hàm tuyến tính liên tục trên không gian Hilbert như sau: Định lý 1.4. ( Riesz ) Với mỗi vectơ a cố định thuộc một không gian Hilbert X , hàm số f (x) = (a, x) xác định một phiếm hàm tuyến tính liên tục f (x) trên không gian X với kf k = kak. Ngược lại, bất kỳ phiếm hàm tuyến tính liên tục f (x) nào trên không gian Hilbert X cũng đều có thể biểu diễn một cách duy nhất dưới dạng f (x) = (a, x) trong đó a là một vectơ của X thỏa mãn điều kiện kf k = kak. Từ định lý trên ta suy ra hệ quả như sau: Hệ quả 1.1. Mỗi toán tử tuyến tính liên tục A trong không gian Hilbert X xác định f (x, y) = (Ax, y) một phiếm hàm song tuyến tính liên tục f (x, y) nghiệm đúng kf k = kAk. 11 11Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Ngược lại, bất kỳ phiếm hàm song tuyến tính liên tục f (x, y) nào trên một không gian Hilbert X cũng đều có thể biểu diễn một cách duy nhất dưới dạng f (x, y) = (Ax, y) trong đó A là một toán tử tuyến tính liên tục trên X thỏa mãn điều kiện kf k = kAk. 1.1.4 Toán tử đối xứng hoàn toàn liên tục Cho một toán tử tuyến tính liên tục A trong không gian Hilbert X . Ta có (Ax, y) là một phiếm hàm song tuyến tính liên tục, cho nên có một toán tử tuyến tính liên tục duy nhất A∗ sao cho: (Ax, y) = (x, A∗ y). Ta gọi toán tử A∗ là toán tử liên hợp của toán tử A và kA∗ k = kAk Ta có các tính chất sau: i)(A∗ )∗ = A ii)(A + B)∗ = A∗ + B ∗ (αA)∗ = αA∗ iii)(AB)∗ = B ∗ A∗ . Một toán tử tuyến tính liên tục A gọi là đối xứng nếu với mọi x, y ta có (Ax, y) = (x, Ay). Khi đó A = A∗ nên A được gọi là toán tử tự liên hợp. Ta nói một số λ là trị riêng của toán tử A nếu phương trình Ax = λx có nghiệm x không tầm thường. Khi ấy, nghiệm x này gọi là một vectơ riêng của A ứng với trị riêng λ. iv) Tập hợp tất cả các vectơ riêng của toán tử tuyến tính liên tục A ứng với cùng một trị riêng λ cùng với phần tử 0 làm thành một không gian con đóng của X bất biến đối với A. Không gian con này gọi là không gian con riêng ứng với trị riêng λ. v) Nếu A là một toán tử đối xứng thì các vectơ riêng của A ứng với hai trị riêng khác nhau bao giờ cũng trực giao với nhau. vi) Nếu A là một toán tử đối xứng thì phần bù trực giao của mọi không gian con bất biến đối với A cũng bất biến đối với A. Tiếp theo là khái niệm toán tử hoàn toàn liên tục. Định nghĩa 1.6. Nếu A là một toán tử tuyến tính liên tục trong không gian Hilbert X thì kxk ≤ K ⇒ kAxk ≤ kAk K 12 12Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn nghĩa là A biến mỗi tập bị chặn thành một tập bị chặn. Một toán tử tuyến tính A trong không gian Hilbert X là hoàn toàn liên tục nếu nó biến một tập bị chặn thành một tập hoàn toàn bị chặn. Ta có các tính chất sau: i) Nếu toán tử A hoàn toàn liên tục, toán tử B liên tục (tức là bị chặn) thì các toán tử AB, BA cũng hoàn toàn liên tục. ii) Nếu toán tử A hoàn toàn liên tục thì các toán tử A∗ , AA∗ , A∗ A cũng hoàn toàn liên tục. iii) Nếu toán tử A hoàn toàn liên tục và kAN − Ak → 0 thì các toán tử AN cũng hoàn toàn liên tục. Ta xét một toán tử A vừa đối xứng vừa hoàn toàn liên tục trong không gian Hilbert X . Khi đó, ta có các tính chất sau: i) Một toán tử đối xứng hoàn toàn liên tục A bao giờ cũng có một trị riêng λ với kλk = kAk. ii) Tập các trị riêng của một toán tử đối xứng hoàn toàn liên tục cùng lắm là đếm được. Nếu là đếm được thì tập đó làm thành một dãy hội tụ đến 0. Định lý 1.5. ( Hilbert ) Nếu A là một toán tử đối xứng hoàn toàn liên tục thì mọi x ∈ X đều có thể biểu diễn thành tổng trực giao: X x= (x, ej ) + z j trong đó mỗi ej là một vectơ riêng ứng với một trị riêng khác 0 và Az = 0. Do đó mọi phần tử có dạng Ax đều có thể phân tích ra được theo các vectơ riêng tương ứng với các trị riêng khác 0: X X Ax = (Ax, ej ) + z = λj (x, ej )ej . j j Từ định lý trên ta suy ra hệ quả như sau: Hệ quả 1.2. Trong không gian Hilbert tách được, mọi toán tử đối xứng hoàn toàn liên tục đều có một hệ trực chuẩn đầy đủ vectơ riêng. 1.2 Kiến thức cơ bản về tập lồi Giải tích lồi đóng vai trò quan trọng trong việc nghiên cứu, phân tích và xây dựng các thuật toán giải bài toán cân bằng. Trong phần này ta 13 13Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn nhắc lại một số kiến thức về giải tích lồi. Định nghĩa 1.7. Xét dãy {xn }n≥0 và x thuộc không gian Hilbert thực X . Khi đó: i) Dãy {xn } được gọi là hội tụ mạnh tới x, ký hiệu là xk → x nếu lim kxn − xk = 0. n→+∞ ii) Dãy {xn } được gọi là hội tụ yếu tới x, ký hiệu là xk * x nếu lim hw, xn i = hw, xi , ∀w ∈ X. n→+∞ iii) Điểm x được gọi là điểm tụ mạnh (yếu) của dãy {xn } nếu từ dãy này có thể trích ra một dãy con hội tụ mạnh (yếu) tới x. Mệnh đề 1.1. i) Nếu dãy {xn } hội tụ mạnh tới x thì cũng hội tụ yếu tới x. ii) Nếu dãy {xn } hội tụ yếu tới x và lim kxn k = kxk thì dãy {xn } hội n→+∞ tụ mạnh tới x. iii) Mọi dãy hội tụ mạnh (yếu) đều bị chặn và giới hạn theo sự hội tụ mạnh (yếu) nếu tồn tại là duy nhất. iv) Nếu không gian Hilbert X là không gian hữu hạn chiều thì sự hội tụ mạnh và sự hội tụ yếu là tương đương. v) Nếu {xn }n≥0 là một dãy bị chặn trong không gian Hilbert X thì ta trích ra được một dãy con hội tụ yếu. vi) Nếu {xn }n≥0 là một dãy bị chặn trong không gian Hilbert hữu hạn chiều X thì ta trích ra được một dãy con hội tụ mạnh. Tiếp theo ta nhắc lại một số định nghĩa và kết quả cơ bản về tập lồi và hàm lồi. 1.2.1 Các tính chất cơ bản về tập lồi Định nghĩa 1.8. i) Một đường thẳng nối hai điểm (hai vectơ) a và b trong không gian Hilbert X là tập hợp tất cả các vectơ x ∈ X có dạng {x ∈ X| x = (1 − λ) a + λb, λ ∈ R} 14 14Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ii) Đoạn thẳng nối hai điểm (hai vectơ) a và b trong không gian Hilbert X là tập hợp tất cả các điểm (vectơ) x ∈ X có dạng {x ∈ X| x = (1 − λ) a + λb, 0 ≤ λ ≤ 1} iii) Một tập M được gọi là tập affine (đa tạp affine) nếu nó chứa đường thẳng đi qua hai điểm bất kỳ của nó, tức là ∀x, y ∈ M, ∀λ ∈ R ⇒ λx + (1 − λ)y ∈ M . Nhận xét 1.2. i) Nếu M là tập affine thì a + M = {a + x | x ∈ M } cũng là một tập affine với ∀a ∈ Rn . ii) M là tập affine chứa gốc khi và chỉ khi M là không gian con. iii, Tập affine là trường hợp riêng của tập lồi. Định nghĩa 1.9. i) Thứ nguyên (hay chiều) của không gian con song song với tập affine M được gọi là thứ nguyên (hay chiều) của một đa tạp affine M và được kí hiệu là dimM . ii) Siêu phẳng trong không gian Hilbert X là một tập affine có số chiều bằng (n-1), hay chính là tập có dạng {x ∈ X | aT x =α} trong đó 0 6= a ∈ X và α ∈ R. Vectơ a được gọi là vectơ pháp tuyến của siêu phẳng. Trong trong không gian Hilbert X , siêu phẳng {x ∈ X | aT x =α} với 0 6= a ∈ X và α ∈ R chia X thành hai nửa không gian đóng {x ∈ X | aT x ≤ α}, {x ∈ X | aT x ≥ α} Mỗi nửa không gian này nằm về một phía của siêu phẳng và phần chung của chúng chính là siêu phẳng. Tương tự, siêu phẳng cũng chia X thành hai nửa không gian mở {x ∈ X | aT x < α}, {x ∈ X | aT x > α} Ví dụ 1.4. i) Điểm a ∈ Rn là tập affine có số chiều bằng 0 vì không gian con song song với M = {a} là L = {0}. ii) Trong không gian hai chiều, siêu phẳng là đường thẳng. Trong không gian 3 chiều, siêu phẳng là mặt phẳng. Định nghĩa 1.10. i) Một tập C trong không gian Hilbert X được gọi là tập lồi nếu C chứa mọi đoạn thẳng nối hai điểm thuộc nó, tức là tập C lồi khi và chỉ khi ∀x, y ∈ C, ∀λ ∈ [0, 1] ta có λx + (1 − λ)y ∈ C . ii) Bao lồi của tập C là tập lồi nhỏ nhất chứa C , ký hiệu là CoC , đây 15 15Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn chính là giao của tất cả các tập lồi chứa C . iii) Cho hai tập A, B bất kỳ trong không gian Hilbert X , tổ hợp lồi của các tập A và B là tập các điểm thuộc không gian Hilbert X có dạng x = λa + (1 − λ)b, a ∈ A, b ∈ B, 0 ≤ λ ≤ 1. Lớp các tập lồi là đóng đối với phép giao, phép cộng đại số và phép nhân tích Decartes, cụ thể ta có định lý sau: Định lý 1.6. Nếu A, B là các tập lồi trong không gian Hilbert X , C là lồi trong gian Hilbert Y , thì các tập sau là tập lồi: i) A ∩ B := {x |x ∈ A, x ∈ B }. ii) αA + βB := {x |x = αa + βb, a ∈ A, b ∈ B, α, β ∈ R}. iii) A × C := {x ∈ A ∪ C |x = (a, c), a ∈ A, c ∈ C } Định nghĩa 1.11. i) Cho C là tập lồi, tập affine nhỏ nhất chứa C được gọi là bao affine của C, ký hiệu là af f C . ii) Thứ nguyên của tập lồi C ký hiệu là dimC được cho bởi thứ nguyên của bao affine của C. iii) Một điểm a ∈ C được gọi là điểm trong của C nếu tồn tại một lân cận mở U của a sao cho U ⊂ C , tập hợp các điểm trong của C ký hiệu là intC . iv) Một tập lồi C trong không gian Hilbert X có thể không có điểm trong (khi xét trong gian Hilbert X ), nhưng nó luôn có điểm trong khi xét trong af f C , điểm trong này gọi là điểm trong tương đối. Nếu ký hiệu riC là tập các điểm trong tương đối của C thì riC := {x ∈ affC |∃ U, U ∩ affC ⊂ C} trong đó U là một lân cận mở của x. Định nghĩa 1.12. i) Một tập hợp là giao của một số hữu hạn các nửa không gian đóng được gọi là tập lồi đa diện (khúc lồi). Như vậy, dạng tường minh của một tập lồi đa diện D được cho như sau  D = {x ∈ X < aj , x >≤ bj , j = 1, 2, .., n}. ii) Một tập con C 0 của C được gọi là một diện của C nếu nó chứa một điểm trong của một đoạn thẳng thì nó chứa cả đoạn thẳng đó, tức là ∀a, b ∈ C nếu x = λa + (1 − λ)b, 0 < λ < 1, x ∈ C 0 thì a, b ∈ C 0 . 16 16Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Một diện có thứ nguyên bằng 0 được gọi là đỉnh hay điểm cực biên. Cạnh là một diện có thứ nguyên bằng 1. iii) Đối với một tập C bất kỳ, một điểm x ∈ C được gọi là điểm biên của C nếu không tồn tại a, b ∈ C, 0 < λ < 1 sao cho x = λa + (1 − λ)b và đoạn thẳng [a, b] ⊂ C . Với một tập lồi đa diện, một đỉnh của diện cũng chính là đỉnh của tập đó. iv) Một tập C được gọi là nón nếu ∀x ∈ C , t ≥ 0 thì tx ∈ C . v) Một tập C được gọi là nón lồi nếu ∀x, y ∈ C thì x + y ∈ C và tx ∈ C với mọi t ≥ 0 Định nghĩa 1.13. i) Cho C là một tập lồi trong không gian Hilbert X , một vectơ y 6= 0 được gọi là hướng lùi xa của C nếu mọi tia xuất phát từ một điểm bất kỳ của C theo hướng y đều nằm trọn trong C , tức là y 6= 0 là hướng lùi xa khi và chỉ khi x + λy ∈ C, ∀x ∈ C, ∀λ ≥ 0. ii) Tập tất cả các hướng lùi xa của C cùng với điểm gốc được gọi là nón lùi xa của C , ký hiệu là reC . iii) Cho C là một tập lồi trong không gian Hilbert X và x ∈ C , tập hợp NC (x) = {w |< w, y − x >≤ 0, ∀y ∈ C} được gọi là nón pháp tuyến ngoài của C tại x. iv) Tập hợp −NC (x) = {w |< w, y − x >≥ 0, ∀y ∈ C} được gọi là nón pháp tuyến trong của C tại x. v) Tập hợp C ∗ = {w |< w, x >≥ 0, ∀x ∈ C} được gọi là nón đối cực của C . Đây cũng là một nón lồi đóng chứa gốc. vi) Cho C là một tập lồi khác rỗng và x thuộc C . Ta nói d ∈ X là một hướng chấp nhận được của C nếu tồn tại t0 > 0 sao cho x + td ∈ C với mọi 0 ≤ t ≤ t0 . Tập tất cả các hướng chấp nhận được của C tại x ký hiệu là FC (x) và gọi là nón chấp nhận được của C tại x. 1.2.2 Các tính chất cơ bản về hàm lồi Từ phần này trở đi, nếu không nói gì thêm, ta luôn xét hàm thực, nhận giá trị hữu hạn, xét trong không gian Hilbert X . 17 17Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Định nghĩa 1.14. i) Cho C ⊆ X là tập lồi và f : C → R ∪ {+∞}. Ta ký hiệu domf := {x ∈ C | f (x) < +∞} và gọi là miền hữu dụng của f . Nếu domf 6= ∅ và f (x) > −∞ thì f được gọi là hàm lồi chính thường. ii) Tập epif := {(x, µ) ∈ C × R | f (x) ≤ µ} được gọi là trên đồ thị của hàm f . Định nghĩa 1.15. Cho ∅ = 6 C ⊆ X là một tập lồi và f : X → R ∪ {+∞}. i) Ta nói f là hàm lồi xác định trên C nếu f [λx + (1 − λ)y] ≤ λf (x) + (1 − λ)f (y), ∀x, y ∈ C, ∀λ ∈ (0, 1). ii) Hàm f được gọi là lồi chặt trên C nếu f [λx + (1 − λ)y] < λf (x) + (1 − λ)f (y), ∀x, y ∈ C, ∀λ ∈ (0, 1). iii) Hàm f được gọi là hàm lõm (lõm chặt) trên C nếu −f là hàm lồi (lồi chặt) trên C . iv) Hàm f được gọi là lồi mạnh với hệ số β > 0 trên C nếu f [λx+(1−λ)y] ≤ λf (x)+(1−λ)f (y)−β (1 − λ) kx − yk2 , ∀x, y ∈ C, ∀λ ∈ (0, 1). vi) Hàm f được gọi là tựa lồi trên C nếu ∀λ ∈ R, tập mức {x ∈ C |f (x) ≤ λ} là tập lồi. v) Hàm f được gọi là hàm tựa lõm trên C nếu −f là hàm tựa lồi trên C . Ví dụ 1.5. 1) Trong không gian Hilbert thực X , ta có khai triển: 2 2 2 kyk kλx+(1−λ)yk λ kxk 2 +2 (1 − λ) 2 − 2 2 2 2 kxk kyk 2 kyk 2 kxk =λ 2 + (1 − λ) − λ + (1 − λ) 2 2 2 − λ (1 − λ) hx, yi   = λ(1−λ) kxk2 + kyk2 − 2 hx, yi 2 = λ(1−λ) 2 kx − yk2 2 Do đó, hàm f (x) = kxk 2 là hàm lồi mạnh với hệ số 1. 2) Hàm affine: f (x) = aT x + α, trong đó α ∈ X, α ∈ R. Dễ dàng kiểm tra được rằng f là một hàm vừa lồi vừa lõm trên toàn không gian. Khi α = 0 18 18Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn thì hàm này được gọi là hàm tuyến tính. 3) Hàm chỉ: Cho C 6= ∅ là một tập lồi. Đặt  0 nếu x ∈ C δC (x) = +∞ nếu x ∈ /C Ta nói δC là hàm chỉ của C . Do C lồi nên δC là một hàm lồi. 4) Hàm mặt cầu: Cho S := {x ∈ X| kxk = 1} là một mặt cầu và h : S → R+ là môt hàm bất kỳ. Định nghĩa hàm f như sau:   0 nếu kxk < 1 f (x) = h (x) nếu kxk = 1  +∞ nếu kxk > 1 Hàm này được gọi là hàm mặt cầu. Dễ thấy rằng f là một hàm lồi trên X mặc dù h là một hàm không âm bất kỳ trên mặt cầu S . Lớp các hàm lồi là đóng đối với phép lấy tổ hợp tuyến tính không âm và phép lấy max, cụ thể: Định lý 1.7. Cho f là hàm lồi trên tập A và g là hàm lồi trên tập B . Khi đó các hàm sau là lồi trên tập A ∩ B : i) αf + βg, ∀α, β > 0. ii) max{f, g}. Định lý trên nhìn chung không đúng cho hàm tựa lồi. Định lý sau đây cho phép kiểm tra tính lồi của một hàm số: Định lý 1.8. Cho f : C → X là một hàm khả vi trên tập lồi mở C . Điều kiện cần và đủ để f lồi trên C là: f (x) + h∇f (x), y − xi ≤ f (y), ∀x, y ∈ C trong đó ký hiệu ∇f (a) là đạo hàm của f tại a. Nếu f khả vi hai lần thì điều kiện cần và đủ để f lồi trên C là với mọi x thuộc C , ma trận Hessian H(x) của f tại x xác định không âm, tức là: y T H(x)y ≥ 0, ∀x ∈ C, y ∈ X . Như vậy một dang toàn phương xT Qx là một hàm lồi khi và chỉ khi Q xác định không âm. Tiếp theo ta nêu các khái niệm liên quan đến tính liên tục và tính khả vi của hàm số: Định nghĩa 1.16. Xét hàm f : X → R. Khi đó: i) Một hàm f xác định trên tập X được gọi là nửa liên tục dưới tại điểm 19 19Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn x0 thuộc X nếu với mọi ε > 0, tồn tại δ > 0, sao cho f (x) ≥ f (x0 ) − ε, với mọi x ∈ X thỏa mãn x − x0 < δ . ii) Hàm f được gọi là nửa liên tục trên tại x0 nếu−f nửa liên tục dưới tại x0 . iii) Hàm f được gọi là liên tục tại điểm x0 nếu f vừa nửa liên tục trên vừa nửa liên tục dưới tại điểm này. iv) Hàm f được gọi là liên tục (nửa liên tục) trên X nếu nó liên tục (nửa liên tục) tại mọi điểm trên X . Định nghĩa 1.17. Xét hàm f : X → R. Khi đó: i) Hàm f được gọi là khả vi tại điểm x ∈ X nếu như tồn tại phần tử, ký hiệu là f 0 (x) ∈ X thỏa mãn: f (y) − f (x) − hf 0 (x) , y − xi lim =0 ky−xk→0 ky − xk Phần tử f 0 (x) được gọi là đạo hàm của f tại điểm x. ii) Hàm f được gọi là khả vi trên X nếu nó khả vi tại mọi điểm thuộc X . Lớp các hàm lồi là đóng đối với phép lấy tổ hợp tuyến tính không âm và phép lấy max, cụ thể: Định lý 1.9. Đối với một hàm lồi chính thường trên Rn và x0 ∈ int(domf ), các khẳng định sau đây là tương đương: (i) f liên tục tại điểm x0 . (ii) f bị chặn trong một lân cận của x0 . (iii) int(epif ) 6= ∅. (iv) int(domf ) 6= ∅ và f liên tục trên tập int(domf ). Mệnh đề 1.2. Xét hàm f : X → R. Khi đó: i) Nếu f liên tục thì f nửa liên tục dưới. ii) Nếu f khả vi thì f liên tục và f (x + ty) − f (x) = hf 0 (x) , yi , ∀x, y ∈ X t→0 t lim Chứng minh. i) Hiển nhiên. ii) Giả sử f khả vi. Xét x khác y bất kỳ thuộc X . Ta có: f (y) − f (x) − hf 0 (x) , y − xi f (y) − f (x) = ky − xk + hf 0 (x) , y − xi ky − xk 20 20Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn