Bài toán tối ưu không trơn trong bài toán ngược và ứng dụng

ĐẠI HỌC ĐÀ NẴNG

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

TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC

Đà Nẵng - Năm 2017

Công trình được hoàn thành tại

Trường Đại học Sư phạm - ĐHĐN

Người hướng dẫn khoa học: TS. LÊ HOÀNG TRÍ

Phản biện 1: TS. LÊ VĂN DŨNG

Phản biện 2: TS. HOÀNG QUANG TUYẾN

Luận văn sẽ được bảo vệ trước Hội đồng chấm Luận văn tốt nghiệp

thạc sĩ Khoa học họp tại Trường Đại học Sư phạm - ĐHĐN vào ngày

09 tháng 09 năm 2017

Có thể tìm hiểu luận văn tại

- Trung tâm Thông tin - Học liệu, Đại học Đà Nẵng

- Thư viện trường Đại học Sư phạm, Đại học Đà Nẵng

1

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ĩnh vực

khoa học kỹ thuật thường dẫn đến nghiên cứu các bài toán tối ưu khô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 được quan tâm rất lớn và có những

bước phát triển rất mạnh trong vài thập niê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 Tikhonov thườ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ưới nhưng

không khả vi.

Đây là dạng bài toán đã được nhóm tác giả Phạm Quý Mười, Đinh Nho Hào,

Peter Maass và Michael Pidcock nghiên cứu. Một vài trường hợp cụ thể của bài

toán cũng được nghiên cứu trong luận án tiến sĩ của Phạm Quý Mười.

Về giải thuật để giải Bài toán (1), phương pháp được nghiên cứu nhiều nhất

là giải thuật giảm Gradient và các giải thuật cải tiến của nó.

Với mong muốn nghiên cứu bài toán trên cũng như một số giải thuật tì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ông trơn trong

bài toán ngược và ứng dụng”. Với đề tài này, tôi dự định nghiên cứ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.

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ác thuậ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)

2

+ 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ận vă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ết quả đ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ải thuật để

giải các bài toán tối ưu không trơn trong bài toán ngược. Luận văn có thể được

dùng làm tài liệu tham khảo cho sinh viên, học viên cao họ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 trong bài toán ngược.

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ải tích

hàm. Các tính chất, định lí được nêu ở đây chúng tôi không chứng minh. 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àm coercive.

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 trong chỉnh

hóa bài toán ngược. Nội dung chính của chương này là giới thiệu giải thuật giảm

Gradient và giải thuật cải tiến của Nesterov cũng như xem xét tốc độ hội 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ân cấp một và ví dụ

minh họa.

3

CHƯƠNG 1

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 ở đây chúng tôi không

chứng minh. 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àm

coercive. 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ướng trong

X là một ánh xạ

h., .i : X × X → R

thỏa mãn các tính chất sau đây:

(i) hy + y, zi = hx, zi + hy, zi, ∀x, y, z ∈ X,

(ii) hαx, yi = α hx, yi, ∀x, y ∈ X, ∀α ∈ R,

(iii) hx, yi = hy, xi, ∀x, y ∈ X,

(iv) hx, xi ≥ 0, ∀x ∈ X và hx, xi = 0 ⇔ x = 0.

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ết ngắ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ính chất sau:

(v) hx, y + y

0

i = hx, yi + hx, y0

i ∀x, y, y0 ∈ X,

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

Định nghĩa 1.1.3. (Chuẩn)

Cho X là một không gian vectơ trên trường số thực R. Một chuẩn trên X là

một ánh xạ

k.k : X → R

thỏa mãn các tính chất sau đây:

4

(i) kxk > 0, ∀x ∈ X, x 6= 0,

(ii) kαxk = |α| kxk, ∀x ∈ X và ∀α ∈ R,

(iii) kx + yk ≤ kxk + kyk, ∀x, y ∈ X.

Một không gian vectơ X trên R cùng với chuẩn k.k được gọi là không gian định

chuẩn trên R. Kí hiệu: (X, k.k) hoặc được viết ngắn gọn k.k nếu chuẩn được xác

định.

Đị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:

kxk := q

hx, xi, x ∈ X,

là một chuẩn.

Hơn nữa, ta có:

(iv) |hx, yi| ≤ kxk kyk, ∀x, y ∈ X (Bất đẳng thức Cauchy - Schwarz),

(v) kx ± yk

2 = kxk

2 + kyk

2 ± hx, yi, ∀x, y ∈ X,

(vi) kx + yk

2 + kx − yk

2 = 2kxk

2 + 2kyk

2

, ∀x, y ∈ X.

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ội tụ; các hàm

liên tục. Hình cầu tâm x ∈ X và bán kính r > 0 xá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ồn tại ε > 0 sao cho

K (x, ε) ⊂ M. Tập M ⊂ X được gọi là tập đóng nếu phầ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 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ại một dãy

con (xkn

)n

hội tụ đến x.

5

(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.

Đị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 ≥ c1 > 0 sao cho

c1kxk1 ≤ kxk2 ≤ c2kxk1

, ∀x ∈ X.

Định lí 1.1.9. Cho X là một không gian định chuẩn trên trường số thực R và

M ⊂ X là tập con.

(a) M là đóng nếu và chỉ nếu M = cl(M) và M là mở nếu và chỉ nếu

M = int (M).

(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.

(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, điều

ngược lại cũng đúng theo (Định lí Bolzano - Weierstrass): Trong mộ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ông gian

Banach nếu mọi dãy Cauchy đều hội tụ trong X. Một không gian tiề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:

(i) hxk, xj i = 0, ∀k 6= j.

(ii) kxkk = 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ực chuẩn

B với A ⊂ B và A 6= B.

Có thể sử dụng Bổ đề Zorn để 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ết rằ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ực chuẩn hóa.