Luận văn Thạc sĩ Toán học: Một phương pháp quy hoạch lồi giải một lớp bài toán chấp nhận lồi tách

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:51

Thêm vào BST

Báo xấu

9
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục đích của luận văn là giới thiệu lại kiến thức cơ bản về giải tích lồi, bài toán về quy hoạch lồi. Đặc biệt đi sâu vào các bài chấp nhận lồi tách và một phương pháp giải. Mời các bạn tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Một phương pháp quy hoạch lồi giải một lớp bài toán chấp nhận lồi tách

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THÀNH TRUNG MỘT PHƯƠNG PHÁP QUY HOẠCH LỒI GIẢI MỘT LỚP BÀI TOÁN CHẤP NHẬN LỒI TÁCH LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2018
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THÀNH TRUNG MỘT PHƯƠNG PHÁP QUY HOẠCH LỒI GIẢI MỘT LỚP BÀI TOÁN CHẤP NHẬN LỒI TÁCH Chuyên ngành: Toán ứng dụng Mã số: 84 60 112 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 Thái Nguyên - 2018
i Mục lục Lời cảm ơn ii Mở đầu 1 Chương 1 Kiến thức chuẩn bị 2 1.1 Tập lồi, hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Toán tử chiếu lên tập lồi đóng . . . . . . . . . . . . . . . . . . . . . 10 1.3 Dưới vi phân hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . 14 Chương 2 Phương pháp quy hoạch lồi giải bài toán chấp nhận lồi tách 21 2.1 Bài toán quy hoạch lồi . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.1.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.1.2 Điều kiện tồn tại nghiệm . . . . . . . . . . . . . . . . . . . 25 2.1.3 Định lý Karush-kuhn-Tucker . . . . . . . . . . . . . . . . . 28 2.1.4 Phương pháp chiếu đạo hàm . . . . . . . . . . . . . . . . . 32 2.2 Bài toán chấp nhận lồi tách và một phương pháp giải . . . . . . . . 37 2.2.1 Bài toán chấp nhận lồi tách . . . . . . . . . . . . . . . . . . 37 2.2.2 Giới thiệu một mô hình thực tế dẫn tới bài toán . . . . . . . 38 2.2.3 Chuyển bài toán chấp nhận lồi tách về bài toán quy hoạch lồi 39 Kết luận 46 Tài liệu tham khảo 47
ii 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 dưới sự giúp đỡ và hướng dẫn tận tình của GS.TSKH Lê Dũng Mưu. Qua đây, tác giả xin bày tỏ lòng kính trọng và biết ơn sâu sắc tới Thầy, người đã dành nhiều thời gian và tâm huyết để hướng dẫn và tạo điều kiện cho tác giả trong suốt thời gian làm luận văn. Trong quá trình học tập và làm luận văn, từ bài giảng của các giáo sư, phó giáo sư công tác tại Viện Toán học, Viện Công nghệ Thông tin - Viện Hàn lâm Khoa học và Công nghệ Việt Nam, các thầy cô trong trường Đại học Khoa học - Đại học Thái Nguyên, tác giả đã trau dồi thêm rất nhiều kiến thức phục vụ cho việc nghiên cứu và công tác của bản thân. Tác giả xin gửi lời cảm ơn chân thành đến các thầy cô. Tác giả xin chân thành cảm ơn Ban giám hiệu, Phòng đào tạo, khoa Toán - Tin trường Đại học Khoa học - Đại học Thái Nguyên đã quan tâm và giúp đỡ tác giả trong suốt thời gian học tập tại trường. Cuối cùng tác giả xin gửi lời cảm ơn tới gia đình, bạn bè đã luôn động viên, giúp đỡ và tạo điều kiện tốt nhất cho tác giả trong quá trình học tập, nghiên cứu và làm luận văn. Thái Nguyên, tháng 05 năm 2018 Học viên Nguyễn Thành Trung
1 Mở đầu Quy hoạch lồi là một lớp bài toán cơ bản của tối ưu hóa. Một đặc điểm cơ bản nhất của lớp bài toán này 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 quan tâm 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; về phương diện tính toán, đã có khá nhiều phương pháp hữu hiệu cho lớp bài toán này. Các phương pháp đó đã được giới thiệu trong cuốn sách Tối ưu lồi (Convex Optimization) của các tác giả Stephen Boyd and Lieven Vandenberghe do nhà xuất bản Cambridge University Press in năm 2004. Đề tài luận văn "Một phương pháp quy hoạch lồi giải một lớp bài toán chấp nhận lồi tách" có mục đích giới thiệu lại kiến thức cơ bản về giải tích lồi, bài toán về quy hoạch lồi. Đặc biệt đi sâu vào các bài chấp nhận lồi tách và một phương pháp giải. Nội dung luận văn gồm hai chương: Chương 1. "Kiến thức chuẩn bị” giới thiệu các kiến thức cơ bản nhất về tập lồi, hàm lồi và dưới vi phân hàm lồi. Chương 2. "Phương pháp quy hoạch lồi giải bài toán chấp nhận lồi tách" giới thiệu bài toán quy hoạch lồi và một số tính chất của nó. Nhắc lại phương pháp chiếu đạo hàm giải bài toán đó. Cuối cùng tác giả giới thiệu bài toán chấp nhận lồi tách và một phương pháp giải.
2 Chương 1 Kiến thức chuẩn bị Trong chương này, tác giả giới thiệu các kiến thức cơ bản nhất về giải tích lồi, là những kiến thức nền tảng cần thiết phục vụ cho việc nghiên cứu và giải quyết đề tài. Các kiến thức của chương này được tổng hợp từ các tài liệu [1] và [2]. 1.1 Tập lồi, hàm lồi Trước hết ta nhắc lại khái niệm tập lồi trong Rn và các khái niệm có liên quan. Định nghĩa 1.1. Một tập C ⊆ Rn đượ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ồi khi và chỉ khi ∀x, y ∈ C, ∀λ ∈ [0, 1] ⇒ λx + (1 − λ)y ∈ C. Ta nói x là tổ hợp lồi của các điểm (véctơ) x1 , x2 , . . . , xk nếu k X k X j x= λj x , λj > 0 ∀j = 1, . . . , k, λj = 1. j=1 j=1 Tương tự, x là tổ hợp affine của các điểm (véctơ) x1 , . . . , xk nếu k X k X j x= λj x , λj = 1. j=1 j=1 Tập hợp của các tổ hợp affine của x1 , . . . , xk thường được gọi là bao affine của các điểm này.
3 Hình 1.1: (a), (b), (e) - Tập lồi; (c), (d) - Tập không lồi 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 khi và chỉ khi k X k X 1 k ∀k ∈ N, ∀λ1 , . . . , λk > 0 : λj = 1, ∀x , . . . , x ∈ C ⇒ λj xj ∈ C. j=1 j=1 Chứng minh. Điều kiện đủ là hiển nhiên từ định nghĩa. Ta chứng minh điều kiện cần bằng quy nạp theo số điểm. Với k = 2, điều cần chứng minh suy ra ngay từ định nghĩa của tập lồi và tổ hợp lồi. Giả sử mệnh đề đúng với k − 1 điểm. Ta cần chứng minh với k điểm. Giả sử x là tổ hợp lồi của k điểm x1 , . . . , xk ∈ C. Tức là k X k X j x= λj x , λj > 0 ∀j = 1, . . . , k, λj = 1. j=1 j=1 Đặt k−1 X ζ= λj . j=1 Khi đó 0 < ζ < 1 và k−1 k−1 X j k X λj x= λj x + λk x = ζ xj + λk xk . j=1 j=1 ζ Do k−1 X λj =1 j=1 ζ λj và > 0 với mọi j = 1, . . . , k − 1 nên theo giả thiết quy nạp, điểm ζ k−1 X λj y := xj ∈ C. j=1 ζ
4 Ta có x = ζy + λk xk . Do ζ > 0, λk > 0 và k X ζ + λk = λj = 1, j=1 nên x là một tổ hợp lồi của hai điểm y và xk đều thuộc C. Vậy x ∈ C. Lớp các tập lồi là đóng với các phép giao, phép cộng đại số và phép nhân tích Descartes. Cụ thể, ta có mệnh đề sau: Mệnh đề 1.2. Nếu A, B là các tập lồi trong Rn , C là lồi trong Rm , thì các tập sau là lồi : A ∩ B := {x | x ∈ A, x ∈ B}, λA + βB := {x | αa + βb, a ∈ A, b ∈ B, α, β ∈ R}, A × C := {x ∈ Rn+m | x = (a, c) : a ∈ A, c ∈ C}. Định nghĩa 1.2. 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 (tập affine nhỏ nhất chứa C). Ta sẽ ký hiệu tập hợp các điểm trong tương đối của C là riC. Theo định nghĩa trên ta có: riC := {a ∈ C | ∃B : (a + B) ∩ affC ⊂ C}, 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}. Tiếp theo ta nhắc khái niệm hàm lồi và một số khái niệm liên quan. Cho C ⊆ Rn là tập lồi và f : C → R. Ta sẽ ký hiệu domf := {x ∈ C | f (x) < +∞}. Tập dom f được gọi là miền hữu dụng của f . Tập epif := {(x, µ) ∈ C × R | f (x) ≤ µ}
5 đượ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à hiển nhiên là domf = {x ∈ Rn | f (x) < +∞}, epif = {(x, µ) ∈ Rn × R | f (x) ≤ µ}. Do sẽ làm việc với hàm số nhận cả giá trị −∞ và +∞, nên ta quy ước: Nếu λ = 0, thì λf (x) = 0 với mọi x. Định nghĩa 1.3. Cho ∅ 6= C ⊆ Rn lồi và f : C → R. Ta nói f là hàm lồi trên C, nếu epif là một tập lồi trong Rn+1 . Sau đây ta sẽ chủ yếu làm việc với hàm f : Rn → R ∪ {+∞}. Trong trường hợp này, dễ thấy rằng định nghĩa trên tương đương với f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) ∀x, y ∈ C, ∀λ ∈ (0, 1). Hàm f : Rn → R ∪ {+∞} đượ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). Hàm f : Rn → R ∪ {+∞} được gọi là lồi mạnh trên C với hệ số η > 0 nếu ∀x, y ∈ C, ∀λ ∈ (0, 1) có: 1 f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) − ηλ(1 − λ)kx − yk2 . 2 Dễ kiểm tra được rằng, f lồi mạnh trên C với hệ số η > 0 khi và chỉ khi hàm η h(.) := f (.) − k.k2 2 lồi trên C. Bằng qui nạp, dễ dàng chứng minh được rằng, nếu f nhận giá trị hữu hạn trên tập lồi C, thì với mọi số tự nhiên m và mọi x1 , . . . , xm ∈ C thoả mãn λ1 ≥ 0, . . . , m λj = 1, ta có P λm ≥ 0, j=1 m ! m X X f λj x j ≤ λj f (xj ) (bất đẳng thức Jensen). j=1 j=1
6 Hàm f được gọi là một hàm lõm trên C, nếu −f lồi trên C. Ví dụ 1.1. Cho S := {x ∈ Rn | 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 Rn , mặc dù h là một hàm không âm bất kỳ trên mặt cầu S. Ví dụ 1.2. Ví dụ về hàm lồi, hàm lõm Hình 1.2: (a) - Hàm lồi; (b) - Hàm lõm Dưới đây là một điều kiện cần và đủ về hàm lồi, rất tiện ích trong nhiều trường hợp. Mệnh đề 1.3. Một hàm f : C → R là lồi trên C khi và chỉ khi ∀x, y ∈ C, ∀α > f (x), ∀β > f (y), ∀λ ∈ [0, 1] ⇒ f (λx + (1 − λ)y) ≤ λα + (1 − λ)β.
7 Chứng minh. Chứng minh điều kiện cần. Giả sử f lồi. Chọn x, y, α, β như đã nêu trong mệnh đề. Chọn α0 ∈ (f (x), α) và β 0 ∈ (f (y), β). Vậy (x, α0 ) và (y, β 0 ) thuộc epif . Do epif lồi, nên ((1 − λ)x + λy, (1 − λ)α0 + λβ 0 ) ∈ epif. Do đó f ((1 − λ)x + λy) ≤ (1 − λ)α0 + λβ 0 < (1 − λ)α + λβ. Chứng minh điều kiện đủ. Chọn (x, µ) và (y, ν) thuộc epif và λ ∈ (0, 1). Thế thì với mọi > 0, ta có f (x) < µ + , f (y) < ν + . Do đó f [(1 − λ)α0 + λβ 0 ] < (1 − λ)(µ + ) + λ(ν + ) = (1 − λ)µ + λν + . Điều này đúng với mọi > 0, nên cho → 0, ta được f [(1 − λ)α0 + λβ 0 ] ≤ (1 − λ)µ + λν. Chứng tỏ (1 − λ)(x, µ) + λ(y, ν) ∈ epif. Vậy f lồi. Dưới đây là một định nghĩa khác, tương đương về hàm lồi, lồi mạnh, dựa vào khái niệm hệ số lồi. Định nghĩa 1.4. Cho f : Rn → R ∪ {+∞} (không nhất thiết lồi), C ⊆ Rn là một tập lồi khác rỗng và η là một số thực. Ta nói η là hệ số lồi của f trên C, nếu với mọi λ ∈ (0, 1), mọi x, y thuộc C, ta có 1 f [(1 − λ)x + λy] ≤ (1 − λ)f (x) + λf (y) − ηλ(1 − λ)kx − yk2 . 2
8 Hiển nhiên nếu η = 0 thì f lồi trên C. Nếu f có hệ số lồi trên C là η > 0, thì f lồi mạnh trên C với hệ số η. Một hàm f được gọi là chính thường nếu domf 6= ∅ và f (x) > −∞ với mọi x. Hàm f được gọi là đóng, nếu epif là một tập đóng trong Rn+1 . Như đã nói ở trên, 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), nếu x ∈ C,  fe (x) := +∞, nếu x 6∈ C.  Hiển nhiên fe (x) = f (x) với mọi x ∈ C và fe lồi trên Rn . Hơn nữa fe là chính thường khi và chỉ khi f chính thường. Tương tự fe đóng khi và chỉ khi f đóng. Chú ý rằng, nếu f là một hàm lồi trên Rn thì domf là một tập lồi, vì domf chính là hình chiếu trên Rn của epif , tức là: domf = {x | ∃µ ∈ R : (x, µ) ∈ epif }. Từ định nghĩa của tập trên đồ thị, ta thấy rằng một hàm lồi được xác định bởi trên đồ thị của nó. Mệnh đề đưới đây cho thấy lý do vì sao trong thực tế người ta thường chỉ quan tâm đến các hàm lồi chính thường. Mệnh đề 1.4. Giả sử f là một hàm lồi không chính thường trên Rn và f 6≡ +∞. Khi đó f (x) = −∞ với mọi x ∈ ri(domf ). Chứng minh. Theo định nghĩa hàm chính thường, nếu domf 6= ∅, thì tồn tại một x0 sao cho f (x0 ) = −∞. Giả sử x ∈ ri(domf ). Theo định nghĩa của điểm trong tương đối, tồn tại y ∈ domf thỏa mãn x = λy + (1 − λ)x0 với λ ∈ (0, 1). Do f lồi và f (y) < +∞, nên f (x) ≤ λf (y) + (1 − λ)f (x0 ) = −∞. Theo mệnh đề trên, để tránh làm việc với các hàm lồi đồng nhất với −∞ tại miền trong tương đối của miền hữu dụng, từ nay về sau, nếu không nhấn mạnh gì thêm,
9 khi nói đến một hàm lồi trên Rn , ta luôn hiểu đó là một hàm chính thường, tức là nó không đồng nhất với +∞ và không nhận giá trị −∞. Mệnh đề 1.5. Nếu f là một hàm lồi trên Rn , thì các tập mức Lf (α) := {x | f (x) ≤ α}, lf (α) := {x | f (x) < α} là lồi với mọi α ∈ R. Chứng minh. Trường hợp α = +∞ hoặc −∞ là hiển nhiên (nhớ rằng tập rỗng là lồi). Lấy x, y ∈ lf (α). Tức là f (x) < α, f (y) < α. Do f lồi, nên theo Mệnh đề 1.3, với mọi λ ∈ (0, 1) ta có: f (λx + (1 − λ)y) < λα + (1 − λ)α = α. Vậy λx + (1 − λ)y ∈ lf (α). \ Tập Lf (α) = lf (µ), nên nó cũng là tập lồi. µ>α Một lớp hàm lồi rất quan trọng là hàm lồi thuần nhất dương. Nhắc lại rằng một hàm f được gọi là thuần nhất dương (bậc 1) trên Rn nếu f (λx) = λf (x) ∀x ∈ Rn , ∀λ > 0. Một hàm thuần nhất dương không nhất thiết là hàm lồi, tuy nhiên ta dễ dàng chứng minh mệnh đề sau: Mệnh đề 1.6. Cho f là một hàm thuần nhất dương trên Rn . Khi đó f lồi khi và chỉ khi nó là dưới cộng tính, theo nghĩa f (x + y) ≤ f (x) + f (y) ∀x, y. Một hàm thuần nhất dương và dưới cộng tính được gọi là dưới tuyến tính. Một ví dụ điển hình về hàm dưới tuyến tính là hàm chuẩn f (x) = kxk.
10 1.2 Toán tử chiếu lên tập lồi đóng Trong mục này ta sẽ chứng minh sự tồn tại và tính duy nhất của hình chiếu xuống một tập lồi đóng. Tiếp đến sẽ khảo sát một số tính chất cơ bản của toán tử chiếu. Định nghĩa 1.5. Cho ∅ 6= C ⊆ Rn (không nhất thiết lồi) và y là một véctơ bất kỳ, đặt dC (y) := inf kx − yk. Ta nói dC (y) là khoảng cách từ y đến C. Nếu tồn tại x∈C π ∈ C sao cho dC (y) = kπ − yk, thì ta nói π là hình chiếu của y trên C. Theo định nghĩa,ta thấy rằng hình chiếu pC (y) của y trên C sẽ là nghiệm của 1 bài toán tối ưu minx kx − yk2 | x ∈ C . Nói cách khác việc tìm hình chiếu của 2 y trên C có thể đưa về việc tìm cực tiểu của hàm toàn phương kx − yk2 trên C. Ta ký hiệu π = pC (y), hoặc đơn giản hơn là p(y) nếu không cần nhấn mạnh đến tập chiếu C. Chú ý rằng, nếu C 6= ∅, thì dC (y) hữu hạn, vì 0 ≤ dC (y) ≤ ky − xk với mọi x ∈ C. Cho C ⊆ Rn , x0 ∈ C. Nón pháp tuyến (ngoài) của tập C tại x0 là tập hợp NC (x0 ) := {w | wT (x − x0 ) ≤ 0 ∀x ∈ C}. Hình 1.3: Hình chiếu vuông góc
11 Mệnh đề 1.7. Cho C là một tập lồi đóng khác rỗng. Khi đó: (i) Với mọi y ∈ Rn , π ∈ C hai tính chất sau là tương đương: a) π = pC (y), b) y − π ∈ NC (π). (ii) Với mọi y ∈ Rn , 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 6∈ C, thì hpC (y) − y, x − pC (y)i = 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à hpC (y) − y, x − pC (y)i ≥ 0, ∀x ∈ C, và hpC (y) − y, y − pC (y)i < 0. (iv) Ánh xạ y ,→ pC (y) có các tính chất sau: a) kpC (x) − pC (y)k ≤ kx − yk ∀x, ∀y, (tính không giãn), b) hpC (x) − pC (y), x − yi ≥ kpC (x) − pC (y)k2 , (tính đồng bức). Chứng minh. (i) Giả sử có a). Lấy x ∈ C và λ ∈ (0, 1). Đặt 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 kπ − yk ≤ ky − xλ k. Hay kπ − yk2 ≤ kλ(x − π) + (π − y)k2 . Khai triển vế phải, ước lược và chia hai vế cho λ > 0, ta có λkx − πk2 + 2 hx − π, π − yi ≥ 0. Điều này đúng với mọi x ∈ C và λ ∈ (0, 1). Do đó khi cho λ tiến đến 0, ta được hπ − y, x − πi ≥ 0 ∀x ∈ C.
12 Vậy y − π ∈ NC (π). Bây giờ giả sử có b). Với mọi x ∈ C, có 0 ≥ (y − π)T (x − π) = (y − π)T (x − y + y − π) = ky − πk2 + (y − π)T (x − y). Từ đây và b), dùng bất đẳng thức Cauchy-Schwarz ta có: ky − πk2 ≤ (y − π)T (y − x) ≤ ky − πkky − xk. Suy ra ky − πk ≤ ky − xk ∀x ∈ C, và do đó π = p(y). (ii) Do dC (y) = inf kx − yk, nên theo định nghĩa của cận dưới đúng, tồn tại một x∈C dãy {xk } ∈ C sao cho lim kxk − yk = dC (y) < +∞. k Vậy dãy {xk } bị chặn, do đó nó có một dãy con {xkj } hội tụ đến một điểm π nào đó. Do C đóng, nên π ∈ C. Vậy kπ − yk = lim kxkj − yk = lim kxk − yk = dC (y). j k Chứng tỏ π là hình chiếu của y trên C. 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 − π ∈ NC (π), y − π 1 ∈ NC (π 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 kπ − π 1 k2 ≤ 0, và do đó π = π 1 . (iii) Do y − π ∈ NC (π), nên hπ − y, x − πi ≥ 0 ∀x ∈ C.
13 Vậy hπ − y, xi = hπ − y, πi 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 6= π, nên hπ − y, y − πi = −kπ − yk2 < 0. (iv) Theo phần (ii) ánh xạ x ,→ pC (x) xác định khắp nơi. Do z−p(z) ∈ NC (p(z)) với mọi z, nên áp dụng với z = x và z = y, ta có hx − p(x), p(y) − p(x)i ≤ 0 và hy − p(y), p(x) − p(y)i ≤ 0. Cộng hai bất đẳng thức lại sẽ được hp(y) − p(x), p(y) − p(x) + x − yi ≤ 0. Từ đây và theo bất đẳng thức Cauchy-Schwarz, suy ra kp(x) − p(y)k ≤ kx − yk. Để 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 p(x) và p(y), ta có: hp(x) − x, p(x) − p(y)i ≤ 0. hy − p(y), p(x) − p(y)i ≤ 0. Cộng hai bất đẳng thức ta được hp(x) − p(y) + y − x, p(x) − p(y)i = hp(x) − p(y), y − xi + kp(x) − p(y)k2 ≤ 0. Chuyển vế ta có hp(x) − p(y), x − yi ≥ kp(x) − p(y)k2 . Đây chính là tính đồng bức cần được chứng minh.
14 1.3 Dưới vi phân hàm lồi Định nghĩa 1.6. Cho f : Rn → R ∪ {+∞} và x0 ∈ R sao cho f (x0 ) < +∞. Nếu với một vectơ y ∈ Rn mà giới hạn f (x0 + λy) − f (x0 ) lim λ↓0 λ tồn tại (hữu hạn hay vô hạn), thì ta nói f có đạo hàm theo hướng y tại điểm x0 . Ta sẽ ký hiệu giới hạn này là f 0 (x0 , y). Mệnh đề 1.8. Cho f : Rn → R ∪ {+∞} lồi. Khi đó với mọi x ∈domf và mọi y ∈ Rn , ta có: i) ϕ là hàm đơn điệu không giảm trên (0, +∞); f 0 (x, y) tồn tại với mọi y ∈ Rn và f (x + λy) − f (x) f 0 (x, y) := . λ ii) Hàm f 0 (x, .) thuần nhất dương bậc 1. Ngoài ra nếu f 0 (x, .) > −∞ thì: a) Hàm f 0 (x, .) là dưới tuyến tính trên Rn (do đó nó là hàm lồi chính thường trên Rn ). b) −f 0 (x, −y) ≤ f 0 (x, y) ∀y ∈ Rn . c) Hàm f 0 (x, .) nhận giá trị hữu hạn trên F khi và chỉ khi x ∈ridomf , trong đó F là không gian con của domf . Định nghĩa 1.7. Cho f : Rn → R ∪ {+∞}. Ta nói x∗ ∈ Rn là dưới đạo hàm của f tại x nếu hx∗ , z − xi + f (x) ≤ f (z), ∀z. Tương tự như đối với hàm lồi khả vi thông thường, biểu thức này có nghĩa là phương trình tiếp tuyến nằm dưới đồ thị của hàm số. Tuy nhiên khác với trường hợp khả vi, tiếp tuyến ở đây có thể không tồn tại duy nhất. Ký hiệu tập hợp tất cả các dưới đạo hàm của f tại x là ∂f (x). Nói chung đây là
15 một tập (có thể bằng rỗng) trong Rn . Khi ∂f (x) 6= ∅, thì ta nói hàm f khả dưới vi phân tại x. Theo định nghĩa, một điểm x∗ ∈ ∂f (x) khi và chỉ khi nó thỏa mãn một hệ vô hạn các bất đẳng thức tuyến tính. Như vậy ∂f (x) là giao của các nửa không gian đóng. Vậy ∂f (x) luôn là một tập lồi đóng (có thể rỗng). Ta ký hiệu dom(∂f ) := {x | ∂f (x) 6= ∅}. Ví dụ 1.3. f = δC là hàm chỉ của một tập lồi C 6= ∅. Khi đó với x0 ∈ C, ∂δC (x0 ) = {x∗ | x∗ , x − x0 ≤ δC (x) ∀x}. Với x 6∈ C, thì δC (x) = +∞, nên bất đẳng thức này luôn đúng. Vậy ∂δC (x0 ) = {x∗ | x∗ , x − x0 ≤ 0 ∀x ∈ C} = NC (x0 ). Vậy dưới vi phân của hàm chỉ của một tập lồi C khác rỗng tại một điểm x0 ∈ C chính là nón pháp tuyến ngoài của C tại x0 . Mệnh đề dưới đây cho một định nghĩa khác tương đương của dưới vi phân. Mệnh đề 1.9. Cho f : Rn → R ∪ {+∞} lồi, chính thường. (i) x∗ ∈ ∂f (x) khi và chỉ khi f 0 (x, y) ≥ hx∗ , yi , ∀y. Nếu x ∈ ri(domf ), thì f 0 (x, y) = sup hx∗ , yi với mọi y. x∗ ∈∂f (x) (ii) Nếu f là hàm lồi chính thường trên Rn , thì với mọi x ∈ dom(∂f ), ta có f (x) = f¯(x) và ∂f (x) = ∂ f¯(x). Chứng minh. (i) Theo định nghĩa x∗ ∈ ∂f (x) ⇔ hx∗ , z − xi + f (x) ≤ f (z) ∀z. Với bất kỳ y, lấy z = x + λy, λ > 0, ta có hx∗ , λyi + f (x) ≤ f (x + λy).
16 Từ đây suy ra f (x + λy) − f (x) hx∗ , yi ≤ ∀λ > 0. λ Theo định nghĩa của f 0 (x, y), từ đây suy ra hx∗ , yi ≤ f 0 (x, y) ∀y. (1.1) Ngược lại giả sử (1.1) thỏa mãn. Lấy z bất kỳ và áp dụng với (1.1) với y = z − x và λ = 1. Ta có f (x + y) − f (x) ≥ f 0 (x, y) = f 0 (x, z − x) ≥ hx∗ , z − xi ∀z. Vậy x∗ ∈ ∂f (x). Chú ý rằng do f 0 (x, .) là hàm lồi, thuần nhất dương, nên mọi hàm non affine của f 0 (x, .) đều tuyến tính, tức là có dạng hp, .i. Vậy nếu hp, .i là hàm non affine của f 0 (x, .) trên Rn , thì hp, yi ≤ f 0 (x, y) ∀y. Theo Mệnh đề 1.9 ta có p ∈ ∂f (x). Hơn nữa, do f 0 (x, .) là một hàm lồi đóng, nên theo định lý xấp xỉ tập lồi nó là bao trên của các hàm non của nó. Vậy f 0 (x, y) = sup hp, yi . p∈∂f (x) (ii) Cho x ∈ dom(∂f ) và x∗ ∈ ∂f (x). Theo định nghĩa của f¯, của hàm liên hợp và do x∗ ∈ ∂f (x) ta có: f (x) ≥ f¯(x) = f ∗∗ (x) ≥ hx∗ , xi − f ∗ (x∗ ) = f (x). Từ đây suy ra f (x) = f¯(x). Nếu y ∗ ∈ ∂ f¯(x), thì với mọi z có: f (z) ≥ f¯(z) ≥ f¯(x) + hy ∗ , z − xi = f (x) + hy ∗ , z − xi . Suy ra ∂ f¯(x) ⊆ ∂f (x). Để chứng minh điều ngược lại, lấy z 0 ∈ ri(domf ). Với mọi z ta có f¯(z) = lim f (1 − t)z + tz 0 . t&0