Tài liệu Về cực trị hàm lồi

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------------- NGUYỄN ĐÌNH THỌ VỀ CỰC TRỊ HÀM LỒI LUẬN VĂN THẠC SĨ TOÁN HỌC Hà Nội - Năm 2014 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------------- NGUYỄN ĐÌNH THỌ VỀ CỰC TRỊ HÀM LỒI Chuyên ngành: TOÁN GIẢI TÍCH Mã số: 60 46 01 02 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: GS. TSKH. LÊ DŨNG MƯU Hà Nội - Năm 2014 MỤC LỤC Lời nói đầu ii Chương 1. Các kiến thức cơ bản về giải tích lồi 1 1.1. Tập lồi 1 1.2. Hàm lồi 9 1.3. Dưới vi phân 11 1.3.1. Khái niệm 11 1.3.2. Phép tính với dưới vi phân 14 1.4. Đạo hàm theo hướng và tính khả vi của hàm lồi Chương 2. Cực tiểu hàm lồi trên tập lồi 17 19 2.1. Phát biểu bài toán 19 2.2. Sự tồn tại nghiệm tối ưu 23 2.3. Điều kiện tối ưu 26 2.3.1. Bài toán với ràng buộc đẳng thức 27 2.3.2. Bài toán với ràng buộc bất đẳng thức 29 2.4. Đối ngẫu Lagrange 32 2.5. Các phương pháp giải cơ bản 35 2.5.1. Phương pháp chiếu dưới đạo hàm 35 2.5.2. Thuật toán Frank-Wolfe 38 Chương 3. Cực đại hàm lồi trên tập lồi 44 3.1. Phát biểu bài toán 44 3.2. Tính chất cơ bản 44 3.3. Các phương pháp giải cơ bản 46 3.3.1. Phương pháp xấp xỉ ngoài 46 3.3.2. Phân hoạch không gian và thuật toán nhánh cận 52 Kết luận 62 Tài liệu tham khảo 63 i LỜI NÓI ĐẦU Cực trị hàm lồi trên tập lồi là một lớp bài toán cơ bản của tối ưu hóa. Cực tiểu hàm lồi trên tập lồi gọi là quy hoạch lồi có tính chất cơ bản là mọi điểm cực tiểu địa phương đều là cực tiểu tuyệt đối. Tính chất quan trọng này cho phép các lý thuyết có tính địa phương như giới hạn, vi phân,...có thể áp dụng trực tiếp vào quy hoạch lồi. Lý thuyết về bài toán quy hoạch lồi đã được nghiên cứu nhiều và đã thu được nhiều kết quả quan trọng dựa trên lý thuyết của giải tích lồi và tối ưu hóa. Cực đại hàm lồi trên tập lồi có tính chất khác hẳn cực tiểu hàm lồi trên tập lồi, cụ thể ta thấy rằng cực đại địa phương của một hàm lồi không nhất thiết là cực đại tuyệt đối. Mục đích của luận văn này là để trình bày bài toán cực đại, cực tiểu hàm lồi trên tập lồi và một số phương pháp giải cơ bản các bài toán này. Luận văn gồm có ba chương: Chương 1. Các kiến thức cơ bản về giải tích lồi Trình bày một số khái niệm, định nghĩa và kết quả cần thiết liên quan đến tập lồi và hàm lồi. Chương 2. Cực tiểu hàm lồi trên tập lồi Trình bày bài toán cực tiểu hàm lồi trên tập lồi, sự tồn tại nghiệm tối ưu và điều kiện tối ưu của bài toán. Đối ngẫu Lagrange. Trình bày hai phương pháp cơ bản giải bài toán quy hoạch lồi đó là phương pháp chiếu dưới đạo hàm và thuật toán Frank-Wolfe. Chương 3. Cực đại hàm lồi trên tập lồi Trình bày bài toán cực đại hàm lồi trên tập lồi và một số tính chất cơ bản. Trình bày hai phương pháp cơ bản giải bài toán cực đại hàm lồi trên tập lồi đó là phương pháp xấp xỉ ngoài và thuật toán nhánh cận. Luận văn được hoàn thành tại Trường Đại học Khoa học Tự nhiên - Đại học Quốc gia Hà Nội, dưới sự hướng dẫn của GS. TSKH. Lê Dũng Mưu. Em xin bày tỏ lòng biết ơn sâu sắc tới GS. TSKH. Lê Dũng Mưu, người đã tận tình hướng dẫn và giúp đỡ em trong suốt quá trình nghiên cứu để em có thể hoàn thành luận văn này. ii Em cũng bày tỏ lòng biết ơn chân thành tới quý 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 đã giảng dạy và giúp đỡ em hoàn thành khóa học. Nhân dịp này em cũng xin chân thành cảm ơn Ban giám hiệu, đồng nghiệp Trường THPT Ân Thi, gia đình và bạn bè đã luôn động viên, giúp đỡ và tạo điệu kiện cho em về mọi mặt trong suốt quá trình học tập và thực hiện luận văn này. 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. Tác giả rất mong nhận được ý kiến đóng góp của quý thầy, cô giáo và bạn đọc để luận văn được hoàn thiện hơn. Xin trân trọng cảm ơn! iii Chương 1. Các kiến thức cơ bản về giải tích lồi Chương này trình bày một số khái niệm, định nghĩa và kết quả cần thiết liên quan đến tập lồi và hàm lồi. Nội dung của chương được tham khảo từ các tài liệu [1], [2], [4], [9]. 1.1. Tập lồi Định nghĩa 1.1. Cho hai điểm a, b   n . (i) Đường thẳng đi qua hai điểm a và b là tập hợp có dạng x   n  x  αa  βb, α, β  , α  β  1 . (ii) Đoạn thẳng nối hai điểm a và b là tập hợp có dạng x   n  x  αa  βb, α  0, β  0, α  β  1 . Định nghĩa 1.2. Một tập C   n được gọi là một tập lồi, nếu C chứa mọi đoạn thẳng đi qua hai điểm bất kỳ của nó. Tức là C là tập lồi  x, y  C , λ   0,1 thì λx  1  λ  y  C . Định nghĩa 1.3. (i) Ta nói x là tổ hợp lồi của các điểm (vectơ) x1, x 2 ,..., x k nếu k x   λ j x j với λ j  0, j  1, 2,..., k và j 1 k  λj  1. j 1 (ii) Ta nói x là tổ hợp affine của các điểm (vectơ) x1, x 2 ,..., x k nếu k x   λ j x j với j 1 k  λj  1. j 1 Mệnh đề 1.1. Tập hợp C là lồi khi và chỉ khi nó chứa mọi tổ hợp lồi của các điểm của nó. Tức là C lồi  k  , λ1 ,..., λk  0 sao cho k k  λ j  1 và x1,..., xk  C thì  λj x j C . j 1 j 1 1 Chương 1. Các kiến thức cơ bản về giải tích lồi Định nghĩa 1.4. Một tập C được gọi là 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à C là tập affine  x, y  C , λ   thì λx  1  λ  y  C . Định nghĩa 1.5. Siêu phẳng trong không gian  n là tập hợp các điểm có dạng x   n  aT x  α , trong đó a   n là một vectơ khác 0 và α   . Định nghĩa 1.6. Nửa không gian là một tập hợp có dạng x   n  aT x  α , trong đó a   n là một vectơ khác 0 và α   , đây là nửa không gian đóng.   Tập x   n aT x  α là nửa không gian mở. Mệnh đề 1.2. Tập M   là tập affine khi và chỉ khi nó có dạng M  L  a với L là một không gian con và a  M . Không gian con L này được xác định duy nhất. Không gian L trong mệnh đề trên được gọi là không gian con song song với M (hoặc không gian con của M ). Định nghĩa 1.7. Thứ nguyên (hay chiều) của một tập affine M là thứ nguyên của không gian song song với M và được ký hiệu là dim M . Mệnh đề 1.3. Bất kỳ một tập affine M   n có số chiều r đều có dạng   M  x   n Ax  b , (1.1) trong đó A là ma trận cấp m  n , b   m và rankA  n  r . Ngược lại, mọi tập hợp có dạng (1.1) với rankA  n  r đều là tập affine có số chiều là r . Định nghĩa 1.8. Các điểm x 0 , x1,..., x k trong  n được gọi là độc lập affine nếu bao affine của chúng có thứ nguyên là k . Định nghĩa 1.9. Một tập hợp S   n được gọi là một đơn hình có thứ nguyên bằng k (hoặc k  đơn hình), nếu S là tổ hợp lồi của k  1 vectơ độc lập affine. Các vectơ này được gọi là đỉnh của đơn hình. 2 Chương 1. Các kiến thức cơ bản về giải tích lồi Định nghĩa 1.10. Một tập được gọi là tập lồi đa diện, nếu nó là giao của một số hữu hạn các nửa không gian đóng. Dạng tường minh của một tập lồi đa diện được cho như sau:   D : x   n a j , x  b j , j  1, 2,..., m , trong đó 0  a j   n và b j   , j  1, 2,..., m . Nếu ta kí hiệu A là ma trận có m hàng là các vectơ a j  j  1, 2,..., m  và vectơ bT   b1, b2 ,..., bm  thì hệ trên viết được là:   D  x   n Ax  b . Định nghĩa 1.11. Một tập C được gọi là nón nếu λ  0, x  C  λx  C . (i) Một nón được gọi là nón lồi nếu nó đồng thời là một tập lồi. (ii) Một nón lồi được gọi là nón nhọn nếu nó không chứa đường thẳng, khi đó ta nói O là đỉnh của nón. Nếu nón lồi này là một tập lồi đa diện thì ta nói nó là nón lồi đa diện. Định nghĩa 1.12. Cho C   n là một tập lồi và x  C . (i) Tập  N C  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 . (ii) Tậ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 . Định nghĩa 1.13. Một điểm a  C được gọi là điểm trong tương đối của C nếu nó là điểm trong của C theo tô-pô cảm sinh bởi affC . Ký hiệu tập các điểm trong tương đối của C là riC . Vậy   riC : a  C B :  a  B   affC  C , 3 Chương 1. Các kiến thức cơ bản về giải tích lồi trong đó B là một lân cận mở của gốc. Hiển nhiên   riC  a  affC B :  a  B   affC  C . Mệnh đề 1.4. Cho C   n là một tập lồi. Giả sử x  riC . Khi đó với mọi y  C , tất cả các điểm trên đoạn thẳng nối x và y , có thể trừ y , đều thuộc riC . Nói cách khác, với mọi 0  λ  1 thì 1  λ  riC  λC  riC . Định nghĩa 1.14. Bao lồi của một tập E là giao của tất cả các tập lồi chứa E . Ký hiệu là coE . Định nghĩa 1.15. Một điểm x  C được gọi là điểm cực biên của C nếu không tồn tại a, b  C , a  0 và 0  λ  1 sao cho x  λa  1  λ  b . Trong trường hợp C tập lồi đa diện thì điểm cực biên còn được gọi là đỉnh. Ta kí hiệu V  C  là tập các điểm cực biên của C . Bao lồi của một số hữu hạn điểm là một tập đa diện lồi, compact. Nếu v 0 , v1 ,..., v m độc lập affine thì bao lồi của chúng là một đơn hình. Đơn hình này có thứ nguyên là m . Các điểm v 0 , v1 ,..., v m được gọi là đỉnh (điểm cực biên) của đơn hình này. Định nghĩa 1.16. Một tập F  C được gọi là một diện của một tập lồi C nếu F là tập lồi có tính chất x, y  C : tx  1  t  y  F , 0  t  1 thì  x, y   F . Điểm cực biên là diện có thứ nguyên bằng 0. Cạnh là diện có thứ nguyên bằng 1. Tia cực biên là một diện nửa đường thẳng. Như vậy tia cực biên là một cạnh vô hạn. Hướng cực biên là hướng của tia cực biên. Định nghĩa 1.17. Cho x 0  C . Ta nói aT x  α là siêu phẳng tựa của C tại x 0 , nếu aT x 0  α , aT x  α , x  C . Định nghĩa 1.18. Cho C   (không nhất thiết lồi) và y là một vectơ bất kỳ, đặt dC  y  : inf x  y . xC 4 Chương 1. Các kiến thức cơ bản về giải tích lồi Ta nói dC  y  là khoảng cách từ y đến C . Nếu tồn tại π  C sao cho dC  y   π  y , thì ta nói π là hình chiếu (vuông góc) của y trên C và ký hiệu là π  PC  y  . Theo định nghĩa, ta thấy rằng hình chiếu PC  y  của y trên C là nghiệm của bài toán tối ưu 1 min  x  y 2 2  xC.  Nói cách khác việc tìm hình chiếu của y trên C có thể đưa về việc tìm cực tiểu của hàm toàn phương x  y 2 trên C . Nếu C   thì dC  y  hữu hạn, vì 0  dC  y   x  y , x  C . Mệnh đề 1.5. Cho C là một tập lồi đóng khác rỗng. Khi đó: (i) Với mọi y   n , π  C hai tính chất sau là tương đương: a) π  PC  y  , b) y  π  NC  π  . (ii) Với mọi y   n , hình chiếu PC  y  của y trên C luôn tồn tại và duy nhất. (iii) Nếu y  C , thì PC  y   y, x  PC  y   0 là siêu phẳng tựa của C tại PC  y  và tách hẳn y khỏi C , tức là PC  y   y, x  PC  y   0, x  C và PC  y   y, y  PC  y   0 . (iv) Ánh xạ y  PC  y  có các tính chất sau: a) PC  x   PC  y   x  y , x, y   n (tính không giãn). b) PC  x   PC  y  , x  y  PC  x   PC  y  2 (tính đồng bức). Chứng minh. (i) Giả sử có a). Lấy x  C và λ   0,1 . Đặt 5 Chương 1. Các kiến thức cơ bản về giải tích lồi xλ : λx  1  λ  π . Do x, π  C và C lồi, nên xλ  C . Hơn nữa do π là hình chiếu của y nên π  y  y  xλ . Hay 2 2 π  y  λ  x  π   π  y . Khai triển vế phải, ước lược và chia hai vế cho λ  0 , ta có 2 λ x  π  2 x  π, π  y  0 . Điều này đúng với mọi x  C và λ   0,1 . Do đó khi cho λ  0 , ta được π  y, x  π  0, x  C . Vậy y  π  NC  π  . Bây giờ giả sử có b). Với mọi x  C , ta có T 0   y  π  x  π    y  π T  x  y  y  π  2 T  y  π   y  π   x  y . Từ đây và b), dùng bất đẳng thức Cauchy-Schwarz ta có y π 2 T   y  π  y  x  y π . y  x . Suy ra y  π  y  x , x  C và do đó π  PC  y  . (ii) Do dC  y   inf x  y nên theo định nghĩa của cận dưới đúng, tồn tại một dãy xC x   C sao cho k lim x k  y  dC  y    . k    hội tụ đến một điểm π nào   Vậy dãy x k bị chặn, do đó nó có một dãy con x kj đó. Do C đóng nên π  C . Vậy π  y  lim x j  kj  y  lim x k  y  dC  y  . k  Chứng tỏ π là hình chiếu của y trên C . 6 Chương 1. Các kiến thức cơ bản về giải tích lồi Bây giờ ta chỉ ra tính duy nhất của hình chiếu. Thật vậy, nếu tồn tại hai điểm π và π1 đều là hình chiếu của y trên C thì   y  π  N C  π  , y  π1  N C π1 . Tức là π  y , π1  π  0 và π1  y, π  π1  0 . Cộng hai bất đẳng thức này ta suy ra π  π1  0 , và do đó π  π1 . (iii) Do y  π  NC  π  nên π  y, x  π  0, x  C . Vậy π  y, x  π  y, π là một siêu phẳng tựa của C tại π . Siêu phẳng này tách y khỏi C vì y  π nên 2 π  y, y  π   π  y  0 . (iv) Theo phần (ii) ánh xạ x  PC  x  xác định khắp nơi. Do z  PC  z   N C  PC  z   với mọi z , nên áp dụng z  x và z  y ta có x  PC  x  , PC  y   PC  x   0 và x  PC  y  , PC  x   PC  y   0 . Cộng hai bất đẳng thức trên ta được PC  y   PC  x  , PC  y   PC  x   x  y  0 . Từ đây và theo bất đẳng thức Cauchy-Schwarz suy ra PC  x   PC  y   x  y . Để chứng minh tính đồng bức, áp dụng tính chất b) của (i) lần lượt với PC  x  và PC  y  , ta có 7 Chương 1. Các kiến thức cơ bản về giải tích lồi PC  x   x, PC  x   PC  y   0 , y  PC  y  , PC  x   PC  y   0 . Cộng hai bất đẳng thức ta được PC  x   PC  y   y  x, PC  x   PC  y   0 2  PC  x   PC  y  , y  x  PC  x   PC  y   0 2  PC  x   PC  y  , x  y  PC  x   PC  y  . Định lý 1.1. (Định lý xấp xỉ tuyến tính tập lồi) Mọi tập lồi đóng khác rỗng và không trùng với toàn bộ không gian đều là giao của tất cả các nửa không gian tựa của nó. Định nghĩa 1.19. Cho hai tập C và D khác rỗng, ta nói siêu phẳng aT x  α tách C và D nếu aT x  α  aT y, x  C , y  D . Ta nói siêu phẳng aT x  α tách chặt C và D nếu aT x  α  aT y, x  C , y  D . Ta nói siêu phẳng aT x  α tách mạnh C và D nếu sup aT x  α  inf aT y , x  C , y  D . xC yD Định lý 1.2. (Định lý tách 1) Cho C và D là hai tập lồi khác rỗng trong  n sao cho C  D   . Khi đó có một siêu phẳng tách C và D . Định lý 1.3. (Định lý tách 2) Cho C và D là hai tập lồi đóng khác rỗng trong  n sao cho C  D   . Giả sử có ít nhất một tập là compact. Khi đó hai tập này có thể tách mạnh được bởi một siêu phẳng. Bổ đề 1.1. (Bổ đề Farkas) Cho A là một ma trận thực cấp m  n và a   n . Khi đó trong hai hệ dưới đây có một hệ và chỉ duy nhất một hệ có nghiệm Ax  0, aT x  0, x   n , AT y  a, y  0, y   m . 8 Chương 1. Các kiến thức cơ bản về giải tích lồi Ý nghĩa hình học của Bổ đề Farkas: Nón lồi, đóng  x   n  Ax  0 nằm  trong nửa không gian x   n aT x  0 khi và chỉ khi vectơ pháp tuyến a ở trong nón sinh bởi các hàng của ma trận A . 1.2. Hàm lồi Cho C   n là tập lồi và f : C   . Ta sẽ ký hiệu   domf : x  C f  x    . Định nghĩa 1.20. Tập domf được gọi là miền hữu dụng của f . Tập epif :  x, μ   C   f  x   μ được gọi là trên đồ thị của hàm f . Bằng cách cho f  x    nếu x  C , ta có thể coi f được xác định trên toàn không gian, và ta có   domf  x   n f  x    , epif   x, μ    n    f  x  μ . Định nghĩa 1.21. Cho   C   n lồi và f : C   . Ta nói f là hàm lồi trên C , nếu epif là một tập lồi trong  n1 . Ta chủ yếu làm việc với hàm f :  n     . Trong trường hợp này định nghĩa trên tương đương với f  λx  1  λ  y   λf  x   1  λ  f  y  , x, y  C , λ   0,1 . Định nghĩa 1.22. Cho   C   n lồi. (i) Hàm f :  n     được gọi là hàm lồi chặt trên C nếu f  λx  1  λ  y   λf  x   1  λ  f  y  , x, y  C , λ   0,1 . 9 Chương 1. Các kiến thức cơ bản về giải tích lồi (ii) Hàm f :  n     được gọi là hàm lồi mạnh trên C với hệ số η  0 , nếu x, y  C , λ   0,1 ta có 1 2 f  λx  1  λ  y   λf  x   1  λ  f  y   ηλ 1  λ  x  y . 2 (iii) Hàm f được gọi là hàm lõm trên C , nếu  f là hàm lồi trên C . Mệnh đề 1.6. Một hàm f : C   là hàm lồi trên C khi và chỉ khi x, y  C , α  f  x  , β  f  y  , λ   0,1  f  λx  1  λ  y   λα  1  λ  β . Ví dụ 1.1. (Một số ví dụ về hàm lồi) (i) Cho C   là một tập lồi, δC là hàm chỉ của C , được định nghĩa như sau: khi x  C , 0 δC  x  :   khi x  C. δC là một hàm lồi. (ii) Cho C lồi đóng, hàm khoảng cách đến tập C , được định nghĩa như sau: dC  x  : min x  y . yC dC là một hàm lồi. Định nghĩa 1.23. Một hàm f gọi là chính thường, nếu domf   và f  x   , x . Định nghĩa 1.24. Một hàm f gọi là đóng, nếu epif là một tập đóng trong  n1 . Chú ý 1.1. (i) Nếu f là một hàm lồi trên một tập lồi C , thì có thể thác triển f lên toàn không gian bằng cách đặt  f  x  f e  x  :   khi x  C , khi x  C. (ii) Nếu f là hàm lồi trên  n thì domf là một tập lồi, vì domf là hình chiếu trên    n của epif , tức là domf  x μ   :  x, μ   epif . Định nghĩa 1.25. Hàm f được gọi là thuần nhất dương (bậc 1) trên  n nếu 10 Chương 1. Các kiến thức cơ bản về giải tích lồi f  λx   λf  x  , x   n , λ  0 . Mệnh đề 1.7. Cho f là một hàm thuần nhất dương trên  n . Khi đó f là hàm lồi khi và chỉ khi f là dưới cộng tính theo nghĩa f  x  y   f  x   f  y  , x, y   n . Mệnh đề 1.8. Nếu f1, f 2 là những hàm lồi, chính thường thì f1  f 2 là hàm lồi. Hệ quả 1.1. Nếu f1, f 2 ,..., f m là các hàm lồi, chính thường và λ1, λ2 ,..., λm là các số dương thì hàm λ1 f1  λ2 f 2  ...  λm f m là lồi. Định nghĩa 1.26. Hàm l là hàm non affine của một hàm f trên  n nếu l là hàm affine trên  n và l  x   f  x  , x   n . Định lý 1.4. Mọi hàm lồi đóng chính thường f trên  n đều là bao trên của các hàm non affine của nó. Tức là f  x   sup lv  x  lv  A , v trong đó A là tập hợp tất cả các hàm non affine của f . 1.3. Dưới vi phân 1.3.1. Khái niệm Định nghĩa 1.27. Cho f :  n     . Ta nói x*   n là dưới đạo hàm của f tại điểm x 0   n nếu   x* , x  x0  f  x   f x 0 , x   n . Tập hợp tất cả các dưới đạo hàm của f tại điểm x 0 được gọi là dưới vi phân của   f tại điểm đó và được kí hiệu là f x 0 . Vậy       f x 0  x* x* , x  x 0  f  x   f x 0 , x   n .   Nếu f x 0   thì ta nói f khả dưới vi phân tại điểm x 0 . 11 Chương 1. Các kiến thức cơ bản về giải tích lồi Ví dụ 1.2. (Một số ví dụ về dưới vi phân) (i) Nếu f là hàm affine f ( x)  x* , x  α với x*   n và α       thì f x 0  x* , x 0   n (ii) Nếu C   n là tập lồi và x 0  C thì     δC x 0  x*   n x* , x  x 0  δC  x  , x   n . Với x  C thì δC  x    nên x* , x  x0  δC  x  luôn đúng. Vậy       δC x 0  x*   n x* , x  x0  0, x  C  N C x 0 . Mệnh đề 1.9. Cho f :  n     lồi, chính thường. Khi đó: (i) Nếu x  domf thì f  x    . (ii) Nếu x  int  domf  thì f  x    và compact. Ngược lại, nếu f  x    , compact thì x  ri  domf  . Chứng minh. (i) Cho z  domf thì f  z    . Vậy nếu x  domf thì f  x    và do đó không thể tồn tại x* thỏa mãn x* , z  x  f  x   f  z    . Vậy f  x    . (ii) Giả sử x  int  domf  . Ta có điểm  x, f  x   nằm trên biên của epif . Do f lồi, chính thường nên tồn tại siêu phẳng tựa của bao đóng của epif đi qua  x, f  x   , tức là tồn tại p   n , t   không đồng thời bằng 0 thỏa mãn p, x  tf  x   p, y  tμ,   y, μ   epif . Ta có t  0 , vì nếu t  0 thì p, x  p, y , y  domf . Nhưng do x  int  domf  nên điều này kéo theo p  0 . Vậy t  0 . 12 (1.2) Chương 1. Các kiến thức cơ bản về giải tích lồi Hơn nữa t  0 , vì nếu t  0 thì trong bất đẳng thức (1.2), khi cho μ   ta suy ra mâu thuẫn vì vế trái cố định. Chia hai vế của (1.2) cho t  0 , đồng thời thay μ  f  y  và đặt x*   p , ta được t x* , x  f  x   x* , y  f  y  , y  domf . Hay là x* , y  x  f  x   f  y  , y  domf . Nếu y  domf thì f  y    , do đó x* , y  x  f  x   f  y  , y   n . Chứng tỏ x*  f  x  . Bây giờ ta chỉ ra tập f  x  compact. Do x  domf nên x*  f  x  khi và chỉ khi f '  x, d   x* , d , d   n . (1.3) Lấy ei vectơ đơn vị thứ i  i  1,..., n  của  n . Áp dụng (1.3) lần lượt với d  ei   với i  1,..., n ta có xi*  f ' x, ei . Tương tự, áp dụng với d  ei với i  1,..., n ta     có  xi*  f ' x, ei hay xi*   f ' x, ei . Tóm lại      f ' x, ei  x*  f ' x, ei , i  1,..., n.   Do x  ri  domf  nên f '  x, y  hữu hạn với mọi y   n . Nói riêng f ' x, ei và   f ' x, ei hữu hạn với mọi i  1,..., n. Vậy f  x  bị chặn, và do tính đóng nên nó compact. Ngược lại, giả sử f  x  khác rỗng và compact. Ta chỉ ra rằng x  ri  domf  . Do f  x    nên x  domf . Nếu trái lại x  ri  domf  thì x ở trên biên tương đối 13 Chương 1. Các kiến thức cơ bản về giải tích lồi của domf . Do domf lồi, theo mệnh đề về siêu phẳng tựa, tồn tại một siêu phẳng tựa của bao đóng của domf tại x , tức là tồn tại vectơ p   n , p  0 sao cho pT x  pT z , z  domf . Lấy x*  f  x  . Từ đây và theo định nghĩa dưới vi phân ta có f  z   f  x   x* , z  x  x*  λp, z  x , λ  0, z   n . Chứng tỏ x*  λp  f  x  , λ  0 . Điều này mâu thuẫn với tính bị chặn của f  x  . Vậy x  ri  domf  . 1.3.2. Phép tính với dưới vi phân Mệnh đề 1.10. Cho f là hàm lồi chính thường trên  n và λ  0 . Khi đó   λf  x   λf  x  , x   n . Chứng minh. Ta có: x*    λf  x   x* , z  x   λf  z    λf  x  , z   n  x* , z  x  λf  z   λf  x  , z   n   x* , z  x  f  z   f  x  , z   n λ x*  f  x  λ  x*  λf  x  . Vậy   λf  x   λf  x  , x   n . Định lý 1.5. (Định lý Moreau-Rockafellar) Cho f1, f 2 , ..., f m là các hàm lồi chính thường trên  n . Khi đó: m m  a)    fi   x    fi  x  , x   n . i 1  i 1  14 Chương 1. Các kiến thức cơ bản về giải tích lồi m b) Nếu  ri  domfi    thì i 1 m m     fi   x    fi  x  , x   n . i 1  i 1  * m m * Chứng minh. a) Giả sử x   fi  x  thì x   xi* , với xi*  fi  x  , i  1, 2,..., m . i 1 i 1 Ta có xi*  fi  x  , i  1, 2,..., m  xi* , z  x  fi  z   fi  x  , z   n , i  1, 2,..., m m   xi* , z m m i 1 i 1  x   fi  z    fi  x  , z   n i 1 m m i 1 i 1  x* , z  x   fi  z    fi  x  , z   n m    x*     fi   x  , x   n .  i 1  m m  Vậy    fi   x    fi  x  , x   n . i 1  i 1  m m  b) Ta cần chứng minh    fi   x    fi  x  , x   n . i 1  i 1  (1.4) Trước hết ta có mệnh đề sau: Mệnh đề 1.11. Cho f1, f 2 ,..., f m là các hàm lồi hữu hạn trên một tập lồi D   và A là một ma trận thực cấp k  n . Giả sử b  int A  D  . Khi đó hệ x  D, Ax  b, fi  x   0, i  1,..., m không có nghiệm, khi và chỉ khi tồn tại t   k và λi  0, i  1,..., m sao cho m m  λi  1 và t , Ax  b   λi fi  x   0, x  D . i 1 i 1 Bây giờ ta chứng minh b). Trường hợp m  1 là hiển nhiên. Ta chứng minh cho m  2 . Thật vậy:   Lấy x 0   n và x*    f1  f 2  x 0 . Theo định nghĩa của dưới vi phân ta có 15