Giải Thuật Cho Bài Toán Tối ưu Không Trơn Trong Chỉnh Hóa Thưa Và ...

Tải bản đầy đủ (.pdf) (55 trang)

1. Trang chủ
>>
2. Thạc sĩ - Cao học
>>
3. Sư phạm

Giải thuật cho bài toán tối ưu không trơn trong chỉnh hóa thưa và ứng dụng

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (512.75 KB, 55 trang )

ĐẠI HỌC ĐÀ NẴNGTRƯỜNG ĐẠI HỌC SƯ PHẠM——————————–NGUYỄN THỊ LIÊU NOAGIẢI THUẬTCHO BÀI TỐN TỐI ƯU KHƠNG TRƠNTRONG CHỈNH HĨA VÀ ỨNG DỤNGLUẬN VĂN THẠC SĨ TOÁN HỌCĐà Nẵng - 2017 ĐẠI HỌC ĐÀ NẴNGTRƯỜNG ĐẠI HỌC SƯ PHẠM——————————–NGUYỄN THỊ LIÊU NOAGIẢI THUẬTCHO BÀI TỐN TỐI ƯU KHƠNG TRƠNTRONG CHỈNH HĨA THƯA VÀ ỨNG DỤNGChuyên ngành: Giải tíchMã số: 60.46.01.02LUẬN VĂN THẠC SĨ TOÁN HỌCNgười hướng dẫn khoa học:TS. Phạm Quý MườiĐà Nẵng - 2017 LỜI CAM ĐOANTơi xin cam đoan đây là cơng trình nghiên cứu của riêng tôi.Các số liệu, kết quả nêu trong luận văn là trung thực và chưa từng đượcai cơng bố trong bất kì cơng trình nào khác.Tác giảNguyễn Thị Liêu Noa LỜI CẢM ƠNLời đầu tiên tác giả xin gửi lời cảm ơn đến Ban Giám Hiệu Trường Đạihọc Sư phạm - Đại học Đà Nẵng đã tạo điều kiện thuận lợi cho tác giảtrong suốt quá trình học và làm luận văn này.Tác giả xin gửi lời cảm ơn sâu sắc tới giáo viên hướng dẫn, TS. PhạmQuý Mười, đã tận tình hướng dẫn trong suốt quá trình thực hiện và hoànthiện luận văn.Tác giả cũng xin gửi lời cảm ơn chân thành nhất đến các thầy cô đãtrực tiếp giảng dạy tác giả trong suốt quá trình học tập và các q thầy cơtrong khoa Tốn của Trường Đại học Sư phạm Đà Nẵng đã giúp đỡ trongthời gian qua.Cuối cùng, tác giả cũng xin gửi lời cảm ơn đến các thành viên tronglớp Giải tích K31 đã xây dựng một tập thể lớp đồn kết, gắn bó và giúpđỡ lẫn nhau trong tồn bộ khóa học.Tác giảNguyễn Thị Liêu Noa MỤC LỤCMỞ ĐẦU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1CHƯƠNG 1. KIẾN THỨC CƠ SỞ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.1. KHÔNG GIAN HILBERT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2. HỆ TRỰC CHUẨN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.3. TOÁN TỬ TUYẾN TÍNH LIÊN TỤC VÀ TỐN TỬ COMPACT . . . . . 91.4. HÀM SỐ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.5. DƯỚI VI PHÂN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.6. HÀM PHẠT CĨ TÍNH CHẤT THƯA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151.7. TOÁN TỬ CO RÚT MỀM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16CHƯƠNG 2. CÁC GIẢI THUẬT CHO BÀI TOÁN TỐI ƯU KHƠNGTRƠN TRONG CHỈNH HĨA THƯA . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.1. ĐIỀU KIỆN CÓ NGHIỆM CỦA BÀI TOÁN . . . . . . . . . . . . . . . . . . . . . . . 202.2. PHƯƠNG PHÁP KIỂU GRADIENT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212.2.1. Tính chất hội tụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242.2.2. Các tiêu chuẩn chọn kích thước bước . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292.2.3. Giải thuật kiểu Gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302.3. GIẢI THUẬT CẢI TIẾN CỦA BECK . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30CHƯƠNG 3. MỘT SỐ VÍ DỤ VÀ ỨNG DỤNG . . . . . . . . . . . . . . . . . . 353.1. BÀI TỐN TỐI ƯU KHƠNG TRƠN HAI BIẾN . . . . . . . . . . . . . . . . . . . 353.1.1. Bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 MỤC LỤC3.1.2. Chương trình Matlab cho giải thuật kiểu Gradient . . . . . . . . . . . . . . . . . 353.1.3. Chương trình Matlab cho giải thuật cải tiến của Beck . . . . . . . . . . . . . . 363.1.4. Sự hội tụ và nghiệm số của các giải thuật . . . . . . . . . . . . . . . . . . . . . . . . 373.2. PHƯƠNG TRÌNH TÍCH PHÂN LOẠI 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 393.2.1. Bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393.2.2. Rời rạc bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393.2.3. Áp dụng chỉnh hóa thưa cho bài tốn . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403.2.4. Chương trình Matlab cho giải thuật kiểu Gradient . . . . . . . . . . . . . . . . . 413.2.5. Chương trình Matlab cho giải thuật cải tiến của Beck . . . . . . . . . . . . . . 423.2.6. Minh họa nghiệm số và sự hội tụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43KẾT LUẬN VÀ KIẾN NGHỊ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45TÀI LIỆU THAM KHẢO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464 BẢNG KÍ HIỆU: Tập các số thực: Tập các số thực mở rộng: Không gian tiền Hilbert hoặc không gian Hilbertn chiềux: Chuẩn của xK: Chuẩn của toán tử KH: Khơng gian HilbertSτ: Hàm co rútSτ: Tốn tử co rút mềmδf: Dữ liệu xấp xỉ của fx := y: x được định nghĩa bằng y∀x: Với mọi x∃x: Tồn tại xx, y: Tích vơ hướng của x và y(X, ., . ) : Không gian tiền Hilbert(X, . ) : Không gian định chuẩnC[a, b]: Không gian của các hàm liên tục trên [a,b]L(X, Y ) : Không gian gồm tất cả các ánh xạ tuyến tính bị chặntừ X vào YK(x, r) : Hình cầu tâm x, bán kính rint(M ) : Phần trong của Mcl(M ): Bao đóng của M2L (a, b) : Khơng gian các hàm bình phương khả tích trên (a, b)SpanA: Khơng gian con sinh bởi tập AC(f, α) : Tập mức dưới của f với mức α∂f: Dưới vi phân của hàm fRRRn DANH SÁCH CÁC HÌNH VẼSố hiệu hình vẽTên hình vẽTrang2.1Đồ thị của hàm Θ(v), Θs (v, u) và Js (u)22n3.1Sự hội tụ của Θ(x ) ứng với n=5037n3.2Sự hội tụ của Θ(x ) ứng với n=10038n3.3Sự hội tụ của Θ(v )44 1MỞ ĐẦU1. Lịch sử vấn đề và lý do chọn đề tàiTối ưu là một trong những lĩnh vực kinh điển của tốn học, có ảnhhưởng đến hầu hết các lĩnh vực khoa học - công nghệ và kinh tế - xã hội.Trong thực tế, việc tìm nghiệm tối ưu cho một bài tốn nào đó chiếm mộtvai trị hết sức quan trọng.Bài tốn tối ưu có thể phát biểu như sau: Tìm min f (x) trong đó, f (x)x∈Dlà hàm mục tiêu, x là nghiệm của bài toán, D được biểu diễn như là tậpcác ràng buộc thỏa mãn một số tính chất cho trước của bài tốn. Khi đó,tồn tại x∗ ∈ D đem lại giá trị nhỏ nhất cho hàm mục tiêu, lúc này ta nóix∗ là nghiệm tối ưu của bài tốn. Để tìm nghiệm số cho bài tốn tối ưu,chúng ta cần có một giải thuật phù hợp. Đối với mỗi giải thuật, cần phảixây dựng cơ sở lý thuyết của giải thuật, chứng minh tính hữu hạn hay hộitụ của nó.Ngày nay, do nhu cầu phát triển không ngừng của khoa học kỹ thuật,ngày càng xuất hiện nhiều bài toán với hàm mục tiêu f (x) là khơng trơn(khơng có đạo hàm) [10], [14]. Ví dụ như các phương pháp chỉnh hóa thưa,chỉnh hóa biến phân cho bài toán ngược, đều dẫn đến các bài tốn tối ưukhơng trơn [14].Phương pháp chỉnh hóa thưa được nghiên cứu trong 10 năm trở lạiđây. Phương pháp này đã và đang được ứng dụng trong nhiều lĩnh vựckhác nhau như xử lí ảnh, xác định tham số của phương trình đạo hàmriêng,. . . [12].Với mong muốn nghiên cứu và tìm hiểu bài tốn tối ưu khơng trơn, đặcbiệt là bài toán tối ưu xuất hiện trong lĩnh vực chỉnh hóa thưa nên tơichọn đề tài nghiên cứu: “Giải thuật cho bài tốn tối ưu khơng trơntrong chỉnh hóa thưa và ứng dụng”. Đề tài nhằm nghiên cứu sự tồn 2tại nghiệm, các điều kiện cần và đủ cho nghiệm của bài toán. Đặc biệt, đềtài dành phần lớn cho việc nghiên cứu hai giải thuật để giải bài toán này.2. Mục đích nghiên cứuNghiên cứu và xây dựng giải thuật cho các bài tốn tối ưu khơng trơntrong chỉnh hóa thưa và chứng minh các tính chất hội tụ của nó. Từ đó,ứng dụng vào để giải một số ví dụ cụ thể.3. Đối tượng và phạm vi nghiên cứuBài tốn tối ưu khơng trơn trong chỉnh hóa thưa.Các giải thuật cho các bài tốn tối ưu khơng trơn: Giải thuật kiểuGradient và giải thuật cải tiến của Beck.4. Phương pháp nghiên cứuVới đề tài: “Giải thuật cho bài tốn tối ưu khơng trơn trongchỉnh hóa thưa và ứng dụng” tôi đã sử dụng các phương pháp nghiêncứu sau:Thu thập, phân tích và tổng hợp tài liệu.Phân loại và hệ thống hóa lý thuyết.Trao đổi với giáo viên hướng dẫn.5. Ý nghĩa khoa học và thực tiễnĐề tài sẽ trình bày chi tiết cở sở lý thuyết và các giải thuật để giải cácbài tốn tối ưu khơng trơn trong chỉnh hóa thưa. Luận văn có thể sẽ làtài liệu tham khảo cho các sinh viên, học viên cao học và những người cónhu cầu tìm hiểu về các bài tốn tối ưu khơng trơn trong chỉnh hóa thưa.6. Cấu trúc luận vănLuận văn gồm 3 chương:Chương 1: Kiến thức cơ sở.Trong chương này, chúng tơi trình bày các khái niệm, định lý cơ bản vềgiải tích hàm và giải tích lồi. Một số tính chất của hàm phạt có tính chấtthưa, tốn tử co rút mềm sẽ sử dụng trong luận văn. 3Chương 2: Các giải thuật cho bài toán tối ưu khơng trơn trongchỉnh hóa thưa.Trong chương này, luận văn sẽ nghiên cứu hai giải thuật để giải bàitoán tối ưu khơng trơn trong chỉnh hóa thưa: Giải thuật kiểu Gradient vàgiải thuật cải tiến của Beck. Luận văn tập trung vào chứng minh các tínhchất hội tụ của các phương pháp này trong khơng gian Hilbert và cáchchọn kích thước bước của mỗi giải thuật.Chương 3: Một số ví dụ và ứng dụng.Trong chương này, luận văn sẽ áp dụng hai giải thuật để giải một số bàitoán cụ thể và xem xét các tính chất hội tụ đã được nghiên cứu lý thuyếttrong Chương 2. 4CHƯƠNG 1KIẾN THỨC CƠ SỞTrong chương này, chúng tôi nhắc lại một số khái niệm, định lý cơ bảnvề giải tích hàm và giải tích lồi. Các tính chất, định lý được nêu ở đâychúng tôi không chứng minh và các chứng minh của chúng có thể thamkhảo trong các tài liệu cơ bản về giải tích hàm và giải tích lồi, chẳng hạnnhư trong [1], [2], [3], [11].Chương này cũng đề cập đến một số tính chất của hàm phạt có tínhchất thưa, tốn tử co rút mềm. Các tính chất này được sử dụng trongChương 2 và đã được nghiên cứu trong các tài liệu [10], [14].1.1. KHÔNG GIAN HILBERTĐịnh nghĩa 1.1.1. (Tích vơ hướng). Cho X là khơng gian vectơ trêntrường số thực R. Tích vơ hướng xác định trong X là một ánh xạ:., . : X × X → R(x, y) → x, ythỏa mãn các điều kiện sau đây:i) x, x ≥ 0, ∀x ∈ X vàx, x = 0 ⇔ x = 0,ii) x, y = y, x ∀x, y ∈ X ,iii) x + x , y = x, y + x , y , ∀x, x , y ∈ X ,iv) λx, y = λ x, y∀x, y ∈ X, ∀λ ∈ R.Số x, y được gọi là tích vơ hướng của hai vectơ x và y . Một không gianvectơ X cùng với tích vơ hướng ., . được gọi là khơng gian tiền Hilbert,kí hiệu là (X, ., . ) hoặc ngắn gọn lại là X nếu tích vơ hướng đã được xácđịnh rõ. 5Nhận xét 1.1.2. Từ các tính chất i), ii) ta suy ra được các tính chất:v) x, y + y = x, y + x, y , ∀x, y, y ∈ X ,vi) x, λy = λ x, y ∀x, y ∈ X, ∀λ ∈ R.Định nghĩa 1.1.3. (Chuẩn). Cho X là không gian vectơ trên trường sốthực R. Một chuẩn trên X là ánh xạ. :X→Rthỏa mãn các tính chất sau đây:i) x > 0, ∀x ∈ X với x = 0,ii) αx = |α| x , ∀x ∈ X và α ∈ R,iii) x + y ≤ x + y , ∀x, y ∈ X .Một không gian vectơ X trên trường số thực R với chuẩn . được gọilà khơng gian định chuẩn trên trường R, kí hiệu là (X, . ) hoặc được viếtngắn gọn lại là X nếu chuẩn đã được xác định rõ.Tính chất (iii) được gọi là bất đẳng thức tam giác. Áp dụng đồng nhấtthức x = (x − y) + y và y = (y − x) + x từ hai kết quả này ta được bấtđẳng thức tam giác thứ hai x − y ≤ x − y , ∀x, y ∈ X .Định lí 1.1.4. Cho (X, ., . ) là không gian tiền Hilbert. Ánh xạ.:X → R được định nghĩa như sau:x, x , ∀x ∈ Xx :=là một chuẩn.Từ Định nghĩa 1.1.3 ta có các tính chất sau:1. Bất đẳng thức Cauchy – Schwarz: | x, y | ≤ x . y ,2. x + y2+ x−y2=2x2+ y2(đẳng thức hình bình hành).Ví dụ 1.1.5. 1) Rn là không gian tiền Hilbert n chiều trên R với tích vơnhướng x, y :=xk y k .k=12) Khơng gian C[a, b] của các hàm liên tục trên [a,b] là một không gian 6tiền Hilbert trên R với tích vơ hướngbx (t) y (t)dt,(x, y)L2 :=x, y ∈ C [a, b] .aChuẩn tương ứng được gọi là chuẩn Euclidean và được kí hiệu như sau:bxL2:=|x (t)|2 dt,(x, x)L2 =x ∈ C [a, b] .aTa kí hiệu:K (x, r) := {y ∈ X : y − x < r}là hình cầu tâm x ∈ X , bán kính r.Định nghĩa 1.1.6. Cho X là không gian định chuẩn trên trường R.a) Một tập con M ⊂ X được gọi là bị chặn nếu tồn tại r > 0 sao choM ⊂ K(x, r). Tập M ⊂ X được gọi là tập mở nếu với mọi x ∈ M tồn tạiε > 0 sao cho K(x, ε) ⊂ M . Tập M ⊂ X được gọi là tập đóng nếu phầnbù X\M là tập mở.b) Dãy (xk )k ⊂ X được gọi là bị chặn nếu tồn tại c > 0 sao cho xk ≤ c∀k . Dãy (xk )k ⊂ X được gọi là hội tụ nếu tồn tại x ∈ X sao cho x − xkhội tụ đến 0 trong R. Ta kí hiệu lim xk = x. Dãy (xk )k ⊂ X được gọik→∞là dãy Cauchy nếu với mỗi ε > 0 tồn tại N ∈ N sao cho xm − xk < ε∀m, k ≥ N .c) Cho (xk )k ⊂ X là một dãy, x ∈ X được gọi là điểm tụ nếu tồn tạimột dãy con (xkn )n hội tụ đến x.d) Tập M ⊂ X được gọi là compact nếu mọi dãy trong M đều có điểmtụ trong M.Ta có các tập:int(M ) := {x ∈ M | ∃ε > 0 : K (x, ε) ⊂ M } ,được gọi là phần trong của M vàcl(M ) :=x ∈ M | ∃(xk )k ⊂ M : x = lim xk ,được gọi là bao đóng của M .k→∞ 7Định lí 1.1.7. Cho X là khơng gian định chuẩn trên R và M ⊂ X .a) M là đóng nếu và chỉ nếu M = cl(M ) và M là mở nếu và chỉ nếuM = int(M ).b) Nếu M = X là khơng gian con tuyến tính, khi đó int(M ) = ∅ vàcl(M) cũng là khơng gian con tuyến tính.c) Trong khơng gian hữu hạn chiều, mọi khơng gian con là đóng.d) Mọi tập compact là đóng và bị chặn. Trong không gian hữu hạn chiều,ngược lại cũng đúng (theo định lí Bolzano-Weierstrass): Trong khơng gianđịnh chuẩn hữu hạn chiều, mọi tập đóng và bị chặn là compact.Định nghĩa 1.1.8. (Không gian Banach, không gian Hilbert)Một không gian định chuẩn X trên trường số thực R được gọi là đầyđủ hoặc không gian Banach nếu mọi dãy Cauchy đều hội tụ trong X . Mộtkhông gian tiền Hilbert đầy đủ được gọi là khơng gian Hilbert.Ví dụ 1.1.9. 1) Không gian Rn là không gian Hilbert với tích vơ hướngchính tắc.2) Trong l2 với x = (xk ), y = (yk ), ta định nghĩa∞xk yk ,x, y :=k=12thì ., . là tích vơ hướng, (l , ., . ) là không gian Hilbert.Định nghĩa 1.1.10. (Không gian tách). Không gian định chuẩn X đượcgọi là tách nếu tồn tại một tập con trù mật đếm được M ⊂ X sao chocl(M ) = X .Ví dụ 1.1.11. 1) Không gian Rn là một không gian tách và tập con đếmđược M là tập tất cả các vectơ với hệ số hữu tỉ.2) L2 (a, b) và C[a,b] đều là khơng gian tách, tập M có thể lấy là tậpcác đa thức với hệ số hữu tỉ.1.2. HỆ TRỰC CHUẨNTrong phần này, ta cho X là không gian Hilbert tách trên trường sốthực R. 8Định nghĩa 1.2.1. (Hệ trực chuẩn). Một tập đếm được các phần tửA = {xk : k = 1, 2, 3, ...} được gọi là hệ trực chuẩn nếu:1. xk , xj = 0, ∀k = j .2. xk = 1, ∀k ∈ N.A được gọi là đầy đủ hoặc hệ trực chuẩn cực đại nếu khơng có hệ trựcchuẩn B với A ⊂ B và A = B .Có thể sử dụng bổ đề Zorn’s để chỉ ra rằng mọi khơng gian Hilbert táchđều có một hệ trực chuẩn cực đại. Hơn nữa, từ đại số tuyến tính ta biếtrằng mọi tập đếm được các phần tử độc lập tuyến tính của X có thể trựcgiao.Cho bất kỳ một tập A ⊂ X . Khi đónαk xk : α ∈ R, xk ∈ A, n ∈ Nspan A :=k=1là khơng gian con của X sinh bởi A.Định lí 1.2.2. Cho A = {xk : k = 1, 2, 3, ...} là hệ trực chuẩn. Khi đóa) Mọi tập con hữu hạn của A đều độc lập tuyến tính.b) Nếu A hữu hạn, A = {xk : k = 1, 2, 3, ..., n} thì với mọi x ∈ X tồntại duy nhất hệ số α ∈ R, k = 1, 2, ..., n, sao chonx−αk xk ≤ x − a , ∀a ∈ span Ak=1hệ số αk được cho bởi αk = x, xk , ∀k = 1, ..., n.c) ∀x ∈ X , ta có bất đẳng thức Bessel:∞2| x, xk |2 ≤ x ,k=1∞x, xk xk hội tụ trong X .và chuỗik=1d) A là đầy đủ nếu và chỉ nếu spanA là trù mật trong X.e) A là đầy đủ nếu và chỉ nếu với mọi x ∈ X , ta có phương trình 9Parseval sau đây:∞| x, xk |2 = x 2 .k=1f) A là đầy đủ nếu và chỉ nếu với mọi x ∈ X có một khai triển Fourier∞x=x, xk xk ,k=1trong đó, sự hội tụ được hiểu theo chuẩn của X . Trong trường hợp này,phương trình Parseval là đúng:∞x, xkx, y =y, xk .k=11.3. TỐN TỬ TUYẾN TÍNH LIÊN TỤC VÀ TOÁN TỬ COMPACTĐịnh nghĩa 1.3.1. Cho X, Y là hai khơng gian tuyến tính định chuẩntrên trường R. Ánh xạ A : X → Y là liên tục tại x0 ∈ X nếu với mọi dãy(xn ) ⊂ X mà xn → x0 thì Axn → Ax0 . Ánh xạ A được gọi là liên tụctrên X nếu nó liên tục tại mọi điểm x ∈ X .Định lí 1.3.2. Cho X, Y là hai khơng gian tuyến tính định chuẩn và A làtốn tử tuyến tính từ X vào Y . Khi đó, các mệnh đề sau tương đương:a) A liên tục trên X .b) A liên tục tại điểm x0 ∈ X .c) A liên tục tại 0.d) Tồn tại một số M dương sao cho với mọi x ∈ X , ta có Ax ≤M x (nghĩa là A bị chặn).Định nghĩa 1.3.3. Cho A là một tốn tử tuyến tính liên tục từ khơnggian tuyến tính định chuẩn X vào Y . Theo Định lí 1.3.2 ln tồn tại sốM > 0 sao cho Ax ≤ M x với mọi x ∈ X , nên ta định nghĩa chuẩnA như sau:A = inf {M > 0 : ∀x ∈ X, Ax ≤ M x } . 10Định lí 1.3.4. Cho A là một tốn tử tuyến tính liên tục từ khơng giantuyến tính định chuẩn X vào Y . Khi đóAxA = sup= sup Ax = sup Ax .xx=0x ≤1x =1Định nghĩa 1.3.5. (Toán tử compact). Cho X, Y là hai khơng gianđịnh chuẩn. Tốn tử tuyến tính bị chặn K : X → Y được gọi là tốntử compact nếu nó biến mỗi tập bị chặn S thành tập compact tương đốiK(S).Tập M ⊂ X được gọi là tập compact tương đối nếu mỗi dãy bị chặn(yi ) ⊂ M đều có điểm tụ trong cl(M ), tức là bao đóng cl(M ) là compact.Định lí 1.3.6. (a) Nếu K1 và K2 là hai tốn tử compact đi từ X vào Y ,khi đó K1 + K2 và λK1 cũng là compact, ∀λ ∈ R.(b) Cho Kn : X → Y là một dãy của tốn tử compact giữa hai khơnggian Banach X và Y . Giả sử K : X → Y bị chặn và Kn hội tụ đến Ktheo chuẩn của toán tử. Tức là:Kn − K := supx=0Kn x − Kx→ 0 (n → ∞),xkhi đó, K cũng là compact.(c) Nếu L ∈ L(X, Y ) và K ∈ L(Y, Z) và L hoặc K là compact thì KLcũng là compact.(d) Giả sử An ∈ L(X, Y ) hội tụ từng điểm đến A ∈ L(X, Y ), tức làAn x → Ax, ∀x ∈ X . Nếu K : Z → X là compact thì An K − AK → 0,nghĩa là toán tử An K hội tụ đến AK trong chuẩn của tốn tử.Định lí 1.3.7. (a) Giả sử k ∈ L2 ((c, d) × (a, b)). Tốn tử K : L2 (a, b) →L2 (c, d) được định nghĩa như sau:b(Kx)(t) :=k(t, s)x(s)ds,t ∈ (c, d), x ∈ L2 (a, b)(1.1)a2là compact từ L (a, b) vào L2 (c, d).(b) Giả sử k liên tục trên [c, d] × [a, b]. Khi đó, K được xác định bởi(1.1) cũng là compact như một toán tử từ C[a, b] vào C[c, d]. 111.4. HÀM SỐĐịnh nghĩa 1.4.1. (Hàm coercive). Cho X là không gian định chuẩn.Hàm f : X → R được gọi là coercive nếu với mọi dãy {xn } ⊂ X màxn → +∞ thì f (xn ) → +∞.Định nghĩa 1.4.2. (Hàm liên tục Lipschitz). Cho X, Y là hai khônggian định chuẩn, ánh xạ f : X → Y . Ta lấy tập mở A ⊂ X . Khi đó, fđược gọi là liên tục Lipschitz trên tập con mở A nếu tồn tại một hằng sốL sao chof (x) − f (y) ≤ L x − y , ∀x, y ∈ A.L được gọi là hằng số Lipschitz.Nếu A = X , thì ta nói f liên tục lipschitz trên X.Định nghĩa 1.4.3. (Đạo hàm Fréchet). Cho X và Y là hai khônggian định chuẩn trên trường số thực R, U ⊂ X là tập mở, xˆ ∈ U vàT : X ⊃ U → Y là một ánh xạ.a) T được gọi là liên tục tại xˆ nếu ∀ε > 0, ∃δ > 0 thì T (x) − T (ˆx) ≤ε, ∀x ∈ U với x − xˆ ≤ δ.b) T được gọi là khả vi Fréchet tại xˆ ∈ U nếu tồn tại một toán tử tuyếntính bị chặn A : X → Y phụ thuộc vào xˆ sao cho:1T (ˆx + h) − T (ˆx) − Ah = 0.limh→0 hTa đặt T (ˆx) := A. Đặc biệt T (ˆx) ∈ L(X, Y ).c) Ánh xạ T được gọi là khả vi Fréchet liên tục tại xˆ ∈ U nếu T là khảvi Fréchet trong lân cận V của xˆ và ánh xạ T : V → L (X, Y ) là liên tụctại xˆ.Tính liên tục và tính khả vi của ánh xạ tùy thuộc vào các chuẩn trongX và Y , điều này trái ngược với trường hợp hữu hạn chiều. Nếu T khả vitại xˆ thì ánh xạ tuyến tính bị chặn A trong (b) ở Định nghĩa 1.4.3 là duynhất. Vì thế, T (ˆx) := A hoàn toàn xác định. Nếu T khả vi tại x thì Tcũng liên tục tại x. Trong trường hợp hữu hạn chiều X = Rn và Y = Rmánh xạ tuyến tính bị chặn T (ˆx) chính là ma trận Jacobian. 12Ví dụ 1.4.4. Cho f : [c, d] × [a, b] × R → R liên tục và khả vi liên tục vớiba đối số. Giả sử ánh xạ T : C[a, b] → C[c, d] được xác định như sau:bf (t, s, x (s)) ds, t ∈ [c, d] , x ∈ C [a, b] .T (x) (t) :=aKhi đó, T là liên tục khả vi Fréchet với đạo hàmb∂f (t, s, x (s)) ds, t ∈ [c, d] , x ∈ C [a, b] .∂x(T (x) z) (t) :=aĐịnh lí 1.4.5. a) Cho T, S : X ⊃ U → Y là khả vi Fréchet tại x ∈ U .Khi đó T + S và λT cũng là khả vi Fréchet với mọi λ ∈ R và(T + S) (x) = T (x) + S (x), (λT ) (x) = λT (x).b) Cho T : X ⊃ U → V ⊂ Y và S : Y ⊃ V → Z là khả vi Fréchet tạix ∈ U và T (x) ∈ V . Khi đó, ST cũng là khả vi Fréchet tại x và(ST ) (x) = S (T (x)) T (x) ∈ L(X, Z) (vì S (T (x)) ∈ L(Y, Z), T (x) ∈L(X, Y )).c) Trường hợp đặc biệt: Nếu T : X → Y là khả vi Fréchet tại xˆ∈Xthì ψ : R → Y được định nghĩa bởi:ψ(t) := T (tˆx)cũng khả vi Fréchet tại mọi điểm t ∈ R và ψ (t) = T (tˆx)ˆx∈Y.Chú ý rằng ban đầu ψ (t) ∈ L(R, Y ). Trong trường hợp này, ánh xạtuyến tính ψ (t) : R → Y với ψ (t) ∈ Y.Định lí 1.4.6. Cho T : X × Z → Y là liên tục khả vi Fréchet với đạo∂∂hàm riêng ∂xT (x, z) ∈ L (X, Y ) và ∂zT (x, z) ∈ L (Z, Y ). Hơn nữa, cho∂T (ˆx, zˆ) = 0 và ∂xT (ˆx, zˆ) : Z → Y là đẳng cự. Khi đó, tồn tại một lâncận U của xˆ và một hàm khả vi Fréchet ψ : U → Z sao cho ψ (ˆx) = zˆ vàT (x, ψ (x)) = 0, ∀x ∈ U . Đạo hàm riêng ψ ∈ L (X, Z) cho bởi−1∂∂ψ =−T (x, ψ (x))T (x, ψ (x)) , x ∈ U.∂z∂xTrường hợp đặc biệt sau là rất quan trọng 13ˆ = 0 vàCho Z = Y = R, T : X × R → R và T xˆ, λˆ =0xˆ, λˆ vàKhi đó, tồn tại lân cận U của xˆ và hàm khả vi Fréchet ψ (ˆx) = λT (x, ψ (x)) = 0, ∀x ∈ U và∂1ψ (x) = − ∂T (x, ψ (x)) ∈ L (X, R) = X , x ∈ U.∂xT(x,ψ(x))∂λVới X là không gian đối ngẫu của X .∂∂z TCho X là một không gian Hilbert. M là một tập con lồi khác rỗng củaX và phiếm hàm nhận giá trị thực mở rộng trên M :f : M → R := [−∞, ∞] .Các tập dưới đây:domf := {x ∈ M |f (x) < ∞} ; epi f := {(x, γ) ∈ M × R|f (x) ≤ γ}lần lượt được gọi là miền hữu hiệu và trên đồ thị của f . Ngoài ra, với mỗiα ∈ R, ta gọi tập mức dưới của hàm f là:C (f ; α) := {x ∈ M |f (x) ≤ α} = {x ∈ M | (x, α) ∈ epi f } .Định nghĩa 1.4.7. (Hàm lồi). Cho X là không gian Hilbert, M ⊂ X làtập con lồi khác rỗng. Khi đó, phiếm hàm tuyến tính f : M → R được gọilà hàm lồi nếu epi f là tập lồi.Hàm f được gọi là hàm lõm nếu −f là hàm lồi.Nhận xét 1.4.8. 1. Nếu f lồi thì domf lồi.2. Nếu f lồi thì C (f ; α) lồi với mọi α ∈ R.3. Nếu f : X → R là hàm lồi và f (x0 ) > −∞ với x0 ∈ int dom f thìf (x) > −∞ ∀x ∈ X .Mệnh đề 1.4.9. f : X → (−∞, +∞] . Lúc đó, f lồi nếu và chỉ nếuf (λx + (1 − λ) y) ≤ λf (x) + (1 − λ) f (y) , ∀x, y ∈ X, λ ∈ (0, 1) .Ví dụ 1.4.10. Cho hàm f (x) = ax + α, a ∈ X , α ∈ R.∀x, y ∈ X , ∀λ ∈ (0, 1) ta có:f [λx + (1 − λ)y] = a[λx + (1 − λ)y] + α= λax + (1 − λ)ay + α 14= λax + λα + (1 − λ)ay + (1 − λ)α= λ(ax + α) + (1 − λ)(ay + α)= λf (x) + (1 − λ)f (y)Vậy f là hàm lồi trên X .∀x, y ∈ X , ∀λ ∈ (0, 1) ta lại có:−f [λx + (1 − λ)y] = −a[λx + (1 − λ)y] − α= −λax − (1 − λ)ay − α= −λax − λα − (1 − λ)ay − (1 − λ)α= −λ(ax + α) − (1 − λ)(ay + α)= −λf (x) − (1 − λ)f (y)Vậy −f là hàm lồi trên X .Suy ra f là một hàm lõm trên X .Định nghĩa 1.4.11. (Hàm nửa liên tục dưới). Một hàm f : X → Rđược gọi là nửa liên tục dưới tại x0 nếulim inf f (x) ≥ f (x0 ) .x→x0f được gọi là nửa liên tục dưới yếu nếu nó nửa liên tục dưới tại mọi x ∈ X.1.5. DƯỚI VI PHÂNĐịnh nghĩa 1.5.1. Cho X là không gian Hilbert, X ∗ là không gian liênhợp của X . Giả sử f là một hàm lồi, chính thường trên khơng gian HilbertX và x0 ∈ dom f . Một phiếm hàm x∗ ∈ X ∗ được gọi là dưới Gradient củaf tại x0 nếuf (x) ≥ f (x0 ) + x∗ , x − x0 , ∀x ∈ X.Về mặt hình học, điều đó có nghĩa rằng hàm affineϕ (x) := f (x0 ) + x∗ , x − x0 , x ∈ Xcó đồ thị là một siêu phẳng tựa của epif tại điểm (x0 , f (x0 )). Tập hợptất cả các dưới Gradient của f tại x0 được gọi là dưới vi phân của f tại 15điểm đó và được kí hiệu là ∂f (x0 ). Vậy∂f (x0 ) = {x∗ ∈ X ∗ |f (x) − f (x0 ) ≥ x∗ , x − x0 , ∀x ∈ X} .Nếu ∂f (x0 ) là tập khác rỗng ta nói f khả dưới vi phân tại x0 . Để thuậntiện ta cũng quy ước ∂f (x0 ) = ∅ nếu x0 ∈/ dom f .1.6. HÀM PHẠT CĨ TÍNH CHẤT THƯACho H là khơng gian Hilbert với chuẩn . , {ϕk }k∈Λ là cơ sở trựcchuẩn của H. Khi đó, hàm phạt có tính chất thưa Φ : H → R ∪ {∞} đượcđịnh nghĩa bởi:|uk |,Φ (u) :=(1.2)k∈Λtrong đó, uk := u, ϕk .Bổ đề 1.6.1. Hàm phạt có tính chất thưa Φ định nghĩa bởi (1.2) có cáctính chất như sau:1) Φ khơng âm, lồi và nửa liên tục dưới yếu.2) Tồn tại một hằng số C , sao cho ∀u ∈ HΦ (u) ≥ C 1/2 u .Từ đó, suy ra Φ là coercive, Φ (u) → ∞ khi u → ∞.3) Nếu {un }n∈N ⊂ H hội tụ yếu đến u ∈ H và Φ (un ) hội tụ đến Φ(u).Khi đó, Φ (un − u) hội tụ đến 0.Chứng minh. 1) Hiển nhiên Φ không âm, lồi và nửa liên tục dưới yếu vìvới mỗi k ∈ Λ thì |uk | là không âm, lồi và hàm liên tục dưới yếu.|uk | =2) Ta có Φ (u) =k∈Λ⇒ Φ (u) ≥| u, ϕk |k∈Λ| u, ϕk | ≥k∈Λ| u, ϕk |2121≥ C2 u .k∈ΛVậy Φ (u) ≥ C 1/2 u .3) Giả sử Φ (un ) → Φ (u).Ta có lim sup Φ (un − u)= lim sup [2 (Φ (un ) + Φ (u)) − 2 (Φ (un ) + Φ (u)) + Φ (un − u)] 16[2 | ϕk , un | + 2 | ϕk , u | − | ϕk , un − u |]= 4Φ (u) − lim infk∈Λ[2 | ϕk , un | + 2 | ϕk , u | − | ϕk , un − u |]Ta có − lim infk∈Λlim inf [2 | ϕk , un | + 2 | ϕk , u | − | ϕk , un − u |].≤−k∈ΛnTa lại có {u }n∈N hội tụ yếu đến u ∈ H nên ϕk , un → ϕk , u ∀k ∈ Λlim inf [2 | ϕk , un | + 2 | ϕk , u | − | ϕk , un − u |]⇒−k∈Λ= −4| ϕk , u |k∈Λn⇒ lim sup Φ (u − u) ≤ 4Φ (u) − 4| ϕk , u | = 4Φ (u) − 4Φ (u) = 0k∈ΛVậy lim sup Φ (un − u) = 0.1.7. TOÁN TỬ CO RÚT MỀMCho hàm co rút S : R → RSτ (x) = sgn (x) max (|x| − τ, 0) .(1.3)Định nghĩa 1.7.1. Toán tử co rút mềm S : H → H được xác định bởi:Sτ ( u, ϕk ) ϕk ,Sτ (u) =(1.4)k∈Λhàm Sτ được cho ở (1.3) và {ϕk }k∈Λ là cơ sở trực chuẩn của H.Bổ đề 1.7.2. Toán tử co rút mềm được định nghĩa ở (1.4) là không dãn,tức làSτ (u) − Sτ (v) ≤ u − v , ∀u, v ∈ H.Chứng minh của bổ đề này có thể xem trong [9, Bổ đề 2.2].Bổ đề 1.7.3. Cho {un } , {v n } , {hn } là các dãy trong H và {β n } là dãythực dương sao choun = Sβ n (v n − β n hn ) .Nếu un , v n hội tụ yếu đến u∗ , hn hội tụ yếu đến h∗ và β n > 0, lim β n =n→∞∗β > 0. Khi đóu∗ = Sβ ∗ (u∗ − β ∗ h∗ ) . 17Chứng minh. Từ giả thiết, ta cóun = Sβ n (v n − β n hn ) ,hoặcunk = sgn (vkn − β n hnk ) max (|vkn − β n hnk | − β n , 0) , ∀k ∈ Λ.Ta đặt(1.5)Γ1 := {k ∈ Λ : |u∗k − β ∗ h∗k | > β ∗ }Γ2 := {k ∈ Λ : |u∗k − β ∗ h∗k | < β ∗ }Γ3 := {k ∈ Λ : |u∗k − β ∗ h∗k | = β ∗ }Vì vkn − β n hnk → u∗k − β ∗ h∗k và |vkn − β n hnk | − β n → |u∗k − β ∗ h∗k | − β ∗ khin → ∞ (k cố định), ta có• Nếu k ∈ Γ1 thì vkn −β n hnk , u∗k −β ∗ h∗k cùng dấu và |vkn − β n hnk |−β n > 0khi n đủ lớn và do đó hai vế của (1.5) có giới hạn vàu∗k = sgn (u∗k − β ∗ h∗k ) max (|u∗k − β ∗ h∗k | − β ∗ , 0) , ∀k ∈ Γ1 ,hoặcu∗k = Sβ ∗ (u∗k − β ∗ h∗k ) , ∀k ∈ Γ1 .• Nếu k ∈ Γ2 thì |vkn − β n hnk | − β n < 0 khi n đủ lớn. Như vậy, unk = 0 khin đủ lớn. Khi đó, ta có u∗k = 0 và ta có kết luậnu∗k = Sβ ∗ (u∗k − β ∗ h∗k ) , ∀k ∈ Γ2 .• Nếu k ∈ Γ3 thì vkn − β n hnk và u∗k − β ∗ h∗k cùng dấu và khác 0 khi n đủunku∗klớn. Như vậy, sgn(vn −β→n∗nh )sgn(uk −β ∗ h∗k ) khi n → ∞. Vì thế, ở công thứckk(1.5) ta kết luận rằng max (|vkn − β n hnk | − β n , 0) cũng hội tụ và bằng 0 vì|vkn − β n hnk | − β n → 0. Khi đó, ta suy ra rằng u∗k = 0 vàu∗k = Sβ ∗ (u∗k − β ∗ kk∗ ) , ∀k ∈ Γ3 .Cuối cùng, ta cóu∗k = Sβ ∗ (u∗k − β ∗ h∗k ) , ∀k ∈ Γ1 ∪ Γ2 ∪ Γ3 = Λ.Điều này, tương đương với u∗ = Sβ ∗ (u∗ − β ∗ h∗ ).Bổ đề 1.7.4. Cho {hn } ⊂ H bị chặn đều và {dn } ⊂ H hội tụ yếu đến 0.Nếu β n ∈ β, β và lim Sβ n (hn + dn ) − Sβ n (hn ) − dn = 0 thì dn →n→∞0 khi n → ∞.Chứng minh. Vì {hn } bị chặn đều, ta đặt tập hữu hạn Γ0 ⊂ Λ sao cho

Tài liệu liên quan

• Ứng dụng luật kết hợp và thuật toán di truyền vào bài toán tối ưu sắp xếp container hàng hóa trên tàu
  • 26
  • 871
  • 1
• Điều kiện tối ưu cấp một và cấp hai cho bài toán tối ưu trong không gian vectơ tôpô
  • 23
  • 623
  • 0
• Gradient suy rộng và ứng dụng vào bài toán tối ưu không trơn
  • 51
  • 1
  • 0
• Phương pháp xấp xỉ trơn cho bài toán tối ưu không trơn
  • 50
  • 548
  • 0
• Tối ưu số cho bài toán tối ưu một mục tiêu
  • 85
  • 724
  • 1
• Báo cáo nghiên cứu khoa học: "MỘT THUẬT TOÁN ĐỊNH TUYẾN TỐI ƯU TÀI NGUYÊN TRONG MẠNG IP/WDM VÀ ỨNG DỤNG TRÊN TÔPÔ MẮT LƯỚI" pot
  • 8
  • 492
  • 1
• Tóm tắt báo cáo nghiên cứu khoa học " SỰ TỒN TẠI, ỔN ĐỊNH NGHIỆM VÀ THUẬT TOÁN GIẢI BẤT ĐẲNG THỨC BIẾN PHÂN VÀ BÀI TOÁN TỐI ƯU KHÔNG TRƠN " doc
  • 5
  • 449
  • 3
• Luận văn về Điều kiện cần tối ưu cấp 2 cho bài toán tối ưu có các ràng buộc đẳng thức và bất đẳng thức
  • 47
  • 768
  • 3
• sự tách nón cho bài toán tối ưu vector
  • 43
  • 524
  • 0
• Các điều kiện tối ưu theo dãy cho bài toán tối ưu trơn với các ràng buộc phiếm hàm
  • 63
  • 377
  • 0

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(512.75 KB - 55 trang) - Giải thuật cho bài toán tối ưu không trơn trong chỉnh hóa thưa và ứng dụng Tải bản đầy đủ ngay ×