Tài liệu Phương pháp dykstra lai ghép cho hai toán tử đơn điệu

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THỊ HOÀNG NGUYÊN PHƯƠNG PHÁP DYKSTRA LAI GHÉP CHO ,. HAI TOÁN TỬ ĐƠN ĐIỆU LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2015 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THỊ HOÀNG NGUYÊN PHƯƠNG PHÁP DYKSTRA LAI GHÉP CHO HAI TOÁN TỬ ĐƠN ĐIỆU Chuyên ngành: Toán ứng dụng Mã số: 60 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC GS.TS. NGUYỄN BƯỜNG Thái Nguyên - 2015 i Mục lục Lời cảm ơn ii Danh sách ký hiệu iii Mở đầu 1 1 Một số vấn đề cơ bản 3 1.1 Không gian Hilbert và các vấn đề liên quan . . . . . . . . 3 1.2 Một số vấn đề về giải tích lồi . . . . . . . . . . . . . . . . 11 1.3 Toán tử đơn điệu, nghiệm của phương trình toán tử đơn điệu và của bất đẳng thức biến phân trong không gian Hilbert 19 2 Phương pháp Dykstra lai ghép cho hai toán tử đơn điệu 2.1 Bài toán tìm giao điểm của hai không gian con đóng và thuật toán Neumann . . . . . . . . . . . . . . . . . . . . . 2.2 27 27 Phương pháp Dykstra tìm không điểm của tổng hai toán tử đơn điệu . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Kết luận 40 Tài liệu tham khảo 41 ii Lời cảm ơn Để hoàn thành được luận văn một cách hoàn chỉnh, tôi luôn nhận được sự hướng dẫn và chỉ bảo tận tình của GS.TS. Nguyễn Bường (Viện Công nghệ Thông tin - Viện Hàn lâm Khoa học và Công nghệ Việt Nam). Tôi xin chân thành bày tỏ lòng biết ơn và xin gửi lời tri ân sâu sắc nhất đến thầy. Tôi xin chân thành cảm ơn Ban lãnh đạo khoa Toán - Tin, phòng Đào tạo, quý thầy cô giảng dạy lớp cao học toán K7Y (01/2014–01/2016) trường Đại học Khoa học – Đại học Thái Nguyên đã tận tình truyền đạt những kiến thức quý báu và tạo điều kiện cho tôi trong quá trình học tập và nghiên cứu. Tôi xin gửi lời cảm ơn chân thành nhất tới gia đình, bạn bè, đồng nghiệp những người đã luôn động viên, hỗ trợ và tạo mọi điều kiện cho tôi trong suốt quá trình học tập và thực hiện luận văn. Trong quá trình thực hiện, mặc dù đã rất cố gắng luận văn không tránh khỏi những thiếu sót. Tôi rất mong nhận được sự góp ý của các Thầy, các Cô và các Độc giả quan tâm để luận văn được hoàn thiện hơn. Xin trân trọng cảm ơn! Thái Nguyên, 2015 Nguyễn Thị Hoàng Nguyên Học viên Cao học Toán Khóa 01/2014–01/2016, Trường ĐH Khoa học - ĐH Thái Nguyên iii Danh sách ký hiệu Trong toàn luận văn, ta dùng những ký hiệu với các ý nghĩa xác định trong bảng dưới đây: R không gian số thực H không gian Hilbert thực X∗ không gian đối ngẫu của X PC (x) phép chiếu trực giao của điểm x trên tập C hx, yi tích vô hướng của hai vectơ x và y kxk chuẩn của vectơ x xn → x xn hội tụ mạnh đến x xn * x xn hội tụ yếu x x := y x được gán bằng y spanC tổ hợp tuyến tính của C ∀ mọi ∃ tồn tại ∅ tập rỗng Id ánh xạ đơn vị. 1 Mở đầu Toán tử đơn điệu là một trong những công cụ được sử dụng nhiều và rất có hiệu quả trong lĩnh vực toán ứng dụng chẳng hạn như bất đẳng thức biến phân. Nó giúp ích cho việc nghiên cứu ánh xạ dưới gradient và gradient, chứng minh sự tồn tại và duy nhất nghiệm cho rất nhiều các lớp bài toán cân bằng, bài toán bất đẳng thức biến phân và bài toán tối ưu. Từ bài toán tìm giao điểm của hai không gian con đóng đã được chứng minh bởi nhà toán học Neumann trong thuật toán chiếu luân hướng cổ điển vào năm 1933. Và sau này nhà toán học Dykstra sử dụng phép chiếu lên hai tập đóng lồi của không gian Hilbert để xây dựng phép chiếu lặp lên giao của chúng. Đề tài của luận văn là trình bày cách tiếp cận đối ngẫu để mở rộng thuật toán của Dykstra nhằm xây dựng toán tử giải cho toán tử tổng hai toán tử đơn điệu cực đại từ các toán tử giải đơn điệu. Nội dung của luận văn được trình bày trong hai chương. Chương 1 giới thiệu một số kiến thức cơ bản về không gian Hilbert thực, giải tích lồi, phép chiếu trong không gian Hilbert, toán tử đơn điệu, nghiệm của phương trình toán tử đơn điệu và nghiệm của bất đẳng thức biến phân trong không gian Hilbert. Chương 2 gồm hai mục chính. Mục 2.1 nêu bài toán tìm giao điểm của hai không gian con đóng. Mục 2.2 trình bày về phương pháp Dykstra lai ghép cho hai toán tử đơn điệu cực đại. Qua quá trình hoàn thành luận văn, tác giả nhận thấy rằng luận văn chỉ thể hiện được một phần nhỏ các vấn đề được đề cập trong luận văn. Tuy 2 nhiên, thông qua việc trình bày luận văn tác giả được trau dồi những kiến thức khởi đầu định hướng cho sự tiếp cận các vấn đề sau này. Thái Nguyên, tháng 11 năm 2015 Nguyễn Thị Hoàng Nguyên Học viên cao học toán khóa 01/2014 – 01/2016 Chuyên ngành Toán ứng dụng Trường Đại học Khoa học - Đại học Thái Nguyên 3 Chương 1 Một số vấn đề cơ bản Trong chương này chúng tôi nhắc lại một số kiến tức cơ bản của giải tích hàm, giải tích lồi, toán tử đơn điệu và bài toán bất đẳng thức biến phân, có liên quan đến nội dung nghiên cứu của đề tài. Các kiến thức trong chương được tham khảo trong các tài liệu [1], [2], [3], [4], [6]. 1.1 Không gian Hilbert và các vấn đề liên quan Trong toàn bộ đề tài, chúng tôi chỉ đề cập đến không gian Hilbert thực, với tích vô hướng h., .i và chuẩn ||.||. Phép chiếu lên tập con U đóng lồi khác rỗng của H kí hiệu là PU và xn −→ x có nghĩa là dãy xn hội tụ mạnh đến x. 1.1.1. Định nghĩa và ví dụ Định nghĩa 1.1. Cho không gian tuyến tính H trên trường số thực R, ta gọi tích vô hướng trên không gian H là một ánh xạ đi từ tích Descartes H × H vào trường R ký hiệu h., .i thỏa mãn các điều kiện sau: a) hx, yi = hy, xi, ∀x, y ∈ H. b) hx + y, zi = hx, zi + hy, zi, ∀x, y, z ∈ H. c) hαx, yi = αhx, yi, ∀x, y ∈ H, ∀α ∈ R. 4 d) hx, xi > 0 nếu x 6= 0 và hx, xi = 0 nếu x = 0. Nhận xét 1.1. Từ định nghĩa ta suy ra 1) hx, λyi = λhy, xi, ∀x, y ∈ H; 2) hx, y + zi = hx, yi + hx, zi, ∀x, y, z ∈ H; Định nghĩa 1.2. Không gian tuyến tính H cùng với một tích vô hướng trên nó được gọi là một không gian tiền Hilbert. Định lí 1.1. (Bất đẳng thức Schwarz) Trong không gian tiền Hilbert H, với mọi x, y ∈ H ta luôn có bất đẳng thức sau: |hx, yi|2 ≤ hx, xihy, yi Chứng minh. Với mọi số thực α ta có 0 ≤ hx − αy, x − αyi = hx, xi − 2αhx, yi + α2 hy, yi Nên ∆ = |hx, yi|2 − hx, xihy, yi ≤ 0. Hay |hx, yi|2 ≤ hx, xihy, yi.  Dấu đẳng thức trong bất đẳng thức xảy ra khi và chỉ khi x và y phụ thuộc tuyến tính. Định lí 1.2. Cho H là một không gian tiền Hilbert, khi đó H cũng là một không gian tuyến tính định chuẩn với chuẩn được xác định bởi ||x|| = p hx, xi với mọi x ∈ H. (1.1) Chuẩn này được gọi là chuẩn cảm sinh từ tích vô hướng. Ta dễ dàng chứng p minh được hàm số ||x|| = hx, xi với mọi x ∈ H, là một chuẩn trên H. Thật vậy, từ điều kiện d) ta có ||x|| > 0 nếu x 6= 0, ||x|| = 0 nếu x = 0. 5 Từ điều kiện a), c) ta suy ra ||λx|| = |λ|.||x||. Từ bất đẳng thức Schwarz và cách định nghĩa chuẩn ta có (1.2) |hx, yi| ≤ ||x||.||y||. Từ đó hx + y, x + yi = hx, xi + 2hx, yi + hy, yi ≤ ||x||2 + 2||x||.||y|| + ||y||2 = (||x|| + ||y||)2 . Suy ra ||x + y|| ≤ ||x|| + ||y||. Định nghĩa 1.3. Nếu H là một không gian tiền Hilbert thực và đầy đủ đối với chuẩn cảm sinh từ tích vô hướng xác định bởi (1.1) thì H được gọi là không gian Hilbert thực. Ví dụ 1.1. Rn là không gian Hilbert thực với tích vô hướng hx, yi = n X xk yk k=1 trong đó x = (x1 , x1 , ..., xn ), y = (y1 , y2 , ..., yn ) ∈ Rn và chuẩn cảm sinh n X p 1 x2k ) 2 . ||x|| = hx, xi = ( k=1 Ví dụ 1.2. Không gian 2 l = {x = {xn }n ∈ R : ∞ X |xn |2 < +∞} n=1 là không gian Hilbert với tích vô hướng hx, yi = ∞ X x n yn n=1 trong đó x = (xn )n∈N , y = (yn )n∈N ∈ l2 và chuẩn cảm sinh v u n n X p uX 1 ||x|| = hx, xi = t |xk |2 = ( |xk |2 ) 2 . k=1 k=1 6 Ví dụ 1.3. Gọi C[a,b] là tập tất cả các hàm giá trị thực liên tục trên khoảng đóng hữu hạn [a, b] ⊂ R. Trong C[a,b] xét tích vô hướng Z b hx, yi = x(t)y(t)dt, x(t), y(t) ∈ C[a,b] . a Khi đó, không gian C[a,b] với chuẩn Z b 1 ||x|| = ( |x(t)|2 dt) 2 a là không gian tiền Hilbert. 1.1.2. Một số tính chất Định lí 1.3. Giả sử (xn )n∈N , (yn )n∈N là hai dãy lần lượt hội tụ mạnh đến x0 , y0 trong không gian tiền Hilbert thực H, khi đó lim hxn , yn i = hx0 , y0 i. n→∞ Chứng minh. Giả sử lim xn = x0 , lim yn = y0 trong không gian H. Ta n→∞ n→∞ sẽ chứng minh cho lim hxn , yn i = hx0 , y0 i trong R. Thật vậy, ta có n→∞ |hxn , yn i − hx0 , y0 i| = |hxn , yn i + hxn , y0 i − hxn , y0 i − hx0 , y0 i| ≤ |hxn , yn − y0 i| + |hxn − x0 , y0 i| ≤ ||xn ||.||yn − y0 || + ||xn − x0 ||.||y0 ||. Vì dãy (xn )n∈N hội tụ trong H nên tồn tại M > 0 sao cho ||xn || ≤ M với mọi n ∈ N . Khi đó, lim hxn , yn i = hx0 , y0 i. n→∞  Nhận xét 1.2. Từ định lý trên cho thấy tích vô hướng là một hàm số liên tục trên H × H, nó cũng là một phiếm hàm song tuyến tính bị chặn và hơn nữa phiếm hàm này cũng liên tục. 7 Định lí 1.4. Với mọi x, y thuộc không gian tiền Hilbert H ta luôn có đẳng thức hình bình hành sau ||x + y||2 + ||x − y||2 = 2(||x||2 + ||y||2 ). Chứng minh. Với mọi x, y ∈ H, ta có ||x + y||2 = hx + y, x + yi = ||x||2 + ||y||2 + 2hx, yi và ||x − y||2 = hx − y, x − yi = ||x||2 + ||y||2 − 2hx, yi. Cộng hai đẳng thức trên ta được đẳng thức cần chứng minh.  Áp dụng đẳng thức hình bình hành cho hai véc tơ x − y, x − z ta có hệ quả sau Hệ quả 1.1. Cho H là một không gian tiền Hilbert và x, y, z ∈ H. Khi đó, ta có đẳng thức Apollonius 2(||x − y||2 + ||x − z||2 ) = 4||x − y+z 2 || + ||y − z||2 . 2 Nhận xét 1.3. (Ý nghĩa của đẳng thức hình bình hành) 1) Đẳng thức trên nói lên một tính chất hình học: tổng bình phương các cạnh của hình bình hành bằng tổng bình phương hai đường chéo. 2) Từ định lý trên ta thấy, muốn đưa được tích vô hướng vào một không gian định chuẩn thì không gian này phải thỏa mãn điều kiện hình bình hành. Ngược lại nếu H là một không gian định chuẩn trong đó đẳng thức hình bình hành được thỏa mãn với mọi phần tử thuộc H thì trên H sẽ tồn tại một tích vô hướng h., .i sao cho chuẩn này được xác định nhờ tích vô hướng. Điều này được thể hiện qua định lý sau. 8 Định lí 1.5. Giả sử (H, ||.||) là một không gian định chuẩn trên R trong đó đẳng thức hình bình hành nghiệm đúng với mọi x, y ∈ H. Và khi đó ta đặt 1 hx, yi = p(x, y) = (||x + y||2 − ||x − y||2 ) 4 (1.3) thì h., .i là một tích vô hướng trên H và ta có hx, xi = ||x||2 . Chứng minh. Ta chứng minh h., .i xác định như trên thỏa mãn các điều kiện trong định nghĩa về tích vô hướng. Điều kiện a) - d) hiển nhiên được thỏa mãn (theo [2]). Để ý rằng h., .i : H × H −→ R là một hàm liên tục và p(x, 0) = 0, p(−x, y) = −p(x, y), ∀x, y ∈ H. Với mọi x, y, z ∈ H ta có 4(p(x, z) + p(y, z)) = (||x + z||2 − ||x − z||2 + ||y + z||2 − ||y − z||2 x+y ⇔ p(x, z) + p(y, z) = 2p( , z). 2 Trong đẳng thức trên lấy y = 0 được p(x, z) = 2p( x2 , z). Như vậy ta có x+y 2p( , z) = p(x + y, z). Nghĩa là p(x, z) + p(y, z) = p(x + y, z). Vậy 2 điều kiện b) được chứng minh. Thay thế x bằng 2x ta được 2p(x, z) = p(2x, z), ∀x, y, z ∈ H. Bằng quy nạp ta kiểm tra được p(nx, z) = np(x, z), ∀n ∈ N và bằng lập luận như trên ta có p(rx, z) = rp(x, z), ∀r ∈ Q và x, z ∈ H. Nhờ tính liên tục của chuẩn ||.|| suy ra hàm p(., z) liên tục, qua giới hạn ta có p(ax, z) = ap(x, z), ∀x, z ∈ H và a ∈ R. 9 Vậy p(x, y) là một tích vô hướng trên H và hiển nhiên hx, xi = p(x, x) = ||x||2 . Định lý được chứng minh.  Định lí 1.6. Với mọi không gian tiền Hilbert H đều tồn tại một không gian Hilbert H1 chứa H sao cho H là không gian con trù mật trong H1 . Chứng minh. Dùng phép bổ sung đầy đủ của một không gian định chuẩn ta được một không gian định chuẩn đầy đủ H1 chứa H sao cho H là không gian định chuẩn trù mật trong H1 [4, Định lý 2.8]. Với mọi x, y ∈ H1 sẽ tồn tại các dãy (xn )n , (yn )n ⊂ H sao cho lim xn = x, lim yn = y n−→∞ n−→∞ trong H1 . Theo đẳng thức hình bình hành ta có ||xn + yn ||2 + ||xn − yn ||2 = 2(||xn ||2 + ||yn ||2 ). Cho n −→ ∞, do tính liên tục của hàm chuẩn ta suy ra ||x + y||2 + ||x − y||2 = 2(||x||2 + ||y||2 ). Theo định lý trên sẽ tồn tại một tích vô hướng trong H1 cảm sinh ra chuẩn của H1 và ta có lim hxn , yn iH1 = hx, yiH1 . n−→∞ Định lý được chứng minh .  Tính chất khác biệt của không gian Hilbert so với không gian định chuẩn là ở đó khái niệm tích vô hướng bao hàm các khái niệm về tính trực giao, trực chuẩn, góc giữa các vectơ.... Trong phần sau chúng ta nhắc lại định nghĩa, tính chất của các khái niệm đó và một số ví dụ minh họa. 10 Định nghĩa 1.4. Cho H là không gian tiền Hilbert thực. 1) Hai phần tử x, y ∈ H được gọi là trực giao với nhau nếu hx, yi = 0 và được kí hiệu là x⊥y. 2) Hệ S ⊂ H được gọi là hệ trực giao nếu các phần tử của S trực giao với nhau từng đôi một, tức là ∀x, y ∈ S, x 6= y ta có hx, yi = 0. 3) Hệ E = {e1 , e2 , ..., } ⊂ H được gọi là hệ trực chuẩn nếu E là hệ trực giao và ||ej|| = 1 ∀ei ∈ E . Một cách tương đương, hệ E được gọi là hệ trực chuẩn nếu   0 nếu i 6= j hei , ej i = δij =  1 nếu i = j. 4) Phần tử x ∈ H được gọi là trực giao với M ⊂ H nếu ∀y ∈ M ta có hx, yi = 0 và được kí hiệu là x⊥M . 5) Phần bù trực giao của M ⊂ H được kí hiệu M ⊥ là tập hợp M ⊥ = {x ∈ H : x⊥y, ∀y ∈ M }. Định lí 1.7. Cho M là một không gian con đóng của không gian Hilbert H. Khi đó mọi phần tử x ∈ H đều biểu diễn một cách duy nhất dưới dạng x = y + z, y ∈ M, z ∈ M ⊥ trong đó y thỏa mãn ||x − y|| = ||z|| = inf {||x − u||} = d(x, M ). u∈M Nhận xét 1.4. Từ định lý này ta có thể viết H = M ⊕ M⊥ và y được gọi là hình chiếu trực giao của x lên không gian con M . 11 Định nghĩa 1.5. Dãy (xn )n∈N ∈ H được gọi là (i) Hội tụ mạnh đến x0 ∈ H nếu nó hội tụ theo chuẩn, nghĩa là lim ||xn − x0 || = 0, n−→∞ kí hiệu xn −→ x0 hay lim xn = x0 . n−→∞ (ii) Hội tụ yếu đến x ∈ H nếu ∀y ∈ H ta có lim hxn , yi = hx, yi. n→∞ w Ký hiệu là {xn } −→ x hoặc {xn } * x, khi n −→ ∞. Chú ý 1.1. Nếu dãy {xn } hội tụ mạnh về x thì nó cũng hội tụ yếu về x, nhưng điều ngược lại không đúng. 1.2 Một số vấn đề về giải tích lồi Trước hết ta nhắc lại một số khái niệm và tính chất cơ bản của giải tích lồi như tập lồi, hàm lồi, dưới vi phân,... 1.2.1. Tập lồi, bao lồi và nón lồi Giả sử X là không gian tuyến tính, R là tập số thực. Định nghĩa 1.6. Tập A ⊂ X, ∀x, y ∈ A, ta có 1) A được gọi là lồi ⇔ λx + (1 − λ)y ∈ A, với mọi λ ∈ [0, 1]. 2) [x1 , x2 ] = {x ∈ A : x = λx1 + (1 − λ)x2 , 0 ≤ λ ≤ 1}, là đoạn nối x1 , x2 . 3) Giao của tất cả các tập lồi chứa A được gọi là bao lồi của A và ký hiệu là coA. 12 Ví dụ 1.4. cho A = {(x, y) ∈ R| y ≥ x2 }. Dễ thấy A là tập lồi. Cho tập A ⊂ X, khi đó, ta có nhận xét sau: 1) coA là tập lồi nhỏ nhất chứa A. 2) Tập A là lồi nếu với mọi x1 , x2 ∈ A suy ra [x1 , x2 ] ⊂ A. 3) A là tập lồi khi và chỉ khi A ≡ coA. 4) coA = { m P λi xi |xi ∈ A; n=1 m P λi = 1; λi > 0 ∀i = 1, 2, ..., m}. n=1 Định nghĩa 1.7. Cho tập A ⊂ X khi đó, i) Giao tất cả các tập con đóng của X chứa A được gọi là bao đóng của A và ký hiệu là A. ii) Giao tất cả các tập con lồi đóng của X chứa A được gọi là bao lồi đóng của A và ký hiệu là coA. Nhận xét 1.5. Ta có coA là tập lồi đóng và là tập lồi đóng nhỏ nhất chứa A. Chú ý 1.2. Bao lồi đóng của tập A trùng với bao lồi của A tức là ta có co A = coA. Định nghĩa 1.8. Cho tập K ⊂ X ta có các định nghĩa 1) Tập K được gọi là nón có đỉnh tại 0 nếu với mọi x ∈ K và mọi λ > 0 suy ra λx ∈ K. 2) Tập K ⊂ X được gọi là nón có đỉnh tại x0 nếu K − x0 là nón có đỉnh tại 0. 3) Nón K có đỉnh tại 0 được gọi là nón lồi nếu K là một tập lồi, có nghĩa là với mọi x, y ∈ K và với mọi λ, µ > 0 suy ra λx + µy ∈ K. 13 Định lí 1.8. Tâp K ⊂ X là nón lồi có đỉnh tại 0 khi và chỉ khi với mọi x, y ∈ K, với mọi λ > 0 suy ra x + y ∈ K, λx ∈ K. Định nghĩa 1.9. Cho A ⊂ Rn , ta có: 1) A được gọi là tập affine nếu: (1 − λ)x + λy ∈ A, ∀x, y ∈ A, ∀λ ∈ R. 2) Giao của tất cả các tập affine chứa A ⊂ Rn được gọi là bao affine của A và ký hiệu là affA. Nghĩa là m m X X affA := { λi xi |xi ∈ A; λi = 1; ∀i = 1, 2, ..., m.} n=1 n=1 1.2.2. Hàm lồi và dưới vi phân Định nghĩa 1.10. Giả sử X là không gian lồi địa phương, D ⊂ X và f : D −→ R ∪ {−∞, +∞}. Ta có các định nghĩa: 1) Trên đồ thị (epigraph) của hàm f , ký hiệu là epif và epif = {(x, r) ∈ D × R : f (x) ≤ r}. 2) Hàm f được gọi là hàm lồi nếu epif là tập lồi trong X × R. Hàm f được gọi là hàm lõm nếu −f là hàm lồi. 3) Miền hữu dụng (miền xác định) của hàm f ký hiệu là domf và: domf = {x ∈ D : f (x) < +∞}. 4) Hàm f xác định trên X được gọi là thuần nhất dương (positively homogeneous), nếu với mọi x ∈ X và với mọi λ ∈ (0, +∞) ta đều có: f (λx) = λf (x). 14 Ví dụ 1.5. Dễ thấy f (x) = |x|, ∀x ∈ R là một hàm lồi. Định lí 1.9. Giả sử D là tập lồi, khác rỗng trong không gian X, hàm f : D → (−∞, +∞]. Khi đó, f lồi trên D khi và chỉ khi: f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y), ∀λ ∈ [0, 1] và ∀x, y ∈ D. Định nghĩa 1.11. Hàm f được gọi là chính thường (proper) nếu f thỏa mãn hai điều kiện sau: i) domf 6= 0; ii) f (x) > −∞ với mọi x ∈ D. Mệnh đề 1.1. Hàm thuần nhất dương f : X → (−∞, +∞] là lồi khi và chỉ khi với mọi x, y ∈ X ta luôn có: f (x + y) ≤ f (x) + f (y). Định nghĩa 1.12. Cho f là hàm lồi, phiếm hàm (vectơ) x∗ ∈ X ∗ được gọi là dưới gradient của f tại x̄ nếu: f (x) − f (x̄) ≥ hx∗ , x − x̄ i với mọi x ∈ X. Tập tất cả các dưới gradient của f tại x̄ được gọi là dưới vi phân của f tại x̄. Ký hiệu là: ∂f (x̄). Như vậy: ∂f (x̄) = {x∗ ∈ X : f (x) − f (x̄) ≥ hx∗ , x − x̄i với mọi x ∈ X}. Hàm f được gọi là khả dưới vi phân tại x̄ nếu ∂f (x̄) 6= ∅. Ví dụ 1.6. Cho C là tập lồi khác rỗng của H. Xét hàm chỉ của tập C có dạng δC (x) :=   0 nếu x ∈ C  +∞ nếu x ∈ / C. 15 Khi đó dưới vi phân của δC (x) tại x0 ∈ C là nón pháp tuyến ngoài của C tại x0 . Thật vậy, khi x0 ∈ C thì ∂δC (x0 ) = {x∗ ∈ H : hx∗ , x − x0 i ≤ δC (x), ∀x ∈ C}. Với x ∈ / C thì δC (x) = +∞ nên bất đẳng thức hx∗ , x − x0 i ≤ δC (x) luôn đúng. Do đó ∂δC (x0 ) = {x∗ ∈ H : hx∗ , x − x0 i ≤ 0, ∀x ∈ C} = NC (x0 ). Ví dụ 1.7. Cho f : H −→ R là hàm lồi thuần nhất dương, (tức là f lồi và f (λx) = λf (x), ∀λ > 0, ∀x ∈ H.) Khi đó ∂f (x) = {z ∈ H : hz; xi = f (x), hz, xi ≤ f (x), ∀x ∈ C}. Thật vậy, nếu z ∈ ∂f (x) thì hz, x − xi ≤ f (x) − f (x), ∀x ∈ C. Thay x = 2x, ta có hz, xi ≤ f (2x) − f (x) = f (x). Còn nếu thay x = 0, ta có −hz, xi ≤ −f (x). Từ kết quả trên suy ra hz, xi = −f (x). Hơn nữa, hz, x − xi = hz, xi − hz, xi = hz, xi − f (x). Do đó, hz, xi ≤ f (x), ∀x ∈ C.