Bài Toán Tối ưu Không Trơn Trong Bài Toán Ngược Và ứng Dụng - 123doc

Lịch sử vấn đề và lý do chọn đề tài Hiện nay, khi mô hình hóa các vấn đề thực tiễn đặt ra trong nhiều lĩnhvực khoa học kỹ thuật thường dẫn đến nghiên cứu các bài toán tối ưukhông trơn tứ

Trang 1

TRƯỜNG ĐẠI HỌC SƯ PHẠM

——————————–

PHẠM NGỌC THÁI

BÀI TOÁN TỐI ƯU KHÔNG TRƠN TRONG

BÀI TOÁN NGƯỢC VÀ ỨNG DỤNG

LUẬN VĂN THẠC SĨ KHOA HỌC

Đà Nẵng - 2017

Trang 2

TRƯỜNG ĐẠI HỌC SƯ PHẠM

——————————–

PHẠM NGỌC THÁI

BÀI TOÁN TỐI ƯU KHÔNG TRƠN TRONG

BÀI TOÁN NGƯỢC VÀ ỨNG DỤNG

Chuyên ngành: Toán Giải tích

Mã số: 60.46.01.02

LUẬN VĂN THẠC SĨ KHOA HỌC

Người hướng dẫn khoa học:

TS Lê Hoàng Trí

Đà Nẵng - 2017

Trang 3

Tôi 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 được ai công

bố trong bất kỳ công trình nào khác

Tác giả

PHẠM NGỌC THÁI

Trang 4

Lời đầu tiên, tác giả xin gửi lời cảm ơn chân thành tới thầy giáo hướngdẫn, TS Lê Hoàng Trí, người đã tận tình hướng dẫn tác giả trong suốtthời gian qua Với sự giúp đỡ của thầy, tác giả mới có thể hoàn thành đượcluận văn này.

Tác giả cũng xin gửi lời cảm ơn đến TS Phạm Quý Mười về những traođổi, thảo luận và các góp ý của thầy trong suốt quá trình làm luận vănnày

Tác giả trân trọng gửi lời cảm ơn đến tất cả quý thầy lãnh đạo KhoaToán - Trường Đại học Sư phạm - Đại học Đà Nẵng cùng quý thầy cô giáo

đã tận tình dạy bảo tác giả trong suốt thời gian học tập của khóa học.Đồng thời, tác giả cũng xin gửi lời cảm ơn đến các anh chị học viên lớpGiải tích K31 đã nhiệt tình giúp đỡ tác giả trong quá trình học tập Tácgiả muốn gửi lời cảm ơn đến người bạn cùng lớp, Nguyễn Thị Liêu Noa,

đã hỗ trợ và giúp đỡ tác giả, phần nghiệm số trong luận văn này

Tác giả

PHẠM NGỌC THÁI

Trang 5

MỞ ĐẦU 1

CHƯƠNG 1.KIẾN THỨC CƠ SỞ 4

1.1 KHÔNG GIAN HILBERT 4

1.2 HỆ TRỰC CHUẨN 8

1.3 TOÁN TỬ TUYẾN TÍNH BỊ CHẶN VÀ TOÁN TỬ COMPACT 9

1.4 HÀM SỐ 13

1.5 DƯỚI VI PHÂN 15

CHƯƠNG 2.BÀI TOÁN TỐI ƯU KHÔNG TRƠN VÀ CÁC GIẢI THUẬT 16

2.1 BÀI TOÁN 16

2.2 ĐIỀU KIỆN CÓ NGHIỆM VÀ ĐIỀU KIỆN CẦN CỦA NGHIỆM 16

2.3 GIẢI THUẬT GIẢM GRADIENT 19

2.3.1 Tốc độ hội tụ 20

2.3.2 Tiêu chuẩn lựa chọn stepsizes 25

2.3.3 Giải thuật giảm Gradient 26

2.4 GIẢI THUẬT CẢI TIẾN NESTEROV 27

CHƯƠNG 3.ỨNG DỤNG VÀ VÍ DỤ 32

3.1 BÀI TOÁN 32

3.2 ÁP DỤNG CHỈNH HÓA THƯA 32

3.3 VÍ DỤ ÁP DỤNG 33

Trang 6

3.3.1 Bài toán 33

3.3.2 Rời rạc bài toán 33

3.3.3 Áp dụng chỉnh hóa thưa 34

3.3.4 Minh họa nghiệm số và sự hội tụ 35

KẾT LUẬN VÀ KIẾN NGHỊ 39

TÀI LIỆU THAM KHẢO 40

Trang 7

R : Trường các số thực

hx, yi : Tích vô hướng của x và y

kKk : Chuẩn của toán tử K

kxk : Chuẩn của x

(X, h.i) : Không gian tiền Hilbert của X

Rn : Không gian tiền Hilbert n chiều

(X, k.kX) : Không gian định chuẩn của X

H : Không gian Hilbert

kxkL2 : Chuẩn Ơclit

C [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 toán tử tuyến tính bị chặn từ X vào Y

A∗ : Toán tử liên hợp của A

Trang 8

MỞ ĐẦU

1 Lịch sử vấn đề và lý do chọn đề tài

Hiện nay, khi mô hình hóa các vấn đề thực tiễn đặt ra trong nhiều lĩnhvực khoa học kỹ thuật thường dẫn đến nghiên cứu các bài toán tối ưukhông trơn (tức là hàm mục tiêu không có đạo hàm) Điều này đã thúcđẩy việc nghiên cứu các bài toán tối ưu không trơn, một lĩnh vực đượcquan tâm rất lớn và có những bước phát triển rất mạnh trong vài thậpniên gần đây

Trong lĩnh vực bài toán ngược, phương pháp chỉnh hóa kiểu Tikhonovthường dẫn đến việc nghiên cứu bài toán tối ưu dạng:

min

u∈H Θ (u) := F (u) + Φ (u) (1)

Trong đó, F là hàm khả vi liên tục nhưng Φ là hàm nửa liên tục dướinhưng không khả vi

Đây là dạng bài toán đã được nghiên cứu bởi nhóm tác giả Phạm QuýMười, Đinh Nho Hào, Peter Maass và Michael Pidcock đưa ra trong bàibáo [10] Một vài trường hợp cụ thể của bài toán cũng được nghiên cứutrong luận án tiến sĩ của Phạm Quý Mười [11]

Về giải thuật để giải Bài toán (1), phương pháp được nghiên cứu nhiềunhất là giải thuật giảm Gradient và các giải thuật cải tiến của nó Bêncạnh đó, Newtơn nửa trơn và phương pháp tựa Newtơn nửa trơn cũngđược sử dụng để tính toán đối với bài toán ngược

Với mong muốn nghiên cứu bài toán trên cũng như một số giải thuậttìm nghiệm xấp xỉ của bài toán, tôi chọn đề tài “Bài toán tối ưu khôngtrơn trong bài toán ngược và ứng dụng” Với đề tài này, tôi dự định nghiêncứu sự tồn tại nghiệm của bài toán, điều kiện cần cho nghiệm của bài toán.Đặc biệt, đề tài tập trung vào nghiên cứu và áp dụng hai giải thuật cơbản: Giải thuật giảm Gradient và giải thuật cải tiến của Nesterov

Trang 9

2 Mục đích nghiên cứu

Mục tiêu của đề tài là nghiên cứu, tìm hiểu Bài toán tối ưu (1) và cácthuật toán cho bài toán tối ưu này Ứng dụng các giải thuật cho một sốbài toán cụ thể

3 Đối tượng và phạm vi nghiên cứu

Bài toán tối ưu không trơn min

u∈H Θ (u) := F (u) + Φ (u).Các giải thuật cho các Bài toán tối ưu không trơn (1)

+ Giải thuật giảm Gradient,

+ Giải thuật cải tiến Nesterov

4 Phương pháp nghiên cứu

Với đề tài: “Bài toán tối ưu không trơn trong bài toán ngược vàứng dụng” tôi đã sử dụng các phương pháp nghiên cứu sau:

- Thu thập, tổng hợp các tài liệu liên quan đến nội dung đề tài luậnvăn

- Phân tích, nghiên cứu các tài liệu thu thập được để thực hiện đề tài

- Tham gia các buổi seminar của thầy hướng dẫn để trao đổi các kếtquả đang nghiên cứu

5 Ý nghĩa khoa học và thực tiễn

Nội dung chính của đề tài là nghiên cứu cở sở lý thuyết và các giảithuật để giải các bài toán tối ưu không trơn trong bài toán ngược Luậnvăn có thể được dùng làm tài liệu tham khảo cho sinh viên, học viên caohọc và những ai có nhu cầu tìm hiểu về bài toán tối ưu không trơn trongbài toán ngược

Trang 10

6 Cấu trúc luận văn

Luận văn “Bài toán tối ưu không trơn trong bài toán ngược vàứng dụng” được trình bày theo cấu trúc như sau:

Mở đầu

Chương I: Kiến thức cơ sở

Chúng tôi nhắc lại một số khái niệm, định nghĩa, định lí cơ bản của Giảitích hàm Các tính chất, định lí được nêu ở đây chúng tôi không chứngminh Mặt khác, luận văn cũng nhắc lại một số tính chất của hàm lồi, hàmcoercive Các tính chất này được dùng trong chương tiếp theo

Chương II: Bài toán tối ưu không trơn và các giải thuật

Chương này sẽ giới thiệu về bài toán tối ưu không trơn xuất hiện trongchỉnh hóa bài toán ngược Trước hết, luận văn nêu giả thiết cho bài toán,phát biểu và chứng minh các bổ đề, định lí về điều kiện có nghiệm và điềukiện cần của nghiệm Nội dung chính của chương này là giới thiệu giảithuật giảm Gradient và giải thuật cải tiến của Nesterov cũng như xem xéttốc độ hội tụ của hai giải thuật

Chương III: Ứng dụng và ví dụ

Áp dụng hai giải thuật giảm Gradient và giải thuật cải tiến của Nesterov

đã nghiên cứu ở trên để tìm nghiệm xấp xỉ của phương trình K (x) = y

Áp dụng chỉnh hóa thưa để tìm nghiệm xấp xỉ của phương trình vi phâncấp một và ví dụ minh họa

Trang 11

KIẾ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 nghĩa,định lí cơ bản của Giải tích hàm Các tính chất, định lí được nêu ở đâychúng tôi không chứng minh Về chứng minh của chúng có thể tham khảotrong các tài liệu [1, 2]

Mặt khác, luận văn cũng nhắc lại một số tính chất của hàm lồi, hàmcoercive Các tính chất này được dùng trong chương tiếp theo

1.1 KHÔNG GIAN HILBERT

Định nghĩa 1.1.1 (Tích vô hướng, không gian tiền Hilbert)

Cho X là một không gian vectơ trên trường số thực R Tích vô hướngtrong X là một ánh xạ

Một không gian vectơ X trên R cùng với tích vô hướng h., i được gọi

là một không gian tiền Hilbert trên R Kí hiệu: (X, h, ,i) hoặc được viếtngắn gọn là X nếu tích vô hướng đã được xác định rõ

Nhận xét 1.1.2 Từ Định nghĩa 1.1.1 ta dễ dàng suy ra được các tínhchất sau:

(v) hx, y + y0i = hx, yi + hx, y0i ∀x, y, y0 ∈ X,

(vi) hx, λyi = λ hx, yi ∀x, y ∈ X, ∀λ ∈ R.

Trang 12

Định lí 1.1.4 Cho (X, h.i) là một không gian tiền Hilbert Ánh xạ k.k :

X →R được định nghĩa như sau:

Trang 13

là một tích vô hướng trên `2.

(c) Không gian C [a, b] của các hàm thực liên tục trên [a, b] là mộtkhông gian tiền Hilbert trên R với tích vô hướng

kxkL2 =

q

hx, xiL2 =

vuuut

Mỗi không gian định chuẩn là một không gian tôpô sinh bởi chuẩn đó,tức là chúng có thể định nghĩa các tập mở, đóng và compact; các dãy hộitụ; các hàm liên tục Hình cầu tâm x ∈ X và bán kính r > 0xác định bởi:

K (x, r) = {y ∈ X : ky − xk < r}, K [x, y] = {y ∈ X : ky − xk ≤ r}.Định nghĩa 1.1.6 Cho X là một không gian định chuẩn trên trường sốthực R

(a) Một tập con M ⊂ X được gọi là bị chặn nếu tồn tại r > 0 thì

M ⊂ K (x, r) Tập M ⊂ X được gọi là tập mở nếu với mọi x ∈ M tồntại ε > 0 sao cho K (x, ε) ⊂ M Tập M ⊂ X được gọi là tập đóng nếuphần bù 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

kxkk ≤ c với mọi k Dãy (xk)k ⊂ X được gọi là hội tụ nếu tồn tại x ∈ M

sao cho kx − xkk hội tụ đến 0 trong R Khi đó, kí hiệu lim

k→∞xk = x hoặc

Trang 14

xk → x khi k → ∞ Dãy (xk)k ⊂ X được gọi là dãy Cauchy nếu với mỗi

ε > 0 tồn tại N ∈ N sao cho kxm − xkk < ε, với mọi 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ểm

tụ trong M

Ví dụ 1.1.7

Cho X = C [0, 1] trên R và xk(t) = tk, t ∈ [0, 1] , k ∈ N Dãy (xk)

hội tụ đến 0 với chuẩn Euclidean k.kL2 được nêu trong (1.3) Với chuẩnsupremum k.k∞ của (1.4) Tuy nhiên, dãy này không hội tụ đến 0

Người ta chứng minh được rằng một tập M là đóng nếu và chỉ nếu giớihạn của mọi dãy (xk)k ⊂ M là một phần tử của M

tương ứng được gọi là phần trong và bao đóng của M

Tập M ⊂ X được gọi là trù mật trong X nếu cl (M ) = X

Định lí 1.1.8 Cho X là một không gian hữu hạn chiều với chuẩn k.k1

và k.k2 Khi đó, cả hai chuẩn là tương đương, tức là tồn tại hằng số c2 ≥

(b) Nếu M 6= X là một không gian con tuyến tính thì int (M ) = φ và

cl (M ) cũng là một không gian con tuyến tính

Trang 15

(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ạnchiều, điều ngược lại cũng đúng theo (Định lí Bolzano - Weierstrass): Trongmột 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.10 (Không gian Banach, không gian Hilbert)Một không gian định chuẩn X trên R được gọi là đầy đủ hoặc khônggian Banach nếu mọi dãy Cauchy đều hội tụ trong X Một không giantiền Hilbert đầy đủ được gọi là một không gian Hilbert

1.2 HỆ TRỰC CHUẨN

Cho X là không gian Hilbert tách trên trường số thực R

Đị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à một hệ trực chuẩn nếu:

là 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

Trang 16

(b) Nếu A hữu hạn, tức là A = {xk : k = 1, 2, , n}, thì với mọi x ∈ X

tồn tại duy nhất hệ số αk ∈ R, k = 1, 2, , n, sao cho

hệ số αk được cho bởi αk = hx, xki với k = 1, , n

(c) ∀x ∈ X, bất đẳng thức Bessel như sau:

(e) A là đầy đủ nếu và chỉ nếu với mọi x ∈ X có một khai triển Fourier

Định nghĩa 1.3.2 (Sự bị chặn, chuẩn của A)

Cho X và Y là hai không gian định chuẩn và A : X → Y là một toán

tử tuyến tính Toán tử tuyến tính A được gọi là bị chặn nếu tồn tại c > 0

sao cho

kAxk ≤ c kxk, ∀x ∈ X

Trang 17

Định lí 1.3.3 Các khẳng định sau là tương đương:

(a) A bị chặn,

(b) A là liên tục khi x = 0, tức là xj → 0 kéo theo Axj → 0,

(c) A là liên tục tại mọi điểm x ∈ X

Không gian L (X, Y ) gồm tất cả ánh xạ tuyến tính bị chặn từ X vào

Y với chuẩn của toán tử là một không gian định chuẩn, tức là chuẩn củatoán tử thỏa mãn tính chất (i), (ii) và (iii) của Định nghĩa 1.1.3 Cho

B ∈ L (X, Y ) và A ∈ L (X, Y ), khi đó ta có:

AB ∈ L (X, Y ) và kABk ≤ kAk kBk.Định nghĩa 1.3.4 Cho A là một toá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 nghĩa 1.3.2 luôn tồn tại

số M > 0sao cho kAxk ≤ M kxk với mọi x ∈ X, nên ta định nghĩa chuẩn

A như sau:

kAk = inf {M > 0 : ∀x ∈ X, kAxk ≤ M kxk}

Định lí 1.3.5 Cho A là một toá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 đó

kAk = sup

x6=0

kAxkkxk = supkxk≤1kAxk = supkxk=1kAxk

Định lí 1.3.6 (a) Cho k ∈ L2((c, d) × (a, b)) Toán tử

Trang 18

Chúng ta có thể mở rộng định lí này đến toán tử tích phân với nhânsuy biến yếu Ta nói rằng nhânk được gọi là suy biến yếu trên[a, b] × [a, b]

nếu k được xác định và liên tục ∀t, s ∈ [a, b] , t 6= s, và tồn tại hằng số

c > 0 và α ∈ [0, 1) sao cho

|k (t, s)| ≤ c|t − s|−α, ∀t, s ∈ [a, b] , t 6= s.Định lí 1.3.7 Cho k là nhân suy biến yếu trên [a, b] Khi đó, toán tử tíchphân A xác định bởi (1.6) với [c, d] = [a, b], là đơn ánh và bị chặn như mộttoán tử trong L2(a, b) cũng như trong C [a, b]

Trường hợp đặc biệt Y = R, ta kí hiệu X0 := L (X,R) là không gianđối ngẫu của X

Định lí 1.3.8 (Riesz - Fischer) Cho X là một không gian Hilbert Vớimỗi x ∈ X, hàm số fx(y) := (y, x) , y ∈ X, xác định một ánh xạ tuyếntính bị chặn từ X vào R, tức là fx ∈ X0 Hơn nữa, cho mỗi f ∈ X0 tồntại một và chỉ một x ∈ X với f (y) = (y, x) , ∀y ∈ X và

kf k := sup

y6=0

|f (y)|

kyk = kxk.Định lí 1.3.9 (Toán tử liên hợp)

Cho A : X → Y là toán tử tuyến tính và bị chặn giữa hai khônggian Hilbert Khi đó, tồn tại một và chỉ một toán tử tuyến tính bị chặn

A∗ : X → Y với tính chất

(Ax, y) = (x, A∗y) , ∀x ∈ X, ∀y ∈ Y.Toán tử A∗ : Y → X được gọi là toán tử liên hợp của A Cho X = Y,toán tử A gọi là tự liên hợp nếu A∗ = A

Ví dụ 1.3.10 ChoX = L2(a, b) , Y = L2(c, d)vàk ∈ L2((c, d) × (a, b)).Toán tử liên hợp A∗ của toán tử tích phân

Trang 19

được cho bởi

Cho X, Y là hai không gian định chuẩn Toán tử K : X → Y đượcgọi là toán tử compact nếu nó biến mỗi tập bị chặn S thành tập compacttương đối K (S)

Chúng ta nói rằng một tập hợp M ⊂ Y được gọi là compact tương đốinếu mỗi dãy bị chặn (yj) ⊂ M có một điểm tụ trong cl (M ), tức là baođóng cl (M ) là compact Tập hợp tất cả các toán tử compact từ X vào Y

là một không gian con đóng của L (X, Y )

Định lí 1.3.12 (a) Nếu K1 và K2 là các toán tử compact thì K1+ K2 và

λK1 với mỗi λ ∈R cũng là toán tử compact.

(b) Cho Kn : X → Y là một dãy của toán tử compact từ không gianBanach X vào không gian Banach Y và K : X → Y bị chặn Giả sử rằng

Kn hội tụ đến K theo chuẩn toán tử, tức là

kKn− Kk := sup

x6=0

kK n x−Kxk kxk → 0 (n → ∞).Khi đó K cũng là toán tử compact

(c) Nếu L ∈ L (X, Y ) và K ∈ L (Y, Z) và L hoặc K là toán tử compactthì KL cũng là toán tử compact

(d) Cho An ∈ L (X, Y ) hội tụ theo từng điểm đến một toán tử A ∈

L (X, Y ), tức là Anx → Ax, ∀x ∈ X Nếu K : X → Z là toán tử compactthì kAnK − AKk → 0, tức là toán tử AnK hội tụ đến AK theo chuẩntoán tử

Định lí 1.3.13 (a) Cho k ∈ L2((c, d) × (a, b)) Toán tử K : L2(a, b) →

Trang 20

là toán tử compact từ L2(a, b) vào L2(a, b).

(b) Cho k là liên tục trên [c, d]×[a, b] hoặc suy biến yếu trên[a, b]×[a, b]

(trong trường hợp này [c, d] = [a, b]) Khi đó K được xác định bởi (1.1)cũng là toán tử compact từ C [a, b] vào C [c, d]

1.4 HÀM SỐ

Định nghĩa 1.4.1 (Hàm liên tục Lipschitz)

Cho (X, k.kX) và (Y, k.kY) là hai không gian định chuẩn Một hàm

f : X → Y được gọi là liên tục Lipschitz nếu tồn tại một số thực L ≥ 0

sao cho ∀x1, x2 ∈ X

kf (x1) − f (x2)k ≤ L kx1 − x2k

L được gọi là hằng số Lipschitz

Định nghĩa 1.4.2 (Hàm coercive)

Cho X là không gian định chuẩn Hàm số f : X → R được gọi là

coercive nếu với mọi dãy {xn} ⊂ X và kxnk → +∞ thì f (xn) → +∞

Định nghĩa 1.4.3 (Đạo hàm Fréchet)

Cho X vàY là hai không gian định chuẩn trên trường số thực R,U ⊂ X

Ta viết T0(bx) := A Đặc biệt, T0(bx) ∈ L (X, Y )

(c) Ánh xạ T được gọi là khả vi liên tục Fréchet tại x ∈ Ub nếu T khả

vi Fréchet trong lân cận V của xb và ánh xạ T0 : V → L (X, Y ) là liên tụctrên xb

Trang 21

Tính liên tục và tính khả vi của ánh xạ phụ thuộc vào chuẩn trên X

và Y, điều này trái ngược trong trường hợp hữu hạn chiều Nếu T khả vitại xb thì ánh xạ tuyến tính bị chặn A trong (b) ở Định nghĩa 1.5.3 là duynhất Nếu T khả vi tại x khi đó T cũng liên tục tại x Trong trường hợphữu hạn chiều X = Rn và Y = Rm ánh xạ tuyến tính bị chặn T0(x)b chính

là ma trận Jacobian

Định lí 1.4.4 (a) Cho T, S : X ⊃ U → Y khả vi Fréchet tại x ∈ X Khi

đó, T + S và λT cũng khả vi Fréchét với mọi λ ∈K và

(T + S)0(x) = T0(x) + S0(x), (λT )0(x) = λT0(x)

(b) Cho T : X ⊃ U → V ⊂ Y và S : Y ⊃ V → Z khả vi Fréchet tại

x ∈ U và T (x) ∈ V tương ứng Khi đó, ST cũng khả vi Fréchet trên x và

(ST )0(x) = S0(T (x)) T0(x) ∈ L (X, Y )

Do S0(T (x)) ∈ L (Y, Z) và T0(x) ∈ L (X, Y )

(c) Nếu T : X → Y là khả vi Fréchet tại x ∈ Xb thì hàm Ψ : K → Y

xác định bởi Ψ (t) := T (tbx), t ∈ K, khả vi tại mọi điểm t ∈ K và Ψ0(t) =

T0(tx)b bx ∈ Y Chú ý rằng đầu tiên Ψ0(t) ∈ L (K, Y ) Trong trường hợpnày, ánh xạ tuyến tính Ψ0(t) : K → Y với Ψ0(t) ∈ Y

Cho H là một không gian Hilbert M là một tập con lồi khác rỗng của

H 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ớimỗ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 }

Trang 22

Hàm f được gọi là chính thường nếu domf 6= φ và f (x) > −∞ vớimọi x ∈ M.

Định nghĩa 1.4.5 (Hàm lồi)

Cho H là một không gian Hilbert Hàm f : M → R được gọi là hàm

lồi trên M nếu epi f là tập lồi và được gọi là hàm lõm nếu −f là hàm lồi.Nhận xét 1.4.6 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 : H → R là hàm lồi và f (x0) > −∞ với x0 ∈ int dom f thì

f (x) > −∞ ∀x ∈ H

Mệnh đề 1.4.7 f : H → (−∞, +∞] Lúc đó f lồi nếu và chỉ nếu

f (λx + (1 − λ) y) ≤ λf (x) + (1 − λ) f (y) , ∀x, y ∈ H, λ ∈ (0, 1)

Định nghĩa 1.4.8 (Hàm nửa liên tục dưới)

Một hàm f : H → R được gọi là nửa liên tục dưới tại x0 nếu

Trang 23

BÀI TOÁN TỐI ƯU KHÔNG TRƠN VÀ CÁC GIẢI THUẬT

Chương này sẽ giới thiệu về bài toán tối ưu không trơn xuất hiện trongchỉnh hóa bài toán ngược Trước hết, luận văn nêu giả thiết cho bài toán,phát biểu và chứng minh các bổ đề, định lí về điều kiện có nghiệm và điềukiện cần của nghiệm Nội dung chính của chương này là giới thiệu giảithuật giảm Gradient và giải thuật cải tiến của Nesterov cũng như xem xéttốc độ hội tụ của hai giải thuật

2.1 BÀI TOÁN

Chúng ta xét bài toán tối ưu không trơn dạng

min

u∈H Θ (u) (2.1)trong đó Θ (u) := F (u) + Φ (u)

Ở đây H là một không gian Hilbert, F : H → R là một hàm trơn,

nhưng không nhất thiết phải lồi, Φ : H → R là một hàm lồi nhưng có thể

không trơn Khi nghiên cứu Bài toán (2.1) chúng ta thường quan tâm đếnviệc tìm câu trả lời cho các câu hỏi cơ bản sau:

(1) Khi nào bài toán có nghiệm?

(2) Điều kiện cần và đủ của nghiệm?

Đầu tiên, chúng ta tập trung nghiên cứu các điều kiện để Bài toán (2.1)

có nghiệm Để nhận được kết quả như thế ta cần các giả thiết sau:

Trang 24

Giả định 2.2.1 (1) Φ là một hàm dương, lồi chính thường, nửa liên tụcdưới yếu và coercive với Dom (Φ) 6= φ.

(2) F bị chặn dưới và nửa liên tục dưới yếu Không mất tính tổng quát,

ta giả thiết F (u) ≥ 0, ∀u ∈ H

(3) F là liên tục Lipschitz khả vi Fréchet, tức là nó khả vi Fréchet vàtồn tại một hằng số L sao cho

Nhận xét 2.2.3 1 Điều kiện (3) của Giả định 2.2.1 ta có:

|F (v) − F (u) − hF0(u) , v − ui| ≤ L2kv − uk2, ∀v, u ∈ H

Thật vậy, ta có:

|F (v) − F (u) − hF0(u) , v − ui|

=

=

2 Điều kiện (4) của Giả định 2.2.1 suy ra rằng tậpEt = {u ∈ H : Φ (u) ≤ t}

là compact với mỗi t ∈ R và F0 liên tục Thật vậy, un hội tụ yếu đến u và

Θ (un) là đơn điệu giảm Khi đó, {Φ (un)}n∈N bị chặn và {un} ⊂ Et với

... (4) Giả định 2.2.1 suy tậpEt = {u ∈ H : Φ (u) ≤ t}

là compact với t ∈ R và< /sub> F0 liên tục Thật vậy, un hội tụ yếu đến u

Θ (un)